# Application of Particle Swarm Optimizer on Load Distribution for Hybrid Network Selection Scheme in Heterogeneous Wireless Networks

Authors: Yoke Chek Yee; Su Wei Tan; Heng Siong Lim; Su Fong Chien
Journal: ISRN Communications and Networking
 (2012)

---

## Abstract

Mobile terminal with multiradios is getting common nowadays with the presence of heterogeneous wireless networks such as 3G, WiMAX, and WiFi. That Network selection mechanism plays an important role in ensuring mobile terminals are always connected to the most suitable network. In this paper, we introduce and evaluate the performance of load distribution model to facilitate better network selection. We focus on the optimization of network resource utilization using the particle swarm optimizer (PSO) with the objective to distribute the system load according to the various conditions of the heterogeneous networks in order to achieve minimum system cost. Simulation results showed that the proposed approach outperformed the conventional iterative algorithm by a cost improvement of 7.24% for network size of 1000 mobile terminals using 10 particles.


---

## Body

## 1. Introduction

There has been a drastic and huge development in both mobile technologies such as global system for mobile communications (GSM), general packet radio service (GPRS), and universal mobile telecommunications system (UMTS) which promise high mobility, wide coverage, but low bandwidth rate, as well as on other wireless technologies such as wireless fidelity (WiFi) and worldwide interoperability for microwave access (WiMAX) which offer faster rates at lower cost but suffered from limited mobility and coverage. The different characteristics of these mobile/wireless technologies help compensating for coverage, mobility, bandwidth, and speed, and this helps meeting the requirements due to the increase of user demands in a complementary manner [1]. It is therefore believed that the future network infrastructure will consist of coverage overlapping of heterogeneous networks [2], where multiradios mobile devices could seamlessly and conveniently access to any network in a ubiquitous manner according to the concept of always best connected (ABC) [3].The challenge to ubiquitous access to any network lies on an efficient and effective mobility management framework which initially focused on enabling seamless vertical handover across heterogeneous networks due to user mobility. Recently, vertical handover is also considered as proactive means to system performance improvement [4, 5]. Realizing a seamless and ubiquitous network access heavily depends on the second phase in vertical handover process called handover decision, which determines and selects one of the most optimal alternative networks to connect to. The selection of network is usually based on parameters such as signal strength, network conditions, battery power, application types, mobile node condition, operator policies, and user preferences [6]. Such selection could be executed by the mobile terminal (MT) in a distributed manner or performed by the network in a centralized manner.The basic idea of distributed network selection is to enable each MT with capability to receive other network metrics beyond signal information in order to draw conclusion on the best network for subsequent connection. However, such distributed approach failed to consider the load unbalance problem in the entire heterogeneous network [8]. A typical implementation of distributed approach can be found in [9], which is based on session initiation protocol (SIP) following the IEEE media independent handover (MIH) framework, whereby the triggering of handover was mainly based on the signal strength information. Unlike existing distributed approaches which mainly concentrated on network layer performance such as blocking probability and utilization, authors in [10] formulated the heterogeneous networks as a restless bandit system with multimedia application layer performance consideration. Nevertheless, no discussion was made on the overall load balancing across heterogeneous networks.Load balancing has been considered as one of the key technologies in converged heterogeneous networks [11] as it helps improving resource utilization and scales system capacity and as a result providing better connectivity to users. In [12], load balancing issue for both streaming and elastic applications is studied across both cellular and WiFi networks, whereby streaming application is distributed to cellular network because of its larger coverage and consistent QoS guarantees, while the elastic application is assigned to the WiFi network. In [13], the authors extended a similar study across both WiMAX and WiFi networks, whereby the system is modelled as a G/G/K loss-queue system. However, such study assumed that the capacity of WiFi networks is fixed and had no performance impact on the number of associated MTs. The concept of soft load balancing was also introduced in [13] whereby IP traffic was divided into subflows to be distributed into various different access network based on parameters such as channel conditions, topological environment, multipath, and path loss information overall system performance. There are pros and cons in both distributed and centralized network selection approaches and as such motivated the study of hybrid network selection approaches in recent years [14–16], which in general combine the best schemes/elements from both distributed and centralized approaches into a more effective and efficient network selection framework.As an effort to support the hybrid network selection approach, we propose a centralized load balancing model to facilitate better network selection. The basis of our model is a system-level cost function which takes into consideration both the network bandwidth and errors to determine the optimal load distribution among heterogeneous networks with minimal system cost. Figure1 shows an overlay of heterogeneous wireless networks with different cell sizes (e.g., macrocell, microcell, and picocell), similar to the next generation wireless network setup that could be owned by one or multicooperative operators as described in [15] through a central management server. Mobile terminal (MT) is equipped with multiple radios or network interfaces that are capable of attaching to any of these networks. The result of optimal load distribution could then be translated into an adjustment value that will be utilized by the MT to perform network selection as described in the hybrid approach in [7]. Our contribution here is to improve the iterative scheme as proposed in [7] with the evolutionary approach called particle swarm optimizer (PSO) in order to achieve local and possibly global optimal solutions. The choice of particle size also provides extra implementation flexibility on minimal cost versus runtime length.Figure 1
Overlay of heterogeneous wireless networks.This remainder of the paper is organized as follows. Section2 describes the derivation of the system cost function. Section 3 presents both the iterative algorithm and the proposed PSO algorithm. The description of the simulation model is provided in Section 4. Section 5 discusses the results, and Section 6 summarizes the paper.


