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.
Type de document :
Communication dans un congrès
Maria Gradinariu Potop-Butucaru et Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel 2010), May 2010, Belle Dune, France. 2010
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00474180
Contributeur : Stephane Rovedakis <>
Soumis le : lundi 19 avril 2010 - 11:46:47
Dernière modification le : jeudi 9 février 2017 - 15:49:56
Document(s) archivé(s) le : mardi 28 septembre 2010 - 11:56:26

Fichier

SS_MLST-Algotel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00474180, version 1

Collections

Citation

Stephane Rovedakis. Construction auto-stabilisante d'un arbre couvrant maximisant le nombre de feuilles. Maria Gradinariu Potop-Butucaru et Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel 2010), May 2010, Belle Dune, France. 2010. 〈inria-00474180〉

Partager

Métriques

Consultations de la notice

150

Téléchargements de fichiers

122