基于启发式遗传算法的时分星间网络拓扑优化设计

田 露，向才炳，孙剑伟，李骏平

(1.中国电子科技集团公司 第十五研究所，北京 100083; 2.中国人民解放军32021部队，北京 100094)

0 引言

在全球卫星导航系统中，引入星间链路可以进行星间测距和星间数据传输，通过星间测距可以提高导航卫星的定轨精度，利用星间数据传输可以提高导航星历的更新频度，也可以减少全球布站的数量，因此，依托星间链路技术在空间建立星间网络是卫星导航系统必然的发展趋势。目前，国际上全球导航系统(GNSS) 都已加入或正在进行星间链路的建设，GPS 通过星间链路已经实现星座自主导航，并且可以保证系统自主运行180天，系统精度不会降低，极大地提高了系统的抗毁能力，我国的北斗系统也加入了星间链路。

北斗三号卫星工程星间链路网络是我国第一个在建的大型星地一体的空间信息网络系统，采用相控阵时分体制，是天地一体、具有精密测量和数传功能的动态无线网络[1]。

区别于传统的地面网络，卫星与卫星之间、卫星与地面站之间的相对运动导致星间链路拓扑持续快速地变化，这对网络的管理和使用提出了更高的要求。文献[2]通过对具有异轨星间链路的星间的能见分析，探索了建立异轨道星间链路的可行性，偏向于轨道理论研究，没有与工程实际相结合。文献[3]在进行星间可见理论分析的基础上，分别针对点波束和宽波束星间链路条件进行了链路分配研究，提出宽波束条件更适用于导航系统的星间建链。文献[4]就一种基于TDMA的双层混合型星座提出了一种时隙分配方案。文献[5]将星间测距需求作为一个约束，以星间通信的延时性能为优化目标，提出一种基于首次改善(FI)的本地搜索算法和基于模拟退火(SA)的启发式优化算法以对链路分配问题进行求解。文献[6]利用演化图对动态变化的星间网络拓扑结构进行建模，从而解决星座网络拓扑非连通状态条件下星座中任意两颗卫星间的最早到达路由问题。文献[7]基于演化图理论分别从最短路径、最先路径、最快路径三种不同的路径衡量指标进行了星间路由算法的研究。文献[8]针对基于时分捷变建链全球卫星导航网络特点及其数据传输要求，围绕其数据业务过程中的路由问题开展了研究。但是这些研究都没有兼顾导航系统测量和通信需求，对此，文献[9]考虑测量与通信之间的依赖关系，构建双层规划模型分别设计上层启发式星间测量链路贪婪搜索分配算法(RL-HGSA) 和下层基于全局“邻域”搜索的星间路由优化算法(ROA-SGN)，但是其计算路由的等待时延时并没有考虑发送时刻的不确定性。

本文提出一种将网络的链路层与网络层管理解耦合，提出一种基于启发式遗传算法的网络拓扑优化设计方法，并采用分时最短时延的路由算法。最后，对星间网络测量指标进行了统计分析，以星间数据传输和星星地数据下传作为星间网络数据传输的典型工况，对星间网络拓扑路由规划的结果进行了逻辑仿真，验证了算法的实用性和优越性。

1 问题分析

本问题针对的是GEO/IGSO/MEO多层混合星座场景，共30颗卫星。其中MEO轨道高度为21 000 km，轨道倾角为55°，构型为24/3/1的Walker星座，即卫星总数为24、轨道面数为3，相邻轨道面邻近卫星之间的相位因子为1。GEO的纬度选取分别为E80°，E110°和E140°的3颗卫星，而IGSO则选择倾角55°，纬度E116°，相位间隔120°的3颗卫星，并设置了2个时分体制地面站。

1.1 可见性约束

1.1.1 几何可见性约束

几何可见是最基本的建链前提条件，星间可见的影响因素包括卫星位置和天线扫描角。具体的判断条件如图1所示。

图1 星间几何可见

满足地球无阻挡条件：

(1)

d≤dmax

(2)

其中：dmax为两星之间的最大可视距离，Re为地球平均半径，h为大气层厚度。

满足卫星扫描角约束：

(3)

(4)

θ1≤α1

(5)

θ2≤α2

(6)

其中：θ1,θ2分别为卫星2和卫星1在对方本体坐标系中的视线锥角，α1，α2分别为卫星1和卫星2的天线扫描角。

对于卫星与地面站，它们互相可见的条件是卫星位于地面站外切水平面之上，并满足卫星波束扫描角度和地面设备波束截止角度的约束。

图2 星地几何可见

根据设置的轨道高度，地球整体都在卫星波束扫描角范围之内，所以只需计算地面设备波束的截止角度约束，计算方式如下：

(7)

