Locating mobile nodes with EASE: learning efficient routes from encounter histories alone
Authors:
- 19 June 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 14 (3) , 457-469
Abstract
Routing in large-scale mobile ad hoc networks is challenging because all the nodes are potentially moving. Geographic routing can partially alleviate this problem, as nodes can make local routing decisions based solely on the destinations' geographic coordinates. However, geographic routing still requires an efficient location service, i.e., a distributed database recording the location of every destination node. Devising efficient, scalable, and robust location services has received considerable attention in recent years. The main purpose of this paper is to show that node mobility can be exploited to disseminate destination location information without incurring any communication overhead. We achieve this by letting each node maintain a local database of the time and location of its last encounter with every other node in the network. This database is consulted by packets to obtain estimates of their destination's current location. As a packet travels towards its destination, it is able to successively refine an estimate of the destination's precise location, because node mobility has "diffused" estimates of that location. We define and analyze a very simple algorithm called EASE (Exponential Age Search) and show that in a model where Theta(n) nodes perform independent random walks on a square lattice of size n, the length of the routes computed by EASE are of the same order as the distance between the source and destination even for very large n. Therefore, without disseminating any explicit location information, the length of EASE routes are within a constant factor of routes obtained with perfect information. We discuss refinements of the EASE algorithm and evaluate it through extensive simulations. We discuss general conditions such that the mobility diffusion effect leads to efficient routes without an explicit location service. In practical settings, where these conditions may not always be met, we believe that the mobility diffusion effect can complement existing location services and enhance their robustness and scalabilityKeywords
This publication has 19 references indexed in Scilit:
- Dynamic Source Routing in Ad Hoc Wireless Networks2007
- Space-Time Routing in Ad Hoc NetworksLecture Notes in Computer Science, 2003
- Mobility increases the capacity of ad hoc wireless networksIEEE/ACM Transactions on Networking, 2002
- An adaptive distance-based location update algorithm for next-generation PCS networksIEEE Journal on Selected Areas in Communications, 2001
- Geographical Region Summary Service for geographical routingACM SIGMOBILE Mobile Computing and Communications Review, 2001
- Geographical routing using partial information for wireless ad hoc networksIEEE Wireless Communications, 2001
- The capacity of wireless networksIEEE Transactions on Information Theory, 2000
- Markov paths on the Poisson-Delaunay graph with applications to routeing in mobile networksAdvances in Applied Probability, 2000
- Routing with guaranteed delivery in ad hoc wireless networks1999
- A distance routing effect algorithm for mobility (DREAM)1998