楊 光，屈德新*，張更新

(1.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003；2.南京郵電大學(xué) 通信與網(wǎng)絡(luò)技術(shù)國家地方聯(lián)合工程研究中心，江蘇 南京 210003)

0 引言

隨著全球?qū)Ш叫l(wèi)星系統(tǒng)(Global Navigation Sate-llite System,GNSS)的快速發(fā)展,越來越多的領(lǐng)域?qū)NSS運用到工程當中,從而使得更多的人從中受益。然而,在導(dǎo)航系統(tǒng)快速發(fā)展的同時,為了提高適用性以及可靠性,對該系統(tǒng)的要求也越來越嚴格,其中就包括更短的定位耗時以及更高的定位精度。由此,全世界各個有能力的國家都將發(fā)展自己的導(dǎo)航衛(wèi)星列為國家的長期發(fā)展規(guī)劃。截至目前,全球已經(jīng)建成了4套完善的全球定位系統(tǒng):中國的BDS、歐盟的Galileo、俄羅斯的GLONASS以及美國的GPS,已有超過120顆全球?qū)Ш叫l(wèi)星在軌運行,能夠?qū)崿F(xiàn)在同一地點有多顆衛(wèi)星為用戶提供服務(wù)。然而,隨著可見星數(shù)量的快速增加,如果將所有可見星同時應(yīng)用到定位中去,計算效率將會大幅度降低,其對定位精度的提升效果有限,因此,如何快速地從所有可見星中選出最優(yōu)構(gòu)型成為一個熱門問題。

選星是在獲取當前所有可見星位置、鐘差等信息后,確定一定數(shù)量的衛(wèi)星參與定位解算的過程。傳統(tǒng)選星過程以最小幾何精度因子(Geometric Dilution of Precision,GDOP)遍歷法[1]為基礎(chǔ),此外還有最大四面體體積法[2]、最大行列式法[3]、幾何布局算法[4]、最優(yōu)GPS遞歸算法[5]、GPS/Galileo組合導(dǎo)航定位系統(tǒng)選星算法[6]等。目前主要還是依據(jù)最小GDOP準則進行選星操作,然而如何簡化選取擁有最小GDOP值的衛(wèi)星組合成為了一個急需解決的問題。Mosavi等[7]提出了基于進化算法(EA)的自適應(yīng)濾波技術(shù)來計算GDOP的方法,但該方法存在一定的誤差。宋丹等[8]提出了一種基于遺傳算法的選星方法,該方法能夠快速準確地實現(xiàn)多個GNSS下選星顆數(shù)大于4的選星。徐小鈞等[9]提出了一種將選星數(shù)目和GDOP值同時作為目標的基于NSGA-II遺傳算法的多星座選星方法,該算法能夠綜合優(yōu)化GDOP和選星數(shù)目,同時保證較小的計算量和更高的定位精度。張兆龍等[10]提出了一種將BP神經(jīng)網(wǎng)絡(luò)和遺傳算法結(jié)合的選星算法,既大大減小了計算量,又增加了選星的準確率。王爾申等[11]提出了一種基于人工魚群算法的粒子群優(yōu)化選星算法,利用人工魚群算法良好的全局收斂特性,克服粒子群算法易于陷入局部最優(yōu)的缺點,使其準確率優(yōu)于標準PSO選星算法。王暉等[12]提出了一種顧及信噪比的蝙蝠選星算法,通過設(shè)置信噪比閾值,剔除信號受干擾的衛(wèi)星,結(jié)合選星算法的高效率優(yōu)點,減少選星耗時。余德熒等[13]提出了一種基于灰狼優(yōu)化(Grey Wolf Optimizer,GWO)算法的快速選星方法,利用自適應(yīng)收斂因子和信息反饋機制,避免局部極值,能夠大幅度減小計算量。石濤等[14]提出了一種利用多種群并行遺傳算法(Parallel Genetic Algorithm,PGA)進行快速選擇當前最優(yōu)可見星組合的方法,該方法可以有效地在典型高軌環(huán)境下快速準確地完成選星。邱明等[15]提出了基于帝國競爭優(yōu)化算法的雙目標選星算法,通過引入可見星仰角和方向角先驗信息,同時約束GDOP以及選星數(shù),提高選星靈活度。

