A Cloud Evolution Based Handoff Decision Scheme with ABC Supported

Abstract

With wireless access technologies maturing, the wireless network environments have a characteristic of multiple networks overlapping, called heterogeneous wireless networks. As a key procedure of the always best connected (ABC) concept, handoff decision schemes need to consider with plenty of factors. Based on the game analysis and a cloud evolution algorithm, it is proposed that a cloud evolution-based handoff decision scheme with ABC supported to maximize user utility and network provider utility. Simulation results show that this scheme can search the optimal solution efficiently and has good performance.

1 Introduction

The access network technologies have been rapidly developed, and 2, 2.5, 3 and 4G networks appear. And they constitute heterogeneous access networks with plenty of networks overlapping at the same time. With the support of Software defined radio (SDR) and multimode intelligent terminals, it becomes the core issue for heterogeneous access networks that the Always Best Connected (ABC) concept [1] allows an application to connect with any network anywhere and anytime. And ABC supporting handoff technologies insures the application Quality of service (QoS) and the seamless roaming [2] for users among a multitude of access network technologies. But it is difficult for users to describe QoS requirements accurately, and QoS requirements have strong fuzziness [3]. In addition, handoff decision schemes need to ensure that terminals have reasonable dwell time for each decision, so as to prevent terminals from frequent handoffs. On this base, we think that handoff decision schemes should consider with the will of users and network providers besides many internal factors.

Some existing algorithms [4, 5] made handoff decisions to decrease the probabilities of handoff dropping, call blocking, and frequent handoffs. Some algorithms [6, 7] considered with some factors, such as Received signal strength (RSS), load balancing, bandwidths, delay, service types, service prices, terminal velocities, power, and user preferences to select the better wireless access technology. However, network environments and influence factors of ABC supporting handoff schemes are not considered comprehensively at the same time in these schemes. The most important thing is that they do not make users and access network providers achieve the win–win situation. So we propose a handoff decision scheme with ABC supported. This scheme should consider with application types, QoS requirements, service prices, access network provider preferences, mobile terminal conditions and access network conditions to find optimal handoff solutions, and ensure the rationality of handoff and the equilibrium of user utility and network provider utility. To improve the efficiency of decisions, we use the evolutionary algorithm based on cloud model [8], which converges more rapidly with retaining diversities.

2 Model Descriptions

According to the DiffServ (differentiated services) model, this scheme supports different types of applications, and ATS = {AT ₁,…, AT _|ATS|} is the set of applications. QS _i is the QoS requirements of AT _i type applications, where QS _i  = {[BW ^l _i , BW ^h _i ], [DL ^l _i , DL ^h _i ], [JT ^l _i , JT ^h _i ], [ER ^l _i , ER ^h _i ]}, i = 1,…, |ATS|. Since it is difficult to describe QoS requirements accurately, the form of interval is adopted to describe QoS.

Assume that the order number of an access network is $j \in \left[ {1, M} \right]$, where M represents the total number of access networks. The access network model is defined as follows.

The access network provider and access network type are NP _j  ∊ NPS and NT _j ∊ NTS, where NPS = {NP ₁,…,NP _|NPS|} and NTS = {NT ₁,…,NT _|NTS|} are the corresponding sets. Similarly, NAS _j  ⊆ ATS and SL _j  ⊆ SL are the sets of application types and service levels supported by the access network, where SL is the set of all service levels. And there are some parameters of the access network described, such as the coverage CA _j , lowest signal strength LS _j , highest terminal velocity HV _j , work frequency FR _j , total bandwidth TB _j , available bandwidth AB _j , and overload threshold AB ^min _j . If AB _j  < AB ^min _j , access network cannot accept any of the terminal requests.

