Vers une structuration auto-stabilisante des réseaux Ad HocReport as inadecuate




Vers une structuration auto-stabilisante des réseaux Ad Hoc - Download this document for free, or read online. Document in PDF available to download.

1 CRESTIC - Centre de Recherche en Sciences et Technologies de l-Information et de la Communication 2 CERMICS - Centre d-Enseignement et de Recherche en Mathématiques et Calcul Scientifique 3 LID - Laboratoire d-Informatique de Dakar

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* log2n+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.

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 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 log2n + 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.

en fr

Keywords : Ad hoc networks clustering distributed algorithms self-stabilizing OMNeT++.

Mots-clés : réseaux Ad Hoc clustering algorithmes distribués auto-stabilisation OMNeT++





Author: Mandicou Ba - Olivier Flauzac - Bachar Salim Haggar - Rafik Makhloufi - Florent Nolot - Ibrahima Niang -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents