基于混沌粒子群優(yōu)化的北斗/GPS組合導(dǎo)航選星算法

王爾申， 賈超穎， 曲萍萍， 黃煜峰， 龐濤， 別玉霞， 姜毅

(1. 沈陽航空航天大學(xué) 電子信息工程學(xué)院， 沈陽 110136； 2. 北京航空航天大學(xué) 電子信息工程學(xué)院， 北京 100083; 3. 沈陽航空航天大學(xué) 遼寧省通用航空重點(diǎn)實(shí)驗(yàn)室， 沈陽 110136；4. 大連海事大學(xué) 水上智能交通行業(yè)重點(diǎn)實(shí)驗(yàn)室， 大連 116026)

隨著全球衛(wèi)星導(dǎo)航系統(tǒng)(Global Navigation Satellite System, GNSS)的不斷建設(shè)和完善，由多個(gè)系統(tǒng)支持的組合導(dǎo)航成為了可能。組合導(dǎo)航使得可見衛(wèi)星數(shù)大大增加，獲得遠(yuǎn)比單一星座更優(yōu)的衛(wèi)星幾何結(jié)構(gòu)和更多的導(dǎo)航冗余信號，同時(shí)也加大了接收機(jī)的信號處理負(fù)擔(dān)[1-2]。此外，導(dǎo)航信號在傳播過程中還會受到電離層延遲、對流層延遲、建筑物遮擋、電磁波干擾等因素的影響，接收機(jī)很難接收到全部可見衛(wèi)星。為此，根據(jù)導(dǎo)航需求，在定位之前粗略判別接收機(jī)所在位置的可見衛(wèi)星分布，從中選擇一個(gè)衛(wèi)星子集進(jìn)行定位解算。通過最小化幾何精度因子(Geometric Dilution of Precision, GDOP)來獲得最佳衛(wèi)星子集的算法稱為最優(yōu)選星算法；以使接收機(jī)與可見衛(wèi)星構(gòu)成空間體積盡可能大，選擇衛(wèi)星子集最佳的算法稱為最大體積算法。對于單一系統(tǒng)，由于定位和時(shí)鐘偏差，定位所需的衛(wèi)星最小數(shù)目為4顆[3]，而對于組合導(dǎo)航，由于不同系統(tǒng)的時(shí)鐘偏差有所差異，用于定位的衛(wèi)星數(shù)目最少為5顆[4]。因而，對于組合導(dǎo)航選星算法通常選擇超過5顆衛(wèi)星來盡可能提高定位精度。

現(xiàn)有的快速選星算法主要集中在2個(gè)方面：①從所有可見衛(wèi)星中選擇最佳衛(wèi)星幾何分布的某些可見衛(wèi)星。研究者根據(jù)最優(yōu)選星方案的衛(wèi)星分布特點(diǎn)，利用衛(wèi)星高度角和方位角信息實(shí)現(xiàn)衛(wèi)星的區(qū)域劃分，并對如何分配高仰角和低仰角的選星數(shù)目展開討論[5-6]。②GDOP的計(jì)算。GDOP通?？煽醋魇墙邮諜C(jī)測量誤差與定位誤差之間的放大倍數(shù)，是用來衡量從m顆可見衛(wèi)星(m>n)中選擇出的n顆衛(wèi)星子集是否具有較好的空間幾何分布的重要指標(biāo)。GDOP的計(jì)算存在矩陣相乘和求逆過程，明顯增加了選星的計(jì)算量。若實(shí)現(xiàn)快速選星，可通過求逆引理等方法簡化求解GDOP的計(jì)算公式[7]，也可以采用優(yōu)化算法盡可能減少GDOP的計(jì)算次數(shù)[8-10]，二者都能在一定程度上縮減選星耗時(shí)。2010年，Mosavi和Divband[8]提出用遺傳算法(GA)實(shí)現(xiàn)選星，通過GA的快速尋優(yōu)能力減少GDOP的計(jì)算次數(shù)。然而GA選星存在易陷入局部最優(yōu)的問題，研究者又對算法進(jìn)行大量改進(jìn)，提高了算法選星結(jié)果的準(zhǔn)確性[9-10]。但由于GA的計(jì)算過程需要調(diào)節(jié)的參數(shù)過多，所以在保證選星準(zhǔn)確性的條件下，GA選星速度也會隨著可見衛(wèi)星數(shù)目的增加而減慢。

