基于时变图的天地一体化网络时间确定性路由算法与协议

李红艳，张焘，张靖乾，史可懿，曾鹏程

（1.西安电子科技大学通信工程学院，陕西 西安 710071；2.中国电信福建分公司网络运营支撑中心，福建 福州 350001)

1 引言

随着应急通信、应急救援、导航定位、遥感遥测、国防安全、智慧城市等领域的迅速发展，天地一体化网络在很多领域起着不可替代的作用[1]。如图1 所示，未来天地一体化网络将由中继星、星座、星群、专用卫星、空间飞行器、地面站及地面用户构成，通过一体化组网互联，支持信息实时采集、传输和处理海量数据。特别地，与现有地面网络相比，天地一体化网络具有全球覆盖、远距离传输、不受地理环境限制、大容量等显著优点[2]。然而，由于空间卫星不同周期的高速运动、空间与地面设备的动态加入与退出、网络承载业务负荷随时间的动态变化，导致天地一体化网络拓扑和多维网络资源（如链路容量、节点存储等）具有时变性，造成网络稳定的端到端传输路径难构建、业务服务质量（QoS,quality of service）难保障、网络资源利用率难提升[3]。此外，卫星与卫星之间、卫星与地面节点之间通信距离长，链路传播时延大。例如，低轨卫星间的链路时延达毫秒级，远超地面有线网络中的节点间时延。链路的长时延特性造成网络拓扑发现与维护不及时，导致过时路由产生，造成端到端数据传输不可达，同时用户接入长时延也会影响端到端的时延性能保障。因此，长时延链路严重制约着组网协议的效能，导致传统地面网络路由协议在天地一体化网络环境中不适用。基于此，针对链路长时延、资源时变的天地一体化网络环境，亟需研究面向业务的时间确定性路由策略与协议，支持时变路由的构建、保障业务的传输QoS 需求、提升网络资源的效率。

近年来，伴随着物联网、工业互联网的发展需求，国内外研究机构及标准化组织纷纷启动时间确定性网络关键技术与协议的研究[4-11]。目前，在局域网领域，较成熟的时间确定性网络技术、标准化工作正在进行；在多跳网络领域，时间确定性网络组网技术尚处于研究进程中。时间确定性网络通过调度网络资源与业务，保障业务的时延。当前，时间确定性网络有着广泛的应用需求，例如卫星测控网、车联网、工业互联网、无人机测控网、部分传感器网络等物联网要求严格的业务时延保障；VR、AR、语音及视频交互业务均要求较严格的时延。同时，IEEE 主导的以太网、第三代合作伙伴计划（3GPP,3rd Generation Partnership Project）主导的下一代无线通信系统、美国国家航空航天局（NASA,National Aeronautics and Space Administration）主导的星载网络均启动了时间确定性网络的研究工作。然而，针对时变环境的天地一化网络时间确定性组网研究才刚开始，其主要原因在于，时变确定性组网设计面临众多挑战，具体如下。

1) 资源共享与时间确定性相矛盾

由于网络中节点（路由器或交换机）通过单跳或多跳链路互联互通，路由器与链路采用共享模式进行信息传输。共享模式有效提升了链路资源的利用率，支撑灵活的组网模式，但是资源共享模式引入了网络的高时变性，导致网络的时间确定性难以保障。

图1 天地一体化网络示意

2) 资源表征无时间属性，确定性路由难构建

现有的互联网路由协议如TCP/IP，以及新兴的分段路由（SR,segment routing）协议，由于路由表中缺乏时间属性的刻画，数据分组难以按时间进行转发或路由，导致确定性路由难以构建。同时，天地一体化网络中端到端路径存在断续连通的时变特性，稳定传输路径的缺乏加剧了时间确定性路由构建的难度。

3) 多维资源未关联，时变资源利用率低