Assume that the access network provides a k level service to an AT _i type application, and k ∊ SL _j . So that the QoS is $QS_{ji}^{k} = \left\{ {\left[ {bw_{ji}^{kl} ,bw_{ji}^{kh} } \right],\left[ {{\text{d}}l_{ji}^{kl} ,{\text{d}}l_{ji}^{kh} } \right],\left[ {jt_{ji}^{kl} ,jt_{ji}^{kh} } \right]} \right.,$ $\left. {\left[ {er_{ji}^{kl} ,er_{ji}^{kh} } \right]} \right\}$, where the parameter intervals are subsets of the ones of AT _i type applications, such as [bw ^kl _ji , bw ^kh _ji ] ⊆ [BW ^l _i , BW ^h _i ]. And sc ^k _ji and sp ^k _ji are the service cost and service price of access network for k level services. For seeking the greater utilities of both sides, this handoff decision scheme can support the cooperation among terminals or access networks. If there is a cooperation, pr ^k _ji should be cut or risen.

Assume that the order number of a terminal is t ∊ [1, N], where N represents the total number of terminals. The terminal model is defined as follows.

TAS _t  ⊆ ATS is the set of application types with the terminal supported. And there are some parameters of the terminal described, such as the work frequency WF _t , lowest received signal strength RS _t , current velocity of the terminal CV _t , threshold of high velocity CV _h , remainder battery capacity RB _t , and threshold of low battery capacity RB _th . If CV _t  ≥ CV _h , the terminal is considered at high velocity conditions; if RB _t  ≤ RB _th , the terminal is considered at low capacity conditions.

PP _t  = {PP _t1,PP _t2,…,PP _tm } ⊆ NPS is the sequence of user preferences to access network providers, where PP _t is sorted by preference degrees from high to low. And WP _ti is the price that the user is willing to pay for AT _i type applications.

In summary, HR _t  = {AT _i , PP _t , WP _ti } is the handoff request of terminal t.

On the base of above-mentioned models, the QoS satisfaction model is defined as follows.

In this paper, the grey relational analysis method [9] is adopted to evaluate service levels. According to handoff request HR _t , access network j provides a k level service to terminal t with an AT _i type application running based on the access network conditions. So the weighted fuzzy satisfactions for bandwidth $\left[ {bw_{ji}^{kl} ,bw_{ji}^{kh} } \right]$ and delay$\left[ {{\text{d}}l_{ji}^{kl} ,{\text{d}}l_{ji}^{kh} } \right]$ are BS ^k _ji and DS ^k _ji , as Eqs. (1) and (2). And weighted fuzzy satisfactions for delay jitters and error rates are JS ^k _ji and ES ^k _ji , which are calculated like Eq. (2).

Assume that k ^* is the ideal service level, and $BS_{i}^{{k^{*} }} = \mathop {\hbox{max} }\limits_{j} BS_{ji}^{k}$ is the bandwidth satisfaction. Similarly, $DS_{i}^{{k^{*} }}$, $JS_{i}^{{k^{*} }}$ and $ES_{i}^{{k^{*} }}$ can be obtained. The grey relational degrees of four parameters, GR ^kB _ji , GR ^kD _ji , GR ^kJ _ji , and GR ^kE _ji , are regarded as the evaluations of them. And the mean of them is the evaluation QE ^k _ji of k level service. Where GR ^kB _ji is obtained as Eq. (3), and then GR ^kD _ji , GR ^kJ _ji , and GR ^kE _ji are calculated like Eq. (3). CB ^k _ji and CD ^k _ji are the conformity of bandwidth $\left[ {bw_{ji}^{kl} ,bw_{ji}^{kh} } \right]$ and delay$\left[ {{\text{d}}l_{ji}^{kl} ,{\text{d}}l_{ji}^{kh} } \right]$ to bandwidth request [BW ^l _i , BW ^h _i ] and delay request [DL ^l _i , DL ^h _i ]. They can be calculated by Eqs. (4) and (5), where α is a constant. And conformity CJ ^k _ji and CE ^k _ji are calculated like Eq. (5).

