Modeling steady-state and transient behaviors of user mobility: formulation, analysis, and application

ABSTRACT

Recent studies on mobility modeling have focused on characterizing user mobility from real traces of wireless LANs (WLANs)and creating mobility models based on such characterization. However, most of the work does not study how user mobility is correlated in time at different time scales. For example, the future APs with which a user will be associated are predicted without the knowledge of when the association will take place and for how long. In this paper, we build a mathematical model for characterizing both steady state and transient behaviors of user mobility in WLANs. Specifically, we mode user mobility by a semi-Markov process, and obtain the transition probability matrix and the sojourn time distribution from the association history of WLAN users available at Dartmouth college [21]. With the steady-state characterization of user mobility in WLANs, we can estimate the long-term wireless network usage among different access points. By comparing the steady-state distributions of semi-Markov models built based on trace data collected at different time scales, we are able to characterize the degree of correlation in time and location.We also perform a transient behavior analysis of the semi-Markov process (that characterizes user mobility), and devise a timed location prediction algorithm that accurately predicts the future locations of users both the future access points they will associate themselves with and the association duration. We demonstrate the utility of timed location prediction, by showing how it can be utilized to predict the distribution of future user ocations with the time information figured in, and redistributing loads among neighboring APs. An improvement of 80% (in terms of load balance) is observed in a wide spectrum of traffic loads in the simulation.

REFERENCES

• 1: Anand Balachandran , Geoffrey M. Voelker , Paramvir Bahl , P. Venkat Rangan, Characterizing user behavior and network performance in a public wireless LAN, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 2: Anand Balachandran , Paramvir Bahl , Geoffrey M. Voelker, Hot-Spot Congestion Relief in Public-Area Wireless Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.70, June 20-21, 2002
• 3: Magdalena Balazinska , Paul Castro, Characterizing mobility and network usage in a corporate wireless local-area network, Proceedings of the 1st international conference on Mobile systems, applications and services, p.303-316, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066127]
• 4: D. Bhattacharjee, A. Rao, C. Shah, M. Shah, and A. Helmy. Empirical modeling of campus-wide pedestrian mobility: observations on the USC campus. In Proceedings of IEEE VTC'04 Los Angeles, CA, September 2004.
• 5: T. Camp, J. Boleng, and V. Davies. Mobility models for ad hoc network simulations. Wireless Communication and Mobile Computing 2(5):483--502,2002.
• 6: F. Chinchilla, M. Lindsey, and M. Papadopouli. Analysis of wireless information locality and association patterns in a campus. In Proceedings of IEEE INFOCOM'04 Hong Kong, China, March 2004.
• 7: Gianfranco Corradi, Jacques Janssen, and Raimondo Manca. Numerical treatment of homogeneous semi Markov processes in transient case-a straightforward approach. Methodology and Computing in Applied Probability 3:233--246, 2004.
• 8: N. Golmie. Interference in the 2.4 GHz band. In Proceedings of International Conference on Applications and Services in Wireless Networks pages 187--199, 2001.
• 9: Tristan Henderson , David Kotz , Ilya Abyzov, The changing usage of a mature campus-wide wireless network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023739]
• 10: Wei jen Hsu, Kashyap Merchant, Haw wei Shu, Chih hsin Hsu, and Ahmed Helmy. Preference based mobility model and the case for congestion relief in WLANs using Ad hoc Networks. In Proceedings of IEEE VTC'04 Los Angeles, CA, September 2004.
• 11: Ravi Jain , Anupama Shivaprasad , Dan Lelescu , Xiaoning He, Towards a model of user mobility and registration patterns, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.4, October 2004 [doi>10.1145/1052871.1052877]
• 12: Ravi Jain , Dan Lelescu , Mahadevan Balakrishnan, Model T: an empirical model for user registration patterns in a campus wireless LAN, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080848]
• 13: Amit Jardosh , Elizabeth M. Belding-Royer , Kevin C. Almeroth , Subhash Suri, Towards realistic mobility models for mobile ad hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939008]
• 14: Minkyung Kim and David Kotz. Classifying the mobility of users and the popularity of access points. In Proceedings of Int. Workshop on Location- and Context-Awareness (LoCA'05), May 2005.
• 15: Minkyong Kim , David Kotz, Modeling users' mobility among WiFi access points, Papers presented at the 2005 workshop on Wireless traffic measurements and modeling, p.19-24, June 05-05, 2005, Seattle, Washington
• 16: David Kotz , Kobby Essien, Analysis of a campus-wide wireless network, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570659]
• 17: Gerard Salton , Chris Buckley, Term Weighting Approaches in Automatic Text Retrieval, Cornell University, Ithaca, NY, 1987
• 18: Libo Song, David Kotz, Ravi Jain, and Xiaoning He. Evaluating location predictors with extensive Wi Fi mobility data. In Proceedings of IEEE INFOCOM'04 Hong Kong, China, March 2004.
• 19: Diane Tang , Mary Baker, Analysis of a local-area wireless network, Proceedings of the 6th annual international conference on Mobile computing and networking, p.1-10, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345912]
• 20: C. Tuduce and T. Gross. A mobility model based on WLAN traces and its validation. In Proceedings of IEEE INFOCOM'05 Miami, FL, March 2005.
• 21: A community resource for archiving wireless data at Dartmouth. http://crawdad.cs.dartmouth.edu/data.php
• 22: Linksys WRT54G Wireless G broadband router source codes. http://www.linksys.com/support/gpl.asp
• 23: Kismet. http://www.kismetwireless.net

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Measurement, Performance

Keywords:
WLAN, load balacing algorithm, location prediction, mobility model, semi-Markov process