Journal of Computers, Vol 7, No 1 (2012), 11-18, Jan 2012

Leveraging 1-hop Neighborhood Knowledge for Connected Dominating Set in Wireless Sensor Networks

Wenyong Wang, Jun Zhang, Yong Tang, Yu Xiang, Ting Yang


To improve the efficiency of routing and broadcast and reducing energy consumption in the process of data transmission, calculating minimum connected dominating set is always used to construct virtual backbone network in wireless sensor networks. Calculating the minimum connected dominating set (MCDS)  of plane graphs is a NP-complete problem. In this paper, an algorithm leveraging 1-hop neighborhood knowledge for connected dominating set  is proposed. First, the minimum forwarding set is calculated severally by each node in the entire network. Then any one node can start the process of broadcasting messages including the information of minimum forwarding set in the network. Finally, the connected dominating set of the entire network is achieved by exchanging information. The proposed algorithm aims to get  a small connected dominating set, meanwhile, to minimize the consumption of energy and time. The simulation results  show that the algorithm has achieved its purpose with fast convergence, low transmission traffic and reasonable size of connected dominating set.


Wireless Sensor Networks, 1-hop, Communi- cation Coverage, Connected Dominating Set


S.C.H. Huang, M. Sun, P. Wan, X. Jia, "Interference Aware, Fully-Distributed Virtual Backbone Construction and its Application in Multi-Hop Wireless Networks", IEEE Transactions on Communications, vol.58, no.12, pp. 3550-3560, 2010.

Dai F, Wu J, "Performance analysis of broadcast protocols in adhoc networks based on self-pruning", IEEE Trans on Parallel and Distributed Systems, vol. 15,no.11, pp. 1-13, 2004.

Lee J, Mans B, "Energy-efficient virtual backbones for reception-aware MANET", Proceedings of the 63rd IEEE Vehicular Technology Conference, Melbourne: IEEE Press, 2006: 1097-1101.

L. Ruan, H. Du, X. Jia, W. Wu, Y. Li, and Ker-I Ko, "A greedy approximation for minimum connected dominating sets", Theoretical Computer Science, vol. 329, issues1–3, pp. 325–330, Dec. 2004.

S. Butenko, X. Cheng, C. Oliveira, P. M. Pardalos, "A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks", Recent Developments in Cooperative Control and Optimization, pp. 61-73, New York:Kluwer Academic Publishers, 2004.

M. Min, H. Du, X. Jia, C. Huang, S. Huang, and W. Wu, "Improving construction for connected dominating set with Steiner tree in wireless sensor networks", Journal of Global Optimization, vol.35, no.1, pp.111-119, 2006.

Lu G, Zhou MT, Tang Y, Zhao MY, Niu XZ, and She K, "Approximation algorithms for the connected dominating set problem in unit disk graphs", Journal of Electronic Science and Technology of China, vol.3, no.7, pp. 214-222, 2009.

Full Text: PDF

Journal of Computers (JCP, ISSN 1796-203X)

Copyright @ 2006-2014 by ACADEMY PUBLISHER – All rights reserved.