雖然上述算法在不同程度上提高了選星效率,但為了避免局部最優(yōu),需要多次實驗尋找最優(yōu)的參數(shù)配置,從而實現(xiàn)尋得全局最優(yōu)解。哈里斯鷹優(yōu)化(Harris Hawks Optimization,HHO)算法是Heidari等[16]于2019年提出的一種新型群體智能算法,整個尋優(yōu)過程包括探索、探索與開發(fā)轉(zhuǎn)換和開發(fā)3個階段,具有原理簡單、控制參數(shù)少和全局搜索能力出色等特點。HHO算法相較于其他成熟的元啟發(fā)式技術(shù)而言,提供了非常有前途的結(jié)果,有時甚至具有競爭性,同時以靈活的結(jié)構(gòu)、高性能和高質(zhì)量的結(jié)果越來越受到研究人員的關(guān)注,在作業(yè)車間調(diào)度[17]、神經(jīng)網(wǎng)絡(luò)[18]、惡意軟件檢測[19]、定位解算[20]和結(jié)構(gòu)體壽命預(yù)測[21]等領(lǐng)域得到廣泛應(yīng)用。

鑒于目前沒有將HHO算法應(yīng)用于GNSS系統(tǒng)快速選星的研究,本文將HHO算法引入到多GNSS組合導(dǎo)航選星過程中,建立了基于HHO算法的快速選星模型。通過對多GNSS下不同時間、不同選星顆數(shù)、HHO算法種群數(shù)以及算法迭代次數(shù)進行仿真實驗,以GWO、改進粒子群算法(Improved Particle Swarm Optimization,IPSO)以及遍歷法結(jié)果作為對比,驗證了HHO算法的快速選星能力和高準確率。

1 HHO算法

1.1 算法背景

HHO算法靈感來源于哈里斯鷹在自然界中的合作行為和追逐方式,稱為“突襲”,在該策略中,幾只老鷹合作從不同方向撲向獵物,試圖以出乎意料的方式將其捕獲。整個搜索過程可以分為3個階段:① 探索階段;② 探索與開發(fā)轉(zhuǎn)換階段;③ 開發(fā)階段。

1.2 數(shù)學(xué)模型

在每次迭代過程中,為了確定下一次位置更新策略,將擁有最優(yōu)適應(yīng)度值的哈里斯鷹作為獵物或者預(yù)期的獵物。

1.2.1 探索階段

此階段哈里斯鷹會隨機飛抵某些位置,并根據(jù)2種策略探索獵物。如果每種飛行策略機會p相等,隨機生成p的大小,當p≤0.5時,哈里斯鷹根據(jù)其他成員和獵物的位置進行棲息;當p>0.5時,則隨機棲息在鷹群活動范圍內(nèi)的大樹上,具體模型為:

(1)

(2)

式中:X(t+1)為下一次迭代中鷹的坐標向量,Xrabbit(t)為獵物的坐標(即擁有最優(yōu)適應(yīng)度的個體坐標),X(t)為當前鷹的位置向量,r1、r2、r3、r4和p為(0,1)的隨機數(shù),UB、LB為位置數(shù)據(jù)的上下限,Xrand(t)為在所有已知的鷹群中隨機選擇的鷹的坐標,Xm(t)為坐標的平均值,N為鷹群大小,Xi(t)為當前第i只鷹的坐標。

1.2.2 探索到開發(fā)的轉(zhuǎn)換

HHO算法會從探索轉(zhuǎn)到開發(fā)階段,隨后根據(jù)獵物的逃逸能量在不同的開發(fā)行為之間進行轉(zhuǎn)換。獵物逃跑會導(dǎo)致能量下降,逃逸能量可表示為:

(3)

