A Note on Node Coloring in the SINR Model

Bilel Derbel 1, 2, * El-Ghazali Talbi 2
* Auteur correspondant
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : A $\xi$-coloring of a graph $G$ is a coloring of the nodes of $G$ with $\xi$ colors in such a way any two neighboring nodes have different colors. We prove that there exists a $O(\Delta \log n)$ time distributed algorithm computing a $O(\Delta)$-colroing for unit disc graphs under the signal-to-interference-plus-noise ratio (SINR)-based physical model ($\Delta$ is the maximum degree of the graph). We also show that, for a well defined constant $d$, a $d$-hop $O(\Delta)$-coloring allows us to schedule an interference free MAC protocol under the physical SINR constraints. For instance this allows us to prove that any point-to-point message passing algorithm with running time $\tau$ can be simulated in the SINR model in $O(\Delta (\log n + \tau))$ time using messages of well chosen size. All our algorithms are proved to be correct with high probability.
Type de document :
[Research Report] RR-7058, INRIA. 2009, pp.15
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

Contributeur : Bilel Derbel <>
Soumis le : jeudi 22 octobre 2009 - 14:11:16
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 11:21:54


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00408670, version 4


Bilel Derbel, El-Ghazali Talbi. A Note on Node Coloring in the SINR Model. [Research Report] RR-7058, INRIA. 2009, pp.15. 〈inria-00408670v4〉



Consultations de la notice


Téléchargements de fichiers