## 2. Cost Function

Since the proposed PSO approach is a centralized network selection scheme, it is therefore assumed that the cost function at the central load management system for determining optimal load distribution refers to the total cost of all networks (i.e., from satellite, macrocell, microcell to picocell network) on supporting all users’ communications [7] as in (1) as follows:
(1)Cost(N1,N2,…,NM)=C1(N1)+C2(N2)+⋯+CM(NM)=∑i=1MCi(Ni),
where Ci is the cost of ith network, Ni has to pay for supporting MTs which connect to it, and M is the maximum number of networks in the entire system. This means that to support all the users in the network, the ith network has to spend a certain amount of resources such as available bandwidth, processing capability, and computational resource. All these costs are denoted by cost Ci(Ni). In short, Ci is a cost function that relies on the total number of users in network i, represented by (Ni). The larger the network (Ni) is, the larger the cost (Ci) will be. This is because more resources of the network Ni have to be utilized.The cost function in (1) depends on the total bandwidth offered to all users (B) and the service quality. These two parameters are proportional to the user size in the network. If Ni increases, it implies that the requested bandwidth by the users increases. Since the total bandwidth is limited, the quality of service (QoS) may be degraded if Ni increases. Hence, to maintain the service quality, the metric of service quality Ei(err) is included in the cost function as well. We define Ei(err) to be the total of all different errors caused by the increase of active user size, network traffic congestion, packet lost, and so forth. Setting all these constraints helps defining a near-realistic heterogeneous network environment whereby heavy traffic shall incur congestion which leads to transmission errors, long service request delays, and maybe link disconnections. However, our model does not include error which is caused by poor channel link or other factors that are not related to the increase of Ni. Hence, Ci in (1) can be written as
(2)Ci(Ni)=ci(b)Bi+ci(e)Ei(err⁡),
where ci(b) and ci(e) are the cost of offering one unit of bandwidth and the cost of correcting each error, respectively. Note that both ci(b) and ci(e) are constants that can be selected to make the sum of the values in different units meaningful. We further assume that Bi= Avg (Bi)Ni, where Avg (Bi) is the average bandwidth requested by each user in network i.SinceEi(err) is the average number of errors that may occur within a time period, it can be written as
(3)Ei(err⁡)=∑k=1∞kpi(k),
where pi(k) is the probability of having k errors in network i. If qi is the probability of having only one error during the communication period, then  pi(k)=qik, and (3) becomes
(4)Ei(err⁡)=∑k=1∞kqik=qi+2qi2+⋯+kqik+⋯=qi(1-qi)2.
Given the probability that a single communication (i.e., of one user) has errors within a time period due to network congestion is ai, then a single communication with no error within the time period is 1-ai. The probability that Ni communications have no error within one unit time is equal to  (1-ai)Ni. Therefore, the probability that Ni users’ communications have errors in a time period can be expresses as
(5)qi=1-(1-ai)Ni.
Thus, (2) can be rewritten as
(6)Ci(Ni)=αci(b)Avg(Bi)Ni+βci(e)qi(1-qi)2=αci(b)Ni+βci(e)qi(1-qi)2.Note that the Avg(Bi) can be absorbed into the cost constant ci(b), and both α and β are the respective weight of the bandwidth and error parameters in the cost function. Both (1) and (6) are the cost functions which will be minimized by the proposed PSO algorithm.


## 3. Optimization Schemes

As described, it is assumed that the maximum number of MTs in the entire system is fixed for a certain time period, and the number of networks in the system isM. Given N1+N2+⋯+NM=N, it means that our defined cost function falls under the nonlinear integer problem since Ni is an integer. Therefore, it is very hard to find the optimal solution for such cost function. We also assume that the cost constants ci(b) and  ci(e) can be obtained from the central module of the network system, whereby ci(b) contains the value of Avg (Bi) that can be obtained from the system according to [17] (e.g., through traffic monitoring/logging over certain period of time). Given the average error probability per unit time of each network ai, the weight of bandwidth α, the error parameter β, and both cost constants ci(b) and  ci(e), the proposed network-based selection cost function can be summarized as
(7)Given⁢α,β,ci(b),ci(e),aiFind⁢(N1,N2,…,NM),Mintegervariables.MinimizeCost(N1,N2,…,NM)=Min⁡⁡∑i=1MCi(Ni)Subjectto⁢∑i=1MNi=N.We have evaluated and compared the proposed approach against the iterative algorithm in [7]. Both algorithms are explained in the following subsections.


### 3.1. Iterative Algorithm

This algorithm works on a simple principle. The network with the highest cost(Cmax) that is caused by large number of active users should be reduced, whereas the network with the least number of users (Cmin) should be increased. These two extreme networks will have their δ number of users exchanged at each iterative step. In each iteration, the costs of all networks Ci are recalculated and reordered by cost value. During the next iteration, the next (maybe the same or different) networks with the highest and lowest cost will exchange their δ users. This iteration ends only when the new total cost value is larger than the old one, which was precalculated at the very beginning before the algorithm starts running. See Algorithm 1 for the summary of iterative algorithm.Algorithm 1
Initialize eachNi with arbitrary value;
ComputeCostold=Costnew=∑i=1MCi(Ni);
WhileCostold-Costnew≥0
Sort all networks byCostnew value;
FindCmax and Cmin;
ComputeCostold=∑i=1MCi(Ni);
Nmax=Nmax-δ;
Nmin=Nmin+δ;
ComputeCostnew=∑i=1MCi(Ni);
EndThe results of executing the algorithm will be the optimized users distribution(N1,N2,…,NM) with minimal overall system cost. However, such optimized solution may not guarantee a global optimal solution, and very likely it is just a local minimal solution because it generates only one possible result. To address the limitation of the simple iterative algorithm, we adopt one of the evolutionary algorithms (i.e., PSO) in order to accomplish more optimized results and increase the chances of achieving global optimal solution at the cost of higher complexity as explained in the next few sections. PSO was chosen because it could lead to computational faster convergence than genetic algorithm [18–21].


### 3.2. PSO Algorithm

