A socio-aware overlay for publish/subscribe communication in delay tolerant networks

ABSTRACT

The emergence of Delay Tolerant Networks (DTNs) has culminated in a new generation of wireless networking. We focus on a type of human-to-human communication in DTNs, where human behaviour exhibits the characteristics of networks by forming a community. We show the characteristics of such networks from extensive study of real-world human connectivity traces. We exploit distributed community detection from the trace and propose a Socio-Aware Overlay over detected communities for publish/subscribe communication. Centrality nodes have the best visibility to the other nodes in the network. We create an overlay with such centrality nodes from communities. Distributed community detection operates when nodes (i.e. devices) are in contact by gossipping, and subscription propagation is performed along with this operation. We validate our message dissemination algorithms for publish/subscribe with connectivity traces.

REFERENCES

• 1: R. Baldoni, R. Beraldi, G. Cugola, M. Migliavacca, and L. Querzoni. Structure-less content-based routing in mobile ad hoc networks. In Proc. ICPS, 2005.
• 2: S. Berkowitz. An Introduction to structured analysis: The network approach to social research. Butteworth, 1982.
• 3: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 4: A. Chaintreau et al. Impact of human mobility on the design of opportunistic forwarding algorithms. In Proc. INFOCOM, 2006.
• 5: A. Chaintresu, P. Hui, J. Crowcroft, et al. Pocket switched networks: Real-world mobility and its consequences for opportunistic forwarding. Technical Report UCAM-CL-TR617, Univ. of Cambridge, 2005.
• 6: A. Clauset. Finding local community structure in networks. Physical Review E, 72:026132, 2005.
• 7: Paolo Costa , Matteo Migliavacca , Gian Pietro Picco , Gianpaolo Cugola, Epidemic Algorithms for Reliable Content-Based Publish-Subscribe: An Evaluation, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.552-561, March 24-26, 2004
• 8: L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas. Comparing community structure identification, 2005.
• 9: Dartmouth College. Metrosense project, http://metrosense.cs.dartmouth.edu, 2006.
• 10: Dartmouth College. A community resource for archiving wireless data at dartmouth, http://crawdad.cs.dartmouth.edu/index.php, 2007.
• 11: C. Diot et al. Haggle Project, http://www.haggleproject.org,2004.
• 12: Nathan Eagle , Alex (Sandy) Pentland, Reality mining: sensing complex social systems, Personal and Ubiquitous Computing, v.10 n.4, p.255-268, March 2006 [doi>10.1007/s00779-005-0046-3]
• 13: Z. J. Haas, J. Halpern, and L. Li. Gossip-based ad-hoc routing. In Proc. IEEE INFOCOM, 2002.
• 14: L. H. Hartwell, J. J. Hopfield, S. Leibler, and A. W. Murray. From molecular to modular cell biology. Nature, 402(6761 Suppl), December 1999.
• 15: Tristan Henderson , David Kotz , Ilya Abyzov, The changing usage of a mature campus-wide wireless network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023739]
• 16: Yongqiang Huang , Hector Garcia-Molina, Publish/Subscribe in a mobile enviroment, Proceedings of the 2nd ACM international workshop on Data engineering for wireless and mobile access, p.27-34, May 2001, Santa Barbara, California, United States [doi>10.1145/376868.376889]
• 17: P. Hui and J. Crowcroft. Bubble rap: Forwarding in small world dtns in every decreasing circles. Technical Report UCAM-CL-TR684, Univ. of Cambridge, 2007.
• 18: Pan Hui , Jon Crowcroft, How Small Labels Create Big Improvements, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, p.65-70, March 19-23, 2007 [doi>10.1109/PERCOMW.2007.55]
• 19: P. Hui et al. Pocket switched networks and human mobility in conference environments. In WDTN, 2005.
• 20: Pan Hui , Eiko Yoneki , Shu Yan Chan , Jon Crowcroft, Distributed community detection in delay tolerant networks, Proceedings of first ACM/IEEE international workshop on Mobility in the evolving internet architecture, August 27-30, 2007, Kyoto, Japan [doi>10.1145/1366919.1366929]
• 21: IETF. Delay Tolerant Network Research Group (DTNRG). http://www.dtnrg.org, 2004.
• 22: M. E. J. Newman. Analysis of weighted networks. Physical Review E, 70:056131, 2004.
• 23: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 24: S.-J. Lee et al. A performance comparison study of ad hoc wireless multicast protocols. In Proc. IEEE INFOCOM, pages 565--574, 2000.
• 25: Jérémie Leguay , Anders Lindgren , James Scott , Timur Friedman , Jon Crowcroft, Opportunistic content distribution in an urban setting, Proceedings of the 2006 SIGCOMM workshop on Challenged networks, p.205-212, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162654.1162657]
• 26: A. Lindgren, A. Doria, and O. Schelen. Probabilistic routing in intermittently connected networks. In Proc. SAPIR, 2004.
• 27: M. Newman. Detecting community structure in networks. Eur. Phys. J. B, 38:321--330, 2004.
• 28: T. Nicolai, E. Yoneki, N. Behrens, and H. Kenn. Exploring social context with the wireless rope. In Proc. Workshop MONET: LNCS 4277, 2006.
• 29: E. Nordstrom, C. Diot, R. Gass, and P. Gunningberg. Experiences from measuring human mobility using bluetooth inquiring devices. In Proc. MobiEval, 2007.
• 30: E. O'Neill et al. Instrumenting the city: Developing methods for observing and understanding the digital cityscape. In UbiComp, pages 315--332, 2006.
• 31: G. Palla et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814--818, 2005.
• 32: P. Jaccard. Bulletin de la Societe Vaudoise des Sciences Naturelles, 37:547, 1901.
• 33: UCLA. Urban sensing project, http://research.cens.ucla.edu/, 2006.
• 34: UCSD. Wireless topology discovery project, http://sysnet.ucsd.edu/wtd/wtd.html, 2004.
• 35: S. Wasserman and K. Faust. Social network analysis: Method and applications. Cambridge University Press, 1994.
• 36: E. Yoneki and J. Bacon. An adaptive approach to content-based subscription in mobile ad hoc networks. In Proc. MP2P, 2004.
• 37: E. Yoneki and J. Bacon. Distributed multicast grouping for publish/subscribe over mobile ad hoc networks. In IEEE Wireless Communications and Networking Conference (WCNC), 2005.
• 38: Eiko Yoneki , Pan Hui , Jon Crowcroft, Visualizing community detection in opportunistic networks, Proceedings of the second workshop on Challenged networks CHANTS, September 14-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1287791.1287810]
• 39: Z. Zhang. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges. IEEE Comm. Surveys, 8:547, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
connectivity modeling and analysis, delay tolerant networks, network measurement, pervasive computing, social networks