改進(jìn)粒子群優(yōu)化的衛(wèi)星導(dǎo)航選星算法

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

（1.沈陽(yáng)航空航天大學(xué) 電子信息工程學(xué)院，沈陽(yáng)110136；2.沈陽(yáng)航空航天大學(xué) 遼寧省通用航空重點(diǎn)實(shí)驗(yàn)室，沈陽(yáng)110136）

全球?qū)Ш叫l(wèi)星系統(tǒng)（Global Navigation Satellite Systems，GNSS）不斷發(fā)展和日益完善［1］，可用于導(dǎo)航的衛(wèi)星增多，為了獲得更優(yōu)的幾何結(jié)構(gòu)和更多的導(dǎo)航信號(hào)，多星座組合導(dǎo)航成為導(dǎo)航技術(shù)發(fā)展趨勢(shì)［2］。然而，如果利用全部可見(jiàn)衛(wèi)星進(jìn)行定位，不僅增加接收機(jī)信號(hào)處理負(fù)擔(dān)，更為重要的是，當(dāng)可見(jiàn)衛(wèi)星達(dá)到一定數(shù)量時(shí)，幾何精度因子（Geometric Dilution of Precision，GDOP）將不會(huì)有明顯的改善。因此，研究選星算法，在保證定位精度的前提下，從全部可見(jiàn)衛(wèi)星中選取較優(yōu)的一組用于定位是必要的。

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

本文基于人工魚(yú)群算法的粒子群優(yōu)化（Artificial Fish Swarm Algorithm-Particle Swarm Optimization，AFSA-PSO）算法引入到選星過(guò)程中，并將得到的結(jié)果與標(biāo)準(zhǔn)的PSO選星算法結(jié)果對(duì)比，驗(yàn)證了AFSA-PSO選星算法的性能。

1 AFSA-PSO算法

AFSA-PSO算法包含標(biāo)準(zhǔn)的PSO算法和AFSA算法的聚群和追尾行為。標(biāo)準(zhǔn)的PSO算法是模仿鳥(niǎo)類(lèi)覓食行為的一種智能尋優(yōu)算法［12］，該算法將每個(gè)個(gè)體看作是空間中一個(gè)沒(méi)有質(zhì)量和體積的粒子，每個(gè)粒子在搜索空間以一定的移動(dòng)速度改變自身位置，根據(jù)自身和集體的尋優(yōu)經(jīng)驗(yàn)動(dòng)態(tài)調(diào)節(jié)自身的移動(dòng)速度。

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

式中：t為當(dāng)前的迭代次數(shù)；ω為慣性權(quán)因子；c1和c2為正的加速常數(shù)；r1和r2為0～1之間均勻分布的隨機(jī)數(shù)；M為種群規(guī)模。

AFSA算法是一種模擬魚(yú)群覓食行為的全局尋優(yōu)智能算法［13］，相對(duì)于PSO算法，AFSA算法全局收斂速度較慢，且尋優(yōu)過(guò)程較為復(fù)雜。在A(yíng)FSA-PSO算法中，粒子經(jīng)過(guò)PSO算法更新后，在A(yíng)FSA的聚群和追尾行為之間做出判斷，基于選擇的行為更新自身位置。以求最小值為例，若中心位置的適應(yīng)度值小于視野范圍內(nèi)最小適應(yīng)度值，則粒子執(zhí)行聚群行為，反之，執(zhí)行追尾行為。

1.1 AFSA聚群行為

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

1.2 AFSA追尾行為

經(jīng)過(guò)PSO算法更新后，粒子的位置和適應(yīng)度值為xk（t+1）和yk（t+1），粒子搜索當(dāng)前視野范圍內(nèi)粒子的數(shù)目Nf及視野內(nèi)粒子適應(yīng)度值yb最優(yōu)的粒子的位置xb，若滿(mǎn)足式（6），則表明xi所處的位置并不擁擠且適應(yīng)度值最優(yōu)，那么粒子則按照式（7）向xi位置移動(dòng)。

2 基于A(yíng)FSA-PSO的選星算法

