Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks

ABSTRACT

We present a series of approximation algorithms for finding a small weakly-connected dominating set (WCDS) in a given graph to be used in clustering mobile ad hoc networks. The structure of a graph can be simplified using WCDS's and made more succinct for routing in ad hoc networks. The theoretical performance ratio of these algorithms is O(ln Δ) compared to the minimum size WCDS, where Δ is the maximum degree of the input graph. The first two algorithms are based on the centralized approximation algorithms of Guha and Khuller cite guha-khuller-1998 for finding small connected dominating sets (CDS's). The main contribution of this work is a completely distributed algorithm for finding small WCDS's and the performance of this algorithm is shown to be very close to that of the centralized approach. Comparisons between our work and some previous work (CDS-based) are also given in terms of the size of resultant dominating sets and graph connectivity degradation.

REFERENCES

• 1: B. Khan, Routing Through Networks with Hierarchical Topology Aggregation, Proceedings of the Third IEEE Symposium on Computers & Communications, p.406, June 30-July 02, 1998
• 2: Dennis Baker, Anthony Ephremides, and Julia A. Flynn. The design and simulation of a mobile radio network with distributed control. IEEE Journal on Selected Areas in Communications, SAC-2(1):226--237, 1984.
• 3: S. Banerjee and S. Khuller. A clustering scheme for hierarchical routing in wireless networks. Technical Report CS-TR-4103, University of Maryland, College Park, February 2000.
• 4: Stefano Basagni, Distributed Clustering for Ad Hoc Networks, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), p.310, June 23-25, 1999
• 5: Christian Bettstetter , Roland Krausser, Scenario-based stability anlysis of the distributed mobility-adaptive clustering (DMAC) algorithm, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501448]
• 6: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 7: Geng Chen and Ivan Stojmenovic. Clustering and routing in mobile wireless networks. Technical Report TR-99-05, SITE, June 1999.
• 8: Imrich Chlamtac , András Faragó, A new approach to the design and analysis of peer-to-peer mobile networks, Wireless Networks, v.5 n.3, p.149-156, May 1999 [doi>10.1023/A:1019186624837]
• 9: Bevan Das and Vaduvur Bharghavan. Routing in ad-hoc networks using minimum connected dominating sets. In IEEE International Conference on Communications (ICC'97), June 1997.
• 10: Jean E. Dunbar , Jerrold W. Grossman , Johannes H. Hattingh , Stephen T. Hedetniemi , Alice A. McRae, On weakly connected domination in graphs, Discrete Mathematics, 167-168, p.261-269, April 15, 1997 [doi>10.1016/S0012-365X(96)00233-6]
• 11: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 14: Sudipto Guha and Samir Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374--387, 1998.
• 15: Teresa W. Haynes, Stephen T. Hedetniemi, and Peter J. Slater. Fundamentals of Domination in graphs. Marcel Dekker, Inc., 1998.
• 16: P. Krishna , N. H. Vaidya , M. Chatterjee , D. K. Pradhan, A cluster-based approach for routing in dynamic networks, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.49-64, Apr. 1997 [doi>10.1145/263876.263885]
• 17: Elizabeth M. Royer and Chai-Keong Toh. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Personal Communications, pages 46--55, 4 1999.
• 18: Jie Wu and Hailan Li. On calculating connected dominating set for efficient routing in ad

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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

General Terms:
Algorithms, Experimentation

Keywords:
ad hoc network, clustering, distributed algorithm, dominating set, weakly-connected dominating set