Constructing (k, r)-connected dominating sets for robust 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 connected k-dominating sets ((k, r)-CDS) can reduce the size of CDS and the total amount of information to be transmitted. Their multiple dominating properties can provide higher fault tolerance and robustness as well. In this paper a (k, r)-CDS construction approximation algorithm for wireless sensor and ad-hoc networks is presented. The main strategy is partition to clusters, from which the r-hop k-dominating set nodes ((k, r)-DS) are selected separately. Then (k, r)-DS are connected together to form (k, r)-CDS. Extensive simulations according to the algorithm steps have been conducted. Performance with detailed analysis has been shown at last.