A Link Reversal Approach to Distributed Algorithms in Mobile Ad Hoc Networks

Busch, Costas and Tirthapura, Srikanta (2004) A Link Reversal Approach to Distributed Algorithms in Mobile Ad Hoc Networks. Publisher UNSPECIFIED, Ames, IA, USA.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

We present a unified approach to the fundamental problems of leader election, spanning tree maintenance, and routing in mobile ad hoc networks. We give a distributed and local algorithm for solving these problems based on the link reversal technique. Our algorithm is self-stabilizing and deals with arbitrary topological changes, including partitions which divide the network into disjoint connected components. For any connected component with n nodes, the network stabilizes in O(n) operations per node and in O(n^2) time steps. To our knowledge, this is the first link reversal based algorithm which can converge in the presence of network partitions and also has a complete formal analysis.

EPrint Type:	Technical Report
Subjects:	Computer Engineering > SOFTWARE SYSTEMS > Parallel and Distributed Computing
ID Code:	462
Identification Number:	Identification Number UNSPECIFIED
Deposited By:	Dr Srikanta Tirthapura
Deposited On:	30 November 2008

Archive Staff Only: edit this record