The Usefulness and Complexity of Learning Subscriber's Movement Patterns

Over the past few years, much discussions and debates haves fathomed among the researchers and technologists, over the specifics of the next generation wireless communication technology as well as its role in the evolution of the information technology of the future. A careful look at these discussions reveals that there are essentially two common demands posed on the wireless service that are universally agreed upon. First, the wireless service of the next generation must evolve into an information service that is convergent of multiple media such as voice, video and loss-sensitive data. Second, the subscribers need to be provided with ubiquitous seamless connectivity, so far as this service is concerned. To elaborate, today's voice-centric wireless service must retain and likely enhance the current quality of voice; and in addition, should at least provide standard Internet services (web, email, file transfer and remote login) and real-time/streaming video capability.

The fact that the so called "anytime anywhere" accessibility should apply to all the services offered by the provider, poses a new kind of demand on the location management system. The objective of the location management problem in the current voice-centric wireless network has been the optimization of the combined registration and paging costs, for a successfully call delivery. Knowledge of the subscriber's current cell or location area (a designated cluster of cells) is sufficient for that purpose. On the other hand, it would be quite useful to have good capability of predicting individual subscriber's movement, on the part of a wireless infrastructure designed to support the mobile information technology of the future. One reason behind this conjecture is the need for bandwidth reservation to support end-to-end quality of service (QoS) guarantee for multimedia traffic. Irrespective of whether the reservation is hard or soft state based, it would be extremely wasteful to follow a conservative reservation scheme with highly mobile terminals. Considering the scarcity of wireless bandwidth, this even may not be affordable at all. A highly predictive reservation scheme that learns subscriber's movement profile seems to be a more reasonable alternative. Another need for building movement profile may arise from some sort of locator services that can be augmented with wireless data service. The most convenient service access location for a mobile user is not necessarily the closest one, -- it could be the one on the way to current destination. The location management database can intelligently guess the possible direction and immediate destination for the ongoing movement.

We have earlier proposed a novel location update scheme for today's cellular architecture which possesses the capability of learning the movement profiles of individual subscribers. Naturally, it is also capable of using the learned profile to make good prediction about the subscriber's next move, -- at least to the extent possible from an information-theoretic perspective. Moreover, it is quite a simple matter to build group movement profiles by easy aggregation of such individual's movement database. In fact, this technique uses a well known principle of computational learning that treats the learning problem as a data compression problem. Designed around the acclaimed Lempel-Ziv LZ78 universal compressor-decompressor duo, this scheme has been named as the LeZi-update algorithm. Simply said, it uses the learning capability of a data compression algorithm because a good compressor must always be a good learner and predictor, to be able to compress the data well. However, to achieve the power of a universal predictor, the LeZi-update scheme must use path-based update messages as opposed to the traditional position-based (cell or location area) messages.

Being the derivative of a universal predictor, LeZi-update possesses a highly desirable characteristic -- it imposes very weak assumption as far as the mobility model of individuals. Given that the movement profile of a user is stationary, the scheme is asymptotically optimal no matter what. The real-life interpretation to this is that the scheme would be able to track the movement profile of a subscriber, as long as he/she has a definitive stationary pattern of movement. This is true for most of us because our lifestyle and habitual behavior dictate these patterns. In reality, however, movement profile may still change from one stationary pattern to another due to major change in lifestyle, such as a change of job or residential neighborhood. In this paper, we attempt to reflect this reality by making the mobility model even weaker -- from stationary to piecewise stationary. By analysis and simulation, we would establish that the LeZi-update technique performs very well under this almost model-independent scenario. As a result this scheme shows potential to be considered as a prime candidate for mobility support in next-generation wireless networks.

People

• Amiya Bhattacharya
• Abhishek Roy