Asymptotically optimal geometric mobile ad-hoc routing

ABSTRACT

In this paper we present AFR, a new geometric mobile ad-hoc routing algorithm. The algorithm is completely distributed; nodes need to communicate only with direct neighbors in their transmission range. We show that if a best route has cost c, AFR finds a route and terminates with cost &Ogr;(c²) in the worst case. AFR is the first algorithm with cost bounded by a function of the optimal route. We also give a tight lower bound by showing that any geometric routing algorithm has worst-case cost $Ogr;(c²). Thus AFR is asymptotically optimal. We give a non-geometric algorithm that also matches the lower bound, but needs some memory at each node. This establishes an intriguing trade-off between geometry and memory.

REFERENCES

• 1: 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
• 2: Prosenjit Bose , Pat Morin , Andrej Brodnik , Svante Carlsson , Erik D. Demaine , Rudolf Fleischer , J. Ian Munro , Alejandro López-Ortiz, Online Routing in Convex Subdivisions, Proceedings of the 11th International Conference on Algorithms and Computation, p.47-59, December 18-20, 2000
• 3: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 4: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 5: Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks, Proceedings of the 21st International Conference on Distributed Computing Systems, p.461, April 16-19, 2001
• 6: 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]
• 7: G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI/RR-87-180, USC/ISI, March 1987.
• 8: K. Gabriel and R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18:259--278, 1969.
• 9: S. Giordano, I. Stojmenovic, and L. Blazevic. Position based routing algorithms for ad hoc networks: a taxonomy, July 2001. http://www.site.uottawa.ca/\~ivan/routing-survey.pdf.
• 10: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 11: T. Hou and V. Li. Transmission range control in multihop packet radio networks. IEEE Transactions on Communications, 34(1):38--44, 1986.
• 12: T. Imielinski and J. Navas. Gps-based addressing and routing. Technical Report RFC 2009, Computer Science, Rutgers University, November 1996.
• 13: Young Ko , Nitin H. Vaidya, Location-Aided Routing (LAR) in Mobile Ad Hoc Networks, Texas A & M University, College Station, TX, 1998
• 14: E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In Proc. 11th Canadian Conference on Computational Geometry, pages 51--54, Vancouver, August 1999.
• 15: F. Kuhn, R. Wattenhofer, and A. Zollinger. Geometric ad-hoc routing for unit disk graphs and general cost models. Technical Report 373, ETH Zurich, Department of Computer Science, 2002. Submitted. http://www.distcomp.ethz.ch/publications/tr373.ps.
• 16: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 17: X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed construction of planar spanner and routing for ad hoc wireless networks. In IEEE INFOCOM, 2002.
• 18: M. Mauve, J. Widmer, and H. Hartenstein. A survey on position-based routing in mobile ad-hoc networks. IEEE Network Magazine, 15(6):30--39, November 2001.
• 19: Julio C. Navas , Tomasz Imielinski, GeoCast—geographic addressing and routing, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.66-76, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262132]
• 20: S. Ramanathan , Martha Steenstrup, A survey of routing techniques for mobile communications networks, Mobile Networks and Applications, v.1 n.2, p.89-104, Oct. 1996 [doi>10.1007/BF01193330]
• 21: E. Royer and C. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. In IEEE Personal Communications, pages 46--55, April 1999.
• 22: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 23: H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, 32(3):246--257, 1984.
• 24: G. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12(4):261--268, 1980.
• 25: Jorge Urrutia, Routing with guaranteed delivery in geometric and wireless networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory

Keywords:
ad-hoc networks, face routing, geometric routing, routing, unit disk graphs, wireless communication