一種基于改進(jìn)免疫算法的GNSS快速選星方法

甘宇婷 陳 健 趙興旺 劉 超

1 安徽理工大學(xué)空間信息與測(cè)繪工程學(xué)院,安徽省淮南市泰豐大街168號(hào),232001

2 安徽理工大學(xué)礦山采動(dòng)災(zāi)害空天地協(xié)同監(jiān)測(cè)與預(yù)警安徽普通高校重點(diǎn)實(shí)驗(yàn)室,安徽省淮南市泰豐大街168號(hào),232001

3 安徽理工大學(xué)礦區(qū)環(huán)境與災(zāi)害協(xié)同監(jiān)測(cè)煤炭行業(yè)工程研究中心,安徽省淮南市泰豐大街168號(hào),232001

GNSS的快速發(fā)展,對(duì)當(dāng)前衛(wèi)星導(dǎo)航系統(tǒng)的實(shí)時(shí)性、可靠性以及定位精度提出更高的要求。對(duì)高動(dòng)態(tài)接收機(jī)而言,會(huì)大大增加接收機(jī)硬件設(shè)計(jì)的成本與難度[1]。當(dāng)可見(jiàn)衛(wèi)星達(dá)到一定數(shù)目,其定位精度并不會(huì)得到有效提升,相反其冗余信息會(huì)使計(jì)算量增大。因此,通過(guò)對(duì)當(dāng)前可見(jiàn)衛(wèi)星進(jìn)行選取,獲取幾何構(gòu)型良好的衛(wèi)星組合進(jìn)行定位解算,降低定位所需計(jì)算量,提高實(shí)時(shí)解算能力很有必要。

傳統(tǒng)的選星算法主要是基于遍歷法思想,即通過(guò)將當(dāng)前觀測(cè)到的所有可見(jiàn)衛(wèi)星進(jìn)行合適數(shù)目衛(wèi)星排列組合,計(jì)算各個(gè)衛(wèi)星組合下的幾何精度因子(geometric dilution of precision, GDOP),并從全部組合中找出最小GDOP作為最終結(jié)果[2-3]。當(dāng)前,選星算法多數(shù)從單目標(biāo)優(yōu)化問(wèn)題和聚類2個(gè)方面出發(fā)。單目標(biāo)優(yōu)化方法是指將GDOP值作為適應(yīng)度函數(shù),通過(guò)智能優(yōu)化算法求解適應(yīng)度函數(shù)的最小值。聚類方法是指將所有可見(jiàn)衛(wèi)星進(jìn)行分類,從每類衛(wèi)星中選取1顆衛(wèi)星,從而獲得與遍歷法相近的GDOP值,提高選星效率,但該方法在衛(wèi)星分布分散情況下效果較差[4-5]。隨著研究的深入,針對(duì)傳統(tǒng)選星算法計(jì)算量大、耗時(shí)長(zhǎng)等缺點(diǎn),許多學(xué)者對(duì)其進(jìn)行大量研究?；艉接畹萚6]基于遺傳算法,比較選星數(shù)目和GDOP的關(guān)系,根據(jù)所需精度來(lái)確定衛(wèi)星數(shù)目,進(jìn)而進(jìn)行定位解算;Azami等[7]結(jié)合神經(jīng)網(wǎng)絡(luò)和主成分分析 ,對(duì)當(dāng)前可見(jiàn)衛(wèi)星進(jìn)行分類,從而選出最小GDOP值的衛(wèi)星組合;余德熒等[8]采用灰狼優(yōu)化算法,通過(guò)固定選星數(shù)目,根據(jù)最小GDOP值進(jìn)行選擇,降低選星耗時(shí);王爾申等[9-10]提出基于粒子群優(yōu)化算法(particle swarm optimization, PSO)的快速選星,并比較PSO參數(shù)設(shè)置對(duì)選星結(jié)果的影響;朱軍等[11]結(jié)合幾何分布和差分進(jìn)化算法,自適應(yīng)改變種群大小,從而實(shí)現(xiàn)快速選星。

綜上可知,現(xiàn)有的研究成果在一定程度上可提高選星實(shí)時(shí)性,但并未對(duì)選星算法在不同衛(wèi)星系統(tǒng)組合下的普適性進(jìn)行系統(tǒng)分析,且免疫算法在選星領(lǐng)域還未被使用。該方法具有并行分布式搜索、魯棒性強(qiáng)等特點(diǎn),可以克服一般“尋優(yōu)”中不可避免的過(guò)早收斂問(wèn)題,更加快速地尋求全局最優(yōu)解。因此,本文提出基于改進(jìn)免疫算法的GNSS快速選星算法,分析初始化種群數(shù)目、最大迭代次數(shù)對(duì)結(jié)果的影響,獲得參數(shù)的最佳取值,并通過(guò)實(shí)測(cè)數(shù)據(jù)驗(yàn)證所提方法的普適性和有效性。

