Clustering auto-stabilisant à k sauts dans les réseaux Ad Hoc
Résumé
Ad hoc networks offer many applications areas because of their easy of deployment. Communication that takes place by diffusion is typically expensive and may cause network saturation. To optimize these communications, one approach is to structure the network into clusters. In this paper, we present a self-stabilizing asynchronous distributed algorithm that builds k-hops clusters. Our approach does not require any initialization. It is based only on information from neighboring nodes with periodic exchange of messages. 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 at most n + 2 transitions and uses at most n ∗ log(2n + k + 3) space, where n is the number of network nodes. Using the Omnet++ simulator, we performed an evaluation of our approach.
Les réseaux ad hoc offrent de nombreux domaines d'application du fait de leur facilité de déploiement. La communication qui s'effectue classiquement par diffusion est couteuse et peut entrainer une saturation du réseau. Pour optimiser ces communications, une approche est de structurer le réseau en clusters. Dans cet article, nous présentons un algorithme de clustering asynchrone, distribué et auto-stabilisant qui construit des clusters à k sauts. Notre approche ne nécessite aucune initialisation. Elle se base uniquement sur l'information provenant des noeuds voisins à l'aide d'échange périodique de messages. Partant d'une configuration quelconque, le réseau converge à un état stable au bout d'un nombre fini d'étapes. Par un schéma de preuve, nous montrons que pour un réseau de n noeuds, la stabilisation est atteinte au plus en n+2 transitions et nécessite au plus une occupation mémoire de n*log(2n+k+3). Avec des simulations sous Omnet++, nous évaluons les performances moyennes de notre algorithme.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...