式中:E表示獵物逃逸能量,T為最大迭代次數(shù),t為當前迭代次數(shù),E0為能量初始狀態(tài),是(-1,1)的隨機數(shù)。當|E|≥1時,哈里斯鷹處于探索階段,反之進入開發(fā)階段,進而采取不同的更新策略。

1.2.3 開發(fā)階段

當鷹處于開發(fā)階段時,會對之前發(fā)現(xiàn)的預(yù)定獵物進行突襲捕捉,同時,獵物也在嘗試逃脫追捕。因此,在實際情況下會根據(jù)獵物狀態(tài)采用不同的捕獵風格。HHO依據(jù)獵物的逃逸風格和哈里斯鷹的追逐策略,提出了4種策略去模擬攻擊階段。此處定義r用來表示獵物在突襲前是否有機會逃脫,當r<0.5時表示有機會逃脫,反之則沒有機會。

① 軟圍攻

在r≥0.5且|E|>0.5時,獵物有足夠的能量,但沒有逃脫的機會,只能通過隨機跳動來嘗試逃脫,在此過程中哈里斯鷹輕柔地包圍獵物,使其疲憊后再進行突襲。此行為可以建模為:

X(t+1)=ΔX(t)-E|JXrabbit(t)-X(t)|,

(4)

式中:ΔX(t)為最優(yōu)個體和當前個體的差值,J為獵物逃跑時移動的距離。

ΔX(t)=Xrabbit(t)-X(t),

(5)

J=2(1-r5),

(6)

式中:r5為(0,1)的隨機數(shù)。

② 硬圍攻

在r≥0.5且|E|≤0.5時,獵物既沒有逃脫的機會,也沒有足夠的逃脫能量,此時哈里斯鷹采用硬包圍的方式捕獲獵物,該行為可以建模為:

X(t+1)=Xrabbit(t)-E|ΔX(t)|。

(7)

圖1為哈里斯鷹進行硬圍攻時的示例。

圖1 硬圍攻矢量示例Fig.1 Hard siege vector example

③ 漸進式快速俯沖的軟包圍

在r<0.5且|E|>0.5時,獵物有機會逃脫,并且有足夠的能量,因此哈里斯鷹需要在進攻前形成一個更加智能的軟包圍圈,采用2種策略實施,根據(jù)情況選擇其中一個策略。

策略1:

Y=Xrabbit(t)-E|JXrabbit(t)-X(t)|。

(8)

策略2:

Z=Y+S×LF(D),

(9)

式中:D為問題維度,S為一個D維的隨機向量,LF為Levy函數(shù)。

(10)

式中:

(11)

u和v為(0,1)的D維隨機向量,β=1.5,Γ( )為伽瑪函數(shù)。策略選擇標準如式(12)所示:

(12)

式中:F()為適應(yīng)度函數(shù),即GDOP值。

這一過程的矢量示例如圖2所示。

圖2 漸進式快速俯沖的軟包圍矢量示例Fig.2 Example of soft encirclement vector for progressive rapid subduction

④ 漸進式快速俯沖的硬包圍

在r<0.5且|E|≤0.5時,獵物有機會逃脫,但能量不足,此時哈里斯鷹在突襲前形成一個硬包圍圈,縮小和獵物的平均距離,策略如下:

(13)

Y=Xrabbit(t)-E|JXrabbit(t)-Xm(t)|,

(14)

Z=Y+S×LF(D)。

(15)

2 基于HHO算法的快速選星方法

2.1 哈里斯鷹算法適應(yīng)度函數(shù)

在多GNSS中,用戶從接收機獲取的自身位置精度與接收機中觀測到的參與定位的衛(wèi)星幾何構(gòu)型和偽距值有關(guān),其中幾何構(gòu)型用GDOP表示。其值越小,表示利用該衛(wèi)星構(gòu)型進行定位時定位精度越高,因此選用GDOP值作為HHO算法的適應(yīng)度函數(shù)。

(16)

式中:tr(*)表示取矩陣的跡,H為觀測矩陣。在多GNSS中,同時可觀測到BDS、Galileo、GLONASS以及GPS組成的多顆衛(wèi)星,此時H可表示為:

