Bubble rap: social-based forwarding in delay tolerant networks

ABSTRACT

In this paper we seek to improve our understanding of human mobility in terms of social structures, and to use these structures in the design of forwarding algorithms for Pocket Switched Networks (PSNs). Taking human mobility traces from the real world, we discover that human interaction is heterogeneous both in terms of hubs (popular individuals) and groups or communities. We propose a social based forwarding algorithm, BUBBLE, which is shown empirically to improve the forwarding efficiency significantly compared to oblivious forwarding schemes and to PROPHET algorithm. We also show how this algorithm can be implemented in a distributed way, which demonstrates that it is applicable in the decentralised environment of PSNs.

References

1. V. D. Blondel and P. V. Dooren. A measure of similarity between graph vertices: Applications to synonym extraction and web searching. SIAM Rev., 46(4):647--666, July 2004.
2. A. Chaintreau, P. Hui, et al. Impact of human mobility on the design of opportunistic forwarding algorithms. In Proc. INFOCOM, April 2006.
3. E. Daly and M. Haahr. Social network analysis for routing in disconnected delay-tolerant manets. In Proceedings of ACM MobiHoc, 2007.
4. L. Danon, J. Duch, et al. Comparing community structure identification. J. Stat. Mech., page P09008, Oct 2005.
5. N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing, V10(4):255--268, May 2006.
6. K. Fall. A delay-tolerant network architecture for challenged internets. In Proc. SIGCOMM, 2003.
7. G. W. Flake, S. Lawrence, et al. Self-organization of the web and identification of communities. IEEE Computer, 35(3):66--71, 2002.
8. L. C. Freeman. A set of measuring centrality based on betweenness. Sociometry, 40:35--41, 1977.
9. L. H. Hartwell, J. J. Hopfield, et al. From molecular to modular cell biology. Nature, 402(6761 Suppl), December 1999.
10. P. Hui, A. Chaintreau, et al. Pocket switched networks and human mobility in conference environments. In Proc. WDTN, 2005.
11. P. Hui and J. Crowcroft. How small labels create big improvements. In Proc. IEEE ICMAN, March 2007.
12. P. Hui, E. Yoneki, et al. Distributed community detection in delay tolerant networks. In Sigcomm Workshop MobiArch '07, August 2007.
13. P. Jaccard. Bulletin de la Societe Vaudoise des Sciences Naturelles, 37:547, 1901.
14. E. P. C. Jones, L. Li, and P. A. S. Ward. Practical routing in delay-tolerant networks. In Proc. WDTN, 2005.
15. D. Kempe et al. Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci., 64(4):820--842, 2002.
16. J. Lebrun, C.-N. Chuah, et al. Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks. IEEE VTC, 4:2289--2293, 2005.
17. J. Leguay, T. Friedman, et al. Evaluating mobility pattern space routing for DTNs. In Proc. INFOCOM, 2006.
18. J. Leguay, A. Lindgren, et al. Opportunistic content distribution in an urban setting. In ACM CHANTS, pages 205--212, 2006.
19. A. Lindgren, A. Doria, et al. Probabilistic routing in intermittently connected networks. In Proc. SAPIR, 2004.
20. D. Lusseau and M. E. J. Newman. Identifying the role that individual animals play in their social network. PROC.R.SOC.LONDON B, 271:S477, 2004.
21. A. Mislove, K. P. Gummadi, and P. Druschel. Exploiting social networks for internet search. In Proceedings of the 5th Workshop on Hot Topics in Networks (HotNets'06), November 2006.
22. M. Musolesi, S. Hailes, et al. Adaptive routing for intermittently connected mobile ad hoc networks. In Proc. WOWMOM, 2005.
23. M. P. N. Sarafijanovic-Djukic and M. Grossglauser. Island hopping: Efficient mobility-assisted forwarding in partitioned networks. In IEEE SECON, 2006.
24. M. E. J. Newman. Analysis of weighted networks. Physical Review E, 70:056131, 2004.
25. M. E. J. Newman. Detecting community structure in networks. Eur. Phys. J. B, 38:321--330, 2004.
26. M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69, February 2004.
27. S. Okasha. Altruism, group selection and correlated interaction. British Journal for the Philosophy of Science, 56(4):703--725, December 2005.
28. G. Palla, I. Derenyi, et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814--818, 2005.
29. T. Spyropoulos, K. Psounis, et al. Spray and wait: An efficient routing scheme for intermittently connected mobile networks. In Proc. WDTN, 2005.
30. A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, April 2000.
31. P. Winters. Forecasting sales by exponentially weighted moving averages. Management Science, 6:324--342, 1960.
32. E. Yoneki, P. Hui, S. Chan, and J. Crowcroft. A socio-aware overlay for multi-point asynchronous communication in delay tolerant networks. In Proc. MSWiM, 2007.
33. W. Zhao, M. Ammar, et al. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In Proc. of ACM MOBIHOC, 2004.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Computing methodologies

  • Modeling and simulation

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles