|
RÉSUMÉ.
Dans cet article, nous proposons un algorithme de structuration auto-stabilisant, distribué
et asynchrone qui construit des clusters de diamètre au plus 2k. Notre approche ne nécessite aucune
initialisation. Elle se fonde uniquement sur l'information provenant des noeuds voisins à l'aide
d'échanges de messages. Partant d'une configuration quelconque, le réseau converge vers un état
stable après un nombre fini d'étapes. Nous montrons par preuve formelle que pour un réseau de n
noeuds, la stabilisation est atteinte en au plus n + 2 transitions. De plus, l'algorithme nécessite une
occupation mémoire de (u + 1) * log(2n + k + 3) bits pour chaque noeud u où Δu représente le
degré (nombre de voisins) de u et k la distance maximale dans les clusters. Afin de consolider les
résultats théoriques obtenus, nous avons effectué une campagne de simulation sous OMNeT++ pour
évaluer la performance de notre solution.
ABSTRACT.
In this paper, we present a self-stabilizing asynchronous distributed clustering 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.
Firstly, we prove that the stabilization is reached after at most n+2 transitions and requires (u+1)*
log(2n+k+3) bits per node, whereΔu represents node's degree, n is the number of network nodes
and k represents the maximum hops number. Secondly, using OMNet++ simulator, we performed an
evaluation of our proposed algorithm.
MOTS-CLÉS :
Réseaux Ad Hoc, clustering, algorithmes distribués, auto-stabilisation, OMNeT++.
KEYWORDS:
Ad hoc networks, clustering, distributed algorithms, self-stabilizing, OMNeT++.
|
présentation