PSO is a well-known evolutionary computation technique developed by Kennedy and Eberhart [22]. PSO is developed according to the social behaviour metaphor. The algorithm is initialized with a population of random candidate solutions conceptually known as particles. Each particle is assigned an arbitrary velocity and will iteratively traverse into the problem space. It is then attracted towards the location of the best fitness achieved so far by the particle itself as well as by location of the best fitness achieved so far by other particles across the entire population. A complete theoretical analysis of the algorithm is presented in [23].This subsection explains the PSO motion equations. LetYm(t) be the position of the mth particle at time t, a vector whose ith component is ym,i(t). Subsequently, Vm(t) is the current velocity of the mth particle at time t, a vector in whose ith component is vm,i(t). Similarly, the best position found by particle m at time t or earlier is represented by  Lm(t), which also consists of component lm,i(t). Eventually, G(t) is the best position of all particles at time t or earlier, with component gi(t). Each particle moves around in space based on the following equations:
(8)vm,i(t+1)=wvm,i(t)+c1×rand()×(lm,i(t)-ym,i(t))+c2×rand()×(gi(t)-ym,i(t))(9)ym,i(t+1)=ym,i(t)+vm,i(t+1),
where (8) describes the velocity update for each dimension i of the particle m. The continuous-valued particle swarm algorithm limits vm,i by a value vmax, which is a parameter of the system. Subsequently, c1 and c2 are two positive constants called acceleration coefficients that affect the maximum size step that each particle can take in a single iteration; rand()is a uniformly distributed random number in the interval [0, 1]. Equation (9) describes the updating of position at ith dimension in particle m. In this study, we use c1=c2=2.0 as suggested in [24]. The use of the inertia weight w is to speed up the convergence rate in finding the optimal solution. As initially developed, w is often reduced linearly from about 1.2 to 0.4 during a run as in [24]. The correct choice of the inertia weight provides a balance between both global and local exploitation and thus reduces the number of iterations on average in order to find a sufficiently optimal solution. To adapt PSO into the calls distribution optimisation problem, the real value ym,i is rounded up to an integer value, and this integer value is assigned to Nm.Following is the high-level sequence of the proposed Algorithm2 which utilizes and calculates the equations described earlier.Algorithm 2
Create and initiateP-particles of M-dimension and their associated objective functions (5) and (6),
whereP is the number of particles, and M is the number of networks
Repeat:
For each particlem∈[1,2,…,P], where P is the number of particles
For each dimensioni∈[1,2,…,M], where M is the number of networks
Calculate  (8) and (9)
end for;
Update the fitness value, which is the system cost value
Update the best position found so far (Global and Local) using the fitness value;
end for particles;
until a satisfactory solution is reached or computational limit are exceeded.


## 3.1. Iterative Algorithm

This algorithm works on a simple principle. The network with the highest cost(Cmax) that is caused by large number of active users should be reduced, whereas the network with the least number of users (Cmin) should be increased. These two extreme networks will have their δ number of users exchanged at each iterative step. In each iteration, the costs of all networks Ci are recalculated and reordered by cost value. During the next iteration, the next (maybe the same or different) networks with the highest and lowest cost will exchange their δ users. This iteration ends only when the new total cost value is larger than the old one, which was precalculated at the very beginning before the algorithm starts running. See Algorithm 1 for the summary of iterative algorithm.Algorithm 1
Initialize eachNi with arbitrary value;
ComputeCostold=Costnew=∑i=1MCi(Ni);
WhileCostold-Costnew≥0
Sort all networks byCostnew value;
FindCmax and Cmin;
ComputeCostold=∑i=1MCi(Ni);
Nmax=Nmax-δ;
Nmin=Nmin+δ;
ComputeCostnew=∑i=1MCi(Ni);
EndThe results of executing the algorithm will be the optimized users distribution(N1,N2,…,NM) with minimal overall system cost. However, such optimized solution may not guarantee a global optimal solution, and very likely it is just a local minimal solution because it generates only one possible result. To address the limitation of the simple iterative algorithm, we adopt one of the evolutionary algorithms (i.e., PSO) in order to accomplish more optimized results and increase the chances of achieving global optimal solution at the cost of higher complexity as explained in the next few sections. PSO was chosen because it could lead to computational faster convergence than genetic algorithm [18–21].


## 3.2. PSO Algorithm

