一種基于改進免疫算法的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系統組合下的定位,具有良好的普適性。