Mohammed Amer
email: mohammed.amer@ens-lyon.fr

Anthony Busson
email: anthony.busson@ens-lyon.fr

Isabelle Guerin Lassous
email: isabelle.guerin-lassous@ens-lyon.fr

Association Optimization in Wi-Fi Networks: Use of an Access-based Fairness

Keywords: IEEE 802.11, wireless, association optimization

Densification of Wi-Fi networks has led to the possibility for a station to choose between several access points (APs). On the other hand, the densification of APs generates interference, contention and decreases the global throughput as APs have to share a limited number of channels. Optimizing the association step between APs and stations can alleviate this problem and increase the overall throughput and fairness between stations. In this paper, we propose an original solution to this optimization problem based on two contributions. First, we present a mathematical model for the association optimization problem based on a realistic share of the medium between APs and stations and among APs when using the 802.11 DCF (Distributed Coordination Function) mode. Then, we introduce a local search algorithm to solve this problem through a suitable neighborhood structure. This approach has the benefit to be tuned according to the CPU and time constraints of the WLAN controller. Our evaluation, based on simulations, shows that the proposed solution improves the overall throughput and the fairness of the network.

Introduction

Wireless LANs (WLANs) have become the first technology of access networks in terms of traffic [START_REF]Cisco visual networking index: Forecast and methodology[END_REF].

WLANs are now extensively deployed by operators, companies, public institutions and Internet subscribers. Their success is explained by a performance increase that satisfies the users' need for bandwidth, its simplicity to access the network everywhere, and the possibility for users to be mobile. Among the existing wireless technologies, IEEE 802.11 [START_REF]IEEE standard for information technologytelecommunications and information exchange between systems local and metropolitan area networks-specific requirements part 11: Wireless LAN[END_REF] is the de facto WLAN technology. It is used mainly in infrastructure mode where stations have to associate with access points (APs) to access the network. Most of APs use the two unlicensed bands ISM (2.4GHz) and U-NII (5.15-5.82 GHz) for which 14 1 and 8 channels are available.

Most of the Internet subscribers have a set-top box that integrates a Wi-Fi AP. On the other hand, companies / institutions deploy a large number of Wi-Fi APs to ensure an efficient coverage of the area or to allow transparent mobility. These approaches have led to a densification of WLANs, which generates congestion in terms of channel usage when several APs in detection range of each other use the same channel [START_REF] Shin | Per-node throughput enhancement in Wi-Fi densenets[END_REF]. The number of channels being fixed, optimizations at different levels are required to efficiently manage the limited resources and ensure a sufficient throughput to Wi-Fi stations.

Among the different management operations in the IEEE 802.11 standard, the association between wireless stations and APs is a key step that has an impact on the user performance as well as on the over-all wireless network performance. In a IEEE 802.11based infrastructure network, a wireless station must be associated with one AP to be allowed to use the network. When several APs are available within its reception range, one AP must be selected. In many IEEE 802.11 products, a wireless station uses the received signal strength indicator (RSSI), from the different APs it detects, to choose the AP to associate with. This approach does not consider the number of already attached wireless stations per AP, and may consequently lead to poor performance and unfairness between stations. It does not consider either the impact of the stations' transmission rates on the user and global throughputs. Indeed, stations using a low physical transmission rate occupy the channel longer than the stations with a high physical rate [START_REF] Heusse | Performance anomaly of 802.11b[END_REF]. High rate stations may then be significantly penalized as low and high rate stations attached to the same AP tend to have the same throughput.

Nowadays, most of the WLANs commercial solutions consist of thin APs combined with one or several WLAN controllers. In this architecture, decisions (association, security, etc.) are taken by the controller. Such an approach offers more functionalities than with autonomous APs as the controller has a centralized view of the stations parameters and their performance. These solutions are closed and not flexible, and make difficult the coexistence of heterogeneous network equipments. Besides these proprietary solutions, recent standards aim to provide a technological framework to allow such centralized systems. CAPWAP protocol (Control and Provisioning of Wireless Access Points) [START_REF] Calhoun | Control and provisioning of wireless access points (CAPWAP) protocol specification[END_REF], standardized by IETF, allows an AC (Access Controller) to manage a collection of wireless APs. IEEE has standardized the IEEE 802.11v amendment [START_REF]Wireless LAN medium access control (MAC) and physical layer (PHY) specifications amendment 8: IEEE 802.11 wireless network management[END_REF] which enables the management of stations in a centralized fashion (e.g. monitoring, configuring, and updating) through a layer 2 mechanism. Also, the SDN (Software Defined Networking) paradigm [START_REF] Yang | Software-defined and virtualized future mobile and wireless networks: A survey[END_REF] may offer such an approach, even if its application to WLANs is not yet defined. These different centralized approaches offer the opportunity to implement an optimized parameterization of WLANs, which is more difficult to realize in a distributed context.

