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.

Abstract

In this work, we model the tactical wireless network design with a physically-modeled signal in three elementary data traÿc scenarios. We model this problem for different restrictions on the type of topologies that are allowed, from trees to full mesh clusters and any combination thereof. We also consider two types of antennas: single-beam and multi-beam. We use the language of graph theory to state validity conditions for each main component of a network: its topology, its configuration and its antenna configurations. We finally model an optimization criterion based on the weakest link in the network in terms of effective throughput, i.e. data transmission speeds given the congestion of the network. To our knowledge, we are the firsts to model this complex non-linear combinatorial optimization problem in its entirety. We propose a multi-level algorithm to solve this novel problem. At the highest level, we use a meta-heuristic local search for the topology design sub-problem. At the mid level, we use a mix of exhaustive enumeration, meta-heuristics, heuristics and approximations to solve the network configuration sub-problem. At the lowest level, we use intuitive geometrically-based heuristics to solve the antenna configurations sub-problem. We finally evaluate our approach through multiple tests. We compare various ways of eval-uating mesh clusters. We study the effects of the algorithm's parameters on its performance. We compare quantitatively and qualitatively the best networks found by our algorithm for single-beam versus multi-beam antennas. We also compare the objective values of the best tree topologies that our algorithm finds with full mesh clusters on the same instances. We also identify the main limitation of our current approach which is its timing, and especially the time it takes to evaluate the objective function. We conclude by identifying other limitations of our approach and describing promising avenues for further research in the continuation of this work.