A Lightweight Distributed Social Distance Routing Algorithm in Opportunistic Networks

Abstract

Abstract: Most of routing algorithms in the previous work used the flooding methods to obtain the auxiliary-information, which wasted network resources. Motivated by this, a distributed social distance routing algorithm was proposed. Firstly, we analyze the stability and regularity of contact between nodes to determine the friend relationship. Then, social-distance among nodes is constructed by the friend relationship. In addition, Each node maintains a table for recording the shortest social distance of other nodes, and the minimum social distance is continually updated by exchanging and comparing the information in the table. The construction of social distance only needs to exchange information among friends instead of all nodes, so it can greatly reduce the number of auxiliary-information exchange. Finally, when the packet is sent to the relay node with a smaller social distance to its destination node, the delivery-ratio can be significantly improved. The experimental results demonstrate that, compared with PRoPHET, the delivery ratio increased by about 5%, the delivery delay reduced by about 2%, and auxiliary-information exchange times reduced by about 60%. Compared with SimBet, delivery ratio in increased by about 9%, delivery delay is basically flat, auxiliary-information exchange times reduced by about 60%. This algorithm provides a theoretic support for the large scale of mobile opportunistic networks, because of the better performance in the scalability.

Key words: opportunistic network, routing protocols, friend relationship, auxiliary-information, social distance

摘要： 目前大部分机会路由算法采取洪泛的方式进行辅助信息的交换造成了网络资源浪费严重。针对此问题，提出了一种分布式社会距离路由算法。首先，通过分析节点间接触的稳定性与规律性来确定朋友关系；其次，通过朋友关系来构建节点间的社会距离；进一步地，每个节点维护一张用于记录当前已知的到其他节点的最短社会距离表，通过朋友节点之间相互交换并比较表中信息来不断更新最短社会距离。由于社会距离的构建与更新只需要朋友之间交换信息而并不需要全部节点来参与，极大地减少了辅助信息的交换次数；最后，数据包被发送到与其目的节点社会距离较近的中继节点，保证了数据包高效率地投递。实验结果表明：与PRoPHET算法相比投递率提升约5%，投递延时降低约2%，辅助信息交换次数减少约60%；与SimBet算法相比包投递率提升约9%，投递延时方面基本持平，辅助信息交换次数减少约60%。社会距离路由算法在可扩展性方面的良好表现，为移动机会网络大规模部署提供了理论支撑。

关键词: 移动机会网络, 路由协议, 朋友关系, 辅助信息, 社会距离

Peiyan Yuan Ming-Yang SONG. A Lightweight Distributed Social Distance Routing Algorithm in Opportunistic Networks[J]. .

袁培燕宋明阳. DPCS2017+18+移动机会网络中一种轻量级的分布式社会距离路由算法[J]. .

References

Yuan P, Fan L, Liu P, et al. Recent progress in routing protocols of mobile opportunistic networks[J]. Journal of Network & Computer Applications, 2016, 62(C):163-170. Vahdat A, Becker D. Epidemic Routing for Partially-Connected Ad Hoc Networks[J]. Master Thesis, 2000. 马华东, 袁培燕, 赵东. 移动机会网络路由问题研究进展[J]. 软件学报, 2015, 26(3):600-616. Lindgren A, Doria A, Schel, et al. Probabilistic routing in intermittently connected networks[J]. Acm Sigmobile Mobile Computing & Communications Review, 2004, 7(3):239-254. Li Z, Shen H. Probabilistic Routing with Multi-Copies in Delay Tolerant Networks[C]// The, International Conference on Distributed Computing Systems Workshops. IEEE, 2008:471-476. Wang X, He R, Lin B, et al. Probabilistic Routing Based on Two-Hop Information in Delay/Disruption Tolerant Networks[J]. Journal of Electrical & Computer Engineering, 2015, 2015(3):1-11. Borah S J, Dhurandher S K, Woungang I, et al. A multi-objectives based technique for optimized routing in opportunistic networks[J]. Journal of Ambient Intelligence & Humanized Computing, 2017:1-12. Yu C, Tu Z, Yao D, et al. Probabilistic routing algorithm based on contact duration and message redundancy in delay tolerant network[J]. International Journal of Communication Systems, 2016, 29(16):2416-2426. Bulut E, Szymanski B K. Exploiting Friendship Relations for Efficient Routing in Mobile Social Networks[J]. Parallel & Distributed Systems IEEE Transactions on, 2012, 23(12):2254-2265. Daly E M, Haahr M. Social network analysis for routing in disconnected delay-tolerant MANETs[C]// ACM Interational Symposium on Mobile Ad Hoc NETWORKING and Computing, MOBIHOC 2007, Montreal, Quebec, Canada, September. DBLP, 2007:32-40. Mtibaa A, May M, Diot C, et al. Peoplerank: social opportunistic forwarding[C]// Conference on Information Communications. IEEE Press, 2010:111-115. Jang K, Lee J, Kim S K, et al. An adaptive routing algorithm considering position and social similarities in an opportunistic network[J]. Wireless Networks, 2016, 22(5):1537-1551. Wu X H, Gu X F, Poslad S. Routing algorithm based on social relations in opportunistic networks[C]// International Computer Conference on Wavelet Active Media Technology and Information Processing. IEEE, 2016. Chaintreau A, Hui P, Crowcroft J, et al. Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms[C]// INFOCOM 2006. IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 23-29 April 2006, Barcelona, Catalunya, Spain. DBLP, 2006:1-13. Rhee I, Shin M, Hong S, et al. On the Levy-Walk Nature of Human Mobility[C]// INFOCOM 2008. the, Conference on Computer Communications. IEEE. IEEE Xplore, 2011:924-932.

