research-article

The diameter of opportunistic mobile networks

Authors:

Augustin Chaintreau,

Abderrahmen Mtibaa,

Laurent Massoulie,

Christophe DiotAuthors Info & Claims

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

Article No.: 12, Pages 1 - 12

https://doi.org/10.1145/1364654.1364670

Published: 10 December 2007 Publication History

Abstract

Portable devices have more data storage and increasing communication capabilities everyday. In addition to classic infrastructure based communication, these devices can exploit human mobility and opportunistic contacts to communicate. We analyze the characteristics of such opportunistic forwarding paths. We establish that opportunistic mobile networks in general are characterized by a small diameter, a destination device is reachable using only a small number of relays under tight delay constraint. This property is first demonstrated analytically on a family of mobile networks which follow a random graph process. We then establish a similar result empirically with four data sets capturing human mobility, using a new methodology to efficiently compute all the paths that impact the diameter of an opportunistic mobile networks. We complete our analysis of network diameter by studying the impact of intensity of contact rate and contact duration. This work is, to our knowledge, the first validation that the so called "small world" phenomenon applies very generally to opportunistic networking between mobile nodes.

References

[1]

B. Bui-Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science, 14(2):267--285, 2003.

[2]

A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, J. Scott, and R. Gass. Impact of human mobility on opportunistic forwarding algorithms. IEEE Trans. Mob. Comp., 6(6):606--620, 2007.

Digital Library

[3]

A. Chaintreau, A. Mtibaa, L. Massoulié, and C. Diot. The diameter of opportunistic mobile networks. Technical Report CR-PRL-2007-07-0001, Thomson, 2007. www.thlab.net/tr/CR-PRL-2007-07-0001.pdf.

Digital Library

[4]

N. Eagle and A. Pentland. Reality mining: Sensing complex social systems. Journal of Personal and Ubiquitous Computing, 10(4):255--268, 2005.

Digital Library

[5]

M. Grossglauser and D. Tse. Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Trans. on Net., 10(4):477--486, 2002.

Digital Library

[6]

T. Henderson, D. Kotz, and I. Abyzov. The changing usage of a mature campus-wide wireless network. In Proceedings of ACM MobiCom, 2004.

Digital Library

[7]

S. Jain, K. Fall, and R. Patra. Routing in a delay tolerant network. In Proceedings of ACM SIGCOMM, 2004.

Digital Library

[8]

S. Janson, T. Luczak, and A. Ruciński. Random Graphs. John Wiley & Sons, 2000.

[9]

T. Karagiannis, J.-Y. Le Boudec, and M. Vojnovic. Power law and exponential decay of inter contact times between mobile devices. In Proceedings of ACM MobiCom, 2007.

Digital Library

[10]

D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. In Proceedings of ACM STOC, 2000.

Digital Library

[11]

J. Kleinberg. The small-world phenomenon: An algorithmic perspective. In Proceedings of ACM STOC, 2000.

Digital Library

[12]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceeding of ACM SIGKDD, 2005.

Digital Library

[13]

M. McNett and G. M. Voelker. Access and mobility of wireless PDA users. SIGMOBILE Mob. Comput. Commun. Rev., 7(4):55--57, 2003.

Digital Library

[14]

E. Nordström, C. Diot, R. Gass, and P. Gunningberg. Experiences from measuring human mobility using bluetooth inquiring devices. In Proceedings of Workshop ACM MobiEval, 2007.

Digital Library

[15]

A. Orda and R. Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM, 37(3):607--625, 1990.

Digital Library

[16]

M. Papadopouli and H. Schulzrinne. Seven degrees of separation in mobile ad hoc networks. In Proceedings of IEEE GLOBECOM, 2000.

[17]

V. Srinivasan, M. Motani, and W. Tsang Ooi. Analysis and implications of student contact patterns derived from campus schedules. In Proceedings of ACM MobiCom, 2006.

Digital Library

[18]

X. Zhang, J. Kurose, B. N. Levine, D. Towsley, and H. Zhang. Study of a bus-based disruption tolerant network: Mobility modeling and impact on routing. In Proceedings of ACM MobiCom, 2007.

Digital Library

[19]

W. Zhao, M. Ammar, and E. Zegura. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In Proceedings of ACM MobiHoc, 2004.

Digital Library

Cited By

