BreadCrumbs: forecasting mobile connectivity

ABSTRACT

Mobile devices cannot rely on a single managed network, but must exploit a wide variety of connectivity options as they travel. We argue that such systems must consider the derivative of connectivity--the changes inherent in movement between separately managed networks, with widely varying capabilities. With predictive knowledge of such changes, devices can more intelligently schedule network usage.

To exploit the derivative of connectivity, we observe that people are creatures of habit; they take similar paths every day. Our system, BreadCrumbs, tracks the movement of the device's owner, and customizes a predictive mobility model for that specific user. Combined with past observations of wireless network capabilities, BreadCrumbs generates connectivity forecasts. We have built a BreadCrumbs prototype, and demonstrated its potential with several weeks of real-world usage. Our results show that these forecasts are sufficiently accurate, even with as little as one week of training, to provide improved performance with reduced power consumption for several applications.

REFERENCES

• 1: Ian F. Akyildiz , Wenye Wang, The predictive user mobility profile framework for wireless multimedia networks, IEEE/ACM Transactions on Networking (TON), v.12 n.6, p.1021-1035, December 2004 [doi>10.1109/TNET.2004.838604]
• 2: A. Aljadhai and T. Znati. Predictive mobility support for QoS provisioning in mobile wireless environments. IEEE Journal on Selected Areas in Communications, 19(10):1915--1930, October 2001.
• 3: Manish Anand , Edmund B. Nightingale , Jason Flinn, Self-tuning wireless network power management, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939004]
• 4: Amiya Bhattacharya , Sajal K. Das, LeZi-update: an information-theoretic approach to track mobile users in PCS networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.1-12, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313457]
• 5: Vladimir Bychkovsky , Bret Hull , Allen Miu , Hari Balakrishnan , Samuel Madden, A measurement study of vehicular internet access using in situ Wi-Fi networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161097]
• 6: M. Chen, T. Sohn, D. Chmelev, D. Haehnel, J. Hightower, J. Hughes, A. LaMarca, F. Potter, I. Smith, and A. Varshavsky. Practical metropolitan-scale positioning for GSM phones. In Proceedings of UbiComp, pages 225--242, September 2006.
• 7: Yu-Chung Cheng , Yatin Chawathe , Anthony LaMarca , John Krumm, Accuracy characterization for metropolitan-scale Wi-Fi localization, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067195]
• 8: Marcel Dischinger , Andreas Haeberlen , Krishna P. Gummadi , Stefan Saroiu, Characterizing residential broadband networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298313]
• 9: Dieter Fox , Jeffrey Hightower , Lin Liao , Dirk Schulz , Gaetano Borriello, Bayesian Filtering for Location Estimation, IEEE Pervasive Computing, v.2 n.3, p.24-33, July 2003 [doi>10.1109/MPRV.2003.1228524]
• 10: Joy Ghosh , Matthew J. Beal , Hung Q. Ngo , Chunming Qiao, On profiling mobility and predicting locations of wireless users, Proceedings of the 2nd international workshop on Multi-hop ad hoc networks: from theory to reality, May 26-26, 2006, Florence, Italy [doi>10.1145/1132983.1132993]
• 11: Andreas Haeberlen , Eliot Flannery , Andrew M. Ladd , Algis Rudys , Dan S. Wallach , Lydia E. Kavraki, Practical robust localization over large-scale 802.11 wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023728]
• 12: Familiar Linux. http://familiar.handhelds.org/.
• 13: Pan Hui , Augustin Chaintreau , James Scott , Richard Gass , Jon Crowcroft , Christophe Diot, Pocket switched networks and human mobility in conference environments, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.244-251, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080142]
• 14: M. Kim, D. Kotz, and S. Kim. Extracting a mobility model from real user traces. In Proceedings of INFOCOM, April 2006.
• 15: D. Kotz, T. Henderson, and I. Abyzov. CRAWDAD trace set dartmouth/campus/movement (v. 2005-03-08), Mar. 2005.
• 16: A. LaMarca, Y. Chawathe, S. Consolvo, J. Hightower, I. Smith, J. Scott, T. Sohn, J. Howard, J. Hughes, F. Potter, J. Tabert, P. Powledge, G. Borriello, and B. Schilit. Place Lab: Device positioning using radio beacons in the wild. In Procedings of Pervasive, pages 116--133, May 2005.
• 17: Ben Liang , Zygmunt J. Haas, Predictive distance-based mobility management for multidimensional PCS networks, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.718-732, October 2003 [doi>10.1109/TNET.2003.815301]
• 18: T. Liu, P. Bahl, and I. Chlamtac. Mobility modelling, location tracking, and trajectory prediction in wireless ATM networks. IEEE Journal on Selected Areas in Communications, 16(6):922--936, August 1998.
• 19: Natalia Marmasse , Chris Schmandt, A User-Centered Location Model, Personal and Ubiquitous Computing, v.6 n.5-6, p.318-321, December 2002 [doi>10.1007/s007790200035]
• 20: Vishnu Navda , Anand Prabhu Subramanian , Kannan Dhanasekaran , Andreas Timm-Giel , Samir Das, MobiSteer: using steerable beam directional antenna for vehicular network access, Proceedings of the 5th international conference on Mobile systems, applications and services, June 11-13, 2007, San Juan, Puerto Rico [doi>10.1145/1247660.1247684]
• 21: Anthony J. Nicholson , Yatin Chawathe , Mike Y. Chen , Brian D. Noble , David Wetherall, Improved access point selection, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134705]
• 22: Pubudu N. Pathirana , Andrey V. Savkin , Sanjay Jha, Mobility modelling and trajectory prediction for cellular networks with mobile base stations, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778441]
• 23: Ahmad Rahmati , Lin Zhong, Context-for-wireless: context-sensitive energy-efficient wireless data transfer, Proceedings of the 5th international conference on Mobile systems, applications and services, June 11-13, 2007, San Juan, Puerto Rico [doi>10.1145/1247660.1247681]
• 24: Adam Smith , Hari Balakrishnan , Michel Goraczko , Nissanka Priyantha, Tracking moving devices with the cricket location system, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990088]
• 25: L. Song, U. Deshpande, U. Kozat, D. Kotz, and R. Jain. Predictability of WLAN mobility and its effects on bandwidth provisioning. In Proceedings of INFOCOM, April 2006.
• 26: L. Song, D. Kotz, R. Jain, and X. He. Evaluating location predictors with extensive Wi-Fi mobility data. In Proceedings of INFOCOM, pages 1414--1424, March 2004.
• 27: J. Yoon, M. Liu, and B. Noble. Random waypoint considered harmful. In Proceedings of INFOCOM, pages 1312--1321, March 2003.
• 28: Jungkeun Yoon , Brian D. Noble , Mingyan Liu , Minkyong Kim, Building realistic mobility models from coarse-grained traces, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134699]
• 29: F. Yu and V. Leung. Mobility-based predictive call admission control and bandwidth reservation in wireless cellular networks. In Proceedings of INFOCOM, pages 518--526, April 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Human Factors, Management, Measurement

Keywords:
BreadCrumbs, connectivity forecast, derivative of connectivity, opportunistic connectivity