Research Article
Access Point Selection for Fair Load Balancing in Wireless LAN
Anna University of Technology, Coimbatore, Tamil Nadu, India
C. Manoharan
Sri Shanmugha College of Engineering and Technology, Salem, Tamil Nadu, India
In recent years, WLAN technology has emerged as the predominant alternative for wireless broadband data access in local and global environments, enabling individuals to connect to the network from almost everywhere. The WLAN environment consists of APs and MUs and each MU selects an available AP in order to connect to the network without any centralized control. The IEEE 802.11 standard currently merely provides a mechanism for association and disassociation. There is no information about access point load is provided; as a result, the only viable policy for access point selection is to pick the access point with the best signal-noise ratio. An analysis of the signal-noise ratios in the two seminar halls reveals that while the access point coverage is equal, for most locations the original access point has a slightly better signal-noise ratio. The result is that nearly all the mobile users associate with the original access point leaving it overloaded and the new access point nearly idle.
Load balancing in WLANs has been intensely studied. Bejerano et al. (2007) proposed association control algorithm for efficient bandwidth allocation. An efficient decentralized AP selection algorithm is needed in order to avoid over load of MUs and different AP selection algorithms have been proposed (Nicholson et al., 2006). Bejerano et al. (2004) proposed the demand users association, the bandwidth of MUs are not stable. Since the throughput of each MU decreases in proportion to the number of MUs connected to the same AP (Fukuda et al., 2004), the concentration causes the degradation of the entire wireless network (Balachandran et al., 2002). In addition, the values of throughputs are not stable and depend heavily on the position of the MUs in case of the common algorithm. For example Fukuda et al. (2004) proposed an AP selection algorithm which is referred to as the Maximizing Local Throughput (MLT) and the result in shows that MLT achieves better minimum throughput of MUs than the throughput obtained by other AP selection algorithms. Tsai and Lien (2003) proposed to re-associate users when some conditions are violated. As suggested in existing studies in Papanikos and Logothetis (2001), the load imbalance problem can be alleviated by balancing the load among the Aps via intelligently selecting the user-AP association. Singh et al. (2008) proposed position based load balancing scheme for mobile users, find the position and placing the user is difficult to implement. Jabri et al. (2008) proposed the protocol for increase the throughput but the architecture of the entire mobile user may not able to support. Optimal association control algorithm has been proposed by Venkatesan and Manoharan (2010). Since, the throughput and bandwidth of each MU decreases in proportion to the number of MUs connected to the same AP, the concentration causes the degradation of the entire WLAN. In this study, load sensitive approach has been proposed to access point selection that is distributed in nature.
PRELIMINARIES
Communication model : The communication model and throughputs has been discussed in this study. It is assumed that there are n Mus and m Aps in the WLAN environment and MU = {mu0, mu1,..., mun-1} and AP = {ap0, ap1,..., apn-1} denote two sets of MUs and APs, respectively.
For each pair of MU mui and AP apj, a packet error rate pi, j is defined. The packet error rate pi, j represents the signal strength between MU mui and AP apj and 0≤pi, j≤1. Since the packet error rate is the ratio of the number of test packets that are not successfully delivered to a destination, a high packet error rate indicates low signal strength.
Throughput Ti, j has been calculated by using packet error rate between MU mui and AP apj for the case in which mui is connected with apj, according to the IEEE 802.11 MAC mechanism. Let Nj be the number of MUs that are connected to AP apj. Then, the throughput Ti, j is given by the following expression (IEEE Standard 802.11, 1999):
In the above expression, tT and Data denote the transmission time and the size of the transmitted packet, respectively. Since tr is a constant that depends on the WLAN environment, when all of the packets are of the same size, the Ti, j can be represented as:
In the above expression, α is a constant that depends on the wireless LAN environment. This expression implies that the throughput θi, j is linearly dependent on:
The following assumption has been employed in the communication model for the wireless LAN environment.
Each AP can send the three values which are the number of connected MUs, the sum of the throughputs and the maximum packet error rate, to any MU. In other words, each MU knows these values for all of the APs.
EXISTING ALGORITHMS
Two Existing AP selection algorithms have been discussed in this section. The first is a conventional approach used in the current WLAN technology, second is algorithm based on a communication model. The existing algorithms are briefly described in the following.
Received signal strength indicator (RSSI): The Received Signal Strength Indicator (RSSI) is a basic and conventional AP selection algorithm. Each MU associates one of available APs according to signal strength. An outline of the algorithm on each MU muj is given below:
Step 1: | For each AP apj (0≤j≤m-1), compute rssij = 1-pi, j |
Step 2: | MU will select AP apji such that rssiji = max {rssij|0≤j≤m-1} |
If all MUs are uniformly distributed, RSSI is sufficient for obtaining sufficient throughputs and bandwidth. However, RSSI causes degradation of the minimum throughput and bandwidth when several MUs are close to one AP.
Maximizing local throughput (MLT): The Maximizing Local Throughput (MLT) (Fukuda et al., 2005) is an AP selection algorithm based. In this the future throughput has been calculated before going to association in the WLAN environment, the throughput between MU mui and AP apj depends linearly on the value of I-pi, j/Ni. In the MLT, each MU selects one of the available APs according to the future throughput value. An outline of MLT on each MU mui is given below:
Step 1: | Receive Nj from each AP apj (0≤j≤m-1) |
Step 2: | For each AP apj (0≤j≤m-1), set Nj = Nj+1 then, calculate the value mltj |
Step 3: | MU mui will select AP apj such that mltj = max {mltj|0≤j≤m-1} |
LOAD BALANCING ALGORITHM
Here, a new algorithm has been proposed, namely the Load Balancing Algorithm (LBA) that considers not only the priority of applications requesting connections but also the load balance among APs in the system. Incoming session will be associated with AP providing the highest data rate with RSSI, MLT and Utilization of bandwidth by each user. For best effort applications which are not delay sensitive, connection requests will be distributed to APs in the vicinity to maintain load balance in the system.
In Association Control Algorithm, MLT and RSSI is making the association in initial stage but after the association that MUs is associated with the same AP up to the connection termination this is leading the problem because after some session may be the MUs will be relieved from the APs. This type of association scheme may not be able to balance load of the system but the users requesting frequent session may not be able to communicate at the highest data rate due to the lower data rate received from the assigned APs. This may cause problem to fairness in APs. In this time the APs will handover some of the MUs to lesser loaded AP by Hand Over between Access Points (HOAP).
Here, after exploring the details of proposed algorithm for APs and MUs, stability has been analyzed for the proposed algorithm. By exchanging information among MUs and APs, the proposed scheme can be summarized as shown in Fig. 1.
In IEEE 802.11 standard, the management packets from the AP do not contain any field indicating the AP load information. To realize the proposed scheme, it is required to maintain the load of each access point and mobile user. Moreover, due to the dynamic nature of the wireless network and the mobility of MUs, the APs should keep updating the AP load by iterative moving average as where time gap Tgap is the fixed updating interval of 5 milliseconds and 0≤Tgap≤1.
The average throughput Tavg denotes the average of throughput of the MUs. Tavg is defined for an output of AP selection as follows:
(1) |
where, Θi, j is the data loss due to circumstances like objects, moisture etc.
In order to maximize the total throughput of the WLAN environment, an AP selection algorithm is needed that maximizes the average throughput.
The load on an AP apj, denoted by Lap, is the maximum of its aggregated loads on both its wireless and infrastructure links produced by all the MUs. Its requires relevant information on each mobile user mui, such as its weight wi, the effective wireless link bit rate ri, j for each AP and infrastructure bit rate Ri, j and band width allotted for link by access point is xi, j. The Lap is:
(2) |
Therefore, the load of an AP is given in terms of the time it takes to complete the transmission of certain traffic volume from each associated user. This is not surprising, since the load should be inversely proportional to the bandwidth that the AP apj provides to its users. Furthermore, the bandwidth that AP provides to mu is:
(3) |
Fig. 1: | Proposed Load Balancing Algorithm for WLANs |
Whenever the new mobile user mu is going to be joined in network then, if the Tavg with the selected AP is greater than Tmin value and, If the Load of the selected AP Lap is lesser than Maximum load of the AP Lmax, then the mu will be associated selected AP otherwise, the next best AP will be selected by AP Selection Algorithm. The step by step procedure of AP selection algorithm is follows:
Access Point Selection Algorithm (APS Algorithm):
Step 1: | Select the possible APs for the new mu from all APs according the Tavg value |
Step 2: | Calculate the current load Lap of all the APs by Eq. 2 |
Step 3: | Sort the APs in ascending order by Lap |
Step 4: | Select the AP from the list as minimum load to maximum |
Step 5: | If the load of the AP is lesser than the threshold value then select this AP to connect otherwise go to step iii |
Step 6: | If all the APs from the list is having maximum load then the MU will be connected with AP which is having the maximum Tavg value and bandwidth is calculated by Eq. 3 with that MU |
Whenever the existing mobile user mu is going to be relieved from the network then, the load of all the APs may be normalized. select the from first to last and check whether the load of the AP Lap is lesser than maximum load is allotted for each AP Lmax, then normalize the workload of the AP by Normalization algorithm. The step by step procedure of normalization algorithm is follows:
Normalization algorithm:
Step 1: | Calculate the current load Lap of all the APs |
Step 2: | Sort the APs in descending order by Lap |
Step 3: | If any of the AP is over loaded then select the AP from the list as minimum loaded and maximum loaded |
Step 4: | Select the common mu between the selected APs; make the hand over between maximum loaded to minimum loaded by HOAP in Venkatesan and Manoharan (2011) |
Step 5: | Repeat the above steps up to the load in normalized for all APs |
If all the APs from the list is having maximum load then the MU will be connected with AP which is having the maximum Tavg Value and bandwidth is calculated by Eq. 3 with that MU.
This operation is not only necessary to reduce the effect introduced by the joining order of MUs but also required for the MU to be adaptive to the dynamic wireless environment and topology changes. The period Tgap, configured to be more than Tgap seconds, is much longer than the load updating period Tgap on the AP.
A balance index β Chiu and Jain (1989) is defined as a measure that represents the fairness among MUs. The balance index β is defined for an output of AP selection as follows:
The balance index becomes 1 when all of the MUs have the same throughput. On the other hand, the balance index approaches 1/n when the throughputs of the MUs are largely imbalanced.
PERFORMANCE EVALUATION
Here, experimental results have been described for known algorithms and the proposed algorithms. All the algorithms are implemented in C language simulation environments. In the simulation, it is assumed that there are 4 APs and 100 MUs in a 2D plain with 50 m2 square area and each AP is located at the middle point of all the sides. It is assumed that all the MUs are randomly located in the plan.
In each simulation, locations are randomly generated for 100 MUs. For each mu location, the each packet error rate pi, j is calculated from the distance between MU mui and AP apj. Then, the simulation has been executed for each MU location using the following steps:
Step 1: | Select the MUs locations randomly |
Step 2: | Relocate some of the MUs from existing locations to new locations |
Step 3: | Calculate the pi,j for the all MUs locations |
Step 4: | Execute three AP selection algorithms which are RSSI, MLT and Proposed Algorithm, for the STA location in order of the permutation. Repeat the steps (2-4) 100 times |
Step 5: | Repeat the steps (1-4) 1000 times in order to stabilize the results of the algorithms |
In Fig. 2, the throughput of each and every MU and these results imply that the throughputs obtained by the RSSI and MLT are unstable and depend heavily on the locations of the STAs. However, it is confirmed that the throughput of proposed method is better than that existing methods.
Fig. 2: | Throughput of existing and proposed algorithms |
Fig. 3: | Average Bandwidth per MU of existing and proposed algorithms |
Fig. 4: | Average Balance Index of existing and proposed algorithms |
In Fig. 3, the average user bandwidth value of our method is over 10% higher than that of MLT and 17% higher than RSSI.
In Fig. 4, the average balance indices of proposed algorithm and existing algorithms. The values of the balance indices show that the proposed method achieves satisfactory fairness, while the values of the RSSI and the MLT are low.
In this research, load balancing scheme has been explored to guarantee the throughput fairness among the MUs in the WLAN environment. The algorithm is proposed for maximizing the throughput and bandwidth of individual user of among MUs. The experimental results show that the proposed algorithm achieves high throughputs and bandwidth per MU. In the future, AP selection algorithms for heterogeneous WLAN environments may be considered. The heterogeneous WLAN environments consist of Aps and Mus having different standards. In heterogeneous environment, the communication model is different from the model used in the present study and some modifications are needed in order to propose an efficient AP selection algorithm in heterogeneous WLAN.