Skip to Main content Skip to Navigation
Conference papers

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

Résumé : 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.
Complete list of metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/inria-00474180
Contributor : Stephane Rovedakis <>
Submitted on : Monday, April 19, 2010 - 11:46:47 AM
Last modification on : Tuesday, October 6, 2020 - 9:20:05 AM
Long-term archiving on: : Tuesday, September 28, 2010 - 11:56:26 AM

File

SS_MLST-Algotel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00474180, version 1

Citation

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⟩

Share

Metrics

Record views

185

Files downloads

151