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

Speaker: Dr. Milan Vojnovic, Microsoft Research, UK

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 power law 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 waypoint can exhibit the same dichotomy in the distribution of inter-contact times as in 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 favourite location site may already explain the observed dichotomy. Our findings suggest that existing results on the performance of forwarding schemes based on power-law tails might be overly pessimistic.


Milan Vojnovic is a researcher with systems and networking group at Microsoft Research, Cambridge, United Kingdom. His research interests are in architecture and performance of computer systems with particular interests in mobile systems, information dissemination, and usage control of network resources. He received his PhD in technical sciences from EPFL, Switzerland, in 2003, and his MSc and BSc in electrical engineering from the University of Split, Croatia, in 1998 and 1995, respectively. He undertook an internship with Math Center of Bell Laboratories, Murray Hill, New Jersey, in 2001. He received ACM Sigmetrics 05 Best Paper Award (with Laurent Massoulié) for a work on performance of file swarming systems, IEEE Infocom 05 Best Paper Award (with Jean-Yves Le Boudec) for a work on stationarity and perfect simulation of random mobility models, and ITC-17 2001 Best Student Paper Award (with Jean-Yves Le Boudec) for a work on TCP-friendliness of equation-based congestion control. In 2005, he has been awarded ERCIM Cor Baayen Award.

Presented On: March 15th, 2007
Video: QuickTime Streaming video