席志紅,常佳博

(哈爾濱工程大學 信息與通信工程學院，哈爾濱　150001)

?

基于LS-PSO的北斗偽距單點定位算法

席志紅,常佳博

(哈爾濱工程大學 信息與通信工程學院，哈爾濱150001)

北斗偽距單點定位具有易于實現(xiàn)、不存在整周模糊度、速度快等特點，具有很大的研究和應用價值;傳統(tǒng)最小二乘法由于引入了線性誤差、對初始值依賴性強而導致定位精度低;為了提高北斗偽距單點定位的精度，通過分析最小二乘法和粒子群算法的優(yōu)缺點，提出了一種LS-PSO組合算法;首先利用最小二乘法定位計算接收機的大約位置，作為粒子群算法解的基準值并建立解的搜索空間，然后利用粒子群算法得到全局最優(yōu)值，解算出精度更高的結果;經過實驗驗證，LS-PSO組合算法可以穩(wěn)定的解算出m級精度的定位結果，并且三維方向偏差都在大約5 m以內;最后通過與遺傳算法的收斂情況和最小二乘法的定位精度進行對比，證明LS-PSO組合算法可以快速的收斂到最優(yōu)解并且有效的提高了北斗偽距單點定位精度。

北斗；偽距單點定位；最小二乘-粒子群；精度

0　引言

近年來，北斗衛(wèi)星導航系統(tǒng)的發(fā)展越來越迅速，提高北斗的定位精度一直是研究的熱點。偽距單點定位不涉及到模糊度的求解，而且只要觀測衛(wèi)星數目足夠可以快速地定位出大約的位置，在北斗完成組網后，北斗偽距觀測質量優(yōu)于 GPS，特別是北斗GEO 衛(wèi)星偽距觀測量受多路徑、硬件延遲及隨機噪聲的影響比北斗其他衛(wèi)星及GPS衛(wèi)星都要小很多[1]。但是其之前受限于觀測衛(wèi)星較少而稍微劣勢于GPS。因此如何提高北斗系統(tǒng)偽距單點定位精度，也是時下研究的熱點方向。鑒于傳統(tǒng)的最小二乘法雖然可以快速解算出位置，但是結果不可靠，偏差較大，而且在解算過程中進行了線性化處理，引入了線性誤差。所以基于偽距觀測的非線性方程，對其進行直接解算尋找最優(yōu)值，也是提高偽距單點定位的方法之一。文獻[2]提出了一種基于遺傳算法的GPS單歷元解算方法，該方法雖然有效的提高了定位精度，但是遺傳算法的收斂速度太慢，很耗解算時間；文獻[3]同樣采用了遺傳算法進行了GPS的動態(tài)單點定位，但是同樣存在收斂速度慢的問題。文獻[4]提出了一種快速的最小二乘算法，利用差值法和牛頓法相結合進行解算，加速了解算的速度和可靠性，但是由于其還是進行了線性化處理，所以同樣不可避免地引入了線性誤差。

1　北斗系統(tǒng)簡介

北斗導航系統(tǒng)是中國自行研制的全球衛(wèi)星導航系統(tǒng)。北斗導航系統(tǒng)目前在軌正常工作的衛(wèi)星有5顆GEO衛(wèi)星、5顆IGSO衛(wèi)星和4顆MEO衛(wèi)星。北斗導航系統(tǒng)在2012年已具備覆蓋亞太地區(qū)的定位、導航和授時以及短報文通信服務能力。預計在2020年左右，建成覆蓋全球的北斗衛(wèi)星導航系統(tǒng)。

北斗系統(tǒng)的時間基準為北斗時(BDT)，起始歷元為協(xié)調世界時(UTC) 2006 年 1 月 1 日00 時 00 分 00 秒，單位為國際單位制(SI)秒[5]。GPST可以在200納秒的偏差內粗略的通過公式(1)來轉換為BDT：

tBDT=tGPST-14

(1)

北斗系統(tǒng)采用的坐標系統(tǒng)為2000中國大地坐標系(CGCS2000)。

2　北斗偽距單點定位數學模型

