J. Bermond, N. Nisse, P. Reyes, and H. Rivano. Proceedings of the 8th international conference on Ad Hoc Networks and Wireless (AdHoc-Now), (2009)to appear.
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.
%0 Conference Paper
%1 BNR+09a
%A Bermond, J.-C.
%A Nisse, N.
%A Reyes, P.
%A Rivano, H.
%B Proceedings of the 8th international conference on Ad Hoc Networks and Wireless (AdHoc-Now)
%D 2009
%K Perso delay distributed gathering wireless
%T Minimum delay Data Gathering in Radio Networks
%U http://hal.inria.fr/inria-00363908/fr/
%X 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.
@inproceedings{BNR+09a,
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.},
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/2c59d6e2e873a9853bdd0486da9560064/herverivano},
booktitle = {Proceedings of the 8th international conference on Ad Hoc Networks and Wireless (AdHoc-Now)},
date-added = {2009-08-07 13:05:23 +0200},
date-modified = {2009-08-07 13:06:30 +0200},
description = {Ma biblio},
interhash = {c1dfa64b435658bc4283e939c70e5957},
intrahash = {c59d6e2e873a9853bdd0486da9560064},
keywords = {Perso delay distributed gathering wireless},
note = {to appear},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/adHocNow09.pdf},
timestamp = {2009-08-21T11:03:28.000+0200},
title = {Minimum delay Data Gathering in Radio Networks},
url = {http://hal.inria.fr/inria-00363908/fr/},
year = 2009
}