基于改进遗传算法的导航卫星星间链路网络动态拓扑优化技术

韩凯,董日昌,邵丰伟,龚文斌1,,*,常家超

1. 中国科学院大学,北京 100049 2. 中国科学院 微小卫星创新研究院,上海 201210

卫星导航系统作为重要的国家战略基础设施,提高其可靠性和系统性能具有重要意义。星间链路(Inter-Satellite Links, ISLs)作为全球导航卫星系统(Global Navigation Satellite Systems, GNSS)的重要组成部分,为监控站分布受限情况下的星座定轨提供了一种有效方法。星间链路的作用主要包括星间测量和星间通信。

当前,卫星导航系统的星间链路主要包括微波链路和激光链路。相较激光链路,微波链路的发展与应用更早。美国的GPS率先实现了UHF (Ultra High Frequency)星间链路,并逐步向更高频段的星间链路发展。其中,射频窄波束天线与宽波束天线相比具有指向灵活、抗干扰能力强、测距精度高等优势。近年来,高速率、高容量、高精度的空间激光通信开始应用于星间链路。欧洲航天局(European Space Agency, ESA)主导的Sentinel-1A环境监测卫星与Alphasat通信卫星成功开展了激光星间链路实验。但由于其复杂的设计,激光链路在全球导航卫星系统中的应用需要进一步验证。本文主要针对Ka射频波段窄波束星间链路开展研究。由于卫星平台和星间链路硬件数量的约束,卫星所装配的星间链路天线的数量远少于该卫星当前的可见卫星数量。当卫星只装配有一个天线时,卫星网络的连通性是不连续的,只有 ISL在不同的时隙进行切换才能实现卫星网络之间的互相连通。因此,导航卫星网络是典型的延迟/中断容忍网络(Delay/Disruption Tolerant Networks, DTN)。DTN的动态变化特性使得导航卫星网络需要在不同的时间切换星间链路,而星间测距作为卫星导航系统的重要功能之一,星间链路的数量和分布影响着导航定位的精度。因此,优化星间链路的动态拓扑网络是实现高精度导航定位中至关重要的问题。

针对星间链路拓扑优化问题,国内外学者已广泛开展了相关研究。文献[7-9]采用“永久链路+非永久链路”的思想实现卫星导航系统的链路分配。其中,文献[7]提出了一种多层链路拓扑及混合路由设计方案,按照持续可见链路为主和非持续可见链路为辅的原则,采用基于代价函数的非持续链路选择方法实现了星间链路拓扑方案的生成。文献[8]针对非永久链路提出了基于几何精度因子(Geometric Dilution of Precision, GDOP)贡献值的设计方法,实现了任意MEO (Medium Earth Orbit)定轨精度的平均空间位置精度因子(Position Dilution of Precision, PDOP) 小于2.2的技术指标。文献[9]以可见卫星距离和俯仰角作为约束原则为非永久链路进行分配。

文献[10-14]以通信性能作为优化目标,对星间链路分配做出优化。其中,文献[10]提出以通信时延作为优化目标、以星间测距最优性能和卫星间关系为约束条件的优化问题,从而对链路拓扑结构进行优化。文献[11]基于最小生成树理论提出一种混合导航星座的链路分配算法,将GEO卫星为核心传输节点,首先分配通信成本较低的星间链路,然后通过迭代为所有可见卫星至少分配一次。通过仿真分析,降低了全网平均通信时延。文献[12]将星间测距需求作为一个约束,以星间通信的时延性能为优化目标,利用基于首次改善的本地搜索算法和基于模拟退火的启发式优化算法对链路分配问题进行求解,并提出了一种基于分支交换策略的新链路分配生成方法。文献[13]提出了一种基于目标评价函数进行负载均衡的网络拓扑优化方法,并以网络时延和接入能力为指标进行验证。文献[14]提出了有限状态自动机(Finite State Automation, FSA)的思想,以卫星的负载均衡为优化目标,通过两步启发式算法解决了不确定多项式(Non-deterministic Polynomial, NP)完全混合整数优化问题,并使用模拟退火算法迭代计算。然而,上述研究在链路规划问题中只考虑了通信指标,并未考虑卫星导航系统的测距定位需求。

