Construction algorithms for k-connected m-dominating sets in wireless sensor networks

ABSTRACT

A Connected Dominating Set (CDS) working as a virtual backbone is an effective way to decrease the overhead of routing in a wireless sensor network. Furthermore, a k-Connected m-Dominating Set (kmCDS) is necessary for fault tolerance and routing flexibility. Some approximation algorithms have been proposed to construct a kmCDS. However, most of them only consider some special cases where k = 1,2 or k ≤ m, or are not easy to implement, or have high message complexity. In this paper, we propose a novel distributed algorithm LDA with low message complexity to construct a kmCDS for general k and m whose size is guaranteed to be within a small constant factor of the optimal solution when the maximum node degree is a constant. We also propose one centralized algorithm ICGA with a constant performance ratio to construct a kmCDS. Theoretical analysis as well as simulation results are shown to evaluate the proposed algorithms.

REFERENCES

• 1: Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]
• 2: B. Das and V. Bharghavan, Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets, Proc. IEEE Intl. Conf. Comm., 1997.
• 3: K. Alzoubi , P.-J. Wan , O. Frieder, New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.297, January 07-10, 2002
• 4: Fei Dai , Jie Wu, An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.908-920, October 2004 [doi>10.1109/TPDS.2004.48]
• 5: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, Wireless Networks, v.8 n.5, p.481-494, September 2002 [doi>10.1023/A:1016542229220]
• 6: P.-J. Wan, K. M. Alzoubi and O. Frieder, Distributed Construction of Connected Dominating Sets in Wireless Ad Hoc Networks, IEEE INFOCOM, 2002.
• 7: Y. Li, S. Zhu, My T. Thai, and D.-Z. Du, Localized Construction of Connected Dominating Set in Wireless Networks, NSF International Workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor and Peer-to-Peer Networks, Chicago, June 2004.
• 8: Xiuzhen Cheng , Min Ding , David Hongwei Du , Xiaohua Jia, Virtual backbone construction in multihop ad hoc wireless networks: Research Articles, Wireless Communications & Mobile Computing, v.6 n.2, p.183-190, March 2006 [doi>10.1002/wcm.v6:2]
• 9: Fei Dai , Jie Wu, On Constructing k-Connected k-Dominating Set in Wireless Networks, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.81.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.302]
• 10: F. Wang, M. T. Thai, D.-Z. Du, 2-connected Virtual Backbone in Wireless Network, Accpeted by IEEE Transactions on Wireless Communications, 2007.
• 11: W. Shang, F. Yao, P. Wan, and X. Hu, Algorithms for Minimum m-Connected k-Dominating Set Problem, COCOA 2007, LNCS 4616, pp. 182--190, 2007.
• 12: My T. Thai , Ning Zhang , Ravi Tiwari , Xiaochun Xu, On approximation algorithms of k-connected m-dominating sets in disk graphs, Theoretical Computer Science, v.385 n.1-3, p.49-59, October, 2007 [doi>10.1016/j.tcs.2007.05.025]
• 13: Y. Wu, F. Wang, M. T. Thai and Y. Li, Constructing k-Connected m-Dominating Sets in Wireless Sensor Networks, Military Communications Conference, Orlando, FL, October 29-31, 2007.
• 14: D. Kim, Y. Wu, Y. Li, F. Zou and D.-Zhu Du, Constructing Energy Efficient Connected Dominating Sets with Bounded Diameters in Wireless Networks, submitted to IEEE Transactions on Parallel and Distributed Systems, 2007.
• 15: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 16: D. B. West, Introduction to Graph Theory (Second Edition), Prentice-Hall, Inc. ISBN 0-13-014400-2, 2001.
• 17: Joseph Cheriyan, Fast algorithms for k-shredders and k-node connectivity augmentation, Journal of Algorithms, v.33 n.1, p.15-50, Oct. 1999 [doi>10.1006/jagm.1999.1040]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
connected dominating set, fault-tolerance, k-connected m-dominating set, localized algorithm, wireless sensor networks