(17)

式中:下標分別代表對應(yīng)所屬的衛(wèi)星系統(tǒng)。假設(shè)某一個系統(tǒng)有n顆衛(wèi)星參與定位,則此時H*為n行3列矩陣,3列分別是各個衛(wèi)星與觀測站連線在(x,y,z)軸上的方向余弦,1*為n行1列的純1向量,0*為n行1列的純0向量。

2.2 哈里斯鷹選星算法設(shè)計

圖3 HHO選星算法流程Fig.3 Flowchart of HHO satellite selection algorithm

具體的選星步驟如下:

步驟①:提取可見星。根據(jù)導(dǎo)航電文,獲取當前仰角大于5°的所有可見星。

步驟②:編號。將獲取的所有可見星按PRN由小到大編號為:1,2,3,…,m。

步驟③:初始化種群。設(shè)種群數(shù)為j,從m顆可見星中隨機抽取n顆進行組合,產(chǎn)生j只不同的鷹構(gòu)成一個種群。

步驟④:計算適應(yīng)度值。計算每只鷹對應(yīng)的GDOP值作為該只鷹的適應(yīng)度值,將適應(yīng)度值最小的鷹作為當前目標組合。

步驟⑤:迭代更新。計算當前獵物能量E,隨機生成r,根據(jù)值的不同決定采用探索還是不同的開發(fā)策略,從而產(chǎn)生新的衛(wèi)星組合,計算更新后的適應(yīng)度值,將本次迭代適應(yīng)度值與原目標組合適應(yīng)度值比較,將適應(yīng)度值小的組合作為本次迭代目標組合。不斷重復(fù)本步驟,直至達到最大迭代次數(shù),當前目標組合即最優(yōu)衛(wèi)星組合。

3 HHO選星算法性能分析

針對智能優(yōu)化算法在多GNSS選星中的應(yīng)用,參數(shù)選擇是決定算法性能的關(guān)鍵。在HHO選星算法中,主要影響選星性能的參數(shù)為種群規(guī)模(鷹的數(shù)量)和迭代次數(shù)(搜索次數(shù)),規(guī)模和次數(shù)的差異對選星誤差和耗時有著較大的影響。

群體智能優(yōu)化算法是將種群逐漸向真值逼近的算法,但因存在隨機性和初始種群選取的差別,每次結(jié)果并不一定能夠與真值保持一致。因此,為了具象化算法的選星性能,對算法進行了多次蒙特卡羅實驗,最后統(tǒng)計出GDOP最大、最小和平均值,最大值表示此時衛(wèi)星構(gòu)型最差,最小值表示此時構(gòu)型最優(yōu),平均值則反映了算法的平均選星性能。遍歷法的選星結(jié)果是最優(yōu)結(jié)果,將遍歷法結(jié)果與HHO法選星結(jié)果比較可以看出HHO法選星的性能。

3.1 鷹群個體數(shù)對HHO選星性能的影響

將迭代次數(shù)固定為40,鷹群個體數(shù)依次設(shè)置為20、40、60、80、100,各進行100次蒙特卡羅實驗求取均值,分析鷹群個體數(shù)對選星性能的影響,結(jié)果如圖4～圖6和表1所示。

圖4 種群數(shù)引起的GDOP值變化Fig.4 Changes in GDOP value caused by population number

圖5 種群數(shù)引起的計算耗時變化Fig.5 Changes in calculation time due to population number

圖6 種群數(shù)引起的GDOP誤差變化Fig.6 Changes in GDOP error due to population number

表1 鷹群個體數(shù)對算法性能影響

分析圖5和表1的數(shù)據(jù)可知,增加種群規(guī)模也會增加選星算法的耗時,由開始的0.057 1 s逐漸增加到0.279 0 s,但仍舊低于遍歷法的耗時?？梢奌HO選星算法能夠?qū)崿F(xiàn)在保證準確率的前提下快速選出最優(yōu)構(gòu)型。

3.2 迭代次數(shù)對HHO選星性能的影響