传统路由算法以静态图论为设计依据，因此在时变网络环境中制约了资源的利用率，限制了时变网络的吞吐量、时延等性能。如图2 所示，假设前向链路与回程链路的容量均为50 Mbit/s。第1 秒时，回程链路的资源被某些业务占用，可用容量为20 Mbit/s；第2 秒时，前向链路的资源被某些业务占用，可用容量为20 Mbit/s。最新互联网协议OSPFv3、RIPng 依托静态图论，将该网络看作分时段的静态网络，则从基站到核心网节点的最大容量为20 Mbit/s。但是，若将该网络看作时变网络，如图3 所示，第1 秒时，前向链路以满负荷50 Mbit/s运行，其中20 Mbit/s 的业务流通过回程链路传输，其余30 Mbit/s 业务流暂存于中间节点；第2 秒时，前向链路以满负荷20 Mbit/s 运行，回程链路以50 Mbit/s 运行，转发来自前向链路及中间缓存的业务。基于此，从基站到核心网节点的容量达到35 Mbit/s，与基于静态图论的路由算法相比，路径吞吐量提升了75%。由此可见，关联利用存储和链路资源，可有效提升网络资源利用率，以及网络对时间确定性业务的保障能力。

图2 传统静态组网

实际上，时变图理论对于时变的天地一化网络研究具有天然优势，包括建模的精准性以及求解的高效性[3]。这是因为时变图通过引入时间属性，支持时变网络多维资源动态特性的刻画。同时，时变图可表征各时段网络之间的承接关系，支持多维资源的关联利用。然而，现有的时变图模型及相应的时变图求解算法均处于研究初期[12-19]，缺乏成熟的时变图理论，难以设计高效的按需路由策略。因此，针对时变的天地一体化网络环境，本文提出了基于时变图的天地一体化网络时间确定性路由算法与协议。首先，构建时变连续图模型，实现天地一体化网络拓扑、链路连通机会、链路带宽、节点缓存等多维资源时空属性的联合刻画；同时，给出时变路径流守恒和链路容量约束等相关定义，设计链路的累积流量计算规则，支持具有差异化链路带宽的路径可行流计算。其次，提出面向业务的时间确定性路由算法，通过联合考虑业务的传输量与开始时刻、链路的连通机会以及节点的存储资源，构建面向业务的最短时延路径，保障业务传输的时间确定性。再次，将所提路由算法与SR技术以及TSN 技术相结合，设计具有时延保障的时间确定性路由协议，支持时变拓扑发现、路由设计以及分组的按时转发。最后，通过仿真实验，验证所提算法与协议的有效性与可行性。

图3 时变组网

2 相关工作

2.1 时间确定性网络发展动态

关于时间确定性网络的研究可以追溯到20 世纪70 年代。早在1979 年，维也纳技术大学（UVT,Vienna University of Technology）便提出时间触发以太网（TTE,time-triggered ethernet）技术，旨在改变传统以太网基于事件触发的传输模式。该技术是局域网领域首个时间确定性网络组网技术，通过调度业务的传输时刻，保障业务的时延[4-5]。而后，TTE技术被应用于2014 年发射的猎户座太空船，并成为美国汽车工程师协会SAE AS6802 总线标准[6]。此外，2005 年，IEEE 802.1 任务组开始制定以太网标准音视频桥（AVB,audio video bridging），主要应用于实时传输需求的音视频领域[7]，包括IEEE 802.1D、IEEE 802.1Q、IEEE 802.1AS 等标准。2012 年，AVB工作组演进为时间敏感网络（TSN,time sensitive network）工作组，对IEEE 802.1Q 协议进行了扩展，提升无线局域网络对时延敏感类业务的保障能力[8]。

当前，TTE 和TSN 技术[9]成为时间确定性网络的主要构成部分，也成为实时可靠网络的研究热点。国内外研究机构及标准化组织纷纷启动时间确定性网络关键技术与协议。例如，2014 年10 月互联网工程任务组（IETF,Internet Engineering Task Force）启动了确定性网络（DetNet,deterministic networking）研究与标准化工作[10-11]，拟采用基于TSN 和多协议标签交换（MPLS,multiprotocol label switching）的方案，旨在从网络层协议设计出发，保障网络时延。然而，DetNet 要求亚微秒级的时钟同步，不适用互联网等大型网络。目前，确定性网络仍以分时段静态网络为假设，网络资源调度算法未考虑网络的时变特征，网络资源利用率难以提升。此外，2018 年12 月，3GPP 也发布了最新的5G 系统服务需求技术规范TS22.261，给出了自动化控制、交通物流、智慧城市、媒体娱乐等典型应用场景的服务指标（时延、可靠性、定位精度等）。可以预见，时间确定性组网设计将在未来网络研究中扮演着越来越重要的角色。

