密集低轨星座启发式星间路由算法设计

密集低轨星座启发式星间路由算法设计

杨敬文¹，张保庆²，孟维晓¹

（1.哈尔滨工业大学电子与信息工程学院，黑龙江 哈尔滨 150001；

2.北京电子系统工程研究所，北京 100084）

【摘  要】星间链路决定了整个密集低轨星座的通信性能，而基于链路连通性的路由算法发挥着不可替代的重要作用。为提高星间链路通信性能，基于Python程序语言设计了一种启发式星间路由算法，在路径带宽和最大容忍时延的双约束条件下，对路径开销与端到端时延的混合参数进行统筹优化。将遗传算法与蚁群算法动态融合，加速全局最优收敛过程、增强算法的稳定性。最后，通过星链星座参数实例进行了仿真，仿真结果验证了所提启发式星间路由算法的优越性。

【关键词】密集低轨星座；星间链路；卫星通信；多约束优化；启发式星间路由算法

doi:10.3969/j.issn.1006-1010.20240718-0001

中图分类号：TN927.2          文献标志码：A

文章编号：1006-1010(2024)09-0109-07

引用格式：杨敬文,张保庆,孟维晓. 密集低轨星座启发式星间路由算法设计[J]. 移动通信, 2024,48(9): 109-115.

YANG Jingwen, ZHANG Baoqing, MENG Weixiao. Heuristic Inter-Satellite Routing Algorithms for Dense Low Earth Orbit Constellations[J]. Mobile Communications, 2024,48(9): 109-115.

0   引言

最近几年，由于一箭多星发射技术与平板式卫星的快速发展，卫星的发射成本越来越低，同时出现了越来越多地面网络难以满足的场景，密集低轨星座的研发和部署掀起前所未有的热潮^[1-2]。密集低轨星座中卫星数量十分庞大，排布十分密集，两颗卫星之间存在众多路径，如图1所示。如何选择一条路径时延最短、路径开销最小的最优路径进行信息传输是值得研究的问题，选择一条更好的路径可以显著提升整个系统的通信性能^[3-4]。目前已有的面对密集低轨星座的路由算法结构都比较复杂，计算开销很大，收敛时间较长，这样会占用星上处理系统的大量资源^[5]。

为了解决上述问题，本文提出了一种启发式星间路由算法，通过对星间链路信道状态信息的刻画获得路由算法所需要的路径开销参数，然后分析了卫星网络的时延来源，综合考虑路径时延与路径开销两个优化目标对搜索到的路径进行评估。将结构简单的遗传算法与蚁群算法进行动态融合，目的是使得融合后的算法相比于单独使用蚁群算法大幅减少路径搜索时长。仿真分析后可知遗传算法与蚁群算法融合后，在不降低路径搜索效果的情况下可以显著降低迭代次数，减少算法运行时间。

1   信道状态信息刻画

1.1  大尺度衰落性能

星间路径传输损耗是影响链路通信质量的最大因素，其值往往能达到200 300 dB，路径传输损耗的具体数值进行仿真分析是必要的。

文献[6]中对路径传输损耗的理论计算式进行了推导分析，得到空间路径传输损耗表达式为：

式中：D为星间距离，单位为km，f为信号频率，单位为MHz。

以一条实际的异轨星间激光链路为研究对象，仿真分析2 h内的路径传输损耗变化情况，步长为1 min，信号频率为193 THz。仿真结果如图2所示：

从图中可以看出星间路径传输损耗的变化范围在259.826 4.1 dB之内，变化幅度较小且具有周期性，变化周期为绕地球半圈的时长。

1.2  星间多普勒频移分析

多普勒频移对星间通信链路的影响主要体现在两个方面，一方面是从星座图的角度来说，多普勒频移的存在增大了载波残留偏差，会导致星座图旋转，进而可能导致判决出错；另一方面是从采样的角度来说，存在多普勒频移时会导致采样点出现偏移，进而可能导致判决出错，增大误码率^[7]。

