一种基于改进免疫算法的GNSS快速选星方法

甘宇婷 陈 健 赵兴旺 刘 超

1 安徽理工大学空间信息与测绘工程学院,安徽省淮南市泰丰大街168号,232001

2 安徽理工大学矿山采动灾害空天地协同监测与预警安徽普通高校重点实验室,安徽省淮南市泰丰大街168号,232001

3 安徽理工大学矿区环境与灾害协同监测煤炭行业工程研究中心,安徽省淮南市泰丰大街168号,232001

GNSS的快速发展,对当前卫星导航系统的实时性、可靠性以及定位精度提出更高的要求。对高动态接收机而言,会大大增加接收机硬件设计的成本与难度[1]。当可见卫星达到一定数目,其定位精度并不会得到有效提升,相反其冗余信息会使计算量增大。因此,通过对当前可见卫星进行选取,获取几何构型良好的卫星组合进行定位解算,降低定位所需计算量,提高实时解算能力很有必要。

传统的选星算法主要是基于遍历法思想,即通过将当前观测到的所有可见卫星进行合适数目卫星排列组合,计算各个卫星组合下的几何精度因子(geometric dilution of precision, GDOP),并从全部组合中找出最小GDOP作为最终结果[2-3]。当前,选星算法多数从单目标优化问题和聚类2个方面出发。单目标优化方法是指将GDOP值作为适应度函数,通过智能优化算法求解适应度函数的最小值。聚类方法是指将所有可见卫星进行分类,从每类卫星中选取1颗卫星,从而获得与遍历法相近的GDOP值,提高选星效率,但该方法在卫星分布分散情况下效果较差[4-5]。随着研究的深入,针对传统选星算法计算量大、耗时长等缺点,许多学者对其进行大量研究。霍航宇等[6]基于遗传算法,比较选星数目和GDOP的关系,根据所需精度来确定卫星数目,进而进行定位解算;Azami等[7]结合神经网络和主成分分析 ,对当前可见卫星进行分类,从而选出最小GDOP值的卫星组合;余德荧等[8]采用灰狼优化算法,通过固定选星数目,根据最小GDOP值进行选择,降低选星耗时;王尔申等[9-10]提出基于粒子群优化算法(particle swarm optimization, PSO)的快速选星,并比较PSO参数设置对选星结果的影响;朱军等[11]结合几何分布和差分进化算法,自适应改变种群大小,从而实现快速选星。

综上可知,现有的研究成果在一定程度上可提高选星实时性,但并未对选星算法在不同卫星系统组合下的普适性进行系统分析,且免疫算法在选星领域还未被使用。该方法具有并行分布式搜索、鲁棒性强等特点,可以克服一般“寻优”中不可避免的过早收敛问题,更加快速地寻求全局最优解。因此,本文提出基于改进免疫算法的GNSS快速选星算法,分析初始化种群数目、最大迭代次数对结果的影响,获得参数的最佳取值,并通过实测数据验证所提方法的普适性和有效性。

1 免疫算法

免疫算法的运行过程与其他智能算法类似[12],均是基于算子来进行计算,每个算子均有其各自的功能。

1)亲和度评价算子。亲和度是指生成的种群个体与全局最优解的结合强度,其通常表示为aff(x):S∈R,其中aff(x)为适应度函数,S为适应度函数的可行解区间,R为实数域。

2)抗体浓度评价算子。抗体浓度是指生成种群多样性的好坏。抗体浓度通常定义为:

(1)

式中,N为种群数目;S(abi,abj)为种群个体间的相似度,其中abi为种群中的第i个个体。

3)克隆算子。克隆是将符合要求的种群个体进行复制,其可以描述为Tc(abi)=clone(abi),其中clone(abi)为mi个与abi相同的克隆构成集合,mi为克隆数目,根据实际情况设定。

免疫算法的寻优过程为:通过生成初始化种群,利用抗体浓度评价算子和亲和度评价算子获取种群个体质量信息,选择出优质个体,利用克隆算子对优质个体进行克隆复制,并进行变异等操作,从而获取全局最优解。

