Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc - Calculs locaux et réétiquetages des graphes dynamiques

Abstract

Les réseaux mobiles ad hoc sont par nature instables et imprévisibles. De ces caractéristiques découle la difficulté à concevoir et analyser des algorithmes distribués garantissant certaines propriétés. C’est sur ce point que porte la contribution majeure de cette thèse. Pour amorcer cette étude, nous avons étudié quelques problèmes fondamentaux de l’algorithmique distribuée dans ce type d’environnement. Du fait de la nature de ces réseaux, nous avons considéré des modèles de calculs locaux, où chaque étape ne fait collaborer que des nœuds directement voisins. Nous avons notamment proposé un nouveau cadre d’analyse, combinant réétiquetages de graphes dynamiques et graphes évolutifs (modèle combinatoire pour les réseaux dynamiques). Notre approche permet de caractériser les conditions de succès ou d’échec d’un algorithme en fonction de la dynamique du réseau, autrement dit, en fonction de conditions nécessaires et/ou suffisantes sur les graphes évolutifs correspondants. Nous avons également étudié la synchronisation sous-jacente aux calculs, ainsi que la manière dont une application réelle peut reposer sur un algorithme de réétiquetage. Un certain nombre de logiciels ont également été réalisés autour de ces travaux, notamment un simulateur de réétiquetage de graphes dynamiques et un vérificateur de propriétés sur les graphes évolutifs.