Self-stabilization in Self-organized Multihop Wireless Networks

International audienceIn 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