Tactical Wireless Network Design for Challenging Environments

Dans ce mémoire, nous modélisons le problème de conception de réseau sans fil tactique avec un signal modélisé physiquement et en considérant trois scénarios élémentaires de trafic de données. Nous modélisons ce problèmes pour différents types de topologies possibles, des arbres jusqu'au maillage et tout ce qui se trouve entre les deux. Nous considérons aussi deux types d'antennes : celles à simple faisceau et celles à multiples faisceaux. Nous utilisons des notions de théorie des graphes afin de donner des conditions de validité pour chaque grande partie des réseaux : leur topologie, leur configuration et la configuration de leurs antennes. Nous modélisons finalement un critère d'optimisation basé sur le lien le plus faible du réseau en terme de débit effectif, i.e. de vitesse de transmission de données en tenant compte de la congestion du réseau. À ce que nous sachions, nous sommes les premiers à modéliser complètement ce problème combinatoire non-linéaire complexe. Nous proposons un algorithme à plusieurs niveaux pour résoudre ce nouveau problème. Au plus haut niveau, nous utilisons une méta-heuristique de type recherche local pour résoudre le sous-problème de conception de la topologie. Au niveau moyen, nous utilisons une combinaison d'énumération exhaustive, de méta-heuristiques, d'heuristiques et d'approximations pour résoudre le sous-problème de configuration du réseau. Au plus bas niveau, nous utilisons une heuristique intuitive basée sur la géométrie pour résoudre le sous-problème de la configuration des antennes. Finalement, nous caractérisons notre approche à travers plusieurs tests. Nous comparons plusieurs façons d'évaluer les maillages. Nous étudions l'e˙et des paramètres de notre algorithme sur sa performance. Nous comparons quantitativement et qualitativement les meilleurs réseaux trouvés par notre algorithme pour des antennes à simple faisceau avec ceux pour des antennes à multiple faisceaux. Nous comparons également les valeurs d'objectif des meilleurs topologies arbres avec les maillages complets sur les mêmes instances. Nous identifions aussi la plus grande limite de notre approche, qui est sa durée d'exécution, spécifiquement le temps nécessaire pour évaluer la fonction objectif. Nous concluons en identifiant d'autres limites de notre approche ainsi qu'en esquissant des avenues prometteuses pour poursuivre la recherche suite à ce travail.