Modélisation et optimisation de la planification des réseaux locaux sans fil

There are two relevant stages in Wireless Local Area Network (WLAN) planning. First, a location for each transmitter must be selected and the parameters for all sites must be set. The second important stage is to allocate a frequency to the transmitters in order to provide users with a wireless access in their local network. The objective is to respect financial requirements and to guarantee a given Quality of Service (QoS). The modeling is based on the calculation of the real throughput offered to each service point by the network. It is demonstrated that this real throughput criterion allows a complete modeling of QoS. It unifies the usual criteria of coverage, interferences management and capacity.The optimization addresses the access point location and the frequency assignment problems together. A new algorithm called Random Variable Neighbourhood is defined: at each iteration of this local search, the neighbourhood structure is randomly selected. This algorithm is highly modular and easily combines the location and assignment problems.Collaborations and industrial partnerships were established: WLAN global planning software with Orange Labs and sequential planning solutions with the start-up Trinaps. Finally the modeling problem is further examined by clarifying the links between the real throughput calculations and the SINR. Initially, it is shown that the SINR threshold constraints induce a graph T-coloring problem (necessary condition). To obtain an equivalence accounting for the multiple interferences, a generalization of T-coloring problems for the hypergraphs is introduced. Secondly, an algorithm deducing the SINR thresholds from the real throughput constraints is defined. This new modeling is the base of future developments.Le problème de planification de réseaux WLAN consiste d'une part à positionner et à paramétrer des antennes dans un bâtiment et d'autre part à leur affecter une fréquence afin d'offrir aux clients un accès sans fil au réseau local. Le réseau ainsi construit doit répondre à des critères de couverture et de qualité de service, tout en minimisant le coût financier.Notre modélisation est basée sur le calcul du débit réel offert en chaque point de demande de service du réseau. Nous montrons que ce critère de débit réel permet une modélisation complète de la qualité de service car il unifie les critères habituels de couverture, de gestion des interférences et de capacité.Notre optimisation traite simultanément le problème de placement des points d'accès et le problème d'affectation de fréquences par un algorithme à Voisinages Variables Aléatoires VVA : à chaque itération de cette recherche locale le type de voisinage est tiré au hasard. Cet algorithme est très modulaire et permet facilement de combiner les deux sous problèmes (placement et affection).Ces travaux ont donné lieu à des collaborations et partenariats industriels : logiciel de planification globale des WLAN avec Orange Labs et solutions de planification séquentielle avec la start-up Trinaps.Enfin nous approfondissons la modélisation du problème en explicitant les liens entre le calcul du débit réel et les SINR. Dans une première étape, nous montrons que les contraintes de seuil sur les SINR induisent un problème de T-coloration de graphe (condition nécessaire). Pour obtenir une équivalence rendant compte des interférences multiples, une généralisation du problème de T-coloration pour les hypergraphes est introduite. Dans une seconde étape, nous définissons un algorithme déduisant les seuils de SINR à partir des contraintes sur les débits réels. Cette nouvelle modélisation est la base de nos développements futurs