17.4 Optimal Location Tracking and Prediction in Symbolic Space

17.4 "Optimal" Location Tracking and Prediction in Symbolic Space

In this section, we first show how LeZi-Update, ^[23], ^[24] a path-based location update mechanism, can be used to provide efficient location predicting and tracking of mobile devices in a symbolic location space. This path-based approach is asymptotically optimal and outperforms earlier location-management algorithms based on location areas (LA), because it exploits the mobility profile associated with individual users. Moreover, we can store the relevant details of the user's location history in a compact data structure, and also derive accurate predictions of the relative likelihood of future locations of the mobile device. Finally, we shall describe our ongoing work on enhancing this algorithm with an efficient location-translation capability for transferring mobility profiles across heterogeneous systems.

Most mobility management solutions employ a position update technique for location management, where the mobile device simply updates its current location (e.g., cell ID or GPS coordinates) whenever it crosses a cell boundary (or other thresholds such as time or distance). Position update schemes can be viewed as a lossy sampling of the true trajectory of the mobile object. Such position-based schemes do not, however, use these location update samples to construct or predict the user's path; in effect, the schemes do not correlate across multiple sample points to learn the "pattern of device movement." The performance of conventional paging and location update schemes thus depend heavily on the precise parameters of the user mobility model; different algorithms perform better for different mobility models. A generic location management scheme must, however, perform well, independent of the individual mobility patterns followed by different users. Such a generic model must be based on the weakest set of assumptions on the mobility behavior of individual users or devices, and must incorporate some form of learning that uses the past history of the mobile node to optimize the signaling associated with location tracking.

We assume that the user mobility is "well-behaved," in that users/devices typically move on some definitive paths that are based on the lifestyle of the mobile user. According to the activity-based model, trips are considered the basic element of a user's long-term mobility profile. Trips in both outdoor and indoor environments are categorized by the purpose behind them, such as going to and coming back from work, shopping, a walk to a colleague's cubicle, a lunch-hour visit to the cafeteria, etc. Each trip in the symbolic space then appears as a phrase of symbols. For example, if the location of a user is sampled successively, the mobility profile of a user over the graph of Figure 17.1 may be expressed by the stream of symbols "aaababbbbbaabccddcbaaaa...." From a computational standpoint, the mobility profile of any user can then be represented by a user-specific stationary distribution over the generation of the symbol stream. Because neither the lifestyle nor the stationary pattern of mobility remains the same for one person, it is more realistic to conjecture that the symbolic capture of the movement pattern of a well-behaved pervasive device is stationary or piecewise stationary. The assumption of stationarity is weak enough to accommodate a wide variety of mobility models (from random to piece-wise deterministic), yet strong enough to prove the performance of our LeZi-update location-tracking algorithm.

17.4.1 The LeZi-Update Algorithm

The LeZi-update algorithm ^[25], ^[26] is based on the observation that location update is essentially equivalent to the transmission of the generated symbol sequence. Optimizing the signaling associated with location updates is then functionally equivalent to maximally compressing the symbol stream through the use of appropriate encoding schemes. The LeZi-update algorithm is thus based on an incremental parsing and compression technique, the LZ78 algorithm, ^[27] which parses the outgoing symbol stream in a causal manner to adaptively construct the optimal transmission code.^[28],^[29]

We now briefly describe the fundamental functioning of the LeZi-update algorithm using the encoder-decoder duo shown in Figure 17.2. The encoder part, residing in the mobile terminal, intercepts any combination of primitive dynamic update (distance/movement/time-based) treating the zone-ids as input symbols. The coded update message is sent to the system (MSC/VLR for cellular systems) where the decoder resides, which on receipt of the coded update message, decodes it into the original symbol sequence and updates their relative frequencies. For example, the symbol sequence aaababbbbbaabccddcbaaaa... considered earlier, gets parsed as "a, aa, b, ab, bb, bba, abc, c, d, dc, ba, aaa, ..." by the encoder, where commas indicate the points of updates separating the updated path segments.