In this paper, we are interested in the association step in 802.11-based wireless networks using a controller. In these architectures, the association can be solved with a centralized approach, which allows the use of an optimization model like in [START_REF] Karimi | Optimal collaborative access point association in wireless networks[END_REF][START_REF] Li | Proportional fairness in multi-rate wireless LANs[END_REF][START_REF] Li | AP association for proportional fairness in multi-rate WLANs[END_REF][START_REF] Bejerano | Fairness and load balancing in wireless LANs using association control[END_REF][START_REF] Collotta | FLBA: A fuzzy algorithm for load balancing in IEEE 802.11 networks[END_REF][START_REF] Tang | Throughput optimization via association control in wireless LANs[END_REF]. Most of the optimization models, proposed for this problem, assume a time based fairness between the AP and the stations [START_REF] Karimi | Optimal collaborative access point association in wireless networks[END_REF][START_REF] Li | Proportional fairness in multi-rate wireless LANs[END_REF][START_REF] Li | AP association for proportional fairness in multi-rate WLANs[END_REF][START_REF] Tang | Throughput optimization via association control in wireless LANs[END_REF]. This assumption requires to apply an appropriate scheduling on AP that must take into account different parameters like the packet sizes and the physical transmission rates. In practice, APs use very simple scheduling policies like a FIFO scheduling and the DCF (Distributed Coordination Function) mode of IEEE 802.11 provides an access based share of the medium between APs/stations in contention. Therefore an access based fairness model for the medium share seems more appropriate. Very few solutions based on explicit optimization models use such an access based fairness scheme. This is the case in [START_REF] Bejerano | Fairness and load balancing in wireless LANs using association control[END_REF], but the solution goal is to minimize the maximal load on all the APs. In our work, we opt for the logarithmic utility function because of the good tradeoff that can be achieved between the overall network throughput and the fairness of user throughputs. Finally, contrary to most of the proportional fairness solutions based on optimization models (and all considering a time based fairness share), we evaluate our solution not only with an optimization solver but also with a network simulator. The contributions of this paper are the following:

• We propose an optimization model for the association step that is based on the logarithmic utility function. In this model, we consider that an AP allocates, in average, the same number of access to the medium to each station associated with it, compared to the literature where the AP allocate the same amount of time to each station. Our approach is thus more realistic as it corresponds to the current implementation of APs and to the 802.11 DCF mode.

• A local search heuristic is proposed to solve this problem (being NP-hard). This heuristic has the benefit to be tuned according to time and CPU constraints of the WLAN controller.

• Our solution has been implemented on the net-work simulator ns-3. Results show that the global throughput is significantly increased compare to the default RSSI association, and leads to an improvement of fairness. A deeper analysis points out that, thanks to our optimization, stations are more homogeneously shared among access points, and individual throughput per station is improved for almost of the stations.

This paper is organized as follows. In Section 2 we present works related to the optimization of Wi-Fi association problem. Then, in Section 3, we present our mathematical model of the optimization problem when orthogonal and non-ortho-gonal channels are used. In Section 3.2, the proposed approach to solve this model is described. A performance evaluation of our solution based on ns-3 simulations is carried out in Section 4. We conclude in Section 5.

Related Work

Several papers claim that the use of the RSSI metrics is not an efficient approach for the association step and have proposed different approaches.

The association decision can be done in a central way or in a distributed way. As our work takes benefit of the presence of a controller to apply a centralized association algorithm, we only survey the centralized solutions like in [START_REF] Karimi | Optimal collaborative access point association in wireless networks[END_REF][START_REF] Li | Proportional fairness in multi-rate wireless LANs[END_REF][START_REF] Li | AP association for proportional fairness in multi-rate WLANs[END_REF][START_REF] Bejerano | Fairness and load balancing in wireless LANs using association control[END_REF][START_REF] Collotta | FLBA: A fuzzy algorithm for load balancing in IEEE 802.11 networks[END_REF][START_REF] Tang | Throughput optimization via association control in wireless LANs[END_REF]. When the solution is based on an optimization model, the solution seeks to optimize an objective function. In [START_REF] Karimi | Optimal collaborative access point association in wireless networks[END_REF][START_REF] Li | Proportional fairness in multi-rate wireless LANs[END_REF][START_REF] Li | AP association for proportional fairness in multi-rate WLANs[END_REF][START_REF] Tang | Throughput optimization via association control in wireless LANs[END_REF], the authors look for a proportional fair association by optimizing the logarithmic utility function which corresponds to maximizing the sum of logs of the users' throughputs. In [START_REF] Bejerano | Fairness and load balancing in wireless LANs using association control[END_REF], the goal is to maximize the minimal throughput among all the stations. In [START_REF] Collotta | FLBA: A fuzzy algorithm for load balancing in IEEE 802.11 networks[END_REF], although the proposed solution is centralized on a controller, it uses fuzzy logic and its decisions are based on metrics like, for instance, the signal quality and the packet loss rate.

Most of these works consider a specific bandwidth sharing among the users. For instance, in [START_REF] Karimi | Optimal collaborative access point association in wireless networks[END_REF][START_REF] Li | Proportional fairness in multi-rate wireless LANs[END_REF][START_REF] Li | AP association for proportional fairness in multi-rate WLANs[END_REF][START_REF] Tang | Throughput optimization via association control in wireless LANs[END_REF], the authors search to improve the network performance while ensuring fairness in terms of service time between stations on the same AP. It ensures that each station obtains a throughput proportional to its physical transmission rate. As explained in Introduction, this approach requires to change the AP scheduling. Other solutions, closer to the reality, consider that the share is fair in the number of channel accesses [START_REF] Bejerano | Fairness and load balancing in wireless LANs using association control[END_REF][START_REF] Collotta | FLBA: A fuzzy algorithm for load balancing in IEEE 802.11 networks[END_REF]. As these two solutions, our model captures the access-based fairness of the IEEE 802.11 DCF mode, but, contrary to these two solutions we look for a proportional fair association.

In many solutions based on an optimization model, this latter is numerically evaluated by using a tool that solves optimization problems, like, for instance, CVX in [START_REF] Karimi | Optimal collaborative access point association in wireless networks[END_REF] and CPLEX in [START_REF] Li | Proportional fairness in multi-rate wireless LANs[END_REF]. In [START_REF] Tang | Throughput optimization via association control in wireless LANs[END_REF], approximate algorithms are designed and they are implemented in Python. In these papers, only the model/algorithm is evaluated and the performance evaluation part gives few clues on the solution performance in a more realistic networking setting, like, for instance, when the medium share is governed by the IEEE 802.11 DCF principles. On the other hand, network simulation results are provided in [START_REF] Li | AP association for proportional fairness in multi-rate WLANs[END_REF] with the OMNetpp simulator while the solution of [START_REF] Collotta | FLBA: A fuzzy algorithm for load balancing in IEEE 802.11 networks[END_REF] is experimentally evaluated with a homemade testbed. Contrary to most of the association solutions targeting a proportional fairness and based on an optimization model (and all considering a time based fairness medium share), we evaluate our solution with a network simulator.

Association Optimization

Problem Formulation

