Local Approximation Schemes for Topology Control

Simple item page
dc.creatorDamian, Mirela
dc.creatorPandit, Saurav
dc.creatorPemmaraju, Sriram
dc.date2008-03-14
dc.date.accessioned2026-07-07T09:26:53Z
dc.date.available2026-07-07T09:26:53Z
dc.descriptionThis paper presents a distributed algorithm on wireless ad-hoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a linear size, lightweight, (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 < α\le 1, and d \ge 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.
dc.description11 pages, 6 figures
dc.identifierhttps://arxiv.org/abs/0803.2174
dc.identifierhttp://arxiv.org/abs/0803.2174
dc.identifierProceedings of the 25th ACM Symposium on Principles of Distributed Computing, pages 208-218, July 2006
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/156912
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.subjectC.2.4; F.2.2
dc.titleLocal Approximation Schemes for Topology Control
dc.typetext

Files

Collections

arXiv