ψ≥ψmin

(8)

其中：ψmin为地面设备的截止角。

1.1.2 链路可达性约束

受星上天线载荷的条件限制，星间几何可见的卫星可能由于天线的发射功率、天线增益、接收灵敏度、空间损耗等原因，星间信号可传输的极限距离小于实际几何距离，导致建链不成功，因此，在进行规划时，必须考虑链路可达性。

(9)

d≤dmax

(10)

1.2 体制约束

本文所设计的星间链路系统是基于TDMA体制下的，即在一个超帧内，将时间划分成若干个等同的时间片，称为时隙。在一个时隙内，卫星可以与在其可见范围内的某一颗卫星建立链路进行测量与数据传输。在每个时隙内，网络拓扑结构固定，整个卫星星座拥有许多条星间链路，这些链路相互独立互不干扰，每一条连接着两颗相互可见的卫星，它们可以通过链路进行测量数据传输，并且每颗卫星有且仅有一条链路。

以5个节点组成的10时隙时分网络为例，图3表示了时分体制的建链拓扑表达方式。图中第一行表示，在1时隙，节点1与节点5建链，节点2与节点3建链，节点4轮空。

图3 时分体制网络拓扑

对于一个卫星来说，在一个超帧的不同时隙，可以通过与不同的卫星轮流进行建链，以满足测量的多样性。但是在星间数据传输过程中，若路由所选链路的时隙与数据的传输时机距离较远，就可能因时隙等待造成较大的数据传输时延，在网络规划时应当给予充分考虑。

1.3 业务要求

导航星座星间链路承载着自主导航、精密定轨、时间统一等导航业务，这些业务对网络的测量和数传要求均不相同，本文取其在某工作模式下的指标要求如表1所示。

表1 导航星座指标要求

2 拓扑规划

拓扑规划是复杂星间网络的链路层规划，是网络层路由规划的基础，本文采取将二者解耦和的方式进行规划，在进行底层的拓扑规划时充分将业务数据传输要求纳入考虑范畴，在进行网络层路由规划时，以已有拓扑规划为基础进行路径选择，不再根据路由的结果返回修改拓扑规划。

拓扑规划的对象包括30个节点，且每分钟20个时隙，拓扑规划的链路≤600，并且存在很多约束条件，是一个多维多约束多解问题，无论是通过经验设定规则进行规划还是单纯依靠的通用智能算法进行搜索，都很难求得其确定的最优解，因此本方案采用启发式遗传算法将二者相结合，先通过理论分析制定拓扑规划的基本原则，给出一个能满足大部分需求的拓扑框架，以此作为初值，利用遗传算法对拓扑进行优化，来寻求其有限时间内能取得的局部最优解。

2.1 初步规划

通过对星座的仿真分析，有如下结论：

1) 全星座下，每一个MEO卫星都有8个MEO卫星与之永久可见。

2) 每小时内MEO都有大于等于12 个非永久可见卫星(包括GEO、IGSO和MEO)在本小时内与之持续可见。

通过对星座数据传输任务过程和拓扑规划过程的分析，有如下结论：

1) 境外-境内星间链路在星星地数据传输中起重要作用；

2) 境外-境内星间链路的时序排列与星星地数据传输时延息息相关；

3) 在进行拓扑表的规划时，存在先后制约关系，在排入可见的卫星对时，必须先检查拓扑表中该时隙下预排入的两个卫星是否空闲，如果任何一方已经建链，则本次排列不成功。故先排入的卫星配对排列成功的概率要比后排入的卫星配对排列成功的概率要高。

充分利用以上先验知识，本方案在进行初步规划时，制定了如下原则：

1) 排入的卫星配对必须在本周期内持续可见；

2) 优先排列境内-境外星间链路；

3) 优先为可见境内星较少的境外卫星安排境内-境外星间链路；

4) 优先排列永久可见链路；

5) 境内-境外星间链路尽量等间隔均匀排入，避免出现局部长时间无境内-境外链路的情况；

6) 对各卫星尽量安排与不同卫星建立星间链路。

规划步骤如下：

步骤1：进行可见性统计，本周期内持续可见方认为可见，并生成星间可见矩阵K；

(11)

K为0,1对称矩阵，N为节点个数，为卫星节点和时分体制地面站节点之和，ki,j为0表示节点i与节点j不可见，ki,j为1表示节点i与节点j可见。

步骤2：统计境内星集合，境外星集合，境外星的可见境内星集合；

步骤3：生成境外卫星按照可见境内星个数从少到多排序序列；

步骤4：统计生成永久可见的卫星配对；

