基于多时间段优化贝叶斯网络的车载容迟网络路由算法

doi:10.11959/j.issn.1000-436x.2021222

通信学报 ›› 2021, Vol. 42 ›› Issue (12): 109-120.doi: 10.11959/j.issn.1000-436x.2021222

基于多时间段优化贝叶斯网络的车载容迟网络路由算法

吴家皋¹^,², 郭亚航¹^,², 蔡沈磊¹^,², 刘林峰¹^,²

¹ 南京邮电大学计算机学院，江苏南京 210023
² 江苏省大数据安全与智能处理重点实验室，江苏南京 210023

修回日期:2021-11-19 出版日期:2021-12-01 发布日期:2021-12-01
作者简介:吴家皋（1969- ），男，江苏苏州人，博士，南京邮电大学副教授，主要研究方向为计算机网络、分布式计算、人工智能等
郭亚航（1994- ），男，河南商丘人，南京邮电大学硕士生，主要研究方向为车载容迟网络、路由算法等
蔡沈磊（1998- ），男，江苏南通人，南京邮电大学硕士生，主要研究方向为车载容迟网络、路由算法等
刘林峰（1981- ），男，江苏丹阳人，博士，南京邮电大学教授，主要研究方向为计算机网络、机器学习等
基金资助:
国家自然科学基金资助项目(61872191);国家自然科学基金资助项目(41571389)

Vehicular delay tolerant network routing algorithm based on optimized multi-period Bayesian network

Jiagao WU¹^,², Yahang GUO¹^,², Shenlei CAI¹^,², Linfeng LIU¹^,²

¹ School of Computer Science， Nanjing University of Posts and Telecommunications， Nanjing 210023， China
² Jiangsu Key Laboratory of Big Data Security ＆Intelligent Processing， Nanjing 210023， China

Revised:2021-11-19 Online:2021-12-01 Published:2021-12-01
Supported by:
The National Natural Science Foundation of China(61872191);The National Natural Science Foundation of China(41571389)

摘要/Abstract

摘要：

针对车载容迟网络（VDTN）中车辆节点高速移动造成的通信链路不稳定性问题，利用车辆节点移动的规律性和时段性特点，提出了基于多时间段优化贝叶斯网络（BN）的VDTN路由算法。首先，提出了新的多时间段BN模型及其节点分类动态奖励机制，以更准确地描述车辆的移动模式。接着，提出了2种新的BN的时间段优化划分算法：二分搜索K2GA（BS-K2GA）算法和模拟退火K2GA（SA-K2GA）算法，其中，BS-K2GA算法具有简单高效的优势，而 SA-K2GA 算法则能有效避免陷入局部最优解，进一步优化算法性能。仿真实验表明，所提出的基于多时间段优化BN的VDTN路由算法能显著提高消息的投递率，降低消息的投递时延，从而验证了研究方案的有效性。

关键词: 车载容迟网络, 贝叶斯网络, 路由算法, 二分搜索, 模拟退火

Abstract:

Aiming at the instability of communication link caused by the high-speed movement of vehicle nodes in vehicular delay tolerant network （VDTN）， considering the characteristics of regularity and periodicity of vehicle nodes movement， a VDTN routing algorithm based on optimized multi-period Bayesian network （BN） was proposed.Firstly， a new multi-period BN model and its dynamic reward mechanism for node classification were proposed to describe the movement pattern of vehicle nodes with higher accuracy.Then， two novel time-optimal-partition algorithms of multi-period BN were proposed including binary search K2GA （BS-K2GA） algorithm and simulated annealing K2GA （SA-K2GA） algorithm， where BS-K2GA algorithm had the advantages of simplicity and efficiency， while SA-K2GA could effectively avoid falling into the local optimal solution and further optimize the performance.The simulation results show that the proposed VDTN routing algorithm based on optimized multi-period BN model can significantly improve the message delivery ratio and reduce the delivery delay.Thus， the effectiveness of the approach is validated.

Key words: vehicle delay tolerant network, Bayesian network, routing algorithm, binary search, simulated annealing

中图分类号:

TP393

吴家皋, 郭亚航, 蔡沈磊, 刘林峰. 基于多时间段优化贝叶斯网络的车载容迟网络路由算法[J]. 通信学报, 2021, 42(12): 109-120.

Jiagao WU, Yahang GUO, Shenlei CAI, Linfeng LIU. Vehicular delay tolerant network routing algorithm based on optimized multi-period Bayesian network[J]. Journal on Communications, 2021, 42(12): 109-120.

图/表 7

图1

图2

表1

图3

图4

图5

图6

参考文献 31