PSO is a well-known evolutionary computation technique developed by Kennedy and Eberhart [22]. PSO is developed according to the social behaviour metaphor. The algorithm is initialized with a population of random candidate solutions conceptually known as particles. Each particle is assigned an arbitrary velocity and will iteratively traverse into the problem space. It is then attracted towards the location of the best fitness achieved so far by the particle itself as well as by location of the best fitness achieved so far by other particles across the entire population. A complete theoretical analysis of the algorithm is presented in [23].This subsection explains the PSO motion equations. LetYm(t) be the position of the mth particle at time t, a vector whose ith component is ym,i(t). Subsequently, Vm(t) is the current velocity of the mth particle at time t, a vector in whose ith component is vm,i(t). Similarly, the best position found by particle m at time t or earlier is represented by  Lm(t), which also consists of component lm,i(t). Eventually, G(t) is the best position of all particles at time t or earlier, with component gi(t). Each particle moves around in space based on the following equations:
(8)vm,i(t+1)=wvm,i(t)+c1×rand()×(lm,i(t)-ym,i(t))+c2×rand()×(gi(t)-ym,i(t))(9)ym,i(t+1)=ym,i(t)+vm,i(t+1),
where (8) describes the velocity update for each dimension i of the particle m. The continuous-valued particle swarm algorithm limits vm,i by a value vmax, which is a parameter of the system. Subsequently, c1 and c2 are two positive constants called acceleration coefficients that affect the maximum size step that each particle can take in a single iteration; rand()is a uniformly distributed random number in the interval [0, 1]. Equation (9) describes the updating of position at ith dimension in particle m. In this study, we use c1=c2=2.0 as suggested in [24]. The use of the inertia weight w is to speed up the convergence rate in finding the optimal solution. As initially developed, w is often reduced linearly from about 1.2 to 0.4 during a run as in [24]. The correct choice of the inertia weight provides a balance between both global and local exploitation and thus reduces the number of iterations on average in order to find a sufficiently optimal solution. To adapt PSO into the calls distribution optimisation problem, the real value ym,i is rounded up to an integer value, and this integer value is assigned to Nm.Following is the high-level sequence of the proposed Algorithm2 which utilizes and calculates the equations described earlier.Algorithm 2
Create and initiateP-particles of M-dimension and their associated objective functions (5) and (6),
whereP is the number of particles, and M is the number of networks
Repeat:
For each particlem∈[1,2,…,P], where P is the number of particles
For each dimensioni∈[1,2,…,M], where M is the number of networks
Calculate  (8) and (9)
end for;
Update the fitness value, which is the system cost value
Update the best position found so far (Global and Local) using the fitness value;
end for particles;
until a satisfactory solution is reached or computational limit are exceeded.


## 4. Simulation Model

We have conducted a simulation study based on 4 heterogeneous access networks, that is,M= 4 as shown in Figure 1. The total number of MTs, N =200, 400, 600, 800, and 1000, are covered by these four networks. It is further assumed that the total number of MTs is fixed during a period of time, with only unforced handover being considered. Both α and β are set to 10000 each, implying that the offering bandwidth and correcting errors are of equal importance to each network. Both cost constants ci(b) and  ci(e) are obtained from [7] as shown in Table 1.Table 1
System parameters.
c
i
(
b
)
c
i
(
e
)
a
i
Network1
1.2 × 10−6
0.12
2.0 × 10−6
Network2
1.23 × 10−6
0.113
1.0 × 10−7
Network3
1.0 × 10−6
0.12
1.0 × 10−5
Network4
1.25 × 10−6
0.11
8.0 × 10−9In this study, we have investigated 3 performance metrics. First is on the effect of applying the PSO algorithm onto achieving minimal system cost as compared to the iterative algorithm in [7], in networks with different number of MTs. We also set a baseline PSO with only two particles as the basic reference, which simulates the general nature of an iterative algorithm, against the proposed flexibility of PSO configurations with more than two particles. Second is on seeking for further understanding on the effect of particle size onto achieving minimal system cost. Last is on investigating the use of PSO with different particle size for network with large number of users.


## 5. Results and Discussion

