甘宇婷 陳 健 趙興旺 劉 超

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

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

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

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

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

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

1 免疫算法

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

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

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

(1)

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

3)克隆算子?？寺∈菍⒎弦蟮姆N群個體進(jìn)行復(fù)制,其可以描述為Tc(abi)=clone(abi),其中clone(abi)為mi個與abi相同的克隆構(gòu)成集合,mi為克隆數(shù)目,根據(jù)實(shí)際情況設(shè)定。

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

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

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

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

σ=σUERE·GDOP

(2)

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

(3)

式中,

(4)

(5)

式中,trace(·)表示矩陣的跡,H表示可見衛(wèi)星的觀測矩陣,下標(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ī)位置到可見衛(wèi)星的方向余弦,上標(biāo)k為當(dāng)前系統(tǒng)可見衛(wèi)星數(shù)目。

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

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

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

其具體算法步驟如下:

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

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

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

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

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

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

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

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

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

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

表2 選星耗時百分比

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

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

為了驗(yàn)證本文所提算法對不同衛(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)下的選星耗時和平均GDOP差值,結(jié)果如圖3所示。

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

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

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

4 結(jié) 語

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

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

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

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