| We present simple algorithms for achieving self-stabilizing location
management and routing in mobile ad-hoc networks. While mobile clients may
be susceptible to corruption and stopping failures, mobile networks are
often deployed with a reliable GPS oracle, supplying frequent updates of
accurate real time and location information to mobile nodes. Information
from a GPS oracle provides an external, shared source of consistency for
mobile nodes, allowing them to label and timestamp messages, and hence
aiding in identification of, and eventual recovery from, corruption and
failures. Our algorithms use a GPS oracle.
Our algorithms also take advantage of the Virtual Stationary Automata
programming abstraction, consisting of mobile clients, virtual timed
machines called virtual stationary automata (VSAs), and a local broadcast
service connecting VSAs and mobile clients. VSAs are distributed at known
locations over the plane, and emulated in a self-stabilizing manner by the
mobile nodes in the system. They serve as fault-tolerant building blocks
that can interact with mobile clients and each other, and can simplify
implementations of services in mobile networks.
We implement three self-stabilizing, fault-tolerant services, each built
on the prior services: (1) VSA-to-VSA geographic routing, (2) mobile
client location management, and (3) mobile client end-to-end routing. We
use a greedy version of the classical depth-first search algorithm to
route messages between VSAs in different regions. The mobile client
location management service is based on home locations: Each client
identifier hashes to a set of home locations, regions whose VSAs are
periodically updated with the client\'s location. VSAs maintain this
information and answer queries for client locations. Finally, the
VSA-to-VSA routing and location management services are used to implement
mobile client end-to-end routing. |