2 基于改进免疫算法的GNSS快速选星方法

2.1 适应度函数

适应度函数选取的原则为能够衡量所选卫星组合的定位精度。免疫算法对种群每个个体的适应度函数值进行计算,其选取直接影响到算法能否正确求解问题以及计算的时间复杂度[13]。本文采用GDOP值作为适应度函数,定位精度与其关系可表示为:

σ=σUERE·GDOP

(2)

式中,σUERE为等效距离误差,假设在不同卫星系统组合情况下,其等效距离误差大致相同;σ为定位精度。GDOP计算公式如下:

(3)

式中,

(4)

(5)

式中,trace(·)表示矩阵的迹,H表示可见卫星的观测矩阵,下标C、R、G、E、J分别代表BDS、GLONASS、GPS、Galileo和QZSS(quasi-zenith satellite system, 准天顶卫星系统),I为单位矩阵,下标x指代卫星系统,l、m、n为接收机位置到可见卫星的方向余弦,上标k为当前系统可见卫星数目。

2.2 算法实现步骤

在免疫算法中,免疫个体数为Np,最大迭代次数为G,X={x1,x2,…,xNp}为初始化种群个体集合,xi={y1,y2,…,yn}为每个个体所选的卫星组合,算法详细流程如图1所示。

图1 算法流程Fig.1 Algorithm flow chart

其具体算法步骤如下:

1)根据导航电文,获取历元可见卫星的高度角。

2)设置截止高度角(10°),对可见卫星进行提取,并计算可用卫星的观测矩阵H。

3)根据观测矩阵的行数获取可用卫星数目m,对可用卫星从1到m进行编号,使之一一对应;将初始化种群数目和最大迭代次数作为改进免疫算法的输入参数,进行免疫计算,此时计时开始。

5)根据设置的最大迭代次数进行迭代运算,对每个个体计算GDOP值即适应度函数,每次迭代保留适应度函数值最好的个体。

6)当迭代数目达到设置的最大迭代次数G之后,免疫算法结束,停止计时,输出最小GDOP值和耗时。

2.3 免疫算法参数选取

免疫算法通过迭代次数和初始化种群大小从全局寻优缓慢收敛到局部寻优。为了寻求免疫算法运算过程中最佳的迭代次数和初始化种群数目,本文利用CUT0测站2023-02-02观测数据进行实验,所使用软件为MATLAB R2018b,电脑搭载R5-4600H,3.00 GHz处理器,16GB RAM。其中GDOP差值指免疫算法所寻找的最小GDOP值与遍历法之间的差值,时间的度量从计算出当前所有观测卫星的观测矩阵H进入免疫算法开始,判断免疫算法迭代次数是否到达设置的最大迭代次数,满足条件则结束。本文设置截止高度角为10°,通过固定初始化种群数目(从20开始,步长为20,直至60结束),分别对最大迭代次数取不同值(从80开始,步长为20,直至140结束)进行讨论,实验结果如图2、表1所示。

表1 初始化种群数目与迭代次数对选星性能的影响

图2 初始化种群数目与迭代次数对性能的影响Fig.2 Effects of initial population number and iterations on positioning performance

由图2、表1可知,GDOP差值均在0～0.5之间波动,且较为稳定,表明免疫算法能够大概率搜索到与遍历法结果一致的GDOP值,而小部分由于随机生成的初始化种群而无法保证其良好的多样性,从而获取与遍历法相近略大的GDOP值,即局部最优解[14]。当初始化种群数目固定时,随着迭代次数增加,其GDOP差值呈现减小的趋势,但耗时明显增加。初始化种群数目为60和最大迭代次数为140时,平均GDOP值差值仅为0.128,说明免疫算法能够搜索到最佳的卫星组合。当固定最大迭代次数为120、初始化种群数目为20时,平均耗时最少,为0.860 s。为了更加直观地分析初始化种群数目与最大迭代次数对选星实时性的影响,表2(单位%)为选星耗时百分比。