In this section, we provide the model and the notations used for the mathematical formulation of our solution. We consider a wireless network with m access points and n wireless stations as illustrated in Figure 1. We consider only downlink traffic, from the APs to the stations. The amount of uplink traffic is considered negligible, or at least not significant, with regard to the downlink traffic [START_REF] Gupta | WiFox: Scaling Wi-Fi performance for large audience environments[END_REF]. We also assume that the amount of data intended to the stations associated to the same AP are equal in average, or in a long term period. To this end, we assume that the mean number of frames transmitted to each station and the mean frame size are the same for each station. Obviously, it will not correspond to the reality, but it allows us to express the problem with an equal priority to each station. This assumption is motivated by different reasons: i) the optimization problem is thus addressed without privileging a station because it has more traffic than the others at a given time; ii) Internet traffic is quite sporadic and the time scale in terms of dynamics is very likely smaller than the one of the association problem, which implies that, in average, stations may receive the same amount of data; iii) the association problem output consists in associating stations with APs and the goal is not to directly set/reserve any resource for each station; consequently, stations that receive more traffic still benefit of the statistical multiplexing offered by the Wi-Fi technology. Table 1 summarizes the different notations used throughout this paper.

Lij

Mean number of frames transmitted from AP j to Sta i xij

1 if Sta i is associated to AP j , 0 otherwise sij 1 if AP i is in sensing range of AP j , 0 otherwise

Table 1: Notations

We model the IEEE 802.11 infrastructure based wireless network through the following steps. We consider only the IEEE 802.11 DCF mode [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]. The objective function that we optimize is based on the mean throughputs between stations and APs, denoted d ij (i ∈ {1, ..., n} and j ∈ {1, ..., m}). By convention, we set d ij = 0 if the station i is not associated to AP j . This throughput depends on the number of stations associated with the AP, and the corresponding link capacity. The link capacity r ij is defined here as the maximum amount of data that can be exchanged between AP j and the station i in one second. The throughput d ij is the throughput when considering the other stations and, in one of the model (see Section 3.1.2), the other interfering APs. In other words, d ij takes into account the fact that the medium is shared whereas r ij does not.

We present our optimization problem under two variants. The first approach assumes that the channels used by the access points are orthogonal, meaning that they can not detect each other and can transmit at the same time. It is equivalent to assume that there are as many orthogonal channels as APs. Then, in the second approach, we consider that the number of orthogonal channels is limited. Consequently, APs which use the same channel and which are in the sensing range of each other share the medium. The formula that characterizes the throughput between an AP and a station is refined accordingly.

Orthogonal channels

We assume that all APs use different orthogonal channels, or equivalently the APs using the same channel are far enough to avoid any interference and signal detection. Therefore, each AP can be considered as an independent sub-network and the mean aggregate throughput for the whole Wi-Fi network is the sum of the mean AP throughputs. We begin by computing the mean overall throughput offered by an AP from which we derive the mean throughput between this AP and one of its stations.

The mean throughput D j of AP j is defined as the downlink throughput sent by this AP to the set of its associated users:

D j = n i=1 d ij
It can also be expressed as the ratio between the mean quantity of data transmitted to all wireless stations associated to it and the time required for these transmissions:

D j = n i=1 L ij p i x ij n i=1 L ij t ij x ij (1)
where L ij is the mean number of frames sent from AP j to Sta i , p i is the mean size of these frames, x ij indicates if Sta i is associated to AP j (it equals to 1 if it is true, and 0 otherwise) and t ij is the mean time to send a frame from AP j to Sta i . This time is given by the ratio between the mean frame size and the link capacity:

t ij = p i r ij (2)
By substituting ( 2) in (1), we get:

D j = n i=1 L ij p i x ij n i=1 L ij p i r ij x ij (3)
As we assume that the mean number of frames transmitted to each station and the mean frame size are identical for each station, the mean overall throughput of an AP is then given by:

D j = n i=1 x ij n i=1 x ij r ij (4)
Also, as we assume that the stations associated to the same AP receive the same amount of data in average, then the throughput of the AP is equally shared among its wireless stations. Therefore, the mean throughput d ij between a station and its AP (AP j ) becomes:

d ij = D j n k=1 x kj (5)
Substituting D j in its formula, we get:

d ij = 1 n k=1 x kj r kj (6)
From Equation ( 6), we can easily see that the mean throughput d ij of a Sta i associated to AP j is the same for all stations associated to this AP, whereas they may experience different link capacities with this AP.

Our optimization aims to maximize the throughput of the total downlink for the whole network while ensuring fairness between wireless stations. In order to introduce fairness in the objective function, we use the logarithmic utility function proposed by Kelly in [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF]. The association optimization problem with orthogonal channels can then be formulated as follows:

