Research Abstracts - 2007

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.

We have also extended the protocol to support autonomous virtual mobile nodes that can control their motion dynamically, rather than travelling along a fixed, predetermined path. This creates two main challenges: first, the mobile nodes responsible for emulating the virtual node must coordinate to determine how the virtual node shoudl move; second, when the virtual node fails (due to depopulation, for example), recovery is more difficult. We present a self-stabilizing algorithm for virtual node recovery, including strategies for maintaining the virtual node dynamically.

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 algorithms 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 leader-moderated approach to achieve robust replication of the state of the VSA. Whichever mobile node is designated a leader 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 the mselves 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. Similar concepts were used to provide a virtual traffic light service, another motion coordination service. In this service, a VSA was used to collect information on mobile units and to control a virtual traffic light that could direct those units to safely stop or go at path intersections.

The VSA abstraction was also used to implement Geocast and home location services for mobile nodes. The Geocast service allows region-to-region broadcasts. The 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. The home location service was then used to implement a point-to-point routing service.

As another example of the use of the VSA abstraction, it was used to provide a hierarchical tracking service for mobile nodes. Here the VSAs served as representatives of regions and levels in a network hierarchy and maintained a data structure that guarantees updates to the tracking structure after mobile object moves take work proportional to the distance moved times a log of network diameter factor, while finds initiated distance d from a mobile object take linear work to complete.

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) [4]. 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 has appeared in Distributed Computing [5]. Research on the Virtual Mobile Node abstraction is underway: an extended abstract on VMNs has appeared at [3], and on autonomous VMNs has appeared at [6]. An extended abstract of the Virtual Stationary Automata work was published in the 9th International Conference on Principles of Distributed Systems (OPODIS 2005), and a more complete version can be found at [2]. The Virtual Stationary Automata abstraction is used to provide a motion

This work is supported in part by AFOSR Contract #F49620-00-1-0097, DARPA Contract #F33615-01-C-1896, NSF Grant 64961-CS, NTT Grant MIT9904-12, NSF grant CCR-0098305, NSF ITR Grant 0121277, Quanta-MIT Award #012627-009, NSF Award #CCR-0326277 and USAF,AFRL Award #FA9550-04-1-0121. Part of the work of the second author has been done during visits to MIT and Texas A&M. The second and fourth authors are partially supported by an IBM faculty award, the Israeli Ministry of Defense, NSF, and the Israeli Ministry of Trade and Industry. The tenth author is partially supported by the NSF Grant 9988304, 0311368 and by the NSF Career Award 9984774. The twelfth author is partially supported by NSF Grant 0098305 and Texas Advanced Research Program 000512-0091-2001.

References:

[1] Matthew Brown, Seth Gilbert, Nancy Lynch, Calvin Newport, Tina Nolte, and Michael Spindel. The Virtual Node Layer: A Programming Abstraction for Wireless Sensor Networks. To appear: International Workshop on Wireless Sensor Network Architecture, 2007.

[2] Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte. Timed Virtual Stationary Automata for Mobile Networks. Technical Report LCS-TR-979a, MIT, 2005. Also in Proceedings of the 9th International Conference on Principles of Distributed Computing, December, 2005. Also invited paper, 43rd Annual Allerton Conference on Communication, Control, and Computing, September, 2005. Also brief announcement, in Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing, July, 2005.

[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 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.

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

[6] Shlomi Dolev, Seth Gilbert, Elad Schiller, Alex A. Shvartsman, and Jennifer L. Welch. Autonomous Virtual Mobile Nodes. In Proceeding of the 3rd Workshop on Foundations of Mobile Computing (DIAL-M-POMC), September 2005.

[7] Shlomi Dolev, Limor Lahiani, Nancy Lynch, and Tina Nolte. Self-stabilizing Mobile Node Location Management and Message Routing. Technical Report LCS-TR-999, MIT, 2005. Also in Proceeding of the 7th International Symposium on Self-Stabilizing Systems, October, 2005.

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

[9] Tina Nolte and Nancy Lynch. A Virtual Node-based Tracking Algorithm for Mobile Networks. To appear: International Conference on Distributed Computing Systems (ICDCS), 2007.

[10] Tina Nolte and Nancy Lynch. Self-Stabilization and Virtual Node Layer Emulations. Submitted for publication, 2007.