Optimisation de la capacité des réseaux radio maillés

In this thesis, we focus on optimizing the capacity of wireless mesh networks. These broadband access networks are a promising solution in urban areas and for military operations. We define the capacity of a wireless mesh network as the fair throughput offered to each flow. In order to get theoretical bounds on the network performances, we develop optimization models integrating the cross-layer characteristics of radio communications. More precisely, we study the joint routing and scheduling problem. We develop, for the linear relaxation of the problem, a resolution method based on the column generation process. We derive a linear formulation which focus on the transport capacity available on the network cuts. We prove the equivalence of the models, and adapt the resolution method into a cross line and column generation process. Thorough tests, we point out a contention area located around the mesh gateways which constraints the network capacity. These results are applied to a quantitative study of the effects of acknowledgments on the capacity. We then present a stability study of a protocol which routes a traffic injected arbitrarily. We improve existing results by showing the stability even if the total traffic injected is a maximum flow. All this research work has been implemented in the open-source library MASCOPT (Mascotte Optimisation) dedicated to network optimization problems.Dans cette thèse, nous nous intéressons aux problématiques d'optimisation de la capacité des réseaux radio maillés. Cette architecture de réseau d'accès est particulièrement pertinente en milieu urbain ou en situation opérationnelle militaire. Nous définissons la capacité d'un réseau comme la quantité de flot que peut répartir équitablement une topologie aux utilisateurs qu'elle sert. Afin d'obtenir des bornes théoriques sur les performances du réseau, nous développons des modèles d'optimisation intégrant les caractéristiques inter-couche des communications radio. Nous étudions plus précisément le problème joint du routage et de l'ordonnancement. Nous développons, pour la relaxation linéaire de ce problème, une méthode de résolution efficace utilisant la génération de colonnes. Nous dérivons ensuite une formulation qui élimine le routage pour se concentrer sur la capacité de transport disponible sur les coupes du réseau. L'équivalence des solutions optimales est démontrée, et le processus de résolution est adapté en une génération croisée de lignes et de colonnes. Ces études mettent en évidence la présence d'une zone de contention autour de chaque point d'accès qui contraint la capacité du réseau. Ces résultats permettent une étude quantitative des effets du trafic d'acquittement sur la capacité. Nous présentons enfin une étude de la stabilité d'un protocole routant du trafic injecté de manière arbitraire au cours du temps. Nous améliorons les résultats existants en démontrant la stabilité quand le trafic injecté est un flot maximum. L'ensemble de ces travaux a été implémenté dans la bibliothèque open source MASCOPT (Mascotte Optimisation) dédiée aux problèmes d'optimisation des réseaux