max n i=1 log m j=1 d ij x ij with d ij = 1 n k=1 x kj r kj 1 ≤ i ≤ n, 1 ≤ j ≤ m (7) s.t m j=1 x ij = 1 1 ≤ i ≤ n, x ij ∈ {0, 1} 1 ≤ i ≤ n, 1 ≤ j ≤ m, if r ij = 0 then x ij = 0 1 ≤ i ≤ n, 1 ≤ j ≤ m.
The objective is thus to find the set of association variables x ij that maximizes the total network throughput while ensuring a certain fairness. The two first constraints are related to the association variables x ij and ensure that a station is connected to a single AP. The third constraint aims to guarantee that a wireless station cannot associate with an AP that is not within its receiving range.

Non-orthogonal channels

We propose to refine the model by considering nonorth-ogonal channels. A certain number of orthogonal channels are available but their number is limited, so several APs may use the same channel. In practice, it is difficult to know the various interferences that can undergo a radio signal in a wireless network. A source of interference can belong to the same Wi-Fi network, e.g. a nearby AP with the same SSID, part of the same Extended Service Set (ESS), or can be external such as another wireless network, or any radio source in the same frequency band. As information on interferences and traffic are not easily available and unpredictable for external sources, we consider only interferences that exist between APs of the same ESS.

We assume that the assignment of the channels to the APs has been set. Two APs will detect transmissions of each other if they use the same channel and are in the detection range of each other. It leads to a share of the medium, as transmissions can not take place at the same time or collisions may happen if they transmit at the same time. The two APs are then in conflict.

According to the IEEE 802.11 DCF mode, APs in mutual conflict have equivalent opportunities to access the medium [START_REF] Berger-Sabbatel | Short-Term Fairness of 802.11 Networks with Several Hosts[END_REF]. Therefore, we assume that the number of accesses to the medium is equal, in average, between conflicting APs. In Figure 2a, we represent three APs in mutual conflict.

To compute the mean throughput D * j of AP j in presence of conflicts, we use Equation [START_REF]Wireless LAN medium access control (MAC) and physical layer (PHY) specifications amendment 8: IEEE 802.11 wireless network management[END_REF] and adapt it to this context. The throughput of stations associated to the same AP is seen as an aggregation, as shown in Figure 2b. d ij is then replaced by D * j . D j corresponds to the mean throughput of AP j without conflict, therefore r kj (which is the bandwidth obtained by one station without conflict) is replaced by D j . Finally, in this context, the share comes from the APs in conflict: x kj is replaced by s kj that represents the number of APs in conflict with AP j . Note that this adaptation of Equation ( 6) is possible because the opportunity to access the channel is the same for all APs in mutual conflicts (as the throughput of an AP is equally shared among its associated stations in the previous model):

D * j = 1 m k=1 s kj D k (8)
Substituting ( 4) in ( 8), we get :

D * j = 1 m k=1   s kj n i=1 x ik n i=1 x ik r ik   (9)
As for the case with orthogonal channels, we assume that the AP throughput is equally shared among the stations associated with it. Therefore, the mean throughput for a particular station is:

d * ij = 1 n i =1 x i j • 1 m k=1   s kj n i =1 x i k • n i =1 x i k r i k   (10)
The formulation of the association optimization problem in a wireless network with non-orthogonal channels is given as follows:

max n i=1 log m j=1 d ij x ij with d ij = 1 n i =1 x i j • 1 m k=1    s kj n i =1 x i k • n i =1 x i k r i k    (11)
s.t

m j=1 x ij = 1 1 ≤ i ≤ n, x ij ∈ {0, 1} 1 ≤ i ≤ n, 1 ≤ j ≤ m, if r ij = 0 then x ij = 0 1 ≤ i ≤ n, 1 ≤ j ≤ m.
The objective here is to maximize the overall network throughput while ensuring a certain fairness between the wireless stations when the APs use nonorthogonal channels. The expression of the mean throughput between an AP and an associated station has changed, compared to the orthogonal channel case, to take into account conflicts between APs. The constraints are the same as in the orthogonal channel case.

Optimization problem solving