文献[15-18]在链路拓扑优化中除了考虑通信指标的要求之外,同时也将测距性能加入优化模型中。文献[15]中以PDOP和传输时延分别为测距性能和通信度量,使用Blossom算法来获得每个时隙中的链路最大匹配,并使用非支配排序遗传算法II生成与优化整个时隙的卫星序列。文献[16]以网络时延和PDOP作为通信性能和高精度测量的量化指标,提出了一种基于多目标模拟退火算法的改进算法求解,并在某卫星或某条激光链路失效时进行动态优化。此外设计了一种避免冲突的链路交叉算法,改进了多源最小时延路由算法。文献[17]采用双层规划求解兼顾测量与通信的星间链路设计,其中上层采用启发式星间测量链路贪婪搜索分配算法对星间测量进行优化,而下层采用基于全局“邻域”搜索的星间路由优化算法对星间通信进行优化。文献[18]提出了基于遗传算法的双环星间链路分配优化方法,通过设定通信和测量性能的权重,将星间链路分配问题描述为单目标优化问题。在上述研究中,链路规划目标函数不仅包括了通信指标,还对测距性能做出了要求,所以星间链路拓扑规划的结果表现为测距性能与通信性能的均衡,以牺牲彼此的部分性能指标作为代价来实现全局优化的均衡。

随着星间链路技术的发展,卫星导航精密定轨的研究逐步成为热点。目前,武汉大学和中国科学院上海天文台开展了相关的定轨实验,并对精度衰减因子(Dilution of Precision, DOP)的结果进行了分析。结果表明,基于星间链路测量的定轨结果可以通过改变观测几何构型和增加星间测量次数进行改善。当前在星间链路拓扑规划的研究中通常使用PDOP作为评估星间链路测距性能的指标。其中,文献[12,15,16]分别采用本地搜素算法+模拟退火算法、遗传算法和模拟退火算法进行求解。然而,上述的启发式算法都包含新链路分配的产生环节。当卫星所搭载的星间链路天线数量受限时,随机交叉产生的新链路必须满足天线数量受限的约束条件,因此需要在新链路生成后补充冲突检测算法,文献[12,16]分别提出了相应的冲突检测算法。为了减少链路分配的计算量,如何设计一种在既满足链路约束,同时避免冲突检测交叉机制是有必要的。

本文以一颗卫星只能携带一个星间链路相控阵天线为例,建立了以星间测量PDOP值作为优化目标的星间链路规划模型。通过利用FSA的思想设计了一种星间链路拓扑划分机制,将每个超帧(包含20个子帧)视为种群,建模为以最大PDOP值最小化为目标的优化问题。针对传统遗传算法的基因变异机制和染色体交叉机制无法满足优化模型约束条件的难题,本文提出了单点溯源变异(SPTV)机制和基于“杂交+自交”思想的时隙杂交(TSX)与位置自交(PSX)染色体交叉机制。最后,利用改进后的遗传算法对星间链路拓扑优化进行迭代求解。

1 动态链路拓扑规划问题描述

星间链路的建立需要满足3个基本条件：① 2 颗建链卫星之间不被遮挡；② 2颗卫星的天线都在给定的指向角内；③ 二者之间的距离小于最大通信距离。但由于卫星在空间中一直处于运动状态,因此卫星之间的可视性是动态变化的。在卫星搭载星间链路天线受限的情况下,如何在动态变化的可视卫星集合中选择1颗卫星建立星间链路值得深入研究。

1.1 链路拓扑处理

