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
Résumé : Nous présentons des algorithmes efficaces pour la collecte d'informations par une station de base au sein d'un réseau sans-fil multi sauts en présence d'interférences. Nous nous focalisons sur les réseaux en grille car ils sont un bon modèle des réseaux d'accès comme des réseaux aléatoires de capteurs. Le temps est divisé en étapes élémentaires. Au cours d'une étape, un nœud peut transmettre au plus un message à l'un de ces voisins. Chaque appareil est équipé d'un interface half duplex et ne peut donc émettre et recevoir à la même étape. Ainsi, au cours d'une étape, l'ensemble des transmissions valides induit un couplage de la grille. Le problème consiste à minimiser le nombre d'étapes nécessaires à la collecte de tous les messages par la station de base. Le meilleur algorithme connu était une 3/2 approximation. Nous donnons un algorithme très simple qui approche l'optimum à 2 près, puis nous présentons un algorithme plus évolué qui est une +1 approximation. Nos résultats sont valides lorsque les appareils ne disposent d'aucune mémoire tampon et doivent retransmettre un message à l'étape suivant sa réception.
Type de document :
Communication dans un congrès
Chaintreau, Augustin and Magnien, Clemence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009
Liste complète des métadonnées


https://hal.inria.fr/inria-00376040
Contributeur : Patricio Reyes <>
Soumis le : jeudi 7 mai 2009 - 13:02:27
Dernière modification le : lundi 11 mai 2009 - 18:26:56
Document(s) archivé(s) le : jeudi 10 juin 2010 - 20:43:59

Fichier

BNRR09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00376040, version 1

Collections

Citation

Jean-Claude Bermond, Nicolas Nisse, Patricio Reyes, Hervé Rivano. Fast Data Gathering in Radio Grid Networks. Chaintreau, Augustin and Magnien, Clemence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009. <inria-00376040>

Partager

Métriques

Consultations de
la notice

170

Téléchargements du document

244