VCM: The Vector-Based Coloring Method for Grid Wireless AdHhoc and Sensor Networks

Cédric Adjih 1 Ichrak Amdouni 1 Pascale Minet 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 : Graph coloring is used in wireless ad hoc and sensor 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 paper, we focus on wireless ad hoc and 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. In h-hop coloring, no nodes that are p-hop away, with 1<= p <= h use the same color. 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. Finally, we discuss the applicability of this method to a real wireless network.
Complete list of metadatas

https://hal.inria.fr/hal-00757324
Contributor : Saoucene Mahfoudh <>
Submitted on : Monday, November 26, 2012 - 4:18:15 PM
Last modification on : Wednesday, January 23, 2019 - 10:29:24 AM

Identifiers

Collections

Citation

Cédric Adjih, Ichrak Amdouni, Pascale Minet. VCM: The Vector-Based Coloring Method for Grid Wireless AdHhoc and Sensor Networks. MSWIM 2012 - 15th ACM International Conference on Modeling, Analysis, Oct 2012, Paphos, Cyprus. pp.213-222, ⟨10.1145/2387238.2387275⟩. ⟨hal-00757324⟩

Share

Metrics

Record views

290