設(shè)某歷元時(shí)刻可見(jiàn)衛(wèi)星數(shù)為n，選擇m顆衛(wèi)星，使構(gòu)成的衛(wèi)星組合的GDOP值最小。在A(yíng)FSA-PSO選星算法中，每組衛(wèi)星組合代表一個(gè)粒子，GDOP為適應(yīng)度函數(shù)。具體的選星步驟如下：

步驟1獲取可見(jiàn)衛(wèi)星。根據(jù)導(dǎo)航電文，獲取當(dāng)前時(shí)刻仰角大于遮蔽角的衛(wèi)星（本文中選取5°），得到可見(jiàn)衛(wèi)星。

步驟2編碼。將步驟1獲取的可見(jiàn)衛(wèi)星隨機(jī)排列，對(duì)其從1，2，…，n依次編碼，編碼與衛(wèi)星號(hào)一一對(duì)應(yīng)。

步驟3生成初始種群。從n顆可見(jiàn)星中選取m顆，共有種衛(wèi)星組合，每種組合代表一個(gè)粒子。設(shè)在A(yíng)FSA-PSO選星算法中，種群大小為M，從所有可見(jiàn)星組合中隨機(jī)搜索M 個(gè)組合，得到初始種群，初始種群中粒子k的位置表示為：xk=［x01，x02，…，x0m］，m為選擇的衛(wèi)星數(shù)。初始化粒子的速度為vk=［v01，v02，…，v0m］，下標(biāo)“0”為粒子k的初始迭代次數(shù)。

步驟4適應(yīng)度值計(jì)算。將初始種群中的每個(gè)粒子代入到適應(yīng)度函數(shù)中，計(jì)算每個(gè)粒子的適應(yīng)度值，將適應(yīng)度值最小的粒子位置設(shè)為初始全局最優(yōu)位置gbest，每個(gè)粒子本身的位置設(shè)置為初始個(gè)體最優(yōu)位置pbestk。

步驟5更新。通過(guò)判斷每個(gè)粒子的個(gè)體最優(yōu)值，確定每次迭代過(guò)程中每個(gè)粒子經(jīng)過(guò)的個(gè)體最優(yōu)位置pbestk和群體中的全局最優(yōu)位置gbest?；谑剑?）～式（7）更新粒子的位置和速度，計(jì)算粒子的適應(yīng)度值，直到滿(mǎn)足條件，得到最佳衛(wèi)星組合和適應(yīng)度值。

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

參數(shù)的選取影響算法的性能，本文中基于Shi和Eberhart的經(jīng)驗(yàn)進(jìn)行多次仿真實(shí)驗(yàn)［15］，選取標(biāo)準(zhǔn)PSO算法的參數(shù)值為：種群規(guī)模M=100，最大迭代次數(shù)Mt=50，加速常數(shù)c1=c2=1.4962，粒子最大移動(dòng)速度vmax=2，最小移動(dòng)速度vmin=-2，慣性權(quán)因子引入自適應(yīng)值，其表示為

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

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

3.1 視野對(duì)算法性能影響

在A(yíng)FSA-PSO選星算法中，通過(guò)多次仿真選取合適的視野值，終止迭代次數(shù)設(shè)為50，移動(dòng)步長(zhǎng)設(shè)為10，擁擠度因子設(shè)為0.4，得到的GDOP誤差及選星耗時(shí)如表1所示。

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

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

3.2 移動(dòng)步長(zhǎng)對(duì)算法性能影響

在A(yíng)FSA-PSO選星算法中，設(shè)置終止迭代次數(shù)為50，視野值為10，擁擠度因子為0.4，其GDOP誤差及選星耗時(shí)如表2所示。

表2 移動(dòng)步長(zhǎng)對(duì)算法性能的影響Table 2 Effect of step length on algorithm perform ance

表2結(jié)果表明，當(dāng)移動(dòng)步長(zhǎng)為6～10時(shí)，隨著移動(dòng)步長(zhǎng)的增加，AFSA-PSO平均選星耗時(shí)減少，GDOP平均誤差也隨之減小；當(dāng)移動(dòng)步長(zhǎng)超過(guò)10時(shí)，隨著移動(dòng)步長(zhǎng)的增加，AFSA-PSO平均選星耗時(shí)增加，GDOP誤差也逐漸增大。