[1]	JAIN S , FALL K , PATRA R . Routing in a delay tolerant network[J]. ACM SIGCOMM Computer Communication Review, 2004,34(4): 145-158.
[2]	ALAOUI S E , RAMAMURTHY B . Routing optimization for DTN-based space networks using a temporal graph model[C]// Proceedings of 2016 IEEE International Conference on Communications (ICC). Piscataway:IEEE Press, 2016: 1-6.
[3]	LUO J H , CHEN Y P , WU M ,et al. A survey of routing protocols for underwater wireless sensor networks[J]. IEEE Communications Surveys ＆ Tutorials, 2021,23(1): 137-160.
[4]	XIANG S H , YANG J . Performance reliability evaluation for mobile ad hoc networks[J]. Reliability Engineering ＆ System Safety, 2018,169: 32-39.
[5]	TORNELL S M , CALAFATE C T , CANO J C ,et al. DTN protocols for vehicular networks:an application oriented overview[J]. IEEE Communications Surveys ＆ Tutorials, 2015,17(2): 868-887.
[6]	TIAN J W , GAO M J , GE G S . Wireless sensor network node optimal coverage based on improved genetic algorithm and binary ant colony algorithm[J]. EURASIP Journal on Wireless Communications and Networking, 2016,2016(1): 104.
[7]	BOCQUILLON R , JOUGLET A . Robust routing in deterministic delay-tolerant networks[J]. Computers ＆ Operations Research, 2018,92: 77-86.
[8]	VASILAKOS A V , ZHANG Y , SPYROPOULOS T . Delay tolerant networks:protocols and applications[M]. Los Angeles: CRC Press, 2019.
[9]	LI Y , ZHAO L , LIU Z J ,et al. N-Drop:congestion control strategy under epidemic routing in DTN[C]// Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing:Connecting the World Wirelessly.[S.l.:s.n.], 2009: 457-460.
[10]	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 Press, 2005: 252-259.
[11]	LINDGREN A , DORIA A , SCHELéN O , . Probabilistic routing in intermittently connected networks[C]// Service Assurance with Partial and Intermittent Resources. Berlin:Springer, 2004: 239-254.
[12]	SHARMA D K , DHURANDHER S K , WOUNGANG I ,et al. A machine learning-based protocol for efficient routing in opportunistic networks[J]. IEEE Systems Journal, 2018,12(3): 2207-2213.
[13]	ROLLA V G , CURADO M . A reinforcement learning-based routing for delay tolerant networks[J]. Engineering Applications of Artificial Intelligence, 2013,26(10): 2243-2250.
[14]	SEGUNDO F R , FARINES J M , SILVEIRA E . Quasi-opportunistic contact prediction in delay/disruption tolerant network[C]// Proceedings of Global Information Infrastructure Symposium - GIIS 2013. Piscataway:IEEE Press, 2013: 1-6.
[15]	AHMED S , KANHERE S S . A Bayesian routing framework for delay tolerant networks[C]// Proceedings of 2010 IEEE Wireless Communication and Networking Conference. Piscataway:IEEE Press, 2010: 1-6.
[16]	DUDUKOVICH R , HYLTON A , PAPACHRISTOU C . A machine learning concept for DTN routing[C]// Proceedings of 2017 IEEE International Conference on Wireless for Space and Extreme Environments (WiSEE). Piscataway:IEEE Press, 2017: 110-115.
[17]	LIANG J J , BAI Y B , BI C G ,et al. Adaptive routing based on Bayesian network and fuzzy decision algorithm in delay-tolerant network[C]// Proceedings of 2013 IEEE 10th International Conference on High Performance Computing and Communications ＆ 2013 IEEE International Conference on Embedded and Ubiquitous Computing. Piscataway:IEEE Press, 2013: 690-697.
[18]	SUTRISNOWATI R A , BAE H , PARK J ,et al. Learning Bayesian network from event logs using mutual information test[C]// Proceedings of 2013 IEEE 6th International Conference on Service-Oriented Computing and Applications. Piscataway:IEEE Press, 2013: 356-360.
[19]	ZGUROVSKII M Z , BIDYUK P I , TERENT’EV A N , . Methods of constructing Bayesian networks based on scoring functions[J]. Cybernetics and Systems Analysis, 2008,44(2): 219-224.
[20]	WU J G , GUO Y H , ZHOU H Y ,et al. Vehicular delay tolerant network routing algorithm based on Bayesian network[J]. IEEE Access, 2020,8: 18727-18740.
[21]	ZHOU H Y , WU J G , SHEN L ,et al. Vehicle delay-tolerant network routing algorithm based on Multi-period Bayesian network[C]// Proceedings of 2018 IEEE 37th International Performance Computing and Communications Conference (IPCCC). Piscataway:IEEE Press, 2018: 1-8.
[22]	EKMAN F , KER?NEN A , KARVO J >,et al. Working day movement model[C]// Proceeding of the 1st ACM SIGMOBILE Workshop on Mobility Models. New York:ACM Press, 2008: 33-40.
[23]	DORIGO M , STüTZLE T , . Ant colony optimization:overview and recent advances[M]. Berlin: Springer, 2018.
[24]	DOGUC O , RAMIREZ-MARQUEZ J E , . A generic method for estimating system reliability using Bayesian networks[J]. Reliability Engineering ＆ System Safety, 2009,94(2): 542-550.
[25]	刘彬, 王海羽, 孙美婷 ,等. 一种通过节点序寻优进行贝叶斯网络结构学习的算法[J]. 电子与信息学报, 2018,40(5): 1234-1241.
	LIU B , WANG H Y , SUN M T ,et al. Learning Bayesian network structure from node ordering searching optimal[J]. Journal of Electronics ＆ Information Technology, 2018,40(5): 1234-1241.