由于卫星的动态可视性,导航卫星网络的拓扑结构也是一直动态变化的。当单颗卫星仅能建立一个星间链路的时候,导航卫星网络就构成了一个典型的DTN网络。图1为不同时隙下导航卫星网络拓扑示意图。在不同的时隙下,除自身以外,卫星1～卫星4分别与不同的卫星建链。每一时隙下每颗卫星仅能与1颗卫星建立双向链路,因此卫星只有建链和空闲2种状态。如图1中,在时隙4时刻,卫星1和卫星4均处于空闲状态,卫星2和卫星3处于建链状态。

图1 不同时隙下导航卫星网络拓扑示意图Fig.1 Topology for navigation satellite network in different time slots

导航卫星网络以时分复用传输模式(Time-Division Multi-plexing Access, TDMA)运行,且轨道运动的周期具有周期性,因此本文借鉴FSA的思想进行建模。FSA的思想是将时间范围划分成对应于不同状态的几个等长时间间隔,并将其定义为超帧。每个超帧由几个等长的子帧组成,每个子帧包含若干个时隙。每个超帧都是一个星间链路观测周期,也是链路分配的基本时间单位。

图2为星间链路网络拓扑处理方案,将导航卫星网络系统的周期划分为个等长的时间间隔,每个时间间隔对应一个FSA状态。当2颗卫星在整个FSA状态下彼此可见时,才被定义为可见,否则定义为不可见。因此在上述方案下,每个FSA状态下卫星之间的能见度是固定的,因此可以在不同的FSA状态中以固定的可见性进行链路分配。通过FSA状态的设置可以节省计算和存储资源,并提高链路计划管理的简单性。考虑到不同大小的将会影响一个FSA状态内的可见卫星数量,因此本文在第3节性能分析部分对不同对卫星可见数量和链路影响进行了评估。

图2 星间链路网络拓扑处理方案Fig.2 Scheme for handling ISL network topology

1.2 性能指标PDOP

导航卫星网络的轨道定位精度取决于测距卫星的数量、几何分布和测距精度。当可见卫星数量和链路测距精度固定时,卫星网络的轨道定位精度由测距链路的几何形状决定。由于PDOP既能反映星间观测的数量,又能反映星间观测的几何分布,因此本文采用PDOP作为测距性能的度量,其计算方式为

(1)

式中：表示当卫星与颗卫星相连接时,得到具有个观测值的观测矩阵,维度为×3,即

(2)

文献[22]推导出PDOP+1始终小于PDOP,这就表明观测数量的增多会导致更小的PDOP。由于卫星间能见度和Ka波段天线数量的限制,PDOP受到一个定轨周期内时隙分配的影响。因此,应该为每个时隙分配更多不同的测距链路。

1.3 链路拓扑优化模型

导航卫星网络链路分配的目的是实现星间测距最优化,本文将星间测距的PDOP作为优化目标,将链路分配问题建模为在满足星间链路建链约束下,以最大PDOP值最小化为目标的优化问题。基于以上的问题描述,对模型符号进行了相关定义与说明,如表1所示。

表1 模型参数说明Table 1 Model parameter description

假设在第个时隙存在第颗卫星和第颗卫星,此时二者的可见关系可以表述为,,。当,,=1时,表示卫星与卫星可视。若选择卫星与卫星在第个时隙建链,则,,=1,否则,,=0。因为FSA的思想是在时间间隔内2颗卫星持续可见才定义为可见,故卫星网络的可视矩阵集合为=[,,…,,…,]。其中,为第个超帧的可见关系矩阵。

由以上符号定义可知,链路拓扑优化问题模型可以描述为

1) 目标函数

(3)

2) 约束条件

,,=,,, ∀,,

(4)

(5)

(6)

,,=,,, ∀,,

(7)

,,∈[0,1], ∀,,

(8)

,,∈[0,1], ∀,,

(9)

,,=0,=, ∀

(10)

,,=0,=, ∀

(11)

