Skip to Main content Skip to Navigation
Conference papers

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

Jean-Claude Bermond 1 Luisa Gargano 2 Stéphane Pérennes 1 Adele Rescigno 2 Ugo Vaccaro 2 
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Complete list of metadata
Contributor : Jean-Claude Bermond Connect in order to contact the contributor
Submitted on : Saturday, April 30, 2011 - 1:32:54 PM
Last modification on : Saturday, June 25, 2022 - 11:05:55 PM
Long-term archiving on: : Sunday, July 31, 2011 - 2:27:31 AM


Files produced by the author(s)


  • HAL Id : inria-00589687, version 1



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, Gdansk University of technology, Jun 2011, Gdansk, Poland. pp.306-317. ⟨inria-00589687⟩



Record views


Files downloads