Agréger Rapidement des Données est Difficile

Résumé : La première utilisation des réseaux de capteurs sans fil est l'agrégation des données collectées par chaque capteur, de manière économe en énergie. Dans ce papier, nous présentons le problème de l'agrégation des données de manière formelle dans les réseaux de capteurs dynamiques (dont la topologie évolue avec le temps). Dans les réseaux statiques de degré au plus quatre, il a déjà été prouvé que résoudre ce problème en minimisant le délai est NP-Complet. Il en est donc de même dans les réseaux dynamiques. Notre première contribution est de caractériser exactement ce qui fait de l'agrégation de données un problème NP-Complet. En effet, dans les réseaux statiques, où le problème est trivial pour les réseaux de degré au plus deux, nous montrons que le problème reste NP-Complet dans les réseaux de degré au plus trois. De même, le problème est trivial dans les réseaux dynamiques de degré au plus un et nous montrons qu'il est NP-Complet dans les réseaux dynamiques de degré au plus deux. Nous montrons donc que l'ajout de la dynamique rend le problème de l'agrégation de données intrinsèquement plus difficile. Notre deuxième contribution est de présenter des bornes inférieures et supérieures pour la durée d'agrégation des données dans un réseau dynamique. Là encore, l'ajout de la dynamique augmente la durée d'agrégation des données dans le pire des cas.
Type de document :
Communication dans un congrès
ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, France
Liste complète des métadonnées

https://hal.sorbonne-universite.fr/hal-01144458
Contributeur : Quentin Bramas <>
Soumis le : mardi 21 avril 2015 - 16:39:40
Dernière modification le : jeudi 22 novembre 2018 - 14:30:41
Document(s) archivé(s) le : mercredi 19 avril 2017 - 02:25:39

Fichier

mdat_algotel2015.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01144458, version 1

Citation

Quentin Bramas, Sébastien Tixeuil. Agréger Rapidement des Données est Difficile. ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, France. 〈hal-01144458〉

Partager

Métriques

Consultations de la notice

507

Téléchargements de fichiers

367