Self-stabilization in Self-organized Wireless Multihop Networks
N. Mitton, B. Sericola, S. Tixeuil, E. Fleury and Guérin Lassous
In large scale multihop wireless networks, flat architectures are typically not scalable. Clustering was introduced to support self-organization and enable hierarchical routing. When dealing with multihop wireless networks, robustness is a crucial issue due to the dynamics of such networks. Several algorithms have been designed for clustering but to date, in none of them the self-stabilization features of the resulting structure have been investigated.
In this paper, we show that a clustering algorithm, known for its good robustness properties, is actually self-stabilizing. We propose several enhancements to the scheme to reduce the stabilization time and thus improve stability in a dynamic environment. The key technique to these enhancements is a localized self-stabilizing algorithm for Directed Acyclic Graph (DAG) construction.We provide extensive studies (both theoretical and experimental) that show that our approach enables efficient yet adaptive clustering in wireless multihop networks.
Keywords: multihop wireless networks, clustering, self-stabilization, scalability, coloring, theoretical analysis, Markov chains.