MIT Libraries logoDSpace@MIT

MIT
View Item 
  • DSpace@MIT Home
  • Computer Science and Artificial Intelligence Lab (CSAIL)
  • CSAIL Digital Archive
  • CSAIL Technical Reports (July 1, 2003 - present)
  • View Item
  • DSpace@MIT Home
  • Computer Science and Artificial Intelligence Lab (CSAIL)
  • CSAIL Digital Archive
  • CSAIL Technical Reports (July 1, 2003 - present)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Self-Stabilizing Message Routing in Mobile ad hoc Networks

Author(s)
Lynch, Nancy; Lahiani, Limor; Dolev, Shlomi; Nolte, Tina
Thumbnail
DownloadMIT-CSAIL-TR-2009-003.pdf (552.7Kb)
Additional downloads
MIT-CSAIL-TR-2009-003.ps (2.751Mb)
Other Contributors
Theory of Computation
Advisor
Nancy Lynch
Metadata
Show full item record
Abstract
We present a self-stabilizing algorithm for routing messages between arbitrary pairs of nodes in a mobile ad hoc network. Our algorithm assumes the availability of a reliable GPS service, which supplies mobile nodes with accurate information about real time and about their own geographical locations. The GPS service provides an external, shared source of consistency for mobile nodes, allowing them to label and timestamp messages, and thereby aiding in recovery from failures. Our algorithm utilizes a Virtual Infrastructure programming abstraction layer, consisting of mobile client nodes, virtual stationary timed machines called Virtual Stationary Automata (VSAs), and a local broadcast service connecting VSAs and mobile clients. VSAs are associated with predetermined regions in the plane, and are emulated in a self-stabilizing manner by the mobile nodes. VSAs are relatively stable in the face of node mobility and failure, and can be used to simplify algorithm development for mobile networks. Our routing algorithm consists of three subalgorithms: [(1)] a VSA-to-VSA geographical routing algorithm, [2] a mobile client location management algorithm, and [3] the main algorithm, which utilizes both location management and geographical routing. All three subalgorithms are self-stabilizing, and consequently, the entire algorithm is also self-stabilizing.
Date issued
2009-01-28
URI
http://hdl.handle.net/1721.1/44516
Citation
Closely based on chapters 12-14 of Tina Nolte's MIT PhD Thesis, 2009.
Series/Report no.
MIT-CSAIL-TR-2009-003
Keywords
Self-stabilizing algorithms, Mobile ad-hoc networks, Routing algorithms

Collections
  • CSAIL Technical Reports (July 1, 2003 - present)
  • Technical Reports and Memos

Browse

All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

Login

Statistics

OA StatisticsStatistics by CountryStatistics by Department
MIT Libraries
PrivacyPermissionsAccessibilityContact us
MIT
Content created by the MIT Libraries, CC BY-NC unless otherwise noted. Notify us about copyright concerns.