Agrégation Distribuée de Données dans les Réseaux Dynamiques
Abstract
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.
Origin : Files produced by the author(s)