基于混沌粒子群優化的北斗/GPS組合導航選星算法

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

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

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

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

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

1 混沌粒子群優化模型

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

PSO算法是Eberhart和Kennedy通過模仿鳥類的覓食行為而產生的[13]，搜索空間的個體通過比較自身所經過的最優位置和種群中其他粒子最優位置，不斷調整自身速度，使其向最優解靠攏。個體被稱為“粒子”，每個粒子為d維空間的一個點，第i個粒子可以表示為xi=[xi1,xi2,…,xid]，粒子在運動過程中，會根據自身經驗產生個體極值pbest=[pi1,pi2,…,pid]，同時在種群中會產生全局極值gbest，粒子通過2個“極值”不斷調整自身位置，位置更新如式(1)所示，使其不斷趨近全局最優值。第i個粒子的位置變化速度被表示為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為當前迭代次數；N為種群中粒子的總數；ω為慣性權重；c1和c2為加速常數，分別調節向pbest和gbest方向的運動速度；r1和r2為0～1之間均勻分布的隨機數。另外，通過設置微粒的速度范圍[vmin,vmax]和位置范圍[xmin,xmax]，可以對粒子運動的步長進行適當的限定。

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

PSO算法的結果容易陷入局部最優，為此引入混沌理論，提高結果的有效性。混沌搜索，即對于給定的優化函數，將變量從混沌空間映射到解空間，然后利用混沌變量進行搜索[15]，可避免搜索結果陷入“局部最優”。

Logistic映射是較為常見的混沌序列產生方法，其表達式為

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

(3)

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

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

2 北斗/GPS組合導航選星算法

2.1 混沌粒子群優化適應度函數

適應度函數又稱為目標函數，是用來評價粒子優劣的重要衡量標準，適應度函數的選取直接影響算法結果的有效性。本文采用的適應度函數是各可見衛星組合的GDOP值，用于評價所選衛星組合的空間幾何結構性能。

選星算法主要以用戶與可見衛星組合的空間幾何分布為衡量標準。針對用戶與可見衛星組合的空間幾何分布特性的表征，DOP是應用最廣泛的參數，按照DOP進行選星可以保證定位精度[1]。衛星導航定位系統的DOP可用GDOP與用戶等效測距誤差(User Equivalent Range Error，UERE)的乘積來表示，即

σp=GDOP·σUERE

(4)

式中：σp為導航定位位置/時間解的精度；σUERE為偽距測量值的標準差；GDOP與用戶到衛星的幾何結構有關。從式(4)可知，當σUERE確定時，GDOP越小，定位精度越高。

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

(5)

式中：trace(·)表示矩陣的跡；H為觀測矩陣。假設北斗/GPS組合導航接收機能接收到m顆GPS衛星、k顆北斗衛星，即可產生m+k個觀測量，構成的觀測矩陣為

(6)

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

2.2 混沌粒子群優化選星算法設計

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

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

步驟1可見衛星提取。根據導航電文，提取當前時刻仰角大于遮蔽角的衛星(本文中的遮蔽角取值為5°)，得到該時刻的可見衛星總數。

步驟2編碼。對當前時刻接收機觀測到的所有可見衛星進行隨機排列，然后將可見衛星從1,2,…,n依次連續編碼，編碼與可見衛星一一對應。

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

步驟5更新。對于每個粒子，根據式(1)和式(2)不斷修正種群中粒子的位置xti和速度vti，分別計算新位置對應的目標值fti，并更新粒子所經過的最優位置pbest和種群最優位置gbest。直到達到最大迭代次數，終止迭代。

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

在算法流程中，粒子更新時需注意2個關鍵點：①可見衛星編號為整數，因此更新過程中必須

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

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

3 仿真驗證與結果分析

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

圖2 北斗/GPS可見衛星數及對應的GDOP最小值Fig.2 Number of BDS/GPS visible satellite and their minimum GDOP

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

采用CPSO算法對同一時刻進行仿真實驗，結果如圖4所示。

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

遍歷法、PSO和CPSO選星算法在相同歷元的選星耗時及其對應的選星結果(最后一列數字代表衛星號)如表1所示。

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

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

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

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

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

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

4 結 論

本文提出了一種基于CPSO的北斗/GPS組合導航選星算法，利用CPSO算法的快速尋優能力，減少GDOP的計算次數，從而實現了北斗/GPS組合導航快速選星，通過對算法進行仿真驗證，得到以下結果：

1) 在北斗/GPS組合導航下，選星顆數為6時，算法能夠實現快速選星。該算法的單次選星時間約為1.5 s，約為遍歷法選星的37.5%。

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

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

本文將CPSO算法應用于組合衛星導航選星過程中，為多星座組合導航快速選星問題提供了新的解決方法。