1 免疫算法

免疫算法的運(yùn)行過(guò)程與其他智能算法類似[12],均是基于算子來(lái)進(jìn)行計(jì)算,每個(gè)算子均有其各自的功能。

1)親和度評(píng)價(jià)算子。親和度是指生成的種群個(gè)體與全局最優(yōu)解的結(jié)合強(qiáng)度,其通常表示為aff(x):S∈R,其中aff(x)為適應(yīng)度函數(shù),S為適應(yīng)度函數(shù)的可行解區(qū)間,R為實(shí)數(shù)域。

2)抗體濃度評(píng)價(jià)算子?？贵w濃度是指生成種群多樣性的好壞?？贵w濃度通常定義為:

(1)

式中,N為種群數(shù)目;S(abi,abj)為種群個(gè)體間的相似度,其中abi為種群中的第i個(gè)個(gè)體。

3)克隆算子。克隆是將符合要求的種群個(gè)體進(jìn)行復(fù)制,其可以描述為Tc(abi)=clone(abi),其中clone(abi)為mi個(gè)與abi相同的克隆構(gòu)成集合,mi為克隆數(shù)目,根據(jù)實(shí)際情況設(shè)定。

免疫算法的尋優(yōu)過(guò)程為:通過(guò)生成初始化種群,利用抗體濃度評(píng)價(jià)算子和親和度評(píng)價(jià)算子獲取種群個(gè)體質(zhì)量信息,選擇出優(yōu)質(zhì)個(gè)體,利用克隆算子對(duì)優(yōu)質(zhì)個(gè)體進(jìn)行克隆復(fù)制,并進(jìn)行變異等操作,從而獲取全局最優(yōu)解。

2 基于改進(jìn)免疫算法的GNSS快速選星方法

2.1 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)選取的原則為能夠衡量所選衛(wèi)星組合的定位精度。免疫算法對(duì)種群每個(gè)個(gè)體的適應(yīng)度函數(shù)值進(jìn)行計(jì)算,其選取直接影響到算法能否正確求解問(wèn)題以及計(jì)算的時(shí)間復(fù)雜度[13]。本文采用GDOP值作為適應(yīng)度函數(shù),定位精度與其關(guān)系可表示為:

σ=σUERE·GDOP

(2)

式中,σUERE為等效距離誤差,假設(shè)在不同衛(wèi)星系統(tǒng)組合情況下,其等效距離誤差大致相同;σ為定位精度。GDOP計(jì)算公式如下:

(3)

式中,

(4)

(5)

式中,trace(·)表示矩陣的跡,H表示可見(jiàn)衛(wèi)星的觀測(cè)矩陣,下標(biāo)C、R、G、E、J分別代表BDS、GLONASS、GPS、Galileo和QZSS(quasi-zenith satellite system, 準(zhǔn)天頂衛(wèi)星系統(tǒng)),I為單位矩陣,下標(biāo)x指代衛(wèi)星系統(tǒng),l、m、n為接收機(jī)位置到可見(jiàn)衛(wèi)星的方向余弦,上標(biāo)k為當(dāng)前系統(tǒng)可見(jiàn)衛(wèi)星數(shù)目。

2.2 算法實(shí)現(xiàn)步驟

在免疫算法中,免疫個(gè)體數(shù)為Np,最大迭代次數(shù)為G,X={x1,x2,…,xNp}為初始化種群個(gè)體集合,xi={y1,y2,…,yn}為每個(gè)個(gè)體所選的衛(wèi)星組合,算法詳細(xì)流程如圖1所示。

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

其具體算法步驟如下:

1)根據(jù)導(dǎo)航電文,獲取歷元可見(jiàn)衛(wèi)星的高度角。

2)設(shè)置截止高度角(10°),對(duì)可見(jiàn)衛(wèi)星進(jìn)行提取,并計(jì)算可用衛(wèi)星的觀測(cè)矩陣H。

