Minimum delay Data Gathering in Radio Networks

Jean-Claude Bermond 1 Nicolas Nisse 1 Patricio Reyes 1 Hervé Rivano 2
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
2 SWING - Smart Wireless Networking
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
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 neighbours 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 to the base station a set of messages generated by the nodes, this completion time is also denoted makespan of the call scheduling. The best known algorithm for open-grids was a multiplicative 1.5-approximation algorithm [Revah, Segal 07]. 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 :
Communication dans un congrès
8th international conference on Ad Hoc Networks and Wireless (AdHoc-Now),, Sep 2009, Murcia, Spain. Springer Verlag, 5793, pp.69-82,, 2009, Lecture Notes in Computer Science,. <http://dx.doi.org/10.1007/978-3-642-04383-3_6>. <10.1007/978-3-642-04383-3_6>
Liste complète des métadonnées

https://hal.inria.fr/inria-00505522
Contributeur : Jean-Claude Bermond <>
Soumis le : vendredi 23 juillet 2010 - 23:27:07
Dernière modification le : samedi 6 novembre 2010 - 20:37:05

Identifiants

Collections

Citation

Jean-Claude Bermond, Nicolas Nisse, Patricio Reyes, Hervé Rivano. Minimum delay Data Gathering in Radio Networks. 8th international conference on Ad Hoc Networks and Wireless (AdHoc-Now),, Sep 2009, Murcia, Spain. Springer Verlag, 5793, pp.69-82,, 2009, Lecture Notes in Computer Science,. <http://dx.doi.org/10.1007/978-3-642-04383-3_6>. <10.1007/978-3-642-04383-3_6>. <inria-00505522>

Partager

Métriques

Consultations de la notice

249