Node coloring for dense wireless sensor networks

Ichrak Amdouni 1 Pascale Minet 1 Cédric Adjih 1
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR
Résumé : Le coloriage est utilisée dans les réseaux sans fil pour améliorer l'efficacité des communications, principalement en termes de bande passante, énergie et éventuellement délais de bout-en-bout. Dans ce rapport de recherche, nous définissons le problème de coloriage des noeuds à h sauts, avec h entier positif quelconque. Nous prouvons que le problème de décision associé est NP-complet. Nous présentons un algorithme de coloriage à 3 sauts distribué qui est optimisé pour des réseaux denses: un noeud ne doit plus échanger les couleurs et priorités de ses voisins à 2 sauts. Nous mettons en évidence à travers des résultats de simulation, l'impact de l'assignation de priorité sur le nombre de couleurs obtenu pour un réseau quelconque. Nous nous intéressons ensuite aux réseaux en grille et identifions un motif colorié pouvant être reproduit pour colorier entièrement la grille. Nous montrons comment l'algorithme de coloriage peut utiliser les propriétés de régularité pour obtenir un motif périodique avec le nombre optimal de couleurs. Nous considérons ensuite des grilles avec trous et étudions comment étendre nos résultats.
Type de document :
Rapport
[Research Report] RR-7588, INRIA. 2011, pp.35
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00582457
Contributeur : Pascale Minet <>
Soumis le : vendredi 8 avril 2011 - 17:55:12
Dernière modification le : jeudi 11 janvier 2018 - 01:50:30
Document(s) archivé(s) le : samedi 9 juillet 2011 - 02:24:26

Fichiers

RR-7588.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00582457, version 1
  • ARXIV : 1104.1859

Collections

Citation

Ichrak Amdouni, Pascale Minet, Cédric Adjih. Node coloring for dense wireless sensor networks. [Research Report] RR-7588, INRIA. 2011, pp.35. 〈inria-00582457〉

Partager

Métriques

Consultations de la notice

293

Téléchargements de fichiers

259