Distributed Node Coloring in the SINR Model

Bilel Derbel 1, 2 El-Ghazali Talbi 1, 2
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Given a palette P of at most ξ colors, and a parameter d, a (d,ξ)-coloring of a graph is an assignment of a color from the palette P to every node in the graph such that any two nodes at distance at most d have different colors. We prove that for every n-node unit disk graph with maximum degree Δ, there exists a distributed algorithm computing a (1,O(Δ))-coloring under the SINR (Signal-to-Interference-plus-Noise Ratio) physical model in at most O(Δlogn) time slots, which is optimal up to a logarithmic factor. Our result is based on revisiting a previous coloring algorithm, due to T. Moscibroda and R. Wattenhofer, described in the so called graph-based model~\cite{MW08}. We also prove that, for a well defined constant d, a (d,O(Δ))-coloring allows us to schedule an interference free TDMA-like MAC protocol under the physical SINR constraints. As a corollary, any uniform interference-free message passing algorithm with running time τ can be simulated in the SINR model in O(Δ(logn+τ)) time slots. The latter generic result provides new insights into the distributed scheduling of radio network tasks under the harsh SINR constraints.
Type de document :
Communication dans un congrès
ICDCS 2010 - 30th IEEE International Conference on Distributed Computing Systems, Jun 2010, Genova, Italy. IEEE, Distributed Computing Systems (ICDCS), 2010 IEEE 30th International Conference on, pp.708-717, 2010, 〈10.1109/ICDCS.2010.35〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00524140
Contributeur : Bilel Derbel <>
Soumis le : jeudi 7 octobre 2010 - 09:42:08
Dernière modification le : lundi 23 avril 2018 - 14:14:00

Identifiants

Citation

Bilel Derbel, El-Ghazali Talbi. Distributed Node Coloring in the SINR Model. ICDCS 2010 - 30th IEEE International Conference on Distributed Computing Systems, Jun 2010, Genova, Italy. IEEE, Distributed Computing Systems (ICDCS), 2010 IEEE 30th International Conference on, pp.708-717, 2010, 〈10.1109/ICDCS.2010.35〉. 〈inria-00524140〉

Partager

Métriques

Consultations de la notice

234