The optimization association problem, as formulated in the previous section, is a non-linear optimization problem with discrete variables, which is known to be NP-hard [START_REF] Bu | Generalized proportional fair scheduling in third generation wireless data networks[END_REF]. We propose an heuristic, based on a local search to approach the optimal solution.

Most of the studies that deal with optimization of Wi-Fi associations, and that have been briefly present in Section 2 [START_REF] Karimi | Optimal collaborative access point association in wireless networks[END_REF][START_REF] Li | Proportional fairness in multi-rate wireless LANs[END_REF][START_REF] Li | AP association for proportional fairness in multi-rate WLANs[END_REF][START_REF] Tang | Throughput optimization via association control in wireless LANs[END_REF], use approximation algorithms based on relaxation to a non-linear convex program. It allows them to apply the rounding process proposed by Shmoys and Tardos for the generalized assignment problem [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF], to provide binary values of the association variable x ij . This often does not allow an exact solution of the problem in a reasonable computational time.

Instead, to solve our optimization problem, we propose an iterative heuristic based on the principle of local search, also called descent or iterative improvement. Local search is an important class of heuristics used to solve combinatorial optimization problems.

The key idea of a local search algorithm is to start from an initial feasible solution and iteratively find, at each iteration, a solution called a best neighbor that improves the objective function [START_REF] Walser | Integer Optimization by Local Search: A Domain-independent Approach[END_REF]. The main benefits of local search lie in its simplicity and its iterative process which can stop the optimization process at any time to comply with a constraint like the computation time for instance. Contrary to constructive approaches, local search algorithms consider only complete feasible solutions during the search. The proposed algorithm has then the advantage to improve Wi-Fi associations at each iteration, and can be stopped at any time with a feasible solution. The time that the system spends in computing a solution can thus be bounded and tuned.

Our iterative local search method is based on two essential elements: a neighborhood structure and a procedure exploiting this neighborhood. The method can be summarized as follows:

1. It starts with an initial feasible solution.

2. At each iteration, it chooses, among all the neighbors of the current solution, one of the solutions that maximizes the objective function. This neighbor becomes the current solution on which to apply the next iteration.

A neighbor of a feasible solution X(X = (x ij ) 1≤i≤n,1≤j≤m ) corresponds to a feasible solution where only a single station has changed of access point compared to the given solution X. Note that the change must respect the constraints. The condition to stop the iteration loop can be chosen according to the context. For instance, it can be stopped when it has: 1) found a local maximum (as the solution space is finite, the local search reaches a local maximum in a finite number of iterations when the current solution has no neighbor with a greater objective function), 2) reached a fixed maximum threshold for the number of iterations, or 3) exceeded a fixed maximum threshold for the runtime of the optimization program.

The two last stop conditions ensure that a feasible and better solution (compared to the initial one) may be found while respecting the time constraint of the system.

Performance Evaluation

In order to assess the effectiveness of the proposed approach, we used the N etwork Simulator -3(ns -3.23) [START_REF]NS-3: A discrete-event network simulator for internet systems[END_REF]. Compared to optimization tools, this tool offers a more realistic and richer environment and simulates all aspects of a network from the physical to the application layers.

Simulations are performed as follows. The first step consists in using ns-3 to create the network topologies, to compute the link capacities between the APs and the stations (r ij ) and to extract the initial association based on the RSSI values. A link capacity between one AP and one station corresponds to the throughput received by the station when a saturated constant bit rate (CBR) flow is generated between the two considered nodes and when all other stations and interferences from the other AP/stations are neglected. Note that these capacities are computed at the application layer of the TCP/IP stack. This has the advantage of: i) taking into account the headers generated by the sub-layers and the overhead induced by the IEEE 802.11 DCF mode (e.g. the MAC header and the Acknowledgment frame), ii) directly obtaining the useful throughput, iii) designing the proposed model independently of the standard (802.11 a/b/g/n, ...).

In a second step, we generate CBR traffic between APs and stations. This traffic is homogeneous between stations and saturates the medium. The generated payloads have a size of 1500 bytes. We then measure the throughput obtained (d ij ), during the ns-3 simulation, for all stations.

The last step consists in running our heuristic on the initial solution (RSSI based association). The heuristic has been integrated to ns-3. Once our heuristic has found the solution, we force the stations to associate to the APs computed by our heuristic. We then generate again the same CBR traffic between APs and stations and measure the throughput obtained (d ij ) for all stations.

