李東新，彭 云，常 青，李 晶，于 淵

(1.北京航空航天大學(xué) 電子信息工程學(xué)院，北京100191；2.北京航天長征飛行器研究所，北京100076；3.交通信息通信技術(shù)研究發(fā)展中心，北京100011)

?

基于粒子群算法的偽衛(wèi)星布站優(yōu)化設(shè)計

李東新1，3，彭 云2，常 青1，李 晶3，于 淵3

(1.北京航空航天大學(xué) 電子信息工程學(xué)院，北京100191；2.北京航天長征飛行器研究所，北京100076；3.交通信息通信技術(shù)研究發(fā)展中心，北京100011)

針對偽衛(wèi)星布站問題，采用粒子群智能優(yōu)化算法，以導(dǎo)航定位中精度因子作為粒子群適應(yīng)度函數(shù)，采用線性遞減慣性權(quán)值策略，通過適當(dāng)次數(shù)的進化與迭代，最終尋找到最優(yōu)化的偽衛(wèi)星布站設(shè)計方案。通過對兩條豎直平面內(nèi)的拋物線軌跡進行仿真驗證，結(jié)果表明，基于粒子群算法的偽衛(wèi)星布站優(yōu)化設(shè)計方案可以減小全程精度因子，提高了偽衛(wèi)星獨立定位系統(tǒng)的定位精度。

粒子群算法；線性遞減慣性權(quán)值策略；偽衛(wèi)星布站

0 引言

衛(wèi)星導(dǎo)航定位的基本作用是向各類用戶和運動平臺實時提供準(zhǔn)確、連續(xù)、可靠的位置、速度和時間信息。當(dāng)前各種全球?qū)Ш叫l(wèi)星系統(tǒng)，其系統(tǒng)的精度、可靠性和可用性都在一定程度上依賴于可跟蹤衛(wèi)星的數(shù)量以及幾何分布情況。由于受到以上因素的制約，在峽谷、室內(nèi)以及地下等比較苛刻的觀測環(huán)境下，可視衛(wèi)星的數(shù)量和幾何布局就不能滿足定位的需求。同時，由于用戶與導(dǎo)航衛(wèi)星之間的距離一般都比較遠(yuǎn)，信號衰減較大，導(dǎo)航信號到達地面時都比較弱，在復(fù)雜電磁環(huán)境下，極易受到干擾而無法使用。位于地面的偽衛(wèi)星系統(tǒng)就能夠更好解決這個問題。國內(nèi)外學(xué)者在這一領(lǐng)域進行了深入的研究，相關(guān)的研究成果已經(jīng)初步應(yīng)用于露天礦邊坡變形監(jiān)測、壩體變形監(jiān)測以及建筑物變形監(jiān)測等領(lǐng)域，并產(chǎn)生了良好的效益[1-4]。

偽衛(wèi)星不僅可以輔助GNSS導(dǎo)航定位，而且因為其自身功能和原理與導(dǎo)航衛(wèi)星類似，且具有設(shè)置靈活機動，抗干擾性能好等優(yōu)點，所以在特定環(huán)境，可以完全替代導(dǎo)航衛(wèi)星，進行獨立定位。偽衛(wèi)星系統(tǒng)中，偽衛(wèi)星的幾何分布情況對用戶導(dǎo)航定位精度具有重要影響，偽衛(wèi)星布站技術(shù)是偽衛(wèi)星系統(tǒng)設(shè)計的關(guān)鍵技術(shù)之一，在偽距測量誤差一定的情況下，偽衛(wèi)星良好的幾何位置分布可以大大減小導(dǎo)航定位誤差，提高定位精度。

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是Kennedy和Eberhart[5]于1995年提出的一種全局優(yōu)化進化算法，其思想來源于對鳥群捕食行為的研究，同遺傳算法和蟻群算法相比，PSO有著算法簡單、容易實現(xiàn)，并且可調(diào)整參數(shù)少等特點，因此被廣泛應(yīng)用于結(jié)構(gòu)設(shè)計[6]、電磁場[7]和任務(wù)調(diào)度[8]等工程優(yōu)化問題中。

在本文中，我們采用粒子群優(yōu)化算法對偽衛(wèi)星獨立定位系統(tǒng)中偽衛(wèi)星的幾何位置進行優(yōu)化，并用兩條豎直平面內(nèi)的拋物線軌跡進行導(dǎo)航定位幾何精度因子仿真試驗，仿真結(jié)果表明，采用基于改進的粒子群布站優(yōu)化算法能夠大大減小導(dǎo)航定位精度因子，提高了定位精度。

1 偽衛(wèi)星定位原理

