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, Polytechnique - X, 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.
Type de document :
Communication dans un congrès
MSWIM 2012 - 15th ACM International Conference on Modeling, Analysis, Oct 2012, Paphos, Cyprus. ACM, pp.213-222, 2012, 〈10.1145/2387238.2387275〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00757324
Contributeur : Saoucene Mahfoudh <>
Soumis le : lundi 26 novembre 2012 - 16:18:15
Dernière modification le : jeudi 11 janvier 2018 - 06:22:23

Identifiants

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. ACM, pp.213-222, 2012, 〈10.1145/2387238.2387275〉. 〈hal-00757324〉

Partager

Métriques

Consultations de la notice

238