$$ BS_{ji}^{k} = \frac{{\frac{1}{2}(bw_{ji}^{kl} + bw_{ji}^{kh} ) - \mathop {\hbox{min} }\limits_{j} \frac{1}{2}(bw_{ji}^{kl} + bw_{ji}^{kh} )}}{{\mathop {\hbox{max} }\limits_{j} \frac{1}{2}(bw_{ji}^{kl} + bw_{ji}^{kh} ) - \mathop {\hbox{min} }\limits_{j} \frac{1}{2}(bw_{ji}^{kl} + bw_{ji}^{kh} )}} $$

(1)

$$ DS_{ji}^{k} = \frac{{\mathop {\hbox{max} }\limits_{j} \frac{1}{2}({\text{d}}l_{ji}^{kl} + {\text{d}}l_{ji}^{kh} ) - \frac{1}{2}({\text{d}}l_{ji}^{kl} + {\text{d}}l_{ji}^{kh} )}}{{\mathop {\hbox{max} }\limits_{j} \frac{1}{2}({\text{d}}l_{ji}^{kl} + {\text{d}}l_{ji}^{kh} ) - \mathop {\hbox{min} }\limits_{j} \frac{1}{2}({\text{d}}l_{ji}^{kl} + {\text{d}}l_{ji}^{kh} )}} $$

(2)

$$ GR_{ji}^{kB} = \frac{{\mathop {\hbox{min} }\limits_{i} \mathop {\hbox{min} }\limits_{j} \left| {BS_{ji}^{k} - BS_{i}^{{k^{*} }} } \right| + \frac{1}{2}\mathop {\hbox{min} }\limits_{i} \mathop {\hbox{max} }\limits_{j} \left| {BS_{ji}^{k} - BS_{i}^{{k^{*} }} } \right|}}{{\left| {BS_{ji}^{k} - BS_{i}^{{k^{*} }} } \right| + \frac{1}{2}\mathop {\hbox{min} }\limits_{i} \mathop {\hbox{max} }\limits_{j} \left| {BS_{ji}^{k} - BS_{i}^{{k^{*} }} } \right|}} $$

(3)

There are four coefficients ϖ ^B _i , ϖ ^D _i , ϖ ^J _i , and ϖ ^E _i representing the importance of bandwidth, delay, delay jitter, and error rate, respectively, and ϖ ^B _i  + ϖ ^D _i  + ϖ ^J _i  + ϖ ^E _i  = 1. They are assigned by access network providers according to application types. CQ ^k _ji is the suitability of QS ^k _ji to the QoS requirements of AT _i type applications, and CQ ^k _ji  = ϖ ^B _i  · CB ^k _ji  + ϖ ^D _i  · CD ^k _ji  + ϖ ^J _i  · CJ ^k _ji  + ϖ ^E _i  · CE ^k _ji . In summary, SQ ^k _ji  =  QE ^k _ji  · CQ ^k _ji is the QoS satisfaction of a user for the k level service which is provided by access network j to AT _i type application.

$$ CB_{ji}^{k} = \left( {\frac{{\frac{{bw_{ji}^{kl} + bw_{ji}^{kh} }}{2} - BW_{i}^{l} }}{{BW_{i}^{h} - BW_{i}^{l} }}} \right)^{\alpha } $$

(4)

$$ CD_{ji}^{k} = \frac{1}{2} - \frac{1}{2}\sin \frac{\pi }{{DL_{i}^{h} - DL_{i}^{l} }}\left( {\frac{{{\text{d}}l_{ji}^{kh} + {\text{d}}l_{ji}^{kl} }}{2} - \frac{{DL_{i}^{h} + DL_{i}^{l} }}{2}} \right) $$

(5)