偽衛(wèi)星定位原理同衛(wèi)星導(dǎo)航原理類似，利用到達時間測距原理來確定用戶的位置。偽衛(wèi)星定位原理如圖1所示。

圖1 偽衛(wèi)星定位原理圖Fig.1 Principle of pseudo-satellite positioning

接收機測量偽衛(wèi)星發(fā)射信號與接收機接收到信號之間的時間差Δt，乘以光速c便可求得距離ρ(ρ=cgΔt)。由于偽衛(wèi)星系統(tǒng)時鐘和接收機時鐘并不完全同步，存在時鐘偏移誤差，設(shè)這個誤差為δtu。一般偽衛(wèi)星布設(shè)在地面或?qū)α鲗右詢?nèi)，電磁波必然要通過對流層，由于對流層引起測量誤差設(shè)為T，則用戶相對于偽衛(wèi)星i的觀測方程為

ρi=ri+c·(δtu-δti)+Ti+εi

(1)

ρi-Ti+cgδti-εi=

(2)

其中含有4個未知量，通過接收到至少4顆偽衛(wèi)星信號聯(lián)立求解，就可以單獨實現(xiàn)導(dǎo)航定位。

2 精度因子DOP

雖然偽衛(wèi)星定位原理和GNSS導(dǎo)航定位原理相似，但由于偽衛(wèi)星布站區(qū)域僅限于對流層到地平面區(qū)域，大多數(shù)偽衛(wèi)星平臺都直接安裝在地面，組成地基偽衛(wèi)星網(wǎng)，偽衛(wèi)星布局受限，從而造成偽衛(wèi)星獨立定位系統(tǒng)中定位精度很差，嚴(yán)重影響偽衛(wèi)星系統(tǒng)的可用性和性能。

在衛(wèi)星導(dǎo)航定位系統(tǒng)中，有很多方法可以評定偽衛(wèi)星的幾何分布結(jié)構(gòu)對定位精度的影響，精度因子(DilutionofPosition，DOP)由于計算較為簡單并且表達直觀，成為其中較為常用的一種衡量尺度。在同等用戶等效距離誤差的條件下，DOP值越小，往往代表星座分布結(jié)構(gòu)越好，定位精度越高。通過對已知衛(wèi)星幾何分布下空間內(nèi)各點的DOP的仿真計算，可以得到對相應(yīng)分布結(jié)構(gòu)的評價結(jié)果，以此作為設(shè)計、選擇偽衛(wèi)星組網(wǎng)方式好壞的判斷依據(jù)。

設(shè)用戶接收機的位置為(xu，yu，zu)，第i顆偽衛(wèi)星的位置為(xi，yi，zi)(i=0，1，…，n，n為偽衛(wèi)星數(shù)目)。由偽衛(wèi)星的幾何分布可以首先得到觀測矩陣如下[9]

(3)

其中，(axi，ayi，azi)為從用戶接收機(即需要計算DOP的位置)指向第i顆衛(wèi)星的單位矢量。單位矢量的計算式如下

(4)

得到觀測矩陣G后，可以由此得到權(quán)系數(shù)矩陣H如下

(5)

而相應(yīng)的各種DOP值都可以根據(jù)權(quán)系數(shù)矩陣H計算得到。

常用精度因子有幾何精度因子(GDOP)、位置精度因子(PDOP)、水平精度因子(HDOP)、垂直精度因子(VDOP)和時間精度因子(TDOP)。幾何精度因子GDOP反應(yīng)了空間位置誤差和時鐘誤差的綜合影響；空間位置精度因子PDOP反應(yīng)了空間位置誤差的影響；水平位置精度因子HDOP反應(yīng)了水平位置誤差的影響；垂直位置精度因子VDOP反應(yīng)了垂直位置誤差的影響；時間精度因子TDOP反應(yīng)了時鐘誤差的影響，其表達式分別如下

(6)

由式(6)，我們有了評價精度因子的指標(biāo)，可以看出精度因子只與用戶位置和偽衛(wèi)星位置有關(guān)，根據(jù)不同的要求，取不同的精度因子，為粒子群優(yōu)化中的適應(yīng)度函數(shù)，則可以找到對應(yīng)的最優(yōu)的偽衛(wèi)星布站方案。

3 基于粒子群算法的偽衛(wèi)星布站優(yōu)化方法

3.1 基本粒子群優(yōu)化方法

