具有星间链路的导航星座重构研究

程竟爽 何善宝 林益明 谢军

（北京空间飞行器总体设计部，北京 100094）

1 引言

利用星间链路，导航星座可以支持星地联合定轨与时间同步、全球星座实时测控管理，并实现导航星座自主导航等功能，提高了地面对系统的管理能力，增强了系统的自主运行能力［1］。导航星座在运行过程中，卫星节点及星间链路设备会由于故障或维护而出现失效情况，导致星座与星间网络拓扑原有的性能下降，须对其进行重构。如何优化设计重构后的星座构型与网络拓扑，使星座综合性能得到最优恢复，而重构风险则处于可接受的范围内，是一个需要研究的问题。

目前，针对星座的重构研究多集中在无星间链路的星座构型设计［2-4］上，对于具有星间链路的星座重构的研究较少。文献［5］研究了具有星间链路的星座设计问题，考虑了星间链路的性能因素，但未对网络拓扑进行优化设计。文献［6］研究了具有星间链路的通信星座重构问题，提出了“补网”的基本策略，但仅考虑到网络的连通性，与导航星座网络的设计目标有较大差别。

本文提出了一种基于遗传算法的优化设计方法。将星座构型重构设计与星间网络拓扑设计统一考虑，以星座导航服务性能、网络测距与通信性能，以及星座与网络的重构风险程度为设计指标，建立了导航星座的综合重构优化设计模型，并以遗传算法为基本手段实现综合重构优化设计。仿真分析表明，重构后网络性能得到一定程度的改善，满足重构策略的期望。

2 具有星间链路的导航星座重构优化设计问题

具有星间链路的导航星座重构优化设计问题，可以表述为寻找重构后的卫星轨道参数和各星之间的网络拓扑，使得形成的星座构型和星间网络具有良好的综合性能。本文只考虑卫星在同一轨道面内轨道机动实现星座重构，因此只将各卫星的相位角集合C作为设计变量。星间网络可用包含卫星节点集合V和星间链路集合E的图G（V，E）描述，其拓扑可用图的邻接矩阵U表示［7］，uij为U中的元素，表示节点i、j间的连接关系，若i、j建立双向链路，则uij＝uji＝1。

2．1 设计目标

具有星间链路的导航星座重构优化设计目标，是尽可能地恢复星座及星间链路性能，同时其重构的风险最小，设计目标包括性能目标函数和重构风险函数。

1）性能目标函数

导航星座的地面定位性能常用对地位置几何精度因子（Position Dilution of Precision，PDOP）值来描述。记对地PDOP值为ρ，可采用ρ＜6的区域百分比（f1）作为定位性能指标。即

式中：A为总的服务区域面积；Ⅰ为5°仰角条件下满足ρ＜6约束的区域个数，Ak为上述区域中第k个区域的面积。

与通信星座不同，导航星座的星间网络承担了测距和通信的双重功能［8］，其性能目标函数包括以下几个方面：

（1）网络测距性能的指标之一是网络测距量数目（f2），指一个定轨周期内网络包含的星间测距量总数目。若整个定轨周期中网络拓扑为稳态拓扑，则测距量数目可以由网络的链路数目描述。即

式中：n为星座中卫星节点数目；uij表示节点i，j之间的连接关系。

（2）网络测距性能的另一方面是网络的测距构型性能，可由星间PDOP值来描述。记节点的星间PDOP值为σ，可用网络各节点σ＜3的平均时间百分比（f3）作为网络测距性能指标。该指标是指一个定轨周期内网络各节点σ＜3的时间占定轨周期T的时间百分比的平均值，即

式中：tσi＜3为节点i在整个定轨周期T内满足σ＜3的总时间。

（3）网络通信性能可由网络平均距离来描述，指一个周期内网络各节点间最小路径长度的平均值。本文将其简化为各节点间的平均最小跳数（f4），即

式中：N为网络各节点间存在的最短路径总数；dij为节点i、j间最小跳数。

2）重构风险函数

星座及星间网络的重构风险目标函数，包括参与轨道机动的卫星数目f5和重构前后的链路变化率f6，反映了星座及星间网络的重构风险。

将各目标函数fi表述为归一化最大值形式f′i，利用相应权重因子Wi加权为单一目标F，即

2．2 数学模型

具有星间链路的导航星座综合重构优化设计问题描述如下：

式中：ci，cj分别表示节点i、j所处轨道面内的相位，Pi、Pj为节点i、j所处轨道面编号。式（7）为星座构型约束，表明星座中各卫星之间应避免碰撞风险；式（8）为链路的可建性约束，表明i、j之间建立链路须满足星间可连性eij；式（9）为网络连通性约束，表明各节点间至少存在一条连通路径；式（10）为网络节点度约束和网络2-连接约束［9］，表明节点i建立的链路数目不超过天线数目ki，且任意节点的链路数目不少于2，以保证网络的稳健性。

3 星座重构优化设计的遗传算法实现

3．1 整体算法

如图1所示，星间网络重构优化设计的整体算法流程如下：①设定星座的故障模式；②产生一个初始化的星座构型染色体群；③针对染色体群中每一个染色体代表的星座构型，优化设计网络拓扑；④根据星座的服务性能与该构型下最优网络的拓扑性能，计算综合适应度；⑤执行染色体群的选择、交叉、变异操作。迭代执行上述遗传学操作，直至迭代次数达到一定次数时终止，最终得到最佳的子星座构型与网络拓扑。

图1 具有星间链路的导航星座重构优化设计流程Fig．1 Flow chart of reconfiguration optimization of navigation constellation with inter-satellite links

3．2 网络拓扑优化设计

上述算法流程中，涉及到网络拓扑的优化设计。网络拓扑优化的算法流程如下：

（1）根据星座构型，更新星间可见性等网络拓扑约束。

（2）初始化网络拓扑染色体种群。在满足可连性约束前提下，首先利用最小生成树算法生成网络的最小支撑树，以确保网络的连通性；检验网络是否满足节点度约束和2-连接约束，如果不满足，则利用相应的修补算子进行修补操作；最后对网络补充新链路直至接近饱和状态，以保证链路数目的近似最大化。

（3）选择、交叉和变异操作。其中变异通过“分支-交叉”操作实现，以减少非可行解的产生。交叉变异操作需要经过链路可连性约束的判断，若不满足约束，则需要重新执行操作。

（4）对染色体个体进行约束条件的判断。若违反约束条件，还需要进行相应的修补操作。

（5）采取精英保留策略，使最优个体保留至下一代群体中。反复执行上述操作直至迭代达到一定次数。

其中，步骤（2）与步骤（4）涉及到网络拓扑的修补操作，如图2所示。

图2 网络拓扑修补操作示意图Fig．2 Illustration of network topology repair operation

针对网络节点度约束的修补操作步骤包括：找出所有违反约束的节点集合；随机选择该集合中的任一节点，删除与之关联的一条边；判断是否违反连通性约束，若违反约束，则根据各节点度与链路可建性约束随机添加一条新边，使网络连通；更新节点度后，对其他节点重复上述操作直至该集合为空集。

针对网络2-连接性约束的修补操作步骤包括：找出所有违反约束的节点集合；选择该集合中的任一节点，寻找可与之建立链路且节点度不小于2的节点集合，随机选择其中一点并删除与之关联的一条边，该边删除的前提是对应端点的节点度大于2；建立新的链路；更新节点度后，对其他节点重复上述操作直至该集合为空集。

4 星座重构设计算例

4．1 仿真环境

本文假设全球导航星座采用Walker 24／3／2构型的星座，轨道高度20 200km，偏心率为0，轨道倾角55°，各轨道面升交点赤经相隔120°。全配置星座的星间网络采用类似网状的星间链路［10］，每颗卫星最多可建立3条链路，分别与同轨相邻两颗卫星建立同轨链路，与异轨道面一颗相邻卫星建立异轨链路。整个网络的拓扑结构如图3所示。

图3 网状星间网络的拓扑结构Fig．3 Topology of mesh-shaped satellite network

根据对导航星座及网络可靠性的初步分析，出现3颗以下卫星故障、3条以下链路故障的概率较大。设定故障模式为3 颗卫星故障和3 副天线故障，根据失效性能分析，当编号为11、25、32卫星故障时导航服务性能最为恶劣，故选取上述3颗卫星为故障卫星。故障天线编号为18、28、35卫星的天线，故障链路编号为（17，18），（27，28），（26，35）。此时，编号为18、26和27的三颗卫星与主卫星网络的链路均中断，3颗卫星脱离网络形成一个孤岛，是一种较为恶劣的故障工况。

4．2 结果分析与讨论

优化算法的参数设置为：种群规模Np＝100，最大迭代次数M＝100，交叉率pc＝0．6，变异率pm＝0．1。各优化目标的权重因子w＝［1／6，1／6，1／6，1／6，1／6，1／6］，反映了对星座与星间网络性能的综合优化设计。经过优化后得到的最佳星座重构方案为：编号为23的卫星由120°机动至216°，编号为35的卫星由240°机动至114°，此时ρ＜6的区域百分比提高到100%，重构后的对地PDOP峰值分布如图4所示。

图4 重构后星座对地PDOP峰值分布Fig．4 Distribution of maximum PDOP after reconfiguration

利用本文方法得到最优重构拓扑，重构前后的网络拓扑如图5所示。