[26]	DELAHAYE D , CHAIMATANAN S , MONGEAU M . Simulated annealing:from basics to applications[M]. Berlin: Springer, 2018.
[27]	METROPOLIS N , ROSENBLUTH A W , ROSENBLUTH M N ,et al. Equation of state calculations by fast computing machines[J]. The Journal of Chemical Physics, 1953,21(6): 1087-1092.
[28]	MADSEN A L , JENSEN F V . Lazy propagation:a junction tree inference algorithm based on lazy evaluation[J]. Artificial Intelligence, 1999,113(1/2): 203-245.
[29]	KOTZ D , HENDERSON T . CRAWDAD:a community resource for archiving wireless data at Dartmouth[J]. IEEE Pervasive Computing, 2005,4(4): 12-14.
[30]	SHAH V , GILBERT J R . Sparse matrices in Matlab*P:design and implementation[C]// Lecture Notes in Computer Science. Berlin:Springer, 2004: 144-155.
[31]	KER?NEN A , OTT J , K?RKK?INEN T , . The ONE simulator for DTN protocol evaluation[C]// Proceedings of the Second International ICST Conference on Simulation Tools and Techniques.[S.l.:s.n.], 2009: 1-10.

参数	值
仿真时间/s	47 000
仿真区域大小	35 km × 25 km
传输范围/m	50
传输速度/（kbit·s^-1）	250
消息大小/KB	50
节点个数	98

基于多时间段优化贝叶斯网络的车载容迟网络路由算法

Vehicular delay tolerant network routing algorithm based on optimized multi-period Bayesian network

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 31

相关文章 15

Metrics

推荐阅读 0

[1]	张兆娟,王万良,唐继军. 适应度二次选择的QPSO和SA协同搜索大规模离散优化算法[J]. 通信学报, 2020, 41(8): 22-31.
[2]	陈卓,冯钢,刘怡静,周杨. MEC中基于改进遗传模拟退火算法的虚拟网络功能部署策略[J]. 通信学报, 2020, 41(4): 70-80.
[3]	李红艳,张焘,张靖乾,史可懿,曾鹏程. 基于时变图的天地一体化网络时间确定性路由算法与协议[J]. 通信学报, 2020, 41(10): 116-129.
[4]	刘彬,范瑞星,刘浩然,张力悦,王海羽,张春兰. 基于混合樽海鞘-差分进化算法的贝叶斯网络结构学习算法[J]. 通信学报, 2019, 40(7): 151-161.
[5]	陈兴蜀,滑强,王毅桐,葛龙,朱毅. 云环境下SDN网络低速率DDoS攻击的研究[J]. 通信学报, 2019, 40(6): 210-222.
[6]	陈志刚,殷滨安,吴嘉. 基于消息重要性的机会网络能量均衡路由算法[J]. 通信学报, 2018, 39(12): 91-101.
[7]	刘浩然,丁攀,郭长江,常金凤,崔静闯. 基于贝叶斯算法的中文垃圾邮件过滤系统研究[J]. 通信学报, 2018, 39(12): 151-159.
[8]	王雅慧,况鸿凤,朱立东. 中轨卫星星座系统容量分析[J]. 通信学报, 2017, 38(Z1): 193-199.
[9]	吴奇烜,马建峰,孙聪,张帅,张双,郑涛. 针对扩展动态故障树的约束分析方法[J]. 通信学报, 2017, 38(9): 159-166.
[10]	耿杨,邵苏杰,郭少勇,喻鹏. 基于可见损伤持续时间贝叶斯网络的视频QoE评估方法[J]. 通信学报, 2017, 38(6): 136-141.
[11]	孙康宁,马林华,茹乐,范文同,胡星,黄绍城. 混合信道下LDPC码稳定条件分析及度序列优化[J]. 通信学报, 2016, 37(9): 168-174.
[12]	陶桦,冯富琴,肖鹏,谭诚伟,陶军. 基于运行轨迹特征分析的车辆自组织网路由算法[J]. 通信学报, 2016, 37(6): 144-153.
[13]	蔡岳平,王昌平. 软件定义数据中心网络混合路由机制[J]. 通信学报, 2016, 37(4): 44-52.
[14]	杨力,孙晶,潘成胜,邹启杰. 基于多目标决策的LEO卫星网络多业务路由算法[J]. 通信学报, 2016, 37(10): 25-32.
[15]	曹玖新,陈高君,杨婧,朱子青,刘波. 基于社会属性的PSN消息路由算法[J]. 通信学报, 2015, 36(5): 13-22.