在基本的粒子群算法中，先在可行解空間中隨機初始化n個粒子構(gòu)成初始種群，并為每個粒子隨機初始化一個速度，每個粒子都對應(yīng)優(yōu)化問題的一個解，并由目標(biāo)函數(shù)為之確定一個適應(yīng)值，而速度用來決定粒子在解空間中的運動。在算法的每次迭代中，粒子將跟蹤自身從開始到當(dāng)前找到的自身最優(yōu)解和種群當(dāng)前找到的最優(yōu)解，逐代搜索，直到最后得到最優(yōu)解。

(7)

其中，c1和c2稱為加速度因子，通常取為2；R1與R2為均勻分布于[0，1]之間的隨機數(shù)，且相互獨立；a稱為約束因子，通常為1；ω為慣性權(quán)值，通常取為1。

式(7)為粒子群算法基本算法，即基本粒子群算法?；綪SO算法早期收斂速度非常快，但卻暴露出局部搜索能力差的缺點，這使得算法后期收斂速度緩慢且求解精度降低。

為了改進粒子群算法，使得開始迭代時盡可能在較大范圍內(nèi)搜索，避免陷入局部最優(yōu)解，當(dāng)?shù)竭_一定階段后，縮小迭代范圍，在較小范圍內(nèi)迭代求解，提高求解精度，Shi等[10]進一步提出了LDIV策略，即在迭代過程中線性地減小慣性權(quán)值，并表示為

(8)

其中，ωmax、ωmin分別表示優(yōu)化過程中慣性權(quán)值的最大最小值，N表示最大迭代次數(shù)，np表示當(dāng)前已迭代的次數(shù)。通過線性遞減慣性權(quán)值，提高了優(yōu)化算法性能，減少迭代次數(shù)，提高了精度，本文采用線性遞減粒子群算法來優(yōu)化偽衛(wèi)星布站問題。

3.2 基于粒子群算法的布站優(yōu)化設(shè)計

基于粒子群算法的優(yōu)化布站設(shè)計主要分以下幾步：

1)初始化。確定可布站分布范圍和需要布站的偽衛(wèi)星數(shù)目，取所有偽衛(wèi)星三維位置坐標(biāo)值的組合作為每個粒子的位置，在可布站分布范圍內(nèi)隨機初始化粒子的位置矢量和速度矢量，偽衛(wèi)星數(shù)目至少為4。并將粒子當(dāng)前位置初始化為該粒子歷史最優(yōu)解，以所需DOP因子為適應(yīng)度函數(shù)，尋找當(dāng)前DOP最小的粒子位置為全局最優(yōu)解。

2)逐步迭代。按照式(7)和式(8)，進行粒子位置和速度進化，在更新位置過程中，我們要不斷對每個粒子的各維位置坐標(biāo)進行檢測，若大于所限定區(qū)域上界，則約束為上界；若小于所限定區(qū)域下界，則約束為下界，這樣使得粒子不超出所限定區(qū)域。同時，對DOP因子的計算過程涉及到矩陣求逆，在求逆之前應(yīng)先檢測矩陣是否可逆，對于不可逆的結(jié)果定義為無效位置，不參與最優(yōu)解計算與比較，繼續(xù)下一次迭代。

3)更新最優(yōu)解。每次迭代后都要重新計算各個粒子的適應(yīng)度(這里指所要求優(yōu)化目標(biāo)的DOP值)。對每個粒子當(dāng)前適應(yīng)度和該粒子歷史最優(yōu)適應(yīng)度進行比較，若優(yōu)于歷史最優(yōu)適應(yīng)度，則更新該粒子的最優(yōu)解。最后，選出粒子群的最優(yōu)適應(yīng)度作為全局最優(yōu)解。

4)算法結(jié)束。當(dāng)?shù)竭_優(yōu)化迭代次數(shù)或者達到求解精度后結(jié)束迭代，當(dāng)前全局最優(yōu)解即為最優(yōu)布站方案。

算法流程如圖2所示。

圖2 基于粒子群算法的偽衛(wèi)星布站優(yōu)化設(shè)計流程圖Fig.2 Flow chart of pseudo-satellite stationoptimization design based on particle swarmoptimization algorithm

4 仿真分析

根據(jù)一種最基本的偽衛(wèi)星定位系統(tǒng)的設(shè)計，采用4～5顆偽衛(wèi)星組成偽衛(wèi)星網(wǎng)絡(luò)，在本次仿真中，對坐標(biāo)系的定義進行說明如下：坐標(biāo)系用o0x0y0z0表示，坐標(biāo)原點用o0表示，o0x0軸在坐標(biāo)原點的水平面內(nèi)，指向瞄準(zhǔn)方向；o0y0軸沿過坐標(biāo)原點的鉛垂線，與o0x0軸垂直且指向上；o0z0軸與o0x0軸及o0y0軸形成右手直角坐標(biāo)系。在以上坐標(biāo)系中，偽衛(wèi)星布局范圍(-300，0，-300)，(-300，0，300)，(60，0，-300)，(60，0，300)(單位：km)。目標(biāo)優(yōu)化軌跡為從兩條從原點出發(fā)在xoy平面內(nèi)以拋物線方式前進一段距離。由于最遠(yuǎn)端對應(yīng)精度因子最差的點，以軌跡最遠(yuǎn)端(坐標(biāo)(300，10，0))為優(yōu)化點，以此來實現(xiàn)對整條軌跡的優(yōu)化。

