A weight based backbone construction algorithm for wireless sensor network

The CDS (connected dominating set) is usually used in wireless sensor networks to construct the virtual backbone. The MCDS (minimum connected dominating set) problem is often applied to this topic but it is NP-hard. In this paper, we propose a weight based CDS construction algorithm to reduce the size of CDS. The algorithm uses one-hop information to count the weight of a node and selects the appropriate dominators based on the value of its weight. The experimental results show that our proposed algorithm with better performance, depending on the size of CDS, is more energy- efficient with the construction, and use the lower number of transmission messages.