Thème : Optimisation évolutionniste multi-objectifs pour des réseaux ad hoc mobiles : la diffusion robuste et le routage multi-chemins non recouvrant.


Directeur de thèse : Francois Spies
Co-encadrants : Christelle Bloch et Damien Charlet


Les réseaux ad hoc mobiles (MANETs) se caractérisent par des topologies très variées, en fonction de la densité du réseau (nombre de noeuds) et du niveau de mobilité (vitesse des noeuds). Ils s'appuient de plus sur des ressources généralement très limitées comme la bande passante ou l'énergie des terminaux. Les travaux présentés dans ma thèse traitent de l'optimisation de la gestion des communications dans les MANETs. Ils proposent des contributions à la fois dans le domaine de l'optimisation multi-critères et celui des réseaux mobiles.


Optimisation multi-objectifs

Ma thèse présente des aspects novateurs de l'algorithmique évolutionniste. Elle propose un algorithme basé sur le calcul de multiples fronts de Pareto et en présente l'impact aussi bien sur des critères de convergence que de diversité. Ensuite, une deuxième version (adaptative) de cet algorithme est introduite. Elle présente un opérateur d'adaptation dynamique qui privilégie alternativement des phases d'exploration ou d'exploitation de zones contenant de bonnes solutions découvertes, en fonction de la valeur d'indicateurs de convergence et de diversité calculés au fil des générations. Ces deux versions sont comparées entre elles et avec des algorithmes de la littérature. Cet algorithme est ensuite appliqué aux problèmes réseaux. Une plateforme qui combine un algorithme évolutionniste multi-objectifs et un simulateur de réseau (ns-2) a été proposé pour optimiser des stratégies de diffusion et/ou de routage en tenant compte du niveau de densité et/ou de mobilité du réseau.


Réseaux ad hoc : la diffusion robuste

La solution de diffusion que j'ai proposée permet de fixer hors ligne les meilleurs comportements adaptés à divers types de réseau (de très peu dense à très dense). Pour chacun d'entre eux, le comportement optimisé s'apparente à une méthode probabiliste ``améliorée''. Il est décrit par quatre paramètres : la probabilité de relai, le nombre de répétitions, le délai entre deux répétitions successives et le TTL. Puis les 5 jeux de paramètres sont implantés sur chaque noeud du réseau afin que celui-ci choisisse au fil du temps, le jeu de paramètres le plus adapté à la densité du réseau qu'il détecte autour de lui. Cette stratégie est comparée par simulation à des stratégies probabilistes plus classiques, dans un réseau présentant des zones de densité variée. Les résultats montrent que ce protocole garantit, contrairement aux autres stratégies, que tous les noeuds du réseau recevront le message diffusé (même dans un réseau très peu dense), au prix d'une légère augmentation du temps de propagation. Par ailleurs, il présente un nombre de collisions plus faible.


Réseaux ad hoc : le problème du routage multi-chemins

J'ai proposé un protocole de routage multi-chemins (NICE-MRP) adapté aux fortes variations de topologies dues à la mobilité des noeuds et à la présence potentielle d'interférences radio entre noeuds proches. Chaque noeud calcule des combinaisons de chemins ne présentant pas de radio-interférences ; puis il sélectionne la combinaison la plus performante comme route principale et l'utilise pour la communication (table active). Les autres combinaisons sont conservées dans une table passive, ce qui permet, en cas de rupture d'un chemin, de continuer la communication en mode dégradé, tout en cherchant dans la table passive une combinaison plus performante sur laquelle la communication sera reportée pour retrouver un mode de fonctionnement normal. Les performances de NICE-MRP en fonction du degré de mobilité sont évaluées avec ns-2, en comparaison avec d'autres protocoles multi-chemins (liens disjoints et à noeuds disjoints). NICE-MRP présente globalement une latence plus faible, avec des taux de pertes et une surcharge du canal sensiblement équivalents, voire plus faibles que pour les autres protocoles et qui restent relativement constants, quel que soit le niveau de mobilité.