A Note on Node Coloring in the SINR Model - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

A Note on Node Coloring in the SINR Model

Résumé

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.
Fichier principal
Vignette du fichier
RR-7058.pdf (195.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00408670 , version 1 (31-07-2009)
inria-00408670 , version 2 (09-10-2009)
inria-00408670 , version 3 (09-10-2009)
inria-00408670 , version 4 (22-10-2009)

Identifiants

  • HAL Id : inria-00408670 , version 3

Citer

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

Collections

INRIA-RRRT LIFL
145 Consultations
151 Téléchargements

Partager

Gmail Facebook X LinkedIn More