导航卫星网络的链路拓扑优化问题模型将PDOP值最小化作为优化目标,为了更准确地表征测距性能这一指标,本文采用所有卫星中的最大PDOP值作为考量标准。如式(3)所示,通过计算某一子帧中各卫星的PDOP,将其中的最大值作为需要优化的目标,在满足约束条件的情况下,实现链路拓扑的最大PDOP的最小化。将最大PDOP最小化作为优化目标的原因是平均PDOP只能代表整网的位置精度因子,并不能保证每颗卫星的PDOP都较小。若当前子帧以牺牲某一颗卫星的PDOP作为代价实现整网的平均PDOP最小,这样的链路分配同样是不可取的。而最大PDOP的最小化能够保证每颗卫星的PDOP均为最优解,保证每颗卫星的星间测量PDOP平均值都比较小,不以牺牲某一卫星的PDOP值来提高其他卫星的PDOP值。同时,最大PDOP的最小化也会有助于整网平均PDOP的优化。因此,选择最大PDOP的最小化作为优化目标是合理的。

约束条件中,约束式(4)为可见性矩阵对称性约束,表示卫星与卫星在时隙时的可视性是对称的。约束式(5)和式(6)为链路数量约束,由于星间链路数量受限,对于任意的卫星和卫星,在时隙时所能链接的最大链路数为1。约束式(7)为链路分配矩阵对称性约束,当卫星与卫星在时隙时互相建链,那么二者的取值是相等的。约束式(8)和式(9)分别为卫星与卫星在时隙时的可见关系和建链关系取值约束。约束式(10)和式(11)表示卫星与卫星在时隙时,卫星自身是无法可见和建链的,因此可视关系矩阵和链路分配矩阵的对角线元素均为0。图3为不同时隙下链路分配矩阵示意图。在链路分配问题中,卫星与卫星能否建链不仅受卫星之间可视性约束、链路数量约束,同时也受时间维度的约束。在不同的时隙下,卫星之间的建链情况是不同的。因此,链路分配问题需要结合DTN的属性来完成以测距性能为优化目标的导航卫星网络拓扑优化。

图3 不同时隙下链路分配矩阵示意图Fig.3 Schematic of link allocation matrix for different time slots

2 拓扑规划算法

从第1节中所建立的链路拓扑优化模型可以看出,在实现最大PDOP值的最小化目标的过程中,首先需要从在满足给定约束条件下生成链路分配集合,将其定义为集合,再以最大PDOP值最小化为目标,从生成的链路分配集合中为每个时隙寻找最优的分配方案。假设星座中有颗卫星,在不考虑链路约束的条件下,某一时隙下星座的链路分配集合为

(12)

当=27时,链路分配集合的可能取值约为5×10。若对所有时隙的集合采用遍历的方法进行全局搜索,在不考虑链路约束条件下的计算量已经十分巨大,因此全局搜索求解最优链路分配十分困难。因此,本文采用遗传算法(Genetic Algorithm, GA)的思想,针对拓扑矩阵机制下的导航卫星链路分配问题进行求解。

2.1 遗传算法

遗传算法最早是由美国的Holland提出的,该算法通过模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程实现最优解的解算。

传统的遗传算法的流程如图4所示。种群预先初始化后,对染色体进行编码,然后根据评估函数计算当前种群的适应度,以此来评估当前种群的优劣性。通过种群的适应度,选择出优质的种群作为父代,并经过染色体交叉生成子代种群。

图4 传统遗传算法流程图Fig.4 Flow chart of traditional genetic algorithm

考虑到自然界中基因变异的存在,根据子代种群生成变异子代种群,通过与父代种群集合形成新一代种群后,再次进行种群的适应度计算。如此循环,直至迭代结束,最终解码染色体得到最优解。

遗传算法的优点在于不需要全网遍历检索求解目标函数,而是将初始化种群按照优胜劣汰的准则,为种群选择优质的基因,从而实现最优解的求解。相比于遍历搜索,遗传算法具有计算量小的优势。

2.2 改进遗传算法

