A distributed algorithm for constructing energy-balanced Connected Dominating Set in wireless sensor networks

One important characteristic of wireless sensor networks is stringent energy of sensor nodes. Constructing a Connected Dominating Set (CDS) as the backbone has been widely used as a topology control strategy to reduce the network communication overhead for wireless ad hoc and sensor networks. Previous methods are mostly designed to minimise the size of the backbone. However, the backbone nodes are easy to fall short of power and fail due to the heavy communication load. In this paper, we present a distributed energy-balanced CDS algorithm to balance energy consumption of the sensor nodes and prolong the network lifetime. The algorithm is with O(n) time complexity and O(n) message complexity. The simulation results show that our algorithm outperforms several existing algorithms in terms of network lifetime and CDS performance. © 2007 Inderscience Enterprises Ltd.