On the Coloring of Grid Wireless Sensor Networks: the Vector-Based Coloring Method

Ichrak Amdouni 1, * Cédric Adjih 1 Pascale Minet 1
* Auteur correspondant
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Résumé : Le coloriage des graphes est utilisé dans les réseaux sans fil afin d'optimiser les ressources du réseau: la bande passante et l'énergie. Les noeuds du réseau accèdent au médium en fonction de leur couleur. L'algorithme de coloriage a la charge d'assurer que les noeuds intereférents n'aient pas la même couleur. Dans ce rapport de recherche, nous nous concentrons sur les réseaux de capteurs sans fil ayant une topologie en grille. Comment un algorithme de coloriage peut profiter de la régularité de cette topologie pour réaliser un coloriage périodique optimal, c'est à dire un coloriage avec le nombre minimal de couleurs? Nous proposons la Méthode des Vecteurs, notée VCM, une nouvelle méthode qui est capable de fournir un coloriage à h sauts, périodique et optimal quelque soit h >= 1 et quelque soit la portée radio. Cette méthode consiste à déterminer quels noeuds de la grille peuvent utiliser la même couleur sans créer des interférences entre ces noeuds tout en minimisant le nombre de couleurs utilisées. Nous comparons le nombre de couleurs utilisées par la Méthode des Vecteurs, à celui obtenu par un algorithme distribué qui affecte les couleurs selon la priorité donnée par la ligne ou la colonne. Nous fournissons aussi des bornes sur le nombre de couleurs des coloriages généraux optimaux de la grille, et prouvons que les coloriages périodiques (et donc VCM) sont asymptotiquement optimaux. Enfin, nous discutons l'applicabilité de cette méthode à un réseau sans fil réel.
Type de document :
Rapport
[Research Report] RR-7756, INRIA. 2011, pp.33
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-00630233
Contributeur : Cédric Adjih <>
Soumis le : vendredi 7 octobre 2011 - 16:58:34
Dernière modification le : mardi 17 avril 2018 - 11:32:49
Document(s) archivé(s) le : dimanche 8 janvier 2012 - 02:35:06

Fichiers

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

Identifiants

  • HAL Id : inria-00630233, version 1
  • ARXIV : 1110.1560

Collections

Citation

Ichrak Amdouni, Cédric Adjih, Pascale Minet. On the Coloring of Grid Wireless Sensor Networks: the Vector-Based Coloring Method. [Research Report] RR-7756, INRIA. 2011, pp.33. 〈inria-00630233〉

Partager

Métriques

Consultations de la notice

267

Téléchargements de fichiers

174