2.2 时变图模型与理论发展动态

一直以来，图论都是网络建模与求解的基础理论工具之一[12]。时变图模型是时变网络资源及其关系的数学表征，也是时变网络协议设计的理论基础。事实上，模型的优劣主要考虑以下2 个因素：1) 精准度，即能否精准表征组网资源随时间的变化关系及资源之间的相互制约关系；2) 高效性，包括模型所占存储资源的大小和基于该模型分析网络性能算法的高效性[3]。传统静态图仅表征了链路资源及节点的连接关系，时变图则增加对节点存储资源、链路资源、节点连接关系等网络时变特征的联合刻画。

图4 离散时间的时变图特性及演进过程

当前，时变图模型可以分为两大类：离散时间的时变图模型和连续时间的时变图模型。具体地，离散时间的时变图模型将连续的时间范围划分为若干个时隙，每个时隙内存在一个相对静止的网络拓扑。因此，离散时间的时变图模型是从静态图演变而来的，并且先后经历了快照图[13]、时间扩展图[14]、时间聚合图[15]、存储时间聚合图[16]的发展历程，如图4 所示。其中，快照图（静态图序列）将时变拓扑在时间维度上进行离散化，每一个快照子图均为静态图，实现动态网络向静态网络的转化。然而，快照图割裂了快照之间的联系，表征精准度低，造成资源浪费。同时，快照图的快照子图数量与时间长度成正比，存储开销大；基于快照图的路由算法在所有的快照子图内重复寻找，路由算法效率低。时间扩展图将快照子图中的对应节点用存储链路相连，可以表征存储−托管−转发机制，表征精准度高；但是，当快照子图较多、网络规模较大时，时间扩展图占用的存储空间大，路由计算复杂度高。时间聚合图将快照图聚合到一起，用链路权重序列表征链路不同时段的权重。时间聚合图模型不需要节点复制，通过资源的聚合表征，降低图模型的存储复杂度，但是缺乏对存储资源的刻画，图模型表征精度低。针对现有时变图模型面临存储复杂度高或表征精度低的问题，本文作者在前期工作中提出存储时间聚合图模型[16]。该模型融合了时间扩展图与时间聚合图模型的各自优势，将时间扩展图进行了聚合表征，在链路与节点处分别构建链路权值序列与节点存储转移序列，实现时变网络时空多维资源以及分时段链路资源制约关系的联合刻画，降低了图模型存储复杂度，提升了图模型的精准度和高效性，支持时变网络最大流与路由算法的高效设计[16-17]。然而，将连续时间进行离散化处理会导致网络时变特性的模糊化，同时划分时隙的大小以及时隙的数量都将影响时变资源刻画的精准度，以及相应求解算法的复杂度。另外，连续时间的时变图模型，则是将链路或节点的时变特性利用时间函数来表示。然而，由于前后链路函数存在复杂的时间约束，导致利用时变函数难以求解时变网络容量以及设计时变路由。

目前的时变图模型可用于路由计算、网络吞吐量求解以及网络多维资源规划，西安电子科技大学、清华大学、哈尔滨工业大学及东北大学等团队均进行了相关研究，并发表成果[14,16-19]。但是，现有时变图理论仅利用静态图、快照图、时间扩展图以及时间聚合图进行时变网络分析与求解，由于图模型的高存储复杂度与低精准度，导致相应算法求解复杂或无法得到全局最优解，而针对存储时间聚合图的高效求解算法的设计才刚刚起步，适用于时变网络规划、多播、稳健性设计的时变图模型不完善或缺失，且适用于随机时变网络的模型也缺失。此外，针对天地一体化网络中有限的传输资源对数据传输的约束与多样化网络任务的时间确定性保障需求的时间连续性表征仍然存在空白。因此，还需进一步完善时变图模型，以降低时间确定性网络分析与设计复杂度。

2.3 时变卫星网络路由算法与协议

