Message-optimal connected dominating sets in mobile ad hoc networks

ABSTRACT

A connected dominating set (CDS) for a graph G(V,E) is a subset V¹ of V, such that each node in V--V¹ is adjacent to some node in V¹, and V¹ induces a connected subgraph. A CDS has been proposed as a virtual backbone for routing in wireless ad hoc networks. However, it is NP-hard to find a minimum connected dominating set (MCDS). Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a very poor approximation ratio, and from high time complexity and message complexity. Recently, new distributed heuristics for constructing a CDS were developed, with constant approximation ratio of 8. These new heuristics are based on a construction of a spanning tree, which makes it very costly in terms of communication overhead to maintain the CDS in the case of mobility and topology changes.In this paper, we propose the first distributed approximation algorithm to construct a MCDS for the unit-disk-graph with a emph constant approximation ratio, and emph linear time and emph linear message complexity. This algorithm is fully localized, and does not depend on the spanning tree. Thus, the maintenance of the CDS after changes of topology guarantees the maintenance of the same approximation ratio. In this algorithm each node requires knowledge of its single-hop neighbors, and only a constant number of two-hop and three-hop neighbors. The message length is O( log n) bits.

REFERENCES

• 1: K. M. Alzoubi, P.-J. Wan, O. Frieder, "Distributed Heuristics for Connected Dominating Set in Wireless Ad Hoc Networks", to appear in Journal on Communication Networks, 2002.
• 2: V. Bharghavan and B. Das, "Routing in Ad Hoc Networks Using Minimum Connected Dominating Sets", International Conference on Communications'97, Montreal, Canada. June 1997.
• 3: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 4: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 5: R. Sivakumar, B. Das, and V. Bharghavan, "An Improved Spine-based Infrastructure for Routing in Ad Hoc Networks", IEEE Symposium on Computers and Communications '98, Athens, Greece. June 1998.
• 6: I. Stojmenovic1 , M. Seddigh , J. Zunic, Internal Nodes based Broadcasting in Wireless Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9005, January 03-06, 2001
• 7: P.-J. Wan, K. M. Alzoubi, O. Frieder, "Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks", to appear in IEEE INFOCOM 2002.
• 8: 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]

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Performance

Keywords:
ad hoc networks, connected dominating set, independent set, maximal, mobility