skip to main content
10.1145/1287853.1287875acmconferencesArticle/Chapter ViewAbstractPublication PagesmobicomConference Proceedingsconference-collections
Article

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

Published: 09 September 2007 Publication History

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]
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.
[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]
N. Eagle and A. Pentland. Reality mining: Sensing complex social systems. In Journal of Personal and Ubiquitous Computing, 2005.
[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]
M. Grossglauser and D. Tse. Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Trans. on Networking, 10(4):477--486, 2002.
[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]
M. McNett and G. M. Voelker. Access and mobility of wireless pda users. In Mobile Computing Communications Review, 2005.
[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.

Cited By

View all
  • (2024)Maximized Content Offloading for Content Centric V2G Networks2024 IEEE 21st Consumer Communications & Networking Conference (CCNC)10.1109/CCNC51664.2024.10454759(318-323)Online publication date: 6-Jan-2024
  • (2023)Generalization-Aware Optimal Mixture Models of Inter-Contact Times for the Internet of Vehicles2023 International Conference on Ubiquitous Communication (Ucom)10.1109/Ucom59132.2023.10257592(389-396)Online publication date: 7-Jul-2023
  • (2023)SparkACO: A Spark-Based Ant Colony Optimization for Path Planning of Large-Scale Complex Road Networks2023 IEEE Ninth International Conference on Big Data Computing Service and Applications (BigDataService)10.1109/BigDataService58306.2023.00038(173-180)Online publication date: Jul-2023
  • Show More Cited By

Index Terms

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

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      MobiCom '07: Proceedings of the 13th annual ACM international conference on Mobile computing and networking
      September 2007
      370 pages
      ISBN:9781595936813
      DOI:10.1145/1287853
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 09 September 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. inter-contact time
      2. mobile devices
      3. opportunistic communications

      Qualifiers

      • Article

      Conference

      MobiCom/MobiHoc '07
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 440 of 2,972 submissions, 15%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)40
      • Downloads (Last 6 weeks)6
      Reflects downloads up to 15 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Maximized Content Offloading for Content Centric V2G Networks2024 IEEE 21st Consumer Communications & Networking Conference (CCNC)10.1109/CCNC51664.2024.10454759(318-323)Online publication date: 6-Jan-2024
      • (2023)Generalization-Aware Optimal Mixture Models of Inter-Contact Times for the Internet of Vehicles2023 International Conference on Ubiquitous Communication (Ucom)10.1109/Ucom59132.2023.10257592(389-396)Online publication date: 7-Jul-2023
      • (2023)SparkACO: A Spark-Based Ant Colony Optimization for Path Planning of Large-Scale Complex Road Networks2023 IEEE Ninth International Conference on Big Data Computing Service and Applications (BigDataService)10.1109/BigDataService58306.2023.00038(173-180)Online publication date: Jul-2023
      • (2023)Mobility of Opportunistic NetworksOpportunistic Networks10.1007/978-3-031-47866-6_1(3-19)Online publication date: 16-Nov-2023
      • (2021)Integrating Social Networks with Mobile Device-to-Device ServicesIEEE Transactions on Services Computing10.1109/TSC.2018.286743714:4(1209-1223)Online publication date: 1-Jul-2021
      • (2020)Modeling and Optimization of Mobility-Aware Dynamic Caching With Time-Varying Content PopularityIEEE Transactions on Vehicular Technology10.1109/TVT.2019.295173769:1(1157-1162)Online publication date: Jan-2020
      • (2019)Energy-Efficient Runtime Management of Heterogeneous Multicores using Online ProjectionACM Transactions on Architecture and Code Optimization10.1145/329344615:4(1-26)Online publication date: 8-Jan-2019
      • (2019)Cluster Aware Mobility Encounter Dataset Enlargement2019 15th International Wireless Communications & Mobile Computing Conference (IWCMC)10.1109/IWCMC.2019.8766720(1918-1922)Online publication date: Jun-2019
      • (2019)Epidemic Routing Performance in DTN With Selfish NodesIEEE Access10.1109/ACCESS.2019.29166857(65560-65568)Online publication date: 2019
      • (2019)On modeling and impact of geographic restrictions for human mobility in opportunistic networksPerformance Evaluation10.1016/j.peva.2018.12.002130(17-31)Online publication date: Apr-2019
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media