改進粒子群優化的衛星導航選星算法

2021-02-05 02:10:48王爾申孫彩苗黃煜峰李軒別玉霞曲萍萍

北京航空航天大學學報 2021年1期

王爾申，孫彩苗，黃煜峰，李軒，別玉霞，曲萍萍

（1.沈陽航空航天大學電子信息工程學院，沈陽110136；2.沈陽航空航天大學遼寧省通用航空重點實驗室，沈陽110136）

全球導航衛星系統（Global Navigation Satellite Systems，GNSS）不斷發展和日益完善［1］，可用于導航的衛星增多，為了獲得更優的幾何結構和更多的導航信號，多星座組合導航成為導航技術發展趨勢［2］。然而，如果利用全部可見衛星進行定位，不僅增加接收機信號處理負擔，更為重要的是，當可見衛星達到一定數量時，幾何精度因子（Geometric Dilution of Precision，GDOP）將不會有明顯的改善。因此，研究選星算法，在保證定位精度的前提下，從全部可見衛星中選取較優的一組用于定位是必要的。

大部分的選星算法主要是基于衡量定位精度的GDOP，GDOP與用戶的幾何結構有關，GDOP越小，定位精度越高。基于GDOP的選星算法主要有Bo和Shao［3］研究的加權幾何精度（WGDOP）法、Phatak［4］研究的矩陣求逆引理法；也有學者研究了基于遺傳算法通過模擬生物進化的方式實現選星［5］。這些算法都在不同程度上減少了選星的計算量。有學者提出一種顧及觀測質量的三維凸包選星思路［6］；Liu等［7］提出了一種基于模糊度精度因子（Ambiguity Dilution of Precision，ADOP）的快速衛星選擇策略，在一定程度上減輕了接收機的計算負擔；也有學者提出一種基于3星子集的GPS快速選星算法，可以有效降低星座突變時由星座選擇帶來的時間消耗［8］。類似遺傳算法，粒子群優化（Particle Swarm Optimization，PSO）算法是一種智能尋優算法［9］，但是該算法在尋優過程中容易陷入局部最優導致尋優結果不準確［10］，為克服這一問題，利用人工魚群算法（Artificial Fish Swarm Algorithm，AFSA）的全局收斂特性，與PSO算法結合，提高PSO算法的全局收斂能力［11］。

本文基于人工魚群算法的粒子群優化（Artificial Fish Swarm Algorithm-Particle Swarm Optimization，AFSA-PSO）算法引入到選星過程中，并將得到的結果與標準的PSO選星算法結果對比，驗證了AFSA-PSO選星算法的性能。

1 AFSA-PSO算法

AFSA-PSO算法包含標準的PSO算法和AFSA算法的聚群和追尾行為。標準的PSO算法是模仿鳥類覓食行為的一種智能尋優算法［12］，該算法將每個個體看作是空間中一個沒有質量和體積的粒子，每個粒子在搜索空間以一定的移動速度改變自身位置，根據自身和集體的尋優經驗動態調節自身的移動速度。

每個粒子為d-維空間中的一個點，第k個粒子的位置可以表示為xk=［xk1，xk2，…，xkd］，xk1，xk2，…，xkd分別表示第k個粒子在d-維空間中的位置分量；第k個粒子位置的變化速度可以表示為vk=［vk1，vk2，…，vkd］，vk1，vk2，…，vkd分別表示第k個粒子在d-維空間中的速度分量。每個粒子在運動過程中，都會根據自身經驗判斷出個體最優位置pbestk，并且在種群中產生全局最優位置gbest。每個粒子通過比較“兩個最優”，不斷改善自身位置以趨近全局最優。粒子的速度和位置更新如下：

式中：t為當前的迭代次數；ω為慣性權因子；c1和c2為正的加速常數；r1和r2為0～1之間均勻分布的隨機數；M為種群規模。

