Introduction

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 devising 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. Our approach is based on associating 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 new 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, and show how it can be used to build distributed applications for dynamic ad hoc networks, thus demonstrating the utility of our approach. We also demonstrate the feasibility of our approach by showing how to implement the Virtual Mobile Node Abstraction.

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.

The GeoQuorums Approach

Providing atomic read/write shared memory is a fundamental problem in distributed computing, with applications in mobile ad hoc networks. Atomic memory is a basic service that facilitates the implementation of many higher-level algorithms. For example, one might construct a location service by requiring each mobile node to periodically write its current location to the memory. Alternatively, a shared memory could be used to collect real-time statistics, for example, recording the number of people in a building. We present here a new algorithm for atomic multi-writer/multi-reader memory in mobile ad hoc networks.

We divide the problem of implementing atomic read/write memory into two parts. First, we define a static system model, the Focal Point Object Model, that associates abstract objects with certain fixed geographic locales. The mobile nodes implement this model using a replicated state machine approach. In this way, the dynamic nature of the ad hoc network is masked by a static model. Second, we present our GeoQuorums algorithm to implement read/write atomic memory using the Focal Point Object Model. The GeoQuorums algorithm uses a quorum-based strategy in which each quorum consists of a set of focal point objects. The quorums are used to maintain the consistency of the shared memory and to tolerate limited failures of the focal point objects, caused by depopulation of the corresponding geographic areas. We present a mechanism for changing the set of quorums on the fly, thus improving efficiency

This research contains three primary contributions. First, we introduce the Focal Point Object Model, a geographic abstraction model which allows simple, static algorithms to be adapted for highly dynamic environments. Second, we provide an implementation of the Focal Point Object Model using mobile nodes. Third, we implement a reconfigurable atomic read/write shared memory, using the static Focal Point Object Model.

The VMN Approach

We propose designing distributed algorithms to run on virtual mobile nodes (VMNs), abstract nodes that move in a predetermined, predictable manner. In this new abstraction, VMNs are simulated by real nodes in the network. The motion of a VMN is determined in advance, and is known to the programs executing on the VMNs. For example, a VMN may traverse the plane in a regular pattern, or it may perform a pseudorandom walk. We allow the motion of the virtual nodes to be uncorrelated with the motion of the real nodes: even if all the real nodes are going in one direction, the virtual nodes are able to travel in the opposite direction. Consider, for example, an application to monitor traffic on a highway: even though all the cars are moving in one direction, a VMN could move in the opposite direction, notifying oncoming cars of the traffic ahead.

We present the Mobile Point algorithm, a new algorithm that implements robust virtual mobile nodes, thus demonstrating the feasibility of our approach. The main idea of the algorithm is to allow real nodes traveling near the location of a virtual node to emulate that VMN. In order to achieve robustness, the algorithm replicates the state of a virtual node at a number of real mobile nodes. As the execution proceeds, the algorithm continually modifies the set of replicas for each mobile node so that the replicas always remain near the desired path of the virtual node. We use a replicated state machine approach, augmented to support joins, leaves, and recovery, to maintain the consistency of the replicas.

A virtual node is prone to "crash-reboot" failures. As long as the path of the virtual node travels through dense areas of the network, the virtual node does not fail. If however, the VMN is directed to an empty spot, a failure may occur. The Mobile Point algorithm, however, allows the VMN to recover to an initial state, if it again reenters a dense area. In this way, the VMN abstraction takes advantage of dense regions of the network to perform arbitrary computation.

To summarize, this research contains three main contributions. First, we define the VMN abstraction. Second, we present selected algorithms based on VMNs that are quite simple compared to previous algorithms. Third, we present an algorithm to implement robust virtual mobile nodes.

The Virtual Stationary Automata Approach

We also propose running distributed algorithms on virtual stationary automata (VSAs). Virtual stationary automata are timed abstract machines that are at fixed locations across the network. These VSAs together provide an overlay virtual network of fixed machines.

