Geometric ad-hoc routing: of theory and practice

ABSTRACT

All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we consider two aspects: We propose a new geometric routing algorithm which is outstandingly efficient on practical average-case networks, however is also in theory asymptotically worst-case optimal. On the other hand we are able to drop the formerly necessary assumption that the distance between network nodes may not fall below a constant value, an assumption that cannot be maintained for practical networks. Abandoning this assumption we identify from a theoretical point of view two fundamentamentally different classes of cost metrics for routing in ad-hoc networks.

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: 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, Online Routing in Triangulations, Proceedings of the 10th International Symposium on Algorithms and Computation, p.113-122, December 16-18, 1999
• 4: 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]
• 5: [5] C. Chiang, H. Wu, W. Liu, and M. Gerla. Routing in Clustered Multihop, Mobile Wireless Networks. In Proc. IEEE Singapore Int. Conf. on Networks, pages 197-211, 1997.
• 6: Susanta Datta , Ivan Stojmenovic , Jie Wu, Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks, Cluster Computing, v.5 n.2, p.169-178, April 2002 [doi>10.1023/A:1013985610753]
• 7: [7] P. G. Doyle and J. L. Snell. Random Walks and Electric Networks. The Carus Mathematical Monographs. The Mathematical Association of America, 1984.
• 8: [8] G. G. Finn. Routing and Addressing Problems in Large Metropolitan-scale Internetworks. Technical Report ISI/RR-87-180, USC/ISI, March 1987.
• 9: Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378666]
• 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: Sudipto Guha , Samir Khuller, Approximation Algorithms for Connected Dominating Sets, Proceedings of the Fourth Annual European Symposium on Algorithms, p.179-193, September 25-27, 1996
• 12: [12] T. C. Hou and V. O. K. Li. Transmission Range Control in Multihop Packet Radio Networks. IEEE Transactions on Communications, 34(1):38-44, 1986.
• 13: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, v.26 n.2, p.238-274, feb. 1998 [doi>10.1006/jagm.1997.0903]
• 14: [14] D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In T. Imielinski and H. Korth, editors, Mobile Computing, chapter 5, pages 153-181. Kluwer Academic Publishers, 1996.
• 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: Young-Bae Ko , Nitin H. Vaidya, Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.101, February 25-26, 1999
• 17: [17] E. Kranakis, H. Singh, and J. Urrutia. Compass Routing on Geometric Networks. In Proc. 11th Canadian Conference on Computational Geometry, pages 51-54, 1999.
• 18: P. Krishna , Mainak Chatterjee , Nitin H. Vaidya , Dhiraj K. Pradhan, A Cluster-based Approach for Routing in Ad-Hoc Networks, Proceedings of the 2nd Symposium on Mobile and Location-Independent Computing, p.1-10, April 10-11, 1995
• 19: 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]
• 20: 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]
• 21: [21] M. Mauve, J. Widmer, and H. Hartenstein. A Survey on Position-Based Routing in Mobile Ad-Hoc Networks. IEEE Network, 15(6), 2001.
• 22: 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]
• 23: [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: 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
• 25: Yu Wang , Xiang-Yang Li, Geometric Spanners for Wireless Ad Hoc Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.171, July 02-05, 2002
• 26: Jie Wu, Dominating-set-based routing in ad hoc wireless networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
• 27: Yuan Xue , Baochun Li , Klara Nahrstedt, A Scalable Location Management Scheme in Mobile Ad-Hoc Networks, Proceedings of the 26th Annual IEEE Conference on Local Computer Networks, p.102, November 14-16, 2001

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

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

General Terms:
Algorithms, Performance, Theory

Keywords:
Ad-Hoc Networks, Cost Metrics, Face Routing, Geometric Routing, Mobile Computing, Performance, Routing, Wireless Communication