Constructing r-Hop 2-Connected Dominating Sets for Fault-Tolerant Backbone in Wireless Sensor Networks

Connected dominated subsets (CDS) of nodes in wireless sensor network are always selected to form a virtual backbone. Construction of r-hop 2-connected dominating sets can reduce the size of CDS and the total amount of information to be transmitted. The 2-connected properties can provide higher fault tolerance and robustness as well. In this paper an approximation r-hop 2-connected dominating set algorithm for wireless sensor and ad-hoc networks is presented. The main strategy is partition to three phases: in the first phase, an r-hop independent dominating set is established; in the second phase, the r-hop dominating set is interconnected successively to form a connected subgraph; in the third phase, more vertices are selected and added into dominating set to make it 2-connected. Extensive simulations according to the algorithm steps have been conducted. Performance with detailed analysis has been shown at last.