Apart from the QoS satisfaction model, there are other evaluating indicators defined as follows. $SP_{{t_{i} j}}$ is the satisfaction of a user for the price of an access network. If sp ^k _ji  ≤ WP _ti , $SP_{{t_{i} j}} = 1$; otherwise, $SP_{{t_{i} j}} = 0$. SR _tj is the satisfaction of a user for an access network provider. If NP _tj  ∊ PP _t , SR _tj  = 1/x ²; otherwise, SR _tj  = 0, where x is the order number of NP _tj in PP _t , and 1 ≤ x ≤ |PP _t |. If the velocity of a terminal is high at current, an access network with larger coverage should be selected to decreasing the number of handoffs. Oppositely, if the battery capacity of a terminal is low at current, an access network with smaller coverage should be selected to decreasing the power of receiving and sending to extend terminal working time. SV _tj is the velocity satisfaction of access network j to terminal t. If CV _t  < CV _h , SV _tj  = 1; if CV _h  ≤ CV _t  ≤ HV _j , SV _tj  = 1/y ²; otherwise, SV _tj  = 0. Where y is the order number of access network type NT _j in NTS sorted by the coverage from high to low, and 1 ≤ y ≤ |NTS|. SB _tj is the battery capacity suitability of access network j. If RB _t  ≤ RB _th , SB _tj  = 1/(|NTS| − y)²; otherwise, SB _tj  = 1.

To make users and access network providers achieve the win–win situation, the game analysis is used in this paper. In the game analysis, a terminal and an access network play the game. And the payoff matrices of the terminal and access network are TG and NG, as Eqs. (6) and (7), where the rows of the matrices show willingness and unwillingness of a terminal in turn, and the columns of the matrices show willingness and unwillingness of an access network; the minus sign shows the lost payoff; the penalty factor, τ > 1, shows that it would have negative effect in future if one side refuses to accept the other. If $tg_{{u^{*} v^{*} }} \ge tg_{{u^{*} v}} \wedge ng_{{u^{*} v^{*} }}$ $\ge ng_{{uv^{*} }}$, {u ^*, v ^*} is a pair of policies which can achieve Nash equilibrium of the terminal payoff and access network payoff, where u ^*, v ^*, u, v = 1, 2.

$$ TG = \left[ {\begin{array}{*{20}c} {WP_{ti} - sp_{ji}^{k} } & {WP_{ti} - sp_{ji}^{k} } \\ { - \tau \cdot (WP_{ti} - sp_{ji}^{k} )} & { - (WP_{ti} - sp_{ji}^{k} )} \\ \end{array} } \right] $$

(6)

$$ NG = \left[ {\begin{array}{*{20}c} {sp_{ji}^{k} - sc_{ji}^{k} } & { - \tau \cdot (sp_{ji}^{k} - sc_{ji}^{k} )} \\ {sp_{ji}^{k} - sc_{ji}^{k} } & { - (sp_{ji}^{k} - sc_{ji}^{k} )} \\ \end{array} } \right] $$

(7)

In this paper, a coefficient matrix Λ = [λ ₁…λ ₅] expressing the relative importance of factors is utilized, and the factors include QoS requirements, service prices, access network providers, terminal velocities, and terminal battery capacities, where ∑ ⁵ _i=1 λ _i  = 1. The value of λ _i, is assigned by access network providers.

An evaluation matrix $G_{{t_{i} j}} = [SQ_{ji}^{k} \, SP_{{t_{i} j}} \, SR_{{t_{i} j}} \, SV_{{t_{i} j}} \, SB_{{t_{i} j}} ]^{T}$ and a control coefficient Ω are introduced. And Ω expresses the influence on the utilities of both sides. If they achieve Nash equilibrium, Ω = 1; otherwise, 0 < Ω < 1. If terminal t transfers to access network j, the terminal utility $uu_{{t_{i} j}} = \varOmega \cdot \varLambda \cdot G_{{t_{i} j}} \cdot ((WP_{ti} - sp_{ji}^{k} )/WP_{ti} )$, and the network provider utility$nu_{{t_{i} j}} = \varOmega \cdot \varLambda \cdot G_{{t_{i} j}} \cdot ((sp_{ji}^{k} - sc_{ji}^{k} )/sp_{ji}^{k} )$; otherwise, both are 0.

3 Algorithm Design

3.1 Species and Initialization

Assume that S is the total number of individuals, and P is the number of populations. The mth population is PS _m , so that S = ∑  ^P _m=1 PS _m . According to the sizes of populations, populations are divided into the building population, advantage populations, and disadvantage populations. The building population is the most representative one of a species, and its size is larger than all advantage populations. There are many advantage populations and disadvantage populations in a species, and the sizes of advantage ones are much larger than all disadvantage ones. The populations are sorted by the sizes from high to low, then |PS ₁| > … > |PS _P |. Individual I _mn of population m is a decision solution. So that I _mn is N dimensional code, I _mn  = (x ¹ _mn ,…,x ^N _mn ), where x ^t _mn is the tth dimension of individual n in population m. Each dimension shows access network information j and service level information k, and n ∊ [1, PS _m ], t ∊ [1, N], j ∊ [1,M], k ∊ SL. The population initialization is a process of assigning an initial value to each individual, where j and k from each dimension of each individual are randomly assigned with the values of interval [1, M] and interval [1, |SL _j |], respectively.

3.2 Fitness Function and Forward Cloud Generator

If ∀t((TAS _t  ⊆ NAS _j ) ∧ (WF _t  ⊆ FR _j ) ∧ (RS _t  ≤ LS _j ) ∧ (CV _t  ≤ HV _j ) ∧ ((AB _j  − bw ^kh _ji ) ≥ AB ^min _j )), handoff solution I _mn is feasible, and the fitness function FT _UN (I _mn ) = ∑  ^N _t=1 (1/uu _tj  + 1/nu _tj ); otherwise, FT _UN (I _mn ) = + ∞. Obviously, the smaller the value of FT _UN (I _mn ) is, the better handoff solution is.

Ar ^Forward C(Ex, En, He) is the one dimensional forward cloud generator [10], which is a mapping from overall characteristics of qualitative concept to quantitative modality. The mapping is π: C → Π satisfying the following conditions: Θ = {p _s |Norm(En, He)}; X = {x _s |Norm(Ex, p _s ), p _s  ∊ Θ}; Π = {(x _s , y _s )|x _s  ∊ X,  $y_{s} = e^{{ - (x_{s} - Ex)^{2} /(2p_{s}^{2} )}} ,p_{s} \in \varTheta \}$. Where Norm(μ, δ) is a normal random variable, μ and δ are the expected value and standard deviation, and s ∊ [1, S] is a cloud drop. In this paper, Ar ^Forward(C(Ex _t , En _t , He _t ), C(Ex ^′ _t , En ^′ _t , He ^′ _t )) is the evolving model of each dimension x ^t _mn .

3.3 Evolving Control Strategies and Termination Condition

Evolving control strategies which adjust entropy En and hyper entropy He to control the evolving process includes the local search operation, local change operation, and mutation operation.

In this paper, the elite individual is the best individual of each generation with the minimum $FT_{UN} (I_{mn} )$. If one individual is always the elite individual in consecutive generations, it is called as an intergenerational elitist. If a new intergenerational elitist appears, the current generation is called as a nontrivial generation. Otherwise, it is a trivial generation. And the number of generations between two nontrivial generations is called as the number of consecutive trivial generations.

If a new intergenerational elitist appears, this algorithm may find a new extreme neighborhood or approach for the previous extreme neighborhood. A local search operation is needed. This operation reduces En and he to decrease the evolutionary range and increase the stability, so as to increase the search accuracy and stability for more rapidly searching the optimal solution of this extreme neighborhood. In this paper, En and he are reduced to 1/K of the originals. And K called as the evolutionary coefficient is much bigger than 1.

If the number of consecutive trivial generations achieve threshold TH _local, this algorithm may fall into a local optimal neighborhood. It needs to jump out of this small range, and try to search a new optimal solution round this neighborhood. The local change operation raises En and he to increase the evolutionary range and decrease the stability. In this paper, En and He are raised to $L = \left\lceil {\sqrt K } \right\rceil$ of the originals, where L is the evolutionary mutation coefficient.

If the number of consecutive trivial generations achieve threshold TH _global = TH _local + C ₁, this algorithm may fall into a local optimal solution and the local operation does not work, where C ₁ is a constant. It needs to get itself off the guarantee of local and search a new extreme in the global range. In this paper, the mean of some historical intergenerational elitist is regarded as the expectation Ex of forward cloud generator; entropy En and hyper entropy He are adjusted suitably; and the mutation operation is executed in all individuals of species.

