Evaluation de requêtes dans des réseaux ad hoc dynamiques

de Tiantian YIN
sous la direction de Stéphane Grumbach (LIAMA, Pékin) et Christophe Bobineau (HADAS)

Résumé

Nous assistons à une extraordinaire popularisation de réseaux opportunistes (ad hoc) de calculateurs autonomes. Et ce du fait (i) du développement de ces calculateurs de plus en plus petits et autonomes et de moins en moins coûteux à produire ; (ii) de l'augmentation constante de la puissance de calcul et de la capacité de stockage de ces calculateurs ; et (iii), des efforts de standardisation des communications informatiques sans fil et des formats d'échange de données.
De nouvelles applications pour ces réseaux émergent dans de nombreux domaines tels que le transport intelligent, les jeux, les réseaux sociaux, les réseaux de capteurs, l'intelligence ambiante, etc. Ces nouvelles applications font souvent intervenir de grands volumes de données qui ne sont plus stockées sur des serveurs fixes mais sur chacun des calculateurs du réseau. Dans plusieurs familles d'applications, les calculateurs génèrent eux-mêmes des données (ex : capteurs).
Les techniques classiques d'évaluation de requêtes ne sont pas applicables dans ce contexte. La distribution à la fois des données et du calcul nécessite l'utilisation de techniques d'optimisation de requêtes distribuées, décomposant une requêtes en sous requêtes qui seront évaluées sur des calculateurs différents. Ces techniques ont été largement étudiées dans le cadre des systèmes de gestion de bases de données distribuées. Néanmoins, les réseaux ad hoc de calculateurs autonomes sont bien différents des bases de données distribuées. En effet, l'absence de connaissances sur la distribution et l'organisation des données, le manque de contrôle, l'absence d'une quelconque vue globale du système imposent la nécessité de développer de nouveaux algorithmes d'évaluation de requêtes, totalement adaptatifs, entraînant une évolution continue de la requête durant son évaluation.
De plus, les réseaux ad hoc de calculateurs autonomes sont très dynamiques. Du fait de lur taille et de leur autonomie électrique, de tels calculateurs sont très mobiles et sont donc sujets à de fréquentes connexions et déconnexions du réseau ad hoc. Les algorithmes d'évaluation de requêtes doivent donc s'adapter à ces changements dans l'environnement d'exécution, car chacun des calculateurs correspond à une source de données et à une puissance de calcul.
Les travaux sur de tels environnements ont été menés uniquement dans des cas bien spécifiques (ex : pair-à-pair, réseaux de capteurs).
L'objectif de cette thèse est de développer et d'implémenter des algorithmes adaptatifs d'évaluation de requêtes distribuées qui permettent d'évaluer des requêtes génériques et complexes sur un ensemble indéterminé de noeuds pris d'un réseau ad hoc dynamique.