將鷹群個體數(shù)固定為40,迭代次數(shù)依次設(shè)置為20、40、60、80、100,進行同3.1節(jié)的實驗,結(jié)果如圖7～圖9和表2所示。

圖7 迭代次數(shù)引起的GDOP值變化Fig.7 Changes in GDOP values caused by the number of iterations

圖8 迭代次數(shù)引起的計算耗時變化Fig.8 Change in computation time due to the number of iterations

由圖7～圖9可以看出,隨著迭代次數(shù)的增加,其選星性能變化類似于種群數(shù)對HHO選星性能的影響。在迭代次數(shù)增加過程中,選星性能逐漸提高,最終GDOP值逼近遍歷法的選星結(jié)果,可見,通過增加迭代次數(shù)能夠有效改善HHO選星算法性能。

表2 迭代次數(shù)對算法性能影響

通過觀察表2的數(shù)據(jù)可以直觀地發(fā)現(xiàn)迭代次數(shù)對HHO選星算法性能的影響。

結(jié)合3.1和3.2節(jié)的仿真分析可知,種群規(guī)模和迭代次數(shù)對于HHO選星算法的性能起著關(guān)鍵作用,需要在誤差和耗時之間做折中。因此要想最大限度地保證HHO選星的性能,正確地選取種群規(guī)模和迭代次數(shù)至關(guān)重要。由表1可以看出,在種群規(guī)模數(shù)達到40時,GDOP誤差變化不再明顯;在表2中,迭代次數(shù)在40～60誤差變化率為0.341%,而在60～80變化率只有0.125 8%,因此,在迭代次數(shù)達到60后誤差下降速度不顯著。綜上所述,在下一節(jié)的仿真驗證中,采取種群規(guī)模數(shù)為40、迭代次數(shù)為60,以實現(xiàn)在保證選星準確率的前提下盡量降低選星時間。

4 仿真驗證與結(jié)果分析

在定位前進行選星操作可以從多顆冗余星中選出最優(yōu)的衛(wèi)星構(gòu)型,從而保證定位精度。為了驗證HHO算法的選星性能,利用衛(wèi)星工具包(Satellite Tool Kit,STK)導(dǎo)出BDS、Galileo、GLONASS以及GPS的星歷數(shù)據(jù),進行仿真分析。仿真所用軟件為Matlab 2016b和STK 11.2,計算機搭載CPU處理器(i7-11800H,2.3 GHz)、RAM 32 GB。

實驗1:在STK中設(shè)置接收機的位置為南京(118.78°,32.10°,0),加入BDS、Galileo、GLONASS和GPS共68顆衛(wèi)星,起始時間為2022-10-13T04:00:00,導(dǎo)出不同時刻接收機能同時獲取的仰角大于5°的衛(wèi)星星歷數(shù)據(jù)。將選星算法的種群規(guī)模設(shè)置為40,迭代次數(shù)設(shè)置為60,選7顆星,仿真時長為90 min,仿真步長為1 min。仿真結(jié)果如圖10、圖11和表3、表4所示。

圖10 不同選星時間GDOP值誤差變化Fig.10 GDOP value error changes at different time of satellite selection

圖11 不同選星時間耗時變化Fig.11 Time consuming changes at different time of satellite selection

表3 不同算法選星GDOP誤差

表4 不同算法與遍歷法的選星耗時差值

