skip to main content
10.1145/1530748.1530790acmconferencesArticle/Chapter ViewAbstractPublication PagesmobihocConference Proceedingsconference-collections
research-article

Multicasting in delay tolerant networks: a social network perspective

Published: 18 May 2009 Publication History

Abstract

Node mobility and end-to-end disconnections in Delay Tolerant Networks (DTNs) greatly impair the effectiveness of data dissemination. Although social-based approaches can be used to address the problem, most existing solutions only focus on forwarding data to a single destination. In this paper, we are the first to study multicast in DTNs from the social network perspective. We study multicast in DTNs with single and multiple data items, investigate the essential difference between multicast and unicast in DTNs, and formulate relay selections for multicast as a unified knapsack problem by exploiting node centrality and social community structures. Extensive trace-driven simulations show that our approach has similar delivery ratio and delay to the Epidemic routing, but can significantly reduce the data forwarding cost measured by the number of relays used.

References

[1]
C. Boldrini, M. Conti, and A. Passarella. Modelling data dissemination in opportunistic networks. Proc. ACM Workshop on Challenged Networks (CHANTS), 2008.
[2]
J. Burgess, B. Gallagher, D. Jensen, and B. Levine. Maxprop: Routing for vehicle-based disruption-tolerant networks. Proc. INFOCOM, 2006.
[3]
A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of Human Mobility on Opportunistic Forwarding Algorithms. IEEE Trans. on Mobile Computing, pages 606--620, 2007.
[4]
E. Daly and M. Haahr. Social network analysis for routing in disconnected delay-tolerant MANETs. Proc. MobiHoc, 2007.
[5]
V. Erramilli, A. Chaintreau, M. Crovella, and C. Diot. Delegation Forwarding. Proc. MobiHoc, 2008.
[6]
K. Fall. A delay-tolerant network architecture for challenged internets. Proc. SIGCOMM, pages 27--34, 2003.
[7]
P. Greenwood and M. Nikulin. A Guide to Chi-Squared Testing. Wiley-Interscience, 1996.
[8]
W. Hsu and A. Helmy. On Nodal Encounter Patterns in Wireless LAN Traces. Proc. International Workshop On Wireless Network Measurement (WiNMee), 2006.
[9]
P. Hui, J. Crowcroft, and E. Yoneki. Bubble rap: social-based forwarding in delay tolerant networks. Proc. MobiHoc, pages 241--250, 2008.
[10]
P. Hui, E. Yoneki, S. Chan, and J. Crowcroft. Distributed community detection in delay tolerant networks. Proc. MobiArch, 2007.
[11]
S. Ioannidis, A. Chaintreau, and L. Massoulie. Optimal and scalable distribution of content updates over a mobile social network. Proc. INFOCOM, 2009.
[12]
U. Lee, S.-Y. Oh, K.-W. Lee, and M. Gerla. Scalable multicast routing in delay tolerant networks. Proc. ICNP, 2008.
[13]
A. Lindgren, A. Doria, and O. Schelen. Probabilistic routing in intermittently connected networks. ACM SIGMOBILE CCR, 7(3):19--20, 2003.
[14]
P. Marsden. Egocentric and sociocentric measures of network centrality. Social Networks, 24(4):407--422, 2002.
[15]
S. Martello and P. Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons.
[16]
S. Milgram. The small world problem. Psychology Today, 2(1):60--67, 1967.
[17]
M. Motani, V. Srinivasan, and P. Nuggehalli. PeopleNet: engineering a wireless virtual social network. Proc. MobiCom, pages 243--257, 2005.
[18]
G. Palla, I. Derényi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814--818, 2005.
[19]
T. Spyropoulos, K. Psounis, and C. Raghavendra. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In Proceedings of 2005 ACM SIGCOMM workshop on Delay-tolerant networking, pages 252--259, 2005.
[20]
T. Spyropoulos, K. Psounis, and C. Raghavendra. Performance analysis of mobility-assisted routing. Proc. MobiHoc, pages 49--60, 2006.
[21]
V. Srinivasan, M. Motani, and W. Ooi. Analysis and implications of student contact patterns derived from campus schedules. Proc. MobiCom, pages 86--97, 2006.
[22]
A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, 2000.
[23]
D. Watts and S. Strogatz. Collective dynamics of "small-world" networks. Nature, 393:440--442, 1998.
[24]
E. Yoneki, P. Hui, S. Chan, and J. Crowcroft. A socio-aware overlay for publish/subscribe communication in delay tolerant networks. Proc. MSWiM, pages 225--234, 2007.
[25]
W. Zhao, M. Ammar, and E. Zegura. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In Proc. MobiHoc, pages 187--198, 2004.
[26]
W. Zhao, M. Ammar, and E. Zegura. Multicasting in delay tolerant networks: semantic models and routing algorithms. Proc. SIGCOMM Workshop on Delay Tolerant Networking, pages 268--275, 2005.

