skip to main content
10.1145/1146381.1146413acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Local approximation schemes for topology control

Published: 23 July 2006 Publication History

Abstract

This paper presents a distributed algorithm for wireless ad-hoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a lightweight, linear size, (1+ε)-spanner for any given ε > 0. A wireless network is modeled by a d-dimensional α-quasi unit ball graph (α-UBG), which is a higher dimensional generalization of the standard unit disk graph (UDG) model. The d-dimensional α-UBG model goes beyond the unrealistic "flat world" assumption of UDGs and also takes into account transmission errors, fading signal strength, and physical obstructions. The main result in the paper is this: for any fixed ε > 0, 0 < α ≤ 1, and d ≥ 2 there is a distributed algorithm running in O(log n•log* n) communication rounds on an n-node, d-dimensional α-UBG G that computes a (1+ε)-spanner G' of G with maximum degree Δ(G') = O(1) and total weight w(G') = O(w(MST(G)). This result is motivated by the topology control problem in wireless ad-hoc networks and improves on existing topology control algorithms along several dimensions. The technical contributions of the paper include a new, sequential, greedy algorithm with relaxed edge ordering and lazy updating, and clustering techniques for filtering out unnecessary edges.

References

[1]
L. Barriére, P. Fraigniaud, and L. Narayanan. Robust position-based routing in wireless ad hoc networks with unstable transmission ranges. In Proc. of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pages 19--27, 2001.
[2]
A. Czumaj and H. Zhao. Fault-tolerant geometric spanners. Discrete & Computational Geometry, 32(2):207--230, 2004.
[3]
G. Das, P. Heffernan, and G. Narasimhan. Optimally sparse spanners in 3-dimensional Euclidean space. In SCG '93: Proc. of the ninth annual symposium on Computational geometry, pages 53--62, New York, NY, USA, 1993. ACM Press.
[4]
G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geometry Appl., 7(4):297--315, 1997.
[5]
J. Gudmundsson, C. Levcopoulos, and G. Narasimhan. Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput., 31(5):1479--1500, 2002.
[6]
M. Hajiaghayi, N. Immorlica, and V. S. Mirrokni. Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks. In Proc. of the 11th IEEE International Conference on Computer Communications and Networks (IC3N), pages 392--398, 2002.
[7]
M. Hajiaghayi, N. Immorlica, and V. S. Mirrokni. Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. In Proc. of the 9th annual international conference on Mobile computing and networking (MobiCom), pages 300--312, 2003.
[8]
M. Hajiaghayi, G. Kortsarz, V.S. Mirrokni, and Z. Nutov. Power optimization for connectivity problems. In IPCO, pages 349--361, 2005.
[9]
B. Karp and H. T. Kung. Greedy perimeter stateless routing for wireless networks. In Proc. of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), pages 243--254, 2000.
[10]
David Kotz, Calvin Newport, and Chip Elliot. The mistaken axioms of wireless-network research. Technical Report TR2003-467, Dartmouth College, Department of Computer Science, 2003.
[11]
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. On the locality of bounded growth. In Proc. of the 24th ACM Symposium on the Principles of Distributed Computing (PODC), pages 60--68, 2005.
[12]
C. Levcopoulos and A. Lingas. There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees. Algorithmica, 8:251--256, 1992.
[13]
X. Y. Li, G. Calinescu, and P. Wan. Distributed construction of planar spanner and routing for ad hoc wireless networks. In Proc. of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2002.
[14]
X. Y. Li, G. Calinescu, P. J. Wan, and Y. Wang. Localized delaunay triangulation with application in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst., 14(10):1035--1047, 2003.
[15]
Xiang-Yang Li and Yu Wang. Efficient construction of low weighted bounded degree planar spanner. International Journal of Computational Geometry and Applications, 14(1--2):69--84, 2004.
[16]
David Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.
[17]
R. Rajaraman. Topology control and routing in ad hoc networks: A survey. SIGACT News, 33:60--73, 2002.
[18]
Y. Wang and X. Y. Li. Localized construction of bounded degree and planar spanner for wireless ad hoc networks. In Proceedinngs of the Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pages 59--68, 2003.
[19]
R. Wattenhofer and A. Zollinger. XTC: A practical topology control algorithm for ad-hoc networks. In 4th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), 2004.
[20]
A.C.-C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721--736, 1982.

Cited By

View all
  • (2023)TFACR: A Novel Topology Control Algorithm for Improving 5G-Based MANET Performance by Flexibly Adjusting the Coverage RadiusIEEE Access10.1109/ACCESS.2023.331888011(105734-105748)Online publication date: 2023
  • (2015)Bounding interference in wireless ad hoc networks with nodes in random positionIEEE/ACM Transactions on Networking10.1109/TNET.2014.231362723:4(1078-1091)Online publication date: 1-Aug-2015
  • (2012)Local Construction of Spanners in the 3D SpaceIEEE Transactions on Mobile Computing10.1109/TMC.2011.14211:7(1140-1150)Online publication date: 1-Jul-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. spanners
  2. topology control
  3. unit ball graphs
  4. wireless ad-hoc networks

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)TFACR: A Novel Topology Control Algorithm for Improving 5G-Based MANET Performance by Flexibly Adjusting the Coverage RadiusIEEE Access10.1109/ACCESS.2023.331888011(105734-105748)Online publication date: 2023
  • (2015)Bounding interference in wireless ad hoc networks with nodes in random positionIEEE/ACM Transactions on Networking10.1109/TNET.2014.231362723:4(1078-1091)Online publication date: 1-Aug-2015
  • (2012)Local Construction of Spanners in the 3D SpaceIEEE Transactions on Mobile Computing10.1109/TMC.2011.14211:7(1140-1150)Online publication date: 1-Jul-2012
  • (2012)Distributed computation of coverage in sensor networks by homological methodsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-012-0167-723:1-2(29-58)Online publication date: 1-Apr-2012
  • (2012)Bounding interference in wireless ad hoc networks with nodes in random positionProceedings of the 19th international conference on Structural Information and Communication Complexity10.1007/978-3-642-31104-8_8(85-98)Online publication date: 30-Jun-2012
  • (2011)Separability and topology control of quasi unit disk graphsWireless Networks10.1007/s11276-010-0264-017:1(53-67)Online publication date: 1-Jan-2011
  • (2010)A new distributed topology control algorithm for wireless environments with non-uniform path loss and multipath propagationAd Hoc Networks10.1016/j.adhoc.2009.09.0018:3(280-294)Online publication date: 1-May-2010
  • (2010)Vietoris---Rips Complexes of Planar Point SetsDiscrete & Computational Geometry10.1007/s00454-009-9209-844:1(75-90)Online publication date: 1-Jul-2010
  • (2009)Remote-spannersProceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing10.1109/IPDPS.2009.5161041(1-10)Online publication date: 23-May-2009
  • (2009)Distributed construction of low-interference spannersDistributed Computing10.1007/s00446-009-0083-722:1(15-28)Online publication date: 1-Apr-2009
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media