Journal Home > Volume 24 , Issue 1

The lack of continuous connectivity and a complete path from source to destination makes node communication quite difficult in Delay-Tolerant Networks (DTNs). Most studies focus on routing problems in idealized network environments without considering social properties. Communication devices are carried by individuals in many DTNs; therefore, DTNs are unique social networks to some extent. To design efficient routing protocols for DTNs, it is important to analyze their social properties. In this paper, a more accurate and comprehensive metric for detecting the quality of the relationships between nodes is proposed, by considering the contact time, contact frequency, and contact regularity. An overlapping hierarchical community detection method is designed based on this new metric, and a tree structure is built. Furthermore, we exploit the overlapping community structure and the tree structure to provide message-forwarding paths from the source node to the destination node. The simulation results show that our Routing method based on Overlapping hierarchical Community Detection (ROCD) achieves better delivery rate than SimBet and Bubble Rap, the classic routing protocols, without affecting the average delay.


menu
Abstract
Full text
Outline
About this article

A Novel Routing Method for Social Delay-Tolerant Networks

Show Author's information Xiangyu MengGaochao XuTingting GuoYongjian YangWenxu ShenKuo Zhao( )
Department of Computer Science and Technology, Jilin University, Changchun 130012, China.
Department of Software Engineering, Jilin University, Changchun 130012, China.
Training Department, Aviation University of Air Force, Changchun 130012, China.

Abstract

The lack of continuous connectivity and a complete path from source to destination makes node communication quite difficult in Delay-Tolerant Networks (DTNs). Most studies focus on routing problems in idealized network environments without considering social properties. Communication devices are carried by individuals in many DTNs; therefore, DTNs are unique social networks to some extent. To design efficient routing protocols for DTNs, it is important to analyze their social properties. In this paper, a more accurate and comprehensive metric for detecting the quality of the relationships between nodes is proposed, by considering the contact time, contact frequency, and contact regularity. An overlapping hierarchical community detection method is designed based on this new metric, and a tree structure is built. Furthermore, we exploit the overlapping community structure and the tree structure to provide message-forwarding paths from the source node to the destination node. The simulation results show that our Routing method based on Overlapping hierarchical Community Detection (ROCD) achieves better delivery rate than SimBet and Bubble Rap, the classic routing protocols, without affecting the average delay.

Keywords: overlapping community, Delay-Tolerant Network (DTN), social properties, hierarchical routing

References(28)

