|Year : 2010 | Volume
| Issue : 1 | Page : 44-51
Vertical Handoff Decision Algorithm Based on Optimal Grade of Service
Computer and Software Institute, Nanjing University of Information Science and Technology,No, 219, Ningliu Road, Nanjing, Jiangsu, China
|Date of Web Publication||26-Mar-2010|
Computer and Software Institute, Nanjing University of Information Science and Technology,No, 219, Ningliu Road, Nanjing, Jiangsu
| Abstract|| |
A new vertical handoff decision algorithm is proposed to minimize the cost of the grade of service (GoS) in heterogeneous wireless networks, which comprise cellular networks and wireless local area networks (WLANs). We first calculate the block probability and the drop probability, which are factors of the GoS and function of new call arrival rate, handoff call arrival rate and radius of WLANs, cellular network and WLANs under the channel-guard call admission strategy. Then we propose a cost function of the GoS, and obtain the optimal radius of WLANs by using simulated annealing (SA) method to minimize the cost. All the nodes should handoff from cellular network to WLAN if they enter WLAN's scope and handoff from WLAN to cellular network if they leave the scope. Finally, we analyze our handoff algorithm and compare it with other algorithm, and the results show that our algorithm could achieve good effects.
Keywords: Cost, Grade of service, Heterogeneous wireless networks, Markov, Simulation annealing, Vertical handoff.
|How to cite this article:|
Xie S. Vertical Handoff Decision Algorithm Based on Optimal Grade of Service. IETE J Res 2010;56:44-51
| 1.Introduction|| |
Next generation wireless systems (B3G and 4G) are envisioned to provide ubiquitous high-speed access over heterogeneous radio technologies. The integration of cellular networks and wireless local area networks has drawn considerable attention because of wider coverage and high bandwidth. In the communication process, nodes will inevitably cross a number of networks; the transfer of point of attachment from one network to another different type of network is called vertical handoff, which is an important focus to be studied in the integration of heterogeneous networks.
There are three main stages in the course of vertical handoff  . The first is the network discovery. In this phase, nodes periodically search if there are some other different types of wireless networks and take these discovered networks as candidates. The second is the handoff decision phase where nodes compare the state of the current network with the candidates, and select one as the handoff target from them according to a certain criterion. The last is the handoff implementation phase where nodes execute the handoff actions, and transfer the point of attachment from one network to another. This phase is a bit complicated and includes some procedures, such as authentication, authority, handoff in the link layer and in the IP layer, etc. Among these three stages, the second is very important, because it has a direct influence on the network performance and the quality of service of nodes.
As far as we are aware, the algorithms, concerned, to the vertical handoff recorded in literatures can be classified to four main directions. The first approach takes the received signal strength (RSS) and some other factors, such as bandwidth, delay and distance, into considerations to select the best network through a simple comparison , . The second approach utilizes the artificial intelligence techniques, such as neural network, fuzzy control and machine learning, combining these factors considered in the first approach to select the best network ,, . The third direction is based on cost/benefit value which is a function of several metrics, such as bandwidth, delay, access cost and power consumption, etc. Nodes select the network which corresponds to the minimum value by comparing the costs from different networks , . The above three methods mainly consider the quality of service of nodes after handoff, but do not consider the overall system performance such as resource utilization affected by handoffs. The fourth approach resolves the above problem, which is based on the resource management, and the handoff execution of a node is used to make the resources be optimally utilized , . The fourth approach has become a new research direction in vertical handoff algorithm in heterogeneous networks  . However, all the four approaches are not irrelevant and they could complement each other and form a new handoff decision algorithm  .
In this paper, we propose a new vertical handoff decision algorithm to minimize the cost of grade of service (GoS), which belongs to the fourth approach, in the heterogeneous wireless networks, which consists of cellular networks and wireless local area networks. The grade of service in our algorithm includes four aspects: Block probability of new call in cellular networks, block probability of new call in WLANs, drop probability of handoff call in cellular networks and drop probability of handoff call in WLANs. All of them are the functions of new call arrival rate, handoff call arrival rate and the radius of WLANs. In view of that in a period, the call arrival rates are stable, so we could represent all the probabilities as functions of the radius of WLAN.
We first calculate the two block probabilities and two drop probabilities under the channel-guard call admission strategy, and propose a cost of the GoS. Then we obtain the radius of WLANs by using simulated annealing (SA) method to minimize the cost. All the nodes should handoff from cellular network to WLAN if they enter WLAN's scope and handoff from WLAN to cellular network if they leave the scope.
The rest of this paper is organized as follows: Section 2 provides the hybrid wireless networks model. Section 3 analyzes the block probability and drop probability in channel-guard call admission method. Section 4 proposes the vertical handoff decision algorithm to minimize the cost of GoS. Section 5 is analysis and comparison of our algorithm. This paper is concluded in Section 6.
| 2.Model of Heterogeneous Wireless Networks|| |
The heterogeneous wireless networks are composed of some cellular networks and wireless local area networks. In this paper, we assume that a cellular network covers WLANs and all the WLANs have no overlapping areas. And more, we assume that they are directly adjacent between two cellular networks. For simplicity, we only draw a single cellular network and some WLANs in [Figure 1], although there are many other cellular networks beside the cellular network. However, this has no influence on the design and analysis of our handoff algorithm.
Consider the radii of cellular network and WLAN to be Ru and Rw the number of channels Cu and Cw respe tively. The region in the hybrid wireless networks that is covered by a cellular network is defined as Au with area Su and perimeter Lu . Similarly, the region that is covered by a WLAN is defined as Aw with area Sw and perimeter Lw . It is noted that Au includes Aw . The region that is covered by a cellular network but not covered by any of the WLANs is defined as Au\w with Su\w area and perimeter Lu\w . So the area Su equals to Sw plus Su\w.
According to the above assumptions and definitions, we could acquire following equations:
We assume that the calls are uniformly distributed in region Au , so the call requests in Au can be classified into four kinds: 1) the new call requests with arrival rateλn , which include two aspects, one is the requests Au\w in with arrival rate λun equaling to and the order is the requests in Aw with arrival rate λwn equaling to ; 2) the handoff call requests coming from adjacent cellular networks with arrival rate λh-uu; 3) the handoff call requests from Au/w to Aw with arrival rate λh-uu ; 4) the handoff call requests from Aw to Au/w with arrival rate λh-wu .
We adapt the fluid flow model  to analyze the dwell time, which is defined as the duration that a node stays in a certain region before it moves out of the boundary of the region, of a node in a region. The fluid model assumes the nodes are uniformly distributed throughout the whole area and each node moves in any direction with equal probability.
We assume the average moving speed of a node E(V) is , then the average dwell time in Aw is 1/νw; where the expression of νw is:
The average dwell time in Au is 1/νu , where the expression of νu is:
The average dwell time in Au\w is 1/νu\w , where the expression of νu\w is:
Next, we consider a communicating node in Au\w . When moving out of Au\w , it may enter adjacent cellular networks, or move into Aw . Therefore, the average dwell time in Au\w before the node moves into another cellular network is 1/νh-u/w , where the expression of νh-u\w is:
The average dwell time in Au/w before node moves into Aw is 1/νv-u\w , where the expression of νv-u\w is:
We assume that the arrival rates of handoff calls and new calls follow Possion distribution, the dwell time in a certain region follows exponential distribution, and the call duration time follows exponential distribution with mean value equaling to 1/η. So the channel holding time also follows exponential distribution.
| 3.Call Admission Control|| |
In this paper, we take the channel-guard method , as our call admission control strategy, which is described as follows: Each cellular network has Cu channels and each WLAN has Cw channels, and Cu-CuR channels in cellular network and Cw-CWR channels in WLAN are reserved only for handoff calls; when the occupied channels are less than CuR in cellular network, not only the new calls, but also handoff calls could be admitted; however when the occupied channels are equal to or more than CuR , only the handoff calls could be admitted; and the same to the WLANs. At the same time, we assume that a call only needs one channel.
We use a K + 1 -dimensional Markov chain to analyze the channel-guard admission algorithm. We define the state of heterogeneous wireless networks by K + 1 -tuple nonnegative integers (m,n 1,... nk) where m is the number of the active nodes in the cellular network and nk is the number of the active nodes in the k th WLAN, and P(m,n1,...nk) denotes the probability of the state(m,n1...nk) . Suppose the current state is (mo,no1,...nok) and it changes to be (mt,nt1,...ntk) in a short time driven by some event. Then we will discuss all these possible cases:
3.1 Case 1
This happens when there is a new call request in Au\w or a handoff call request comes from neighbor cellular networks. Because of it is impossible a handoff call request comes from one of the WLANs, otherwise nt should be no-1 . So the transition rate is λun + λh-uu .
3.2 Case 2
It happens when there is a handoff call request comes from neighbor cellular network. Because of mo≤CuR it is impossible that a new call request is admitted, and because of it is also impossible that a handoff call request comes from WLAN. So the transition rate is λh-uu .
3.3 Case 3
It happens when there is a new call request in the kth WLAN. Because there is no channel release in cellular network, it is impossible a handoff call request comes from cellular network. So the transition rate is λwn .
3.4 Case 4
number of WLANs satisfy It shows that the channels in WLAN have been used up, the channel released in cellular network might be driven by three events: Call finishes its communication; call leaves for the neighbor cellular networks; call leaves for the number of channel-used-up WLANs. So the transition rate is
3.5 Case 5
It shows that the channels in cellular network have been used up. The channel released in the kth WLAN may be driven by two events: Call finishes its communication and call leaves for the cellular networks. So the transition rate is
3.6 Case 6
It shows that the channels in cellular network have not been used up and the channel released in the kth WLAN is only driven by the event that call finishes its communication. It is impossible that a call comes from Aw to Au\w, otherwise mt, should be mo + 1 . So the transition rate is nokη .
3.7 Case 7
It is clear that there is a call in cellular network release its occupied channels and admitted by the kth WLAN. So the transition rate is moνv-u\w .
3.8 Case 8
Like case 7, it is clear that there is a call in the kth WLAN releases its occupied channels of WLAN and admitted by cellular network. So the transition rate is noνw .
For all the other cases, the transition rates are all equal to 0. After obtaining all the transition rates between two states, we can get the transit matrix Q . According to the equation (12) and the expression we can acquire the equilibrium state probabilityP(m,n1,...nk).
where V is the column vector composed by all the equilibrium state probabilities.
Because the calls are uniformly distributed in the region Au, the status of all the WLANs are equal. So the radii of all the WLANs must be equal, and the block probability and drop probability in any WLAN are also equal, i.e. we only need to compute the probabilities in a WLAN.
Then the block probability Pub of new call in cellular networks is:
The block probability Pwb of new call in the k th WLAN is:
The drop probability Pud of handoff call in cellular network is:
The drop probability Pwd of handoff call in the kth WLAN is:
| 4.Vertical Handoff Decision Algorithm|| |
From the analysis in section 3, we learn that if the radius of WLAN is fixed, the block probability and drop probability will be determined by new call arrival rate (NAR) and handoff call arrival rate (HAR). Usually, the arrival rates in a short period are invariable, and thus we can adjust the radius of WLAN by regulating its transmission power to optimize these block probabilities and drop probabilities. So we define a cost of grade of service, CostGoS , which is determined by the block probabilities and the drop probabilities in cellular network and one of the WLAN, and is a function of the radius of WLANs in essence.
Once the radius of WLAN is determined, all the nodes in the WLAN should communicate with WLAN. Even if the channels in WLAN are used up and there are free channels in cellular network, the call request in WLAN would not be admitted by cellular network and would be blocked or dropped. The communicating node shall handoff to WLAN if it enters WLAN and handoff to cellular network if it leaves current WLAN.
The expression of CostGoS is:
where βk,k=1, 2, 3 denotes the weight of block probability in WLAN, drop probability in cellular network and drop probability in a WLAN respectively. As to the new call originates Aw in , it is covered by the cellular network and could have been admitted by cellular network. But according to our algorithm, it loses the opportunity and we also do not want this happens much often, so the weight of β1 should be a bit bigger than one. As for the node moving from Au\w to Aw , the handoff is not necessary because it could have been using the original channel to communicate, but it must handoff to cellular network if node moves from Aw to Au\w , otherwise, it will lose the channel of WLAN. So the weight β3 of should be somewhat greater than β2 . On the other hand, because terminating an on-going call is far more annoying than refusing to admit a new call from user's point of view,β3 and β2should be much bigger than β1. The objective function and restrictive conditions are:
where Rmin and Rmax are the minimum radius and maximum radius of the WLAN.
According to the above analysis, we learn that it is very hard to obtain the optimal radius of WLAN by common numerical programming methods. Using intellectual searching methods, such as simulated annealing, will be a good choice. The procedures of the simulated annealing used in our algorithm are as follows:
S1: Select an initial radius ro randomly for all the WLANs, and let the temperature counter KSA = 1, the repetition counter LSA = 0, and the initial temperature TKSA= 1.
S2: Select a new radius rn in randomly, assuring rn is in [Rmin, Rmax] . Then compute and the result is labeled as ε .
| 5.Analysis and Comparison|| |
In this section, we illustrate the performance of the proposed vertical handoff decision algorithm and compared with other algorithm. The parameters of heterogeneous wireless networks are as follows:Ru is 1000 meters, Cu is 14 channels and Cur is 10 channels; the minimum radius Rmin and maximum radius Rmax of WLAN are 100 meters and 500 meters, Cw is 5 channels, CWR and is 4 channels; the average speed of node is 10 m/s, and the average duration time of a call is 150 seconds; The weight of β1 is 1.2, β2 is 10 and β3 is 12.
First of all, we should use simulation to verify our analytical procedures. The simulation is done by C ++ in IDE VC6.0. Because the cost of GoS is based on the block probabilities and drop probabilities in cellular network and one WLAN, which are obtained by numerical analysis, we only need to verity the block probabilities and drop probabilities.
The block probabilities and drop probabilities in cellular network and WLAN are shown from [Figure 2],[Figure 3],[Figure 4],[Figure 5] when the radius of WLAN varies from 100 meters to 500 meters where the new call arrival rate is 0.1 calls/second. The dashed lines are obtained from simulation, and the real lines are obtained from analysis. From these figures, we could see that the analytical results are very accordance with the simulation results. The gaps between the two results come from the following aspect: In the analytical method, we assume that the dwell time in a certain region follows exponential distribution, however, in the simulation, the dwell time is not so. In the simulation, we let calls appear in a random place at a region, and move in a constant speed along a straight line till they move out of the region.
From [Figure 2] and [Figure 3], we could see that the block probability and drop probability in cellular network decline when the radius of WLAN becomes larger. This is because more and more of new call requests are admitted by WLAN.
From [Figure 4] and [Figure 5], we could see that the block probability and drop probability in WLAN become larger in company with the radius of WLAN. This is because when the radius becomes larger, more and more new call requests are sent to the WLAN, this will result in the increase of block probability and drop probability.
[Figure 6] shows the optimal radius of WLAN under different new call arrival rate and different handoff call arrival rate. From this Figure, we could see that when the new call arrival rate is fixed, the radius varies consistent with the handoff call arrival rate. This is because the handoff call requests are only sent to the cellular network, which will increase the drop probability in cellular network and result in larger cost of GoS. In order to reduce the cost, we must reduce the drop probability in cellular network. If we redirect some of the new call request to send to WLAN, the drop probability could be reduced. And the only way is to increase the radius of WLAN. We also see that when the handoff call arrival rate is fixed, the radius varies inversely with the new call arrival rate. This is because the number of channels in cellular network is more than that in WLAN; the block probability in WLAN is more sensitive to the new call arrival rate than that in cellular network. The block probability will increase more in WLAN than that in cellular network, which will result in larger cost. So it must reduce the radius of WLAN so that more new call requests could be sent to cellular network.
[Figure 7] shows the optimal cost of GoS under different new call arrival rate and different handoff call arrival rate. It is obvious that no matter what arrival rate increases, it will result in larger cost.
[Figure 8] shows the Cost of GoS when the radius of WLAN varies from 100 meters to 500 meters. We find that with the radius of WLAN increasing, the cost first decreases monotonously to an extremum and then increases, with different handoff call arrival rates corresponding to different extrema. This is because when the radius becomes larger, the decrease of block probability and drop probability in cellular network is bigger than the increase of block probability and drop probability in WLAN firstly, as can be seen from [Figure 2],[Figure 3],[Figure 4],[Figure 5]. However, when the radius of WLAN keeps increasing, the increase of block probability and drop probability in WLAN will be bigger than the decrease of block probability and drop probability in cellular network.
In order to evaluate the performance of our algorithm, we compare it with the algorithm in  .  proposes an algorithm to improve the GoS in heterogeneous wireless network, and the detail of the algorithm is: There are two types networks which are overlapped; one is called default network and the other is called cooperating network. The call first attempts to access the default network, and if the channels of default network is used up, the call attempts to access the cooperating network. If the channels of the cooperating network are also used up, the call is blocked. The call, which is served by the cooperating network, will not handoff to the default network even if the default network could afford the channels.
In order to evaluate the performance of our algorithm, we assume that the default network for the call in Aw is the WLAN, and for the call in Au\w is the cellular network. What is more, our algorithm is labeled A1, and the algorithm in  is labeled A2.
From [Figure 9], we could see that the Cost of GoS of A1 is less than that of A2, which means that the performance of A1 is superior to A2. The reason comes from the two following aspects: First, the radius of our algorithm is optimized so as to lower the Cost of GoS, however, the radius in A2 is a constant; Second, there is an call admission strategy in our algorithm, and this is help to reduce the drop probabilities, however, there is no such strategy in A2.
| 6.Conclusions|| |
In this paper, we propose a new vertical handoff decision algorithm in heterogeneous wireless networks, which consist of cellular networks and wireless local area networks. The block probability of new calls and drop probability of handoff calls in different networks are computed, and the cost function of the grade of service is proposed which is based on the block probabilities and drop probabilities. The optimal radius of WLAN is obtained using the simulated annealing method. All the communicating nodes entering the scope of WLAN should handoff from cellular network to WLAN, and those leaving the scope should handoff from WLAN to cellular network. The analytical results show that the optimal radius of WLAN increases proportionally to the handoff call arrival rate but inverse proportionally to the new handoff call arrival rate, and the performance of our algorithm is superior to that in  .
Shengdong Xie received the B.S. and M.S. degrees in 2000 and 2005 respectively, and the Ph.D. degree in information and communication engineering from Nanjing University of Posts and Telecommunications, Jiangsu, China, in 2009. He now is a lecturer in Nanjing University of Information Science and Technology, Jiangsu, China. His research interests include wireless networks, communication signal processing and embedded systems.
| References|| |
|1.||J Ncnair, and F Zhu, Vertical Handoffs in Fourth-Generation Multi-Network Environments, IEEE Wireless Communications, Vol. 11(3), pp. 8-15, 2004. |
|2.||M Ylianttila, M Pande, P Mahonen, Optimization Scheme for Mobile Users Performing Vertical Handoffs between IEEE 802.11 and GPRS/EDGE Networks, Proceedings of IEEE GLOECOM, pp. 3439-43, 2006. |
|3.||A H Zahran, B Liang, and A Aaleh, Signal Threshold Adaptation for Vertical Handoff in Heterogeneous Wireless Networks, Mobile Network Applications, Vol. 11, pp. 625-40, 2006. |
|4.||J D Hou, and C O Dominic, Vertical Handover Decision Making Algorithm Using Fuzzy Logic for the Integrated Radio-and-OW System, IEEE Transactions on Wireless Communications, Vol. 5(1), pp. 176-85, 2006. |
|5.||E Stevens-Navarro, V W S Wong, and Y X Lin, A Vertical Handoff Decision Algorithm for Heterogeneous Wireless Networks, Wireless Communications and Networking Conference, pp. 3199-204, 2007. |
|6.||Q Guo, X H Xu, and J Zhu, A QoS-Guaranteed Cell Selection Strategy for Heterogeneous Cellular Systems, ETRI Journal, Vol. 28(1), pp. 77-83, 2006. |
|7.||A Hasswa, N Nasser, and H Hassanein, Generic Vertical Handoff Decision Function for Heterogeneous Wireless Networks, Second IFIP International Wireless and Optimal Communications Networks, pp. 239-43, 2005. |
|8.||L T Liang, H Wang, and P Zhang, "Net Utility-Based Network Selection Scheme in CDMA Cellular/WLAN Integrated Networks, Wireless Communications and Networking Conference, pp. 3313-7, 2007. |
|9.||G Q Ning, G X Zhu, and L X Peng, Load Balancing Based on Traffic Selection in Heterogeneous Overlapping Cellular Networks, The First IEEE and IFIP International Conference in Central Asia on Internet, pp. 26-9, 2005. |
|10.||P K Tang, Y H Chew, and L C O Michael, Improvement in Grade-of-Service in a Cooperative Overlay Heterogeneous Network, 2007 6 th International Conference on Information, Communications and Signal Processing, pp. 1-5, 2007. |
|11.|| A E M Taha, H S Hassanein, and H T Mouftah, Exploiting Vertical Handoffs in Next Generation Radio Resource Management", 2006 IEE International Conference on Communications, pp. 2083-8, 2006. |
|12.||R Tawil, O Salazar, and J Demerjian, A Decision Scheme for Vertical Handoff in Overlay Wireless Networks, 4 th International Conference on Innovations in information Technology, pp. 436-4, 2007. |
|13.|| Q A Zeng, and D P Agrawal, Modeling and Efficient Handling of Handoffs in Integrated Wireless Mobile Networking, IEEE Transactions on Vehicular Technology, Vol. 51(6), pp. 1469-78, 2002. |
|14.||D Hong, and S S Rappaport, Traffic Model and PerformanceAnalysis for Cellular Mobile Radio Telephone Systems with Priority and Non-prioritized Handoff Procedures, IEEE Transactions on Vehicular Technology, Vol. 35(3), pp. 77-92, 1986. |
|15.||N C Phuong, S H Lee, and J M Moon, Priority-based Call Admission Control of Multi-classes in Mobile networks, 2006 ICACT, pp. 1471-4, 2006. |
|16.||P K Tang, Y H Chew, and L C O Michael, Improvement in Grade-of-Service in a Cooperative Overlay Heterogeneous Network, 2007 6 th International Conference on Information, Communications and Signal Processing, pp. 1-5, 2007. |
[Figure 1], [Figure 2], [Figure 3], [Figure 4], [Figure 5], [Figure 6], [Figure 7], [Figure 8], [Figure 9]