北斗系統(tǒng)t時刻的碼偽距觀測模型[6]為：

(2)

+δion+δtrop+δtide+δrel-cδs(t)

(3)

式中,Xs(t)、Ys(t)、Zs(t)為t時刻衛(wèi)星在地心坐標系下位置矢量的三分量，Xr、Yr、Zr為接收機在地心地固坐標系(ECEF)下位置矢量的3個分量。衛(wèi)星的鐘差參數已知，可以通過衛(wèi)星廣播導航電文得到。鐘差參數包括toc，a0，a1和a2。toc為本時段鐘差參數參考時間，單位為秒，其它3個參數為二進制補碼，則t時刻的衛(wèi)星鐘差可由式4得到 ：

δs(t)=a0+a1(t-toc)+a2(t-toc)2+δrel

(4)

其中：δrel為相對論校正項，單位為s，其值為：

(5)

信號發(fā)射時刻的北斗時可由

t=tsv-δs(t)

(6)

得到，t為信號發(fā)射時刻的北斗時，單位為秒，tsv為信號發(fā)射時刻的衛(wèi)星測距碼相位時間，單位為秒，式中，t可忽略精度，用tsv替代。對于北斗系統(tǒng)，需要通過星上設備時延差TGD1、TGD2進行修正，對于B1I信號，通過 TGD1修正，對于B2I信號，通過TGD2修正[7]。

(δs(t))B1I=δs(t)-TGD1

(7)

(δs(t))B2I=δs(t)-TGD2

(8)

則鐘差之差：

(9)

式中衛(wèi)星鐘差δs(t)已知，接收機鐘差δr(t)未知。將式(9)代入式(2)中并整理得：

(10)

L=F(X)+V,P

(11)

其中:L為觀測向量；X為未知數向量，F(xiàn)(X)是X對應的非線性函數，V為殘差向量，P為觀測向量的權矩陣。因此根據公式(11)可以對未知數向量X進行最小二乘估計。

則解觀測方程由最小二乘準則可的目標函數為：

H(x)=minVTPV

(12)

觀測方程解算未知數的有解的充分非必要條件是，觀測值的格式大于或者等于未知數的個數。觀測值的個數可以表示為ns·nt，其中ns為衛(wèi)星的個數，nt為觀測的歷元數。方程的未知量為觀測站的三維坐標和每個歷元的鐘差，因此，觀測方程有解的基本條件[8]可以表示為：

ns·nt≥3+nt

(13)

由式(13)可知方程有解需要的最少觀測衛(wèi)星數為2時，最少觀測歷元數為3；當觀測的衛(wèi)星數為時，可以得到最少觀測歷元數為1。所以可知，只要有4顆以上的觀測衛(wèi)星，就可以求出任意歷元的4個未知量。

3　基于LS-PSO的北斗偽距單點定位的求解與實現(xiàn)

3.1LS算法定位解算

最小二乘算法(LS)作為衛(wèi)星導航常用的定位算法，已經廣泛的用于偽距單點定位的基本運算當中，根據式(11)，將非線性函數F(X)在待求點(X0,Y0,Z0)展開為泰勒級數[9]，并且忽略二階及以上高階項，得：

(14)

即：

(15)

將式(16)代入式(10)，可得：

(16)

其中：vs為衛(wèi)星s的殘差向量。

令

則公式(16)可以表示為：

(17)

將所有衛(wèi)星的系數放在一起構成系數矩陣A，則可以得到北斗偽距單點定位的線性系統(tǒng)方程：

L=A·dX+V,P

(18)

其中:L為觀測向量，dX為未知數向量，V為殘差向量，P為觀測向量的權矩陣。因此根據公式(19)可以對未知數向量dX進行最小二乘估計。

根據加權最小二乘法的原理，式(19)的最小二乘解為：

dX=(ATPA)-1ATPL

(19)

求出dX然后更新(X0,Y0,Z0)，使：

(X0,Y0,Z0)=(X0+dXr,Y0+dYr,Z0+dZr)

(20)

