Predicting the location of a user or a user's mobile device is an inherently interesting problem and one that presents many open research challenges. The explosion in mobile wireless technologies and applications over the past decade has sparked renewed interest in location prediction techniques. The advent of new access technologies such as wireless local area network (WLAN) and third-generation (3G) systems, location based services, and pervasive computing and communications indicate that location prediction will become even more important in the future.
There are two classes of applications that can benefit from accurate prediction of a user's location:
End-user applications, where the object is to predict location so that a human user can prepare or react accordingly. An example of an end-user application is one that predicts the location of a moving vehicle for road traffic optimization or for catching thieves if the vehicle is stolen.
System-enhancement applications, where location prediction can be used to enhance system performance, availability, or other metrics. An example of a system-enhancement application is one that predicts the location of a moving vehicle where a passenger is using a cell phone so as to reserve resources in adjoining cells and provide a smooth handoff.
Location can be specified in an absolute coordinate system, e.g., latitude/longitude, or in symbolic coordinates (e.g., cell ID). In some cases, both may be available. For example, a facilities administrator in an office building is likely to have a detailed map of the room layout, showing both absolute locations (in meters from some fixed origin) as well as symbolic locations (room numbers).
While in principle the same basic prediction techniques can be used for both end-user and system-enhancement applications, the constraints and metrics differ. For example, in end-user applications it may be important to know the user's geographical location, while for a system-enhancement application knowing parameters required for signaling (e.g., cell ID or paging area) is more relevant. In this chapter, we have assumed that system-enhancement applications are the target. We assume that time is discretized and a user's location is given in symbolic coordinates. The task of the location prediction algorithm is to provide the user's (symbolic) location at the next time step or, if possible, the path of the user (a sequence of locations) over several time steps. Note that the user's predicted location at the next time step may be the same as the current location.
Location prediction has been implicitly or explicitly utilized in many areas of mobile and wireless system design. For example, consider the problem of locating a cellular phone user in order to deliver a call to that user or, more specifically, to determine in which set of cells, called a location area (or registration area or paging area), the user is currently located. Broadly speaking, the strategies employed in cellular systems essentially consist of having the mobile device report its location area to a set of databases that are queried when an incoming call arrives for the user. ,  Analysis showed that these strategies placed a heavy burden on the SS7 signaling network used in the PSTN wired backbone, in particular on the Home Location Register (HLR) database in the user's home network. Early work on reducing this signaling impact used the following simple idea: the caller's switch recorded (cached) the location area at which the called party was found when the switch last queried the HLR database.  For the new call, it attempted to locate the user at that location area first, and only queried the HLR if the user was no longer found there. Essentially, the switch using this caching strategy employed a simple location prediction algorithm in order to reduce the overall signalling load in the system. As we discuss later in this chapter, this can be regarded as a type of order-1 Markov predictor where the next term in the sequence is assumed to be identical to the present term. In this example, as in other applications, in abstract terms the location prediction algorithm is worthwhile if, over the entire population of users:
where p is the probability of successful prediction, S is the benefit of success, A is the cost of running the prediction algorithm itself, and F is the cost of failure. Of course, this general relation has to be made specific and evaluated for any particular application, architecture, and prediction algorithm.
We briefly mention types of location and mobility prediction that we do not consider in this chapter. Efforts on location management and prediction for other types of mobile objects, including software objects such as agents, ,  are outside the scope of this chapter. We also do not cover efforts on predicting the amount of time that the wireless link that a mobile host is using will stay usable (e.g., Su and coworkers ), or on predicting the link quality and availability. , , 
In Section 11.2, we begin our discussion with some definitions and preliminaries. In Section 11.3, we describe location prediction algorithms that do not explicitly take advantage of the specifics of the mobile wireless environment. These algorithms generally are based on order-k Markov prediction or on the prediction capabilities inherent in text compression algorithms. In Section 11.4, we describe algorithms that have been designed for location prediction in mobile wireless environments and explicitly take advantage of their characteristics. Location prediction techniques have been developed or suggested for many domain-specific applications, including location management (e.g., see references 8 through 10, and references therein), smooth handoffs (e.g., see references 10 through 13, and references therein), resource reservations (e.g., see references 14 through 19, and references therein), call admission control (e.g., see references 20 through 25, and references therein) and adaptive resource management (e.g., see references 11 and 26, and references therein). We do not attempt to provide a comprehensive survey of all these domain-specific techniques; instead we briefly present some domain-specific algorithms that suggest slightly different approaches to the prediction problem.
All the algorithms we discuss essentially compare the sequence of recent movements the user has made to the sequence of locations H representing users' (or this particular user's) stored movement history. One way that the domain-independent algorithms discussed in Section 11.3 differ from the domain-specific algorithms discussed in Section 11.4 is in how the stored history H is partitioned into substrings for the purposes of this comparison. The order-k Markov predictors (Section 11.3.1) essentially compare the most recent k movements of the user with every length k substring in H. The LZ-based predictors (Section 11.3.2) partition H based on techniques used in text compression algorithms. In contrast, the domain-specific algorithms partition the history based on the semantics of the location prediction domain, such as considering a location as a substring delimiter if the user was stationary there a significant amount of time or if the location is at the boundary of the geographical service area.
Jain, R., Lin, Y.-B., and Mohan, S., Location strategies for personal communications services, Mobile Communications Handbook, 2nd ed., Gibson, J., Ed., CRC Press, Boca Raton, FL, 1999.
Akyildiz, I.F. et al., Mobility management for next generation wireless systems, Proc. IEEE, 87(8), 1347–1385, 1999.
Jain, R. et al., A caching strategy to reduce network impacts of PCS, IEEE J. Selected Areas Commun., 12(8), 1434–1444, 1994.
Wolfson, O. et al., Cost and imprecision in modeling the position of moving objects, Proc. IEEE Intl. Conf. Data Eng. (ICDE), Feb. 1998.
Pitoura, E. and Samaras, G., Locating objects in mobile computing, IEEE Trans. Knowledge Database Eng., 13 (4), 571–692, 2001.
Su, W., Lee, S., and Gerla, M., Mobility prediction and routing in ad hoc wireless networks, Intl. J. Net. Mgmt., (11), 3–30, 2001.
Jiang, S., He, D., and Rao, J., A prediction-based link availability estimation algorithm for mobile ad hoc networks, Proc. IEEE InfoCom, 2001.
Krishna, P., Vaidya, N., and Pradhan, D., Static and adaptive location management in mobile wireless networks, Computer Commun., 19 (4), 321–334, 1996.
Shivakumar, N., Jannink, J., and Widom, J., Per-user profile replication in mobile environments: algorithms, analysis, and simulation results, ACM/Baltzer Mobile Networks Appl. (MONET), 2 (2), 129–140, 1997.