Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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, 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 research report, we define the h-hop node coloring problem, with h any positive integer. We prove that the associated decision problem is NP-complete. We then present a 3-hop distributed coloring algorithm that is optimized for dense networks: a node does not need to exchange the priorities and colors of its 2-hop neighbors. Through simulation results, we highlight the impact of priority assignment on the number of colors obtained for any network. We then focus on grids and identify a color pattern that can be reproduced to color the whole grid. We show how the coloring algorithm can use regularity properties to obtain a periodic color pattern with the optimal number of colors. We then consider grids with holes and study how to extend our results.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Pascale Minet Connect in order to contact the contributor
Submitted on : Friday, April 8, 2011 - 5:55:12 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:18 AM
Long-term archiving on: : Saturday, July 9, 2011 - 2:24:26 AM


Files produced by the author(s)


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



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



Record views


Files downloads