Fast Data Gathering in Radio Grid Networks

Jean-Claude Bermond 1 Nicolas Nisse 1 Patricio Reyes 1 Hervé Rivano 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The aim of this paper is to design efficient gathering algorithms (data collection) in a Base Station of a wireless multi hop grid network when interferences constraints are present. We suppose the time is slotted and that during one time slot (step) each node can transmit to one of its neighbor at most one data item. Each device is equipped with a half duplex interface; so a node cannot both receive and transmit simultaneously. During a step only non interfering transmissions can be done. In other words, the non interfering calls done during a step will form a matching. The aim is to minimize the number of steps needed to send all messages to the base station, a.k.a. makespan or completion time. The best known algorithm for grids was a multiplicative 1.5-approximation algorithm. In such topologies, we give a very simple +2 approximation algorithm and then a more involved +1 approximation algorithm. Moreover, our algorithms work when no buffering is allowed in intermediary nodes, i.e., when a node receives a message at some step, it must transmit it during the next step.
Type de document :
Rapport
[Research Report] RR-6851, INRIA. 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00363908
Contributeur : Patricio Reyes <>
Soumis le : jeudi 26 mars 2009 - 15:48:59
Dernière modification le : samedi 17 septembre 2016 - 01:34:14
Document(s) archivé(s) le : samedi 26 novembre 2016 - 07:04:08

Fichier

RR-6851.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00363908, version 4

Collections

Citation

Jean-Claude Bermond, Nicolas Nisse, Patricio Reyes, Hervé Rivano. Fast Data Gathering in Radio Grid Networks. [Research Report] RR-6851, INRIA. 2009. 〈inria-00363908v4〉

Partager

Métriques

Consultations de la notice

497

Téléchargements de fichiers

270