We present an algorithm to implement VSA's. As in the VMN approach, each VSA is simulated by the real mobile nodes in the VSA's region in the network. Our implementation uses a round-robin approach to achieve robust replication of the state of the VSA. Whichever mobile node is designated a leader in a region's round-robin ordering is responsible for maintaining the state for the virtual machine. The implementation allows new mobile nodes to join the simulation of a VSA and can tolerate failures of mobile nodes that are simulating the VSA. If, however, the region for the VSA is not populated by any mobile nodes, the VSA can crash. A crashed VSA can be restarted if mobile nodes later enter its region.

A version of the VSA abstraction has been used to help provide a motion coordination framework for mobile nodes, where mobile nodes are supposed to space themselves at an equal distance from each other on a predetermined curve in the network. Each VSA coordinates with nearby VSAs to determine how to distribute mobile nodes between each other based on the length of the curve through their regions. Each VSA then directs mobile nodes in its region to their new locations. The use of the VSA abstraction simplifies the task of aggregating information about the mobile nodes and using that information to coordinate their actions. The VSA abstraction is also being used to implement a home location service for mobile nodes. This home location service allows a mobile node to query its local VSA for the location of another mobile node. The local VSA queries the home location VSAs for the location of the searched-for mobile node, returning the response to the querying mobile node. Again, the use of the VSA abstraction simplifies the task of aggregating information about the mobile nodes.

This research contains three main contributions. First, we define the VSA abstraction. Second, we present an algorithm to implement the VSA abstraction using the mobile nodes in the network. Third, we present algorithms for mobile networks that are simplified by use of the VSA abstraction.

Progress

An extended abstract of the GeoQuorums algorithm was previously published in the 17th International Symposium on Distributed Computing (DISC 2003)[2]. Since then, we have more formally separated the algorithm into two distinct components, defining a Focal Point Object Model, which can be used as the basis for other algorithms in mobile networks. We have also developed complete proofs of correctness that were omitted in the extended abstract. The full version can be found at [4]. Research on the Virtual Mobile Node abstraction is underway, and a report can be found at [3]. The Virtual Stationary Automata research is also ongoing, and a report can be found at [1]. The Virtual Stationary Automata abstraction is used to provide a motion coordination framework for mobile nodes in [5]. The use of the abstraction to implement a simple home location service is also ongoing.

Research Support

This work is supported in part by NSF grant CCR-0098305 and NSF ITR Grant 0121277. Part of the work of the first author has been done during visits to MIT and Texas A&M. The first and third authors are partially supported by an IBM faculty award, the Israeli ministry of defense, NSF, and the Israeli Ministry of Trade and Industry. The second, fourth, fifth, and sixth authors are partially supported by AFOSR Contract #F49620-00-1-0097, DARPA Contract #F33615-01-C-1896, NSF Grant 64961-CS, and NTT Grant MIT9904-12. The eighth author is partially supported by the NSF Grant 9988304, 0311368 and by the NSF Career Award 9984774. The ninth author is partially supported by NSF Grant 0098305 and Texas Advanced Research Program 000512-0091-2001.

References:

[1] Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte. Virtual Stationary Automata for Mobile Networks. Technical Report LCS-TR-979, MIT, 2005.

[2] Shlomi Dolev, Seth Gilbert, Nancy Lynch, Alex Shvartsman, and Jennifer Welch. Geoquorums: Implementing atomic memory in mobile ad hoc networks. In Proceeding of the 17th International Conference on Distributed Computing, October 2003.

[3] Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex A. Shvartsman, and Jennifer L. Welch. Virtual mobile nodes for mobile ad hoc networks. In Proceedings of the 18th International Conference on Distributed Computing, October, 2004.

[4] Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and Jennifer L. Welch. Geoquorums: Implementing atomic memory in ad hoc networks. To appear: Distributed Computing, 2005. Also, Technical Report LCS-TR-900, MIT, 2003.

[5] Nancy Lynch, Sayan Mitra, and Tina Nolte. Motion Coordination using Virtual Nodes. Technical Report LCS-TR-986, MIT, 2005. Also submitted to 44th IEEE Conference on Decision and Control, 2005.