大规模小卫星网络中动态路由和通信资源的联合优化

Joint Dynamic Routing and Resource Allocation in Large-Scale Small Satellite Networks

摘要: 小卫星网络在现代通信中有着重要的作用，普遍应用于各种现代通信场景。由于随机传输需求和随机分组产生/到达，大规模小卫星网络中的流量模式变得复杂，而由于网络规模极大和小卫星资源有限，路由面临更大的挑战。传统的卫星路由算法试图利用时间离散图模型来利用可预测的卫星轨迹，无法应对这些挑战。动态路径路由成为提高网络性能和鲁棒性的关键路由技术之一，本文利用动态网络特性对信息路由问题进行三维建模，将端到端的带跳数约束的最短路径问题建模为0~1整数规划问题。由于难以刻画动态拓扑下的全局信息，我们采用时间切片对卫星位置和星间链路状态进行精确刻画，得到信息路由所需的网络拓扑。同时，我们采用基于“路由–切换”机制的路由算法对三维网络拓扑中的端到端问题进行求解，求解过程涉及一个带有跳数约束的最短时延路径问题，由于该问题为NP-hard，多数已有研究采用启发式算法进行近似求解，以牺牲求解精度来换取求解效率。我们采用基于拉格朗日对偶理论的BiLAD算法对该单约束最短路径问题进行求解，既能保证求解效率，又可以保证求解结果的最优性。在数值实验中，我们随机生成200个测试实例，实验结果显示，本文所提信息路由算法可以成功求解191个测试实例，和贪心算法相比求解成功率提高了约18%。

Abstract: Small satellite networks play an important role in modern communications and are widely used in various modern communication scenarios. Due to random transmission requirements and random packet generation/arrival, the traffic pattern in large-scale small satellite networks becomes complex, and routing faces greater challenges due to the extremely large network scale and limited small satellite resources. Traditional satellite routing algorithms attempt to use time-discrete graph models to exploit predictable satellite trajectories, but cannot cope with these challenges. Dynamic path routing has become one of the key routing technologies to improve network performance and robustness. This paper uses the characteristics of dynamic networks to model the information routing problem in three dimensions, and models the end-to-end shortest path problem with hop count constraints as a 0~1 integer programming problem. Since it is difficult to characterize the global information under dynamic topology, we use a combination of time slicing and dynamic grid models to accurately characterize the satellite position and intersatellite link status, and obtain the network topology required for information routing. At the same time, we use a routing algorithm based on the “routing-switching” mechanism to solve the end-to-end problem in the three-dimensional network topology. The solution process involves a shortest delay path problem with hop count constraints. Since this problem is NP-hard, most existing studies use heuristic algorithms for approximate solutions, sacrificing solution accuracy in exchange for solution efficiency. We use the BiLAD algorithm based on Lagrangian duality theory to solve the single-constrained shortest path problem, which can ensure both the efficiency of the solution and the optimality of the solution. In the numerical experiment, we randomly generated 200 test instances. The experimental results show that the information routing algorithm proposed in this paper can successfully solve 191 test instances, and the success rate of the solution is increased by about 18% compared with the greedy algorithm.

1. 引言

小卫星网络在现代通信中有着重要的作用，并在通信、导航、遥感等领域的应用越来越广泛，普遍应用于各种现代通信场景。因为小卫星网络具有高带宽低时延的优势和极大的经济潜力，越来越多的公司和组织计划构建大规模的小卫星网络以提供全球服务。然而，网络中需求的随机传输和数据包生成/到达的随机性导致了复杂的流量模式，同时由于卫星网络存在动态变化的拓扑结构、不稳定的链路、分布不均衡的用户和有限的资源等问题，这些问题容易导致严重的网络拥塞和高传输延迟，信息的高可靠低时延传输面临极大挑战。

