Power law and exponential decay of inter contact times between mobile devices

ABSTRACT

We examine the fundamental properties that determine the basic performance metrics for opportunistic communications. We first consider the distribution of inter-contact times between mobile devices. Using a diverse set of measured mobility traces, we find as an invariant property that there is a characteristic time, order of half a day, beyond which the distribution decays exponentially. Up to this value, the distribution in many cases follows a power law, as shown in recent work. This powerlaw finding was previously used to support the hypothesis that inter-contact time has a power law tail, and that common mobility models are not adequate. However, we observe that the time scale of interest for opportunistic forwarding may be of the same order as the characteristic time, and thus the exponential tail is important. We further show that already simple models such as random walk and random way point can exhibit the same dichotomy in the distribution of inter-contact time ascin empirical traces. Finally, we perform an extensive analysis of several properties of human mobility patterns across several dimensions, and we present empirical evidence that the return time of a mobile device to its favorite location site may already explain the observed dichotomy. Our findings suggest that existing results on the performance of forwarding schemes basedon power-law tails might be overly pessimistic.

REFERENCES

• 1: Jean-Yves Le Boudec , Milan Vojnovic, The random trip model: stability, stationary regime, and perfect simulation, IEEE/ACM Transactions on Networking (TON), v.14 n.6, p.1153-1166, December 2006 [doi>10.1109/TNET.2006.886311]
• 2: A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms. In INFOCOM, 2006.
• 3: E. Cinlar. Introduction to Stochastic Processes. Prentice Hall, 1 edition, 1975.
• 4: N. Eagle and A. Pentland. CRAWDAD data set mit/reality (v. 2005-07-01), July 2005.
• 5: Nathan Eagle , Alex (Sandy) Pentland, Reality mining: sensing complex social systems, Personal and Ubiquitous Computing, v.10 n.4, p.255-268, March 2006 [doi>10.1007/s00779-005-0046-3]
• 6: A. E. Gamal, J. Mammen, B. Prabhakar, and D. Shah. Optimal Throughput-delay Scaling in Wireless Networks - Part I: The Fluid Model. IEEE Trans. on Information Theory, 52(6):2568--2592, June 2006.
• 7: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 8: Intelligent Transportation Systems Standards Program. Dedicated Short Range Communications, April 2003. http://www.standards.its.dot.gov/Documents/advisories/dsrc_advisory.htm.
• 9: D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing. 1996.
• 10: T. Karagiannis, J.-Y. L. Boudec, and M. Vojnovic. Power law and exponential decay of inter contact times between mobile devices. Technical Report MSR-TR-2007-24, Microsoft Research, March 2007.
• 11: J. Krumm and E. Horvitz. The Microsoft Multiperson Location Survey, August 2005. Microsoft Research Technical Report, MSR-TR-2005-13.
• 12: N. F. Maxemchuk. Routing in the Manhattan Street Network. In IEEE Trans. on Comm., volume 35, pages 503--512, 1987.
• 13: Marvin McNett , Geoffrey M. Voelker, Access and mobility of wireless PDA users, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.2, April 2005 [doi>10.1145/1072989.1072995]
• 14: J. Scott, R. Gass, J. Crowcroft, P. Hui, C. Diot, and A. Chaintreau. CRAWDAD data set cambridge/haggle (v. 2006-01-31), Jan. 2006.
• 15: J. Scott, R. Gass, J. Crowcroft, P. Hui, C. Diot, and A. Chaintreau. CRAWDAD trace cambridge/haggle/imote/infocom (v. 2006-01-31), Jan. 2006.
• 16: E. Seneta. Non-Negative Matrices. Wiley and Sons, 1 ed., 1973.
• 17: G. Sharma and R. R. Mazumdar. Delay and Capacity Trade-off in Wireless Ad Hoc Networks with Random Waypoint Mobility, 2005. Preprint, School of ECE, Purdue University, 2005.
• 18: F. Spitzer. Principles of Random Walk, Graduate Texts in Mathematics. Springer, 2nd edition, 1964.
• 19: W. Zhao, Y. Chen, M. Ammar, M. D. Corner, B. N. Levine, and E. Zegura. Capacity Enhancement using Throwboxes in DTNs. In Proc. IEEE Intl Conf on Mobile Ad hoc and Sensor Systems (MASS), Oct 2006.

INDEX TERMS

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

General Terms:
Algorithms, Design, Human Factors, Measurement

Keywords:
inter-contact time, mobile devices, opportunistic communications