Table2 shows the optimal calls distribution for N from 200 to 1000, with their respective minimum costs, and the actual calls distribution size across the 4 networks using 10 particles. In general, the minimal cost increases as the network size grows as shown in Figure 2. The calls distribution is not evenly spread across all 4 networks with the highest loads always on network 4. This is because it has the smallest ai, that is the network with the lowest probability of having errors due to network congestion. The same explanation goes to network 3 for having the lowest or zero loads. Both ci(b) and ci(e) did not bring any significant effect to the overall distribution because their values are not much different across the 4 networks. Hence, it is concluded that ai carries the highest weight in determining the optimal calls distribution.Table 2
Minimum cost and calls distribution for different network sizes.
Network size
Min. cost
N
1
N
2
N
3
N
4
200
2.54
19
7
0
174
400
5.42
4
34
43
319
600
7.66
87
143
0
370
800
10.05
26
73
0
701
1000
13.06
218
83
16
683
1000 [7]
14.08
240
319
121
320Figure 2
Minimum cost versus network size.Detailed calls distribution for each of the 10 particles is shown in Table3 sorted in ascending order based on the minimal cost achieved.Table 3
Minimum cost and calls distribution for 10 particles.
Particle ID
Min. cost
N
1
N
2
N
3
N
4
1
13.06
218
83
16
683
2
14.92
218
212
212
358
3
14.94
217
214
214
355
4
14.95
218
215
215
352
5
14.95
215
220
216
349
6
14.95
215
216
216
353
7
14.96
219
213
216
352
8
15.11
230
229
229
312
9
15.23
240
240
240
280
10
15.29
244
250
246
260As compared to the results from [7], which achieved the minimal cost of 14.08 with the distributions of 240, 319, 121, and 320 as indicated in the last row of Table 2, it clearly shows that the PSO algorithm with a minimal cost of 13.06 has outperformed the iterative algorithm. The limitation of the iterative algorithm lies very much on the initial calls distribution across the networks (which determines the initial cost), and also on a single walkthrough in the problem space guided by the initial cost calculated. Such approach would most likely achieve only local optimal solution. Unlike the iterative algorithm, PSO employs a variable number of particles to seek for optimal solution, which helps increasing the chance of achieving global optimal solution, that is, a cost improvement of 7.24% for network size of 1000 MTs.Table4 shows the optimal calls distribution of utilizing different number of particles, from 2, 5, 10, 15, 20 to 40, with their respective minimum costs, and the actual calls distribution size across the 4 networks for 1000 MTs. In general, the minimal cost decreases as the particle size grows, but with some interesting exceptions as shown in Figure 3. For example, utilizing 10 particles seems to incur slightly higher cost (close to 1%) than 5 particles, that is, failed to reduce the overall system cost further. The same observation goes to the case with 20 and 15 particles. However, based on the results in Table 2, PSO algorithm should still be a favourable approach here for achieving better optimization with very minor glitches on particle size configurations.Table 4
Minimum cost and calls distribution for different particle sizes.
Particle size
Min. cost
N
1
N
2
N
3
N
4
2
13.94
248
173
103
476
5
12.93
75
178
31
716
10
13.06
218
83
16
683
15
12.82
158
24
2
816
20
13.05
3
217
59
721
25
12.79
72
24
16
888
30
12.56
9
226
6
759
35
12.56
3
186
7
804
40
12.72
53
80
13
854Figure 3
Minimum cost over the number of particles.


## 6. Summary and Future Works

This paper has formulated the cost function for calls distribution in heterogeneous networks based on two parameters, namely, the offering bandwidth and service quality (i.e., probability of having communication errors) and presented an approach using PSO to seek for minimal system cost. The proposed approach outperformed the iterative algorithm in the literature by a cost improvement of 7.24% for network size of 1000 MTs using 10 particles. Our proposed approach has higher chance of achieving global optimal solution as compared to the iterative algorithm given the option to utilize a variable number of particles in the problem space.One possible future work is to consider more parameters besides bandwidth and service quality, and this includes application types, battery power, operator policies, and perhaps user preferences. It is also interesting to study the load balancing issues with different theories and models such as evolutionary games for performance comparison.



---

*Source: 340720-2012-09-05.xml*