传统的遗传算法对于极值求解、旅行商模型求解等问题具有较好的通用性,但对于导航卫星网络的链路分配问题,需要设计新的种群机制、交叉机制和变异机制。由第1节可知,由于DTN的特有属性使得链路分配问题既包括空间的约束,也受到时间的约束,因此这是一个由卫星、超帧和时隙组成的三维体系。若直接使用传统的遗传算法进行目标优化,种群的初始化和种群的交叉和基因的变异是较难完成的。因此,本文采用一种紧凑型的链路分配矩阵,将原有三维体系降为二维系统,如此将卫星和时隙结合,更加有利于导航卫星网络的链路拓扑优化问题。图5为紧凑型链路分配矩阵示意图。当链路分配矩阵由图3紧凑至图5时,可以通过构建多个不同的矩阵实现种群的初始化。

图5 紧凑型链路分配矩阵Fig.5 Compact link allocation matrix

此外,由于链路分配矩阵和可视关系矩阵的取值均为0或1,所以对于导航卫星网络链路拓扑优化问题不需要进行编码和解码。同时,依照传统遗传算法的思想,可以通过染色体交叉和基因变异完成最优解的求解。但由第1节中的模型约束可知,星间链路受限情况下,卫星仅能有一条链路。若对链路分配矩阵进行交叉操作和变异操作,极易产生大量的冲突,导致新生成的种群不满足模型约束。针对上述问题,本文提出了更加适合于链路分配矩阵的新型交叉机制和变异机制,有效地避免了冲突问题的产生。

2.2.1 种群初始化

基于图5的紧凑型链路分配矩阵设计,可以将每一张链路分配矩阵看做每个子帧的链路分配结果,当一个超帧中存在个子帧时,可以将链路分配矩阵扩充为张,如此就形成了第个超帧的初始种群。链路分配矩阵需要满足第1节中的模型约束,由于紧凑型链路分配矩阵包含了时隙信息,约束式(7)需要更改为

,=∀,,

(13)

,=∀,,

(14)

式中：,和,为链路分配矩阵的元素,维度大小为×。张链路分配矩阵可以构成第个超帧的链路分配集合,所以链路分配矩阵集合为={,,…,,…,}。图6为链路分配矩阵种群初始化流程图,若超帧发生变化时,可以通过输入不同超帧对应的可视关系矩阵,实现新的种群初始化。

2.2.2 适应度计算与父代选择

由1.3节中式(3)可知,链路拓扑优化模型以最大PDOP值的最小化为优化目标。根据式(1)和式(2)可以计算得出一个超帧内某个子帧的链路分配矩阵中所有卫星的PDOP,然后取一个子帧内中最大的PDOP值作为适应度值进行父代种群的选择。父代种群的选择使用轮盘赌选择算法进行,若最大PDOP的值越大,反而该链路分配矩阵被选中的概率越小,从而选择将最大PDOP中较小的链路分配矩阵作为父代。

图6 链路分配矩阵Am的种群初始化流程图Fig.6 Flow chart of population initialization of link allocation matrix Am

2.2.3 染色体交叉

目前,常用的染色体交叉算法包括：顺序交叉(Order Crossover, OX)、基于位置的交叉(Position Based Crossover, PBX)和循环交叉(Cyclic Crossover, CX)。图7为遗传算法的3种交叉方法示意图。

OX的思想是在父代1中随机选择染色体的片段作为交叉对象遗传给子代,将父代2中除去被选中的交叉对象段后按顺序依次遗传给子代。PBX方法将父代2中除去被选中位置的交叉个体后,按照先后顺序依次遗传给子代。相比于OX和PBX,CX的思想较为复杂。CX随机选择一个位置作为起始点,按照从父代1到父代2交替的原则寻找一个闭合循环圈。以图7(c)为例,父代1中以“1”作为起点,依次寻找得到的循环：1→5→3→1,将父代1中的对应位置遗传给子代,从父代2中剔除已经被选中的对象后,将剩余对象遗传给子代。

图7 遗传算法的3种交叉方法Fig.7 Three crossover methods of genetic algorithm