步骤5：优先排列可见境内星较少的MEO境外星，将MEO境外卫星中境外-境内的可见配对，以间隔2个时隙的规律排入时隙表，在此步骤中，优先排固定可见的卫星配对，其次排仅本周期内可见的卫星配对。为避免重复建链，如果排列成功，则在可见矩阵中将该配对置0；如果该境外星的可见境内星不足，则选取已经排过的境外-境内链路重复建链。

步骤6：加入高低链路，将高低链路中境内-境外的可见配对间隔2个时隙排入时隙表，优先原则同上，如果排列成功，则在可见矩阵中将该配对置0。

步骤7：进行检查，如果境外-境内链路还有剩余没有排入的，较境外-境外链路优先排入，如果排列成功，则在可见矩阵中将该配对置0。

步骤8：排入星地链路，优先选取持续2小时可见且有空闲时隙的境内卫星与地面站配对进行建链。再次选取本周期内可见且有空闲时隙的境内卫星与地面站配对进行建链。如果排列成功，则在可见矩阵中将该配对进行置0。

步骤9：排入境外-境外链路，优先排入固定可见的卫星配对，其次排仅本周期内可见的卫星配对。如果排列成功，则在可见矩阵中将该配对进行置0。

至此，初步规划完成，基本构成间隔2个时隙有境内-境外链路的拓扑框架，同时还补充了境外-境外链路和星地链路。但是该拓扑框架中存在一些空闲时隙，并不能满足各项指标要求。

2.2 遗传算法优化

本方案采用经典遗传算法对拓扑框架进行优化，遗传算法是一种模拟生物进化规律适者生存优胜劣汰的遗传机制来实现的一种通用的随机搜索方法，过程介绍如下：

1)种群初始化：

本方案随机生成50个个体P，构成初始群体，每一个个体是一个N×3的矩阵:

(12)

其中:TN×1为时隙，SN×1为卫星1，DN×1为卫星2。个体P的含义为在原有拓扑框架的基础上，进行N次编辑修改，每次修改的含义为另ti时隙卫星si与卫星di进行建链；若si在ti时隙有建链对象，则进行拆链处理，同时将该时隙下si原建链对象的拓扑置为0；对卫星di的处理与之相同。

为了确保建链有效性，且不损失建链率，在随机生成个体时，必须满足2个条件，首先卫星si与卫星di在本周起内必须为可见配对，其次ti时隙卫星si与卫星di至少有一个为空闲状态，同时满足以上2个条件方为也可用个体基因，否则将重新随机生成。

2)适应度评估：

本方案采用综合指标评估准则，将链路空置率、星间不重复建链数均值，星间几何精度因子均值，星星地数据传输时延纳入综合指标，对指标值进行了归一化处理，在此，适应度值越小表示越优；

(13)

其中：第一项为全局链路空置率，E为全局链路空置率，意为空闲时隙占总拓扑表的百分比，ωe为链路空置率权值系数；

第二项为星间不重复建链数均值，Li为卫星i的星间不重复建链数，ωl为星间不重复建链数均值项的权值系数；

第三项为星间几何精度因子均值项，Pdopi,j为卫星i在j时刻的星间几何精度因子值，ωp为星间几何精度因子均值项的权值系数；

第四项为星间几何精度因子最大均值项，ωpmax为星间几何精度因子最大均值项的权值系数；

第五项为星星地数据传输时延项，Di.k为卫星i在k时隙要将数据传至地面站或者境内卫星的传输时延(本文仅统计时隙等待时延)，ωd为星星地数据传输时延项的权值系数。

以星星地数据下传为例进行星星地数据传输时延统计，涉及一层下传的路径选择规划，本文在此采用简化路由的方案进行选择，直接建链的卫星配对之间必然存在路由，境外星从任意一个时隙出发，要将数据传输至地面，有3种方式：

(1)传输至境内星，由境内卫星通过星地连续体制链路传至地面站；

(2)传输至境内星，由境内卫星通过星地时分体制链路传至地面站；

(3)传输至境外星，由其他境外星将数据转发至境内星，再传输至地面站；

由于本方案已经预设了间隔2个时隙的境内-境外链路，对于境外星来说，找寻当前时隙之后最近的境内星节点进行下传即可，本文在此基础上进行了增补设计，如果连续3个时隙以上没有找到下传时机，查找与之建链的境外星在该时隙之后的下一个时隙是否是下传时机，如果是，则可以通过该境外-境外-境内链路进行下传。

3)选择操作:通过个体适应度值从当前种群中选择一部分个体进行接下来的交叉，突变操作，本文采用锦标赛选择法。每次从50个个体中随机选取25个个体，从25个个体中选择适应度函数值最小的个体，进入下一代，重复50次，选出50个个体作为下一代的父本。