为了更好地分析两个移动卫星间的多普勒频移，绘制如图3所示多普勒频移分析示意图。根据多普勒频移计算公式^[8]可得：

式中：V_A，V_B分别为卫星A，B的运动速度，γ_A，γ_B分别为卫星A，B的运动方向与星间链路的夹角，λ为信号波长。

数据代入式(2)进行计算后可得如图4所示的分析结果图：

从图中可以看出星间多普勒频移的变化范围在-548～548 MHz之内，变化幅度较大且具有周期性，变化周期为绕地球半圈的时长。

1.3  混合传输时延与信道状态的评价指标

1.4  启发式星间路由算法

（1）遗传-蚁群算法的动态融合

遗传算法收敛较快，但是容易陷入局部最优，算法的结果随机性较大^[12]。蚁群算法相比遗传算法更不容易陷入局部最优，全局搜索能力更强，但是初始阶段信息素的更新较慢，收敛所需的迭代次数较多，算法运行时间较长^[13]。

由以上分析可以发现遗传算法和蚁群算法具有一定的互补性，将二者结合是具有可行性的。遗传-蚁群算法动态融合主要思路是先通过遗传算法在较少的迭代次数内找到可能存在的最优路径，然后根据遗传算法获得的信息在蚁群算法初始化的同时对信息素的浓度进行更新。

遗传算法与蚁群算法融合之后，对星间路由场景进行了有针对性地优化。

（1）全局搜索增强

本论文所提算法通过局部与全局的结合，减少了目前找到“最优”路径的信息素浓度，鼓励蚂蚁对别的路径进行搜索，增强了算法全局搜索能力。

局部信息素更新方式的表达式^[14]如下：

式中：下一时刻信息素的浓度，ρ为信息素挥发因子，为当前时刻信息素的浓度，为蚂蚁释放的信息素浓度，θ为加权因子。

全局信息更新方式的表达式如下：

式中：P^bs为最优路径。

全局信息素更新的会减少目前找到的最优路径的信息素浓度，鼓励蚂蚁对别的路径进行探索，这样避免了过早的陷入局部最优。

（2）多约束优化

如果搜索到的路径端到端时延小于最大容忍时延同时剩余带宽容量大于0，则使用式(14)进行计算，否则将使用惩罚函数进行计算^[15]。同时考虑时延和带宽，对端到端时延和路径开销进行优化。图5为算法流程图。

（3）动态调整启发式信息素参数

根据算法的迭代次数动态调整启发式信息素参数，在算法初期增加信息素重要性（alpha）以加强探索，随着迭代深入逐渐增加启发式重要性（beta）以加强开发。

2   密集低轨星座实例分析与算法应用

2.1  Starlink星座概述

（1）基本情况

本文的所有算法应用都基于Starlink密集低轨星座，所以有必要在此简单介绍一下Starlink的基本情况。

Starlink项目由埃隆马斯克所创办的SpaceX公司发起，目的是通过建设一个密集低轨星座实现全球的网络覆盖，项目的初期目标是首先实现美国本土的覆盖，在星座整体建设完成后实现全球覆盖，整体建设工期初步分为三期^[16]。表1是Starlink星座的建设计划表：

在2019年SpaceX公司再次向FCC提交了追加部署3万颗二代星链卫星的申请，这些卫星将部署在310～565 km的低轨道上，Starlink星座的卫星数量预计将达到4.2万颗^[18]。

Starlink卫星属于小卫星，一颗卫星重量仅约270 kg，卫星寿命仅5～7年，因其本身质量小，只能搭载约90 kg的有效载荷，采用平板型设计，实现一箭60星发射^[19]。

（2）卫星网络拓扑快照

为了更好地对一个时变拓扑系统进行路由选择，需要将卫星时变拓扑离散化，这就带来了一个如何对时间片进行划分的问题，常用的方式主要有等间隔划分和链路状态划分^[20]。