We also compute the Jain's Index [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF] to evaluate the fairness achieved in the network. It is defined as follows:

Jain = n i=1 d iAP (i) 2 n n i=1 d 2 iAP (i)
where AP(i) corresponds to the AP with which the station i is associated.

Wireless interfaces are configured to use the IEEE 802.11n standard. It allows to use the two frequency bands 2.4 GHz and 5 GHz. We use the propagation model LogDistancePropagationLossModel that defines the received signal power as being the ratio between the transmitted signal power and the cube of the distance. The transmission power is 40 mW (16.00206 dBm). We use the rate adaptation algorithm IdealHtW if iM anager of ns-3 to set the physical rate between stations and APs. We had to develop it as it was not available for 802.11n. The code may be found in [START_REF]NS-3 code: Ideal HT Wi-Fi manager[END_REF]. This manager determines the best physical transmission rate to use between a station and its AP according to the SNR measured on packets sent from the source to the destination.

The Wi-Fi network consists of 25 (5x5) access points, deployed on a square grid such that the distance between two adjacent APs is 100 meters. This distance leads to overlapping zones. A station may then have several choices for its association. APs are then randomly moved within a circle with a diameter of 25 meters (the center being the grid points) to obtain more realistic topologies. Stations are randomly distributed in the coverage area of the access points. The distribution is Gaussian, centered in the middle of the grid. A topology sample is shown in Figure 3.

For each scenario, the number of APs is fixed (25), and we increase the number of wireless stations from 25 to 250. For each scenario, we perform 30 different configurations for a given number of stations. These configurations are obtained by randomly changing the station positions. In the different figures, each point is the mean of these 30 simulations with a confidence interval at 95%.

Orthogonal channels

Figure 4 illustrates the performance results when all APs have orthogonal channels in the 2.4 GHz band. It is very likely an unrealistic situation as they are very few orthogonal channels in this frequency band. However, it can happen in a sparse network. This scenario enables to show the solution performance when there is no radio conflict. Figure 4a represents the overall network throughput when associations are We observe that our algorithm improves the overall throughput by about 40% for a low number of stations, and by 20% when the number of stations reaches 250. Also, we can see that the overall throughput of the network increases until 75 stations (3 stations per access point in average) and remains stable for a greater number of stations. Figure 4b shows the evolution of the Jain's Fairness index before and after optimization. The optimization significantly improves the fairness, up to 120% for 250 stations. Moreover, we observe that, with the RSSI association, the fairness decreases with the number of stations whereas it seems to remain stable with our algorithm (at least with 75 stations and more).

Fairness is also illustrated in Figure 7, where for one simulation (250 stations), we plot the distribution of the number of stations associated to each AP, and the station throughput (d ij ) before and after optimization. This simulation is representative: the observed trends are similar for all simulations. In Figure 7a, we can observe that 4 APs do not have any stations associated with them with the RSSI association, whereas there is only one AP without station after optimization. With our optimization, it appears that stations are more homogeneously distributed between APs compared to the RSSI case. A more ho-mogeneous distribution of stations among the APs leads to more balanced throughputs among stations (Figure 7b). In this figure, the x-axis represents the indexes of the 250 stations in an increasing order of the station throughput. The y-axis represents the station throughput (with a log scale). It varies from 1.15 Mb/s to 136 Mb/s for the RSSI association, and from 2.51 Mb/s to 83 Mb/s after optimization. It clearly shows a better usage of Wi-Fi resources: stations use more APs and they are more homogeneously shared between APs leading to a better fairness and a throughput increase.

Non-orthogonal channels

We simulate two cases: one with 3 orthogonal channels (in the 2.4 GHz band) and one with 8 orthogonal channels (in the 5 GHz band). We distribute channels in a way that minimizes the number of conflicts and interference. It corresponds to a scenario where the AP deployment has been planned. Figure 5a (8 orthogonal channels) shows that our optimization (based on the second model Eq. 11) improves the overall throughput up to 40% regardless of the number of stations. The Jain's Fairness index, shown in Figure 5b, is improved by our optimization by a factor varying from 1.2 for 25 stations to 3 for 250 stations. Figure 6 illustrates the simulation results obtained in the 2.4 GHz band with 3 orthogonal channels. Improvements are clearly less significant than in the 8 channels case. Figure 6a shows that the optimiza- tion does not increase the overall throughput and the obtained results are almost equivalent with these two solutions, with a small advantage to the RSSIbased association. Nevertheless, we can observe an improvement of the Jain's index, with our optimization, varying from 10% to 100% (35% in average).