AFSA算法是一種模擬魚群覓食行為的全局尋優智能算法［13］，相對于PSO算法，AFSA算法全局收斂速度較慢，且尋優過程較為復雜。在AFSA-PSO算法中，粒子經過PSO算法更新后，在AFSA的聚群和追尾行為之間做出判斷，基于選擇的行為更新自身位置。以求最小值為例，若中心位置的適應度值小于視野范圍內最小適應度值，則粒子執行聚群行為，反之，執行追尾行為。

1.1 AFSA聚群行為

經過PSO算法更新后，第k個粒子的位置和適應度值為xk（t+1）和yk（t+1），每個粒子搜索當前視野范圍內的粒子數目Nf及粒子中心位置xc，若滿足式（3），則表示中心位置粒子的適應度值更優且粒子不太擁擠，則粒子向中心位置移動［14］。粒子中心位置及向中心位置移動的計算如下：式中：yc為中心位置粒子的適應度值；xi為視野范圍內各粒子的位置；δ為擁擠度因子；s為粒子位置的移動步長；r為0～1之間的隨機數。

1.2 AFSA追尾行為

經過PSO算法更新后，粒子的位置和適應度值為xk（t+1）和yk（t+1），粒子搜索當前視野范圍內粒子的數目Nf及視野內粒子適應度值yb最優的粒子的位置xb，若滿足式（6），則表明xi所處的位置并不擁擠且適應度值最優，那么粒子則按照式（7）向xi位置移動。

2 基于AFSA-PSO的選星算法

設某歷元時刻可見衛星數為n，選擇m顆衛星，使構成的衛星組合的GDOP值最小。在AFSA-PSO選星算法中，每組衛星組合代表一個粒子，GDOP為適應度函數。具體的選星步驟如下：

步驟1獲取可見衛星。根據導航電文，獲取當前時刻仰角大于遮蔽角的衛星（本文中選取5°），得到可見衛星。

步驟2編碼。將步驟1獲取的可見衛星隨機排列，對其從1，2，…，n依次編碼，編碼與衛星號一一對應。

步驟3生成初始種群。從n顆可見星中選取m顆，共有種衛星組合，每種組合代表一個粒子。設在AFSA-PSO選星算法中，種群大小為M，從所有可見星組合中隨機搜索M 個組合，得到初始種群，初始種群中粒子k的位置表示為：xk=［x01，x02，…，x0m］，m為選擇的衛星數。初始化粒子的速度為vk=［v01，v02，…，v0m］，下標“0”為粒子k的初始迭代次數。

步驟4適應度值計算。將初始種群中的每個粒子代入到適應度函數中，計算每個粒子的適應度值，將適應度值最小的粒子位置設為初始全局最優位置gbest，每個粒子本身的位置設置為初始個體最優位置pbestk。

步驟5更新。通過判斷每個粒子的個體最優值，確定每次迭代過程中每個粒子經過的個體最優位置pbestk和群體中的全局最優位置gbest。基于式（1）～式（7）更新粒子的位置和速度，計算粒子的適應度值，直到滿足條件，得到最佳衛星組合和適應度值。

3 AFSA-PSO選星算法性能分析

參數的選取影響算法的性能，本文中基于Shi和Eberhart的經驗進行多次仿真實驗［15］，選取標準PSO算法的參數值為：種群規模M=100，最大迭代次數Mt=50，加速常數c1=c2=1.4962，粒子最大移動速度vmax=2，最小移動速度vmin=-2，慣性權因子引入自適應值，其表示為

式中：ωmax=0.9和ωmin=0.4分別為最大和最小慣性權因子；Mt為最大迭代次數。

AFSA-PSO選星算法主要包括以下參數：人工魚視野V、移動步長s、擁擠度因子δ。本文中將遍歷法［16］選星得到的GDOP值作為參考，計算同一時刻、同一參數取不同值時的GDOP誤差。

3.1 視野對算法性能影響

