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.
- J.-Y. L. Boudec and M. Vojnović. The Random Trip Model: Stability, Stationary Regime, and Perfect Simulation. IEEE/ACM Trans. on Networking, 14(6):1153--1166, Dec 2006. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- E. Cinlar. Introduction to Stochastic Processes. Prentice Hall, 1 edition, 1975.Google Scholar
- N. Eagle and A. Pentland. CRAWDAD data set mit/reality (v. 2005-07-01), July 2005.Google Scholar
- N. Eagle and A. Pentland. Reality mining: Sensing complex social systems. In Journal of Personal and Ubiquitous Computing, 2005. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- M. Grossglauser and D. Tse. Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Trans. on Networking, 10(4):477--486, 2002. Google ScholarDigital Library
- Intelligent Transportation Systems Standards Program. Dedicated Short Range Communications, April 2003. http://www.standards.its.dot.gov/Documents/advisories/dsrc_advisory.htm.Google Scholar
- D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing. 1996.Google Scholar
- 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.Google ScholarDigital Library
- J. Krumm and E. Horvitz. The Microsoft Multiperson Location Survey, August 2005. Microsoft Research Technical Report, MSR-TR-2005-13.Google Scholar
- N. F. Maxemchuk. Routing in the Manhattan Street Network. In IEEE Trans. on Comm., volume 35, pages 503--512, 1987.Google ScholarCross Ref
- M. McNett and G. M. Voelker. Access and mobility of wireless pda users. In Mobile Computing Communications Review, 2005. Google ScholarDigital Library
- J. Scott, R. Gass, J. Crowcroft, P. Hui, C. Diot, and A. Chaintreau. CRAWDAD data set cambridge/haggle (v. 2006-01-31), Jan. 2006.Google Scholar
- 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.Google Scholar
- E. Seneta. Non-Negative Matrices. Wiley and Sons, 1 ed., 1973.Google Scholar
- 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.Google Scholar
- F. Spitzer. Principles of Random Walk, Graduate Texts in Mathematics. Springer, 2nd edition, 1964.Google Scholar
- 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.Google ScholarCross Ref
Index Terms
- Power law and exponential decay of inter contact times between mobile devices
Recommendations
Power Law and Exponential Decay of Intercontact Times between Mobile Devices
We examine the fundamental properties that determine the basic performance metrics for opportunistic communications. We first consider the distribution of intercontact times between mobile devices. Using a diverse set of measured mobility traces, we ...
A survey of message diffusion protocols in mobile ad hoc networks
ValueTools '08: Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and ToolsFor the last twenty years, mobile communications have experienced an explosive growth. In particular, one area of mobile communication, the Mobile Ad hoc Networks (MANETs), has attracted significant attention due to its multiple applications and its ...
Recognizing exponential inter-contact time in VANETs
INFOCOM'10: Proceedings of the 29th conference on Information communicationsInter-contact time between moving vehicles is one of the key metrics in vehicular ad hoc networks (VANETs) and central to forwarding algorithms and the end-to-end delay. Due to prohibitive costs, little work has conducted experimental study on inter-...
Comments