下载掌阅APP，畅读海量书库
立即打开
由于分布式路由可以克服网络动态拓扑对数据传输的影响，因此被广泛应用于动态环境中，如DTN、D2D（Device-to-Device）网络。然而，分布式路由需要网络中节点频繁交互，且不具有全局最优性，因此，为了克服网络动态性对路由策略设计带来的影响，基于时变图（Time-Variant Graph）模型的路由策略研究工作相继展开，例如，利用时变图模型对网络的动态拓扑结构进行建模、利用完备的时变图理论知识进行动态网络下最优路由策略的设计 [67] 。
图理论一直都是网络模型求解的基础工具，在地面静态网络发展的基础上，动态网络图理论的研究也在日益完善。在LEO星座网络中，星间链路或星地链路间的明显相对运动形成了网络的时变拓扑结构，节点之间的连接状态随时间不断演变，导致其链路呈现周期性中断。为了能够更好地捕获卫星网络的拓扑变化，时变图模型被广泛用于卫星网络拓扑建模 [66] 。时变图模型是一种用于表示时变网络资源及其关系的数学方式，也是解决动态网络问题的理论基础。时变图模型按照研究的拓扑结构是否可知，可以分为确知时变网络图模型和随机时变网络图模型，现在主要的设计都是基于提前可知的拓扑网络结构而设计的确知时变网络图模型，适用于随机时变网络的模型尚不多见。传统静态图仅表征了链路资源及节点的连接关系，时变图则增加了对节点存储资源、链路资源、节点连接关系等时变特征的联合刻画。当前，时变图模型可以分为两大类：离散时间的时变图模型和连续时间的时变图模型。离散时间的时变图模型将连续的时间范围划分为若干个时隙，每个时隙内存在一个相对静止的网络拓扑。因此，离散时间的时变图模型是从静态图演变而来的，并且先后经历了拓扑快照图、时间扩展图、时间聚合图、存储时间聚合图的发展历程。然而，将连续时间进行离散化处理，会导致网络时变特性的模糊化，划分时隙的大小及时隙的数量都将影响时变资源刻画的精准度，以及相应求解算法的复杂度。连续时间的时变图模型，则将链路或节点的时变特性利用时间函数来表示 [67] 。
1 ．快照图
拓扑快照 [68] 的主要思想是将动态网络拓扑的连续变化利用多个离散的静态拓扑图记录下来，每个静态图成为一个拓扑快照。多个拓扑快照按时间排序就可以表现出链路间的通断关系随时间的变化，即拓扑快照记录了动态网络各个节点间链路随时间变化的所有形态 [66] 。快照图的优点是时变拓扑在时间维度上进行离散化，每个快照子图均为静态图，传统图理论的算法均可以应用在快照图当中，例如，图的邻接矩阵表示方法、广度优先搜索、深度优先搜索、连通图、Dijkstra算法、最小生成树Prim算法、Kruskal算法、Sollin算法等。但是快照图的缺点也十分明显，其割裂了快照之间的联系，无法表征存储—托管—转发机制，导致资源浪费。快照图的快照子图数量与时间长度成正比，存储开销大；基于快照图的路由算法在所有的快照子图内重复寻找，路由算法效率低 [69] 。此外，由于卫星网络的断续连接特性，在一幅快照子图中可能没有端到端的路径，这样就给分析卫星网络拓扑造成了极大的困难。
2 ．时间扩展图
基于快照图的种种缺点，需要提出一类能够在时间维度上描述拓扑联系的图模型，称为时间扩展图（Time-Expanded Graph）。传统图模型只在某个静止时刻显示点的空间联系，而时间扩展图在空间联系的基础上，将每个离散的时间段内的快照子图的对应节点用存储链路相连接，可以表征存储—托管—转发机制。时间扩展图的优势在于将割裂的快照图联系起来，增加对于时变资源的表征，表征精准度高；它的缺点是当网络规模较大、拓扑快速变化时，时间扩展图缓存需求较大 [70] 。由于时间扩展图需要创建节点副本，同时，时间的离散间隔决定了图模型的描述精度，因此，当快照子图较多、网络规模较大时，时间扩展图占用的存储空间大，路由计算复杂度高 [66][71] 。此外，时间扩展图很有可能导致传统基于静态图理论的算法不能直接作用在时间扩展图上，需要依据特殊的场景做出合理的变形。
3 ．时空图/ 空时图
为刻画动态网络的拓扑变化，时空图（Space-Time Graph）采取的思想类似于数学上的微积分，利用足够小的时间间隔对所关注的时间区间进行离散。在这个时间间隔内，时变网络的拓扑被视为稳定的（实际上离散间隔代表网络维持稳定的最小时间段） [72] 。由于卫星网络的高动态特性，适用于地面网络的静态图建模方式显然不再适用于卫星网络，因为这样很难捕捉到连续变化的动态网络拓扑信息。目前，大多数文献采用时变图的建模方法。基于时空图的变形跨时隙有向图等。时空图的优点是连通了不同时刻快照子图之间的链路连接信息，缺点是不同子图之间的联系依赖于对子图的时隙划分精度，如果时隙划分过于精细则会导致大量的重复子图，增加大数据的存储负担，也为各种图理论的分析、路由算法的查找、缓存策略的设计带来一定的困难。
4 ．事件驱动图
不同于时空图对时间维度的离散化处理，事件驱动图（Event-Driven Graph） [72−74] 注重网络中的事件。在事件驱动图中主要包括两类事件：发送事件（Sending Event）和接收事件（Receiving Event）。事件驱动图以二元变量( v i , t ) 表示时变网络中的节点，称为事件节点（Event-Node），其表示了在不同时刻 t 时变网络节点 v i 的状态。若在 t 时刻存在节点 v i 与 v j 的（单向）连接，则称 v i , v j 分别与发送事件和接收事件关联。此时，可以在事件驱动图中添加连接事件节点( v i , t ) 与( v j , t ) 的有向边，称此类边为点间链路（Inter-Edge）。类似于时空图中的空间链路，点间链路主要用于描述数据的转发 [72] 。事件驱动图和时空图这类时间扩展图的缺点一样，随着网络规模或给定时间范围的增加，导致该类图模型存储量大且相关路由算法求解复杂度高。
5 ．时间聚合图
时间聚合图（Time-Aggregated Graph） [73] 将快照图聚合到一起，用链路权重序列表征链路的不同时段的权重。例如，当权重为链路容量时，链路权重序列即为表征不同时段的链路容量。时间聚合图模型无须节点复制，模型存储量小效率高，通过资源的聚合表征，降低图模型的存储复杂度，但是缺乏对存储资源的刻画，图模型表征精度低；一次路由计算可计算出时间扩展图中的多条路径，路由算法复杂度低。由于缺乏分时段链路与缓存之间制约关系的表征，时间聚合图无法求解网络最大流，原因在于该模型的精准度低 [69] 。
6 ．存储时间聚合图
目前的时变图模型可用于路由计算、网络吞吐量求解及网络多维资源规划，但是，现有时变图理论仅利用静态图、快照图、时间扩展图及时间聚合图进行时变网络分析与求解，因为图模型的高存储复杂度与低精准度，导致相应算法求解复杂或无法得到全局最优解，文献[74]提出存储时间聚合图（Storage-Time-Aggregated Graph）模型，在时间聚合图的节点上增加节点存储资源转移时间序列，设计了存储资源转移关系，精确表征了分时段链路之间的制约关系，获取了时变网络最大流，存储时间聚合图模型的精准度和高效性均优于上述图模型 [69] 。但是针对存储时间聚合图的高效求解算法的设计才刚刚起步，适用于时变网络规划、多播、稳健性设计的时变图模型不完善或缺失，适用于随机时变网络的模型也缺失。
7 ．时变连续图
天地一体化网络是一个典型的时变网络，同时由于卫星周期性的绕轨运动，网络拓扑变化、链路容量、卫星节点的缓存大小及运动周期等特性均具有可预测性。前面所述的图模型都是基于时间离散化进行分析得到的时变图，而离散时间模型的精度受限于时间离散的精度，同时还影响数据的存储空间大小、计算的复杂度等一系列问题。基于此，考虑连续时间情况下的图模型在时变网络中具有更加广阔的研究前景。文献[70]提出将天地一体化网络中的所有物理实体（如卫星、空间飞行器、地面站等）均描述为节点，而物理实体之间（如卫星与卫星之间、卫星与地面站之间）的连通机会等均描述为相应的链路。同时，将时变的链路带宽及连通机会按时间顺序刻画在对应的链路上，并将节点的存储能力也表征在节点处，基于此构建出连续时间的时变图模型和时变连续图（Time-varying Continuous Graph）。
时间确定性网络是一类重要的DTN类型，在多跳网络领域，时间确定性网络组网技术尚处于研究进程中，通过调度网络资源与业务保障业务的时延。时间确定性网络的设计挑战主要在于：①资源共享与时间确定性相矛盾；②资源表征无时间属性，确定性路由难构建；③多维资源未关联，时变资源利用率低。一直以来，关于时间确定性网络的研究也在卫星测控网、车联网、工业互联网、无人机测控网、传感器网络等场景中不断进行着，而卫星网络又是空间信息组网的重要组成部分。在关于卫星网络的研究中，时变图的应用是必不可少的 [66] 。基于时变图在时间维度上的扩展，时变图具有多种应用。DTN包括卫星网络、军事Ad-Hoc网络、传感器网络、车辆Ad-Hoc网络等。在空间通信中，由于空间通信设备的不断运动，导致网络拓扑结构不断发生改变，而时变图则可以连通动态网络拓扑的时间和空间特性，基于不同的网络性能优化指标（如通信时延、网络吞吐量、通信可靠性等）进行路由缓存算法的优化。例如，文献[75]中用一种基于时空图的跨时隙有向图分析LEO卫星网络中的缓存分发问题。文献[76]提出了一种拓扑驱动的更新离散图，通过使用定制的边容量来限制给定交付任务下TEDD的下界并给出路由方案。文献[77]用一个设计良好的时空图来描述具有相同数据量的交通事件的概率到达模型，提出了给定时延要求下的最小代价路由算法。文献[78]用时空图模型设计了一种最小成本约束的多路径路由算法，通过该算法找到的路径，一定数量的任务数据可以在可容忍的时延内以最小成本传输回地面站。文献[79]建立了一个基于事件驱动图的具有时间约束的最小费用流模型，该模型可以有效地描述地球观测星座的时变拓扑结构。文献[80]利用时空图模型，提出了一种时间演化的连通支配集（TCDS）算法，以构建一个主干网络，实现高效的拓扑控制，并具有3层网络的高时空可达性。文献[81]提出了一种新的事件更新图（EUG），用于捕获时域中的细粒度拓扑信息，在此基础上构造了一个最小时间演化覆盖集（MTCS），用于设计具有适当中间节点的网络缓存机制。文献[82]研究了无向时变网络中连续时间主体的平均一致性问题，并允许断开网络连接，提出了无限积分连通性的概念。
时变图在空间通信中具有多种多样的应用，主要还是依赖于其独有的连接时间和空间的表述特性，但不同类型的时变图在存储、计算等方面存在差异，因此，需要针对不同的场景选用相应类型的时变图。文献[83]提出了一种基于改进的时间扩展图的近似算法，以在完成多播传输的同时最小化能量消耗。文献[84]讨论了具有不完全数据和噪声通信链路的时变图上分布式一致性跟踪问题，通过将分布式卡尔曼滤波与一致性更新相结合，来处理时变网络拓扑。文献[85]研究了航天器网络中的拓扑控制问题，将时变航天器网络拓扑形式化为有向时空图。与现有的大多数静态图模型相比，研究所提出的模型包含了时间和空间拓扑信息，为了捕捉实际网络的特征，其将时空图模型中的链路按成本、效率和不可靠性进行加权。文献[86]研究了具有噪声通信链路的时变图上分布式一致性跟踪问题，所提出的算法中每个节点可以生成自己的局部跟踪估计，并在噪声链路上进行通信。