Hierarchical location service for mobile ad-hoc networks

ABSTRACT

Position-based routing has proven to be a scalable and efficient way for packet routing in mobile ad-hoc networks. To enable position-based routing, a node must be able to discover the location of the node it wants to communicate with. This task is typically accomplished by a location service. In this paper, we propose a novel location service called HLS (Hierarchical Location Service). HLS divides the area covered by the network into a hierarchy of regions. The top level region covers the complete network. A region is subdivided into several regions of the next lower level until the lowest level is reached. We call a lowest level region a cell. For a given node A, one specific cell is selected on each level of the hierarchy by means of hash function. As A changes its position it transmits position updates to these responsible cells. If another node wants to determine the position of A it uses the same hash function to determine the cells that may hold information about the position of A. It then proceeds to query the nodes in these cells in the order of the hierarchy until it receives a reply containing the current position of A. Because of its hierarchical approach HLS is highly scalable and particularly well suited for networks where communication partners tend to be close to each other. Due to the inherent scaling limitations of ad-hoc networks it is very likely that most ad hoc networks will display this property. Furthermore HLS is very robust to node mobility and node failures since it uses regions to select location servers and not a chain of mobile nodes as it is the case, e.g., for the well known Grid Location Service (GLS). We demonstrate these traits by providing extensive simulation data on the behaviour of HLS in a wide range of scenarios and by using GLS as a benchmark.

REFERENCES

• 1: 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]
• 2: 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]
• 3: S. Giordano and M. Hamdi. Mobility Management: The Virtual Home Region. Technical Report SSC/1999/037, EPFL-ICA, October 1999.
• 4: P. Gupta and P. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, 46(2):388--404, March 2000.
• 5: 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]
• 6: M. Käsemann. Beaconless Position-Based Routing for Mobile Ad-Hoc Networks. Master's thesis, Department of Mathematics and Computer Science, University of Mannheim, February 2003.
• 7: M. Käsemann, H. Füßler, H. Hartenstein, and M. Mauve. A Reactive Location Service for Mobile Ad Hoc Networks. Technical Report TR-02-014, Department of Computer Science, University of Mannheim, November 2002.
• 8: Michael Käsemann , Hannes Hartenstein, Analysis of a Location Service for Position-Based Routing in Mobile Ad Hoc Networks, Mobile Ad-Hoc Netzwerke, 1. deutscher Workshop über Mobile Ad-Hoc Netzwerke WMAN 2002, p.121-133, March 25-26, 2002
• 9: W. Kieß. Hierarchical Location Service for Mobile Ad-hoc Networks. Master's thesis, Department of Computer Science, University of Mannheim, 2003.
• 10: 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]
• 11: M. Mauve, J. Widmer, and H. Hartenstein. A Survey on Position-Based Routing in Mobile Ad-Hoc Networks. IEEE Network, 15(6):30--39, November/December 2001.
• 12: The ns-2 network simulator. http://www.isi.-edu/nsnam/ns/.
• 13: 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]
• 14: E. M. Royer, P. M. Melliar-Smith, and L. E. Moser. An Analysis of the Optimum Node Density for Ad hoc Mobile Networks. In Proceedings of the IEEE International Conference on Communications, Helsinki, Finland, June 2001.
• 15: 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