A Power Aware Minimum Connected Dominating Set for Wireless Sensor Networks
Mritunjay Rai, Shekhar Verma, Shashikala Tapaswi · Journal of Networks · 2009
Abstract- Connected Dominating Set (CDS) problem in unit disk graph has a significant impact on an efficient design of routing protocols in wireless sensor networks. In this paper, an algorithm is proposed for finding Minimum Connected Dominating Set (MCDS) using Dominating Set. Dominating Sets are connected by using Steiner tree. The algorithm goes through three phases. In first phase Dominating Sets are found, in second phase connectors are identified, connected through Steiner tree. In third phase the CDS obtained in second phase is pruned to obtain a MCDS. MCDS so constructed needs to adapt to the continual topology changes due to deactivation of a node due to exhaustion of battery power. These topological changes due to power constraints are taken care by a local repair algorithm that reconstructs the MCDS i.e. Power Aware MCDS, using only neighbourhood information. Simulation results indicate both the heuristics are very efficient and result in near optimal MCDS. Index Terms- Connected Dominating Set, topology, virtual backbone, wireless sensor networks. away from an element of the subset forms a dominating set S. A connected dominating set (CDS) C of G is a dominating set S in which all the elements are connected i.e. it induces a connected graph. The nodes in C are called dominators and the other nodes which are one hop away from C are dominatees. To minimize the number of hops, the minimum CDS is chosen as the backbone.. The backbone is the smallest CDS and every node is adjacent to this virtual backbone. Once data is received by a dominator, it is relayed through the MCDS towards the sink for minimum hop communication. Since the nodes have equal transmission range, the CDS has to be determined for Unit Disk Graph (UDG). The figures of CDS backbone and its UDG can be shown in Figure 1a and in figure 1b respectively. The problem is known to be NP-hard and requires heuristics for the determination of the CDS [2].