3.3 擁擠度因子對(duì)算法性能影響

在A(yíng)FSA-PSO選星算法中，設(shè)置終止迭代次數(shù)為50，視野值為10，移動(dòng)步長(zhǎng)為8，其GDOP誤差值及選星耗時(shí)如表3所示。

表3結(jié)果表明，當(dāng)δ=0.2和δ=1時(shí)，AFSAPSO算法平均耗時(shí)增加；因此，為實(shí)現(xiàn)快速選星，擁擠度因子可在0.4～0.8之間取值。

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

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

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

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

本文根據(jù)AFSA-PSO選星算法步驟進(jìn)行單次選星，選取參數(shù)擁擠度因子δ=0.4，視野值V=10，移動(dòng)步長(zhǎng)s=10。圖2給出了相同時(shí)刻PSO算法和AFSA-PSO算法GDOP誤差的變化曲線(xiàn)。結(jié)果表明，標(biāo)準(zhǔn)PSO算法的收斂速度很快，但在迭代次數(shù)為11時(shí)，GDOP誤差就穩(wěn)定在0.1758，然而，標(biāo)準(zhǔn)PSO算法容易陷入局部最優(yōu)；而AFSA-PSO算法在迭代次數(shù)為21時(shí)，GDOP誤差就趨于0。因此，AFSA-PSO算法克服了標(biāo)準(zhǔn)PSO算法“早熟”的問(wèn)題。

選星顆數(shù)為6和8時(shí)，3 h內(nèi)標(biāo)準(zhǔn)PSO算法和AFSA-PSO算法的GDOP誤差結(jié)果如圖3所示。

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

在3 h內(nèi)對(duì)比相同選星顆數(shù)下的2種選星算法，圖3（a）、（b）表明，當(dāng)選星顆數(shù)為6時(shí)，AFSA-PSO算法有67%的GDOP誤差趨近于0；對(duì)比PSO算法，AFSA-PSO算法的GDOP誤差更小更穩(wěn)定；對(duì)比圖3（c）、（d），當(dāng)選星顆數(shù)為8時(shí)，AFSA-PSO算法有92%的GDOP誤差趨近于0，PSO算法GDOP誤差分布在0.1～0.4之間，因此。AFSA-PSO 選星算法在精度上優(yōu)于 PSO算法。

圖1 可見(jiàn)衛(wèi)星數(shù)及對(duì)應(yīng)的最小GDOP值Fig.1 Visible number of satellites and corresponding min-GDOP

圖2 單次選星GDOP誤差變化Fig.2 GDOP error change of single satellite selection

圖3 AFSA-PSO算法與PSO算法的GDOP誤差Fig.3 GDOP error in AFSA-PSO and PSO algorithms

表4對(duì)比了不同選星算法單次選星耗時(shí)，給出了選星顆數(shù)為6時(shí)的耗時(shí)結(jié)果。從中可知，AFSA-PSO選星算法單次選星耗時(shí)優(yōu)于遍歷算法。

表4 不同選星算法單次選星耗時(shí)Tab le 4 Single satellite selection tim e of different satellie selection algorithm s

5 結(jié) 論

本文研究了一種改進(jìn)粒子群優(yōu)化衛(wèi)星導(dǎo)航選星算法，將AFSA-PSO算法引入到選星過(guò)程中，減少GDOP的計(jì)算次數(shù)，通過(guò)對(duì)算法進(jìn)行仿真驗(yàn)證和分析，得到以下結(jié)果：

1）AFSA引入到PSO算法中，克服了PSO算法陷入局部最優(yōu)的不足。

2）在組合導(dǎo)航下，選星顆數(shù)相同時(shí)，AFSAPSO選星結(jié)果的準(zhǔn)確性?xún)?yōu)于PSO選星算法。

3）隨著選星顆數(shù)的增加，AFSA-PSO選星算法的GDOP誤差減小。

4）與遍歷法相比，當(dāng)選星顆數(shù)為6時(shí)，AFSAPSO選星效率得到改善。