表2 选星耗时百分比

从表2可知,在最大迭代次数固定的前提下,初始化种群数目从20到60,其耗时比((t遍历法-t免疫算法)/t遍历法×100%)减少,减小幅度大致相当;在初始化种群固定的前提下,最大迭代次数从80到140,耗时比减小,从120到140减小幅度最大。因此,在考虑实时性与定位精度双重因素下,初始化种群数目可选在20附近、最大迭代次数可选择在120附近。

3 实验验证与分析

为了验证本文所提算法对不同卫星系统组合是否具有普适性,在初始化种群数目设置为20、最大迭代次数设置为120的前提下,系统分析不同卫星系统组合(G、C、G/C、G/C/E、G/C/E/R、G/C/E/R/J)下的选星耗时和平均GDOP差值,结果如图3所示。

图3 不同卫星系统组合下的选星耗时和GDOP差值Fig.3 Satellite selection time consuming and GDOP difference under different satellite system combinations

由图3(a)～(c)可知,利用G、C单系统和C/G双系统进行定位时,在固定选星数目情况下改进免疫算法求得的最小GDOP与遍历法结果几乎一致,且GDOP差值最大不超过0.07。平均耗时在0.5～0.6 s内波动,处于平稳状态。由图3(d)～(f)可知,GDOP差值存在较大波动,总体介于0～0.4之间,部分历元平均耗时明显上升,但最大耗时不超过2.0 s。为了量化所提算法的性能,表3为不同系统组合下2种选星算法的GDOP值以及计算耗时。

表3 两种选星算法的GDOP值和平均耗时

由表3可知,随着卫星数增加,遍历法平均耗时急剧上升,当可见卫星数目为45时,遍历法耗时高达29.976 s,严重影响接收机的实时性。改进免疫算法的平均耗时虽然也随可见卫星数的上升而增加,但上升幅度较小,在五系统组合情况下,耗时仅为1.06 s。改进免疫算法计算的GDOP值与遍历法结果相差较小,最大差值约为0.2。与遍历法相比,本文所提方法在进行GPS、BDS单系统定位时平均耗时分别缩短40.58%、53.27%,平均 GDOP差值与遍历法的比值分别为0.44%、0.57%。在GPS/BDS组合系统下,与遍历法相比,改进的免疫算法平均GDOP差值仅为0.011,耗时缩短69.74%。在GPS/BDS/Galileo三系统、GPS/BDS/Galileo/GLONASS四系统、GPS/BDS/Galileo/GLONASS/QZSS五系统组合定位时,本文算法的平均耗时分别缩短93.37%、96.21%、96.47%,其平均GDOP与遍历法相差分别为0.159、0.152、0.122,因此改进的免疫算法在多 GNSS 系统组合定位时均具有良好的性能。

4 结 语

本文提出一种基于改进免疫算法的GNSS快速选星方法,可有效降低运算量,提高接收机定位实时性。在考虑实时性与定位精度双重因素下,选择最佳的初始化种群数目与最大迭代次数。最后,通过实测数据验证所提方法的有效性及普适性,结论如下:

1)初始化种群数目在20附近、最大迭代次数在120附近,免疫算法的选星性能最优,其耗时与遍历法相比缩短93.42%。

2)在单BDS 系统定位时,本文所提算法平均GDOP 值与遍历法相差仅为0.01,平均 GDOP 差值与遍历法的比值仅为0.57%,耗时比遍历法缩短53.27%。

3)在不同系统组合下,包括GPS/BDS/Galileo、GPS/BDS/Galileo/GLONASS和GPS/BDS/Galileo/GLONASS/QZSS,本文所提算法相对于遍历法,GDOP误差不超过0.5,并且平均耗时分别缩短93.37%、96.21%和96.47%。因此,该算法适用于多个GNSS系统组合下的定位,具有良好的普适性。