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.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00582457
Contributor : Pascale Minet <>
Submitted on : Friday, April 8, 2011 - 5:55:12 PM
Last modification on : Thursday, February 7, 2019 - 4:51:28 PM
Long-term archiving on : Saturday, July 9, 2011 - 2:24:26 AM

Files

RR-7588.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

374

Files downloads

295