Construction auto-stabilisante d'un arbre couvrant maximisant le nombre de feuilles - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

Construction auto-stabilisante d'un arbre couvrant maximisant le nombre de feuilles

(1)
1

Abstract

Pour router les messages dans des réseaux auto-organisés, comme les réseaux sans fil ad-hoc ou de senseurs, un ensemble dominant connexe (CDS) est souvent utilisé. La construction d'un arbre couvrant maximisant le nombre de feuilles (MLST) permet d'obtenir un CDS de petite taille pour router les messages dans ce type de réseaux tout en économisant l'énergie. Le paradigme de l'auto-stabilisation est une technique générale et flexible permettant de traiter les fautes transitoires qui peuvent survenir sur les éléments constituant un réseau auto-organisé. Le problème de la construction d'un MLST est un problème NP-difficile à résoudre, ainsi une solution approchée est recherchée. Nous proposons un algorithme distribué et auto-stabilisant pour la construction d'un MLST considérant une topologie arbitraire, sans aucune connaissance sur le réseau et ayant un meilleur rapport d'approximation que les travaux existants. Cet algorithme permet de construire une 1/2-approximation par rapport à une solution optimale, c'est-à-dire que l'arbre couvrant construit possède un nombre de feuilles au moins égal à la moitié des feuilles d'une solution optimale.
Fichier principal
Vignette du fichier
SS_MLST-Algotel.pdf (56.01 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00474180 , version 1 (19-04-2010)

Identifiers

  • HAL Id : inria-00474180 , version 1

Cite

Stephane Rovedakis. Construction auto-stabilisante d'un arbre couvrant maximisant le nombre de feuilles. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel 2010), May 2010, Belle Dune, France. ⟨inria-00474180⟩
107 View
97 Download

Share

Gmail Facebook Twitter LinkedIn More