Robust Self-Stabilizing Clustering Algorithm

Ad hoc networks consist of wireless hosts that communicate with each other in the absence of a fixed infrastructure. Such network cannot rely on centralized and organized network management. The clustering problem consists in partitioning network nodes into groups called clusters, thus giving at the network a hierarchical organization. A self-stabilizing algorithm, regardless of the initial system state, converges in finite time to a set of states that satisfy a legitimacy predicate without external intervention. Due to this property, self-stabilizing algorithms tolerate transient faults. In this paper we present a robust self-stabilizing clustering algorithm for ad hoc network. The robustness property guarantees that, starting from an arbitrary state, in one round, network is partitioned into clusters. After that, network stays partitioned during the convergence toward a legitimate configuration where the clusters partition is optimal. Keywords: Self-stabilization, Distributed algorithm, Clustering, Ad hoc networking. Résumé Les réseaux ad hoc se composent d’hôtes qui communiquent les uns avec les autres en l’absence d’une infrastructure fixe. A eux de prendre en charge l’organisation du réseau (routage, gestion de la bande passante, connectivité). Un tel réseau ne peut pas compter sur la connectivité centralisée et organisée. Le problème clustering consiste à partitionner les noeuds d’un réseau en grappes, donc établissant une organisation hiérarchique au réseau. Un algorithme auto-stabilisant, indépendant de l’état initial du système, converge à un ensemble de l’état qui satisfait à un prédicat légitime dans un temps fini, sans intervention externe. Grâce à cette propriété, les algorithmes auto-stabilisants tolèrent les défaillances transitoires. Dans cet article nous présentons un algorithme auto-stabilisant robuste d’agrégation pour les réseaux ad hoc. La propriété de robustesse garantit que, à partir d’un état arbitraire, en un round, le réseau est partitionné en grappes. Après, le système évolue pour converger vers une configuration légitime où la partition est optimale