Self-Stabilizing Mobile Node Location Management and Message

Abstract

We present simple algorithms for achieving self-stabilizing location management and routing in mobile ad-hoc networks. While mobile clients may be susceptible to corruption and stopping failures, mobile networks are often deployed with a reliable GPS oracle, supplying frequent updates of accurate real time and location information to mobile nodes. Information from a GPS oracle provides an external, shared source of consistency for mobile nodes, allowing them to label and timestamp messages, and hence aiding in identification of, and eventual recovery from, corruption and failures. Our algorithms use a GPS oracle. Our algorithms also take advantage of the Virtual Stationary Automata programming abstraction, consisting of mobile clients, virtual timed machines called virtual stationary automata (VSAs), and a local broadcast service connecting VSAs and mobile clients. VSAs are distributed at known locations over the plane, and emulated in a self-stabilizing manner by the mobile nodes in the system. They serve as fault-tolerant building blocks that can interact with mobile clients and each other, and can simplify implementations of services in mobile networks. We implement three self-stabilizing, fault-tolerant services, each built on the prior services: (1) VSA-to-VSA geographic routing, (2) mobile client location management, and (3) mobile client end-to-end routing. We use a greedy version of the classical depth-first search algorithm to route messages between VSAs in different regions. The mobile client location management service is based on home locations. Each client identifier hashes to a set of home locations, regions whose VSAs are periodically updated with the client's location. VSAs maintain this information and answer queries for client locations. Finally, the VSA-to-VSA routing and location management services are used to implement mobile client end-to-end routing.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 11, 2005
Accession Number
ADA466747

Entities

People

  • Limor Lahiani
  • Nancy Lynch
  • Shlomi Dolev
  • Tina Nolte

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Ad Hoc Networks
  • Algorithms
  • Artificial Intelligence
  • Automata
  • Cellular Networks
  • Computer Programming
  • Computer Science
  • Computers
  • Geographic Regions
  • Hash Tables
  • Machines
  • Mesh Networks
  • Mobile Phones
  • Networks
  • Sensor Networks
  • Two Dimensional
  • Wireless Communications

Fields of Study

  • Computer science

Readers

  • Aerial Delivery - Logistics and Supply Chain Management.
  • Database Systems and Applications
  • Parallel and Distributed Computing.

Technology Areas

  • Space