Optimal Time Data Gathering in Wireless Networks with Omni-Directional Antennas

Abstract : We study algorithmic and complexity issues originating from the problem of data gathering in wireless networks. We give an algorithm to construct minimum makespan transmission schedules for data gathering when the communication graph $G$ is a tree network, the interference range is \emph{any} integer $m\geq 2$, and no buffering is allowed at intermediate nodes. In the interesting case in which all nodes in the network have to deliver an arbitrary non-zero number of packets, we provide a closed formula for the makespan of the optimal gathering schedule. Additionally, we consider the problem of determining the computational complexity of data gathering in general graphs and show that the problem is weakly NP-complete. On the positive side, we design a simple $(1+2/m)$ factor approximation algorithm for general networks.
Type de document :
Communication dans un congrès
SIROCCO2011, Jun 2011, Gdansk, Poland. Springer, 6796, pp.306-317, 2011, Lecture Notes in Computer Science - LNCS
Liste complète des métadonnées

https://hal.inria.fr/inria-00589687
Contributeur : Jean-Claude Bermond <>
Soumis le : samedi 30 avril 2011 - 13:32:54
Dernière modification le : mardi 22 novembre 2011 - 17:14:34
Document(s) archivé(s) le : dimanche 31 juillet 2011 - 02:27:31

Fichier

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

Identifiants

  • HAL Id : inria-00589687, version 1

Collections

Citation

Jean-Claude Bermond, Luisa Gargano, Stéphane Pérennes, Adele Rescigno, Ugo Vaccaro. Optimal Time Data Gathering in Wireless Networks with Omni-Directional Antennas. SIROCCO2011, Jun 2011, Gdansk, Poland. Springer, 6796, pp.306-317, 2011, Lecture Notes in Computer Science - LNCS. <inria-00589687>

Partager

Métriques

Consultations de
la notice

188

Téléchargements du document

88