虽然天地一体化网络尚未部署，但是近年来为了保障时变网络环境中业务端到端的传输需求，许多基于图论的时变网络路由方法被陆续提出。例如，文献[14]利用快照对卫星网络的动态拓扑进行建模，提出了以最小化路径费用为目标的动态路由算法但是，该算法仅在每个快照中计算路径，忽略了快照间存在的可行路径。为了提高快照的路由性能，文献[20]增加了快照的连通性，通过重新分配星间链路，提升了网络链路资源的利用效率。此外，文献[21]利用事件驱动图对卫星网络拓扑及卫星存储资源进行建模，并且设计了以传输能量消耗最小化为优化目标且满足传输时延需求的路由算法。然而，事件驱动图和空时图均可归属于时间扩展图。因此，随着网络规模或给定时间范围的增加，导致该类图模型存储量大且相关路由算法求解复杂度高。与此同时，也有许多工作正在试图将时延容量网络（DTN,delay tolerant network）路由应用于卫星网络中。例如，文献[22]利用了存储−托管−转发机制来适应卫星链路断续连通的特性，即当卫星没有通信机会时，会将数据进行存储，直到新的通信机会出现再进行相应的转发。尽管存储−托管−转发机制可以提升网络吞吐量，但是由于托管时长的不确定，因此无法保证数据的确定性时延。此外，文献[23]分析了卫星网络与DTN 的动态性，认为卫星网络是典型的DTN。由于卫星的轨道和运动周期是固定且预知的，因此一些确定性的DTN 路由算法也被应用于可预测的卫星网络。特别地，由NASA提出的接触图路由（CGR,contact graph routing）算法实现了时变卫星网络拓扑的动态路由构建[24]，并且该路由算法在卫星网络DTN 模拟器及几个空间飞行实验中得到了验证[25]。实际上，CGR 是一种典型的基于中继传输的路由策略，它根据路由失效时间和剩余链路容量来选择最早连通的路径。然而，现有的CGR 没有考虑业务量等传输需求，同时由于卫星链路连通情况的时间顺序，CGR不能保证大容量任务传输需求，并且网络资源利用率低[17]。

在时变网络路由协议方面，路由协议作为TCP/IP 协议栈的重要组成部分，能够为网络中的数据分组选择合适的传输路径，实现高效的端到端投递。路由协议选择的合适与否将直接影响卫星通信网络的传输效率。传统地面网络多采用由IETF 开发开放最短路径优先（OSPF,open shortest path first）协议[26-27]。OSPF 是一个基于链路状态的路由协议，具有适用范围广、快速收敛、无自环和扩展性强等优势，在互联网中扮演了重要角色。然而，由于空间链路具有断续连通、长时延、低带宽、高误码等特性，传统OSPF 协议在时变卫星网络中会面临链路状态通告频繁、路由重计算开销大、路由收敛缓慢等问题，导致协议效率低下，业务QoS 难保障。为适应空间网络的时变性，国际互联网研究任务组（IRTF,Internet Research Task Force）的时延容忍网络研究组（DTNRG,Delay Tolerant Networking Research Group）提出了束协议（BP,bundle protocol）[28-29]，该协议的传输层和应用层之间采用的存储−托管−转发机制能够保障断续连通通信环境中数据的可靠传输。然而，BP 在协议框架和路由算法方面仍存在不足。1) 缺乏动态拓扑发现与维护机制，网络节点无法感知周围节点的变化，易导致过时路由问题。2) 采用的CGR 算法未考虑业务负载和节点缓存的影响，路由结果非最优，且不能保障多业务的QoS 需求。近年来，不同种类的业务不断涌现，对网络提出了不同的要求，如低时延、低抖动、高带宽和低分组丢失率等，而传统的OSPF协议和BP 均无法保障差异化QoS 需求。在这种背景下，SR 应运而生[30]。SR 是基于源路由理念而设计的在网络中转发数据分组的一种协议，其根据业务需求，利用收集的网络拓扑、带宽利用率和时延等信息，为业务定义一条显示路径。路由信息通过编码添加到数据分组头，而网络中的节点只需维护段信息，有助于实现业务的实时快速转发。然而，人们对SR 的研究才刚刚起步。SR对网络时变性的考虑不足，并且业务转发缺乏时间属性，存储−托管−转发方式和时间确定性保障面临挑战。

综上所述，现有的路由算法和协议均无法高效地利用天地一体化信息网络资源，无法保障业务的时间确定性传输需求，需设计适用于时变网络环境的路由算法和协议。

3 系统模型

3.1 时变连续图模型

天地一体化网络是一个典型的时变网络，同时由于卫星周期性的绕轨运动，网络拓扑变化、链路容量、卫星节点的缓存大小以及运动周期等特性均具有可预测性。因此，本文针对可预测性的时变网络环境建立系统模型。不失一般性地，假设在给定的时间范围T内，网络的所有状态信息（包括拓扑信息、链路连通状态以及节点存储资源大小等）均已知。为了精准刻画时变网络时空多维资源，本文将天地一体化网络中的所有物理实体如卫星、空间飞行器、地面站等均描述为节点，而物理实体之间（如卫星与卫星之间、卫星与地面站之间）的连通机会等均描述为相应的链路。同时，将时变的链路带宽及连通机会按时间顺序刻画在对应的链路上，并将节点的存储能力也表征在节点处。基于此，构建出连续时间的时变图模型−时变连续图（TCG,time-varying continuous graph），即TCG={V,E,T,Wu,v(t),Cu,v(T),Bufv,Nv(t)}，v∈V,(u,v)∈E,t∈T，其中，V表示节点集合，E表示星间链路与星地链路的集合，T表示给定的时间范围，Wu,v(t)表示t时刻链路(u,v)的链路带宽，Cu,v(T)表示在给定时间范围T内节点u和v之间的所有连通时段集合，Bufv表示节点v的缓存大小，Nv(t)表示t时刻节点v的缓存占用情况。

为了便于理解，本文考虑一个由4 个节点构成的简单网络，其中节点的存储资源有限且各链路的连通机会均随时间变化。如图5 所示，节点上利用Bufv刻画出节点的存储资源，而链路上则利用Wu,v(t)与Cu,v(T)分别刻画出相应的链路带宽与连通时段集合。例如，链路(S,A) 在给定时间范围T=[t0,t5]内具有2 个连通时段（灰色条带状部分），因此连通时段集合CS,A(T)={[t0,t2],[t3,t4]}。特别地，为了便于描述，本文将时变连续图中同一链路的不同连通时段进行按序编号，将连通时段数依次标记为，i={1,2,…,N}，其中分别表示第i个连通时段的起始和终止时刻。例如，链路(S,A) 的连通时段可表示为CS,A(T)=，其中和。

3.2 基于时变连续图的相关定义及计算规则

在时变连续图中，由于节点与链路均具有时间相关的约束，因此需要重新定义时变网络中网络流的相关约束及计算规则。首先，对于任一链路(u,v)∈E，将fu,v(t)定义为该链路的时变可行流，fu,v(t)需满足以下几个约束。

图5 时变连续图模型

1) 链路容量约束

本文规定链路(u,v)上任何时刻t∈T=[t0,th]的可行流均不能超过该链路对应时刻的链路带宽，则有

同时，在给定的时间范围T内，链路总的可行流量需小于该链路总的传输能力，即

其中，k为T=[t0,th]内链路(u,v)总的连通时段数。

2) 流守恒约束

对于给定的时间范围T=[t0,th]内，流入任一节点v∈V的总数据量等于流出该节点的总数据量，即

其中，fu,v(t)和fv,u(t)分别表示在t时刻流入与流出节点v的可行流。

3) 节点缓存约束

对于任一时刻τ∈T，节点v的缓存占用情况Nv(τ)受限于该节点的缓存Bufv，以及流入与流出节点v的累积可行流，可描述为

此外，对于任意给定的业务M，需要根据业务量大小D(M)、业务传输开始时刻tstart(M)和终止时刻tend(M)，确定业务数据在端到端传输过程中对路径上所有链路连通时段以及节点存储的占用情况。因此，针对时变连续图中端到端的单跳与多跳时变路径，设计相应的链路累积流量及路径累积流量计算规则，具体如下。

1) 面向业务的链路累积流量计算

对于单跳的时变路径，可根据业务传输需求以及该链路的链路带宽与连通时段集合，确定该链路用于数据传输的有效连通时段。不失一般性地，假设单跳的时变路径为链路(A,B)∈E，链路连通时段集合为，如图6 所示，具体计算规则如下。

①确定链路(A,B)有效连通时段的开始时刻

图6 链路累积流量计算

