Self-stabilizing k-hops clustering algorithm for wireless ad hoc networks
Mandicou Ba, Olivier Flauzac, Bachar Salim Haggar, Florent Nolot, Ibrahima Niang · 2013
Most Ad Hoc networks use communications based on diffusion that are typically expensive and may cause network saturation. In order to optimize these communications, one approach is to structure networks into clusters. In this paper, we present a self-stabilizing asynchronous distributed algorithm that builds non-overlapping k-hops clusters. Our approach does not require any initialization. It is based only on information from neighboring nodes with periodic messages exchange. Starting from an arbitrary configuration, the network converges to a stable state after a finite number of steps. We prove that the stabilization is reached after at most n + 2 transitions and uses at most n * log(2n + k + 3) memory space, where n is the number of network nodes. Using the OMNeT++ simulator, we performed an evaluation of the proposed algorithm.