Agrégation Distribuée de Données dans les Réseaux Dynamiques - ALGOTEL 2017 — 19èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications
Communication Dans Un Congrès Année : 2017

Agrégation Distribuée de Données dans les Réseaux Dynamiques

Résumé

L'agrégation de données dans un réseau est un problème central pour de nombreuses applications. Il consiste a récupérer les données de chaque noeud du réseau, en supposant que deux données peuvent être agrégées en une seule, et que chaque noeud ne transmet une donnée qu'une seule fois. Des solutions distribuées performantes (du point de vue du délai) existent dans le cas d'un réseau statique, même en présence de collisions (comme dans les réseaux de capteurs sans fil). Cependant, dans le cas des réseaux dynamiques, le problème est NP-difficile, même avec un algorithme centralisé qui connait l'évolution future du réseau. Dans cet article, nous étudions le problème de l'agrégation de données dans des réseaux dynamiques par un algorithme distribué, dans le cas où il n'y a pas de collisions. Après avoir défini formellement le problème, nous prouvons qu'il n'est pas solvable sans connaissance supplémentaire, face à un adversaire sans mémoire, et ce même avec un algorithme probabiliste. Ensuite, nous étudions le problème face à un adversaire probabiliste choisissant les interactions dans le réseau de manière aléatoire. Dans ce cas nous donnons des algorithmes optimaux utilisant (i) une connaissance partielle du future ou (ii) aucune connaissance.
Fichier principal
Vignette du fichier
DODA_algotel.pdf (159.46 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01518548 , version 1 (04-05-2017)

Identifiants

  • HAL Id : hal-01518548 , version 1

Citer

Quentin Bramas, Toshimitsu Masuzawa, Sébastien Tixeuil. Agrégation Distribuée de Données dans les Réseaux Dynamiques. ALGOTEL 2017 - 19èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2017, Quiberon, France. ⟨hal-01518548⟩
424 Consultations
320 Téléchargements

Partager

More