Titre : Réseaux de capteurs : la marche de l’empereur
Encadrants : C. Delporte, H. Fauconnier
Contact : cd@liafa.jussieu.fr, hf@liafa.jussieu.fr
Lieu : LIAFA-Université Paris 7, 173 rue du Chevaleret 75013 PARIS.
Dans le but d’étudier une population de pingouins, on veut déterminer si au moins trois pingouins ont une température supérieure à une certaine valeur. Pour cela chaque pingouin est équipé d’un capteur qui permet de savoir si le pingouin lui-même a atteint cette température. De plus quand deux pingouins se rencontrent leurs capteurs peuvent échanger des informations. En supposant que deux pingouins quelconques finissent toujours par se rencontrer, il est relativement facile de réaliser un protocole (et les capteurs correspondant) qui assure que si au moins trois pingouins ont dépassé le seuil alors tous les capteurs atteindront dans un état particulier d’alerte.
D’un point de vue plus abstrait on considère un réseau de capteur tel que (1) chaque capteur a une mémoire finie, (2) les capteurs sont anonymes, (3) deux capteurs peuvent communiquer deux à deux, (4) on suppose des propriétés sur le schéma de communication (par exemple chaque capteur communique infiniment souvent avec chaque autre capteur).
Dans l’exemple précédent le protocole est correct signifie que tous les capteurs arrivent ultimement dans un état d’alerte si et seulement si au moins trois pingouins ont une température supérieure au seuil. Plus généralement on peut modéliser de façon formelle ce type de systèmes et de déterminer quels genres de propriétés peuvent ainsi être calculées dans ce genre de modèle et comparer avec les classes plus classiques de calculabilité.
Plusieurs extensions sont possibles :
Ce travail commencera par étudier l’article : Computation in Networks of Passively
Mobile Finite-State Sensors
Dana Angluin,
James Aspnes, Zoe Diamadi,
Michael Fischer, Rene Peralta,
PODC 2004