A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks

Spanning trees help removing cycles and establishing short paths between a given node and the rest of the nodes in a network. In ad hoc mobile computing networks, however, transient node failures occur due to being out of range or powered off. Therefore, we present a self-stabilized distributed algorithm based on homogeneous agents for constructing a random spanning tree. Our approach makes use of distributed random walks as a network traversal scheme, in order to handle dynamic topology changes in ad hoc wireless networks. Each random walk is represented by a mobile agent annexing a territory over the underlying network. These multiple random walks collapse into a final one that defines the random spanning tree. It will be shown that, compared to deterministically predetermined spanning trees, our algorithm is more resilient to transient failures that occur in ad hoc mobile networks. (C) 2003 Elsevier Science (USA). All rights reserved.