[1]
Kayastha N., Niyato D., Wang P., and Hossain E., Applications, architectures, and protocol design issues for mobile social networks: A survey, Proc. IEEE, vol. 99, no. 12, pp. 2130-2158, 2011.
[2]
Li J., Cai Z., Yan M., and Li Y., Using crowdsourced data in location-based social networks to explore influence maximization, in Proc. of IEEE INFOCOM, San Francisco, CA, USA, 2016.
[3]
Wang E., Yang Y., Wu J., Liu W., and Wang X., An efficient prediction-based user recruitment for mobile crowdsensing, IEEE Transactions on Mobile Computing, vol. 17, no. 1, pp. 16-28, 2018.
[4]
Xiao M., Wu J., Huang H., Huang L., and Hu C., Deadlinesensitive user recruitment for mobile crowdsensing with probabilistic collaboration, in Proc. of IEEE ICDCS, Singapore, 2016.
DOI
[5]
Xie J. R., Kelley S., and Szymanski B. K., Overlapping community detection in networks: The state-of-the-art and comparative study, ACM Comput. Surv., vol. 45, no. 4, p. 43, 2013.
[6]
Vahdat A. and Becker D., Epidemic routing for partially connected ad hoc networks, Technical Report CS-200006, Duke University, Durham, NC, USA, 2000.
[7]
Spyropoulos T., Psounis K., and Raghavendra C. S., Spray and wait: An efficient routing scheme for intermittently connected mobile networks, in Proc. 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking, Philadelphia, PA, USA, 2005, pp. 252-259.
DOI
[8]
Spyropoulos T., Psounis K., and Raghavendra C. S., Efficient routing in intermittently connected mobile networks: The single-copy case, IEEE/ACM Trans. Network., vol. 16, no. 1, pp. 63-76, 2008.
[9]
Guo Z., Wang B., and Cui J. H., Prediction assisted single-copy routing in underwater delay tolerant networks, in Proc. 2010 IEEE Global Telecommunications Conf. (GLOBECOM 2010), Miami, FL, USA, 2010.
DOI
[10]
Wang Y., Jain S., Martonosi M., and Fall K., Erasure-coding based routing for opportunistic networks, in Proc. 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking, Philadelphia, PA, USA, 2005, pp. 229-236.
DOI
[11]
Liao Y., Tan K., Zhang Z. S., and Gao L. X., Estimation based erasure-coding routing in delay tolerant networks, in Proc. 2006 Int. Conf. Wireless Communications and Mobile Computing, Vancouver, Canada, 2006, pp. 557-562.
DOI
[12]
Gao W., Cao G. H., La Porta T., and Han J. W., On exploiting transient social contact patterns for data forwarding in delay-tolerant networks, IEEE Trans. Mobile Comput., vol. 12, no. 1, pp. 151-165, 2013.
[13]
Wei K. M., Liang X., and Xu K., A survey of social-aware routing protocols in delay tolerant networks: Applications, taxonomy, and design-related issues, IEEE Commun. Surv. Tutor., vol. 16, no. 1, pp. 556-578, 2014.
[14]
Wei K. M., Zeng D. Z., Guo S., and Xu K., On social delay-tolerant networking: Aggregation, tie detection, and routing, IEEE Trans. Parall. Distrib. Syst., vol. 25, no. 6, pp. 1563-1573, 2014.
[15]
Wang Q. and Haas Z. J., Performance Analysis of Epidemic Routing for Delay-Tolerant Networks, Modeling and Optimization in Science and Technologies. Springer, 2014.
DOI
[16]
Daly E. M. and Haahr M., Social network analysis for routing in disconnected delay-tolerant MANETs, in Proc. 8th ACM Int. Symp. Mobile ad hoc Networking and Computing, Montreal, Canada, 2007, pp. 32-40.
DOI
[17]
Hui P., Crowcroft J., and Yoneki E., Bubble rap: Social-based forwarding in delay-tolerant networks, IEEE Trans. Mobile Comput., vol. 10, no. 11, pp. 1576-1589, 2011.
[18]
Bulut E. and Szymanski B. K., Friendship based routing in delay tolerant mobile social networks, in Proc. 2010 IEEE Global Telecommunications Conf. (GLOBECOM 2010), Miami, FL, USA, 2010.
DOI
[19]
Hui P., Yoneki E., Chan S. Y., and Crowcroft J., Distributed community detection in delay tolerant networks, in Proc. 2nd ACM/IEEE Int. Workshop on Mobility in the Evolving Internet Architecture, Kyoto, Japan, 2007.
DOI
[20]
Zhu Y., Xu B., Shi X. H., and Wang Y., A survey of social-based routing in delay tolerant networks: Positive and negative social effects, IEEE Commun. Surv. Tutor., vol. 15, no. 1, pp. 387-401, 2013.
[21]
Li F. and Wu J., LocalCom: A community-based epidemic forwarding scheme in disruption-tolerant networks, in Proc. 2009 6th Ann. IEEE Communications Society Conf. Sensor, Mesh and Ad Hoc Communications and Networks, Rome, Italy, 2009, pp. 1-9.
DOI
[22]
Mei A., Morabito G., Santi P., and Stefa J., Social-aware stateless routing in pocket switched networks, IEEE Trans. Parall. Distrib. Syst., vol. 26, no. 1, pp. 252-261, 2015.
[23]
Rasul K., Chowdhury S. A., Makaroff D., and Stanley K., Community-based forwarding for low-capacity pocket switched networks, in Proc. 17th ACM Int. Conf. Modeling, Analysis and Simulation of Wireless and Mobile Systems, Montreal, Canada, 2014, pp. 249-257.
DOI
[24]
Michael C. A., Ashenafi S., Ogbuanu I. U., Ohuabunwo C., Sule A., Corkum M., Mackay S., Storms A. D., Achari P., Biya O., et al., An evaluation of community perspectives and contributing factors to missed children during an oral polio vaccination campaign–Katsina State, Nigeria, J. Infect. Dis., vol. 210, no. 1, pp. 131-135, 2014.
[25]
Xiao B. M., Liao J. Y., and Huang M. X., Network evolution of transactional community: A different network closure mechanism from social network, in Proc. Thirteenth Wuhan Int. Conf. E-Business—Human Behavior and Social Impacts on E-Business, Wuhan,China, 2014.
[26]
Keränen A., Opportunistic network environment simulator, Special Assignment Report, Helsinki University of Technology, Helsinki, Finland, 2008.
[27]
Guo T. T. and Yang Y. J., Community based routing in social delay tolerant networks, in Proc. 9th Int. Conf. Frontier of Computer Science & Technology, Dalian, China, 2015, pp. 321-324.
DOI
[28]
Fu D. L. and Peng X. G., TPM-based remote attestation for wireless sensor networks, Tsinghua Sci. Technol., vol. 21, no. 3, pp. 312-321, 2016.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 09 May 2017
Accepted: 19 June 2017
Published: 08 November 2018
Issue date: February 2019

Copyright

© The author(s) 2019

Acknowledgements

This work was supported by the Youth Sci-Tech innovation leader and team project of Jilin Province of China (No. 20170519017JH), the National Science-Technology Support Project (No. 2014BAH02F02), and the Graduate Innovation Fund of Jilin University (No. 2016031).

Rights and permissions

Return