利用牛頓迭代法，不斷迭代更新(X0,Y0,Z0)的值，直到達到預設精度閾值，即可得到接收機的位置。

3.2PSO算法的基本原理

粒子群算法(particle swarm optimization，PSO算法)是一種基于群智能的優(yōu)化算法，是對鳥兒覓食的社會行為的模擬。它從一組隨機解出發(fā)，通過迭代尋找最優(yōu)解。由于原始PSO算法有容易陷入局部最優(yōu)解，收斂精度差等缺點，因此研究者們對PSO算法進行了多種改進措施，Shi等人提出了慣性權重線性下降PSO算法(LDW-PSO)，該算法可以提高算法的收斂性能，平衡收斂的全局性和收斂速度，在多峰函數中效果明顯；Clerk提出了帶收縮因子的PSO算法(CFM)，該算法在保證收斂性的同時使速度的限制放松，畢曉君教授在《信息智能處理技術》一書中，提出了基于種群分類與動態(tài)學習因子的粒子群改進算法，改算法采用動態(tài)調整學習因子的方法平衡進化不同階段粒子的全局和局部搜索能力，提高了算法的性能[10]。

基于北斗偽距定位的數學模型是單峰多維的函數，本文采用引入收縮因子的PSO算法(CFM-PSO)進行北斗偽距單點定位，設置收縮因子k：

(21)

假設代優(yōu)化問題的解釋N維的，由M個粒子組成一個群體，任何一個可能的解(一個粒子)都可以看成是一個N維向量Xi={xi1,xi2,···,xiN},i=1,2,3,···,M。同時粒子i還具有一個與Xi(t)同維數的，隨著迭代次數t增加而不斷變化的速度向量Vi(t)。將Xi帶入目標函數就可以求出第i個粒子的適應值，根據適應值的大小衡量值的優(yōu)劣。

PSO算法的基本流程為[11]：

1)初始化種群規(guī)模M，設定初始值Xi(0)，初始速度Vi(0)(i=1,2,3,···,M)，初始第i個粒子的最好位置Pi(0)和整個群體記憶的最好位置Gi(0)；

2)設迭代次數為t，令t=1開始迭代；

3)利用式(22)和式(23)，計算每個粒子的Xi(t)，Vi(t)。

(22)

Xi(t)=Xi(t-1)+Vi(t)

(23)

其中:rand()是[0,1]之間的隨機數，C1和C2是學習因子。

4)計算每個粒子的適應值，將每個粒子的適應值和其經歷過的最好位置Pi(t-1)作比較，若較好，則作為當前的最優(yōu)值。

Pi(t)=argmin{f(Pi(t)),f(Xi(t))}

(24)

5)將每個粒子經歷的最好位置Pi(t)的適應值進行比較，得到全局最優(yōu)值G(t)。

G(t)=argmin{f(P1(t)),···,f(Pi(t)),···,f(PM(t))}

(25)

6)判斷是否滿足終止條件(一般為迭代的最大次數)，若滿足，則G(t)為最優(yōu)解。

3.3基于LS-PSO組合算法的解算算法描述

LS算法的特點和不足是：

1)進行定位解算雖然速度很快，但是精度上往往很低；

2)受初始值影響較大，而且在觀測值質量不是很好或者衛(wèi)星數不是很多的情況下，精度更會大大地降低；

3)線性化的過程存有線性誤差，影響定位精度。

PSO算法的特點和不足是：

1)不受初值的影響，收斂快，穩(wěn)定高，收斂精度高的特點；

2)容易陷入局部最優(yōu)，但是采用CFM以后可以有效改善；

3)在定位的開始，無法確定接收機的大體位置，所以要搜索的解空間是巨大的。

因此為了提高北斗偽距單點定位的精度，并且減小PSO的搜索范圍，本文將兩者結合，首先用LS算法定位得到接收機的大約位置作為PSO算法解的基準值，建立解的搜索空間，再利用PSO算法得到全局最優(yōu)值，解算出精度更高的結果。

由式(3)和式(12)可以得：

(26)