从上述的交叉操作中不难发现,不论是OX、PBX还是CX,都不适用于链路分配矩阵的情况。如果采用上述的交叉操作后,将会因冲突问题而增加冲突检测算法来满足链路拓扑优化模型的约束条件,这将导致计算量的额外增加。考虑到上述交叉操作的缺陷,本文基于“杂交与自交”的思想提出了一种适用于导航卫星网络拓扑矩阵的时隙杂交操作(Time Slots Crossover, TSX)和位置自交操作(Position Self-Crossover, PSX)。图8为TSX方法示意图,由随机函数rand产生时隙编号,并随机选取群体中的链路分配矩阵和作为父系和母系,将时隙的所有链路分配结果交叉至父系。虽然TSX的方法操作简单,但TSX的最大优点在于避免了交叉所产生的冲突,保证新杂交产生的子代满足链路分配模型的约束条件。

图8 TSX方法示意图Fig.8 Diagram of TSX method

考虑到TSX进行交叉无法保证种群的多样性,本文提出了PSX操作方法。图9为PSX方法示意图,沿用TSX方法中随机产生的时隙编号,分别读取当前时隙的简单型链路分配矩阵。然后随机选择卫星和卫星作为交叉对象,将中卫星和卫星所在的行与列交叉互换,同时将卫星和卫星的原建链卫星和卫星所在的行与列交叉互换。自交完成后的链路既满足约束条件,也出现了新的链路。为了更清楚地阐述PSX方法的操作流程,以算例1为例进行说明。

假设Sat 1～Sat 5表示5颗卫星,Slot 1～Slot 5表示5个时隙,A～J表示在Slot 3时隙5颗卫星的匹配卫星编号,若图9(a)中随机选择Sat 1和Sat 5作为交叉对象,将随机时隙的简单型链路分配矩阵父代中Sat 2所在的行和列与Sat 5所在的行和列自我交叉互换,同时将父代中Sat 1所连接的Sat 4和Sat 5所连接的Sat 3所在的行和列自我交叉互换。经过PSX操作后,种群的链路分配结果由父代的“1→4”与“3→5”改变为子代的“1→3”与“4→5”,所产生的新一代子代不仅链路分配发生了改变,同时还满足了模型约束条件。

图9 PSX方法示意图Fig.9 Diagram of PSX

但是,并非所有的自交操作都如图9所示的完美无暇,而是存在特殊情况使得交叉后的子代不满足链路优化模型约束条件。为了避免冲突,在随机选择卫星和卫星时,要避免选择已建链卫星对作为自交对象,即卫星和卫星已互相建链。若卫星和卫星为卫星对,自交后矩阵对角元素将不满足约束。同时还要考虑卫星和卫星中不存在空闲卫星,即原建链卫星和卫星不能为0,这样就不会违背式(10)和式(11) 的约束。

在染色体交叉操作中,本文采用“先杂交后自交”的原则进行。考虑到自交会增加卫星空闲个数,因此在在交叉结束后通过搜索所有不可见卫星的排列组合结果,在满足可视的条件下为空闲卫星重新建链。染色体杂交的实现见伪代码1,其中new_link函数主要为空闲卫星重新建链,Compact函数负责将简单型链路分配矩阵转化为紧凑型。

伪代码1 染色体交叉操作的伪代码

2.2.4 基因突变

基因突变是种群基因改变的方式之一,不同于染色体交叉操作,基因突变是染色体上某些点位的改变。但因为链路分配矩阵需要满足模型约束,因此当某一个卫星链路发生改变时,势必会引起其他卫星链路的改变,为了解决以上冲突问题,本文提出了单点溯源突变机制(Single Point and Traceable Variation, SPTV)。

如图10所示,随机选择时隙编号上的卫星,从卫星的可视集合中随机选择1颗卫星作为突变卫星进行建链。由于卫星有可能本身已经建链,因此新建链路“→”将会影响其他原有链路卫星的建链情况,因此需要溯源寻找到受影响的卫星,并按照模型约束重新建链。为了直观地理解单点溯源法,本文以算例2进行阐述,基因变异SPTV操作见伪代码2。

图10 SPTV方法示意图Fig.10 Diagram of SPTV

