Distributed construction of bounded-degree low-interference spanners of low weight

ABSTRACT

We propose a new low-interference topology for wireless ad hoc networks modeled by Quasi Unit Disk Graphs (qUDGs). Our topology combines two existing structures, the relaxed Greedy structure developed by Damian, Pandit and Pemmaraju, and the low-interference structure developed by Burkhart, von Rickenbach, Wattenhofer and Zollinger. Our main contribution is showing that, when applied on a qUDG G = (V, E), this new structure inherits most properties of the two underlying structures: (a) it is a t(1+ε) spanner of G, for any t > 1 and ε > 0, (ii) it has optimal interference among all t-spanners for G, (iii) it has O(1) maximum degree, (iv) its total weight is within a factor of O(log n) of the weight of a minimum spanning tree for V, and (v) it can be implemented efficiently in O(log n) rounds of communication.

REFERENCES

• 1: Friedhelm Meyer auf de Heide , Christian Schindelhauer , Klaus Volbert , Matthias Grünewald, Energy, congestion and dilation in radio networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564910]
• 2: Martin Burkhart. Analysis of interference in ad hoc networks. In Diploma Thesis, Distributed Computing Group, Swiss Federal Institute of Technology Zurich, 2003.
• 3: Martin Burkhart , Pascal von Rickenbach , Roger Wattenhofer , Aaron Zollinger, Does topology control reduce interference?, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989462]
• 4: 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]
• 5: Mirela Damian , Saurav Pandit , Sriram Pemmaraju, Local approximation schemes for topology control, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146413]
• 6: Gautam Das and Giri Narasimhan. A fast algorithm for constructing sparse euclidean spanners. Int. J. Comput. Geometry Appl., 7(4):297--315, 1997.
• 7: David Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 425--461, Amsterdam, 2000. Elsevier Science.
• 8: Joachim Gudmundsson and Christian Knauer. Dilation and detours in geometric networks. In T. F. Gonzalez, editor, Handbook on Approximation Algorithms and Metaheuristics, Boca Raton, 2006. Chapman & Hall/CRC.
• 9: Yehuda Hassin , David Peleg, Sparse communication networks and efficient routing in the plane, Distributed Computing, v.14 n.4, p.205-215, December 2001 [doi>10.1007/s004460100054]
• 10: Luigi Iannone, Ramin Khalili, Kave Salamatian, and Serge Fdida. Cross-layer routing in wireless mesh networks. In 1st Int. Symp. on Wireless Communication Systems, pages 319--323, 2004.
• 11: Tomas Johansson , Lenka Carr-Motyčková, Reducing interference in ad hoc networks through topology control, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080815]
• 12: 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]
• 13: Xiang-Yang Li, Kousha Moaveni-Nejad, Wen-Zhan Song, and Wei-Zhao Wang. Interference-aware topology control for wireless sensor networks. In SECON'05: Sensor and Ad Hoc Communications and Networks, pages 263--274, 2005.
• 14: Thomas Moscibroda , Roger Wattenhofer, Minimizing interference in ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080816]
• 15: 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]
• 16: Michiel Smid. Closest-point problems in computational geometry. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 877--935, Amsterdam, 2000. Elsevier Science.
• 17: Pascal von Rickenbach , Stefan Schmid , Roger Wattenhofer , Aaron Zollinger, A Robust Interference Model for Wireless Ad-Hoc Networks, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, p.239.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.65]
• 18: P. J. Wan , G. Călinescu , X. Y. Li , O. Frieder, Minimum-energy broadcasting in static ad hoc wireless networks, Wireless Networks, v.8 n.6, p.607-617, November 2002 [doi>10.1023/A:1020381720601]
• 19: Andrew 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
          Subjects: Distributed applications

General Terms:
Algorithms, Design, Theory

Keywords:
interference, quasi unit disk graphs, spanners, topology control, wireless ad-hoc networks