Conception des réseaux maillés sans fil à multiples-radios multiples-canaux

摘要

Généralement, les problèmes de conception de réseaux consistent à sélectionner les arcs etles sommets d’un graphe G de sorte que la fonction coût est optimisée et l’ensemble decontraintes impliquant les liens et les sommets dans G sont respectées. Une modification dans le critère d’optimisation et/ou dans l’ensemble de contraintes mène à une nouvelle représentation d’un problème différent. Dans cette thèse, nous nous intéressons au problème de conception d’infrastructure de réseaux maillés sans fil (WMN- Wireless Mesh Network en Anglais) où nous montrons que la conception de tels réseaux se transforme d’unproblème d’optimisation standard (la fonction coût est optimisée) à un problèmed’optimisation à plusieurs objectifs, pour tenir en compte de nombreux aspects, souventcontradictoires, mais néanmoins incontournables dans la réalité. Cette thèse, composée detrois volets, propose de nouveaux modèles et algorithmes pour la conception de WMNs oùrien n’est connu à l’ avance.Le premiervolet est consacré à l’optimisation simultanée de deux objectifséquitablement importants : le coût et la performance du réseau en termes de débit. Troismodèles bi-objectifs qui se différent principalement par l’approche utilisée pour maximiserla performance du réseau sont proposés, résolus et comparés.Le deuxième volet traite le problème de placement de passerelles vu son impact sur laperformance et l’extensibilité du réseau. La notion de contraintes de sauts (hop constraints)est introduite dans la conception du réseau pour limiter le délai de transmission. Un nouvelalgorithme basé sur une approche de groupage est proposé afin de trouver les positionsstratégiques des passerelles qui favorisent l’extensibilité du réseau et augmentent saperformance sans augmenter considérablement le coût total de son installation.Le dernier volet adresse le problème de fiabilité du réseau dans la présence de pannessimples. Prévoir l’installation des composants redondants lors de la phase de conceptionpeut garantir des communications fiables, mais au détriment du coût et de la performancedu réseau. Un nouvel algorithme, basé sur l’approche théorique de décomposition enoreilles afin d’installer le minimum nombre de routeurs additionnels pour tolérer les pannessimples, est développé.Afin de résoudre les modèles proposés pour des réseaux de taille réelle, un algorithmeévolutionnaire (méta-heuristique), inspiré de la nature, est développé. Finalement, lesméthodes et modèles proposés on été évalués par des simulations empiriques etd’événements discrets.