随着用户需求的增长和通信技术的不断发展，信息路由对卫星网络的性能和可靠性要求也越来越高。动态多路径路由成为提高网络性能和鲁棒性的关键路由技术之一，该路由策略旨在根据网络状况和需求实时选择最佳的路径来提高网络性能和可靠性，其性能直接影响到整个网络的性能和效率[1]。已有的研究工作提出了多种动态多路径路由策略和方法。一些研究工作采用软件定义网络(SDN)技术来实现动态多路径路由。这些方法通过将网络控制平面与数据平面分离，实现了对网络的灵活控制和管理。例如，一种基于SDN的动态多路径路由策略被提出，通过实时感知网络状态和网络中交换节点的负载来及时调整端到端传输的路由，从而提高传输效率[2]。在低轨小卫星网络中，基于有限状态自动机(FSA)的动态容错路由被提出，将低地球轨道卫星网络发展为具有自适应容错能力的路由系统，以开发自适应容错系统[3]。文献[4]针对低轨小卫星星座网络中的时间变化拓扑，研究了时间变化拓扑模型，并引入多属性决策方法来计算每个链路属性的权重，以量化链路效用和实现动态路由。同样，为适应网络拓扑的时变性，一种新颖的时态网格模型被提出，用于描述大规模小卫星网络的时变拓扑结构，通过网格而非坐标来定位卫星[5]。在软件定义的卫星地面一体化网络中，文献[6]提出了联合优化虚拟网络功能(VNF)部署和路由规划的动态路由方案，将问题建模为一个整数非线性规划问题，考虑资源、VNF部署和时隙流量约束。此外，针对低轨/中轨小卫星网络的动态路由，文献[7]通过考虑链路状态、路由切换等因素，使用边界卫星源路由方案来优化路由，提出一种具有破坏抵抗能力的动态路由算法。另一方面，一些研究工作采用机器学习算法来实现动态多路径路由。这些方法通过学习网络的历史性能和拓扑信息，以预测网络状况并选择最佳路径，以提高网络的容错性和性能。例如，一种基于Q学习的动态分布式路由方案(QRLSN)被提出，用于解决低地球轨道(LEO)卫星网络中的路由策略计算和维护问题[8]。针对大规模低轨小卫星网络，文献[9]基于多智能体深度强化学习提出一种全分布式动态路由算法(FDR-MARL)，用以推导出最优的路由策略。文献[10]提出一种受限的多代理强化学习动态路由算法，首先将数据包路由问题建模为一个带有约束条件的最大化最小化问题，然后使用该算法在更新策略和拉格朗日乘数时对目标改进和约束满足进行平衡。

在中轨和IGSO网络的卫星星座中，文献[11]提出基于网络拓扑演化规律的卫星网络路由策略和算法。同时，低轨小卫星网络已被应用于车联网中，一种通过低轨星座卫星网络实现车联网的联合动态路由方法被提出，以应对车联网中的路径规划问题[12]。针对卫星地面一体化网络，文献[13]研究了联合动态路由和资源分配的方法。在卫星地面网络中，一些学者提出了基于虚拟成本的动态组播路由算法[14] [15]。

综上所述，卫星网络动态路由领域的研究已经涵盖了多种算法和策略，从传统的虚拟代价算法到基于SDN和强化学习的智能路由设计。这些研究为提升卫星网络的性能、容错性和整体效率提供了重要参考和支持。

然而，大规模小卫星网络路由技术仍面临着许多挑战。首先，由于随机传输需求和随机数据包生成/到达，这种方式导致了复杂的流量模式，传统的路由算法往往无法满足其性能要求，信息传输自适应实时优化调整将成为动态网络系统的必然需求。根据复杂网络理论，端到端路由平均跳数可以用来衡量网络的传输效率，端到端路由跳数越大，传输效率越低，网络吞吐量越小[16]-[18]。此外，随着卫星网络业务负载的快速增长，过多的路由跳数也会导致排队延迟过长[19]-[21]，严重影响网络传输性能。因此，如何减少端到端路由的跳数成为一个重要的挑战[22] [23]。文献[18]提出了一种用户驱动的大规模星群灵活有效的链路连接方法，以减少路由跳数，提高网络利用率。文献[24] [25]的作者提到，在相反方向的卫星之间可以建立临时星间链路(ISL)，这样可以显著降低网络的端到端路由平均跳数。这些研究都建立了动态和临时的ISL，以减少端到端路由跳数，提高网络传输性能。文献[26]提出了一种分布式低复杂度星地协同路由方法，其核心思想是每个节点在端到端跳数和排队延迟最小的约束下将数据包转发到下一跳节点。

其次，卫星网络的资源分配问题也是一个重要的研究方向，如何在有限的资源下实现高效的路由和通信是一个巨大的挑战。此外，随着小卫星网络的发展，如何保证其安全性和可靠性也引起了广泛的关注。

大规模小卫星网络的复杂流量模式和有限通信资源给问题的求解带来巨大的挑战，传统的路由算法无法处理这些挑战，本工作拟借助时间切片模型对卫星间的动态链接状态进行实时获取，并基于拉格朗日对偶理论，设计高效可靠的路由算法。本工作主要针对大规模小卫星网络中的动态信息路由问题进行数学机理分析，建立新的优化理论、模型与算法，并设计仿真实验。

2. 问题建模

由于随机传输需求的特点，小卫星网络中的数据包随机到达源卫星节点，并在周期性运转的卫星节点中选择下一跳进行信息路由，最终到达目的卫星节点，完成传输任务。因为卫星的周期性运转，实时确定卫星间的链路连接状态是非常困难的，于是，我们对时间进行切片，通过得到尽可能多的时刻的网络拓扑信息，来近似整个传输任务期间动态的网络拓扑信息。同时，我们考虑信息传输的跳数约束，通过尽可能少地进行下一跳卫星选择，节约通信资源，以应对超大流量、“爆发式”业务增长等极端通信场景。

2.1. 系统模型

针对大规模小卫星网络的动态信息路由问题，我们可建立如下网络拓扑模型。

Figure 1. Schematic diagram of dynamic network information routing for large-scale small satellite network

图1. 大规模小卫星网络动态网络信息路由示意图

我们以时间为横轴、空间为纵轴建立二维坐标系，将时间划分为$n$ 个时刻$t_1,t_2,t_3,\cdot \cdot \cdot$ ，时间间隔为$t_0$ ，每个时刻对应一个当前时刻的卫星网络拓扑。随机流量到达源卫星节点$v_1^1$ ，通过选择中继卫星节点将信息传输至虚拟节点$v_5$ 。在同一时刻，卫星节点若在彼此的通信范围之内，则卫星节点间存在通信链路。同一卫星节点在相邻的两个时刻内存在一条存储链路，目的卫星节点$v_5^1,v_5^2,v_5^3,\cdot \cdot \cdot$ 和虚拟节点$v_5$ 之间分别对应一条虚拟链路，虚拟链路对应的传输时延为0，见图1。

2.2. 数学模型

通过对问题的分析和建立基于时间划分的网络拓扑，我们可以得到大规模小卫星网络的动态信息路由问题的数学模型。

$\begin{array}{c}Min {\displaystyle \sum }_{v_i^t\in \mathcal{V}}x\left(v_i^t,v_i^{t+1}\right)\cdot t_0\end{array}$ (1)

$\begin{array}{c}s.t.{\displaystyle \sum }_{v_i^t\in \mathcal{V}}x\left(s,v_i^t\right)=1,\end{array}$ (2)

$\begin{array}{c}{\displaystyle \sum }_{v_j^t\in \mathcal{V}}x\left(v_i^t,v_j^t\right)+x\left(v_i^t,v_i^{t+1}\right)={\displaystyle \sum }_{v_j^t\in \mathcal{V}}x\left(v_j^t,v_i^t\right)+x\left(v_i^{t-1},v_i^t\right),\forall v_i^t\in V/\left\{s,d\right\}\end{array},$ (3)

$\begin{array}{c}{\displaystyle \sum }_{v_i^t\in \mathcal{V}}x\left(v_i^t,d\right)=1,\end{array}$ (4)