With our topology, the sensing range (distance at which the signal of a transmitting AP is above the clear channel assessment -or carrier sense-threshold) is approximately 221 meters. With our channel allocation, an AP detects transmissions from at most 3 APs. As we have seen during the formulation of the problem, APs/stations that share the medium tends to obtain the same throughput. Consequently, in this very constrained scenario, performance can not be significantly improved. Throughput can hardly be increased since the high number of stations on each channel does not allow to separate stations with high and low link capacities, and fairness is already imposed by stations with low link capacities.

On-Line Optimization

Our optimization can be used, in practice, in an online way. More precisely, it may be run at regular interval to take into account stations that have left or joined the Wi-Fi network or that have moved. To illustrate the dynamic behavior of our approach, we simulated, on the same network topology, another scenario in which we randomly remove 50 stations among the 250 and we replace it with 50 new ones at each interval. The new stations will first associate with in function of the RSSI value, and then our optimization is applied. The results with 8 orthogonal channels are shown in Figure 8 where we evaluate the performance at the first step with and without our optimization for the 250 stations (iteration 1). Then, for each iteration (from 2 to 10), we consider 50 new stations and removed 50 existing ones. We optimize the associations and we evaluate the performance. The "Non optimized" evaluation corresponds to a configuration where the association of the 200 stations that remain come from the pre- vious optimization and the 50 new stations are associated in function of the RSSI. Figure 8a shows the improvement of the overall network throughput after the optimization at each iteration. This improvement varies between 5% and 120%. Figure 8b shows an average improvement of 110% in fairness after each association optimization.

Conclusion

In this paper, we address the association problem in Wi-Fi networks. Our solution, based on an optimization model, aims to improve the overall network throughput while achieving a better fairness between stations, compared to the classical association based on RSSI.

The main contributions of this work are the mathematical formulation of the problem and the proposed local search algorithm. The benefit of this algorithm is a convergence in a few iterations when the starting point is the default RSSI association. Moreover, the algorithm can be stopped at any time and always gives a feasible and better association. It can be easily tuned according to the CPU or time constraints of the WLAN controller. Simulation results show that the proposed optimization significantly improves the network performance. In case of orthogonal channels, our optimization increases the overall throughput up to 40% and the fairness up to 120%, and for non-orthogonal channels we observe an improvement varying from 15% to 40% for the overall throughput and from 25% to 300% the fairness. This improvement is due to a better distribution of stations among the AP, and an improvement throughput for most of the stations.

Figure 1 :

 1 Figure 1: Access points and wireless stations in the network. Dotted lines represent the possible associations between AP and stations.

m

  Number of access points in the network n Number of wireless stations in the network rij Link capacity between Sta i and AP j tij Mean transmission time of one frame from AP j to Sta i pi Mean frame size to be transmitted to Sta i dij Mean throughput obtained by Sta i when associated to AP j Dj Mean overall outgoing throughput of AP j

Figure 2 :

 2 Figure 2: Wireless network with non-orthogonal channels

Figure 3 :

 3 Figure 3: Placement of APs and wireless stations for one simulation.

Figure 7 :

 7 Figure 7: Comparison of the number of stations per AP and station throughput for one simulation sample before (RSSI) and after optimization (Optimized).

  Jain's Fairness Index.

Figure 4 :

 4 Figure 4: All Orthogonal channels.

Figure 5 : 8

 58 Figure 5: 8 Orthogonal channels.

Figure 6 : 3

 63 Figure 6: 3 Orthogonal channels.

  (a) Overall Throughput. (b) Jain's Fairness Index.

Figure 8 :

 8 Figure 8: Overall throughput and Jain's index for dynamic association optimization

It is the number of channels specified by the standard, but for some countries less channels are authorized.