Cited By

View all
  • (2024)Recommendation-Enabled Edge Caching and D2D Offloading via Incentive-Driven Deep Reinforcement LearningIEEE Transactions on Services Computing10.1109/TSC.2024.335121917:4(1724-1738)Online publication date: Jul-2024
  • (2024)A Co-occurrence Prediction Framework in Location-Based Social NetworksNew Generation Computing10.1007/s00354-024-00276-z42:5(1129-1163)Online publication date: 20-Sep-2024
  • (2022)RAIM: A Reverse Auction-Based Incentive Mechanism for Mobile Data Offloading Through Opportunistic Mobile NetworksIEEE Transactions on Network Science and Engineering10.1109/TNSE.2021.31263679:6(3909-3921)Online publication date: 1-Nov-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiHoc '09: Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing
May 2009
370 pages
ISBN:9781605586243
DOI:10.1145/1530748
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: 18 May 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. centrality
  2. community
  3. delay tolerant network
  4. multicast
  5. social network

Qualifiers

  • Research-article

Conference

MobiHoc '09
Sponsor:

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)39
  • Downloads (Last 6 weeks)1
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Recommendation-Enabled Edge Caching and D2D Offloading via Incentive-Driven Deep Reinforcement LearningIEEE Transactions on Services Computing10.1109/TSC.2024.335121917:4(1724-1738)Online publication date: Jul-2024
  • (2024)A Co-occurrence Prediction Framework in Location-Based Social NetworksNew Generation Computing10.1007/s00354-024-00276-z42:5(1129-1163)Online publication date: 20-Sep-2024
  • (2022)RAIM: A Reverse Auction-Based Incentive Mechanism for Mobile Data Offloading Through Opportunistic Mobile NetworksIEEE Transactions on Network Science and Engineering10.1109/TNSE.2021.31263679:6(3909-3921)Online publication date: 1-Nov-2022
  • (2022)Stochastic Multi-Distribution Modeling of Inter-Contact Times2022 International Conference on Information Networking (ICOIN)10.1109/ICOIN53446.2022.9687207(220-225)Online publication date: 12-Jan-2022
  • (2021)Delay Gain Analysis of Wireless Multicasting for Content DistributionIEEE/ACM Transactions on Networking10.1109/TNET.2020.303963429:2(529-542)Online publication date: Apr-2021
  • (2021)Optimal Sensing Task Distribution Algorithm for Mobile Sensor Networks With Agent Cooperation RelationshipIEEE Internet of Things Journal10.1109/JIOT.2020.30452568:10(8223-8233)Online publication date: 15-May-2021
  • (2021)Contact ability based topology control for predictable delay-tolerant networksScientific Reports10.1038/s41598-021-01864-511:1Online publication date: 19-Nov-2021
  • (2021)Enhancing mobile cloud with social-aware device-to-device offloadingComputer Communications10.1016/j.comcom.2020.12.020Online publication date: Jan-2021
  • (2021)Dueling deep Q-networks for social awareness-aided spectrum sharingComplex & Intelligent Systems10.1007/s40747-021-00382-18:3(1975-1986)Online publication date: 27-Apr-2021
  • (2021)VideoOR: A Quality Oriented Replication Scheme for Video Opportunistic TransmissionWireless Personal Communications10.1007/s11277-021-08163-2Online publication date: 15-Feb-2021
  • 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