图5 重构前后的网络拓扑结构比较Fig．5 Comparison of network topology before and after reconfiguration

网络拓扑重构前后的性能如表1所示。

表1 混合故障下的星座与网络拓扑重构前后性能比较Table 1 Results of constellation reconfiguration in case of mixed failure

由表2可以看出，经综合优化重构设计后，星座的ρ＜6区域百分比由48．18%提高到100%。重构后的网络拓扑使原先被隔离的卫星重新接入网络，恢复了网络的连通性，网络链路数从27条增加到31条，提高了σ＜3时间百分比，缩短了通信时延，从而改善了网络的测距与通信性能。同时，只进行了5条链路的切换，降低了链路切换的风险。星座和网络拓扑性能同时得到优化，说明了此方法的有效性。

与无星间链路的星座重构设计结果［2］相比，本方法得到的子星座构型的ρ＜6区域百分比性能，同样达到了100%，这说明此重构方案收敛到众多无星间链路的星座重构方案其中之一。造成这种现象的原因是无星间链路的星座重构设计仅考虑星座性能的优化，可选方案较多；而有星间链路的设计则需要综合考虑星座与星间网络的性能，其星座的优化空间受到一定的限制，因而导致可选方案收敛。

5 结束语

本文针对具有星间链路的导航星座重构优化设计问题，建立了相应的数学模型，并提出基于修改的遗传算法处理该联合设计问题，以得到重构后的最佳星座构型与星间网络拓扑。利用该方法，针对Walker 24／3／2构型星座在3星故障与3条链路故障的混合故障下进行了优化设计。对重构前后的星座与网络拓扑性能比较可以看出，该方法能够有效恢复星座与星间网络的性能，恢复星座的服务性能与网络的连通性，改善网络的测距与通信性能，而且实现重构的卫星数目和链路切换数目较低，因此，这是一种有效可行的设计方法。

（References）

［1］林益明，何善宝，郑晋军，等．全球导航星座星间链路技术发展建议［J］．航天器工程，2010，19（6）：1-7

Lin Yiming，He Shanbao，Zheng Jinjun，et al．Development recommendation of inter-satellite links in GNSS［J］．Spacecraft Engineering，2010，19（6）：1-7（in Chinese）

［2］胡伟，王劼．基于遗传算法的全球导航星座重构研究［J］．宇航学报，29（6），2008：1819-1823

Hu Wei，Wang Jie．The research on global navigation constellation reconfiguration based on genetic algorithm［J］．Journal of Astronautics，2008，29（6）：1819-1823（in Chinese）

［3］Weck O de，Neufville R de，Chaize M．Staged deployment of communications satellite constellations in low Earth orbit［J］．Journal of Aerospace Computing，Information and Communication，2004，1（3）：119-136

［4］Ferringer M P，Spencer D B，Reed P．Many-objective reconfiguration of operational satellite constellations with the large-cluster epsilon non-dominated sorting genetic algorithm-II［C］／／Proceedings of IEEE Congress on Evolutionary Computation．Throndheim，Norway：IEEE，2009：340-349

［5］张艳，张育林．具有星间链路的星座相位设计［J］．宇航学报，2004，25（6）：669-689

Zhang Yan，Zhang Yulin．Phase design of constellation with inter-satellite links［J］．Journal of Astronautics，25（6），2004：669-689（in Chinese）

［6］Chen Xiaoyan，Han Chao．Reconfiguration ofcommunications constellation with ISLs：Fix the net［C］／／Proceedings of the International Conference on Consumer Electronics，Communications and Networks．Xianning，China：IEEE，2011：1540-1543

［7］徐俊明．图论及其应用［M］．合肥：中国科学技术大学出版社，2010

Xu Junming．Graph theory with applications［M］．Hefei：Press of University of Science and Technology of China，2010（in Chinese）

［8］石磊玉，向为，唐小妹．一种兼顾卫星导航系统星间观测及通信的链路分配算法［J］．宇航学报，32（9），2011：1971-1977

Shi Leiyu，Xiang Wei，Tang Xiaomei．A link assignment algorithm applicable to crosslink ranging and data exchange for satellite navigation system［J］．Journal of Astronautics，32（9），2011：1971-1977（in Chinese）

［9］玄光男，程润伟．遗传算法与工程优化［M］．于歆杰，周根贵，译．北京：清华大学出版社，2004：148-160

Gen Mitsuo，Chen Runwei．Genetic algorithms and engineering optimization［M］．Yu Xinjie，Zhou Gengui，translated．Beijing：Tsinghua University Press，2004：148-160（in Chinese）

［10］Barnhart C M，Ziemer R E．Topological analysis of satellite-based distributed sensor networks［J］．IEEE Transactions on Systems， Man，and Cybernetics，1991，21（5）：1060-1070