计算机科学 ›› 2021, Vol. 48 ›› Issue (3): 289-294.doi: 10.11896/jsjkx.200200097

• 计算机网络 • 上一篇    下一篇

车载社交网中基于传递概率的路由算法

张皓晨, 蔡英, 夏红科   

  1. 北京信息科技大学计算机学院 北京100101
  • 收稿日期:2020-02-21 修回日期:2020-05-21 出版日期:2021-03-15 发布日期:2021-03-05
  • 通讯作者: 蔡英(ycai@bistu.edu.cn)
  • 作者简介:zhang_haochen@mail.bistu.edu.cn
  • 基金资助:
    国家自然科学基金(61672106);北京市自然科学基金-海淀原始创新联合基金(L192023)

Delivery Probability Based Routing Algorithm for Vehicular Social Network

ZHANG Hao-chen, CAI Ying, XIA Hong-ke   

  1. Computer School,Beijing Information Science and Technology University,Beijing 100101,China
  • Received:2020-02-21 Revised:2020-05-21 Online:2021-03-15 Published:2021-03-05
  • About author:ZHANG Hao-chen,born in 1996,postgraduate.His main research interests include wireless networks and VANETs.
    CAI Ying,born in 1966,Ph.D,professor,is a member of China Computer Federation.Her main research interests include vehicular networks and edge computing,cyber security and cryptographic algorithms.
  • Supported by:
    National Natural Science Foundation of China(61672106) and Natural Science Foundation of Beijing,China(L192023).

摘要: 在车载社交网(Vehicular Social Network,VSN)中,车辆移动速度快且行驶方向难以预测,导致网络拓扑结构不断变化,通信链路时常中断,因此在进行消息传输时丢失率和传输延迟都居高不下。为了解决上述问题,针对VSN提出了一种基于传递概率的路由算法(ProSim),利用节点间的机会式相遇来进行消息的传输,根据车辆间的社交关系设计VSN路由算法以弥补通信链路中断带来的高丢失率和高延迟;选取了车辆节点的相遇概率和社会相似度这两种社交关系,对其进行量化并计算传递概率。使用真实的道路数据进行仿真,实验结果表明,ProSim与直接传输算法(Direct Delivery,DD)、Epidemic算法以及PRoPHET算法这3种经典路由算法相比,可以在控制传输开销和传输延迟的前提下,有效提高消息的传输率。

关键词: 车载社交网, 传递概率, 机会式通信, 路由算法, 社交关系

Abstract: In a Vehicular Social Network(VSN),due to the rapid and random mobility of vehicles,the network topology changes constantly and the communication link breaks frequently.And thus,the loss rate and the transmission delay are high during message transmission.In order to solve these problems,a delivery probability-based routing algorithm named ProSim is proposed.Opportunistic encounters between nodes are used for message transmission,and the social relationship between vehicles is used to design the routing algorithm.Social relationships used in this paper include the encounter probability and the social similarity between vehicles.These social relationships are quantified and used to calculate the delivery probability.By using real road data for simulation,it proves that ProSim can effectively improve the delivery ratio under the premise of controlling overhead and delay,compared with 3 classic routing algorithms including Direct Delivery,Epidemic and PRoPHET.

Key words: Delivery probability, Opportunistic communication, Routing algorithm, Social relationship, Vehicular social network

中图分类号: 

  • TP393