$\begin{array}{c}{\displaystyle \sum }_{v_i^t\in \mathcal{V}}{\displaystyle \sum }_{v_j^t\in \mathcal{V}}x\left(v_i^t,v_j^t\right)\le H+1,\end{array}$ (5)

$\begin{array}{c}{\displaystyle \sum }_{v_i^t\in \mathcal{V}}{\displaystyle \sum }_{v_j^t\in \mathcal{V}}{a}_{ij}^t\cdot x\left(v_i^t,v_j^t\right)\le t_0,\forall t\in \left\{1,n\right\},\end{array}$ (6)

$\begin{array}{c}x\left(v_i^t,v_j^t\right)\in \left\{0,1\right\},\end{array}$ (7)

其中决策变量$x\left(v_i^t,v_j^t\right)$ 表示路径是否经过链路$\left(v_i^t,v_j^t\right)$ ，若经过链路$\left(v_i^t,v_j^t\right)$ 则取为1，否则为0；$t_0$ 为划分时间片长度，$a_{ij}^t$ 为t时刻链路$\left(v_i^t,v_j^t\right)$ 对应的传输时延。目标函数(1)表示传输所需时间最短，(2)~(4)为流平衡约束，保证该模型找到一条完整的$s-t$ 传输路径，(5)为跳数约束，(6)保证t时刻开始的信息路由时间不超过时间片长度$t_0$ 。

3. 算法设计

BiLAD (Bisection-based Lagrangian Dual)算法[27]是一种用于求解单约束最短路径问题(SCSP)的算法。它基于拉格朗日对偶理论，采用了角度二分法的更新策略，以有效解决SCSP问题。该算法的核心特点是通过不断更新拉格朗日乘子，缩小角度间隔，从而确保在多项式时间内收敛，具有较低的时间复杂度。

SCSP问题要求在满足延迟约束的前提下，找到一条成本最小的路径。通过引入拉格朗日乘子，将问题转化为一个拉格朗日对偶问题，并通过最大化对偶函数来寻找问题的最优解。拉格朗日对偶理论的基本思想是通过求解拉格朗日函数来优化路径的选择，确保路径的成本和延迟满足约束。

BiLAD算法通过引入角度二分法来更新拉格朗日乘子。具体而言，原问题要求在满足延迟约束的前提下找到最小成本路径，BiLAD通过引入拉格朗日乘子$\lambda$ ，将目标函数改写为$\underset{p}{\min }\left[c\left(p\right)+\lambda \cdot d\left(p\right)\right]$ ，使得对于任一固定$\lambda$ ，都可以利用Dijkstra算法快速求解该无约束问题。同时，为了缓解$\lambda$ 值更新过程对解选择的敏感性，算法引入了几何角度$\theta$ 的概念，通过令$\lambda =\tan \theta$ ，将$\lambda$ 的取值区间映射到$\theta \in \left[0,\frac{\pi }{2}\right]$ ，在延迟–成本平面中，不同路径对应的点在等值线$c+\lambda d=\text{constan}t$ 上呈现出明显的几何结构。BiLAD在每次迭代中利用修改后的Dijkstra算法同时返回两条特殊的$\left(c+\lambda d\right)$ 最小路径：一条对应最低成本、一条对应最低延迟，这两条路径在(d, c)平面上分别代表了极端的成本与延迟平衡。接下来，通过Handler-Zang更新规则(即$\lambda =进而\theta =\text{arctan}\lambda$ )以及一个保护机制，保证更新后的角度区间始终包含对偶最优角度${\theta }^{\text{*}}$ 且区间长度至少按一个常数比例$\gamma$ 收缩，从而实现了区间的二分搜索。理论证明表明，这一策略使得经过k次迭代后角度区间长度不超过$\left(\frac{\pi }{2}\right)\cdot {\gamma }^{k-2}$ ，从而确保算法在$O\left(n\log n\right)$ 次Dijkstra调用内收敛，整体时间复杂度达到$O\left(n\log \left(n\right)\left(n\log \left(n\right)+m\right)\right)$ 。此外，通过对所有路径在(d, c)平面上的点集及其凸包性质的分析，可以证明最优路径对应于凸包上的某些顶点，其补充倾斜角区间提供了对偶最优解存在的充分条件；当出现“硬情况”(即对偶最优解与原始最优解之间存在差距)时，基于已获得的对偶最优信息，还可以通过扫描最优路径候选三角形进一步寻找原始最优路径，从而构成ExactBiLAD算法。这一特性使得BiLAD算法能够在多项式时间内收敛，从而解决了传统算法在大规模网络中计算效率低下的问题。通过数值结果验证，BiLAD在大多数QoS路由测试实例中，表现接近于最优解，并且与LARAC算法相比，性能相当或更优。

通过数值实验，BiLAD在许多实例中表现出色，尤其在大规模网络中，能够高效地找到接近最优的解。与其他精确算法相比，BiLAD在实际计算中具有更优的性能，尤其适用于大规模网络环境。

在动态网络拓扑之下，我们需要求解端到端的信息路由问题，找到一条满足跳数约束的最短传输时延路径。针对动态网络拓扑，我们采用设置时间切片的方式，对卫星位置和星间链路状态进行判断，建立三维的网络拓扑表。

算法1：基于BiLAD算法的小卫星网络问题求解算法

输入：G = (V, E)：网络拓扑图(节点集合V、有向边集合E)。s, t：源、目标节点。H：跳数上限。每条边(u, v)的成本c (u, v)，跳数视为1。

1) 初始化两条极值路径：仅最小化成本：运行Dijkstra (边权为c (u, v))，得到路径${\text{P}}_{+}$ ，记其成本为$c_{+}$ 、跳数为$h_{+}$ 。仅最小化跳数：运行Dijkstra (边权均为1)，得到路径${\text{P}}_{-}$ ，记其成本为${\text{c}}_{-}$ 、跳数为$h_{-}$ 。

2) 可行性判断：若$h_{+}\le \text{H}$ ，则直接返回${\text{P}}_{\text{+}}$ (已满足跳数约束)。若$h_{-}$ 仍大于$\text{H}$ ，则问题无解，返回“不可行”。

3) 拉格朗日迭代：令$\lambda \leftarrow \frac{c_{-}-c_{+}}{h_{+}-h_{-}}$ 。对每条边u, v)，定义综合权重$w\left(u,v\right)=c\left(u,v\right)+\lambda \cdot 1。$ 在此新权重下运行Dijkstra，得到候选路径${\text{P}}^{\text{*}}$ ，记其跳数为$h^{*}$ 、成本为$c^{*}$ 。若${\text{h}}^{\text{*}}\le \text{H}$ ，则返回${\text{P}}^{\text{*}}$ ；否则根据$h^{*}$ 与$\text{H}$ 的关系，更新${\text{P}}_{+}$ 或${\text{P}}_{-}$ ，并重复本步骤。

4) 收敛或退出：若在最大迭代次数内找到满足$h^{*}\le \text{H}$ 的路径则返回；否则输出当前最优近似解或报告“不可行”。

输出：${\text{p}}^{\text{*}}$ ：满足跳数约束的最优路径(若可行)；否则返回“不可行”。

4. 数值实验

根据设置的时间切片。每一时刻下的有向拓扑图特征描述如下：

节点数：100个；

有向边数：2500条；

边属性：时延(取值为5~30 s，5~10 s的边占比75%，10~20 s的边占比20%，20~30 s的边占比5%)，跳数(取值为1)；

网络拓扑动态变化时间间隔：6 s；

网络拓扑动态变化次数：20次。

根据每个数据包150 KB (转换为MB)和固定丢包概率(每跳2%)，分别计算吞吐量(MB/s)和总路径丢包率。

1) 根据上述生成的拓扑图，随机生成200次实验测试案例。

BiLAD算法与贪心算法的比较结果详细可见图2~6以及表1。

Table 1. Comparison of numerical experiments between BiLAD algorithm and greedy algorithm

表1. BiLAD算法和贪心算法数值实验对比情况

