Local Approximation Schemes for Topology Control

Details Local Approximation Schemes for Topology Control Local Approximation Schemes for Topology Control

2008-03-14

arxiv.org/abs/0803.2174v1

Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, pages 208-218, July 2006

Computer Science

Data Structures and Algorithms

11 pages, 6 figures

Scientific paper

This 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+\epsilon)-spanner for any given \epsilon > 0. A wireless network is modeled by a d-dimensional \alpha-quasi unit ball graph (\alpha-UBG), which is a higher dimensional generalization of the standard unit disk graph (UDG) model. The d-dimensional \alpha-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 \epsilon > 0, 0 < \alpha \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 \alpha-UBG G that computes a (1+\epsilon)-spanner G' of G with maximum degree \Delta(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.

Affiliated with

Also associated with

No associations

Rating

Local Approximation Schemes for Topology Control does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Local Approximation Schemes for Topology Control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local Approximation Schemes for Topology Control will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-246845