1)4顆陸基偽衛(wèi)星(Y=0)，以HDOP為粒子群適應(yīng)度函數(shù)，迭代次數(shù)200次，偽衛(wèi)星布站優(yōu)化結(jié)果如表1所示(坐標(biāo)單位為km)。

表1 4顆陸基偽衛(wèi)星、HDOP為適應(yīng)度函數(shù)的布站優(yōu)化結(jié)果Tab.1 Optimization results of pseudo-satellite stationby 4 ground-based pseudo-satellites and HDOP as the fitness function

以表1優(yōu)化結(jié)果為偽衛(wèi)星位置，對遠(yuǎn)近兩種軌跡的HDOP進行仿真，結(jié)果如圖3所示。

由圖3可以看出，優(yōu)化后的偽衛(wèi)星布站可以使得較近軌跡上的HDOP在1.6～2.18，較遠(yuǎn)軌跡上的HDOP在1.6～3.17，已經(jīng)達到了可以與GPS導(dǎo)航衛(wèi)星相比擬的程度，可以滿足工程對水平方向定位精度要求的需求。

圖3 沿著近軌跡和遠(yuǎn)軌跡HDOP仿真曲線圖Fig.3 Simulation curves of HDOP along the track of near and far trajectories

2)4顆陸基偽衛(wèi)星(Y=0)，以PDOP為粒子群適應(yīng)度函數(shù)，迭代次數(shù)200次，偽衛(wèi)星布站優(yōu)化結(jié)果如表2所示(坐標(biāo)單位為km)。

表2 4顆陸基偽衛(wèi)星、PDOP為適應(yīng)度函數(shù)的布站的優(yōu)化結(jié)果Tab.2 Optimization results of pseudo-satellitestation by 4 ground-based pseudo-satellites and PDOP as the fitness function

以表2優(yōu)化結(jié)果為偽衛(wèi)星位置，對近軌跡和遠(yuǎn)軌跡的HDOP、VDOP、GDOP進行仿真，結(jié)果如圖4所示。

由圖4中6個仿真圖可以看出，以定位精度因子PDOP為粒子群適應(yīng)度函數(shù)情況下，在水平方向定位精度比以HDOP為適應(yīng)度函數(shù)求解得水平方向精度稍差，由于偽衛(wèi)星都布設(shè)在地面，垂直方向精度因子都比水平方向精度因子大很多，說明地基偽衛(wèi)星不適用于高程定位。通過粒子群算法優(yōu)化，可以保證在較近仿真軌跡上，垂直精度因子小于32；在較遠(yuǎn)仿真軌跡上，垂直精度因子小于55。也說明在遠(yuǎn)離偽衛(wèi)星區(qū)域的地表附近，定位精度急速惡化，此時應(yīng)采用其他方法彌補偽衛(wèi)星高程定位的不足，以確保飛行器全程導(dǎo)航定位。

3)3顆陸基偽衛(wèi)星(Y=0)，1顆高程20km以內(nèi)空基偽衛(wèi)星(0km≤Y≤20km)，以PDOP為粒子群適應(yīng)度函數(shù)，迭代次數(shù)200次，偽衛(wèi)星布站優(yōu)化結(jié)果如表3所示(坐標(biāo)單位為km)。

表3 3顆地基偽衛(wèi)星和1顆空基偽衛(wèi)星、PDOP為適應(yīng)度函數(shù)的布站的優(yōu)化結(jié)果Tab.3 Optimization results of pseudo-satellite station by 3 ground-based and 1 air-based pseudo-satellites and PDOP as the fitness function

以表3優(yōu)化結(jié)果為偽衛(wèi)星位置，對較近仿真軌跡和較遠(yuǎn)軌跡的HDOP、VDOP、GDOP進行仿真，結(jié)果如圖5所示。

圖4 沿著近軌跡和遠(yuǎn)軌跡HDOP、VDOP和PDOP仿真曲線圖Fig.4 Sinulation curves of HDOP，VDOP and PDOP along the track of the near and far trajectories