算法	实验测试用例数	平均求解时间(s)	成功求解数目	成功率(%)	平均时延(仅成功)
BiLAD算法	200	0.18	191	95.5	29.12
贪心算法	200	0.2	155	77.5	27.58

Figure 2. Schematic diagram of the successful solution of the BiLAD algorithm and the greedy algorithm

图2. BiLAD算法和贪心算法成功求解案例示意图

Figure 3. Schematic diagram of the running time of the BiLAD algorithm and the greedy algorithm

图3. BiLAD算法和贪心算法运行时间示意图

Figure 4. Schematic diagram of the frequency distribution of the running time of the BiLAD algorithm and the greedy algorithm

图4. BiLAD算法和贪心算法运行时间频率分布示意图

Figure 5. Schematic diagram of the data throughput of the BiLAD algorithm and the greedy algorithm

图5. BiLAD算法和贪心算法数据吞吐量示意图

Figure 6. Schematic diagram of the packet loss rate of BiLAD algorithm and greedy algorithm

图6. BiLAD算法和贪心算法数据丢包率示意图

5. 总结

由于随机传输需求和随机分组产生/到达，大规模小卫星网络中的流量模式变得复杂，而由于网络规模和小卫星资源有限，路由面临更大的挑战。传统的卫星路由算法试图利用时间离散图模型来利用可预测的卫星轨迹，无法应对这些挑战。本文利用网络特性对信息路由问题进行三维建模，将端到端的带跳数约束的最短路径问题建模为一个0~1整数规划问题。由于难以刻画动态拓扑下的全局信息，我们采用设置时间切片的方式对卫星位置和星间链路状态进行精确刻画，得到信息路由所需的网络拓扑。同时，我们采用基于“路由–切换”机制的路由算法对三维网络拓扑中的端到端问题进行求解，在求解过程中，涉及一个跳数最小的最短时延路径问题，由于该问题为NP-hard，多数已有研究采用启发式算法进行近似求解，以牺牲求解精度来换取求解的效率。此处，我们采用基于拉格朗日对偶理论的BiLAD算法对该单约束最短路径问题进行求解，不仅能保证求解效率，还能保证求解结果的最优性。

在数值实验部分，我们依据实际卫星通信场景，随机生成200个测试实例，实验结果显示，本文所提信息路由算法可以成功求解191个测试实例，而贪心算法仅能成功求解155个测试实例，求解成功率提高了约18%。这表明我们的算法不仅可以保证求解时间和结果的最优性，而且能够极大地提高求解成功率。

下一步我们准备将研究方法推广至空天地海一体化通信场景，根据动态拓扑的变化规律和通信节点间的链接状态，对该场景进行三维建模，并设计高效可靠的端到端信息路由算法，在节约通信资源(跳数受限)的约束下，对信息进行高可靠低时延传输。

未来的研究工作将致力于将本研究方法扩展到更贴近实际应用场景的层面。具体来说，我们计划在现有模型的基础上，进一步考虑卫星轨道扰动、卫星故障以及多业务场景下的服务质量要求。例如，在卫星位置的计算中，可以引入大气阻力、太阳辐射压力及地球重力场不均匀性等扰动因素，从而使得卫星的动态拓扑描述更加真实；同时，通过建立卫星故障模型，模拟因硬件故障或通信中断导致的网络拓扑突变，并设计快速重路由机制，以提高系统的鲁棒性和容错能力。此外，为了满足实际通信中对吞吐量、丢包率、能耗等多种指标的要求，有必要将这些指标融入成本函数，实现多目标优化，这将使得路由决策更加符合实际业务需求。另一方面，我们还计划探索分布式算法和基于机器学习的自适应方法，通过在线学习和预测，动态调整路由策略，以便在网络环境发生快速变化时能够及时响应。综上所述，未来研究将重点关注如何在动态、资源受限的卫星网络中构建更为精确和高效的拓扑描述模型，同时设计能够同时兼顾多重服务质量指标的路由优化算法，为构建下一代全球卫星通信网络提供坚实的理论基础和技术保障。