Optimal Time Data Gathering in Wireless Networks with Omni-Directional Antennas - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

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

Résumé

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.
Fichier principal
Vignette du fichier
paper_26finalSIROCCO.pdf (215.06 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00589687 , version 1 (30-04-2011)

Identifiants

  • HAL Id : inria-00589687 , version 1

Citer

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, Lecture Notes in Computer Science - LNCS, 6796, Springer Verlag, Jun 2011, Gdansk, Poland. pp.306-317. ⟨inria-00589687⟩
170 Consultations
171 Téléchargements

Partager

Gmail Facebook X LinkedIn More