[1]	REN Xiuli, CHEN Yang. Routing protocol optimized for data transmission delay in wireless sensor networks [J]. Journal of Computer Applications, 2020, 40(1): 196-201.
[2]	LI Anchao, CHEN Guifen. Uneven clustering protocol based on odd-even round clustering and double cluster head [J]. Journal of Computer Applications, 2018, 38(7): 1995-2000.
[3]	HE Wangji, MA Xiaoyuan, LI Xin, TANG Weisheng. Energy balancing routing protocol for low-power and lossy network [J]. Journal of Computer Applications, 2018, 38(4): 1095-1101.
[4]	LUO Yujie, ZHANG Jian, TANG Zhangguo, LI Huanzhou. Research summary of secure routing protocol for low-power and lossy networks [J]. Journal of Computer Applications, 2018, 38(12): 3462-3470.
[5]	YUAN Peiyan, SONG Mingyang. Lightweight distributed social distance routing algorithm in mobile opportunistic network [J]. Journal of Computer Applications, 2018, 38(1): 13-19.
[6]	LI Shuangshuang, YANG Wenzhong, WU Xiangqian. Routing protocol based on unequal partition area for wireless sensor network [J]. Journal of Computer Applications, 2016, 36(11): 3010-3015.
[7]	HUANG Tinghui, YI Kai, CUI Gengshen, WANG Yuliang. Hierarchical routing protocol based on non-uniform clustering for wireless sensor network [J]. Journal of Computer Applications, 2016, 36(1): 66-71.
[8]	YANG Xiaofeng, WANG Rui, PENG Li. Hybrid multi-hop routing algorithm of effective energy-hole avoidance for wireless sensor networks [J]. Journal of Computer Applications, 2015, 35(7): 1815-1819.
[9]	DING Xiaohuan, PENG Furong, WANG Qiong, LU Jianfeng. Tensor factorization recommendation algorithm combined with social network and tag information [J]. Journal of Computer Applications, 2015, 35(7): 1979-1983.
[10]	REN Xiuli, WANG Chong. Multi-path routing protocol based on three-dimensional space and regional co-evolution in wireless sensor network [J]. Journal of Computer Applications, 2015, 35(3): 610-614.
[11]	LIU Jie, WANG Ling, WANG Shan, FENG Wei, LI Wen. Minimum MPR set selection algorithm based on OLSR protocol [J]. Journal of Computer Applications, 2015, 35(2): 305-308.
[12]	PENG Yali, XU Hong, YIN Hong, ZHANG Zhiming. Routing protocol for bus vehicle network with cyclical movement [J]. Journal of Computer Applications, 2015, 35(2): 313-316.
[13]	ZHAO Zuopeng, ZHANG Nana, HOU Mengting, GAO Meng. Clustering routing algorithm based on attraction factor and hybrid transmission [J]. Journal of Computer Applications, 2015, 35(12): 3331-3335.
[14]	YUAN Peiyan, WANG Chenyang, LI Sijia. Data forwarding strategy based on gathering point in mobile opportunistic networks [J]. Journal of Computer Applications, 2015, 35(11): 3038-3042.
[15]	LIANG Yumin CAO Tianjie. Lightweight protocol with anonymity for Ad Hoc network based on bilinear pairings [J]. Journal of Computer Applications, 2013, 33(12): 3402-3405.