Title: A distributed algorithm for constructing energy-balanced connected dominating set in wireless sensor networks

Authors: Zeng Yuanyuan, Jia Xiaohua, He Yanxiang

Addresses: Computer School, Wuhan University, Hubei Province, China. ' Department of Computer Science, City University of Hong Kong, Hong Kong, China. ' Computer School, Wuhan University, Hubei Province, China

Abstract: 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.

Keywords: connected dominating set; CDS; distributed algorithms; virtual backbone; wireless sensor networks; energy balance; wireless networks; network lifetime; simulation.

DOI: 10.1504/IJSNET.2007.012984

International Journal of Sensor Networks, 2007 Vol.2 No.1/2, pp.68 - 76

Published online: 02 Apr 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article