② 确定链路(A,B)有效连通时段的终止时刻

在业务规定的传输时间范围内，业务量与时变链路可行流需满足如式(5)和式(6)所示关系。

2) 面向业务的路径累积流量计算

对于多跳类时变路径，需根据业务传输需求进行逐跳的链路计算，依次确定链路的有效连通时段，最终得到面向业务的路径累积流量。为了便于描述，如图7 所示，本文以两跳类路径(A,B,C)为例，介绍路径累积流量的计算规则。

图7 路径累积流量计算

不失一般性地，上述介绍的两跳类路径计算规则也适于多跳类路径计算。其核心思想在于需依次利用前一跳链路的有效连通时段计算后一跳链路的有效连通时段，最后得到面向业务的端到端路径中节点与链路资源的占用情况，实现时变资源的按需分配。

4 面向业务的时间确定性路由方法

在时变的天地一体化网络中，构建具有时间属性的时变路由策略是保障业务端到端QoS 需求的关键。因此，基于所构建的时变连续图模型以及设计的时变可行流约束与计算规则，本文进一步提出面向业务的时间确定性路由算法，如算法1 所示，该算法通过联合考虑业务的传输量与开始时刻，链路的连通机会以及节点的存储资源，借助链路累积流量计算规则，构建面向业务的最短时延路径，从而保障业务传输的时间确定性。

算法1面向业务的时间确定性路由算法

输入时变连续图TCG={(V,E,T,Wu,v(t),Cu,v(T),Bufv,Nv(t))|v∈V,(u,v)∈E,t∈T}，给定的业务M，包括业务量大小D(M)、业务传输开始时刻tstart(M)、终止时刻tend(M)以及传输的源点S与目的点D

输出从S到D的端到端时变路径Path(M)，满足M传输需求且具有确定性时延保障

步骤1每个节点v∈V均设置2 个路由参数c[v]与p[v]，其中c[v]表示将业务量D(M)从源点S传输到节点v的最早完成时间，p[v]表示路由过程中节点v的前一跳节点，同时将其初始化为c[v]=∞，p[v]=−1（−1 表示该节点没有前一跳）。

步骤2配置节点S的节点费用c[S]=tstart(M)以及前一跳节点p[S]=−1，并将节点S加入节点队列Q中，Q←S。

步骤3判断队列Q是否为空集，若Q为空集，跳转至步骤7；否则，执行步骤4。

步骤4从Q中取出节点费用最小的节点u作为当前的找路节点，同时更新队列Q←Q−u。

步骤5当节点u=S时，利用面向业务的链路累积流量计算规则，计算出节点u所有邻接链路(u,v)的有效连通时段；当节点u≠S时，利用面向业务的路径累积流量计算规则，根据链路(p[u],u)的有效链路时段以及节点u的缓存能力Bufu，计算出节点u所有邻接链路(u,v)的有效连通时段。

步骤6利用链路(u,v)的终止时刻对邻接节点v的节点费用c[v]进行更新（如果，则更新c[v]=且p[v]=u），并把节点v加入队列Q，并跳转至步骤3。

步骤7判断目的点D的节点费用大小，若c[D]=∞，则表示任务M不存在从S到D的有效路径，终止算法；否则，执行步骤8。

步骤 8从D开始，依次利用前一跳节点p[D]，获得从S到D的路径Path(M)，并记录下路径中各链路的有效连通时段。

为了便于理解，本文给出一个算法实例来描述路由算法的执行过程，如图8 所示。具体地，在图8(a)中，假设给定业务M的业务量为2 个单位数据，业务传输时刻为t0，要求从节点S传输到节点D；同时，网络的链路连通时段随时间变化，且每个时隙[ti,ti+1]内链路的传输能力为1 个单位数据。为了保障业务的端到端传输，所提路由算法的计算过程如下。首先，如图8(b)所示，选择节点S作为当前节点，并根据业务的传输开始时间t0，更新节点S的节点费用c[S]=t0和前一跳节点p[S]=−1，同时，利用面向业务的链路累积流量计算规则，计算出节点S的所有邻接链路(S,A) 和(S,B)的有效连通时段，并基于有效连通时段的截止时刻对邻接节点A和B进行节点费用与前一跳节点的更新；然后，如图8(c)所示，选择具有最早传输完成时间的节点A作为新的当前节点，利用面向业务的路径累积流量计算规则，根据链路(S,A) 的有效连通时段，确定节点A所有邻接链路(A,B)和(A,D)的有效连通时段，并且更新邻接节点D和B的节点费用与前一跳节点；然后，如图8(d)所示，继续选择具有最早传输完成时间的节点B作为新的当前节点，根据链路(A,B)的有效连通时段，计算链路(B,D)的有效连通时段；最后，如图8(e)所示，根据节点D的前一跳节点p[D]，依次回溯，最终得到从S到D的时变路径，即路径（S−A−B−D）。同时，利用路径（S−A−B−D）中各节点的节点费用以及链路的有效连通时段，可以实现网络资源的按时分配与调度，满足端到端业务的时间确定性传输。

