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

王鹏; 张修社; 索龙; 史可懿

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 基于随机时变图的时间确定性网络路由算法
- Time deterministic network routing algorithm based on stochastic temporal graph
- 通信学报 2021年42卷第9期页码：21-30
- 作者机构：
  
  1. 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071
  2. 中国电子科技集团公司第二十研究所，陕西西安 710071
- 作者简介：
  
  [ "王鹏（1995− ），男，河南济源人，西安电子科技大学博士生，主要研究方向为时变图理论、空间信息网络资源表征与调度、时间确定性网络" ]
  [ "张修社（1965− ），男，陕西西安人，博士，西安电子科技大学教授、博士生导师，中国电子科技集团公司研究员，主要研究方向为雷达系统、无线通信" ]
  [ "索龙（1988− ），男，陕西西安人，博士，西安电子科技大学讲师，主要研究方向为干扰管理、网络资源调度" ]
  [ "史可懿（1995− ），男，陕西汉中人，西安电子科技大学博士生，主要研究方向为时变图理论、天地一体化网络路由算法" ]
- 基金信息：
  
  基础加强重点基金资助项目(2020JCJQXXX)
- DOI：10.11959/j.issn.1000-436x.2021138
  中图分类号： TN915.03
- 网络出版日期：2021-09，
  
  纸质出版日期：2021-09-25
- 稿件说明：
移动端阅览
王鹏, 张修社, 索龙, 等. 基于随机时变图的时间确定性网络路由算法[J]. 通信学报, 2021,42(9):21-30.

Peng WANG, Xiushe ZHANG, Long SUO, et al. Time deterministic network routing algorithm based on stochastic temporal graph[J]. Journal on communications, 2021, 42(9): 21-30.
王鹏, 张修社, 索龙, 等. 基于随机时变图的时间确定性网络路由算法[J]. 通信学报, 2021,42(9):21-30. DOI： 10.11959/j.issn.1000-436x.2021138.

Peng WANG, Xiushe ZHANG, Long SUO, et al. Time deterministic network routing algorithm based on stochastic temporal graph[J]. Journal on communications, 2021, 42(9): 21-30. DOI： 10.11959/j.issn.1000-436x.2021138.

摘要

针对天地一体化网络环境中网络时变性和业务时延确定性保障之间的矛盾，构建了随机时变图模型，并基于该模型提出了时间确定性网络路由算法。首先，将空间信息网络最大概率时延保障路由计算问题建模为非线性规划问题。为解决该问题，提出了随机时变图模型，联合表征了由业务随机性导致的链路、存储与时间资源的随机特征，并且表征了存储与链路资源

的关联关系，为链路资源利用率的提升与业务的时间确定性保障提供了模型基础；在此基础上，提出了时间复杂度为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.

关键词

Keywords

references

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 .

VLK M , HANZÁLEK Z , BREJCHOVÁ K , , et al . 1Qbv time-sensitive networks [J ] . IEEE Transactions on Communications , 2020 , 68 ( 11 ): 7023 - 7038 .

GROSSMAN E . Deterministic networking use cases [R ] . RFC Editor , 2019 .

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 .

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 .

MOY J . OSPF protocol analysis [R ] . RFC Editor , 1991 .

BOOK B . Schedule-aware bundle routing [J ] . Consultative Committee for Space Data Systems , 2019 .

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 .

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 .

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 .

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 .

GENDREAU M , LAPORTE G , SÉGUIN R , . Stochastic vehicle routing [J ] . European Journal of Operational Research , 1996 , 88 ( 1 ): 3 - 12 .

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 .

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 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据