等间隔划分的优势在于划分方法较为简单，缺点在于时间间隔的选择较为困难，时间间隔较长时卫星网络拓扑可能已经发生变化，导致路由算法准确性降低；时间间隔较短时需要计算的网络拓扑时间片较多，增加了路由算法的计算复杂度。

基于链路通断状态划分的优势在于可以保证在一个时间划分内网络拓扑保持不变；缺点是在卫星数量较多时处于极区的链路切换会十分频繁，这样会生成许多持续时间较短且数量众多的时间片划分，增加了路由算法的计算复杂度。

据文献[21]的研究表明，对于Starlink低轨星座来说，在确定源节点与目的节点的情况下卫星网络的拓扑结构基本不变。又由于Starlink低轨星座中的卫星数量众多，所以本文选择等长时间间隔划分的方式对卫星时变拓扑进行离散化，然后路由算法对离散化后的拓扑网络进行路由选择。某一时间划分的卫星拓扑结构如图6所示。

2.2  算法应用与路径搜索

为了说明本论文设计算法的实际应用意义，考虑选择Starlink密集低轨星座为载体运行本论文所设计的启发式星间路由算法（GA-ACO），与传统的遗传算法（GA）和蚁群算法（ACO）相比较，说明本文所设计算法的优越性。

为了更好地展示三种算法的具体过程，现对GA、ACO和本文提出的GA-ACO的路径搜索过程进行仿真分析，卫星网络的拓扑结构如图6所示，源节点为3号卫星，目的节点为95号卫星，对某一时刻的卫星网络拓扑图进行路径搜索，分析结果如图7、图8所示。

观察三种算法的寻路过程可以发现遗传算法有较长时间适应度保持不变，这说明遗传算法容易陷入局部最优。蚁群算法在寻路过程中需要迭代多次才能收敛，找到最佳路径，而且运行时间较长。本文提出的启发式星间路由算法针对这些缺点进行了很好的解决，遗传算法搜寻的结果帮助了蚁群算法快速收敛，并且没有降低算法的搜索效果。

2.3  算法性能对比

为了更好地展示三种算法的具体性能，以20 s为时间间隔，获取20张卫星网络拓扑结构图以及相关数据，设定最大端到端时延容忍为200 ms，分别使用遗传算法、蚁群算法和启发式星间路由算法在20张卫星网络拓扑结构图中寻找最佳路径，获得400 s内的寻路参数指标变化结果如图9、图10、图11、图12所示：

对以上仿真结果的各项参数进行统计分析得到如表2所示统计分析结果：

由以上仿真结果可以发现遗传算法所搜寻到最佳路径的端到端时延、路径开销和适应度方差很大，很容易出现寻路失败的情况，路径搜索成功率只有73.7%。蚁群算法和启发式星间路由算法所搜寻到的最佳路径的端到端时延、路径开销和适应度变化趋势基本相同。在端到端时延方面由于有些时间划分的最小端到端时延都超过了最大端到端时延容忍，这样就会导致三种算法搜索到的最佳路径的端到端时延都超过了容忍值。在搜索时长方面，启发式星间路由算法的搜索时长在绝大多数情况下优于单独的蚁群算法与遗传算法，相比于传统的蚁群算法搜索时长减少了65.6%。总的来说将遗传算法与蚁群算法融合后在不降低搜索路径效果的情况下可以显著降低算法运行时间。

3   结束语

本文将传统的遗传算法与蚁群算法进行了结合，设计了启发式星间路由算法，采用了局部更新与全局更新相结合的方式，对传统蚁群算法的信息素更新方式进行了改进。优化后的启发函数不再只与单一的链路开销有关，而是与链路时延和链路开销加权混合的参量相关联；动态调整的信息素更新参数在迭代初期帮助快速收敛，在迭代后期帮助扩大搜索，有效解决了路由过程中存在的环路问题，显著提升了路径搜索成功率和路径搜索时长。由于人工智能的快速发展与广泛应用，对密集低轨星座路由算法的研究可以考虑与先进的人工智能算法紧密结合，进一步提升算法能力。