Optimal Time Data Gathering in Wireless Networks with Multidirectional Antennas

Jean-Claude Bermond 1 Luisa Gargano 2 Stéphane Pérennes 1 Adele Rescigno 2 Ugo Vaccaro 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A Wireless Network consists of a large number of devices, deployed over a geographical area, and of a base station where data sensed by the devices are collected and accessed by the end users. In this paper 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 under the following hypotheses: the communication graph G is a tree network, the transmissions in the network can interfere with each other up to distance m, where m ≥ 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 NP-complete. On the positive side, we design a simple (1+2/m)-factor approximation algorithm for general networks.
Liste complète des métadonnées

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-00905187
Contributor : Jean-Claude Bermond <>
Submitted on : Sunday, November 17, 2013 - 1:47:59 PM
Last modification on : Friday, April 12, 2019 - 10:18:03 AM
Document(s) archivé(s) le : Tuesday, February 18, 2014 - 3:00:24 AM

File

journal-revised-II-15-1-13.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Claude Bermond, Luisa Gargano, Stéphane Pérennes, Adele Rescigno, Ugo Vaccaro. Optimal Time Data Gathering in Wireless Networks with Multidirectional Antennas. Theoretical Computer Science, Elsevier, 2013, 509, pp.122-139. ⟨10.1016/j.tcs.2013.03.017⟩. ⟨hal-00905187⟩

Share

Metrics

Record views

519

Files downloads

232