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 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. Similar concepts were used to provide a virtual traffic light service and a virtual air traffic control service, two other motion coordination services. In the virtual traffic light 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. In the virtual air traffic control service, each VSA served as an virtual air traffic controller for a geographic area, collecting information on the motion and destination of aircraft in its vicinity, and then coordinating with other virtual controllers to determine safe flight paths for the aircraft.
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.
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.