Information Spreading in Opportunistic Networks is Fast
Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Giovanni Resta, Paolo Santi, Riccardo Silvestri · arXiv (Cornell University) · 2011
Performance bounds for opportunistic networks have been derived in a number of recent papers for several key quantities, such as the expected delivery time of a unicast message, or the ooding time, i.e., the time needed to deliver a message to all nodes in the network. However, to the best of our knowledge, none of the existing results is based on \realistic mobility models, where \realistic refers to a mobility model which is able to accurately reproduce the power law+exponential tail dichotomy of the pairwise node inter-meeting time distribution which has been observed in several real world traces. The contributions of this paper are three-fold: rst, we present a simple link model { called the Home-MEG model { for opportunistic networks based on the notion of a home location derived in previous works, and we show through extensive comparison with realworld traces that the Home-MEG model is \realistic. Second, we use the Home-MEG model to analyze ooding time in opportunistic networks, presenting two upper bounds on ooding time that assume dierent initial conditions for the existence of opportunistic links. Finally, we show that our bounds improve existing ones exponentially, revealing that ooding time in opportunistic networks can be much faster than that predicted by existing bounds based on less realistic mobility models.