圖10和圖11分別為不同時刻的HHO法、GWO法、IPSO法和遍歷法選星的GDOP和耗時差值。由圖10可以看出,在選星的不同時刻,3種優(yōu)化算法的選星結(jié)果均逼近遍歷法選星,GDOP誤差最大接近0.08,但HHO法選星GDOP誤差普遍低于另外2種算法,結(jié)合表3不難發(fā)現(xiàn),在90 min內(nèi),HHO法選星結(jié)果的GDOP平均誤差為0.008 2,遠低于另外2種優(yōu)化算法的0.010 1和0.010 5。由圖11可以看出,3種優(yōu)化算法選星與遍歷法選星耗時差異較大,選星耗時遠低于遍歷法選星耗時,其中HHO法選星耗時高于GWO法,低于IPSO法,主要原因是GWO算法實現(xiàn)最為簡單,算法的復(fù)雜度最低,該算法實現(xiàn)僅需3個階段:包圍獵物、追蹤獵物、攻擊與搜索獵物,且迭代公式的復(fù)雜度較低。而HHO算法雖也分3個階段,但在第3階段中需要依據(jù)獵物的逃逸風格和哈里斯鷹的追逐策略,從4種策略中選擇一種去模擬該階段,且迭代公式的計算復(fù)雜度略高于GWO法。而IPSO法由于引入粒子交叉和淘汰替換機制,復(fù)雜度高于HHO法。結(jié)合表4數(shù)據(jù),GWO法耗時差值最大,為0.477 5 s,其次為HHO法,差值為0.342 8 s,最小值為IPSO算法的0.329 3 s。綜上,HHO法耗時雖然略高于結(jié)構(gòu)較為簡單的GWO法耗時,但其GDOP誤差卻遠低于另外2種算法,在實際選星過程中性能滿足準確率和實時性的要求,能夠?qū)崿F(xiàn)在保證準確率的前提下快速選星。

實驗2:采用實驗1的參數(shù),進行30次重復(fù)實驗求均值,仿真HHO法在2022-10-13T04:00:00選擇不同衛(wèi)星數(shù)時的選星性能,此時仰角大于5°的可用星有17顆。在BDS/GPS雙系統(tǒng)時選5顆星,在BDS/GPS/GLONASS三系統(tǒng)時選6顆星,在BDS/GPS/GLONASS/Galileo四系統(tǒng)時選7、8、9顆星。仿真結(jié)果如圖12～圖15和表5、表6所示。

圖12 不同選星數(shù)GDOP值變化Fig.12 GDOP value changes with different number of selected satellites

圖13 不同選星數(shù)GDOP計算誤差變化Fig.13 Calculation error variation of GDOP with different number of selected satellites

圖14 不同選星數(shù)耗時變化Fig.14 Time consuming change of different satellite selection number

圖15 不同選星數(shù)節(jié)省時間變化Fig.15 Different number of satellites to save time change

表5 不同選星數(shù)選星GDOP值

表6 不同選星數(shù)選星耗時

5 結(jié)論

本文提出了一種基于HHO的多GNSS星座選星算法,通過Matlab仿真分析驗證了算法性能。首先給出了HHO算法的模型;接著將HHO算法引入到選星過程中,以GDOP值作為適應(yīng)度函數(shù)來衡量選星準確率,給出了HHO選星算法的實現(xiàn)步驟;之后考慮了HHO算法的參數(shù)設(shè)置對選星性能的影響,通過仿真來確定合適參數(shù)的選取;最后利用STK導(dǎo)出的衛(wèi)星星歷進行性能驗證。結(jié)論如下:

① HHO法選星性能受迭代次數(shù)和種群數(shù)影響,選星準確率與其成正比關(guān)系,但選星效率會下降。選取種群規(guī)模為40,迭代數(shù)為60可以兼顧選星準確率和效率。

② 對STK導(dǎo)出的90 min內(nèi)數(shù)據(jù),利用HHO法、GWO法、IPSO法與遍歷法對比,HHO法選星GDOP平均誤差為0.008 2,平均耗時差值為0.342 8 s,可見HHO選星性能優(yōu)異。

③ HHO選星算法對選多星有優(yōu)勢,選星數(shù)越多,性能越好,當種群數(shù)量為40,迭代次數(shù)為60,選星數(shù)達到9顆時,HHO選星算法相較于遍歷法計算效率提升了75.168 4%,而此時GDOP誤差為0。

④ HHO選星算法在實際應(yīng)用時可根據(jù)自身需求,通過改變種群規(guī)模數(shù)和迭代次數(shù)在實時性和準確率之間做取舍。將來的研究將聚焦于自適應(yīng)選取參數(shù)、多算法混合使用和單算法優(yōu)化等方面,以提高選星性能。