article

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

Authors:

Stefan Funke,

Alexander Kesselman,

Ulrich Meyer,

Michael SegalAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 2, Issue 3

Pages 444 - 453

https://doi.org/10.1145/1167935.1167941

Published: 01 August 2006 Publication History

Get Access

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]

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).

Crossref

Google Scholar

[2]

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).

Crossref

Google Scholar

[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.

Google Scholar

[4]

Clark, B., Colbourn, C., and Johnson, D. 1990. Unit disk graphs. Discr. Math. 86, 165--177.

Crossref

Google Scholar

[5]

Fejes Tóth, L. 1942-1943. Über die dichteste Kugellagerung. Math. Zeit. 48, 676--684.

Google Scholar

[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.

Google Scholar

[7]

Luby, M. 1986. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 4, 1036--1053.

Crossref

Google Scholar

[8]

Luby, M. 1993. Removing randomness in parallel computation without a processor penalty. J. Comput. Syst. Sci. 47, 2, 250--286.

Crossref

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

Cited By

View all

Xu SWang CYang Y(2024)A Survey on Variant Domination Problems in Geometric Intersection GraphsParallel Processing Letters10.1142/S012962642340018234:01Online publication date: 17-Jan-2024
https://doi.org/10.1142/S0129626423400182
Wang JLiang JLi Q(2024)On construction of quality virtual backbone in wireless networks using cooperative communicationComputer Communications10.1016/j.comcom.2024.107952(107952)Online publication date: Sep-2024
https://doi.org/10.1016/j.comcom.2024.107952
Wang CYang YXu S(2023)Secure connected domination and secure total domination in unit disk graphs and rectangle graphsTheoretical Computer Science10.1016/j.tcs.2023.113824957(113824)Online publication date: May-2023
https://doi.org/10.1016/j.tcs.2023.113824
Show More Cited By

Index Terms

A simple improved distributed algorithm for minimum CDS in unit disk graphs
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

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 Simulation

In 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 2, Issue 3

August 2006

157 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/1167935

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 August 2006

Published in TOSN Volume 2, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

129
Total Citations
View Citations
1,033
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xu SWang CYang Y(2024)A Survey on Variant Domination Problems in Geometric Intersection GraphsParallel Processing Letters10.1142/S012962642340018234:01Online publication date: 17-Jan-2024
https://doi.org/10.1142/S0129626423400182
Wang JLiang JLi Q(2024)On construction of quality virtual backbone in wireless networks using cooperative communicationComputer Communications10.1016/j.comcom.2024.107952(107952)Online publication date: Sep-2024
https://doi.org/10.1016/j.comcom.2024.107952
Wang CYang YXu S(2023)Secure connected domination and secure total domination in unit disk graphs and rectangle graphsTheoretical Computer Science10.1016/j.tcs.2023.113824957(113824)Online publication date: May-2023
https://doi.org/10.1016/j.tcs.2023.113824
Levin M(2022)Note on Dominating Set ProblemsJournal of Communications Technology and Electronics10.1134/S106422692113004066:S1(S8-S22)Online publication date: 24-Mar-2022
https://doi.org/10.1134/S1064226921130040
Gorain BMondal KPandit S(2022)Distributed Dominating Sets in Interval GraphsComputing and Combinatorics10.1007/978-3-031-22105-7_45(508-520)Online publication date: 22-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-22105-7_45
Gorain BMondal KPandit S(2022)Distributed Connected Dominating Sets in Unit Square and Disk GraphsTheory and Applications of Models of Computation10.1007/978-3-031-20350-3_28(346-358)Online publication date: 16-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-20350-3_28
Liang XLiang JZhang W(2021) Constructing d -Robust Connected Dominating Sets in Wireless Sensor Networks With Unstable Transmission Ranges IEEE Transactions on Communications10.1109/TCOMM.2020.303093069:1(398-415)Online publication date: Jan-2021
https://doi.org/10.1109/TCOMM.2020.3030930
Hong YLi DChen Z(2021)Constructing virtual backbone with guaranteed routing cost in Wireless Sensor NetworksAd Hoc Networks10.1016/j.adhoc.2021.102500116(102500)Online publication date: May-2021
https://doi.org/10.1016/j.adhoc.2021.102500
Alphonse PSivaraj CJanakiraman T(2020)An Energy-Efficient Layered Clustering Algorithm for Routing in Wireless Sensor NetworksSensor Technology10.4018/978-1-7998-2454-1.ch012(238-262)Online publication date: 2020
https://doi.org/10.4018/978-1-7998-2454-1.ch012
Liang JYi MZhang WLi YLiang XQin B(2020)On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc NetworksComplexity10.1155/2020/91896452020Online publication date: 24-Feb-2020
https://dl.acm.org/doi/10.1155/2020/9189645
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs

Timer-Based CDS Construction in Wireless Ad Hoc Networks

A Highly Efficient Distributed Algorithm for Constructing CDS in Wireless Ad Hoc Networks with Partial Neighborhood Notification