Local approximation schemes for topology control

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: Lali Barriére , Pierre Fraigniaud , Lata Narayanan, Robust position-based routing in wireless Ad Hoc networks with unstable transmission ranges, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.19-27, July 2001, Rome, Italy [doi>10.1145/381448.381451]
• 2: Artur Czumaj , Hairong Zhao, Fault-Tolerant Geometric Spanners, Discrete & Computational Geometry, v.32 n.2, p.207-230, July 2004 [doi>10.1007/s00454-004-1121-7]
• 3: Gautam Das , Paul Heffernan , Giri Narasimhan, Optimally sparse spanners in 3-dimensional Euclidean space, Proceedings of the ninth annual symposium on Computational geometry, p.53-62, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160998]
• 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: Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan, Fast Greedy Algorithms for Constructing Sparse Geometric Spanners, SIAM Journal on Computing, v.31 n.5, p.1479-1500, 2002 [doi>10.1137/S0097539700382947]
• 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: MohammadTaghi Hajiaghayi , Nicole Immorlica , Vahab S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939016]
• 8: M. Hajiaghayi, G. Kortsarz, V.S. Mirrokni, and Z. Nutov. Power optimization for connectivity problems. In IPCO, pages 349--361, 2005.
• 9: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 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 , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073826]
• 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, 2000
• 17: Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
• 18: Yu Wang , Xiang-Yang Li, Localized construction of bounded degree and planar spanner for wireless ad hoc networks, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.59-68, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941088]
• 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Performance, Theory

Keywords:
spanners, topology control, unit ball graphs, wireless ad-hoc networks