ENCODER	DECODER
initialize dictionary : = null initialize phrase w : = null loop wait for next symbol v if (w.v in dictionary) w : = w.v else encode <index(w),v> add w.v to dictionary w :=null endif forever	initialize dictionary : = null loop wait for next codeword <i,s> decode phrase : = dictionary [i].s add phrase to dictionary increment frequency for every prefix of phrase forever

Figure 17.2: Encoder at the mobile, decoder at the network element.

The symbol sequences (actually user path segments) can easily be maintained in a structure known as a trie (shown in Figure 17.3), which captures all the relevant history of the user in a compact form. In addition to representing the dictionary, the trie can store statistics for contexts explored, resulting in a symbol-wise model for LZ78. Using the stored frequencies, the trie can be used to predict the probability of future occupancy in the cell geometry (symbolic space). The paging operation then consists of a progressive search for the mobile node in a decreasing sequence of the occupancy probabilities. By storing individual mobility profiles, the LeZi-update algorithm adaptively learns the optimal update and paging scheme for each individual mobile node.

Figure 17.3: Trie for the classic LZ symbolwise model.

The algorithm is asymptotically optimal if the user mobility profile remains stationary. Information theory, in fact, shows the existence of a lower bound (known as the entropy rate) on the transmission rate of a stationary sequence of symbols. No lossless compression scheme can reduce the symbol stream to a lower rate; moreover, this lower bound can only be reached asymptotically (using infinitely long sequences of generated symbols). The LeZi-update algorithm, in essence the LZ78 compression scheme, can be proved to asymptotically converge to the entropy rate, as long as the mobile moves randomly according to a stationary distribution.

17.4.2 Translation of Mobility Profiles During Vertical Handoffs

The LeZi-update algorithm discussed in the previous section leads to efficient and intelligent tracking as long as the user moves within a specific symbolic space (equivalently, access technology). To predict the location attributes of a mobile node when it moves to a different access technology (e.g., when a vertical handoff occurs across access technologies), we need to translate the mobility profile from the current to the new symbolic space representation. Figure 17.1 provides an illustration of such a scenario. As long as the user moves across the LAN infrastructure, its path update and trie information are stored in the form of strings such as a1, a2, bl, cl, etc. When a vertical handoff occurs (from the LAN to the PCS network), the network needs to transfer the mobility profile it has learned after translating it to the new symbol space a, b, c, .... The new space, in general, need not directly overlap with the old space; for example, we could have al, bl, and d2 all map to a, and g2, f3, and h4 map to b.

We are currently working on such a translation mechanism, called hierarchical LeZi-update. The hierarchical algorithm is based on the observation that the entire relevant movement history of the mobile node in its original symbolic space is captured in the stored user-specific trie, Given a mapping from the old space to the new symbolic space, we should thus be able to manipulate the trie to obtain an equivalent movement history in the new symbolic space. We can then express the mobile's movement history in a new trie, which refers to the symbolic space associated with the new access infrastructure. The problem of location translation across heterogeneous symbolic location coordinates thus reduces to the construction and communication of a modified trie structure (using a mapping between the new and old coordinate systems) between heterogeneous networks.

^[23]Bhattacharya, A. and Das, S.K., LeZi-update: an information-theoretic approach to track mobile users in PCS networks, Proc. 6th Ann. ACM Int. Conference on Mobile Computing and Networking (MobiCom), pp. 1–12, Aug. 1999.

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

^[25]Bhattacharya, A. and Das, S.K., LeZi-update: an information-theoretic approach to track mobile users in PCS networks, Proc. 6th Ann. ACM Int. Conference on Mobile Computing and Networking (MobiCom), pp. 1–12, Aug. 1999.

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

^[27]Ziv, J. and Lempel, A., Compression of individual sequences via variable-rate coding, IEEE Trans. Infor. Theory, 24 (5), 530–536, 1978.

^[28]Perkins, C., IP mobility support, RFC 2002, Internet Engineering Task Force, Oct. 1996.

^[29]Satyanarayan, M., Pervasive computing: vision and challenges, IEEE Personal Commun., 8 (4), 10–17, 2001.