H(x)作為PSO算法的適應度函數，向量X=(Xr,Yr,Zr，δr(t))組成該方程的解空間。初始化種群M，學習因子C1、C2，最大迭代次數tmax，最大速度Vmax。采用LS算法得到的定位結果Xtemp=(Xt,Yt,Zt.δt(t))作為的基準值，隨機產生Xi(0)、Vi(0)，初始化Pi(0)，G(0)。對每次迭代，每個粒子，根據4.1所述流程計算，最終輸出全局最優(yōu)值G(t)。算法流程如圖1所示。

4　實驗結果及分析

實驗程序是基于開源代碼RTKLIB函數庫進行開發(fā)，開發(fā)環(huán)境為C#，數據取哈工程某實驗樓觀測點2015年1月6日的30個連續(xù)歷元的觀測數據進行單歷元解算。為了驗證算法的可靠性，以下數據均在觀測衛(wèi)星數穩(wěn)定為4的情況下進行定位。

4.1PSO算法收斂性能分析

為了驗證PSO算法的收斂性能，取

M=50,φ=4,C1=C2=2.05,tmax=100

Xmax=Xtemp+30,Vmax=1.5*Xmax

其中：Xmax為解空間范圍最大值，則由式(14)可求得k=0.729，選取其中一個歷元進行定位解算，觀察適應度函數值的收斂情況，如圖2所示。

圖1　LS-PSO算法流程圖

圖2　適應度函數收斂性能圖

由圖2可見，迭代次數在10左右時，適應度函數值開始大范圍收斂，到28次左右時，小幅度逼近最優(yōu)值，參考文獻[3]中應用遺傳算法解算GPS單歷元單點定位時，要在進化代數大于70左右才能小幅度逼近最優(yōu)值，由于GPS和北斗在單歷元偽距單點定位解算時的適應度函數是相同的，因此可以看出在收斂速度上，LS-PSO算法是遠遠快于遺傳算法的。

4.2定位精度分析

PSO算法進行定位解算是對非線性方程組的求解，因此不能用LS算法的精度標準來規(guī)劃衡量LS-PSO算法的定位精度。LS算法得到的定位解釋唯一解，而LS-PSO算法得到的是全局最優(yōu)解，為了對比LS算法和LS-PSO算法的精度，本文采用與三維坐標與真值的差值和三維坐標與真值的幾何距離來對比兩種算法的精度，采用單歷元重復多次定位的方法來驗證算法的穩(wěn)定度。

任取一個歷元重復定位100次，取

M=50,φ=4,C1=C2=2.05,tmax=100

Xmax=Xtemp+30,Vmax=1.5*Xmax

其中：Xmax為解空間范圍最大值。隨機記錄其中10次定位結果的三維坐標與真值的差值dx、dy、dz和三維坐標與真值的幾何距離dr，并且記錄同一歷元最小二乘法相應數據作為對比。記錄數據如表1所示，圖2顯示了100次定位的dx、dy、dz、dr的分布情況。

表1　LS-PSO算法和LS算法定位對比

圖3　100次定位的dx、dy、dz、dr分布情況

由表1可知，LS-PSO算法的三維向量偏差和與真值的幾何距離差均優(yōu)于LS算法；由圖2可知，LS-PSO算法所得到的解算結果穩(wěn)定，并且X方向與真實值偏差在5 m以內，大多數優(yōu)于4 m，Y方向偏差在4 m以內，多數優(yōu)于3 m，Z方向偏差在6 m以內多數優(yōu)于5 m。與真值的空間幾何距離偏差在6 m以內達到m級定位精度。并且數據波動很小，表示定位結果很穩(wěn)定。在多數情況下，X方向和Y方向的偏差甚至可以達到厘米級。因此采用LS-PSO組合的算法可以良好的提高北斗偽距單點定位的精度，并且算法是穩(wěn)定可靠地。

5　結論

