J. Bermond, N. Nisse, P. Reyes, and H. Rivano. 11èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'09), (June 2009)
Abstract
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 noeud 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.
%0 Conference Paper
%1 BNR+09b
%A Bermond, J.-C.
%A Nisse, N.
%A Reyes, P.
%A Rivano, H.
%B 11èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'09)
%D 2009
%K Perso distributed gathering wireless
%T Fast Data Gathering in Radio Grid Networks
%U http://www.lif.univ-mrs.fr/algotel09
%X 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 noeud 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.
@inproceedings{BNR+09b,
abstract = {Nous pr{\'e}sentons des algorithmes efficaces pour la
collecte d'informations par une station de base au sein d'un r{\'e}seau
sans-fil multi sauts en pr{\'e}sence d'interf{\'e}rences. Nous nous
focalisons sur les r{\'e}seaux en grille car ils sont un bon mod{\`e}le des
r{\'e}seaux d'acc{\`e}s comme des r{\'e}seaux al{\'e}atoires de capteurs. Le
temps est divis{\'e} en {\'e}tapes {\'e}l{\'e}mentaires. Au cours d'une {\'e}tape,
un noeud peut transmettre au plus un message {\`a} l'un de ces voisins.
Chaque appareil est {\'e}quip{\'e} d'un interface half duplex et ne peut
donc {\'e}mettre et recevoir {\`a} la m{\^e}me {\'e}tape. Ainsi, au cours d'une
{\'e}tape, l'ensemble des transmissions valides induit un couplage de la
grille. Le probl{\`e}me consiste {\`a} minimiser le nombre d'{\'e}tapes
n{\'e}cessaires {\`a} la collecte de tous les messages par la station de
base. Le meilleur algorithme connu {\'e}tait une 3/2 approximation. Nous
donnons un algorithme tr{\`e}s simple qui approche l'optimum {\`a} 2 pr{\`e}s,
puis nous pr{\'e}sentons un algorithme plus {\'e}volu{\'e} qui est une +1
approximation. Nos r{\'e}sultats sont valides lorsque les appareils ne
disposent d'aucune m{\'e}moire tampon et doivent retransmettre un
message {\`a} l'{\'e}tape suivant sa r{\'e}ception.},
added-at = {2009-08-07T13:37:48.000+0200},
author = {Bermond, J.-C. and Nisse, N. and Reyes, P. and Rivano, H.},
biburl = {https://www.bibsonomy.org/bibtex/202cb0f4663b44d5298564f4be4787c18/herverivano},
booktitle = {11{\`e}mes Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel'09)},
date-added = {2009-08-07 13:05:23 +0200},
date-modified = {2009-08-07 13:34:14 +0200},
description = {Ma biblio},
interhash = {84e67a4023363e77f7c9941b7eff9484},
intrahash = {02cb0f4663b44d5298564f4be4787c18},
keywords = {Perso distributed gathering wireless},
month = {June},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BNRR09.pdf},
timestamp = {2009-08-21T11:01:27.000+0200},
title = {Fast Data Gathering in Radio Grid Networks},
url = {http://www.lif.univ-mrs.fr/algotel09},
year = 2009
}