| The location of a mobile terminal in a wireless infrastructure network is only known in terms of a cell ID. Our work investigates the efficacy and efficiency of reporting this symbolic location information for predicting future locations with high accuracy. As a good prediction calls for a good model, the problem can be reduced to profiling personal mobility patterns of user of the mobile terminal. An important clue is that a reported sequence of location data can also be conceived as an encoding of a string of IDs of cells through which a terminal moves. From this point of view, continuous “path-update” turns out to be more informative than intermittent “position-update.” A path update can easily be engineered by encoding a sequence of traditional location updates with a dictionary as in the acclaimed LZ78 compression algorithm originally proposed by Ziv and Lempel in 1978.; In this dissertation, we describe “LeZi-update,” a novel adaptive location reporting strategy designed around LZ78. While the compressibility of variable-to-fixed length encoding of LZ78 is responsible for the efficiency of LeZi-update, the predictive power comes from the symbol-wise context model preserved in the parse-tree built by the LZ78 incremental parsing. We show that for mobile users with a steady and identifiable movement pattern, LeZi-update exchanges an optimal amount of information between the mobile terminal and the wired infrastructure. Simulation studies based on synthetic movement traces show a significant reduction of cost in both location update and terminal paging, even when a user behaves like a wanderer by changing his/her movement pattern frequently. This is a promising result as far as the support of multimedia applications and location-aware services are concerned. |
