Mandicou Ba ; Olivier Flauzac ; Bachar Salim Haggar ; Rafik Makhloufi ; Florent Nolot et al. - Vers une structuration auto-stabilisante des réseaux Ad Hoc

arima:1970 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, 4 août 2014, Volume 17 - 2014 - Numéro spécial - CARI'12 - https://doi.org/10.46298/arima.1970
Vers une structuration auto-stabilisante des réseaux Ad HocArticle

Auteurs : Mandicou Ba 1; Olivier Flauzac ORCID1; Bachar Salim Haggar 1; Rafik MAKHLOUFI ; Florent Nolot ORCID1; Ibrahima Niang 2

[en]
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.

[fr]
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 aucuneinitialisation. Elle se fonde uniquement sur l’information provenant des noeuds voisins à l’aided’échanges de messages. Partant d’une configuration quelconque, le réseau converge vers un étatstable après un nombre fini d’étapes. Nous montrons par preuve formelle que pour un réseau de nnoeuds, la stabilisation est atteinte en au plus n + 2 transitions. De plus, l’algorithme nécessite uneoccupation mémoire de (u + 1) log(2n + k + 3) bits pour chaque noeud u où u représente ledegré (nombre de voisins) de u et k la distance maximale dans les clusters. Afin de consolider lesrésultats théoriques obtenus, nous avons effectué une campagne de simulation sous OMNeT++ pourévaluer la performance de notre solution.


Volume : Volume 17 - 2014 - Numéro spécial - CARI'12
Publié le : 4 août 2014
Soumis le : 26 janvier 2014
Mots-clés : [INFO]Computer Science [cs], [MATH]Mathematics [math], [en] Ad hoc networks, clustering, distributed algorithms, self-stabilizing, OMNeT++.; [fr] réseaux Ad Hoc, clustering, algorithmes distribués, auto-stabilisation, OMNeT++

Statistiques de consultation

Cette page a été consultée 537 fois.
Le PDF de cet article a été téléchargé 518 fois.