與GA類似，粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法是一種隨機(jī)尋優(yōu)算法。目前該算法已經(jīng)在目標(biāo)跟蹤、圖像處理等諸多領(lǐng)域得到應(yīng)用[11-12]，但在多星座選星方面少有文獻(xiàn)提及。本文針對PSO算法在組合導(dǎo)航選星上的應(yīng)用進(jìn)行研究，建立了PSO選星算法模型；引入混沌序列改進(jìn)算法，提高選星有效性；通過實(shí)際的導(dǎo)航數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證所提算法的性能。

1 混沌粒子群優(yōu)化模型

在多星座組合衛(wèi)星導(dǎo)航系統(tǒng)中，為了降低接收機(jī)的運(yùn)算量，需要從可見的所有衛(wèi)星中選出空間結(jié)構(gòu)較優(yōu)的一組用于定位。精度因子(DOP)常用來衡量衛(wèi)星空間幾何分布情況，其計(jì)算公式中存在矩陣相乘和求逆，是選星中比較耗時(shí)的運(yùn)算。而PSO算法能夠通過有限次迭代，從全部解空間中快速搜索到符合條件的目標(biāo)解。因此，運(yùn)用PSO算法的快速尋優(yōu)能力，從全部可見衛(wèi)星組合中快速選取空間幾何分布較好的衛(wèi)星組合，能夠減少DOP的計(jì)算次數(shù)，從而減少選星的耗時(shí)。

PSO算法是Eberhart和Kennedy通過模仿鳥類的覓食行為而產(chǎn)生的[13]，搜索空間的個(gè)體通過比較自身所經(jīng)過的最優(yōu)位置和種群中其他粒子最優(yōu)位置，不斷調(diào)整自身速度，使其向最優(yōu)解靠攏。個(gè)體被稱為“粒子”，每個(gè)粒子為d維空間的一個(gè)點(diǎn)，第i個(gè)粒子可以表示為xi=[xi1,xi2,…,xid]，粒子在運(yùn)動(dòng)過程中，會根據(jù)自身經(jīng)驗(yàn)產(chǎn)生個(gè)體極值pbest=[pi1,pi2,…,pid]，同時(shí)在種群中會產(chǎn)生全局極值gbest，粒子通過2個(gè)“極值”不斷調(diào)整自身位置，位置更新如式(1)所示，使其不斷趨近全局最優(yōu)值。第i個(gè)粒子的位置變化速度被表示為vi=[vi1,vi2,…,vid]。

vid(t+1)=ωvid(t)+c1r1(pbest-xid(t))+

c2r2(gbest-xid(t))

(1)

xid(t+1)=xid(t)+vid(t+1)i=1,2,…,N

(2)

式中：t為當(dāng)前迭代次數(shù)；N為種群中粒子的總數(shù)；ω為慣性權(quán)重；c1和c2為加速常數(shù)，分別調(diào)節(jié)向pbest和gbest方向的運(yùn)動(dòng)速度；r1和r2為0～1之間均勻分布的隨機(jī)數(shù)。另外，通過設(shè)置微粒的速度范圍[vmin,vmax]和位置范圍[xmin,xmax]，可以對粒子運(yùn)動(dòng)的步長進(jìn)行適當(dāng)?shù)南薅ā?/p>