4)交叉操作:从50个父本中随机选择2个父本P1和P2，以一定的交叉概率，进行交叉操作，在进行基因交叉时，从1～N中随机选择3个交叉点c1，c2，c3，将3个交叉点对应的3个编辑项进行交换，将此交叉操作重复50次，得到50个子代个体。

图4 遗传算法交叉操作示意

5)变异操作：以较低的变异概率，对50个子代个体进行随机选择，并随机选择变异点，按照初代个体的生成原则重新生成对所选中个体变异点处的3个编辑要素(时隙，卫星1，卫星2)，生成新的子代个体。

6) 计算每个子代个体的适应度评估值，并记录群体极值、全局极值与对应个体。

7) 重复3)～6)步，直到完成所有迭代次数。

8) 将全局极值对应的个体作为编辑要素，对拓扑框架进行编辑修改，得到最终优化后的拓扑规划结果。

3 路由规划

在上述拓扑规划的前提下进行网络路由计算，与传统网络路由不同，时分体制下的路径规划与节点的传输起始时刻有关，以最短时延原则为例，从源节点A到目的节点B从不同的时隙出发有不同的最短时延路径。此外，在进行路径规划时，还必须考虑星上的跳数限制。

本方案采用遍历树的方法，步骤如下：

1) 根据拓扑表生成以卫星i为根节点的3级节点树结构；

2) 对节点树进行遍历，寻找卫星i到卫星j之间的所有可达路径；

3) 计算不同出发时隙下，所有可达路径的传输时延；

4) 选择最短时延对应的路径，时延相同的情况下，选择跳数较小的路径；

5) 将所有路径中的第一跳路径记录在路由表中；

6) 重复1)～5)步，计算全网任意2个节点之间的端到端路由。

4 仿真验证

为验证算法的可用性，在VS2016工程中进行了编码仿真，规划时间为2020-03-15 00∶00∶00～2020-03-15 06∶00∶00，星座构成为3GEO+3IGSO+24MEO，Ka地面站2个，S地面站3个，拓扑表周期3 600 s。

4.1 测量性能验证

遗传算法种群大小50，编辑点规模100，迭代次数100。

种群迭代过程中群体适应度极值和适应度均值变化如图5所示。

图5 群体适应度极值/均值变化图

可以看出，在种群迭代过程中群体的适应度极值在不断下降，均值下降7%，极值下降4%，有明显的优化效果。

最终的拓扑规划的适应度评估结果如表2～4所示。

表2 链路空置率

表3 星间不重复建链数均值

表4 星间几何精度因子均值

可以看出，该优化算法对拓扑表链路空置率、星间几何精度因子均有一定的优化效果，空置率提升约3.9%，星间几何精度因子提升约30%，星星地数据下传最大时延保持不变，星间不重复建链数指标略有下降，优化后拓扑表的星间不重复建链数，星间几何精度因子均满足测量各项指标要求。

4.2 数传性能验证

软件对路由规划结果进行了逻辑仿真验证，按照路由表进行数据传输，验证任意两个节点之间不同的出发时隙下，数据传输是否可达，数据传输的跳数和数据传输的时延。统计结果如下：

1) 任意两个节点之间数据均可达；

2) 端到端跳数在5跳以内，且各跳数比例如表5所示。

表5 端到端跳数比例

图6 端到端跳数分布

端到端跳数在4跳以内的占比达到98.02%。

3)端到端时延在60 s内，且比例如表6所示。

端到端数据传输时延在30s之内的占比达到97.72%。

4)星星地数据下传时延

按照本文2.2节中描述的星星地数据下传时机选取方案，对拓扑表进行了逻辑传输仿真，统计结果如表7所示。

表6 端到端时延比例

图7 端到端时延分布

表7 星星地数据下传传输时延 时隙

从表中可以看出：星星地数据下传传输最大时延保持3个时隙不变，平均时延有所减少，有一定的优化效果。

仿真结果表明，采用本文提出的启发式遗传算法对拓扑规划进行优化，并且采用最短时延原则的路由计算方法，其星间数据传输、星星地数据下传过程均满足业务数据的传输跳数与传输时延要求。

5 结束语

本文针对时分体制导航卫星星座的测量与数据传输要求，分析了网络规划的约束条件和业务要求，提出一种基于启发式遗传算法的网络拓扑优化设计方法，首先通过仿真分析制定了规划的基本原则，给出一个能满足大部分需求的拓扑框架，再以此作为初值，利用遗传算法对拓扑进行了优化，在此基础上采用了分时最短时延的路由算法，并进行了仿真验证，结果表明，拓扑路由规划结果能满足导航星座的常规业务。本文能为解决导航星座星间网络的复杂运行管理提供一种解决问题的思路，仿真验证过程未能将星上真实的处理过程纳入考虑，与实际工程尚有一定的偏差。