[1]RAHIM A,KONG X,XIA F,et al.Vehicular Social Networks:A survey[J].Pervasive and Mobile Computing,2018,43:96-113.
[2]SMALDONE S,HAN L,SHANKAR P,et al.RoadSpeak:Enabling Voice Chat on Roadways Using Vehicular Social Networks[C]//Proceedings of the 1st Workshop on Social Network Systems.New York:ACM,2008:43-48.
[3]VAHDAT A,BECKER D.Epidemic Routing for Partially Connected Ad Hoc Networks[R].Durham,NC:Duke University,2000.
[4]SPYROPOULOS T,PSOUNIS K,RAGHAVENDRA C S.Spray and wait:An efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking.New York:ACM,2005:252-259.
[5]DONG B,DENG J,ZHANG D,et al.Technology on data forwarding and routing selection for software defined vehicular Ad Hoc network[J].Journal of Computer Applications,2018,38(1):26-30.
[6]BOURAS C,KAPOULAS V,TSANAI E.A GPSR Enhance-ment Mechanism for Routing in VANETs[C]//International Conference on Wired/Wireless Internet Communications.Berlin:Springer,2015:94-107.
[7]NASCIMENTO H,PEREIRA P R.V-GRADIENT:A Density-Aware Geocast Routing Protocol for Vehicular Delay-Tolerant Networks[C]//Doctoral Conference on Computing,Electrical and Industrial Systems.Berlin:Springer,2019:296-304.
[8]LI Z,XIE G,LIN J,et al.On the geographic patterns of a large-scale mobile video-on-demand system[C]//IEEE Conference on Computer Communications.Piscataway:IEEE,2014:397-405.
[9]SAMARA G.An improved CF-MAC protocol for VANET[J].International Journal of Electrical and Computer Engineering,2019,9(4):2668-2674.
[10]BALOUCHZAHI N M,RAJAEI M.Efficient Traffic Information Dissemination and Vehicle Navigation for Lower Travel Time in Urban Scenario Using Vehicular Networks[J].Wireless Personal Communications,2019,106(2):633-649.
[11]LUO K,LIU G.Routing optimization considering real-time traffic condition and travel distance[J].International Journal of Modern Physics B,2019,33(16):1950169-1 - 1950169-16.
[12]ZHANG L,YU B,PAN J.GeoMob:A mobility-aware geocast scheme in metropolitans via taxicabs and buses[C]//IEEE Conference on Computer Communications.Piscataway:IEEE,2014:1779-1787.
[13]HUI P,CROWCROFT J,YONEKI E.BUBBLE Rap:Social-Based Forwarding in Delay-Tolerant Networks[J].IEEE Transa-ctions on Mobile Computing,2010,10(11):1576-1589.
[14]DALY E M,HAAHR M.Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs[C]//Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing.New York:ACM,2007:32-40.
[15]SHI J,WANG X,HUANG M.ICN-based cache-aware routing scheme in MSN[J].Ad Hoc Networks,2018,75:106-118.
[16]CAI Y,FAN Y,WEN D.An Incentive-Compatible Routing Protocol for Two-Hop Delay-Tolerant Networks[J].IEEE Transa-ctions on Vehicular Technology,2016,65(1):266-277.
[17]CAI Y,HOU L,FAN Y,et al.Message Transmission Scheme Based on the Detection of Interest Community in Mobile Social Networks[C]//International Conference on Mobile Ad-Hoc and Sensor Networks.Berlin:Springer,2017:70-83.
[18]GU X,TANG L,HAN J.A social-aware routing protocol based on fuzzy logic in vehicular ad hoc networks[C]//International Workshop on High Mobility Wireless Communications.Piscataway:IEEE,2015:12-16.
[19]XIA F,LIU L,LI J,et al.BEEINFO:Interest-Based Forwarding Using Artificial Bee Colony for Socially Aware Networking[J].IEEE Transactions on Vehicular Technology,2015,64(3):1188-1200.
[20]STAGKOPOULOU A,BASARAS P,KATSAROS D.A Social-Based Approach for Message Dissemination in Vehicular Ad Hoc Networks[C]//Proceedings of the 6th International Conference on Ad Hoc Networks.Berlin:Springer,2014:27-38.
[21]BRADAI A,AHMED T.ReViV:Selective Rebroadcast Mechanism for Video Streaming over VANET [C]//2014 IEEE 79th Vehicular Technology Conference.Piscataway:IEEE,2015:1-6.
[22]CUNHA F D D,MAIA G G,VIANA A C,et al.Socially Inspired Data Dissemination for Vehicular Ad Hoc Networks[C]//Proceedings of the 17th ACM international conference on Modeling,analysis and simulation of wireless and mobile systems.New York:ACM,2014:81-85.
[23]SU Z,HUI Y,GUO S.D2D-based content delivery with parked vehicles in vehicular social networks[J].IEEE Wireless Communications,2016,23(4):90-95.
[24]LINDGREN A,DORIA A,SCHELÉN O.Probabilistic routing in intermittently connected networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):239-254.
[25]NEWMAN M E J.Clustering and preferential attachment ingrowing networks[J].Physical Review E,2001,64(2):025102.
[26]SPYROPOULOS T,RSOUNIS K,RAGHAVENDRA C S.Single-copy Routing in Intermittently Connected Mobile Networks[C]//2004 First Annual IEEE Communications Society Confe-rence on Sensor and Ad Hoc Communications and Networks.Piscataway:IEEE,2004:235-244.
[1] 董超颖, 续欣, 刘爱军, 苌敬辉.
低轨卫星星座网络路由新方法
New Routing Methods of LEO Satellite Networks
计算机科学, 2020, 47(12): 285-290. https://doi.org/10.11896/jsjkx.191000067
[2] 赵磊, 周金和.
基于复杂网络内容场的ICN能效优化策略
ICN Energy Efficiency Optimization Strategy Based on Content Field of Complex Networks
计算机科学, 2019, 46(9): 137-142. https://doi.org/10.11896/j.issn.1002-137X.2019.09.019
[3] 石峻岭,王兴伟,黄敏.
一种内容中心型车载社交网络路由机制
Content-centric Routing Scheme in Vehicular Social Networks
计算机科学, 2019, 46(7): 50-55. https://doi.org/10.11896/j.issn.1002-137X.2019.07.007
[4] 梁平元, 李杰, 彭娇, 王会.
基于协作MIMO的UWSN三维动态分簇路由算法研究
Research on 3D Dynamic Clustering Routing Algorithm Based on Cooperative MIMO for UWSN
计算机科学, 2019, 46(6A): 336-342.
[5] 王华华, 周远文, 刘江兵.
LLN中基于混合式的网络拥塞控制路由算法
Hybrid-based Network Congestion Control Routing Algorithm for LLN
计算机科学, 2019, 46(6): 107-111. https://doi.org/10.11896/j.issn.1002-137X.2019.06.015
[6] 陈炯, 张虎, 曹付元.
融合多因素的兴趣点协同推荐方法研究
Study on Point-of-interest Collaborative Recommendation Method Fusing Multi-factors
计算机科学, 2019, 46(10): 77-83. https://doi.org/10.11896/jsjkx.180901757
[7] 孙海峰,宋丽丽.
路口中继辅助车载自组织网络路由算法
Intersection-relay-assisted Routing Scheme in VANETs
计算机科学, 2018, 45(5): 75-78. https://doi.org/10.11896/j.issn.1002-137X.2018.05.013
[8] 李璐璐,裘雪红,周端,张剑贤.
片上网络容错技术研究
Research on Fault Tolerant Technology for Networks-on-Chip
计算机科学, 2018, 45(3): 305-310. https://doi.org/10.11896/j.issn.1002-137X.2018.03.050
[9] 黄星河, 李艾静, 王海.
DTN体系结构及关键技术研究综述
Survey of DTN Architecture and Key Technologies
计算机科学, 2018, 45(12): 19-23. https://doi.org/10.11896/j.issn.1002-137X.2018.12.003
[10] 顾云丽, 徐昕, 杜杰.
基于前缀路由策略的无线传感器网络任播路由协议
Prefix-based Anycast Routing Protocol for Wireless Sensor Networks
计算机科学, 2018, 45(12): 81-85. https://doi.org/10.11896/j.issn.1002-137X.2018.12.012
[11] 陈战胜, 沈鸿.
基于虚拟网格的无线传感器网络分簇路由算法
Virtual Grid Based Clustering and Routing Algorithm in Wireless Sensor Networks
计算机科学, 2018, 45(11): 60-65. https://doi.org/10.11896/j.issn.1002-137X.2018.11.007
[12] 林政宽,王铭成,郭莉莉,杜满意.
基于有故障区域的Mesh网络目标结点间的最短路由算法
Shortest Routing Algorithm Based on Target Node in Mesh Network with Faulty Area
计算机科学, 2017, 44(Z6): 252-257. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.058
[13] 朱裴松,钱铁云,吴闽泉.
基于社会化表示的用户性别识别
Identifying Users’ Gender via Social Representations
计算机科学, 2017, 44(Z11): 160-165. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.033
[14] 何超,王琨.
一种非均匀分簇的路由算法
Non-uniform Clustering Routing Algorithm
计算机科学, 2017, 44(8): 60-63. https://doi.org/10.11896/j.issn.1002-137X.2017.08.011
[15] 曾安,徐小强.
基于好友关系和标签的混合协同过滤算法
Hybrid Collaborative Filtering Recommendation Algorithm Based on Friendships and Tag
计算机科学, 2017, 44(8): 246-251. https://doi.org/10.11896/j.issn.1002-137X.2017.08.042
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!