慣性權(quán)重ω對全局和局部搜索的平衡起到了重要作用，其值通常是從0.9～0.4線性遞減的[14]。在迭代過程中，表達(dá)式為ω=ωmax-(ωmax-ωmin)t/tmax，ωmax和ωmin分別為最大和最小慣性權(quán)重，tmax為總的迭代次數(shù)。

PSO算法的結(jié)果容易陷入局部最優(yōu)，為此引入混沌理論，提高結(jié)果的有效性?；煦缢阉?，即對于給定的優(yōu)化函數(shù)，將變量從混沌空間映射到解空間，然后利用混沌變量進(jìn)行搜索[15]，可避免搜索結(jié)果陷入“局部最優(yōu)”。

Logistic映射是較為常見的混沌序列產(chǎn)生方法，其表達(dá)式為

zi+1=f(zi)=μzi(1-zi)i=0,1,…

(3)

式中：zi∈(0,1)。當(dāng)z0?{0,0.25,0.5,0.75,1}、μ=4時(shí)，Logistic映射產(chǎn)生混沌序列。利用Logistic映射初始化均勻分布的初始粒子，能夠增強(qiáng)PSO算法的穩(wěn)定性[16]。

首先生成(0,1)的隨機(jī)數(shù)zi，根據(jù)式(3)更新zi，然后根據(jù)公式xi=ximin+zi(ximax-ximin)，將混沌空間映射到待優(yōu)化的解空間。

2 北斗/GPS組合導(dǎo)航選星算法

2.1 混沌粒子群優(yōu)化適應(yīng)度函數(shù)

適應(yīng)度函數(shù)又稱為目標(biāo)函數(shù)，是用來評價(jià)粒子優(yōu)劣的重要衡量標(biāo)準(zhǔn)，適應(yīng)度函數(shù)的選取直接影響算法結(jié)果的有效性。本文采用的適應(yīng)度函數(shù)是各可見衛(wèi)星組合的GDOP值，用于評價(jià)所選衛(wèi)星組合的空間幾何結(jié)構(gòu)性能。

選星算法主要以用戶與可見衛(wèi)星組合的空間幾何分布為衡量標(biāo)準(zhǔn)。針對用戶與可見衛(wèi)星組合的空間幾何分布特性的表征，DOP是應(yīng)用最廣泛的參數(shù)，按照DOP進(jìn)行選星可以保證定位精度[1]。衛(wèi)星導(dǎo)航定位系統(tǒng)的DOP可用GDOP與用戶等效測距誤差(User Equivalent Range Error，UERE)的乘積來表示，即

σp=GDOP·σUERE

(4)

式中：σp為導(dǎo)航定位位置/時(shí)間解的精度；σUERE為偽距測量值的標(biāo)準(zhǔn)差；GDOP與用戶到衛(wèi)星的幾何結(jié)構(gòu)有關(guān)。從式(4)可知，當(dāng)σUERE確定時(shí)，GDOP越小，定位精度越高。

GDOP可定義為協(xié)方差矩陣的跡的平方根，即

(5)

式中：trace(·)表示矩陣的跡；H為觀測矩陣。假設(shè)北斗/GPS組合導(dǎo)航接收機(jī)能接收到m顆GPS衛(wèi)星、k顆北斗衛(wèi)星，即可產(chǎn)生m+k個(gè)觀測量，構(gòu)成的觀測矩陣為

(6)

式中：(ei,ni,ui)為接收機(jī)近似位置指向第i顆衛(wèi)星單位矢量的方向余弦，下標(biāo)G代表GPS星座，可見星數(shù)目為1，2,…，m,下標(biāo)B代表北斗星座，可見星數(shù)目為1，2,…，k。

2.2 混沌粒子群優(yōu)化選星算法設(shè)計(jì)

假設(shè)某時(shí)刻接收機(jī)接收到可見衛(wèi)星總數(shù)為n顆，從中選取m顆，使其GDOP值盡可能小。在混沌粒子群優(yōu)化(CPSO)算法選星中，每個(gè)粒子代表一種可見衛(wèi)星組合，粒子的位置由m個(gè)元素決定，每個(gè)元素代表一顆可見衛(wèi)星，CPSO選星算法具體步驟如下：

