空间信息网络时变图建模方法*

杨惠婷，刘伟

（西安电子科技大学，陕西 西安 710000）

0 引言

未来6G网络的关键特征和期望之一是提供全球无缝覆盖，实现从万物互联到万物智联的跃迁[1-5]。在实现这愿景的过程中，星地融合网络成为了推动力量之一，其在6G中担任尤为重要的角色[4,6-7]。星地融合网络主要由地面移动通信网络和空间信息网络等共同组成[4,7-8]。星地融合网络实现全球无缝覆盖，在6G的许多应用领域提供了有力支撑，例如智慧城市、远洋航行、偏远地区监测等[9-12]。特别地，在没有基站覆盖的偏远地区，例如沙漠、无人区、海洋和山区等，以及基站被摧毁的重灾地区，例如地震、山洪等[5,10,13]。

空间信息网络是星地融合网络中一个重要组成部分[4,14]，其由同步轨道（GEO,Geostationary Earth Orbit）卫星、中轨道（MEO,Middle Earth Orbit）卫星、低轨道（LEO,Low Earth Orbit）卫星和地面站等组成的多层次网络[13,15-16]。星地融合网络通过空间信息网络可以实现全球无缝覆盖，并且可以支持灵活、无处不在的网络接入[16-17]。此外，星地融合网络中的空间信息网络具有高可靠性、大容量、远距离传输和不受地理环境限制等显著优点[15,17]。

对空间信息网络进行合适的建模是网络规划、资源管理和性能分析等空间信息网络研究的基础[18-21]。通过空间信息网络的建模，可以更深入理解网络结构和性能，可以有助于提高资源利用率、提升网络性能、保障网络的鲁棒性和不同任务的服务质量需求（QoS,Quality of Service）[19-23]。因此，空间信息网络的建模得到广泛研究[19-27]。然而，与传统地面网络相比，空间信息网络的卫星分布较为稀疏，并且卫星沿着固定轨道高速移动，使得卫星之间的通信链路间歇性连通，导致空间信息网络拓扑随时间动态变化且可预测[19-23]。

图模型是一种重要的网络建模与分析的理论工具，已经被广泛应用于表征各种网络[22,28]。传统的地面网络通常采用静态图模型来刻画其网络拓扑结构[29]。然而，传统的静态图模型无法刻画空间信息网络拓扑动态变化。因此，采用时变图模型来表征时变的空间信息网络成为了一个研究热点[21-25,27,30-32]。

目前，表征时变的空间信息网络的时变图主要包括:快照序列图[33]、时间扩展图[29]、存储时间聚合[18]和多功能时间扩展图[19]。文献[30]采用了快照序列图表征空间信息网络的动态演进过程，其联合表征了卫星的通信资源和计算资源，并基于快照序列图提出了一种满足端到端（E2E,End-to-End）时延需求的条件下使得网络收益最大化的路由策略。文献[27,31-32]采用了时间扩展图刻画空间信息网络拓扑的动态变化。其中，文献[27]和文献[31]采用时间扩展图联合表征了空间信息网络的通信资源和存储资源，并基于时间扩展图，文献[27]提出了一种满足E2E时延需求条件下完成任务优先级总和最大化的路由策略，文献[31]提出了一种在收发信机受限的条件下网络流最大化的路由策略；文献[32]采用时间扩展图联合表征了软件定义空间信息网络的通信、存储和计算资源，并基于时间扩展图提出了一种通信资源消耗最小化的路由策略。文献[18]提出了采用存储时间聚合图来表征时变的空间信息网络，并基于存储时间聚合图提出一种在满足E2E时延条件下网络流最大化的路由策略。文献[23-24]采用多功能时间扩展图来联合表征时变的软件定义空间信息网络的通信、存储和计算资源，其中，文献[23]基于多功能时间扩展图提出了一种在保障E2E时延需求条件下完成任务总数最大化的网络切片路由策略；文献[24]基于多功能时间扩展图研究了网络性能和网络协同开销之间的折中问题。

采用一个合适的时变图模型对于空间信息网络性能分析至关重要。因此，在后面章节中首先介绍了空间信息网络的特性，然后详细介绍了多种空间信息网络时变图模型建模方法，包括快照序列图、时间扩展图、存储时间聚合图和多功能时间扩展图，并且分析了它们的特征和优缺点。

1 空间信息网络的特性