3)根據(jù)觀測(cè)矩陣的行數(shù)獲取可用衛(wèi)星數(shù)目m,對(duì)可用衛(wèi)星從1到m進(jìn)行編號(hào),使之一一對(duì)應(yīng);將初始化種群數(shù)目和最大迭代次數(shù)作為改進(jìn)免疫算法的輸入?yún)?shù),進(jìn)行免疫計(jì)算,此時(shí)計(jì)時(shí)開(kāi)始。

5)根據(jù)設(shè)置的最大迭代次數(shù)進(jìn)行迭代運(yùn)算,對(duì)每個(gè)個(gè)體計(jì)算GDOP值即適應(yīng)度函數(shù),每次迭代保留適應(yīng)度函數(shù)值最好的個(gè)體。

6)當(dāng)?shù)鷶?shù)目達(dá)到設(shè)置的最大迭代次數(shù)G之后,免疫算法結(jié)束,停止計(jì)時(shí),輸出最小GDOP值和耗時(shí)。

2.3 免疫算法參數(shù)選取

免疫算法通過(guò)迭代次數(shù)和初始化種群大小從全局尋優(yōu)緩慢收斂到局部尋優(yōu)。為了尋求免疫算法運(yùn)算過(guò)程中最佳的迭代次數(shù)和初始化種群數(shù)目,本文利用CUT0測(cè)站2023-02-02觀測(cè)數(shù)據(jù)進(jìn)行實(shí)驗(yàn),所使用軟件為MATLAB R2018b,電腦搭載R5-4600H,3.00 GHz處理器,16GB RAM。其中GDOP差值指免疫算法所尋找的最小GDOP值與遍歷法之間的差值,時(shí)間的度量從計(jì)算出當(dāng)前所有觀測(cè)衛(wèi)星的觀測(cè)矩陣H進(jìn)入免疫算法開(kāi)始,判斷免疫算法迭代次數(shù)是否到達(dá)設(shè)置的最大迭代次數(shù),滿足條件則結(jié)束。本文設(shè)置截止高度角為10°,通過(guò)固定初始化種群數(shù)目(從20開(kāi)始,步長(zhǎng)為20,直至60結(jié)束),分別對(duì)最大迭代次數(shù)取不同值(從80開(kāi)始,步長(zhǎng)為20,直至140結(jié)束)進(jìn)行討論,實(shí)驗(yàn)結(jié)果如圖2、表1所示。

表1 初始化種群數(shù)目與迭代次數(shù)對(duì)選星性能的影響

圖2 初始化種群數(shù)目與迭代次數(shù)對(duì)性能的影響Fig.2 Effects of initial population number and iterations on positioning performance

由圖2、表1可知,GDOP差值均在0～0.5之間波動(dòng),且較為穩(wěn)定,表明免疫算法能夠大概率搜索到與遍歷法結(jié)果一致的GDOP值,而小部分由于隨機(jī)生成的初始化種群而無(wú)法保證其良好的多樣性,從而獲取與遍歷法相近略大的GDOP值,即局部最優(yōu)解[14]。當(dāng)初始化種群數(shù)目固定時(shí),隨著迭代次數(shù)增加,其GDOP差值呈現(xiàn)減小的趨勢(shì),但耗時(shí)明顯增加。初始化種群數(shù)目為60和最大迭代次數(shù)為140時(shí),平均GDOP值差值僅為0.128,說(shuō)明免疫算法能夠搜索到最佳的衛(wèi)星組合。當(dāng)固定最大迭代次數(shù)為120、初始化種群數(shù)目為20時(shí),平均耗時(shí)最少,為0.860 s。為了更加直觀地分析初始化種群數(shù)目與最大迭代次數(shù)對(duì)選星實(shí)時(shí)性的影響,表2(單位%)為選星耗時(shí)百分比。

表2 選星耗時(shí)百分比

從表2可知,在最大迭代次數(shù)固定的前提下,初始化種群數(shù)目從20到60,其耗時(shí)比((t遍歷法-t免疫算法)/t遍歷法×100%)減少,減小幅度大致相當(dāng);在初始化種群固定的前提下,最大迭代次數(shù)從80到140,耗時(shí)比減小,從120到140減小幅度最大。因此,在考慮實(shí)時(shí)性與定位精度雙重因素下,初始化種群數(shù)目可選在20附近、最大迭代次數(shù)可選擇在120附近。

3 實(shí)驗(yàn)驗(yàn)證與分析