第二，重新評估開放獲取中采取的部分措施和手段。過去科學(xué)工作者出版時(shí)一般不需要考慮錢的問題，而向開放獲取期刊投稿時(shí)需要自籌出版處理費(fèi)，這樣不僅加重了科學(xué)工作者的負(fù)擔(dān)，而且將以付費(fèi)為基礎(chǔ)的學(xué)術(shù)傳播作為一種模式固化下來。出版商在開放獲取中形成的混合開放獲取模式，雖然增加了開放獲取資源的范圍和數(shù)量，但并沒有起到實(shí)質(zhì)性的作用。

步驟1可見衛(wèi)星提取。根據(jù)導(dǎo)航電文，提取當(dāng)前時(shí)刻仰角大于遮蔽角的衛(wèi)星(本文中的遮蔽角取值為5°)，得到該時(shí)刻的可見衛(wèi)星總數(shù)。

步驟2編碼。對當(dāng)前時(shí)刻接收機(jī)觀測到的所有可見衛(wèi)星進(jìn)行隨機(jī)排列，然后將可見衛(wèi)星從1,2,…,n依次連續(xù)編碼，編碼與可見衛(wèi)星一一對應(yīng)。

步驟4適應(yīng)度的計(jì)算。本文采用的適應(yīng)度函數(shù)是編碼所對應(yīng)的可見衛(wèi)星組合的GDOP，記為粒子的目標(biāo)值fti=GDOPi，下標(biāo)“t”為粒子經(jīng)過t次迭代。將初始種群中的粒子依次代入適應(yīng)度函數(shù)中，得出各粒子的適應(yīng)度值(即GDOP)。將種群中GDOP最小的粒子設(shè)置為初始種群最優(yōu)位置gbest，每個(gè)粒子當(dāng)前的位置gt,i為初始個(gè)體最優(yōu)位置pbest。

步驟5更新。對于每個(gè)粒子，根據(jù)式(1)和式(2)不斷修正種群中粒子的位置xti和速度vti，分別計(jì)算新位置對應(yīng)的目標(biāo)值fti，并更新粒子所經(jīng)過的最優(yōu)位置pbest和種群最優(yōu)位置gbest。直到達(dá)到最大迭代次數(shù)，終止迭代。

將CPSO算法應(yīng)用到選星過程中，需要明確3個(gè)量：初始化粒子種群、選取適應(yīng)度函數(shù)和速度位置的更新，其基本步驟流程如圖1所示。

在算法流程中，粒子更新時(shí)需注意2個(gè)關(guān)鍵點(diǎn)：①可見衛(wèi)星編號為整數(shù)，因此更新過程中必須

圖1 CPSO選星算法流程Fig.1 Flowchart of CPSO satellite selection algorithm

保證粒子位置中的每個(gè)元素都為整數(shù)，否則將找不到與編碼對應(yīng)的可見星；②選星顆數(shù)為m顆，如果粒子位置中的元素有相同的，選星顆數(shù)就會少于m顆。為了保證選星數(shù)目，每次更新都必須判斷更新后的粒子位置中是否有相同元素。本文給出的解決辦法是在粒子進(jìn)入迭代循環(huán)后，首先判斷每個(gè)粒子中是否存在相同的元素。如果存在相同元素，則對粒子中元素從小到大排序，找出相同元素的個(gè)數(shù)及位置，在與之重復(fù)的第k個(gè)元素值上加k，然后返回重新判斷是否有重復(fù)元素，直到該粒子中無相同元素為止。

3 仿真驗(yàn)證與結(jié)果分析

