An algorithmic approach to geographic routing in ad hoc and sensor networks

ABSTRACT

The one type of routing in ad hoc and sensor networks that currently appears to be most amenable to algorithmic analysis is geographic routing. This paper contains an introduction to the problem field of geographic routing, presents a specific routing algorithm based on a synthesis of the greedy forwarding and face routing approaches, and provides an algorithmic analysis of the presented algorithm from both a worst-case and an average-case perspective.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Ittai Abraham , Danny Dolev , Dahlia Malkhi, LLS: a locality aware location service for mobile ad hoc networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022643]
• 4: [4] M. Grossglauser and M. Vetterli, "Locating nodes with EASE: Mobility diffusion of last encounters in ad hoc networks," in Proc. 22nd Annu. Joint Conf. IEEE Computer and Communications Societies (INFOCOM) , 2003.
• 5: Roland Flury , Roger Wattenhofer, MLS: an efficient location service for mobile ad hoc networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132931]
• 6: [6] A. Zollinger, "Networking unleashed: Geographic routing and topology control in ad hoc and sensor networks," Ph.D. dissertation, ETH, Zurich, Switzerland, 2005, diss. ETH 16025.
• 7: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 8: R. Ogier , F. Templin , M. Lewis, Topology Dissemination Based on Reverse-Path Forwarding (TBRPF), RFC Editor, 2004
• 9: T. Clausen , P. Jacquet, Optimized Link State Routing Protocol (OLSR), RFC Editor, 2003
• 10: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 11: [11] D. Johnson and D. Maltz, "Dynamic source routing in ad hoc wireless networks," in Mobile Computing, Imielinski and Korth, Eds. Boston, MA: Kluwer Academic, 1996, vol. 353 [Online]. Available: citeseer.nj. nec.com/johnson96dynamic.html
• 12: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 13: [13] M. Joa-Ng and I.-T. Lu, "A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks," IEEE J. Sel. Areas Commun., vol. 17, no. 8, pp. 1415-1425, Aug. 1999.
• 14: [14] N. Nikaein, C. Bonnet, and N. Nikaein, "HARP--Hybrid Ad Hoc Routing protocol," in Int. Symp. Telecommunications (IST 2001), Tehran, Iran, Sep. 2001.
• 15: Venugopalan Ramasubramanian , Zygmunt J. Haas , Emin Gün Sirer, SHARP: a hybrid adaptive routing protocol for mobile ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778450]
• 16: [16] E. Royer and C. Toh, "A review of current routing protocols for ad hoc mobile wireless networks," IEEE Personal Commun., vol. 6, no. 2, pp. 46-55, Apr. 1999.
• 17: Costas Busch , Srikanth Surapaneni , Srikanta Tirthapura, Analysis of link reversal routing algorithms for mobile ad hoc networks, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777446]
• 18: [18] E. Gafni and D. Bertsekas, "Distributed algorithms for generating loop-free routes in networks with frequently changing topology," IEEE Trans. Commun., vol. 29, no. 1, pp. 11-18, Jan. 1981.
• 19: Ravi Prakash, Unidirectional links prove costly in wireless ad hoc networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.15-22, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313263]
• 20: [20] G. Finn, "Routing and addressing problems in large metropolitan-scale internetworks," USC/ISI, Tech. Rep. ISI/RR-87-180, Mar. 1987.
• 21: [21] T. Hou and V. Li, "Transmission range control in multihop packet radio networks," IEEE Trans. Commun., vol. 34, no. 1, pp. 38-44, Jan. 1986.
• 22: [22] H. Takagi and L. Kleinrock, "Optimal transmission ranges for randomly distributed packet radio terminals," IEEE Trans. Commun., vol. 32, no. 3, pp. 246-257, Mar. 1984.
• 23: [23] E. Kranakis, H. Singh, and J. Urrutia, "Compass routing on geometric networks," in Proc. 11th Canadian Conf. Computational Geometry, Vancouver, BC, Canada, Aug. 1999, pp. 51-54 [Online]. Available: citeseer.nj.nec.com/kranakis99compass.html
• 24: 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]
• 25: 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]
• 26: 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
• 27: 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
• 28: 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]
• 29: 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
• 30: 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]
• 31: 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]
• 32: 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]
• 33: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 34: Young-Jin Kim , Ramesh Govindan , Brad Karp , Scott Shenker, Geographic routing made practical, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.217-230, May 02-04, 2005
• 35: Young-Jin Kim , Ramesh Govindan , Brad Karp , Scott Shenker, On the pitfalls of geographic face routing, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080818]
• 36: Ben Leong , Sayan Mitra , Barbara Liskov, Path Vector Face Routing: Geographic Routing with Local Face Information, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.147-158, November 06-09, 2005 [doi>10.1109/ICNP.2005.32]
• 37: Ben Leong , Barbara Liskov , Robert Morris, Geographic routing without planarization, Proceedings of the 3rd conference on 3rd Symposium on Networked Systems Design & Implementation, p.25-25, May 08-10, 2006, San Jose, CA
• 38: Hannes Frey , Ivan Stojmenovic, On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161133]
• 39: [39] C. Chiang, H. Wu, W. Liu, and M. Gerla, "Routing in clustered multihop, mobile wireless networks," in Proc. IEEE Singapore Int. Conf. Networks, 1997, pp. 197-211.
• 40: 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
• 41: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Initializing newly deployed ad hoc and sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023746]
• 42: [42] B. Blum, T. He, S. Son, and J. Stankovic, "IGF: A state-free robust communication protocol for wireless sensor networks," Univ. of Virginia, Charlottesville, VA, Tech. Rep. CS-2003-11, 2003.
• 43: [43] H. Füßler, J. Widmer, M. Käsemann, M. Mauve, and H. Hartenstein, "Contention-based forwarding for mobile ad hoc networks," Elsevier's Ad Hoc Networks, vol. 1, no. 4, pp. 351-369, Nov. 2003.
• 44: [44] M. Zorzi and R. R. Rao, "Geographic Random Forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance," IEEE Trans. Mobile Computing, vol. 2, no. 4, pp. 337-348, Oct.-Dec. 2003.
• 45: [45] M. Heissenbüttel, "Routing and broadcasting in ad hoc networks," Ph.D. dissertation, Univ. of Bern, Bern, Switzerland, 2005.
• 46: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Unit disk graph approximation, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022634]
• 47: Thomas Moscibroda , Regina O'Dell , Mirjam Wattenhofer , Roger Wattenhofer, Virtual coordinates for ad hoc and sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022633]
• 48: [48] M. Wattenhofer, R. Wattenhofer, and P. Widmayer, "Geometric routing without geometry," in 12th Colloquium on Structural Information and Communication Complexity (SIROCCO), Le Mont Saint-Michel, France, May 2005.
• 49: Rodrigo Fonseca , Sylvia Ratnasamy , Jerry Zhao , Cheng Tien Ee , David Culler , Scott Shenker , Ion Stoica, Beacon vector routing: scalable point-to-point routing in wireless sensornets, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.329-342, May 02-04, 2005
• 50: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 51: 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]
• 52: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 53: [53] P. Doyle and J. Snell, Random Walks and Electric Networks, ser. The Carus Mathematical Monographs. Washington DC: The Mathematical Association of America, 1984.
• 54: 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]

INDEX TERMS

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

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design

Keywords:
algorithmic analysis, networks, routing, stretch, wireless