Information dissemination dynamics in delay tolerant network: a bipartite network approach

ABSTRACT

In this paper, we present a model of a delay tolerant network(DTN) and identify that this model can be suitably reformulated as a bipartite network and that the major predictions from the former are equivalent to that of the latter. In particular, we show that the coverage of the information dissemination process in the DTN matches accurately with the size of the largest component in the suitably thresholded one-mode projection of the corresponding bipartite network. In the process of this analysis, some of the important insights gained are that (a) arbitrarily increasing the number of agents participating in the dissemination process cannot increase the coverage once the system has reached the stationary state for a given buffer time (i.e., the time for which a message resides in the buffer of the places visited by the agents), (b) the coverage varies inversely with the square of the number of places in the system and directly with the square of the average social participation of the agents and (c) it is possible to design an optimal buffer time for a desired cost of coverage. To the best of our knowledge, this is the first such work that employs the rich theoretical backbone of bipartite networks as a "proxy" for the analysis of the otherwise intractable DTN dynamics thus allowing for various novel analytical estimates.

References

1. J. Y. L. B. A. Chaintreau and N. Ristanović. The age of gossip: Spatial mean-field regime. In Proceedings of ACM Sigmetrics, 2009.
2. N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker, and M. R. Tuttle. Many random walks are faster than one. In Proceedings of SPAA, pages 119--128, 2008.
3. A. Balasubramanian, B. Levine, and A. Venkataramani. Dtn routing as a resource allocation problem. In SIGCOMM Computer Communication Review, 2007.
4. C. Bettstetter. Mobility modeling in wireless networks: categorization, smooth movement, and border effects. Sigmobile Mob. Comput. Commun. Rev., 5:55--66, July 2001.
5. J. Broch, D. A. Maltz, D. B. Johnson, Y. C. Hu, and J. Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Proceedings of MobiCom, pages 85--97, 1998.
6. T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. WCMC: Special Issue, 2:483--502, 2002.
7. O. S. Chau, P. Hui, and V. O. K. Li. An architecture enabling bluetooth^tm/jini^tm interoperability. In Proceedings of PIMRC, pages 3013--3018, 2004.
8. M. Choudhury, N. Ganguly, A. Maiti, A. Mukherjee, L. Brusch, A. Deutsch, and F. Peruani. Modeling discrete combinatorial systems as alphabetic bipartite networks: Theory and applications. Phys. Rev. E, 81:036103, 2010.
9. P. Diaconis and D. Freedman. Finite exchangeable sequences. Annals of Probability, 8(4):744--764, 1980.
10. V. V. Dimakopoulos and E. Pitoura. On the performance of flooding-based resource discovery. IEEE Trans. Parallel Distrib. Syst., 17(11):1242--1252, 2006.
11. W. Gao, Q. Li, B. Zhao, and G. Cao. Multicasting in delay tolerant networks: A social network perspective. In Proceedings of MobiHoc, 2009.
12. S. Ghosh, A. Srivastava, T. Krueger, and N. Ganguly. Degree distribution of one mode projection of evolving alpha bipartite networks. Available at http://cse.iitkgp.ac.in/resgrp/cnerg/Files/BipartiteNetwork.pdf.
13. B. Gu, X. Hong, and P. Wang. Analysis for bio-inspired thrown-box assisted message dissemination in delay tolerant networks. Telecommun Syst, Springer, 2011.
14. R. Jathar and A. Gupta. Probabilistic routing using contact sequencing in delay tolerant networks. In Proceedings of COMSNETS, 2010.
15. K. Lee, S. Hong, S. J. Kim, I. Rhee, and S. Chong. Slaw: A new mobility model for human walks. In Proceedings of INFOCOM, pages 855--863, 2009.
16. A. Mukherjee, M. Choudhury, and N. Ganguly. Understanding how both the partitions of a bipartite network affect its one-mode projection. Physica A, 390(20):3602--3607, 2011.
17. S. Nandi, L. Brusch, A. Deutsch, and N. Ganguly. Coverage-maximization in networks under resource constraints. Phys. Rev. E, 81(6):061124, Jun 2010.
18. K. Oikonomou, D. Kogias, and I. Stavrakakis. A study of information dissemination under multiple random walkers and replication mechanisms. In Proceedings of MobiOpp, pages 118--125, 2010.
19. F. Peruani, M. Choudhury, A. Mukherjee, and N. Ganguly. Emergence of a non-scaling degree distribution in bipartite networks: a numerical and analytical study. Euro. Phys. Lett., 79:28001, 2007.
20. F. Peruani, A. Maiti, S. Sadhu, H. Chaté, R. R. Choudhury, and N. Ganguly. Modeling broadcasting using omnidirectional and directional antenna in delay tolerant networks as an epidemic dynamics. IEEE-JSAC, 28(4):524, 2010.
21. A. Picu and T. Spyropoulos. Distributed stochastic optimization in opportunistic networks: The case of optimal relay selection. In Proceedings of CHANTS, 2010.
22. S. Shahbazi, S. Karunasekera, and A. Harwood. Improving performance in delay/disruption tolerant networks through passive relay points. In Wireless Network, 2011.
23. T. Small and Z. J. Haas. The shared wireless infostation model: a new ad hoc networking paradigm (or where there is a whale, there is a way). In Proceedings of MobiHoc, 2003.
24. T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility. In Proceedings of IEEE PerCom workshops, 2007.
25. Q. Yuan, I. Cardei, and J. Wu. Predict and relay: an efficient routing in disruption-tolerant networks. In Proceedings of MobiHoc, 2009.
26. W. Zhao, Y. Chen, M. Ammar, M. Corner, B. Levine, and E. Zegura. Capacity enhancement using throwboxes in dtns. In Proceedings of MASS, pages 31--40, 2006.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Network flows

• Networks

  • Network types

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows