Construction et maintenance d'une dorsale virtuelle dans les réseaux AD HOC mobiles

摘要

Un réseau ad hoc mobile est un réseau complètement distribué ne nécessitant pas d'infrastructure fixe. Les terminaux sont libres de se déplacer n'importe quand et dans n'importe quelle direction. L'absence d'une infrastructure nécessite la collaboration de tous les terminaux pour acheminer le trafic d'une source vers une destination. De nombreux protocoles de routage ont été proposés pour assurer le relayage multi saut, utilisant différentes approches (réactives, proactives et hybrides). Toutefois, les performances de ces protocoles se dégradent en présence de la mobilité. Dans cette thèse, nous proposons d'améliorer la performance des protocoles de routage dans les réseaux ad hoc en construisant une dorsale virtuelle.ududUne dorsale virtuelle est un sous-ensemble de noeuds sélectionnés de façon à ce que chaque noeud dans le réseau possède au moins un voisin dans la dorsale. L'ensemble des noeuds qui forment la dorsale doit être toujours maintenu connecté même quand les noeuds changent de position. Plus la taille de la dorsale est minimale, plus la maintenance est efficace. Pour construire la dorsale, nous avons proposé un nouvel algorithme basé sur l'approximation de l'ensemble de domination connexe de taille minimale (MCDS). Un réseau ad hoc est généralement modélisé par un graphe à disque unitaire UDG (Unit Disc Graph). Trouver l'ensemble MCDS dans un graphe UDG est un problème NP-Complet. Dans le but de réduire cette complexité, nous avons décomposé le problème en deux étapes: la première étape consiste à déterminer l'ensemble de domination connexe (MDS) au moyen d'une formulation en programmation linéaire et la deuxième étape consiste à trouver l'arbre de recouvrement de l'ensemble MDS et en déduire l'ensemble MCDS. Les résultats de simulations montrent bien que la solution donnée par notre algorithme est très proche de celle fournie par l'analyse théorique. De plus, la taille de la dorsale est nettement inférieure comparée à d'autres algorithmes proposés dans la littérature quand la taille du réseau augmente.ududNous avons également proposé une procédure de maintenance distribuée. Cette procédure est basée sur un échange simple des messages de contrôle hello modifiés, ces messages étant utilisés pour la découverte au voisinage. Un noeud qui change de position va alors appliquer cette procédure pour se connecter à la dorsale. Une maintenance locale de la dorsale sera effectuée dans la zone où le noeud va se retrouver dans sa nouvelle position. Les résultats de simulation ont démontré l'efficacité et la fiabilité de cette approche. En effet, plus de 90% des noeuds restent connectés pour une mobilité élevée (vitesse moyenne égale à 30 m/s). De plus, cette procédure est peu sensible au facteur de mise à l'échelle (Scalability). La nature distribuée de la procédure de maintenance s'adapte bien à la dynamique de la structure du réseau engendrée par le mouvement des noeuds.ududDans le but de vérifier l'amélioration apportée par la présence d'une dorsale pour les protocoles de routage dans les réseaux ad hoc mobiles, nous avons comparé les performances de certains protocoles de routage, en fonction de la mobilité, en présence de la dorsale avec leurs performances dans leurs versions standards. Les résultats de simulations ont démontré qu'une amélioration de leurs performances peut atteindre 20% pour certains protocoles même pour une mobilité élevée.ududEn conclusion, ce travail de recherche présente de nouvelles solutions pour différents problèmes reliés au routage dans les réseaux ad hoc mobiles.