Randomized and Optimal Algorithms for <italic>k</italic>-Lifetime Dominating Set in Wireless Sensor Networks

Abstract

In wireless sensor networks, rotating dominating set is an efficient method for balancing the energy consumption of nodes, and thereby extending the network operational time. This method can be abstracted as $k$ -Lifetime Dominating Set in bipartite graph, that partitions the set of graph vertices representing sensors into $k$ disjoint dominating sets. However, the considered problem has been proven to be NP-hard, and there is no hope of solving it in polynomial time unless P = NP. Existing studies mainly focus on developing approximation or heuristic algorithms, which usually cannot guarantee a solution for a given problem yes instance. In this study, we first propose a randomized algorithm that can generate a solution with guaranteed probability 1- $\varepsilon $ ( $0 < \varepsilon < 1$ ). Using the color coding method, we show that the randomized algorithm can be improved to guarantee the generation of a solution for a given problem yes instance in exponential time. Based on the idea of randomized partition, we further present a more practical centralized greedy algorithm, and then a distributed implementation. Simulation results indicate that the centralized algorithm can efficiently generate optimal solutions for almost all the given problem instances if the partition redundancy is above a certain limit. Compared with existing algorithm, the centralized algorithm increases the number of dominating sets by factors between 0% and 21%.

Keywords

• Dominating set
• NP-hard
• color coding
• random partition
• optimal algorithms