MLS: an efficient location service for mobile ad hoc networks

ABSTRACT

ALGO is a distributed location service to track the position of mobile nodes and to route messages between any two nodes. The lookup of nodes is achieved by searching in a hierarchy of pointers that each node maintains. We show that ALGO has constant stretch for lookup requests. In contrast to previous work, we consider a concurrent setup where nodes are truly mobile and move even while messages are being routed towards them. We prove correctness and efficiency of ALGO and determine the maximum speed at which the nodes might move, which is up to 1/15 of the routing speed. To the best of our knowledge, this is the first work that bounds the node speed, a necessity to prove the success of a lookup algorithm. We verified our theoretical results through extensive simulation and show that the average lookup stretch is around 6.

REFERENCES

• 1: 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]
• 2: Baruch Awerbuch , David Peleg, Online tracking of mobile users, Journal of the ACM (JACM), v.42 n.5, p.1021-1058, Sept. 1995 [doi>10.1145/210118.210132]
• 3: 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]
• 4: Ljubica Blazevic , Jean-Yves Le Boudec , Silvia Giordano, A Location-Based Routing Method for Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.4 n.2, p.97-110, March 2005 [doi>10.1109/TMC.2005.16]
• 5: 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]
• 6: F. de Rango, M. Gerla, B. Zhou, and S. Marano. Geo-LANMAR Routing: Asymptotic Analysis of a Scalable Routing Scheme with Group Motion Support. In BROADNETS, 2005.
• 7: J. Eriksson, M. Faloutsos, and S. Krishnamurthy. Scalable Ad Hoc Routing: The Case for Dynamic Addressing. In INFOCOM, 2004.
• 8: Q. Fang, J. Gao, and L. J. Guibas. Locating and Bypassing Routing Holes in Sensor Networks. In INFOCOM, 2004.
• 9: 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]
• 10: 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]
• 11: J.-Y. Le Boudec and M. Vojnovic. Perfect Simulations and Stationarity of a Class of Mobility Models. In INFOCOM, 2005.
• 12: 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]
• 13: M. Li, W.-C. Lee, and A. Sivasubramaniam. Efficient Peer-to-Peer Information Sharing over Mobile Ad Hoc Networks. In MobEA, 2004.
• 14: Ananth Rao , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 15: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 16: Adam Smith , Hari Balakrishnan , Michel Goraczko , Nissanka Priyantha, Tracking moving devices with the cricket location system, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990088]
• 17: Aline C. Viana , Marcelo D. de Amorim , Serge Fdida , Yannis Viniotis , José F. de Rezende, Easily-managed and topology-independent location service for self-organizing networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062714]
• 18: Seung-Chul M. Woo , Suresh Singh, Scalable routing protocol for ad hoc networks, Wireless Networks, v.7 n.5, p.513-529, September 2001 [doi>10.1023/A:1016726711167]
• 19: 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
• 20: Y. Yu, G.-H. Lu, and Z.-L. Zhang. Enhancing Location Service Scalability with HIGH-GRADE. In MASS, 2004.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Performance

Keywords:
MANET, ad hoc geo-routing, location service, mobility