空间信息网络是一个由同步轨道卫星、中轨道卫星、低轨道卫星和地面站等组成的多层立体的异构网络，如图1所示。与传统地面网络相比，空间信息网络具有如下特点：

图1 空间信息网络示意图

（1）网络拓扑时变性[22-23,27,31-32]：由于空间信息网络的卫星节点分布较为稀疏，并且卫星沿着固定轨道高速移动，使得卫星之间的通信链路间歇性连通，导致空间信息网络拓扑随时间发生动态变化[22-23,27,31-32]。因此，在空间信息网络中，很难保障节点之间实时存在端到端的传输路径，使得节点通常需要将接收的数据进行存储-携带-转发的方式传输给下一个节点[22,34-35]。

（2）网络拓扑可预测性[22-23,27]：由于卫星是在固定的轨道上移动，并且卫星的通信覆盖范围是可被精准计算，因此，空间信息网络拓扑动态变化是可预测的。

（3）网络资源动态、受限性[13,36]：由于卫星的尺寸、制造和发射成本、平台重量等限制导致卫星所携带的载荷数量和大小是十分有限的，其中载荷包括了收发信机、存储器、处理器等[13]。因此，空间信息网络的通信、计算和存储等资源是稀缺的[13,36]。此外，由于卫星在轨道上周期性高速运动，并且卫星之间的通信链路是断续联通的，导致空间信息网络的通信资源的可用性是周期性动态变化的[35]。

后面的章节将讨论空间信息网络时变图模型的建模方法，考虑一个示例空间信息网络，由4颗卫星组成，分别为v1,v2,v3和v4，如图2所示。在时隙[t0,t1)和时隙[t1,t2)中，卫星v1和卫星v2是联通的，但由于卫星的移动性，导致在时隙[t2,t3)中卫星v1和卫星v2通信中断。因此，空间信息网络的拓扑是动态变化且可预测的。目前，表征时变的空间信息网络的时变图主要包括：快照序列图、时间扩展图、存储时间聚合图和多功能时间扩展图，将在下面章节中逐一介绍。

图2 空间信息网络拓扑变化示意图

2 快照序列图

快照序列图主要通过一系列的离散时间上的快照来刻画时变网络拓扑的动态演进过程[33]，其中每个快照刻画了特定时间段内保持不变的网络拓扑，如图3所示，其为图2所对应的快照序列图。在图3中，蓝色有向线表示的是通信链路，其刻画了当前时隙中卫星之间或者卫星与地面站之间的通信机会，而通信链路上的数值表示的是该链路的通信容量，即在当前时间间隔内该链路能够传输的最大数据量。此外，快照序列图只可以表征时变网络中的通信资源。快照序列图的优缺点如下：

图3 具有三个时隙的快照序列图的示意图

（1）优点：由于快照序列图中的每个快照都可以视为一个静态图，因此，基于静态图设计的路由算法都适用于快照序列图中的每个快照，例如，可以通过Ford-Fulkerson、Edmonds-Karp等网络最大流算法在每个快照内求解端到端最大流[29,37]；还可以通过Dijkstra等最短路径算法在每个快照内求解端到端的最短路由[37]。此外，针对静态图设计的软件定义网络具有服务功能链约束（即从源节点到目的节点的任务流必须按照特定顺序依次接收服务功能）的路由算法同样适用于快照序列图中的每个快照[38-40]。

（2）缺点：由于在空间信息网络中节点稀疏且间歇性联通，使得在某些快照内节点间可能不存在端到端的传输路径，导致大量数据通常需要依靠存储-携带-转发的形式到达目的节点。但是，快照序列图只刻画每个快照内的网络拓扑变化，而忽略了各个快照之间的联系，即快照序列图只表征了时变网络的通信资源，忽略了存储和计算等其他资源。因此，基于快照序列图设计的路由策略网络性能差，资源利用率低[19,21-22]。

以图3为例来介绍快照序列图的网络性能，假设v1和v4分别为源节点和目的节点，从图3可以看出该快照序列图中的三个快照均不存在从v1到v4的传输路径，在时隙τ1内v1分别与v2和v3存在传输路径，而在时隙τ3内v2和v3均与v4存在传输路径，但是由于快照序列图没有考虑各个快照联系，导致v1无法给v4传输数据，即该网络最大流为0。因此，虽然快照序列图可以表征时变网络的动态演进过程，但是，快照序列图忽略了存储资源，造成资源利用低、网络性能差。

