Stefan Funke
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.
- Alzoubi, K. M. 2003. Connected dominating set and its induced position less sparse spanner for mobile ad hoc networks. In Proceedings of the 8th IEEE International Symposium on Computers and Communication (ISCC '03). Google Scholar
- Alzoubi, K. M., Wan, P. J., and Frieder, O. 2003. Weakly-connected dominating sets and sparse spanners in wireless ad hoc networks. In Proceedings of the 23rd International Confererence on Distributed Computing Systems (ICDCS '03). Google Scholar
- 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.Google Scholar
- Clark, B., Colbourn, C., and Johnson, D. 1990. Unit disk graphs. Discr. Math. 86, 165--177. Google Scholar
- Fejes Tóth, L. 1942-1943. Über die dichteste Kugellagerung. Math. Zeit. 48, 676--684.Google Scholar
- 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.Google Scholar
- Luby, M. 1986. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 4, 1036--1053. Google Scholar
- Luby, M. 1993. Removing randomness in parallel computation without a processor penalty. J. Comput. Syst. Sci. 47, 2, 250--286. Google Scholar
- 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.Google Scholar
- Wan, P. J., Alzoubi K., and Frieder, O. 2002. Distributed construction of connected dominating set in wireless ad hoc networks. In Proceedings of INFOCOM.Google Scholar
Index Terms
- A simple improved distributed algorithm for minimum CDS in unit disk graphs
Recommendations
Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs
Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority of ...
Timer-Based CDS Construction in Wireless Ad Hoc Networks
The connected dominating set (CDS) has been extensively used for routing and broadcast in wireless ad hoc networks. While existing CDS protocols are successful in constructing CDS of small size, they either require localized information beyond immediate ...
A Highly Efficient Distributed Algorithm for Constructing CDS in Wireless Ad Hoc Networks with Partial Neighborhood Notification
UKSIM '15: Proceedings of the 2015 17th UKSIM-AMSS International Conference on Modelling and SimulationIn this paper, an efficient distributed algorithm is proposed to construct connected dominating set (CDS) in wireless ad hoc networks. In existing algorithms, nodes exchange their entire local topology via beacon messages with each other, which will ...
Comments