本文通過對比LS算法和PSO算法的優(yōu)缺點，綜合兩者各自的優(yōu)勢，提出LS-PSO組合的算法，通過LS算法確定解空間范圍，PSO算法搜索得到全局最優(yōu)解。通過100歷元的單歷元獨立重復試驗，證明該算法的穩(wěn)定性，且精確度相對于傳統(tǒng)LS算法有所提高。本文算法易于實現(xiàn)，不足是迭代計算耗費了大量的時間，因此是在犧牲了部分解算速度情況下提高了定位的精度。在連續(xù)歷元解算的過程中，可以利用前一歷元得到的定位結果作為本歷元的初值，減小搜索范圍，不但降低了搜索的復雜度，而且可以設定精度閾值，提前終止迭代，加快連續(xù)單歷元解算的速度，這是下一步的研究工作，對于簡單快速提高北斗偽距單點定位精度的有很大的意義。

[1] 嚴麗，黃丁發(fā)，馮威，等.COMPASS與GPS偽距單點定位性能比較研究[A].第三屆中國衛(wèi)星導航學術年會電子文集——S06北斗/GNSS測試評估技術[C].2012.

[2] 劉智敏,劉經南,劉暉. 基于遺傳算法的GPS單歷元單點定位方法研究[J]. 武漢大學學報· 信息科學版,2007,32(1).

[3] 徐愛功,徐濤,張明月,等. GPS 動態(tài)單點定位的遺傳算法探究[J]. 測繪科學,2009(S2)：18-20.

[4] 李春華,蔡成林,鄧克群,等. 一種北斗偽距單點定位的加權最小二乘 (WLS) 快速算法[J]. 重慶郵電大學學報 (自然科學版),2014,4: 008.

[5] 豐勇. COMPASS 系統(tǒng)的偽距單點定位算法研究[J]. 測繪與空間地理信息,2015 (7).

[6] Xu G C. GPS 理論,算法與應用[M]. 北京：清華大學出版社,2011.

[7] 北斗衛(wèi)星導航系統(tǒng)空間信號接口控制文件公開服務信號(2.0版)[Z].中國衛(wèi)星導航系統(tǒng)管理辦公室,2013.

[8] Wellenhof H B,Lichtenegger H,Wasle E. 全球衛(wèi)星導航系統(tǒng) GPS,GLONASS,Galileo 及其他系統(tǒng)[J]. 導航定位學極，2010(2):83.

[9] 許承東. GNSS數學仿真原理及系統(tǒng)實現(xiàn)[M]. 北京：中國宇航出版社，2014.

[10] 畢曉君.信息智能處理技術[M]. 北京：電子工業(yè)出版社,2010.

[11]張建科,王曉智,劉三陽,等. 求解非線性方程及方程組的粒子群算法[J]. 計算機工程與應用,2006,42(7): 56-58.

Compass Pseudorange Single-point Positioning Algorithm Based on LS-PSO

Xi Zhihong，Chang Jiabo

(College of Information and Communication Engineering,Harbin Engineering University,Harbin150001,China)

Compass pseudorange single-point has characteristics of easy to implement,without ambiguity problem,postioning fast . It has great value for research and application. Traditional least squares algorithm has linear error and strong dependence on initial values so that its accuracy of positioning is very low. In order to improve the accuracy of Compass pseudorange single-point positioning,proposed a combination algorithm of LS-PSO by analyzing the advantages and disadvantages of least squares algorithm(LS) and particle swarm optimization(PSO).Firstly it obtains the approximate location of receiver for the base value of PSO by LS and establishes the search space of the solution. Then it calculates the global optimum by PSO so that the result has higher accuracy. Through the verification of experiments,LS-PSO can calculate m-level precision positioning results stably and the three-dimensional errors are all within 5 meters. Finally by compared with the positioning accuracy of LS and the convergence of genetic algorithm,it proves that LS-PSO can converge to the optimal solution quickly and improve the accuracy of Compass pseudorange single-point positioning effectively.

compass; pseudorange single-point positioning; LS-PSO; accuracy

1671-4598(2016)04-0167-04DOI：10.16526/j.cnki.11-4762/tp.2016.04.049

P228.4

A

2015-10-12；

2015-11-06。

席志紅(1965-)，女，陜西省西安人，教授，碩士研究生導師，主要從事北斗定位算法和圖像處理方向的研究。