A reliable connected dominating set algorithm in wireless sensor networks

作者：Li Yaqian; Yin Rongrong^*; Liu Haoran; Hao Xiaochen

来源：Journal of Computational Information Systems, 2012, 8(6): 2583-2592.

• Area-fault-rate
• CdS
• Connected Dominating Set
• Connected dominating set algorithms
• Connected dominating sets
• Constant factors
• Guaranteed quality
• Minimum weight
• Optimum networks
• Reliability optimization
• Virtual backbone

The connected dominating set (CDS) has been proposed as a virtual backbone or routing to alleviate the broadcasting storm problem in wireless sensor networks. Since the nodes in CDS need to carry other node's traffic, it is desirable that the CDS is reliable. In this paper, we define the concepts of area-fault-rate as a weight to select dominator. Then it is proved that the reliability optimization for CDS is a minimum weight connected dominating set (MWCDS) problem. Therefore, an algorithm of MWCDS called RCDS is proposed. The results show that (1) the RCDS has guaranteed quality by proving that its total weight is within a small constant factor of the optimum networks; (2) the RCDS network has a smaller backbone, a smaller total weight, as well as a longer lifetime.

• 出版日期2012