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

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

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 7

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

参数	值
仿真时间/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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 31

Related Articles 15

Metrics

Recommended 0

[1]	Zhuo CHEN,Gang FENG,Yijing LIU,Yang ZHOU. Virtual network function deployment strategy based on improved genetic simulated annealing algorithm in MEC [J]. Journal on Communications, 2020, 41(4): 70-80.
[2]	Hongyan LI,Tao ZHANG,Jingqian ZHANG,Keyi SHI,Pengcheng ZENG. Time deterministic routing algorithm and protocol based on time-varying graph over the space-ground integrated network [J]. Journal on Communications, 2020, 41(10): 116-129.
[3]	Bin LIU,Ruixing FAN,Haoran LIU,Liyue ZHANG,Haiyu WANG,Chunlan ZHANG. Bayesian network structure learning algorithm based on hybrid binary salp swarm-differential evolution algorithm [J]. Journal on Communications, 2019, 40(7): 151-161.
[4]	CHEN Xingshu,HUA Qiang,WANG Yitong,GE Long,ZHU Yi. Research on low-rate DDoS attack of SDN network in cloud environment [J]. Journal on Communications, 2019, 40(6): 210-222.
[5]	Zhigang CHEN,NBin'an YI,Jia WU. Energy balanced routing algorithm for opportunistic network based on message importance [J]. Journal on Communications, 2018, 39(12): 91-101.
[6]	Haoran LIU,Pan DING,Changjiang GUO,Jinfeng CHANG,Jingchuang CUI. Study on Chinese spam filtering system based on Bayes algorithm [J]. Journal on Communications, 2018, 39(12): 151-159.
[7]	Ya-hui WANG,Hong-feng KUANG,Li-dong ZHU. Capacity analysis of the MEO satellite constellation [J]. Journal on Communications, 2017, 38(Z1): 193-199.
[8]	Qi-xuan WU,Jian-feng MA,Cong SUN,Shuai ZHANG,Shuang ZHANG,Tao ZHENG. Constraint analysis for extended dynamic fault tree [J]. Journal on Communications, 2017, 38(9): 159-166.
[9]	Yang GENG,Su-jie SHAO,Shao-yong GUO,Peng YU. Bayesian network-based video QoE assessment method using image sustained damage analysis [J]. Journal on Communications, 2017, 38(6): 136-141.
[10]	Kang-ning SUN,Lin-hua MA,Le RU,Wen-tong FAN,Xing HU,Shao-cheng HUANG. Analysis of stability condition for LDPC codes and optimizing degree sequences over mixed channel [J]. Journal on Communications, 2016, 37(9): 168-174.
[11]	Hua TAO,Fu-qin FENG,Peng XIAO,Cheng-wei TAN,Jun TAO. Routing algorithm based on characteristics analysis of vehicle trace in vehicular ad hoc network [J]. Journal on Communications, 2016, 37(6): 144-153.
[12]	Yue-ping CAI,Chang-ping WANG. Software defined data center network with hybrid routing [J]. Journal on Communications, 2016, 37(4): 44-52.
[13]	Li YANG,Jing SUN,Cheng-sheng PAN,Qi-jie ZOU. LEO multi-service routing algorithm based on multi-objective decision making [J]. Journal on Communications, 2016, 37(10): 25-32.
[14]	Zhen-hua WU,Peng HU. Analysis on VANET routing protocols [J]. Journal on Communications, 2015, 36(Z1): 75-84.
[15]	AOJiu-xin C,HENGao-jun C,ANGJing Y,HUZi-qing Z,IUBo L. Social-based routing in pocket switched networks [J]. Journal on Communications, 2015, 36(5): 13-22.