假设从图10(a)中随机选择Slot 5中的Sat 4作为突变对象,随机从Sat 4的可视集合中选取Sat 1作为建链卫星。由于Sat 4和Sat 1本身已存在链路分配结果。当新链路“1→4”建立后,原有链路“1→2”和“4→5”需要拆解。若拆解后的Sat 5和Sat 2不重新分配链路,那么将会使当前时隙下新增2颗空闲卫星,这对于最大PDOP最小化的目标是不利的。因此,SPTV将询问空闲的Sat 5和Sat 2是否可视,若可视则建立链路,否则将二者置于空闲状态。从图10(b)中可以看出,SPTV会影响4颗卫星的建链情况,这不仅避免了大规模的冲突,同时为寻找最佳链路分配提供了新的可能。

伪代码2 基因变异SPTV操作的伪代码

本文在2.2.3节中提出了以“杂交+自交”为思想的TSX-PSX染色体交叉机制,在2.2.4节中提出了SPTV基因突变机制。上述2种机制都很好地避免了因链路拆建而导致的冲突问题,是适用于链路分配矩阵的较好机制。基于图4所示的遗传算法流程图,结合TSX-PSX染色体交叉和SPTV基因突变机制,可以实现对优化模型的求解。

2.3 算法复杂度分析

遗传算法属于迭代算法,复杂度分析仅需分析其单次迭代过程即可。对于改进遗传算法的单次迭代过程,仅有染色体交叉过程和基因变异过程复杂度较高,其他过程的运行时间为常数。图9所示的染色体交叉操作属于一种随机过程,它包括内层交叉和外层循环2部分。染色体交叉过程可以看作一系列伯努利试验,假设染色体的交叉率为,则实验成功的概率=。定义随机变量为取得一次成功所要进行的实验次数,则应满足几何分布,其期望为()=1,即内层交叉的平均运行次数为1,故内层交叉的复杂度为(1)。外层循环的次数与种群数量(子帧数量)相关,复杂度为(log)。因此,染色体交叉过程的复杂度为((log))。

图10为基因突变操作同样属于一种随机过程,其组成部分与染色体交叉过程一致。假设染色体的交叉率为,则内层变异的复杂度为(1)。而外层循环的次数与种群数量(子帧数量)相关,复杂度为()。因此,染色体交叉过程的复杂度为()。综上,本文改进遗传算法的复杂度为(max((log),))。

3 性能分析

3.1 仿真环境

本文基于STK软件参考BDS卫星星座搭建了仿真模型,其中MEO层采用Walker-σ 24/3/1构型,轨道高度为21 528 km,轨道倾角为55°。IGSO层轨道高度为35 786 km,轨道倾角为55°,交叉点经度为东经118°,3颗卫星以升交点赤经相差120°均匀分布在3个轨道面内。卫星星载天线采用简单圆锥型,圆锥半角为60°,方位角范围为-180°～180°。仿真时间从UTC 2021/05/30 00∶00∶00—2021/05/31 00∶00∶00,共计86 400 s。为了便于计算将星座数据的采样周期设置为1 min。

拓扑处理参数如表2所示,其中超帧的持续时间分别设置为600 s和900 s。在不同超帧持续时间下,不同超帧的各卫星的可见个数不同,如图11所示。以IGSO1、MEO11和MEO21和MEO31这4颗为例,当超帧时间分别为600 s和900 s时,各卫星的可视卫星数量整体在11～20之间。但对于不同超帧下,2种超帧时间的可视卫星数量是有变化的,那么链路分配结果将会不同。因此,超帧的持续时间对优化目标存在一定的影响。

表2 拓扑处理参数Table 2 Parameters of topology processing

图11 不同超帧时间的卫星可视数量Fig.11 Number of satellites visible in different superframe durations

3.2 仿真结果

3.2.1 遗传算法参数对优化目标的影响