在AFSA-PSO選星算法中，通過多次仿真選取合適的視野值，終止迭代次數設為50，移動步長設為10，擁擠度因子設為0.4，得到的GDOP誤差及選星耗時如表1所示。

表1結果表明，視野值越大，平均選星的耗時越長，GDOP誤差值越小，但是算法整體的GDOP平均誤差在0～0.07之間，表明視野對AFSA-PSO選星算法的精度影響不大。

表1 視野對算法性能的影響Table 1 Effect of visual field on algorithm perform ance

3.2 移動步長對算法性能影響

在AFSA-PSO選星算法中，設置終止迭代次數為50，視野值為10，擁擠度因子為0.4，其GDOP誤差及選星耗時如表2所示。

表2 移動步長對算法性能的影響Table 2 Effect of step length on algorithm perform ance

表2結果表明，當移動步長為6～10時，隨著移動步長的增加，AFSA-PSO平均選星耗時減少，GDOP平均誤差也隨之減小；當移動步長超過10時，隨著移動步長的增加，AFSA-PSO平均選星耗時增加，GDOP誤差也逐漸增大。

3.3 擁擠度因子對算法性能影響

在AFSA-PSO選星算法中，設置終止迭代次數為50，視野值為10，移動步長為8，其GDOP誤差值及選星耗時如表3所示。

表3結果表明，當δ=0.2和δ=1時，AFSAPSO算法平均耗時增加；因此，為實現快速選星，擁擠度因子可在0.4～0.8之間取值。

表3 擁擠度因子對算法性能的影響Tab le 3 E ffect of crow ding factor on algorithm perform ance

4 仿真驗證與結果分析

為了驗證本文算法的性能，實驗計算機采用CPU處理器（i5-4570，3.20GHz）、RAM 4GB，通過實際的導航數據進行仿真實驗，導航電文和觀測文件來自于IGS（International GNSS Service，IGS）網站，北斗/GPS接收機坐標為［-2 279 827.315 6，5004704.3094，3219776.2093］m，選星顆數為6。衛星位置由導航星歷計算，衛星的截止高度角設為5°，仿真時長為3 h，仿真步長為1min。圖1給出了3 h內北斗/GPS雙星座下可見衛星數及最小GDOP值。

圖1表明，3 h內北斗/GPS雙星座下可見衛星數目約為18顆，設需從全部可見衛星中選取6顆，按照遍歷法選星，需要進行C=18 564次GDOP值的計算，選星耗時約為4.5 s，最小GDOP值為2.251 028。

本文根據AFSA-PSO選星算法步驟進行單次選星，選取參數擁擠度因子δ=0.4，視野值V=10，移動步長s=10。圖2給出了相同時刻PSO算法和AFSA-PSO算法GDOP誤差的變化曲線。結果表明，標準PSO算法的收斂速度很快，但在迭代次數為11時，GDOP誤差就穩定在0.1758，然而，標準PSO算法容易陷入局部最優；而AFSA-PSO算法在迭代次數為21時，GDOP誤差就趨于0。因此，AFSA-PSO算法克服了標準PSO算法“早熟”的問題。

選星顆數為6和8時，3 h內標準PSO算法和AFSA-PSO算法的GDOP誤差結果如圖3所示。

根據圖3，在3 h內對比不同選星顆數下2種選星算法的GDOP誤差，選星顆數為8時的GDOP誤差小于選星顆數為6時的誤差，表明隨著選星顆數的增加，2種選星算法的精度都有所提高。

在3 h內對比相同選星顆數下的2種選星算法，圖3（a）、（b）表明，當選星顆數為6時，AFSA-PSO算法有67%的GDOP誤差趨近于0；對比PSO算法，AFSA-PSO算法的GDOP誤差更小更穩定；對比圖3（c）、（d），當選星顆數為8時，AFSA-PSO算法有92%的GDOP誤差趨近于0，PSO算法GDOP誤差分布在0.1～0.4之間，因此。AFSA-PSO 選星算法在精度上優于 PSO算法。