The complexity of data aggregation in static and dynamic wireless sensor networks

Quentin Bramas 1, * Sébastien Tixeuil 2, 1
* Corresponding author
1 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : The contribution of this paper is threefold. First, we give tight bounds for the complexity of the problem of data aggregation in static networks. In more details, we show that the problem remains NP-complete when the graph is of degree at most three. Second, we investigate the complexity of the same problem in a dynamic network, that is, a network whose topology can evolve through time. In the case of dynamic networks, we show that the problem is NP-complete even in the case where the graph is of degree at most two. Third, we give the first lower and upper bounds for the minimum data aggregation time in a dynamic graph. We also observe that even in a well-connected evolving graphs, the optimal solution cannot be found by a distributed algorithm or by a centralized algorithm that does not know the future.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.sorbonne-universite.fr/hal-01419900
Contributor : Gestionnaire Hal-Upmc <>
Submitted on : Tuesday, December 20, 2016 - 10:17:17 AM
Last modification on : Wednesday, May 15, 2019 - 4:12:39 AM
Long-term archiving on : Tuesday, March 21, 2017 - 5:46:33 AM

File

Bramas_The_complexity_of.pdf
Files produced by the author(s)

Identifiers

Citation

Quentin Bramas, Sébastien Tixeuil. The complexity of data aggregation in static and dynamic wireless sensor networks. Information and Computation, Elsevier, 2017, 255 (3), pp.369-383. ⟨10.1016/j.ic.2016.12.004⟩. ⟨hal-01419900⟩

Share

Metrics

Record views

523

Files downloads

231