Multicasting in delay tolerant networks: a social network perspective

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: Chiara Boldrini , Marco Conti , Andrea Passarella, Modelling data dissemination in opportunistic networks, Proceedings of the third ACM workshop on Challenged networks, September 15-15, 2008, San Francisco, California, USA [doi>10.1145/1409985.1410002]
• 2: J. Burgess, B. Gallagher, D. Jensen, and B. Levine. Maxprop: Routing for vehicle-based disruption-tolerant networks. Proc. INFOCOM, 2006.
• 3: Augustin Chaintreau , Pan Hui , Jon Crowcroft , Christophe Diot , Richard Gass , James Scott, Impact of Human Mobility on Opportunistic Forwarding Algorithms, IEEE Transactions on Mobile Computing, v.6 n.6, p.606-620, June 2007 [doi>10.1109/TMC.2007.1060]
• 4: Elizabeth M. Daly , Mads Haahr, Social network analysis for routing in disconnected delay-tolerant MANETs, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288113]
• 5: Vijay Erramilli , Mark Crovella , Augustin Chaintreau , Christophe Diot, Delegation forwarding, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374653]
• 6: Kevin Fall, A delay-tolerant network architecture for challenged internets, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863960]
• 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: Pan Hui , Jon Crowcroft , Eiko Yoneki, Bubble rap: social-based forwarding in delay tolerant networks, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374652]
• 10: Pan Hui , Eiko Yoneki , Shu Yan Chan , Jon Crowcroft, Distributed community detection in delay tolerant networks, Proceedings of 2nd ACM/IEEE international workshop on Mobility in the evolving internet architecture, August 27-30, 2007, Kyoto, Japan [doi>10.1145/1366919.1366929]
• 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: Anders Lindgren , Avri Doria , Olov Schelén, Probabilistic routing in intermittently connected networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.3, July 2003 [doi>10.1145/961268.961272]
• 14: P. Marsden. Egocentric and sociocentric measures of network centrality. Social Networks, 24(4):407--422, 2002.
• 15: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 16: S. Milgram. The small world problem. Psychology Today, 2(1):60--67, 1967.
• 17: Mehul Motani , Vikram Srinivasan , Pavan S. Nuggehalli, PeopleNet: engineering a wireless virtual social network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080855]
• 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: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.252-259, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080143]
• 20: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Performance analysis of mobility-assisted routing, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132912]
• 21: Vikram Srinivasan , Mehul Motani , Wei Tsang Ooi, Analysis and implications of student contact patterns derived from campus schedules, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161100]
• 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: Eiko Yoneki , Pan Hui , ShuYan Chan , Jon Crowcroft, A socio-aware overlay for publish/subscribe communication in delay tolerant networks, Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems, October 22-26, 2007, Chania, Crete Island, Greece [doi>10.1145/1298126.1298166]
• 25: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]
• 26: Wenrui Zhao , Mostafa Ammar , Ellen Zegura, Multicasting in delay tolerant networks: semantic models and routing algorithms, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.268-275, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080145]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms, Design, Performance

Keywords:
centrality, community, delay tolerant network, multicast, social network