Altaweel AAslam SKamel I(2024)Security attacks in Opportunistic Mobile Networks: A systematic literature reviewJournal of Network and Computer Applications10.1016/j.jnca.2023.103782221(103782)Online publication date: Jan-2024
https://doi.org/10.1016/j.jnca.2023.103782
Al-Shammari MHaque ARahman M(2023)Static Evaluation of a Midimew Connected Torus Network for Next Generation SupercomputersSustainability10.3390/su1508676615:8(6766)Online publication date: 17-Apr-2023
https://doi.org/10.3390/su15086766
Oettershagen LKriege NMutzel PSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)A Higher-Order Temporal H-Index for Evolving NetworksProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599242(1770-1782)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599242
Show More Cited By

Recommendations

Mobility-based opportunistic routing for mobile ad-hoc networks
PE-WASUN '14: Proceedings of the 11th ACM symposium on Performance evaluation of wireless ad hoc, sensor, & ubiquitous networks

Opportunistic Routing (OR) is an effective and enhanced routing scheme for wireless multihop environment. OR is an approach which selects a certain number of best forwarders (candidates) at each hop by taking the advantage of the broadcast nature of the ...
Mobile Opportunistic Networks: Architectures, Protocols and Applications
An Opportunistic Routing Protocol for Mobile Ad Hoc Networks Based on Stable Ideology

In mobile ad hoc networks (MANETs), traditional routing protocols send packets along pre-determined paths which are vulnerable in dealing with unreliable and unpredictable wireless medium. The main difference between the opportunistic routing and the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '07: Proceedings of the 2007 ACM CoNEXT conference

December 2007

448 pages

ISBN:9781595937704

DOI:10.1145/1364654

General Chairs:
Jim Kurose
University of Massachusetts
,
Henning Schulzrinne
Columbia University

Copyright © 2007 ACM.

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

Alcatel-Lucent
SIGCOMM: ACM Special Interest Group on Data Communication
Thomson
CISCO
IMDEA
IBM: IBM

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 December 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

133
Total Citations
View Citations
823
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)2

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Altaweel AAslam SKamel I(2024)Security attacks in Opportunistic Mobile Networks: A systematic literature reviewJournal of Network and Computer Applications10.1016/j.jnca.2023.103782221(103782)Online publication date: Jan-2024
https://doi.org/10.1016/j.jnca.2023.103782
Al-Shammari MHaque ARahman M(2023)Static Evaluation of a Midimew Connected Torus Network for Next Generation SupercomputersSustainability10.3390/su1508676615:8(6766)Online publication date: 17-Apr-2023
https://doi.org/10.3390/su15086766
Oettershagen LKriege NMutzel PSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)A Higher-Order Temporal H-Index for Evolving NetworksProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599242(1770-1782)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599242
Lan TShao LZhang HYuan C(2023)The impact of pandemic on dynamic volatility spillover network of international stock marketsEmpirical Economics10.1007/s00181-023-02422-w65:5(2115-2144)Online publication date: 24-Apr-2023
https://doi.org/10.1007/s00181-023-02422-w
Oettershagen LMutzel P(2022)TGLib: An Open-Source Library for Temporal Graph Analysis2022 IEEE International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW58026.2022.00160(1240-1245)Online publication date: Nov-2022
https://doi.org/10.1109/ICDMW58026.2022.00160
Casteigts ARaskin MRenken MZamaraev V(2022)Sharp Thresholds in Random Simple Temporal Graphs2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00040(319-326)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00040
Ali MRahman MIbrahim AAl-Naeem MHossain E(2022)A High Static Performance Hierarchical Three-Dimensional Shifted Completely Connected NetworkIEEE Access10.1109/ACCESS.2022.316872810(43812-43836)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3168728
Ali MRahman MIbrahim AInoguchi YHossain E(2021)The Static Performance Effect of Hybrid- Hierarchical Interconnection by Shifted Completely Connected NetworkIEEE Access10.1109/ACCESS.2021.30951469(99249-99265)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3095146
Costantino GMaiti RMartinelli FSanti P(2020)LoSeRO: A Locality Sensitive Routing Protocol in Opportunistic Networks with Contact ProfilesIEEE Transactions on Mobile Computing10.1109/TMC.2019.292322419:10(2392-2408)Online publication date: 1-Oct-2020
https://doi.org/10.1109/TMC.2019.2923224
Kui XSamanta AZhu XZhang SLi YHui P(2018)Energy-Aware Temporal Reachability Graphs for Time-Varying Mobile Opportunistic NetworksIEEE Transactions on Vehicular Technology10.1109/TVT.2018.285483267:10(9831-9844)Online publication date: Oct-2018
https://doi.org/10.1109/TVT.2018.2854832
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten