Ad hoc communication networks are, by nature, highly dynamic. Mobile nodes are often small devices with limited energy that spontaneously join and leave the network. As a mobile node moves, the set of neighbors with which it can directly communicate may change completely.
The nature of ad hoc networks makes it challenging to solve the standard problems encountered in mobile computing, such as location management, using classical tools. The difficulties arise from the lack of a fixed infrastructure to serve as the backbone of the network. In this project, we are developing several new approaches that allow existing distributed algorithms to be adapted for highly dynamic ad hoc environments. These approaches take advantage of geographic information to implement high-level abstract objects that facilitate the design of algorithms for these difficult environments.
Our first approach, the GeoQuorums approach, was originally motivated by the problem of implementing atomic shared memory in mobile ad hoc networks. This approach associates abstract atomic objects with certain geographic locations. We assume the existence of focal points, geographic areas that are normally "populated" by mobile nodes. Mobile nodes that happen to populate a focal point participate in implementing a shared atomic object. These objects, which we call focal point objects, are then used to implement atomic read and write operations on a virtual shared object, using our GeoQuorums algorithm.
Our second approach, the Virtual Mobile Node approach, grew out of the realization that the two primary challenges of mobile ad hoc networks are the unpredictable mobility and the unpredictable reliability of the mobile nodes themselves. We therefore introduce the Virtual Mobile Node Abstraction, which implements reliable, predictable mobile elements using the unreliable, unpredictable physical devices. We examine virtual mobile nodes that move on predictable, predetermined paths, as well as autonomous virtual mobile nodes.
Our third approach, the Virtual Stationary Automata approach, combines some elements of the first two approaches, while extending the capabilities of the virtual nodes that can be implemented. We describe timed abstract machines called Virtual Stationary Automata that are associated with fixed geographic locations. We also show how to both implement these machines and how they can be used to solve some important problems in mobile networks.