Ecole d'ingénieur et centre de recherche en Sciences du numérique

An analysis of the information spreading delay in heterogeneous mobility DTNs

Picu, Andreea; Spyropoulos, Thrasyvoulos; Hossmann, Theus

WOWMOM 2012, 13th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, June 25-28, 2012, San Francisco, California, USA

Best Paper Award

Epidemic spreading is one of the most popular bio-inspired principles, which has made its way into computer networking. This principle naturally applies to Opportunistic or Delay Tolerant Networks (DTNs), where nodes probabilistically meet their neighbors thanks to mobility. Epidemic-based algorithms are often the only choice for DTN problems such as broadcast and unicast routing, distributed estimation etc. Existing analyses of epidemic spreading in various contexts only consider specific graph geometries (complete, random, regular etc) and/or homogeneous exponential node meeting rates. In addition, in wired networks, synchronous communication is usually assumed. In this paper, we relax these assumptions and provide a detailed analysis of epidemic spreading in DTNs with heterogeneous node meeting rates. We observe the special properties of a Markov model, describing the epidemic process and use them to derive bounds for the delay (expectation and distribution). We apply our analysis to epidemic-based DTN algorithms for routing and distributed estimation and validate the bounds against simulation results, using various real and synthetic mobility scenarios. Finally, we empirically show that the delay distribution is relatively concentrated, and that, depending on graph properties (communities, scale-freeness), the delay scales very well with network size.

Document Doi Bibtex

Titre:An analysis of the information spreading delay in heterogeneous mobility DTNs
Ville:San Francisco
Département:Systèmes de Communication
Eurecom ref:3753
Copyright: © 2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+3753, doi = {}, year = {2012}, title = {{A}n analysis of the information spreading delay in heterogeneous mobility {DTN}s}, author = {{P}icu, {A}ndreea and {S}pyropoulos, {T}hrasyvoulos and {H}ossmann, {T}heus}, booktitle = {{WOWMOM} 2012, 13th {IEEE} {I}nternational {S}ymposium on a {W}orld of {W}ireless, {M}obile and {M}ultimedia {N}etworks, {J}une 25-28, 2012, {S}an {F}rancisco, {C}alifornia, {USA}}, address = {{S}an {F}rancisco, {\'{E}}{TATS}-{UNIS}}, month = {06}, url = {} }
Voir aussi: