Self-Stabilizing Mobile Node Location Management and Message
We present simple algorithms for achieving self-stabilizing locationmanagement and routing in mobile ad-hoc networks. While mobile clients maybe susceptible to corruption and stopping failures, mobile networks areoften deployed with a reliable GPS oracle, supplying frequent updates ofaccurate real t...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30563 |
| _version_ | 1811077728271597568 |
|---|---|
| author | Dolev, Shlomi Lahiani, Limor Lynch, Nancy Nolte, Tina |
| author2 | Theory of Distributed Systems |
| author_facet | Theory of Distributed Systems Dolev, Shlomi Lahiani, Limor Lynch, Nancy Nolte, Tina |
| author_sort | Dolev, Shlomi |
| collection | MIT |
| description | We present simple algorithms for achieving self-stabilizing locationmanagement and routing in mobile ad-hoc networks. While mobile clients maybe susceptible to corruption and stopping failures, mobile networks areoften deployed with a reliable GPS oracle, supplying frequent updates ofaccurate real time and location information to mobile nodes. Informationfrom a GPS oracle provides an external, shared source of consistency formobile nodes, allowing them to label and timestamp messages, and henceaiding in identification of, and eventual recovery from, corruption andfailures. Our algorithms use a GPS oracle.Our algorithms also take advantage of the Virtual Stationary Automataprogramming abstraction, consisting of mobile clients, virtual timedmachines called virtual stationary automata (VSAs), and a local broadcastservice connecting VSAs and mobile clients. VSAs are distributed at knownlocations over the plane, and emulated in a self-stabilizing manner by themobile nodes in the system. They serve as fault-tolerant building blocksthat can interact with mobile clients and each other, and can simplifyimplementations of services in mobile networks.We implement three self-stabilizing, fault-tolerant services, each builton the prior services: (1) VSA-to-VSA geographic routing, (2) mobileclient location management, and (3) mobile client end-to-end routing. Weuse a greedy version of the classical depth-first search algorithm toroute messages between VSAs in different regions. The mobile clientlocation management service is based on home locations: Each clientidentifier hashes to a set of home locations, regions whose VSAs areperiodically updated with the client\'s location. VSAs maintain thisinformation and answer queries for client locations. Finally, theVSA-to-VSA routing and location management services are used to implementmobile client end-to-end routing. |
| first_indexed | 2024-09-23T10:47:37Z |
| id | mit-1721.1/30563 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:47:37Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/305632019-04-12T08:26:08Z Self-Stabilizing Mobile Node Location Management and Message Dolev, Shlomi Lahiani, Limor Lynch, Nancy Nolte, Tina Theory of Distributed Systems We present simple algorithms for achieving self-stabilizing locationmanagement and routing in mobile ad-hoc networks. While mobile clients maybe susceptible to corruption and stopping failures, mobile networks areoften deployed with a reliable GPS oracle, supplying frequent updates ofaccurate real time and location information to mobile nodes. Informationfrom a GPS oracle provides an external, shared source of consistency formobile nodes, allowing them to label and timestamp messages, and henceaiding in identification of, and eventual recovery from, corruption andfailures. Our algorithms use a GPS oracle.Our algorithms also take advantage of the Virtual Stationary Automataprogramming abstraction, consisting of mobile clients, virtual timedmachines called virtual stationary automata (VSAs), and a local broadcastservice connecting VSAs and mobile clients. VSAs are distributed at knownlocations over the plane, and emulated in a self-stabilizing manner by themobile nodes in the system. They serve as fault-tolerant building blocksthat can interact with mobile clients and each other, and can simplifyimplementations of services in mobile networks.We implement three self-stabilizing, fault-tolerant services, each builton the prior services: (1) VSA-to-VSA geographic routing, (2) mobileclient location management, and (3) mobile client end-to-end routing. Weuse a greedy version of the classical depth-first search algorithm toroute messages between VSAs in different regions. The mobile clientlocation management service is based on home locations: Each clientidentifier hashes to a set of home locations, regions whose VSAs areperiodically updated with the client\'s location. VSAs maintain thisinformation and answer queries for client locations. Finally, theVSA-to-VSA routing and location management services are used to implementmobile client end-to-end routing. 2005-12-22T02:36:07Z 2005-12-22T02:36:07Z 2005-08-11 MIT-CSAIL-TR-2005-052 MIT-LCS-TR-999 http://hdl.handle.net/1721.1/30563 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 20 p. 27793653 bytes 1205701 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Dolev, Shlomi Lahiani, Limor Lynch, Nancy Nolte, Tina Self-Stabilizing Mobile Node Location Management and Message |
| title | Self-Stabilizing Mobile Node Location Management and Message |
| title_full | Self-Stabilizing Mobile Node Location Management and Message |
| title_fullStr | Self-Stabilizing Mobile Node Location Management and Message |
| title_full_unstemmed | Self-Stabilizing Mobile Node Location Management and Message |
| title_short | Self-Stabilizing Mobile Node Location Management and Message |
| title_sort | self stabilizing mobile node location management and message |
| url | http://hdl.handle.net/1721.1/30563 |
| work_keys_str_mv | AT dolevshlomi selfstabilizingmobilenodelocationmanagementandmessage AT lahianilimor selfstabilizingmobilenodelocationmanagementandmessage AT lynchnancy selfstabilizingmobilenodelocationmanagementandmessage AT noltetina selfstabilizingmobilenodelocationmanagementandmessage |