3 时间扩展图

时间扩展图是在快照序列图的基础上引入了存储链路，使得可以将离散时间上的快照连接起来，如图4所示，其为图2所对应的时间扩展图[29]。时间扩展图中每一层的节点对应相应时隙的网络节点的副本。时间扩展图中的链路可以分为两种类型，分别为通信链路和存储链路，如图4所示，蓝色有向线表示的是通信链路，而红色有向虚线表示的是存储链路，其中存储链路刻画了其对应的节点存储携带数据的能力。在图4中，存储链路上的数值表示的是该存储链路的存储容量，即其对应的节点能够存储携带的最大数据量。因此，在时间扩展图中，通信链路和存储链路分别表征了时变网络中的通信资源和存储资源。此外，时间扩展图的优缺点如下：

图4 具有三个时隙的时间扩展图的示意图

（1）优点：时间扩展图通过引入存储链路将各个快照联系起来，从而能够联合表征时变网络的通信资源和存储资源，可以有效提高资源利用率和网络性能[21,27]。具体而言，在一个时隙内如果一个节点接收的数据量大于其可发送的数据量，则其将发送完后剩余的数据量存储携带等待下一次传输机会再进行传输，从而可以充分利用网络资源并有效提高网络性能[21-22]。此外，时间扩展图通过引入存储链路，实现时变网络的静态化表征，因此，针对静态网络设计的大部分路由算法均可以直接适用于时间扩展图，例如Dijkstra最短路径算法、Ford-Fulkerson、Edmonds-Karp等最大流算法。

（2）缺点：时间扩展图只能联合表征通信资源、存储资源和节点只有单一的计算功能的计算资源，其无法刻画节点具有多个的计算功能的计算资源[19]。软件定义空间信息网络可以打通异构网络资源壁垒，实现网络的多维资源融合共享，从而提高资源利用率和保障不同QoS需求[17,21,23]。因此，软件定义空间信息网络在未来扮演非常重要的角色[21,23,32]。但是，在软件定义空间信息网络中，节点可以被部署多个不同的虚拟网络功能，并且任务流在节点上接收虚拟网络功能将消耗该节点的计算资源。然而，时间扩展图无法表征节点具有多个计算功能的计算资源，因此，时间扩展图无法表征软件定义空间信息网络任务流同时接收多个虚拟网络功能的场景[19,23-24]。此外，当时间规划周期和网络规模越大，时间扩展图的节点副本数量越庞大，使得所涉及的变量数剧增，导致求解优化问题的时间复杂度极高[21-22,27]。

4 存储时间聚合图

存储时间聚合图是将时间扩展图进行聚合表征，即将各个快照内的链路通信容量表示为链路容量序列，将节点在各个快照之间存储的数据量表示为存储转移序列，如图5所示，其为图4所对应的存储时间聚合图[18]。为了便于理解存储时间聚合图，以图5为例，从节点v1到节点v2的通信链路所对应的链路容量序列为(20,10,0)，其表示的是从节点v1到节点v2的通信链路在第一个快照和第二个快照内的通信容量分别为20和10，而在第三个快照内的通信容量为0，即在第三个快照内节点v1和节点v2不存在通信链路；节点v1所对应的存储容量为50，其表示的是节点v1在各个快照之间能够存储的最大数据量为50；节点v1所对应的存储转移序列为[0,0]，其表示的是节点v1从第一个快照到第二个快照之间，以及从第二个快照到第三个快照之间均未存储任何数据。因此，存储时间聚合图可以联合表征时变网络的通信资源和存储资源。此外，存储时间聚合图的优缺点如下：

图5 具有三个时隙的存储时间聚合图的示意图

（1）优点：存储时间聚合图将各个快照进行聚合表征，精简了图模型，从而降低了图模型的空间复杂度[18]。

（2）缺点：存储时间聚合图只能联合表征通信资源和存储资源，而无法表征计算资源。然而，在空间信息网络中大部分任务通常需要通信、存储和计算等多维资源相互协作。此外，针对静态图设计的路由算法无法直接适用于存储时间聚合图[18]，例如Dijkstra最短路径算法、Ford-Fulkerson、Edmonds-Karp等最大流算法。

5 多功能时间扩展图

