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

Ichrak Amdouni 1, * Cédric Adjih 1 Pascale Minet 1
* Corresponding author
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 : Graph coloring is used in wireless networks to optimize network resources: bandwidth and energy. Nodes access the medium according to their color. It is the responsibility of the coloring algorithm to ensure that interfering nodes do not have the same color. In this research report, we focus on wireless sensor networks with grid topologies. How does a coloring algorithm take advantage of the regularity of grid topology to provide an optimal periodic coloring, that is a coloring with the minimum number of colors? We propose the Vector-Based Coloring Method, denoted VCM, a new method that is able to provide an optimal periodic coloring for any radio transmission range and for any h-hop coloring, h>=1. This method consists in determining at which grid nodes a color can be reproduced without creating interferences between these nodes while minimizing the number of colors used. We compare the number of colors provided by VCM with the number of colors obtained by a distributed coloring algorithm with line and column priority assignments. We also provide bounds on the number of colors of optimal general colorings of the infinite grid, and show that periodic colorings (and thus VCM) are asymptotically optimal. Finally, we discuss the applicability of this method to a real wireless network.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00630233
Contributor : Cédric Adjih <>
Submitted on : Friday, October 7, 2011 - 4:58:34 PM
Last modification on : Thursday, February 7, 2019 - 3:03:02 PM
Long-term archiving on : Sunday, January 8, 2012 - 2:35:06 AM

Files

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

Identifiers

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

Share

Metrics

Record views

320

Files downloads

191