Locating Nodes with EASE: Mobility Diffusion of Last Encounters in Ad Hoc Networks

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 {\em 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 {\em node mobility} can be exploited to disseminate destination location information {\em 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 $N$ nodes perform independent random walks on a square lattice, the length of the routes computed by EASE are on the same order as the distance between the source and destination {\em even for very large $N$.} Therefore, without exchanging 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 scalability.