Page 68 - 《武汉大学学报（信息科学版）》2025年第9期

1796 武 汉 大 学 学 报 （信 息 科 学 版） 2025 年 9 月

2.2.3 网络的边连通度 3 链路规划算法
对于由链路规划矩阵 A 或其邻接矩阵 L 描述
的激光链路网络，可用图论中的边连通度来衡量 3.1 NSGA-II 算法
网络拓扑的稳定性。在由 S 个卫星节点构成的激 式（7）~式（11）描述的激光星间链路规划问
光星间链路网络 A 中，去掉任意 k - 1 条链路后 题本质上是一个带约束的多目标优化问题。多
所得的子网络仍然连通，去掉 k 条链路后不连通， 目标优化问题的一种处理方式是通过多目标的
则称 A 是 k 边连通图， k 即为网络 A 的边连通度， 线性加权转化为单目标优化问题，但不同目标函
记作 k( A) 或 k( L)。图 3 为边连通度示意图。由 数的量纲差异以及权重的确定都将直接影响最
优解的性能。另一种方式则是通过求解 Pareto 前
图 3 可知，当灰色链路断开，网络将不再连通。
沿，得到解空间中的非支配解集，从而避免一个
优 化 目 标 的 改 善 导 致 其 他 目 标 的 削 弱 。 文 献
［21］提出带精英策略的 NSGA-II 算法，因其计算
速度快、种群多样性高等优点被引入到微波星间
链路规划问题的求解中 ［22］ 。本文将其首次引入
到激光星间链路的规划问题中。在标准单目标
遗传算法基础上，NSGA-II 增加了父代和子代种
群合并、种群个体非支配排序以及拥挤度计算等
图 3 边连通度示意图 操作，最终得到 Pareto 非支配解集。
Fig. 3 Examples of Edge-Connectivity 在上述激光链路多目标规划问题中，任意两
个 优 化 变 量 A 1 和 A 2 的 Pareto 非 支 配 关 系 定
( )
( )
2.3 最优化模型
义为 ［23-24］ ：
兼顾导航星座的测距和通信需求，同时保证
1） A 1 支 配 A 2 ，当 且 仅 当 ∀i ∈{1，2}，都 有
( )
( )
链路过渡态下星座的对地通信，将激光星间链路
( ))
( ))
J i( A 1 < J i( A 2 ；
网络拓扑的规划问题转化为一个带有多约束条
( )
( )
件 的 多 目 标 优 化 问 题 ，相 应 的 最 优 化 模 型 可 描 2） A 1 弱支配 A 2 ，当且仅当 ∀i ∈{1，2}，都有
( ))
( ))
( ))
述为： J i( A 1 ≤ J i( A 2 ，且 ∃j ∈{1，2}，使 J j( A 1 <
( ))
ï ï ï ï A 1 ≤ i ≤ S PDOP J j( A 2 ；
ìmin J 1( ) = max P i
í （7）
ï ï A 1 ≤ i ≤ S 3） A 1 和 A 2 互不支配，当且仅当 ∃i ∈{1，2}，
( )
( )
ï ï min J 2( ) = max T i
î
( ))
( ))
( ))
̂ 使 J i( A 1 < J i( A 2 ，且 ∃j ∈{1，2}，使 J j( A 1 >
s.t. k[ L( A)] ≥ 1 （8）
( ))
J j( A 2 。
= 1,∀a i,d ≠ 0,1 ≤ i ≤ S,1 ≤ d ≤ D（9）
v i,a i,d
所谓非支配解集，即集合中每个解都是非支
j ∈{a i,d| 1 ≤ d ≤ D},∀i ∈{a j,d| 1 ≤ d ≤ D}∩ i ≠ 0
配 的 ，没 有 其 他 解 在 所 有 目 标 函 数 上 都 比 它 更
（10）
优。在非支配解集的基础上改进任何一个目标
S S
l
l
∑ i,j ≤ D, ∑ i,j ≤ D,∀1 ≤ i,j ≤ S （11） 函数，必然会削弱至少一个其他目标函数。拥挤
j = 1 i = 1
度即个体在种群中的分布密度，以个体邻域解构
上述规划模型以链路稳态拓扑规划矩阵 A
成的最小矩形的周长来衡量。拥挤度越大，表示
作为链路规划变量。优化的性能指标 J 1( A) 为卫
个体在目标空间中的分布越稀疏，有利于种群多
星测距链路的最大 PDOP，性能指标 J 2( A) 为星 样 性 的 保 持 并 且 避 免 算 法 过 早 收 敛 到 局 部 最
座对地通信的最大星间时延。约束条件式（8）为 优解。
当前链路规划周期过渡态拓扑的边连通度约束， NSGA-II 算法主要计算流程如图 4 所示，包
可保证当前链路周期过渡态下的星座整网连通 含以下 5 个部分：
和对地通信。约束条件式（9）为建链卫星之间的 1）初始化。生成规模为 N 的初始父代种群，
可见性约束。约束条件式（10）为双向链路约束。 并通过选择、交叉和变异遗传操作产生规模为 N
约束条件式（11）规定了各卫星的最大建链数量 的子代种群。
不超过搭载的激光终端数量 D。 2）非支配排序与拥挤度计算。将父代与子