Node Coloring in Wireless Networks: Complexity Results and Grid Coloring

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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : Coloring is used in wireless networks to improve communication efficiency, mainly in terms of bandwidth, energy and possibly end-to-end delays. In this paper, we define the h-hop node coloring problem, with h any positive integer, adapted to two types of applications in wireless networks. We specify both general mode for general applications and strategic mode for data gathering applications.We prove that the associated decision problem is NP-complete. We then focus on grid topologies that constitute regular topologies for large or dense wireless networks. We consider various transmission ranges and identify a color pattern that can be reproduced to color the whole grid with the optimal number of colors. We obtain an optimal periodic coloring of the grid for the considered transmission range. We then present a 3-hop distributed coloring algorithm, called SERENA. Through simulation results, we highlight the impact of node priority assignment on the number of colors obtained for any network and grids in particular. We then compare these optimal results on grids with those obtained by SERENA and identify directions to improve SERENA.
Type de document :
Article dans une revue
IFIP Wireless and Mobile Networking Conference WMNC 2011, IFIP, 2011
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00729051
Contributeur : Ichrak Amdouni <>
Soumis le : vendredi 7 septembre 2012 - 12:45:11
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 11:25:17

Fichiers

WMNC11AmdouniI.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00729051, version 1
  • ARXIV : 1209.2810

Collections

Citation

Ichrak Amdouni, Pascale Minet, Cédric Adjih. Node Coloring in Wireless Networks: Complexity Results and Grid Coloring. IFIP Wireless and Mobile Networking Conference WMNC 2011, IFIP, 2011. 〈hal-00729051〉

Partager

Métriques

Consultations de la notice

281

Téléchargements de fichiers

145