A simple improved distributed algorithm for minimum CDS in unit disk graphs

ABSTRACT

Several routing schemes in ad hoc networks first establish a virtual backbone and then route messages via backbone nodes. One common way of constructing such a backbone is based on the construction of a connected dominating set (CDS). In this article we present a very simple distributed algorithm for computing a small CDS. Our algorithm has an approximation factor of at most 6.91, improving upon the previous best-known approximation factor of 8 due to Wan et al. [2002]. The improvement relies on a refined analysis of the relationship between the size of a maximal independent set and a minimum CDS in a unit disk graph. This subresult also implies improved approximation factors for many existing algorithm.

REFERENCES

• 1: Khaled M. Alzoubi, Connected Dominating Set and its Induced Position-less Sparse Spanner For Mobile Ad Hoc Networks, Proceedings of the Eighth IEEE International Symposium on Computers and Communications, p.209, June 30-July 03, 2003
• 2: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Weakly-Connected Dominating Sets and Sparse Spanners in Wireless Ad Hoc Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.96, May 19-22, 2003
• 3: Cheng, X., Huang, X., Li, D., and Du, D.-Z. 2006. Polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks. To appear.
• 4: 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]
• 5: Fejes Tóth, L. 1942-1943. Über die dichteste Kugellagerung. Math. Zeit. 48, 676--684.
• 6: Gandhi, R. and Parthasarathy, S. 2004. Fast distributed well connected dominating sets for ad hoc networks. Tech. rep. CS-TR-4559. Computer Science Department, University of Maryland, College Park, MD.
• 7: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 8: Michael Luby, Removing randomness in parallel computation without a processor penalty, Journal of Computer and System Sciences, v.47 n.2, p.250-286, Oct. 1993 [doi>10.1016/0022-0000(93)90033-S]
• 9: Marathe, M. V., Breu, H., Hunt III, H. B., Ravi, S. S., and Rosenkrantz, D. J. 1995. Simple heuristics for unit disk graphs. Networks 25, 59--68.
• 10: Wan, P. J., Alzoubi K., and Frieder, O. 2002. Distributed construction of connected dominating set in wireless ad hoc networks. In Proceedings of INFOCOM.

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, Theory

Keywords:
Connected dominating set, algorithms, unit disk graphs