Minimizing recovery state In geographic ad-hoc routing

ABSTRACT

Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use of recovery algorithms when the greedy approach fails. We propose a novel idea based on virtual repositioning of nodes that allows to increase the efficiency of greedy routing and significantly increase the success of the recovery algorithm based on local information alone.We explain he problem of predicting dead ends which the greedy algorithm may reach and bypassing voids in the network, and introduce NEAR, Node Elevation Ad-hoc Routing, a solution that incorporates both virtual positioning and routing algorithms that improve performance in ad-hoc networks containing voids. We demonstrate by simulations the advantages of our algorithm over other geographic ad-hoc routing solutions.

REFERENCES

• 1: 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
• 2: C. Chiang, H. Wu, W. Liu, and M. Gerla, "Routing in clustered multihop, mobile wireless networks," in IEEE SICON'97 Apr. 1997, pp.197--211.
• 3: 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
• 4: D. Johnson and D. Maltz, Mobile Computing Kluwer Academic Publishers, 1996.
• 5: M. Mauve, J. Widmer, and H. Hartenstein, "A survey on position-based routing in mobile ad hoc networks," IEEE Networks Mag., vol.15, no.6, pp.30--39,2001.
• 6: D. Johnson, "Routing in ad hoc networks of mobile hosts," in Workshop on Mobile Computing Systems and Applications Santa Cruz, CA, USA, 1994.
• 7: Stefano Basagni , Imrich Chlamtac , Violet R. Syrotiuk , Barry A. Woodward, A distance routing effect algorithm for mobility (DREAM), Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.76-84, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288254]
• 8: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 9: I. Stojmenovic, "Position based routing in ad hoc networks," IEEE Commun. Mag., vol.40, no.7, pp.128--134, 2002.
• 10: Ivan Stojmenovic , Xu Lin, Loop-Free Hybrid Single-Path/Flooding Routing Algorithms with Guaranteed Delivery for Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1023-1032, October 2001 [doi>10.1109/71.963415]
• 11: L. Blazevic, L. Buttyan, S. Capkun, S. Giordano, J. Hubaux, and J. L. Boudec, "Self-organization in mobile ad hoc networks: The approach of terminodes," IEEE Commun. Mag., pp.166--175, 2001.
• 12: E. Kranakis, H. Singh, and J. Urrutia, "Compass routing on geometric networks," in 11th Canadian Conference on Computational Geometry Vancouver, Canada, Aug.1999, pp. 51--54.
• 13: 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]
• 14: 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]
• 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: C. Lochert, H. Hartenstein, J. Tian, H. Fussler, D. Hermann, and M. Mauve, "A routing strategy for vehicular ad hoc networks in city environments," in IEEE Intelligent Vehicles Symposium 2003 Boston, MA, USA, June 2003.
• 17: 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
• 18: 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]
• 19: D. S. J. De Couto and R. Morris, "Location proxies and intermediate node forw rding for practical geographic forwarding," MIT Laboratory for Computer Science, Tech. Rep. MIT-LCS-TR824, June 2001.
• 20: Zygmunt J. Haas , Ben Liang, Ad Hoc mobility management with uniform quorum systems, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.228-240, April 1999 [doi>10.1109/90.769770]
• 21: I. Stojmenovic, "A routing strategy and quorum based loc tion update scheme for d hoc wireless networks," Computer science, University of Ottawa, Tech.Rep.TR-99-09,1999.
• 22: H. S.M. Das and Y. Hu, "Performance comparison of scalable loc tion services for geographic ad hoc routing."
• 23: S. Giordano and M. Hami, "Mobility management: The virtual home region, EPFL, Tech. Rep.SSC/037,1999.
• 24: 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]
• 25: Brad Nelson Karp , H. T. Kung, Geographic routing for wireless networks, 2000
• 26: 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]
• 27: E. Royer, P. Melliar-Smith, and L. Moser, "An analysis of the optimum node density for ad hoc mobile networks," in IEEE Int. Conf. on Communications Helsinki, Finland, 2001.
• 28: L. Zou, M. Lu,nd Z. Xiong, "A distributed algorithm for the dead end problem of location based routing in sensor networks," IEEE Transactions On Vehicular Technology vol.54, no.4, pp.1509--1522, July 2005.
• 29: J.Tian, I. Stepanov, and K. Rothermel, "Spatial aware geographic forwarding for mobile ad hoc networks," Stuttgart University, Tech. Rep., 2002.

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
ad-hoc, distributed, elevation, repositioning, routing