Fine-grained mobility characterization: steady and transient state behaviors

ABSTRACT

Recent popularization of personal hand-held mobile devices makes it important to characterize the mobility pattern of mobile device users, so as to accurately predict user mobility in the future. Currently, the user mobility pattern is mostly characterized at a coarse-grained level, in the form of transition among wireless Access Points (APs). There is limited research effort on the fine-grained characterization of geographical user movement. In this paper, we present a novel approach to characterize the steady-state and transient-state user mobility behaviors at a fine-grained level, based on the Hidden Markov Model (HMM) formulation of user mobility. By applying our approach on both realistic mobility traces and synthetic mobility scenarios, we show that our approach is effective in characterizing user mobility pattern and making accurate mobility prediction. We also experimentally demonstrate that fine-grained user mobility knowledge is more effective to improve the performance of a variety of mobile computing applications.

References

1. }}B. An and S. Papavassiliou. A mobility-based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks. Int'l Journal of Network Management, 11(6):387--395, 2001.
2. }}M. Balazinska and P. Castro. Characterizing mobility and network usage in a corporate wireless local-area network. Proc. MobiSys, pages 303--316, 2003.
3. }}L. Baum, T. Petrie, G. Soules, and N. Weiss. A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains. The Annals of Mathematical Statistics, 41(1):164--171, 1970.
4. }}G. Box, G. M. Jenkins, and G. C. Reinsel. Time Series Analysis: Forecasting and Control. Prentice-Hall, 3rd edition, 1994.
5. }}A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39(1):1--38, 1977.
6. }}A. Ephremides, J. E. Wieselthier, and D. J. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling. In Proc. IEEE, volume 75, pages 56--73, 1987.
7. }}M. Falkhausen, H. Reininger, and D. Wolf. Calculation of distance measures between hidden markov models. Proc. Eurospeech, pages 1487--1490, 1995.
8. }}K. Fall. A delay-tolerant network architecture for challenged internets. Proc. SIGCOMM, pages 27--34, 2003.
9. }}W. Gao, Q. Li, B. Zhao, and G. Cao. Multicasting in delay tolerant networks: a social network perspective. In Proceedings of MobiHoc, pages 299--308, 2009.
10. }}T. Henderson, D. Kotz, and I. Abyzov. The changing usage of a mature campus-wide wireless network. Computer Networks, 52(14):2690--2712, 2008.
11. }}X. Hong, M. Gerla, G. Pei, and C.-C. Chiang. A group mobility model for ad-hoc wireless networks. In Proc. ACM MSWiM, 1999.
12. }}K. Langendoen and N. Reijers. Distributed localization in wireless sensor networks: a quantitative comparison. Computer Networks, 43(4):499--518, 2003.
13. }}J.-K. Lee and J. Hou. Modeling steady-state and transient behaviors of user mobility: formulation, analysis and application. In Proc. MobiHoc, 2006.
14. }}D. Lelescu, U. Kozat, R. Jain, and M. Balakrishnan. Model T++: an empirical joint space-time registration model. In Proc. MobiHoc, 2006.
15. }}B. Liang and Z. Haas. Predictive distance-based mobility management for pcs networks. In Proc. INFOCOM, 1999.
16. }}A. McDonald and T. F. Znati. A mobility-based framework for adaptive clustering in wireless ad hoc networks. IEEE Journal on Selected Areas in Communications, 17(8):1466--1487, 1999.
17. }}S. Merugu, M. Ammar, and E. Zegura. Routing in space and time in networks with predictable mobility. Technical Report, GIT-CC-04-7, Georgia Institute of Technology, 2004.
18. }}C. Neukirchen and G. Rigoll. Controlling the complexity of HMM systems by regularization. In Proceedings of Conference on Advances in Neural Information Processing Systems II, pages 735--743, 1999.
19. }}A. J. Nicholson and B. D. Noble. Breadcrumbs: forecasting mobile connectivity. In Proceedings of MobiCom, pages 46--57, 2008.
20. }}L. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings IEEE, 77(2):257--286, 1989.
21. }}I. Rhee, M. Shin, S. Hong, K. Lee, and S. Chong. On the levy-walk nature of human mobility. In Proc. INFOCOM, pages 924--932, 2008.
22. }}S. Siddiqi, G. Gordon, and A. Moore. Fast state discovery for HMM model selection and learning. In Proc. Int'l Conference on Artificial Intelligence and Statistics, 2007.
23. }}L. Song, D. Kotz, and R. Jain. Evaluating location predictors with extensive Wi-Fi mobility data. Proc. INFOCOM, 2004.
24. }}J. Zhao and G. Cao. VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks. Proc. INFOCOM, 2006.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• Networks

  • Network services

    • Network monitoring