1. Introduction
In recent years, the characteristics of IEEE 802.11 Wireless Local Area Networks (WLANs), such as its easy deployment, flexibility, and low cost, have made it a popular connectivity method to access the Internet. The IEEE 802.11 standards use the Received Signal Strength Indicator (RSSI) as the access point (AP) association scheme, which may lead the stations (STAs) to make associations with congested APs, while leaving adjacent APs to carry very light load or even to be idle. This kind of load unbalancing could result in network performance declining. Therefore, AP association strategy is crucial for load balance. However, various adopted metrics of AP association such as the traffic of clients [
1,
2], the number of associated clients [
3], and the channel busy ratio [
4] still cannot refrain AP performance degradation. In addition, the MAC protocol of 802.11 based on DCF (Distributed Coordination Function) provides equal long-term transmission opportunities to all clients associated with the same AP [
5]. In multi-rate WLANs, due to this kind of throughput-based fairness scheme, clients with lower rates occupy the channel for a longer time than those with higher rates do, which leads to the unfairness of channel access among clients and suppresses the aggregated throughput. Besides, the types of application services are diversified in various wireless terminals, and the different types of clients have different requirements for Quality of Service (QoS) [
6], such as bandwidth and delay. Nevertheless, almost all proposed AP bandwidth allocation strategies are based on the assumption that any client has an enormous bandwidth demand; therefore, they cannot be satisfied no matter how the bandwidth of APs is allocated to them. The flexible AP bandwidth allocation strategy based on their demand and business priority can provide more diverse service and thus perhaps bring the user a better experience.
In this paper, AP association and bandwidth allocation are jointly considered as the constraints of channel access for achieving load balance and proportional fairness in multi-rate WLANs scenario. We firstly present a Fair Bandwidth Allocation strategy based on clients’ Business Priority (FBA-BP), in which the clients’ bandwidth is calculated based on their demand and business priority. In addition, then the aggregated transmission time demanded by all the clients will be regarded as the metric of AP load. Consequently, we propose a Categorized AP Association algorithm Based on the Demands of clients (CAA-BD), which chooses the optimal associating AP according to its category and the aggregated transmission time demanded by all the associating clients. Eventually, these two joint algorithms can realize the proportional fairness of channel access and resolve the performance anomaly, thus bringing significant throughput improvement, especially in high-dense scenarios. The basic idea of AP associating algorithm was first published in CSOC2017 [
7]. However, our new proposed CAA-BD is considering not only clients’ data rates but also their business demand as the associating metric of the AP, and we also present a more detailed analytical model in the new scheme. Finally, the joint AP association and bandwidth allocation can conduct a more delicate AP selection and channel allocation, and the evaluation experiments also demonstrate that the more significant performance can be obtained in terms of AP utilization and channel fairness index.
The remainder of the paper is organized as follows. We give some related works in
Section 2.
Section 3 provides a motivation model and theoretical analysis.
Section 4 presents the details of FBA-BP and CAA-BD. We give the simulation results in
Section 5 and conclude this paper in
Section 6.
2. Related Work
Since the conventional RSSI-based AP association scheme may lead to imbalanced load traffic among APs and unfairness bandwidth allocation among clients, many literatures concentrate on conceiving AP association strategies as the alternative of the default Strong Signal First (SSF) scheme in legacy IEEE802.11.
There have been several AP association schemes for load balance among APs and various metrics are first studied to determine the AP load in some literatures. In [
8], energy consumption and throughput are both proposed as the indication of AP load. In [
9], the author uses the file download time for web browsing to estimate the AP load. In [
10], the traffic intensity of clients and the effect of hidden terminals are considered as the main factors of AP load. Simultaneously, many load balancing strategies for AP association are also investigated. In [
11], Chen et al., propose a load balancing strategy for AP association based on the game theory with local information. In [
12], a multi-constraint load balancing scheme based on cell breathing is utilized for the tradeoff between load balancing among APs and data power loss of clients. However, they are infeasible in many realistic environments due to their high complexity for clients. Gong et al. [
13] proposes a distributed adaptive load balancing algorithm for multi-rate WLANs, which uses some innovative load metrics such as throughput and transmission rates. However, it ignores the negative influence of newly arriving clients on the throughput of the existing clients.
In [
14], a comprehensive study about the correlation between load balancing and channel fairness is presented, which indicates that they cannot be easily achieved simultaneously. In [
15], Li et al., propose a time-based fair AP algorithm, which jointly considers power control and AP association for aggregated throughput and proportional fairness. However, in this algorithm, the AP association is formulated as a NP-hard problem, which can lead the clients to switch among APs frequently due to its multiple iteration process often triggering the power adjustment. In [
16], Gong and Yang present an AP association algorithm, which estimates the throughput of clients from downlink and uplink by a bi-dimensional Markov model and can achieve proportional fairness among clients. However, this algorithm has a high time complexity because some information from all nearby APs must be obtained timely. In [
17], they propose another lower complexity on-line AP association algorithm, namely Categorized algorithm (Categorized), which achieves the proportional fairness by classifying APs based on types of clients associating with them. Although the performance anomaly problem is eliminated, load imbalance may emerge.
In this paper, we propose a CAA-BD algorithm, which utilizes a new metric of AP load, the allocated transmission time of the AP, determined by all clients associating with it, as well as the newly arriving one. Meanwhile, we present an FBA-BP algorithm, which can gather the aggregated transmission time demand according to the clients’ business and their priority. Simultaneously, the APs are categorized by the types of their associating clients. Therewith, the clients will give preference to associating the AP with the same type and the least allocated transmission time. This algorithm not only improves load balance among APs, but also takes channel fairness into consideration, which effectively minimizes the impact of performance anomaly.
4. Bandwidth Allocation and AP Association Algorithms
In this section, we first present the FBA-BP algorithm to calculate the bandwidth demanded by the clients and try to provide fair service to all clients. Then, we propose the CAA-BD algorithm to solve the performance anomaly problem and achieve the load balance among APs.
4.1. Bandwidth Allocation Algorithm
Firstly, we propose the FBA-BP algorithm that allocates bandwidth according to the bandwidth demand of the clients and the clients’ business priority. Herein, all clients are divided into four classes according to their application business, and then each class determines the priority in accordance with their demand for bandwidth and delay. As mentioned in
Section 3, the priorities are classified into four classes according to their application business. The transmission time
of client
is calculated by client demand
, and thus, the total time T for an AP can be achieved by all clients associating with it. Of course, the newly arriving client also needs to be considered. The FBA-BP algorithm can be described in Algorithm 1.
Algorithm 1: The Fair Bandwidth Allocation Based on Clients’ Business Priority (FBA-BP). |
Input: Set of STAs’ throughput , Set of STAs’ transmission time Output: Set of APs’ allocated transmission time , where - 1:
Sort the clients by their business priority in the ascending order; With the same priority, sort the clients by their bandwidth demands in the descending order - 2:
Initialize = T, count = n, k = 1, = /n - 3:
A = , B = - 4:
for each STA k in the sorted clients (k ≤ n) do - 5:
if then - 6:
Add STA k into set B - 7:
k = k + 1; continue; - 8:
else add STA k into set A - 9:
, , count = count − 1, update = /count - 10:
k = k + 1 - 11:
end if - 12:
end for - 13:
for STA k ∈ set B do - 14:
= - 15:
end for
|
The FBA-BP firstly sorts the clients by the client’s business priority. If the clients’ business priority is the same, the clients are sorted according to their bandwidth demand. Next, if the demanded time of the client k is equal to or less than the current average allocated time , the client k also will be added into set A. Otherwise, client k will be added into set B. Then the current average allocated time is updated with the rest allocable transmission time and the algorithm starts up the next turn until it traverses all the clients associated with the AP. Finally, each client in set B will be allocated with time . Ultimately, Each AP will allocate its transmission time to all its associated clients. Moreover, to meet clients’ demands, it also is necessary that the AP should sort the clients by their business priority before allocating its bandwidth.
4.2. AP Association Algorithm
In this subsection, we propose a CAA-BD algorithm that first classifies APs by different types of clients associating with them. In addition, then we utilize the aggregated transmission time demanded by the clients as the associating metric of the AP, which can be obtained by FBA-BP algorithm. The CAA-BD algorithm can be described in Algorithm 2.
Algorithm 2: The Categorized AP Association Algorithm Based on Demands of Clients (CAA-BD). |
Input: Set of APs A, Set of STAs N, STA Type Vector T = {|∀I ∈ N} Output: AP association matrix X = {|∀I ∈ N, a ∈ A}
- 1:
Initialize = 0, ∀I ∈ N, a ∈ A - 2:
for each AP a ∈ A - 3:
set the category of AP a ca to zero; - 4:
end for - 5:
for each STA i ∈ N - 6:
for each AP a ∈ A - 7:
if STA i receives beacon frames from AP a - 8:
Get the category of AP a and the lowest data rate among STA of AP a; - 9:
Add AP a into subset ; - 10:
end if - 11:
end for - 12:
if any AP j ∈ subset and = - 13:
- 14:
Set to 1 - 15:
else if AP j ∈ subset and = 0 - 16:
- 17:
Set to 1, and set to - 18:
else if ∄ subset and = 0 - 19:
- 20:
Set to 1 - 21:
end if - 22:
end for - 23:
for AP j do - 24:
Use Algorithm 1 to allocate the bandwidth - 25:
end for
|
In the pseudo code above, initially, the categories of all APs are set as zero. In addition, then, each AP is classified according to the associated client with the minimum transmission rate, which also may make the transmission rate of all the associated clients close to each other and effectively avoid performance anomaly. Meanwhile, the aggregated transmission time demanded by all clients is used as the metric of AP load when associating, thus the proportional fairness can be achieved among the clients associating to the same AP.
When a new client joins the network and attempts to make an association decision, it firstly acquires a list of candidate APs and potential bit rates according to the signal strength that can be measured by beacons from nearby APs. In addition, then the client selects some APs with the same category based on its bit rate. Finally, the AP with the least allocated transmission time will be chosen as the associating AP. Alternatively, if no such AP exists, the client also may associate with the AP whose category is zero and/or allocated transmission time is the least. Consequently, this strategy can make full use of network resource and effectively improves the utilization of AP and system throughput.
6. Conclusions
In 802.11 WLANs, it is essential that the load balance among APs and fair service to clients are achieved simultaneously. In this paper, we first present the FBA-BP algorithm, which allocates the bandwidth of APs based on their business and priority. Therewith, the aggregated demand time of APs can be calculated according to all the associating clients’ bandwidth demands, which is considered as the metric of AP load. Furthermore, we also propose the CAA-BD algorithm that makes a fine-grained association decision based on the categories of APs, as well as AP load whose metric is provided by FBA-BP algorithm. We evaluate the CAA-BD algorithm in terms of average AP utilization, system throughput, delay, and the fairness index under two kinds of deployments. The results show that the CAA-BD can solve the performance anomaly to some extent and obtains load balance simultaneously.