基于随机时变图的时间确定性网络路由算法

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

通信学报 ›› 2021, Vol. 42 ›› Issue (9): 21-30.doi: 10.11959/j.issn.1000-436x.2021138

基于随机时变图的时间确定性网络路由算法

王鹏¹, 张修社¹^,², 索龙¹, 史可懿¹

¹ 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071
² 中国电子科技集团公司第二十研究所，陕西西安 710071

修回日期:2021-04-30 出版日期:2021-09-01 发布日期:2021-09-01
作者简介:王鹏（1995− ），男，河南济源人，西安电子科技大学博士生，主要研究方向为时变图理论、空间信息网络资源表征与调度、时间确定性网络
张修社（1965− ），男，陕西西安人，博士，西安电子科技大学教授、博士生导师，中国电子科技集团公司研究员，主要研究方向为雷达系统、无线通信
索龙（1988− ），男，陕西西安人，博士，西安电子科技大学讲师，主要研究方向为干扰管理、网络资源调度
史可懿（1995− ），男，陕西汉中人，西安电子科技大学博士生，主要研究方向为时变图理论、天地一体化网络路由算法
基金资助:
基础加强重点基金资助项目(2020JCJQXXX)

Time deterministic network routing algorithm based on stochastic temporal graph

Peng WANG¹, Xiushe ZHANG¹^,², Long SUO¹, Keyi SHI¹

¹ Xidian University State Key Laboratory of Integrated Service Networks, Xi’an 710071, China
² Twentieth Research Institute of China Electronics Technology Group Corporation, Xi’an 710071, China

Revised:2021-04-30 Online:2021-09-01 Published:2021-09-01
Supported by:
Key Project in Fundamental Research(2020JCJQXXX)

摘要/Abstract

摘要：

针对天地一体化网络环境中网络时变性和业务时延确定性保障之间的矛盾，构建了随机时变图模型，并基于该模型提出了时间确定性网络路由算法。首先，将空间信息网络最大概率时延保障路由计算问题建模为非线性规划问题。为解决该问题，提出了随机时变图模型，联合表征了由业务随机性导致的链路、存储与时间资源的随机特征，并且表征了存储与链路资源的关联关系，为链路资源利用率的提升与业务的时间确定性保障提供了模型基础；在此基础上，提出了时间复杂度为O(n²)的最大概率时延保障的路由算法，并证明了该算法的最优性。

关键词: 随机时变图, 时间确定性路由, 最大概率时延保障, 时间确定性网络, 天地一体化网络

Abstract:

With respect to the contradiction between the randomness of space-terrestrial integrated network resources and the deterministic requirements of service delay in the network, a stochastic temporal graph model was proposed, based on which a routing algorithm that could guarantee the service delay was constructed.Firstly, how to compute the time-deterministic route over the space information network was modeled as a non-linear programming.To mitigate the problem, a stochastic temporal graph model was proposed, which characterized the stochastic features, caused by the stochastic services of communication links, storage and temporal resources.In addition, the coupling relationship between storage and communication links was also modeled by the graph.Thus, a model was provided by the graph for enhancing the communication link utilization and supporting the time-deterministic routing.Based on this, a routing algorithm fulfilling service delay requirements with the highest probability was proposed with O(n²) polynomial time.The optimality of the algorithm was proved.

Key words: stochastic temporal graph, time deterministic routing, delay guarantee with maximum probability, time deterministic network, space-terrestrial integrated network

中图分类号:

TN915.03

王鹏, 张修社, 索龙, 史可懿. 基于随机时变图的时间确定性网络路由算法[J]. 通信学报, 2021, 42(9): 21-30.

Peng WANG, Xiushe ZHANG, Long SUO, Keyi SHI. Time deterministic network routing algorithm based on stochastic temporal graph[J]. Journal on Communications, 2021, 42(9): 21-30.

图/表 8

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 14

[1]	DU J , JIANG C X , GUO Q ,et al. Cooperative earth observation through complex space information networks[J]. IEEE Wireless Communications, 2016,23(2): 136-144.
[2]	VLK M , HANZáLEK Z , BREJCHOVá K , ,et al. 1Qbv time-sensitive networks[J]. IEEE Transactions on Communications, 2020,68(11): 7023-7038.
[3]	GROSSMAN E . Deterministic networking use cases[R]. RFC Editor, 2019.
[4]	YOSHIZAWA T , BASKARAN S B M , KUNZ A . Overview of 5G URLLC system and security aspects in 3GPP[C]// 2019 IEEE Conference on Standards for Communications and Networking. Piscataway:IEEE Press, 2019: 1-5.
[5]	PECORELLA T , RONGA L S , CHITI F ,et al. Emergency satellite communications:research and standardization activities[J]. IEEE Communications Magazine, 2015,53(5): 170-177.
[6]	MOY J . OSPF protocol analysis[R]. RFC Editor, 1991.
[7]	BOOK B . Schedule-aware bundle routing[J]. Consultative Committee for Space Data Systems, 2019.
[8]	KYI M T , NAING L L . Application of ford-fulkerson algorithm to maximum flow in water distribution pipeline network[J]. International Journal of Scientific and Research Publications (IJSRP), 2018,8(12): 306-310.
[9]	LI H Y , ZHANG T , ZHANG Y K ,et al. A maximum flow algorithm based on storage time aggregated graph for delay-tolerant networks[J]. Ad Hoc Networks, 2017,59: 63-70.
[10]	RIBEIRO A , SIDIROPOULOS N D , GIANNAKIS G B . Optimal distributed stochastic routing algorithms for wireless multihop networks[J]. IEEE Transactions on Wireless Communications, 2008,7(11): 4261-4272.
[11]	FU L Y , WANG X B , KUMAR P R . Are we connected? optimal determination of source–destination connectivity in random networks[J]. IEEE/ACM Transactions on Networking, 2017,25(2): 751-764.
[12]	GENDREAU M , LAPORTE G , SéGUIN R , . Stochastic vehicle routing[J]. European Journal of Operational Research, 1996,88(1): 3-12.
[13]	RUSEK K , SUáREZ-VARELA J ,, ALMASAN P ,et al. RouteNet:leveraging graph neural networks for network modeling and optimization in SDN[J]. IEEE Journal on Selected Areas in Communications, 2020,38(10): 2260-2270.
[14]	WANG J , TANG J , XU Z Y ,et al. Spatiotemporal modeling and prediction in cellular networks:a big data enabled deep learning approach[C]// IEEE INFOCOM 2017 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2017: 1-9.

基于随机时变图的时间确定性网络路由算法

Time deterministic network routing algorithm based on stochastic temporal graph

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 14

相关文章 4

Metrics

推荐阅读 0

[1]	李贺武,刘李鑫,刘君,吴茜. 基于位置的天地一体化网络路由寻址机制研究[J]. 通信学报, 2020, 41(8): 120-129.
[2]	李红艳,张焘,张靖乾,史可懿,曾鹏程. 基于时变图的天地一体化网络时间确定性路由算法与协议[J]. 通信学报, 2020, 41(10): 116-129.
[3]	薛开平,周焕城,孟薇,李少华. 天地一体化网络无缝切换和跨域漫游场景下的安全认证增强方案[J]. 通信学报, 2019, 40(6): 138-147.
[4]	李凤华,陈天柱,王震,张林杰,史国振,郭云川. 复杂网络环境下跨网访问控制机制[J]. 通信学报, 2018, 39(2): 1-10.