圖5 沿著近軌跡和遠(yuǎn)軌跡HDOP、VDOP和PDOP仿真曲線圖Fig.5 Simulation curves of HDOP，VDOP and PDOP along the track of the near and far trajectories

由圖5中6個仿真曲線圖可以看出，增加1顆空基偽衛(wèi)星后，除去軌跡起始點和終止點處，全程VDOP和PDOP有一定改進，HDOP有一定的惡化。增加空基偽衛(wèi)星后，提高了高程定位精度，從而用戶三維定位精度都有所提高，但是空基偽衛(wèi)星需要將偽衛(wèi)星放置于20km高空，會有飛行器移動的動態(tài)造成用戶測距困難，可能引入較大誤差。

從以上仿真結(jié)果可以看出，基于粒子群算法的偽衛(wèi)星布站優(yōu)化方案，可以根據(jù)不同指標(biāo)要求和不同布站環(huán)境下尋找出較優(yōu)化的偽衛(wèi)星布站方案，從而證實了本文所提出方案的可行性。

5 結(jié)論

通過本文所述線性遞減權(quán)值粒子群優(yōu)化算法，對偽衛(wèi)星布站進行優(yōu)化設(shè)計，針對不同適應(yīng)度函數(shù)，優(yōu)化得出滿足不同要求的偽衛(wèi)星布站方案，大大提高了偽衛(wèi)星獨立導(dǎo)航定位系統(tǒng)的定位精度，提高了偽衛(wèi)星系統(tǒng)的性能，本文方案對偽衛(wèi)星布站設(shè)計具有重要的工程應(yīng)用價值。

[1] Choudhury M，Rizos C.Slow structural deformation monitoring using Locata-A trial at Tumut Pond Dam[J].Journal of Applied Geodesy，2010，4(4)：177-187.

[2] Bonenberg L K，Hancock C，Roberts G W.Locata performance in a long term monitoring[J].Journal of Applied Geodesy，2013，7(4)：271-280.

[3] Jianpeng W，Jingxiang GAO，Chao LIU，et al.High precision slope deformation monitoring model based on the GPS/Pseudolites technology in open-pit mine[J].Mining Science and Technology，2010，20(1)：126-132.

[4] Montillet J P，Meng X，Taha A，et al.Achieving centimeter-level positioning accuracy in urban canyons with locata technology[J].Positioning，2007，1(12).

[5] Kennedy J.Particle swarm optimization[M].Encyclopedia of Machine Learning.Springer US，2010：760-766.

[6] Elegbede C.Structural reliability assessment based on particles swarm optimization[J].Structural Safety，2005，27(2)：171-186.

[7] Robinson J，Rahmat-Samii Y.Particle swarm optimization in electromagnetics[J].Antennas and Propagation，IEEE Transactions on，2004，52(2)：397-407.

[8] Salman A，Ahmad I，Al-Madani S.Particle swarm optimization for task assignment problem[J].Microprocessors and Microsystems，2002，26(8)：363-371.

[9] GPS原理與接收機設(shè)計[M].電子工業(yè)出版社，2009.

[10] Shi Y，Eberhart R C.Empirical study of particle swarm optimization[C].Evolutionary Computation，1999.CEC 99. Proceedings of the 1999 Congress on.IEEE，1999，3.

Optimal Design of Pseudo-satellite Station Based on Particle Swarm Optimization Algorithm

LI Dong-xin1，3，PENG Yun2，CHANG Qing1，LI Jing3，YU Yuan3

(1.Electronic and Informational Engineering Institute，Beihang University，Beijing 100191，China；2.Beijing Institute of Space Long March Vehicle，Beijing 100076，China；3.R&D Center of Traffic Information and Communication Technology，Beijing 100011，China)

For pseudo-satellite station problem，we adopt the particle swarm algorithm which has the function of intelligent optimization.We use the accuracy factor of navigation and positioning as the fitness function of the particle swarm，with a linear decreasing inertia weight strategy and the appropriate number of evolution and iterative，eventually to find optimal design of pseudolite station.We use two parabolic trajectories in the vertical planes for simulation，the results show that，the station design scheme for pseudo-satellite based on particle swarm optimization algorithm can reduce the whole precision factor，and improve the positioning accuracy of independent pseudo-satellite positioning system.

Particle swarm algorithm；Linear decreasing inertia weight strategy；Pseudo-satellite station

2015 - 07 - 15；

2015 - 08 - 13。

國家863項目基金(2013AA122403)

李東新(1989 - )，男，碩士，主要從事擴頻通信，衛(wèi)星導(dǎo)航，信息處理方面的研究。

E-mail：lidx2013@buaa.edu.cn

TN967.1

A

2095-8110(2015)05-0044-08