按照PSO選星步驟，設(shè)定算法參數(shù)：迭代次數(shù)MaxIt=50，種群大小M=100，慣性權(quán)重ω=0.729 8，加速常數(shù)c1=c2=1.496 2，vmax=2。選取某一時(shí)刻進(jìn)行GDOP值的計(jì)算，隨著迭代次數(shù)的增加GDOP值的變化如圖3所示。

圖2 北斗/GPS可見衛(wèi)星數(shù)及對應(yīng)的GDOP最小值Fig.2 Number of BDS/GPS visible satellite and their minimum GDOP

通過遍歷法得出該時(shí)刻的GDOP最小值為2.25。圖3中的結(jié)果顯示，PSO算法的收斂速度很快，迭代次數(shù)在小于15次時(shí)就穩(wěn)定在2.34附近，且在后續(xù)迭代過程中保持不變。很明顯，PSO算法出現(xiàn)“早熟”現(xiàn)象，即陷入局部最優(yōu)解。

采用CPSO算法對同一時(shí)刻進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如圖4所示。

從圖4中可以看出，CPSO算法同樣在迭代次數(shù)低于15次時(shí)收斂，并有效改善了PSO選星算法易陷入局部最優(yōu)的缺點(diǎn)。在迭代次數(shù)為50次時(shí)，耗時(shí)約為1.5 s左右，如果按需求適當(dāng)減少迭代次數(shù)，選星耗時(shí)也會有所減少。

遍歷法、PSO和CPSO選星算法在相同歷元的選星耗時(shí)及其對應(yīng)的選星結(jié)果(最后一列數(shù)字代表衛(wèi)星號)如表1所示。

從表1中數(shù)據(jù)得知，基于PSO和CPSO的選星算法在單次選星所用時(shí)間約為遍歷法選星的37.5%，但選星結(jié)果仍有偏差。為了充分驗(yàn)證算法性能，下面將給出仿真時(shí)長為3 h的PSO和CPSO選星GDOP計(jì)算誤差，其誤差定義為新算法所得到的GDOP值與遍歷法選星所得到GDOP值的差值，結(jié)果如圖5所示。

圖3 PSO選星時(shí)GDOP值隨迭代次數(shù)的變化Fig.3 Change of GDOP with iteration numbers of PSO satellite selection

圖4 CPSO選星時(shí)GDOP值隨迭代次數(shù)的變化Fig.4 Change of GDOP with iteration numbers of CPSO satellite selection

從圖5中可知，PSO和CPSO選星算法的GDOP計(jì)算誤差均小于等于0.6。對所得數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，CPSO選星的GDOP計(jì)算誤差平均值為0.260 9，方差為0.042 4；PSO選星的GDOP計(jì)算誤差平均值為0.263 2，方差為0.043 0。

表1 三種選星算法性能對比Table 1 Performance comparison of three satellite selection algorithms

圖5 PSO和CPSO選星的結(jié)果誤差Fig.5 Result error of satellite selection by PSO and CPSO

4 結(jié) 論

本文提出了一種基于CPSO的北斗/GPS組合導(dǎo)航選星算法，利用CPSO算法的快速尋優(yōu)能力，減少GDOP的計(jì)算次數(shù)，從而實(shí)現(xiàn)了北斗/GPS組合導(dǎo)航快速選星，通過對算法進(jìn)行仿真驗(yàn)證，得到以下結(jié)果：

1) 在北斗/GPS組合導(dǎo)航下，選星顆數(shù)為6時(shí)，算法能夠?qū)崿F(xiàn)快速選星。該算法的單次選星時(shí)間約為1.5 s，約為遍歷法選星的37.5%。

2) 利用混沌方程初始化種群粒子能夠提高選星結(jié)果的準(zhǔn)確性。

3) PSO和CPSO選星算法的GDOP計(jì)算誤差均小于等于0.6，二者的平均計(jì)算誤差約為0.26。

本文將CPSO算法應(yīng)用于組合衛(wèi)星導(dǎo)航選星過程中，為多星座組合導(dǎo)航快速選星問題提供了新的解決方法。