Data gathering and personalized broadcasting in radio grids with interference

Jean-Claude Bermond 1 Bi Li 1, 2 Nicolas Nisse 1 Hervé Rivano 3 Min-Li Yu 4
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 URBANET - Réseaux capillaires urbains
CITI - CITI Centre of Innovation in Telecommunications and Integration of services, Inria Grenoble - Rhône-Alpes
Abstract : In the gathering problem, a particular node in a graph, the base station , aims at receiving messages from some nodes in the graph. At each step, a node can send one message to one of its neighbors (such an action is called a call ). However, a node cannot send and receive a message during the same step. Moreover, the communication is subject to interference constraints, more precisely, two calls interfere in a step, if one sender is at distance at most dI from the other receiver. Given a graph with a base station and a set of nodes having some messages, the goal of the gathering problem is to compute a schedule of calls for the base station to receive all messages as fast as possible, i.e., minimizing the number of steps (called makespan). The gathering problem is equivalent to the personalized broadcasting problem where the base station has to send messages to some nodes in the graph, with same transmission constraints.In this paper, we focus on the gathering and personalized broadcasting problem in grids. Moreover, we consider the non-buffering model: when a node receives a message at some step, it must transmit it during the next step. In this setting, though the problem of determining the complexity of computing the optimal makespan in a grid is still open, we present linear (in the number of messages) algorithms that compute schedules for gathering with dI∈{0,1,2}. In particular, we present an algorithm that achieves the optimal makespan up to an additive constant 2 when dI=0. If no messages are “close” to the axes (the base station being the origin), our algorithms achieve the optimal makespan up to an additive constant 1 when dI=0, 4 when dI=2, and 3 when both dI=1 and the base station is in a corner. Note that, the approximation algorithms that we present also provide approximation up to a ratio 2 for the gathering with buffering. All our results are proved in terms of personalized broadcasting.
Type de document :
Article dans une revue
Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 562, pp.453-475. 〈10.1016/j.tcs.2014.10.029〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger
Contributeur : Hervé Rivano <>
Soumis le : jeudi 20 novembre 2014 - 15:05:38
Dernière modification le : mercredi 18 novembre 2015 - 01:10:36
Document(s) archivé(s) le : lundi 23 février 2015 - 08:49:13


Fichiers éditeurs autorisés sur une archive ouverte




Jean-Claude Bermond, Bi Li, Nicolas Nisse, Hervé Rivano, Min-Li Yu. Data gathering and personalized broadcasting in radio grids with interference. Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 562, pp.453-475. 〈10.1016/j.tcs.2014.10.029〉. 〈hal-01084996〉



Consultations de
la notice


Téléchargements du document