Self-stabilizing tree and cluster management for dynamic networks

Abstract

The lack of infrastructure and dynamic nature of mobile ad hoc networks demand new networking strategies to be implemented in order to provide efficient end-to-end communication. Some researches proposed to organize the network into groups called clusters and use different routing protocols for inter and intra cluster to propagate an information. But with these solutions, the network needs first to be organized into clusters and next, we need to construct each routing table. Other researchers proposed to build a spanning tree on the network to forward informations on a tree but many solutions need to know the global network topology. In this paper, we propose a self-stabilizing algorithm both to construct cluster and simultaneously build a spanning tree on the network. Without any global knowledge, we use only one type of periodically exchanged messages of size Log(5n + 3) bits, and we construct clusters and the spanning tree on the network with a convergence time of at most D+6 rounds.