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:
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.
Archive Staff Only: edit this record