The complexity of data aggregation in static and dynamic wireless sensor networks - Sorbonne Université
Article Dans Une Revue Information and Computation Année : 2017

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

Résumé

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

Dates et versions

hal-01419900 , version 1 (20-12-2016)

Identifiants

Citer

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

Altmetric

Partager

More