多功能时间扩展图是在时间扩展图的基础上，将每个具有多个计算功能的节点进行虚拟分解为：一个虚拟子节点、多个虚拟功能节点和虚拟传输链路，如图6所示，其中虚拟子节点不提供任何计算功能，只起到中继作用；而每个虚拟功能节点只可以为任务流提供一种计算功能。以图2为例，假设v1和v4不提供任何计算功能，而v2和v3均可以提供两种不同的计算功能，因此，可以将v2和v3均虚拟分解为一个虚拟子节点和两个虚拟功能节点，而v1和v4保持不变，无需进行虚拟分解，从而可以获得如图7所示的多功能时间扩展图。

图6 功能节点虚拟分解示意图

多功能时间扩展图中的节点可以分为三种类型：非功能节点、虚拟子节点和虚拟功能节点，其中非功能节点表示的是不具有计算功能的节点，其可以提供通信资源和存储资源，如图7绿色圆圈所示；虚拟子节点可以提供通信资源和存储资源，但不提供任何计算资源，如图7蓝色圆圈所示；而虚拟功能节点只可以提供一种计算功能，如图7橙色方形所示。多功能时间扩展图中的链路可以分为三种类型：通信链路、存储链路和虚拟传输链路，其中，虚拟传输链路是将虚拟子节点和虚拟功能节点连接起来的链路，如图7绿色有向点虚线所示。此外，多功能时间扩展图的优缺点如下：

（1）优点：多功能时间扩展图可以联合表征时变网络中的通信、存储和计算资源。此外，多功能时间扩展图能够表征节点具有多个计算功能的计算资源，因此，多功能时间扩展图可以适用于刻画软件定义空间信息网络任务流同时接受多个计算功能的场景[19,23-24]。

（2）缺点：当网络规模和时间规划周期越大，多功能时间扩展图中的节点数量越庞大，则所涉及的变量数剧增，导致求解优化问题的时间复杂度极高[23-24]。此外，针对静态图设计的路由算法同样不适用于多功能时间扩展图[23-24]。

表1给出了各时变图模型特征对比情况。不同的时变图模型的特征不同，有各自的优点和缺点。时间扩展图和多功能时间扩展图都可以表征时变的空间信网络的通信、存储和计算资源，但是应用场景不同，选择的图模型也有所不同。具体而言，如果所考虑的空间信息网络场景，节点不需要提供多个计算功能，则采用时间扩展图表征时变的空间信息网络更加合适[20-21,25]。因为，与多功能时间扩展图相比，时间扩展图所涉及的变量数量相对较小，使得求解优化问题的时间复杂度相对降低。然而，如果所考虑的是软件定义空间信息网络场景，并且节点需要提供多个计算功能，则采用多功能时间扩展图表征时变的软件定义空间信息网络更加合适[19,23]。因为，时间扩展图无法刻画任务流在同一个节点上接受多个计算功能，而多功能时间扩展图能够表征节点具有多个计算功能的计算资源，并且能够刻画任务流在同一个节点接受多个计算功能的流守恒转化关系。因此，需要根据场景选择合适的时变图模型。

表1 各类时变图模型的特点

此外，虽然现有的时变图模型，例如时间扩展图和多功能时间扩展图，可以联合表征时变的空间信息网络的通信、存储和计算资源，但是还是存在一些不足。其中，最主要的问题在于时间扩展图和多功能时间扩展图在网络规模和时间规划周期很大时，其节点数量非常庞大，导致求解问题的时间复杂度极高。因此，在基于时变图模型的研究中，如何设计低复杂度算法求解问题，仍是亟待解决的问题。

6 结束语

空间信息网络是6G星地融合网络的一个重要组成部分，是各个国家的重要信息网络基础设施。空间信息网络具有全球无缝覆盖、远距离传输和不受地理环境限制等显著优点，在未来6G网络中担任非常重要的角色。但是，由于空间信息网络的卫星节点分布较为稀疏，并且卫星之间的通信链路间歇性连通，导致空间信息网络拓扑随时间动态变化。为了精准表征时变的空间信息网络拓扑变化和多维资源的时变性，可以采用时变图模型。目前表征时变的空间信息网络的时变图主要包括：快照序列图、时间扩展图、存储时间聚合图和多功能时间扩展图。不同的时变图模型的特征不同，有各自的优点和缺点。因此，需要根据应用场景选择合适的时变图模型。