為了驗(yàn)證本文所提算法對(duì)不同衛(wèi)星系統(tǒng)組合是否具有普適性,在初始化種群數(shù)目設(shè)置為20、最大迭代次數(shù)設(shè)置為120的前提下,系統(tǒng)分析不同衛(wèi)星系統(tǒng)組合(G、C、G/C、G/C/E、G/C/E/R、G/C/E/R/J)下的選星耗時(shí)和平均GDOP差值,結(jié)果如圖3所示。

圖3 不同衛(wèi)星系統(tǒng)組合下的選星耗時(shí)和GDOP差值Fig.3 Satellite selection time consuming and GDOP difference under different satellite system combinations

由圖3(a)～(c)可知,利用G、C單系統(tǒng)和C/G雙系統(tǒng)進(jìn)行定位時(shí),在固定選星數(shù)目情況下改進(jìn)免疫算法求得的最小GDOP與遍歷法結(jié)果幾乎一致,且GDOP差值最大不超過(guò)0.07。平均耗時(shí)在0.5～0.6 s內(nèi)波動(dòng),處于平穩(wěn)狀態(tài)。由圖3(d)～(f)可知,GDOP差值存在較大波動(dòng),總體介于0～0.4之間,部分歷元平均耗時(shí)明顯上升,但最大耗時(shí)不超過(guò)2.0 s。為了量化所提算法的性能,表3為不同系統(tǒng)組合下2種選星算法的GDOP值以及計(jì)算耗時(shí)。

表3 兩種選星算法的GDOP值和平均耗時(shí)

由表3可知,隨著衛(wèi)星數(shù)增加,遍歷法平均耗時(shí)急劇上升,當(dāng)可見(jiàn)衛(wèi)星數(shù)目為45時(shí),遍歷法耗時(shí)高達(dá)29.976 s,嚴(yán)重影響接收機(jī)的實(shí)時(shí)性。改進(jìn)免疫算法的平均耗時(shí)雖然也隨可見(jiàn)衛(wèi)星數(shù)的上升而增加,但上升幅度較小,在五系統(tǒng)組合情況下,耗時(shí)僅為1.06 s。改進(jìn)免疫算法計(jì)算的GDOP值與遍歷法結(jié)果相差較小,最大差值約為0.2。與遍歷法相比,本文所提方法在進(jìn)行GPS、BDS單系統(tǒng)定位時(shí)平均耗時(shí)分別縮短40.58%、53.27%,平均 GDOP差值與遍歷法的比值分別為0.44%、0.57%。在GPS/BDS組合系統(tǒng)下,與遍歷法相比,改進(jìn)的免疫算法平均GDOP差值僅為0.011,耗時(shí)縮短69.74%。在GPS/BDS/Galileo三系統(tǒng)、GPS/BDS/Galileo/GLONASS四系統(tǒng)、GPS/BDS/Galileo/GLONASS/QZSS五系統(tǒng)組合定位時(shí),本文算法的平均耗時(shí)分別縮短93.37%、96.21%、96.47%,其平均GDOP與遍歷法相差分別為0.159、0.152、0.122,因此改進(jìn)的免疫算法在多 GNSS 系統(tǒng)組合定位時(shí)均具有良好的性能。

4 結(jié) 語(yǔ)

本文提出一種基于改進(jìn)免疫算法的GNSS快速選星方法,可有效降低運(yùn)算量,提高接收機(jī)定位實(shí)時(shí)性。在考慮實(shí)時(shí)性與定位精度雙重因素下,選擇最佳的初始化種群數(shù)目與最大迭代次數(shù)。最后,通過(guò)實(shí)測(cè)數(shù)據(jù)驗(yàn)證所提方法的有效性及普適性,結(jié)論如下:

1)初始化種群數(shù)目在20附近、最大迭代次數(shù)在120附近,免疫算法的選星性能最優(yōu),其耗時(shí)與遍歷法相比縮短93.42%。

2)在單BDS 系統(tǒng)定位時(shí),本文所提算法平均GDOP 值與遍歷法相差僅為0.01,平均 GDOP 差值與遍歷法的比值僅為0.57%,耗時(shí)比遍歷法縮短53.27%。

3)在不同系統(tǒng)組合下,包括GPS/BDS/Galileo、GPS/BDS/Galileo/GLONASS和GPS/BDS/Galileo/GLONASS/QZSS,本文所提算法相對(duì)于遍歷法,GDOP誤差不超過(guò)0.5,并且平均耗時(shí)分別縮短93.37%、96.21%和96.47%。因此,該算法適用于多個(gè)GNSS系統(tǒng)組合下的定位,具有良好的普適性。