Centralized Optimization of the Association in IEEE 802.11 Networks
Optimisation centralisée de l'association dans les réseaux IEEE 802.11
Résumé
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 asso-
ciation 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 the requests for flow
of the stations and the rates of ’error. 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 makes it possible 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 associated with the optimization
problem makes it possible to propose the best association. The evaluation of this solution by
simulation has shown how accurate our BTF estimate is, and has also shown its ability to
balance the load between APs and satisfy the demand for station throughput.
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 improvementsmade by Wi-Fi’s physical and MAC layers such as channel aggregation, frame aggregation
and acknowledgment block. 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 these stations. The numerical
evaluation of this solution showed the advantage of the new metric compared to the BTF to
improve the flow of the stations 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 problems.
L’emploi intensif des WLANs (Wireless Local Area Networks) ces dernières années, par
les opérateurs et les entreprises, est motivé par les bonnes performances et la simplicité
d’installation de ces réseaux. Les WLANS qui déploient des points d’accès (AP) Wi-Fi (basé
sur le standard IEEE 802.11) sont les plus populaires et les plus répandus pour se connecter à
Internet. Néanmoins, l’installation d’un grand nombre d’APs sans un déploiement rationnel
et une gestion optimale et dynamique de leur configuration comme l’affectation des canaux,
la puissance du signal et l’association des stations, peut conduire à une utilisation non opti-
male de la bande passante et du support radio. L’association à un AP constitue la première
étape qui permet à une station de se connecter à un WLAN. Généralement, dans les réseaux
Wi-Fi actuels, la station choisit l’AP en se basant seulement sur la valeur la plus élevée de
l’indicateur d’intensité du signal reçu (RSSI) provenant des différents APs détectés. Cette
approche distribuée, qui ne tient compte ni du nombre de stations mobiles déjà associées avec
les APs, ni du nombre d’APs qui partagent le même canal radio, conduit très souvent à un
partage de charge très hétérogène entre les APs. Cela affecte négativement les performances
des utilisateurs et même le débit global du réseau.
Dans 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 tien-
nent 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 sta-tions 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 ap-
proches 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 heuris-
tiques 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 complexes.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...