Direction de recherche : Lélia BLIN

Arbres couvrants de la théorie à la pratique. Algorithmes auto-stabilisants et Réseaux de Capteurs

Les réseaux de capteurs sont des réseaux particuliers composés d'objets contraints en ressources. Ils possèdent une faible puissance de calcul, une faible puissance de transmission, une faible bande passante, une mémoire de stockage limitée ainsi qu'une batterie à durée de vie limitée. Afin d'intégrer de tels réseaux dans l'internet des objects, de nouveaux protocoles ont été standardisés. Parmi ces protocoles, le protocole RPL (pour Routing Protocol for Low Power and Lossy Networks). Ce protocole est destiné a construire une topologie logique de routage appelée DODAG. Dans cette thèse, nous abordons l'aspect acheminement de données qui considère une topologie de routage arborescente. L'acheminement des données se fait donc de saut en saut d'un enfant à son parent (ou d'un parent à son enfant). Optimiser la construction du DODAG revient donc à construire un arbre couvrant selon une contrainte donnée. Un arbre couvrant est une structure communicante qui permet de maintenir un unique chemin entre toutes paires de noeuds tout en minimisant le nombre de liens de communication utilisés. De plus, nous considérons les contraintes des réseaux de capteurs telles qu'une batterie déchargée et la variabilité du lien radio comme des fautes transitoires. Ceci nous conduit par conséquent à construire une structure couvrante tolérante aux fautes transitoires. L'auto-stabilisation est une branche de l'algorithmique distribuée qui assure qu'à la suite d'une ou de plusieurs fautes transitoires, le système va retrouver de lui-même un comportement correcte au bout d'un temps fini. L'objectif de cette thèse est de proposer des algorithmes auto-stabilisants dédiés aux réseaux de capteurs. Les contributions de la thèse sont les suivantes :
Dans la première partie de la thèse, nous avons proposé un algorithme auto-stabilisant pour la construction d'un arbre couvrant de diamètre minimum. Cette construction est naturelle lorsque nous souhaitons minimiser le délai de communication entre une racine et les tout les autres noeuds du réseau. Notre algorithme possède plusieurs avantages. Tout d'abord, notre algorithme se limite à une occupation mémoire de O(log n) bits par noeud, ce qui réduit le résultat précédent d'un facteur n tout en conservant un temps de convergence polynomial. De plus, notre algorithme est le premier algorithme pour la construction d'un arbre couvrant auto-stabilisant qui fonctionne sous un démon distribué non équitable. En d'autres termes, nous ne faisons aucune restriction sur le comportement asynchrone du réseau.
Dans la deuxième partie de la thèse, nous nous sommes intéressés à la topologie instable construite par le protocole RPL (DODAG). Notre solution consiste à placer une contrainte additionnelle sur le nombre d'enfants qu'un nœud peut accepter durant la construction du DODAG. Cette contrainte a pour effet de réduire le taux de changement de parent et par conséquent d'améliorer les performances du protocole en termes de taux de délivrance de paquets, de délai de communication et de consommation énergétique. De plus, nous avons implémenté un mécanisme afin de mettre à jour les informations sur les routes descendantes dans RPL. Notre solution a aussi l'avantage de ne pas générer un surplus de messages de contrôle car nous utilisons les messages de contrôle existants fournis par RPL pour l'implémenter. Enfin, cette contribution est double puisque nous avons validé notre solution à la fois en simulations et en expérimentations.

Publications 2015-2018