Colloquium

The location of a mobile terminal in a cellular PCS 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 problemcan be reduced to profiling personal mobility patterns of users of these terminals. 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" must 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.

This talk will describe "LeZi-update", an 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 originates from the symbol-wise context model preserved in the parse-tree built by LZ78 incremental parsing. 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 also a positive result as far as the support of multimedia applications and location-aware services are concerned. (Joint work with Sajal K. Das and Soumya K. Das Bhaumik)

Amiya Bhattacharya is currently a Ph.D. candidate in the Department of Computer Science and Engineering at the University of Texas at Arlington. He received his B.Tech. and M.Tech. degrees in Computer Science and Engineering from the Indian Institute of Technology, Kharagpur, and his M.S. in Computer Science from the University of California, San Diego. He has been a recipient of the TxTEC fellowship at UTA, as well as the Best Student Paper Award in ACM/IEEE MOBICOM'99. His research interests include mobile computing and communication systems, network protocol efficiency and robustness, integrated measures for performance and dependability, optimization in dynamic systems, on-line algorithms and information theory. He is a student member of IEEE, ACM and ACM SIGMOBILE.