Localized construction of bounded degree and planar spanner for wireless ad hoc networks

ABSTRACT

We propose a novel localized algorithm that constructs a bounded degree and planar spanner for wireless ad hoc networks modeled by unit disk graph (UDG). Every node only has to know its 2-hop neighbors to find the edges in this new structure. Our method applies the Yao structure on the local Delaunay graph [21] in an ordering that are computed locally. This new structure has the following attractive properties: (1) it is a planar graph; (2) its node degree is bounded from above by a positive constant 19 + 2p/a (3) it is a t-spanner (given any two nodes u and v, there is a path connecting them in the structure such that its length is no more than t = max(p/2, psina/2 +1) Cdel times of the shortest path in UDG); (4) it can be constructed locally and is easy to maintain when the nodes move around; (5) moreover, we show that the total communication cost is O(n), where n is the number of wireless nodes, and the computation cost of each node is at most O(d log d), where d is its 2-hop neighbors in the original unit disk graph. Here Cdel is the spanning ratio of the Delaunay triangulation, which is at most 4 v3/9 p. And the adjustable parameter a satisfies 0 < a < p/3. In addition, experiments are conducted to show this topology is efficient in practice, compared with other well-known topologies used in wireless ad hoc networks.Previously, only centralized method [5] of constructing bounded degree planar spanner is known, with degree bound 27 and spanning ratio t 10.02. The distributed implementation of their centralized method takes O(n²) communications in the worst case. No localized methods were known previously for constructing bounded degree planar spanner.

REFERENCES

• 1: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513820]
• 2: Sunil Arya , Gautam Das , David M. Mount , Jeffrey S. Salowe , Michiel Smid, Euclidean spanners: short, thin, and lanky, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.489-498, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225191]
• 3: Prosenjit Bose , Luc Devroye , William S. Evans , David G. Kirkpatrick, On the Spanning Ratio of Gabriel Graphs and beta-skeletons, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.479-493, April 03-06, 2002
• 4: P. Bose, J. Gudmundsson, and P. Morin. Ordered theta graphs. In Proc. of Canadian Conf. on Computational Geometry (CCCG), 2002.
• 5: Prosenjit Bose , Joachim Gudmundsson , Michiel H. M. Smid, Constructing Plane Spanners of Bounded Degree and Low Weight, Proceedings of the 10th Annual European Symposium on Algorithms, p.234-246, September 17-21, 2002
• 6: Prosenjit Bose , Pat Morin, Online Routing in Triangulations, Proceedings of the 10th International Symposium on Algorithms and Computation, p.113-122, December 16-18, 1999
• 7: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 8: G. Calinescu. Computing 2-hop neighborhoods in ad hoc wireless networks. In AdHoc-Now'03, 2003.
• 9: David P. Dobkin , Steven J. Friedman , Kenneth J. Supowit, Delaunay graphs are almost as good as complete graphs, Discrete & Computational Geometry, v.5 n.4, p.399-407, Jul. 1990 [doi>10.1007/BF02187801]
• 10: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 11: Matthias Grünewald , Tamás Lukovszki , Christian Schindelhauer , Klaus Volbert, Distributed Maintenance of Resource Efficient Wireless Network Topologies (Distinguished Paper), Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.935-946, August 27-30, 2002
• 12: Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan, Improved Greedy Algorithms for Constructing Sparse Geometric Spanners, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.314-327, July 05-07, 2000
• 13: L. Hu. Topology control for multihop packet radio networks. IEEE Transactions on Communications, 41, 1993.
• 14: L. Jia, R. Rajaraman, and C. Scheideler. On local algorithms for topology control and routing in ad hoc networks, 2002. Submitted for publication.
• 15: 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]
• 16: J. Mark Keil , Carl A. Gutwin, The Delauney Triangulation Closely Approximates the Complete Euclidean Graph, Proceedings of the Workshop on Algorithms and Data Structures, p.47-56, August 17-19, 1989
• 17: J. Mark Keil , Carl A. Gutwin, Classes of graphs which approximate the complete Euclidean graph, Discrete & Computational Geometry, v.7 n.1, p.13-28, 1992 [doi>10.1007/BF02187821]
• 18: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Asymptotically optimal geometric mobile ad-hoc routing, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570814]
• 19: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778447]
• 20: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 21: IEEE Transactions on Parallel and Distributed Systems Staff, 2002 Index Transactions on Parallel and Distributed Systems, Vol. 13, IEEE Transactions on Parallel and Distributed Systems, v.13 n.12, p.1333-1342, December 2002
• 22: X.-Y. Li, P.-J. Wan, and Y. Wang. Power efficient and sparse spanner for wireless ad hoc networks. In IEEE ICCCN, pages 564--567, 2001.
• 23: X.-Y. Li , P.-J. Wan , Y. Wang , O. Frieder, Sparse Power Efficient Topology for Wireless Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.296.2, January 07-10, 2002
• 24: X.-Y. Li and Y. Wang. Efficient construction of low weight bounded degree planar spanner. In 9th COCOON, 2003.
• 25: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 26: 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]
• 27: R. Ramanathan and R. Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. In IEEE INFOCOM, 2000.
• 28: W. Wang, X.-Y. Li, K. Moaveninejad, Y. Wang, and W.-Z. Song. The Spanning Ratios of beta-Skeleton. Canadian Conference on Computational Geometry (CCCG), 2003.
• 29: Y. Wang, X.-Y. Li, and O. Frieder. Distributed spanner with bounded degree for wireless networks. International Journal of Foundations of Computer Science, 14:183--200, 2003.
• 30: R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang. Distributed topology control for wireless multihop ad-hoc networks. In IEEE INFOCOM'01, 2001.
• 31: A. C.-C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Computing, 11:721--736, 1982.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms

General Terms:
Algorithms, Design, Theory

Keywords:
bounded degree, localized algorithm, planar, spanner, topology control, wireless ad hoc networks