图8 面向业务的时间确定性路由算法实例

5 时间确定性路由协议

基于时变图的时间确定性路由算法可为不同业务规划出满足传输需求的时变路径，但为了保障业务传输的时间确定性，还需相应协议作为支撑。因此，本文针对天地一体化网络的时变环境，提出时间确定性路由协议及协议栈模型，如图9 所示。该模型在传统TCP/IP 协议栈的基础上对网络层协议进行扩展，增加了时间确定性路由协议，包括自适应拓扑发现与维护机制和基于时变图的多业务时间确定性路由算法，为业务传输规划出满足时延需求的时变路径。此外，为对每类业务进行精准传输和托管控制，本文将路由协议与SRv6 协议相结合，提出基于SR 的时间触发分组转发机制，实现不同业务按不同显式路径高效传输，保障时间确定性。

图9 天地一体化网络节点协议栈模型

1) 自适应拓扑发现与维护机制

拓扑发现是路由计算的基础，因此及时、准确地获取网络拓扑和可用资源等信息是时间确定性路由构建的关键。天地一体化网络中节点的移动性、资源的共享性以及节点的动态加入和退出导致网络拓扑频繁变化，传统的基于固定周期的拓扑发现机制面临问题。拓扑发现周期越短，拓扑信息的准确性越高，但信令负荷重，制约路由算法的性能。若拓扑发现周期过长，则对于突发情况导致的拓扑变化发现不及时，易产生过时路由，导致分组丢失，且重路由将带来额外的开销。基于此，考虑到天地一体化网络拓扑变化具有一定的可预测性，将周期性拓扑发现与基于拓扑预测的拓扑发现和基于主动探测的拓扑发现相结合，提出自适应的拓扑发现与维护机制，在保障拓扑信息及时、准确的同时降低信令负荷。

如图10(a)所示，以时间T为周期发送Hello 分组进行拓扑探测。若依据节点的运行轨迹、速度和时间等信息预测拓扑的变化，在有链路断开或连通的时刻发送Hello 分组，而在其余时刻按照大于T的周期进行拓扑探测和维护，则能够有效降低开销，如图10(b)所示。对于由故障等原因引起的难以预测的拓扑变化，则由事件触发，主动发送Hello分组进行探测，保障拓扑信息的及时性，如图10(c)所示。

通过自适应拓扑发现与维护机制，能够动态获取天地一体化网络的拓扑和可用资源等信息，作为多业务时间确定性路由算法的输入，计算出确定性时延的时变路径，并转化为具有时间属性的路由表，即包含每跳传输的开始和终止时刻。协议中各模块的关系如图11 所示。

2) 基于SR 的时间触发分组转发机制

借鉴TSN 技术允许周期性与非周期性数据在同一网络中共同传输的思想，本文将业务分组分为时间确定性业务分组与普通业务分组（普通业务无时延保障），利用时间触发机制实现分组转发。特别地，对于时间确定性业务的分组，本文进一步融合了SR 技术对分组进行路由转发。具体来说，依据构建出的时变路由表，将路由信息添加至分组头部。此外，为了精准控制分组的传输，还添加了转发的开始和结束时刻。当网络节点转发分组时，将优先识别分组头部的路由信息，获取下一跳节点，并由时间触发，执行转发流程，直到将分组投递至目的节点。若需要在节点进行托管，则根据路由表信息设置定时器，在定时器超时后再传输数据。对于没有严格的时延保障要求的普通业务，在不影响时间确定性业务传输的前提下，按照统一计算出的路由表，通过IPv6 流程实现分组的存储−托管−转发。

