Optimisation centralisée de l'association dans les réseaux IEEE 802.11

In this thesis we study the problem of association in Wi-Fi networks. We propose solutions that allow a controller to optimize and manage in a centralized way the operations of association and reassociation. Association is expressed as combinatorial optimization problems. The proposed models consider interference between APs and are compliant with the DCF access method of the IEEE 802.11 standard. In the first model proposed we considered the case of a saturated network in which it is assumed that each AP permanently has frames to transmit. In this model, we have assumed that all the stations of the same AP have equivalent chances of transmission, ie the same number of accesses to the medium. The proposed objective function offers a good compromise between improving station throughput and equity. The numerical results obtained on realistic simulations have shown the effectiveness of this solution and show a significant improvement in WLAN performance compared to an association based on the value of the RSSI or compared to existing approaches. Subsequently, since the hypothesis of a saturated network all the time is not very realistic, we have proposed a solution that relies on real measurements such as station throughput requests and the error rates. Our solution seeks to balance the load between APs. Specifically, we seek to reduce the load of the most heavily loaded AP in the WLAN. To evaluate this load, we have proposed a mathematical model that allows to estimate the BTF "Busy Time Fraction" of an AP in any configuration (association scheme). This model is based on a Markov network. The model combined with the optimization problem allows to propose the best association. The evaluation of this solution by simulation has shown how accurate our BTF estimation, and has also shown its ability to balance the load between APs and satisfy the station throughput demands. To generalize this solution to the new versions of the IEEE 802.11 standard such as 802.11n/ac, we adapted the BTF estimation model to take into account the new improvements made by Wi-Fi on physical and MAC layers such as channel aggregation, frame aggregation and block acknowledgment. Thus, we have proposed a new metric that allows to express both the BTF of an AP and the frame aggregation rates of each of its stations. The numerical evaluation of this solution showed the advantage of the new metric compared to the BTF to improve the station throughputs and load balancing in the WLAN. It should be noted that, for the resolution of the combinatorial optimization problems formulated in this thesis, we used iterative local search heuristics. These heuristics are based on the same neighborhood structure, but the search procedures are different depending on the objective function of each model. This choice is justified by the effectiveness of local research in providing acceptable solutions in a reasonable time for complex combinatorial optimization problemsDans cette thèse nous étudions la problématique de l'association dans les réseaux Wi-Fi. Nous proposons des solutions qui permettent à un contrôleur d'optimiser et de gérer d'une manière centralisée les opérations d'association et de réassociation. L'association est exprimée sous forme de problèmes d'optimisations combinatoires. Les modèles proposés tiennent compte des interférences entre les APs et sont conformes avec la méthode d'accès DCF du standard IEEE 802.11. Dans le premier modèle proposé nous avons considéré le cas d'un réseau saturé dans lequel on suppose que chaque AP dispose en permanence de trames à transmettre. Dans ce modèle, nous avons supposé que toutes les stations d'un même AP ont des chances de transmission équivalentes autrement dit le même nombre d'accès au medium. La fonction objectif proposée offre un bon compromis entre l'amélioration du débit des stations et l'équité. Les résultats numériques obtenus sur des simulations réalistes ont montré l'efficacité de cette solution et présentent une amélioration significative des performances du WLAN par rapport à une association basée sur la valeur du RSSI ou par rapport aux approches existantes. Par la suite, étant donné que l'hypothèse d'un réseau tout le temps saturé n'est pas très réaliste, nous avons proposé une solution qui s'appuie sur des mesures réelles telles que les demandes de débit des stations et les taux d'erreur. Notre solution cherche à équilibrer la charge entre les APs. Plus précisément, nous cherchons à diminuer la charge de l'AP le plus chargé dans le WLAN. Pour évaluer cette charge, nous avons proposé un modèle mathématique qui permet d'estimer le BTF « Busy Time Fraction » d'un AP dans n'importe quelle configuration (schéma d'association). Ce modèle est basé sur un réseau de Markov. Le modèle associé au problème d'optimisation permet de proposer la meilleure association. L'évaluation de cette solution par simulation a montré à quel point notre estimation du BTF est précise, et a aussi montré sa capacité à équilibrer la charge entre les APs et à satisfaire la demande en débit des stations. Pour généraliser cette solution aux nouvelles versions du standard IEEE 802.11 comme 802.11n/ac, nous avons adapté le modèle d'estimation du BTF pour qu'il tienne compte des nouvelles améliorations apportées par les couches physiques et MAC du Wi-Fi telles que l'agrégation des canaux, l'agrégation des trames et le bloc d'acquittement. Ainsi, nous avons proposé une nouvelle métrique qui permet d'exprimer à la fois le BTF d'un AP et les taux d'agrégation de trames de chacune de ces stations. L'évaluation numérique de cette solution a montré l'avantage de la nouvelle métrique par rapport au BTF pour améliorer le débit des stations et l'équilibrage de charge dans le WLAN. Il est à noter que, pour la résolution des problèmes d'optimisation combinatoire formulés dans cette thèse, nous avons utilisé des heuristiques de recherche locale itérative. Ces heuristiques sont basées sur une même structure de voisinage, mais les procédures de recherches sont différentes selon la fonction objectif de chaque modèle. Ce choix est justifié par l'efficacité de la recherche locale à fournir des solutions acceptables dans un temps raisonnable pour des problèmes d'optimisation combinatoire complexe