在遗传算法中,影响到迭代结果的因素分别为：迭代次数、染色体交叉率和基因变异率。为了探究以上3个因素对优化目标的影响,本文采用控制变量法的方式,分别对3种因素进行了仿真探究。以第1个超帧为例,图12为3种因素在不同参数下对优化目标最大PDOP的影响结果。从图12中可以看出,当迭代次数为10 000次时优化后的结果最优,最大PDOP为2.574；当染色体交叉率为0.9时,第1个超帧中最大PDOP为2.473,明显优于其他参数的优化结果；当基因突变率为0.1时,第1个超帧中最大PDOP为2.538,相比于其他参数较好。

3.2.2 不同超帧的优化目标仿真结果

基于3.2.1节的参数探究,针对不同超帧的优化目标仿真,遗传算法参数分别设置为：迭代次数10 000、染色体交叉率0.9和基因突变率0.1。由3.1节分析可知,不同超帧持续时间会影响卫星的可视数量,对优化目标存在一定的影响。因此,本文针对两种超帧时间进行模型优化,仿真结果如图13所示。

图13 不同超帧持续时间对最大PDOP的影响Fig.13 Influence of different superframe durations on maximum PDOP

从横向对比,不论超帧的持续时间取值为多少,迭代优化后的最大PDOP整体趋势是保持一致的。因为超帧时间分别为600 s和900 s时,影响到卫星可视性的数量是少数的。同时,从图13中可以看出,所有卫星的整体可视数量区间在超帧改变前后是保持一致的。因此,可视卫星数量的少许变化对于最大PDOP的影响并不明显。但从纵向对比,由于超帧持续时间的改变会导致仿真周期最大PDOP平均值的改变。如表3所示,超帧持续时间为900 s时,最大PDOP的最小值和均值都比超帧持续时间为600 s时大,PDOP值提高了3.82%。由此可见,超帧持续时间较长时会导致PDOP增大。

表3 不同超帧持续时间的最大PDOP值的结果

3.2.3 改进遗传算法的优化目标仿真结果

为验证基于“杂交+自交”思想的TSX-PSX染色体交叉机制的有效性,本文将TSX-PSX作为实验组,以TSX作为对照组,将超帧持续时间设置为600 s进行仿真,实验结果如图14所示。相比于仅使用TSX进行染色体交叉,TSX-PSX交叉后的最大PDOP值更小。TSX-PSX在遗传母系的链路分配结果之后,会对该时隙的链路进行内部交叉。正是这种内部交叉不仅保持了母系的大部分链路分配结果,而且建立了新的链路,增加了种群的多样性。因此,在采用TSX-PSX之后,最大PDOP整体减小,优化后的链路拓扑结构PDOP值更小。

图14 不同染色体交叉机制下的仿真结果Fig.14 Simulation results of different chromosome crossover mechanisms

如表4所示,相比于TSX染色体交叉机制,TSX-PSX对最大PDOP的优化有显著的效果,PDOP值减小了27.28%。此外,相比于文献[22]中的最大PDOP≤2.8,TSX-PSX的结果与之保持一致。因此,改进后遗传算法的TSX-PSX染色体交叉机制的有效性得到验证。

表4 不同染色体交叉机制最大PDOP值的结果

4 结 论

本文针对导航卫星星间链路数量受限情况下的链路拓扑规划问题,以星间测量最大PDOP值最小化作为优化目标建立了链路拓扑优化模型。根据优化目标和约束条件,采用遗传算法对优化模型进行求解。本文提出了基于“杂交+自交”思想的TSX-PSX染色体交叉机制和SPTV基因突变机制,有效解决了传统遗传算法中染色体交叉机制和基因变异机制不满足链路拓扑模型约束而导致大规模冲突问题。仿真结果证明,TSX-PSX染色体机制相比于单一的TSX染色体交叉机制,将最大PDOP值改善了27.28%,验证了改进遗传算法的TSX-PSX染色体机制的有效性。

致 谢

感谢中国科学技术大学尹东副教授和盛捷老师的指点,感谢马慧晨和柯新建对论文研究的帮助和支持。