[attachment=1255][attachment=1257]
ABSTRACT
In cellular networks, QoS degradation or forced termination may occur when there are insufficient resources to accommodate handoff requests. One solution is to predict the trajectory of mobile terminals so as to perform resource reservations in advance. With the vision that future mobile devices are likely to be equipped with reasonably accurate positioning capability, we investigate how this new feature may be used for mobility predictions. We propose a mobility prediction technique that incorporates road topology information, and describe its use for dynamic resource reservation. Simulation results are presented to demonstrate the improvement in reservation efficiency compared with several other schemes.

1. INTRODUCTION
In recent years, there has been a rapid increase in wireless network deployment and mobile device market penetration. With vigorous research that promises higher data rates, future wireless networks will likely become an integral part of the global communication infrastructure. Ultimately, wireless users will demand the same reliable service as today's wire-line telecommuni-cations and data networks. However, there are some unique problems in cellular networks that challenge their service reliability. In addition to problems introduced by fading, user mobility places stringent requirements on network resources. Whenever an active mobile terminal (MT) moves from one cell to another, the call needs to be handed off to the new base station (US), and network resources must be reallocat¬ed. Resource demands could fluctuate abruptly due to the movement of high data rate users. Quality of service (QoS) degradation or even forced termination may occur when there are insufficient resources to accommodate these handoffs.

If the system has prior knowledge of the exact trajectory of every MT, it could take appropriate steps to reserve resources so that QoS may be guaranteed during the MT's connection lifetime. However, such an ideal scenario is very unlikely to occur in real life. Instead, much of the work on resource reservation has adopted a predictive approach. One approach uses pattern matching techniques and a self-adaptive extended Kalman filter for next-cell prediction based on cell sequence observations, signal strength measurements, and cell geometry assumptions. Another approach proposes the concept of a shadow cluster: a set of BSs to which an MT is likely to attach in the near future. The scheme estimates the probability of each MT being in any cell within the shadow cluster for future time intervals, based on knowl¬edge about individual MTs' dynamics and call holding patterns.
In the United States, the FCC recently man¬dated that cellular service providers must be able to pinpoint a wireless emergency call's originat¬ing location to within 125 m. This has spurred intensive research in mobile tracking techniques. One promising approach is the integration of a global positioning system (GPS) receiver in each MT. It is very reasonable to expect assisted GPS positioning methods to yield an accuracy of less than 20 m 67 percent of the time. During 2003-2009, a new batch of GPS satellites will be launched to include two addi¬tional civilian carrier frequencies that could potentially yield positioning accuracy within 1 m for civilian users, even without the use of a ground-based augmentation system. As more breakthroughs in positioning techniques take place, fueled by the strong interest in location-based services from the industry, MTs are likely equipped with reasonably accurate location tracking capability in the near future. The time is thus ripe for active research into how such inherent tracking capability may be harnessed to bring about a leap in wireless network services.
One exciting research area in which mobile positioning is extremely valuable is mobility pre¬diction. The use of real-time positioning infor¬mation for mobility prediction could potentially give rise to better accuracy and greater adapt¬ability to time-varying conditions than previous methods. The availability of practical and accurate mobility prediction technique could open the door to many applications such as resource reservation location management- location-based service and others that have yet to be identified. While there has been previous work that attempted to perform mobility prediction based on mobile positioning, none of the work has addressed the fact that the cell boundary is normally fuzzy and irregularly shaped due to terrain characteristics and the existence of obstacles that interfere with radio wave propagation. Instead either hexagonal or circular cell boundaries have been assumed for simplicity.
Our research seeks to develop mobility pre¬diction techniques that utilize real-time mobile positioning information without the need for any cell geometry assumption. While the positioning accuracy of current commercially available GPS-based MTs is still poor, our work is built on the assumption that future MTs could achieve much better accuracy than today (say < 10 m). We have developed a decentralized prediction scheme in which individual MTs equipped with positioning capability shall perform mobility pre¬dictions based on approximated cell boundary data that were downloaded from the serving BS. The approximated cell boundary is represented as a series of points around the BS; these points are computed based on the previous handoff locations reported by other MTs. In that scheme, road topology information has not been incorpo¬rated. Since MTs that are carried in vehicles would encounter more frequent handoffs. They are the ones that would benefit most from mobil¬ity predictions, and are therefore the main focus of our work. Because vehicles travel on roads, the incorporation of road topology information into the prediction algorithm could potentially yield better accuracy. In this article, we consider a centralized approach in which each BS shall perform mobility predictions for individual active MTs within its coverage area. Since a BS has more computational and storage resources than an MT does, we can afford to incorporate road information into our prediction scheme for better accuracy.
The remainder of this article is organized as follows. We first describe the mobility prediction technique we have developed. We then describe the application of the proposed prediction tech¬nique for wireless resource reservation with the objective of handoff prioritization. Next, we describe the simulations that have been carried out for performance evaluation. Finally, we give our conclusions.
2. ROAD-TOPOLOGY-BASED (RTB) MOBILITY PREDICTION TECHNIQUE
In our proposed technique, we require the serv¬ing BS to receive updated information about each active MT's position at regular time inter¬vals (e.g., 1 s). This will consume several bytes per second of wireless bandwidth for each MT, which might be negligible for future wireless ser¬vices. In order to incorporate road information into the mobility predictions, each BS needs to maintain a database of the roads within its coverage area, We shall treat the road between two neighboring junctions as a road segment, and identify each segment using a junction pair (J1, J2), where a junction can be interpreted as the intersection of roads (e.g.- T-junction or cross-Junction). The approximate coordinates of each junction pair are to be stored in the database. Since a road segment may contain bends, it can be broken down further into piecewise-linear line segments. The coordinates defining these line segments, within each road segment are also recorded. All the above coordinates could easily be extracted from existing digital maps previously designed for GPS-based navigational devices. Infrequent updates to these maps are foreseen because new roads are not constructed very often, while existing road layouts are seldom modified.
The database also stores some important information about each road segment. Since two-way roads would probably have different characteristics for each direction. The database shall store information corresponding to oppo¬site directions separately. Information stored in the database includes the average time taken to transit the segment, the neighboring segments at each junction, and the corresponding probability that an MT traveling along the segment would select each of these neighboring segments as its next segment- These transition probabilities could be computed automatically from the previ¬ous paths of other MTs. The database will be updated periodically every Tdatabase since many of its elements are dependent on current traffic conditions.
In reality, the transition probabilities between road segments would probably vary with time and traffic conditions. For stochastic processes whose statistics vary slowly with time, it is often appropriate to treat the problem as a succession of stationary problems. We propose to model the transition between road segments as a sec¬ond-order Markov process, and we assume that it is stationary between database update instances to simplify the computations. Based on this model, the conditional distribution of an MT choosing a neighboring segment given all its past segments is assumed to be dependent only on the current segment and the immediate prior segment.

Using the road topology shown in Fig.1 as an illustration consider two MTs (MT1 and MT2) that the currently traveling from junction B toward junction E. MT1 came from segment CB. While MT2 came from segment AB. Based on the assumed model, the conditional probabil¬ity of MT1 going to segment EF will be comput¬ed differently from that of MT2.
If previous handoffs have occurred along a road segment, the probability of a handoff occurring in that segment is computed from previous data observed. The handoff probabili¬ty, the target handoff-cell. As well as the average time and position at which handoffs occur after entering the segment, are recorded. We shall refer to a segment that has experienced previ¬ous handoffs as a handoff-probable segment (HPS). An assumption made here is that MTs traveling along the same road segment in the same direction as previous MTs that have encountered handoffs are likely to encounter handoffs themselves.
Using the model described above, we could determine via chain rule the conditional proba¬bilities of reaching and handing off at each of the HPSs from segments that are several hops away. We could also estimate the average time required to reach them. Using current position and speed information, as well as previously col¬lected statistics corresponding to each segment along the paths. The target handoff cell corre¬sponding to each HPS is also available from the database. We could in turn estimate the proba¬bility that an MT would hand off to each neigh¬boring BS within any specified threshold time.
3. HANDOFF PRIORITIZATION VIA DYNAMIC RESOURCE RESERVATION
Among the many possible applications for which an accurate mobility prediction technique would be a valuable tool, this article focuses on apply¬ing mobility predictions to dynamically adjust wireless resource reservations to improve the efficiency of handoff prioritization schemes. In the classic handoff prioritization problem, hand-off requests are prioritized over new call requests by reserving wireless resources at each BS that could only be utilized by incoming handoffs. The prioritization of handoffs is necessary to improve the user's perception of QoS, because forced ter¬mination of an ongoing call during handoff (due to insufficient resources at the new BS) is gener¬ally more objectionable than the blocking of a new call request. Since any such resource reser¬vation would inevitably increase the blocking probability of new calls and reduce the overall system resource utilization, it is extremely impor¬tant that reservations be made as sparingly as possible while achieving the desired degree of handoff prioritization. In this way, wireless ser¬vice providers would be able to provision high-quality services without compromising their revenues unnecessarily.
Early work in handoff prioritization pro¬posed static reservation at each BS as a solution, in which a fixed portion of the radio capaci¬ty is permanently reserved for handoffs. Howev¬er, this approach is unable to handle variable traffic load and mobility it might underutilize precious radio resources when handoffs are less frequent, and could experience high forced ter¬minations when mobility is high. On the other hand the use of real-time mobility predictions for resource reservations has the merit of being more robust to changes in traffic conditions This is potentially more efficient than static reservation and non-predictive
schemes. As men¬tioned earlier, several previous attempts to utilize mobility predictions for resource reservations have the shortcomings of relying on unre¬alistic cell geometry assumptions. The applicability and performance of these tech¬niques in actual networks are therefore unclear. Our previous work is the first handoff prioritization scheme based on mobility predictions that consider irregular cell boundaries. However the prediction model still has room for improvements it does not utilize road topology information, but merely uses instantaneous speed and direction for mobility predic¬tions. Since MTs carried in vehicles are the ones that would encounter the most frequent hand-offs, and the incorporation of road information improves the prediction accuracy for such MTs. Our new mobility prediction technique described in this article could potentially achieve more efficient resource reservations.
In our scheme, each BS shall have a reservation target (Rtarget) that is updated periodically according to the projected demands of anticipat¬ed handoffs from neighboring cells. A new call is accepted if the remaining resource after its acceptance is at least Rtarget. For a handoff request, the admission control rule is more lenient: it is admitted as long as there is suffi¬cient remaining capacity to accommodate the handoff, regardless of the value Rtarget.
At each location update instant, say every 1s, all active MTs within the cell report their posi¬tions to the BS. Given both currently and previ¬ously reported positions, the BS uses an appropriate map-watching algorithm to determine the road segment each MT is transit¬ing. The speed of the MT is also estimated. Using the information stored in the database, the BS could estimate the probability that a MT would hand off to a neighboring cell within any threshold time Rthreshold.
The reservation target R at each BS is to be updated every TRSV. During each
update, the BS estimates the amount of resources it needs to reserve at each neighboring cell on behalf of those active MTs currently within its coverage. Resources are reserved only for those MTs that might handoff to these neighbors within Tthreshold. Suppose the probability that MTi would hand off to neighboring cell Cj within Tthreshold is estimated to be p, and the resource requirement of MTi is Ri. The amount of resources to be reserved in Cj on behalf of MTi is computed as the product of p and Ri. The reservation requirements for all MTs that could hand off to a neighboring cell Cj are aggregated before being conveyed to Cjâ„¢s BS using a single request message.
The threshold time Tthreshold could be inter¬preted as the time given to the target BS to set aside the requested amount of spare resources for the anticipated handoffs. During this time, spare resources are accumulated as they are released by active MTs that either end their calls or hand off to other cells; new calls are blocked as long as Rtarget is compromised. Thus, the value of Tthreshold could indirectly affect the forced termination probability PFT experienced by handoff calls entering the cell. Since the required value of Tthreshold for the same target PFT could vary over time when there are changes in dynamic factors such as system load traffic conditions, and user mobility, Tthreshold should be dynamically adjusted to keep PFT at the desired target value. We utilize an adaptive algorithm to control its value. The algorithm counts the number of forced terminations among a number of observed handoffs. It increases Tthreshold by 1 s if the measured forced termina¬tion ratio exceeds a preset value, and decreases it by 1 s otherwise. In the algorithm, the value of Tthreshold is limited to the range [0, Tthres_max].
4. SIMULATION DETAILS AND RESULTS
Handoff prioritization schemes are commonly evaluated in terms of two QoS metrics: new call blocking probability (PNC) and forced termina¬tion probability (PFT). As mentioned earlier, PFT may be reduced at the expense of increasing PNC. However, in the process of meeting the same PFT requirement, a more efficient scheme will be able to accomplish the task with lower PNC than a less efficient scheme. The efficiency of the scheme depends on whether the reserva¬tions are made at the right place and time. Therefore, a predictive scheme should outper¬form a non-predictive scheme. Similarly, the effi¬ciency of a predictive scheme should improve with its prediction accuracy.
To facilitate the evaluation of the proposed scheme, a novel simulation model was designed. Previous work in the literature either assumes that MTs travel in straight lines for long periods of time, or assumes that MTs follow random movements that do not resemble vehicular motion on roads. Our simulation model incorpo¬rates road layouts that place constraints on MTs' paths. This establishes a more realistic platform to evaluate the performance of any positioning-based prediction algorithm.
The simulation network consists of 42 wire¬less cells. In order to eliminate boundary effects that could make it very difficult to comprehend the performance evaluation results, we have used a common approach found in the literature cells at the boundary wrap around as shown in Fig. 2. In this way, whenever an MT travels out of the network boundary, it is re-injected into the network again via the appropriate wrap-around cell as though a handoff has occurred from outside the simulation network. This com¬pensates for any traffic loss at the network boundary. We randomly generate arbitrary road layouts
based on some heuristic rules; real maps arc not used because we require the roads to wrap around at the network boundary. The road layouts are designed to imitate those found in city areas. Figure 3 shows an example of the road topology that was randomly generated for simulation purposes.

Figure 2. A simulation network with wrap around at network boundary.

Figure 3. A sample road layout randomly generated using heuristic rules for simulation purposes.
Although the cell layout shown in Fig. 2 adopts the hexagonal cell model, the simulation model does not assume that handoffs occur at the hexagonal boundary. In the simulation net¬work, the hexagonal model is merely used to determine the BS locations. In contrast to previ¬ously mentioned work in which handoffs are assumed to occur at either circular or hexagonal cell boundaries, the simulation model used here does not have well-defined cell boundaries. Instead, we randomly generate M = 100 points around each BS that influence the positions at which handoffs occur. We shall call them handoff influence points (HIPs). Suppose R is the cell radius (assumed to be 1000 m in the simulations), which is typically defined as the distance from the BS to the vertex of the hexagonal cell model. When an MT comes within 0.075R of one or more of these HIPs, we assume that a handoff will occur during its transit through this region. The time at which the handoff shall occur is assumed to follow a uniform distribution within the time spent in the region. The target BS is assumed to be the nearest neighboring BS at the time when the handoff occurs, although this may not be the case in real life. The HIPs are created around the BS at regular angles =360/M apart. Tile distance between each point and the BS is first generated using truncated Gaussian distribution, with a mean of 1.15R and a standard deviation of 0.2R. All the distances are truncated to the range [0.95R, 1.35R]. Next, we perform smoothing by averaging the distance of each point with those of its immediate neigh¬boring points to eliminate any gap in the handoff region.
We do not claim that the above model resem¬bles the actual handoff position distribution in a real cellular network. However, we feel that it is sufficient for the purpose of creating an irregular handoff region with some uncertainty to evalu¬ate the performance of different handoff prioritization schemes. To our knowledge, no work has modeled the 2D distribution of handoff posi¬tions in real cellular networks. Therefore, we are unable to make use of any previously known model in our simulations.
To make the problem more interesting, we introduced traffic lights in our simulation model. Two sets of traffic lights arc assumed. When one set is GREEN, the other set is RED. At a T-junction, we randomly assign one set to the two roads that make the largest angle. The other remaining road will be assigned the oppo¬site set. At a cross-junction, the roads are assigned alternate traffic light sets. Each GREEN and RED signal shall last for 60 s. We also assign a speed limit to each road segment chosen from the set 40 km/h, 50 km/h, and 60 km/h with equal probability. Each MT will be randomly assigned a speed as it enters a new road segment, using truncated Gaussian distri¬bution. The mean speed will be the speed limit of that particular road segment. The standard deviation is assumed to be 5 km/h, and the speed is truncated to a limit of three standard deviations from its mean.
In this article, the unit of bandwidth is called bandwidth unit (BU), which is assumed to be the required bandwidth to support a voice connection. Each cell is assumed to have a fixed page link capacity C of 100 BUs. For simplicity, we assume that the bandwidth requirement of each MT is symmetric, meaning that they have the same requirement in both uplink and downlink. However, it is straightfor¬ward to modify the scheme to handle asymmet¬ric requirements.
The traffic model used here is similar to the one used in. Call requests are generated according to Poisson distribution with rate (connections/second/cell) in each cell. The ini¬tial position of a new call and its destination can be on any road with equal probability. The path chosen by the MT is assumed to follow the shortest path possible. For each call request, we assume that it is of either type "voice" (requires 1 BU) or type "video" (requires 4 BUs) with probabilities RVO and 1- RVO, respectively, where RVO is also called the voice ratio. In the simulations, RVO is set to 0.5. The lifetime for each connection is exponentially distributed with mean 180 s. We adopt the same
definition of offered load per cell which is the product of connection generation rate . An average connection's BU requirement (RVO + 4(1 - RVO)], and average connection lifetime (180 s). We normalize the above by dividing it with page link capacity C to obtain the normalized offered loud per cell, L. In our simulations we set L to 1.0.
We have simulated four additional schemes for comparison purposes:
Reactive scheme: This scheme is purely reac¬tive with no prediction. It serves as a lower bound for the efficiency of the schemes consid¬ered. It measures the forced termination ratio among a number of handoffs recently observed and increases the reservation in the cell when the PFT target is not achieved or decreases it otherwise.
Choi's AC1 scheme: This is one of the three schemes proposed . In their simulations based on ID cell layout, their AC3 scheme per¬formed best among the three schemes. AC1, AC2, and AC3. However, in our simulations based on 2D cell layout, we discover that AC1 has the best performance, whereas AC2 and AC3 are over-conservative and have much worse efficiency than the reactive scheme. Therefore, we only present the results for AC1 in this article. This scheme works by estimating the probability that an MT would hand off into a neighboring cell within an estimation time window Test based on its previous cell and extant sojourn time (i.e., the time it has already spent in the current cell). It requires the use of a knowledge base containing the time spent by previous MTs in the cell, the previous cells from which they came, and their corresponding target handoff cells. Test is dynamically adjusted based on the measured forced termination ratio among a number of handoffs recently observed, and it indirectly controls the amount of resource reservations.
Linear extrapolation (LE) scheme: The MTs are assumed to possess positioning capability. However, no road information is used in the mobility predictions. Instead, the MT is simply predicted to continue moving straight in the direction obtained using linear regression over its last few positions. Its speed is estimated to be the average speed over its last few posi¬tions. The handoff region is approximated using a number of points known as handoff approxima¬tion points (BAPs). Each BAP is assigned a most likely target handoff cell computed from previous handoff requests .During each prediction instant (every 1 s). The BS uses a fast search algorithm to determine the BAP that is closest to each MT's trajectory, and estimate the time taken for the MT to reach this point. If the time is found to be shorter than a threshold time Tthreshold MT's resource requirement will be reserved at the tar¬get handoff cell. Threshold is dynamically adjusted using a mechanism similar to the one used for adjusting Test in Choi's AC1 scheme.
Benchmark scheme: This scheme serves as a benchmark indicating the best achievable results it we were to have perfect knowledge regarding when and where handoff requests will occur. It is impossible to achieve this in real life. Reserva¬tions are computed for each active MT at regular time intervals (1 s). If an MT's handoff time is within Tthreshold, the MT's resource require¬ment will be reserved at the target handoff cell. Tthreshold is dynamically adjusted using a mecha¬nism similar to the one used for adjusting Test to meet any specified PFT target.
In the following, we present the results obtained from the simulations. Note that all results presented herein are the averages over 42 cells in the simulation network. In our simu¬lation with no handoff prioritization, both PNC and PFT are 7.6 percent. This is unacceptably high for PFT thus explaining the need for hand-off prioritization. Figure 4 shows the plots of PNC vs PFT for the five
schemes considered. For each scheme, we varied the target PFT to illustrate its trade-off with PNC. For any fixed L (set to 1.0 in the simulations), the relative posi¬tions of such trade-off curves could demon¬strate the relative efficiencies among the different schemes. A curve that is closer to the origin represents a more efficient scheme. It means that the scheme is able to achieve the same PFT target while trading off a smaller increase in PNC.
Among the five schemes, the reactive scheme has the worst efficiency since it does not make use of any prediction. Choi's AC1 scheme has better efficiency than the reactive scheme because it possesses some intelligence of where and when the resources should be reserved. However, it has lower efficiency than the next three schemes. This is probably because it may he insufficient to predict the mobility of an MT based on its previous cell information and extant sojourn time.
Moreover, calls that are newly gen¬erated in the cell do not have previous cell infor¬mation. This hinders the scheme's prediction accuracy, thus lowering its efficiency. The LE scheme has slightly better efficiency over Choi's AC1 scheme. The RTB scheme described in this article demonstrates even greater improvement. These results show that mobility prediction schemes based on mobile positioning informa¬tion are more accurate, thus leading to more efficient reservations. The most efficient scheme among the five schemes considered is the bench¬mark scheme. As mentioned earlier, this is an idealized scheme that possesses complete knowl¬edge of when and where the next handoff of each MT will occur. It merely serves as a bound to the best efficiency that could be achieved by other schemes. For a target PFT of 1 percent, the reactive scheme has a PNC of 17.9 percent, while the lower hound set by the benchmark scheme is 15.8 percent. The RTB scheme is able to achieve a PNC of 16.5 percent.
As we have seen, the plots agree with intu¬ition that handoff prioritization efficiency improves as the amount of knowledge incorpo¬rated into the schemes increases. With the addi¬tional knowledge of real-time mobile positioning information, the LE scheme is able to outper¬form Choi's AC1 scheme, even though it is based


Figure 4. Plots of PNC vs PFT demonstrating the efficiency of different schemes.
on a simple linear extrapolation approach. For the RTB scheme, the use of both real-time mobile positioning information and road topolo¬gy knowledge further reduces the uncertainty in predicting the MTs' future movements. As a result, its performance is even closer to the limit set by the benchmark scheme.
5. CONCLUSION
In this article, we have described a mobility pre¬diction technique in which each BS performs predictions for all active MTs under its service. The technique is built on the assumption that future MTs would be equipped with reasonably accurate positioning capability.
Unlike previous attempts to perform mobility predictions based on mobile positioning, which have assumed either hexagonal or circular cell geometries, our scheme does not require any cell geometry assumption. We have also incorporated road topology information into the prediction tech¬nique, which could potentially yield better pre¬diction accuracy for MTs that are carried in vehicles.
Among the many possible applications for which mobility predictions could prove useful, this article outlines its use for dynamic resource reservation to prioritize handoff calls over new calls. With mobility prediction, the reservations at each BS could be dynamically adjusted accord¬ing to the resource demands of MTs that are anticipated to hand off into the cell from its neighboring cells.
By comparing the plots featur¬ing the trade-offs between new call blocking probability and forced termination probability obtained from several schemes, we demonstrate that reservation efficiency improves as the amount of knowledge incorporated into the scheme increases, and the RTB scheme has the potential to achieve performance closest to the limit set by the idealized benchmark scheme. The use of the RTB scheme could therefore provide
subscribers with the desired degree of call-level QoS throughout their call duration, while achieving higher resource utilization than other handoff prioritization schemes.
With the emergence of telematics systems in vehicles, motorists may receive dynamic route guidance based on real-time traffic information. It this routing information were to he made available to the wireless network; it could help to further diminish the uncertainty in mobility pre¬dictions. And realize even more efficient resource reservation schemes.

6. REFERENCE
1) Y.Zhao, Standardization of Mobile Phone Positioning for 3G Systems, IEEE Communication Magazine, July 2002, pp 108-116.
2) M.H. Chiu and M.A. Bassiouni, Predictive Schemes for Handoff Prioritization in Cellular Networks Based on Mobile Positioning, IEEE JSAC, Vol.18 No.3, March 2000, pp 510-522.
3) Y. Zhao, Vehicle Location and Navigation Systems, Chapter 4, Artech House, 1997.

CONTENTS
1. INTRODUCTION
2. ROAD-TOPOLOGY-BASED MOBILITY PREDICTION TECHNIQUE
3. HANDOFF PRIORITIZATION VIA DYNAMIC RESOURCE RESERVATION
4. SIMULATION DETAILS AND RESULTS
5. CONCLUSION
6. REFERENCE