GRID SEARCH ALGORITHM FOR FINDING TWO-HOP ROUTING POLICIES IN DELAY TOLERANT NETWORKS

  • Divyansh Verma
Keywords: Delay tolerant networks, Social-aware routing, connection strength metric, social graph, community, bridge node.

Abstract

Social-based routing protocols has shown its promising capability for improving the message delivery efficiency in Delay Tolerant Networks (DTNs). The efficiency relies mostly on the quality of the aggregated social graph that has been determined by the metrics used for measuring the strength of social connections. In this paper, we have proposed an improved metrics that leads to the high-quality social graph by taking both frequency and duration of the contacts into its consideration. Furthermore, to improve the performance of the social-based message transmission, we have systematically studied the community evolution
problem that has been little bit investigated in the literature. Distributed algorithms based upon our new proposed metrics have been developed in such a manner that the overlapping communities and bridge nodes (i.e., connecting nodes between communities) can be dynamically detected in the evolutionary social network. Finally, we have taken all the results above into our social-based routing design. The extensive trace-driven simulation results have
shown that our routing algorithm outperforms in the existing social-based forwarding strategies significantly.

Downloads

Download data is not yet available.

Author Biography

Divyansh Verma

Department of Computer Science Engineering, SRM University, Ramapuram, Chennai – 89.

References

[1] E. Altman, G. Neglia, F. De Pellegrini, and D. Miorandi, ―Decentralized stochastic control of delay tolerant networks,‖ in Proc. of INFOCOM, Rio de Janeiro, Brazil, 19-25 April 2009.

[2] F. D. Pellegrini, E. Altman, and T. Basar, ―Optimal monotone forwarding policies in delay tolerant mobile ad hoc networks with multiple classes of nodes,‖ in WiOpt, 2010, pp. 497–504.

[3] A. Ker¨anen, J. Ott, and T. K¨arkk¨ainen, ―The one simulator for dtn protocol evaluation,‖ in SIMUTOOLS, 2009, p. 55.

[4] T. Spyropoulos, T. Turletti, and K. Obraczka, ―Routing in delaytolerant networks comprising heterogeneous node populations,‖ Mobile Computing, IEEE Transactions on, vol. 8, pp. 1132 –1147, August 2009.

[5] S. Jain, K. Fall, and R. Patra, ―Routing in a delay tolerant network,‖ in ACM SIGCOMM, 2004, pp. 145–158.

[6] A. A. Hanbali, P. Nain, and E. Altman, ―Performance of ad hoc networks with two-hop relay routing and limited packet lifetime,‖ in Proc. Of Valuetools. New York NY USA: ACM, 2006, p. 49.

[7] F. P. W. Chahin, R. El-Azouzi and A. P. Azad, ―Blind online optimal forwarding in heterogeneous delay tolerant networks,‖ in Proc. of IFIP Wireless Days, Niagara Falls, Ontario, Canada, October 10-12 2011.

[8] H. Jun, M. Ammar, and E. Zegura, ―Power management in delay tolerant networks: a framework and knowledge-based mechanisms,‖ in IEEE Sensor and Ad Hoc Communications and Networks, september 2005.

[9] A. E. Fawal, J.-Y. L. Boudec, and K. Salamatian, ―Performance analysis of self limiting epidemic forwarding,‖ EPFL, Tech. Rep. LCA-REPORT-2006-127, 2006.

[10] A. Krifa, C. Barakat, and T. Spyropoulos, ―Optimal buffer management policies for delay tolerant networks,‖ in Proc. of IEEE SECON, 2008.

[11] G. Neglia and X. Zhang, ―Optimal delay-power tradeoff in sparse delay tolerant networks: a preliminary study,‖ in Proc. of ACM SIGCOMM CHANTS 2006, 2006.

[12] A. A. Hanbali, P. Nain, and E. Altman, ―Performance of ad hoc networks with two-hop relay routing and limited packet lifetime,‖ in Proc. Of Valuetools.
NewYork,NY,USA:ACM,2006,p.49.

[13] B. J. Choi and X. Shen, ―Adaptive asynchronous clock based power saving protocols for delay tolerant networks,‖ in Proceedings of the 28th IEEE conference on Global telecommunications, ser. GLOBECOM’09, 2009, pp. 3146–151.

[14] J. Kim, J. Shin, D. Yang, and C. Kim, ―Energy optimal epidemic routing for delay tolerant networks,‖ IEICE Transactions on Communications, vol. E92.B, no. 12, pp. 3927– 3930, 2009.

[15] Y. Li, Y. Jiang, D. Jin, L. Su, L. Zeng, and D. Wu, ―Energy-efficient optimal opportunistic forwarding for delay-tolerant networks,‖ Vehicular Technology, IEEE
Transactions on, vol. 59, no. 9, pp. 4500 –4512, nov.2010.
Published
2017-03-27
Section
Articles