Energy efficient distributed connected dominating sets construction in wireless sensor networks

ABSTRACT

One important characteristic of wireless sensor networks is energy stringency. Constructing a connected dominating set (CDS) has been widely used as a topology control strategy to reduce the network communication overhead. In the paper, a novel energy efficient distributed connected dominating set algorithm based on coordinated reconstruction mechanism is presented to further prolong the network lifetime and balance energy consumption. 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.

References

1. Pottie, G. J. and Kaiser, W .J. Wireless integrated network sensors. Communications of ACM, Vol. 43, No. 5, May 2000, 51--58.
2. Akyildiz, IF, Su, W., Sankarasubramaniam, Y., and Cayirci, E. A survey on sensor networks. IEEE Communications Magazine, vol. 40, no.8, 2002, 102--114.
3. Clark, B. N., Colbourn, C.J., and Johnson, D. S. Unit disk graphs. Discrete Mathematics, Vol. 86, 1990, 165--177.
4. Wan, P. J., Alzoubi, K. and Frieder, O. Distributed well connected dominating set in wireless ad hoc networks. In Proc. IEEE INFOCOM,2002.
5. Alzoubi, K., Wan, P. J., Frieder, O. New distributed algorithm for connected dominating set in wireless Ad Hoc networks. In Proc. 35th Hawaii Int'1 Conf, 2000,3881--3887.
6. Wu, J. and Li, H. On calculating connected dominating set for efficient routing in ad hoc wireless networks. In Proc. the 3rd ACM Int'l workshop Disc. Algor. and Methods for Mobile Computing and Commun., 1999,7--14.
7. Butenko, S., Cheng, X., Oliveira, C.A.S, and Pardalos, P. M. A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks. Cooperative Control and Optimization, 2004,61--73.
8. Min, M., Huang, C. X., Huang, S. C.-H., Wu, W., Du, H. and Jia, X. Improving construction for connected dominating set with Steiner tree in wireless sensor networks. Global Optimization, 2004.
9. Wu, J., Dai, F., Gao, M., and Stojmenovic, I. On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks. In Proc. IEEE Int'l ICPP, 2001,346--356.
10. Acharya, T. and Roy, R. Distributed Algorithm for Power Aware Minimum Connected Dominating set for Routing in Wireless Ad Hoc Networks. In Proc. ICPP Workshops, ,2005,387--394.
11. Wu, W., Du, H., Jia, X., Li, Y., Huang, C.-H., Du, D-Z. Minimum connected dominating sets and maximal independent sets in unit disk graphs. technical report 04-047, Department of Computer Science and Engineering, University of Minnesota, 2004.

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks