11.4 Domain-Specific Heuristics

11.4 Domain-Specific Heuristics

In this section, we discuss several location prediction algorithms that have been proposed for specific application domains.

11.4.1 Mobile Motion Prediction (MMP)

Liu and Maguire ^[53] present a location prediction algorithm that can be used for improving mobility management in a cellular network. The movement of a user is modeled as a process {M(a,t) : a ∈ A, t ∈ T}, where A is the set of possible locations (called states) and T is an index set indicating time. It is assumed that the user's movement is composed of a regular movement process {S(a,t)} and a random movement process {X(a,t)}.

A location is called a stationary state if the user resides there longer than some threshold time interval, and a transitional state otherwise. A location at the geographical boundary of the service area is called a boundary state. For convenience we call the stationary and boundary states marker states. Two types of movement patterns are then defined. A movement circle (MC) is a sequence of locations that begins and ends with the same location and contains at least one marker state. A movement track (MT) is a sequence of locations that begins and ends with a marker state. It is possible for an MC to be an MT and vice versa. It is assumed that the regular movement process {S(a,t)} consists only of the MC process {MC(a,t)} and the MT process {MT(a,t)}. The random movement process is further assumed to be a pure (i.e., order-1) Markov process.

The mobile motion prediction (MMP) algorithm consists of a regularity detection algorithm (RDA) that builds up a database of MC and MT seen for each user over time, and a motion prediction algorithm (MPA) that uses this database. Although the details of these algorithms are not clearly specified, it appears that MPA operates as follows (for convenience we describe the algorithm using MTs, although the process for MCs is similar). Suppose the most-recent k - l locations of the mobile's history are the sequence L = l₁l₂...l_k-1, i.e., L is the suffix of H of length k - 1. Suppose there exists an MT stored in the database, C = c₀...c_n, where c₀ and c_n are marker states. Using a matching algorithm (described later), suppose L matches C; we call C a candidate MT. If the current location of the mobile l_k equals that predicted by C, then C continues as the candidate MT and MPA uses it for prediction (as described later). Otherwise, MPA uses the matching algorithm on the sequence L = l_il_i+1...l_k-1l_k, where l_i is the most recent marker state in L, to find a new MT candidate D.

The matching algorithm uses three matching heuristics. The first is called state matching and computes a state matching index μ indicating the degree of similarity in the locations of the mobile's actual itinerary compared to the candidate MT. Using the notation above, for the itinerary L, let m, 0 < m < k, be the number of locations that appear in both L and C. Then μ = m/(k - 1), and higher values indicate a better match. The second heuristic is time matching and computes an index η indicating the degree of similarity in the residence times of the mobile in each location for the mobile's itinerary compared to the candidate MT. Let r_i be the time the mobile spends at each location l_i in L, and similarly s_i be the residence time for location c_i in C. Then and lower values indicate a better match. The third heuristic is frequency matching and computes an index Φ comparing F' and F, where F' is how often the mobile's itinerary appears in a given time period, and F is how often the candidate MT appears over the time period in the database. (Unfortunately, only approximation equations and an example are given for F' and F, so this heuristic is quite unclear.) Then Φ = |(F'/F) - 1| and lower values indicate a better match. The matching algorithm applies the three matching heuristics in sequence, so that the final prediction is dependent on μ, η, and Φ.

(11.7)

Note that in MMP any itinerary that cannot be classified based on the stored MT and MC is assumed to be a random movement. The MMP algorithm is not clearly specified and lacks a theoretical foundation but does contain interesting ideas in terms of classifying location types (stationary and boundary states), as well as movement patterns (MC, MT) and different matching heuristics applied in sequence. Because it was one of the first attempts at location prediction for mobility management, it is often referenced.

11.4.2 Segment Matching

Chan et al. ^[54] use a simplification of the Liu and Maguire algorithm, which they call the segment criterion algorithm. Like Liu and Maguire's stationary states, they define stationary cells based on the residence time of the user in the cell. They then partition the individual user's history into segments, where a segment is a sequence of cells that starts with a stationary cell and ends with the same or different stationary cell. Thus a segment is similar to an MT in Liu and Maguire except that it applies only to stationary cells; there is no concept of boundary cells.

The prediction algorithm begins constructing a segment as the user moves, i.e., the user's itinerary after k moves is L = l₁l₂...l_k, where l₁ is a stationary cell. L is compared with the user's stored segments. A match is found if l_i = c_i, 1 ≤ i ≤ k ≤ n, for some stored candidate segment C = c₁c₂...c_n. In that case, the prediction is the cell c_k+1. If there are multiple candidates, then the prediction is the most frequently occurring cell in position k + 1 among the candidate segments.

Chan et al. ^[55] use two heuristics for overcoming the limitations of relying on the individual user's history. The first heuristic attempts to compensate for sudden changes in movement behavior as follows. The last ten predictions are compared with the user's actual itinerary; a higher weight is assigned to the latest movement of the user if six of the predictions were incorrect, and this weight is decreased gradually if predictions come inside a preset criterion of success. (The weight, the way in which it is decreased, and the criterion are not specified.) The second heuristic attempts to compensate for users who do not have a movement history, and uses the aggregate history over all users instead. These heuristics are used also for Chan et al.'s Markov prediction schemes (see Section 11.3.1), as well as the probabilistic scheme (Section 11.3.3).

11.4.3 Hierarchical Location Prediction (HLP)

Liu et al. ^[56] have developed a two-level prediction scheme intended for use in mobility management in a wireless ATM environment, but with wider applicability. The lower level uses a local mobility model (LMM), which is a stochastic model for intracell movements, while the top level uses a deterministic model (the global mobility model, or GMM) dealing with intercell movements. The two-level scheme is depicted in Figure 11.3 and summarized below.

Figure 11.3: Hierarchical location prediction process. (Source— Liu, T., Bahl, P., and Chlamtac, I., Mobility modeling, location tracking, and trajectory prediction in wireless ATM networks, IEEE J. Sel. Areas Commun., 16 (6), 922–936, 1998.)

The local prediction algorithm is intended only for predicting the next cell that the user will visit, while the global prediction can predict the future path. The local prediction algorithm uses consecutive radio signal strength indication (RSSI) measurements and applies a modified Kalman filtering algorithm to estimate the dynamic state of a moving user, where the dynamic state consists of the position, velocity, and acceleration of the user. When the user is "close" to a cell boundary, (i.e., in an area called a correlation area defined precisely using the geometry of hexagonal cells), the estimated dynamic state is used to determine cell-crossing probability for each neighboring cell, and the cell with the highest crossing probability is output as the predicted next cell. This prediction is used as input to the global prediction algorithm.

As in the Liu and Maguire MMP algorithm, the global prediction algorithm relies on a number of user mobility patterns (UMP) recorded for each user. The user's itinerary so far, along with the next cell predicted by the local prediction algorithm, is compared to these stored UMPs and an edit distance is generated, which is based on the smallest number of cell insertion, cell deletion, and cell ID modification operations required to make the itinerary identical to a UMP. If the edit distance is less than a threshold value, the UMP with the smallest edit distance is found using a dynamic programming method; this UMP is assumed to be the candidate UMP and to indicate the general direction of user movement. The remaining portion of the candidate UMP is output as the predicted path for the user.

Liu et al. ^[57] show by simulation that their scheme has a better prediction accuracy than MMP for mobility patterns with a moderate or high degree of randomness.

It is also worth noting that unlike the MMP algorithm the accuracy of next cell prediction using the local prediction algorithm is based purely on RSSI measurements and is independent of the long-term movement patterns of the mobile. This local prediction can be used to improve the path prediction as depicted in Figure 11.4. Next cell prediction can help choose between two candidate UMPs when the user's itinerary (shown by the shaded cells) is equidistant in terms of edit distance from them.

Figure 11.4: Benefit of local prediction for selecting a candidate UMP. (Source— Liu, T., Bahl, P., and Chlamtac, I., Mobility modeling, location tracking, and trajectory prediction in wireless ATM networks, IEEE J. Sel. Areas Commun., 16 (6), 922–936, 1998.)

11.4.4 Other Approaches

One approach we have not considered so far is to take the help of the user for prediction. Obviously, as little burden as possible should be placed on the user, but one could envision a situation where the user is only prompted for current destination (which could be collected, for example, via a voice prompt) and this is used (possibly along with history information) to do cell and path prediction. Another variation could be that at the start of the day, the user is prompted for a list of the day's likely destinations (or is approximately inferred from her calendar), so that interaction is minimized further. Madi et al. ^[58] have developed schemes for prompting for user destination input in this way, although no prediction is carried out as such.

Biesterfeld et al. ^[59] propose using neural networks for location prediction. They have considered both feedback and feed-forward networks with a variety of learning algorithms. Their preliminary results indicated, somewhat nonintuitively, that feedforward networks delivered better results than feedback networks.

Das and Sen ^[60] consider how to use location prediction to assign cells to location areas so as to minimize mobility management cost (i.e., the combined paging and location update cost), where the location areas are arranged hierarchically. The assignment is dynamic and is calculated periodically, every τ seconds. The user's movement history is assumed only to consist of a set, L_c = {(l_i, f_i) : 0 ≤ i ≤ c}, recording the frequency f_i with which each cell l_i is visited during the previous period, where c is the number of distinct cells visited.

Then the probability of the user visiting a given cell l_i is calculated simply as the relative frequency with which the user has visited that cell in the previous period, i.e., . (Similarly, frequencies for visiting areas where two or more cells overlap are recorded, and the probability of visiting the overlapping area calculated.) We observe that this scheme is similar to order-0 Markov prediction, as described in Bhattacharya and Das. ^[61]

These cell visit probabilities are used to assign cells to a most-probable location area (MPLA). However, it is possible that the user has left this area and moved to an adjoining area, called the future probable location area (FPLA). If the user is not found in the MPLA, the FPLA is paged. The cells belonging to the FPLA are determined based on the current mean velocity, the last cell visited, and (optionally) the direction of future movement. Given the cells in the FPLA, the probability that the user will visit a particular cell is estimated by a heuristic that takes into account the total number of cell crossings , the frequency max_if_i, and c, the number of distinct cells visited.

^[53]Liu, G. and Maguire, G. Jr., A class of mobile motion prediction algorithms for wireless mobile computing and communications, ACM/Baltzer Mobile Networks Appl. (MONET), 1 (2), 113–121, 1996.

^[54]Chan, J., Zhou, S., and Seneviratne, A., A QoS adaptive mobility prediction scheme for wireless networks, Proc. IEEE Globecom, Sydney, Australia, Nov. 1998.

^[55]Chan, J., Zhou, S., and Seneviratne, A., A QoS adaptive mobility prediction scheme for wireless networks, Proc. IEEE Globecom, Sydney, Australia, Nov. 1998.

^[56]Liu, T., Bahl, P., and Chlamtac, I., Mobility modeling, location tracking, and trajectory prediction in wireless ATM networks, IEEE J. Selected Areas Commun., 16 (6), 922–936, 1998.

^[57]Liu, T., Bahl, P., and Chlamtac, I., Mobility modeling, location tracking, and trajectory prediction in wireless ATM networks, IEEE J. Selected Areas Commun., 16 (6), 922–936, 1998.

^[58]Madi, M., Graham, P., and Barker, K., Mobile computing: predictive connection management with user input, Technical report, Department of. Computer Science, University of Manitoba, Aug. 1996.

^[59]Biesterfeld, J., Ennigrou, E., and Jobmann, K., Location prediction in mobile networks with neural networks, Proc. Intl. Workshop Appl. Neural Networks to Telecom., June 1997, pp. 207–214.

^[60]Das, S.K. and Sen, S.K., Adaptive location prediction strategies based on a hierarchical network model in a cellular mobile environment, Computer J., 42 (6), 473–486, 1999.

^[61]Bhattacharya, A. and Das, S.K., LeZi-update: an information-theoretic framework for personal mobility tracking in PCS networks, ACM/Kluwer Wireless Networks, 8 (2–3), 121–135, 2002.