6 仿真与评估

为了验证面向业务的时间确定性路由算法的有效性与可行性，本文将所提算法（记为TCG-based）与CGR 算法[24]和基于快照图的路由算法[26-27]（记为snapshot-based）进行比较，并对仿真结果进行了分析与讨论。

1) 仿真场景及参数设置

本文考虑一个由32 颗低轨卫星和3 个地面站构成的卫星网络场景。其中，低轨卫星均取自Walker 星座，包含4 个轨道面（轨道高度为700 km，倾角为86°）且每个轨道面均匀分布8 颗卫星。地面站分别设在北京（东经116°20′、北纬39°56′）、酒泉（东经100°17′、北纬40°57′）和三亚（东经109°50′、北纬18°25′）。本文利用卫星工具包（STK,satellite tool kit）获取网络的真实连通情况，即网络的时变拓扑，仿真时间段为2020 年6 月5 日00:00—12:00。此外，在32 颗低轨卫星和3 个地面站中随机选定10 组源/汇节点对，且源节点的业务到达均服从泊松过程。特别地，每个业务的大小设定为30 MB，业务总数为400 个。初始时，设定每条传输链路的可用带宽为300 Mbit/s，每颗卫星的可用存储资源为100 MB。

图10 自适应拓扑发现与维护机制

图11 时间确定性路由与转发协议中各模块的关系

为了分析与评估算法性能，考虑如下3 项指标。

2) 仿真结果与分析

图12 给出3 种路由算法的端到端时延对比。从图12 可以看出，snapshot-based 算法的端到端时延最低，但是点数最少（即完成的业务数最少），其背后的原因在于，该算法仅在单独的快照图内搜索端到端路径，不支持跨时段数据传输，所求路径的跳数少、时延低。然而，当快照内不存在端到端路径时，业务无法传输。TCG-based 算法与CGR 算法的端到端时延性能基本一致，由于均采用存储−托管−转发方式，时延略高于snapshot-based 算法。此外，TCG-based 算法比CGR 算法能够完成更多的业务，原因是该算法选路时考虑到节点缓存限制，规避掉了缓存溢出节点。

3种路由算法的链路资源利用率对比如图13所示。从图13 中可以看出，TCG-based 算法的链路资源利用率最高，CGR 算法次之，而snapshot-based算法最低。该现象可以解释为snapshot-based 算法无法联合利用不同时段的网络链路资源，而TCG-based 算法与CGR 算法借助节点缓存资源存储−托管−转发机制，能够构建时变传输路径，实现不同时段空闲资源的高效利用。此外，由于CGR算法在路径计算时未考虑节点缓存限制，可能产生部分无效路径，导致链路资源利用率低于TCGbased 算法。

图12 3 种路由算法的端到端时延对比

图13 3 种路由算法的链路资源利用率对比

图14 给出了3 种路由算法的分组投递率对比。从图14 可以看出，snapshot-based 算法能够成功传输的业务分组最少，原因是在卫星网络环境中，由于拓扑断续连通，单个快照内难以构建出端到端路径，业务分组无法传输到目的节点，导致投递率低。TCG-based 算法和CGR 算法均支持跨时段数据传输，在给定时间范围内能够到达目的节点的业务分组多。此外，由于TCG-based 算法考虑了节点缓存约束，避免由缓存溢出导致的分组丢失，因此投递率更高。

7 结束语

图14 3 种路由算法的分组投递率对比

本文围绕着天地一体化网络中业务端到端传输的路由问题，提出基于时变图的天地一体化网络时间确定性路由算法及协议。首先，通过构建时变连续图模型，实现天地一体化网络时刻多维资源的精准刻画；然后，提出面向业务的时间确定性路由算法，利用面向业务的时变链路累积流量计算规则，构建时变按需的最短时延路径；最后，进一步设计了具有时延保障的时间确定性路由协议，支持断续连通的时变网络环境中拓扑的动态发现、确定性路由的高效计算以及数据分组的定时转发。仿真结果表明，所提路由算法通过利用节点存储资源，有效地提升了时变链路资源利用率，保障了业务在时变环境下的端到端传输需求。