If the number of consecutive trivial generations achieve threshold TH _end = TH _global + C ₂, the intergenerational elitist does not change in C ₁ local change operations and C ₂ mutation operations, where C ₂ is also a constant. So this algorithm has converged to the Pareto optimum solution, and the evolving process ends; otherwise, this algorithm does not terminate until it achieves the maximum of generation denoted by TH _max. Then, the elite individual is regarded as the optimal solution.

3.4 Algorithm Description

Step 1::

Initialize the size of species S, the number of populations P, the threshold of local search TH _local, the threshold of local change TH _global, the threshold of termination condition TH _end, and the maximum of generation TH _max.

Step 2::

According to Sect. 3.1, initialize the species. Then let the optimal fitness of species $FT_{UN}^{*} = + \infty$, the current optimal fitness $FT_{UN} = + \infty$, the number of consecutive trivial generations ct = 0, and the current number of generation et = 0.

Step 3::

Make the terminal and access network of each dimension to play the game, and determine the utilities of both sides based on cooperation conditions.

Step 4::

Calculate the fitness of each individual, assign the minimum of fitness to FT _UN , and et = et + 1. If $FT_{UN} \ge FT_{UN}^{*}$, ct = ct + 1; otherwise, $FT_{UN}^{*} = FT_{UN}$, and ct = 0.

Step 5::

If et > TH _max, go to Step 10.

Step 6::

If $FT_{UN}^{*} = + \infty$, initialize the species again, and go to Step 3.

Step 7::

If ct > TH _end, go to Step 10; if ct > TH _global, execute the mutation operation, and go to Step 9; if ct > TH _local, execute the local change operation; if ct = 1, execute the local search operation.

Step 8::

Select P individuals with the minima of fitness from the current individuals, and sort them by fitness from low to high. Regard them as the parent individual of each population, and put them into each population, respectively.

Step 9::

Utilize the forward cloud generator to generate P subpopulations, keep the size of each subpopulation, and go to Step 3.

Step 10::

If $FT_{UN}^{*} \ne + \infty$, regard the individual corresponding to $FT_{UN}^{*}$ as the handoff decision solution, successfully finish. If there is more than one individual, randomly select one from them. Otherwise, there is no solution, failed.

4 Simulation Results and Discussions

With the help of NS2 (Network Simulator 2), this proposed scheme (Scheme 1) is compared with the greedy algorithm-based handoff decision scheme [11] (Scheme 2) and the QoS-based handoff decision scheme [12] (Scheme 3). We use three hexagonal honeycomb topologies, set two kinds of user cases, and implement 300 times of experiments for 3, 5, 10, 20, and 50 terminals. The means are regarded as results in Tables 1 and 2. All the summation utilities of three schemes fall with the numbers of terminals increasing, but the downward trend and the utility of Scheme 1 are slightly lower and higher. Because Scheme 1 aims to maximize the utilities of both sides, Scheme 2 looks for the load balancing of access networks, and Scheme 3 seeks the QoS satisfaction of users. So Scheme 3 has a higher performance of QoS satisfaction, but Scheme 1 is still better than Scheme 2. Because QoS is the main factor of Scheme 1, but it is not the only one. Scheme 1 has many more advantages than the other two in the other evaluating indicators. And Scheme 1 takes reasonable time to search optimal solutions.

Table 1 Simulation results 1

Table 2 Simulation results 2

5 Conclusions

With the continuous developments of wireless access technologies and mobile terminals, handoff decision schemes supporting the ABC concept have been the main motive force promoting the development of wireless network. We make a close study of the factors influencing handoff decision schemes, and propose a handoff decision scheme with ABC supported with the help of the game analysis and the cloud evolution algorithm. This scheme takes into account of application types, QoS requirements, service prices, access network providers, terminal velocities, battery capacities and access network conditions, and realizes the maximization of user utility and network provider utility. The simulation results show that this proposed scheme has better performance compared with existing schemes.