Construction of a Fault Tolerance Connected Dominating Set in Wireless Sensor Network

In wireless sensor networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to construct a small virtual backbone for high efficiency, which is modeled as the minimum Connected Dominating Set (MCDS) problem. However, the nodes in the CDS need to carry other nodespsila traffic and they are subject to failure. Therefore, it is desirable to construct a fault tolerant CDS. In this paper, we first propose a distributed algorithm to construct a connected dominating set (DACDS). Based on DACDS, we further develop a fault tolerant algorithm (kCDS). We also show our algorithm have better performance ratios and low message complexity.