基于改進(jìn)變異粒子群算法的TDOA/AOA定位研究*

胡 駿，樂英高,b,c，蔡紹堂，曹 莉，吳 浩

(四川理工學(xué)院 a.自動化與信息工程學(xué)院；b.人工智能四川省重點(diǎn)實(shí)驗(yàn)室；c.材料腐蝕與防護(hù)四川省重點(diǎn)實(shí)驗(yàn)室，四川 自貢 643000)

0 引言

移動通信定位技術(shù)[1]是基于美國的全球衛(wèi)星定位系統(tǒng)GPS(Global Positioning System)、中國的北斗雙星BDS(BeiDou Navigation Satellite System)、歐洲的全球衛(wèi)星導(dǎo)航系統(tǒng)伽利略(Galileo)、全球移動通信系統(tǒng)GSM(Global System for Mobile communication)等衛(wèi)星定位系統(tǒng)，通過接收基站和移動臺之間的無線電波，檢測無線電波信號的特征參數(shù)，如幅度、信號入射角、傳輸時間差等，如圖1所示。利用參數(shù)根據(jù)相應(yīng)的定位算法計(jì)算得到移動臺的估計(jì)幾何位置。

圖1 移動通信定位

移動通信中研究的無線定位技術(shù)[2]有兩種實(shí)現(xiàn)方案?；诜较虻亩ㄎ患夹g(shù)，如到達(dá)角(AOA，Angle of Arrival)定位技術(shù)，即利用基站接收機(jī)的天線陣列來測量由移動臺所發(fā)出電波的入射角，并構(gòu)成移動臺到基站的徑向連線，多條連線的交點(diǎn)就是移動臺的位置；基于距離的定位技術(shù)，如到達(dá)時間差(TDOA，Time Difference of Arrival)定位技術(shù)，即利用基站檢測到信號的時間與移動臺發(fā)射信號的時間差，計(jì)算出基站與移動臺之間的距離，時間差測量值表現(xiàn)形式為雙曲線，多條雙曲線的交點(diǎn)就是移動臺的位置[3]?，F(xiàn)有的AOA定位技術(shù)會因?yàn)橐苿优_到基站的位置遠(yuǎn)近，非視距傳播以及其他環(huán)境改變，使得定位精度大幅降低，如當(dāng)兩者距離較遠(yuǎn)時，測量角度出現(xiàn)一點(diǎn)的微小偏差，則定位距離會受到很大的影響。而TDOA定位技術(shù)對所有參與定位的基站的時間雖然相比于到達(dá)時間(TOA，Time of Arrival)沒有要求嚴(yán)格的完全同步，但依然對時間基準(zhǔn)的依賴性較高[4]。

針對上述的AOA或TDOA所存在的問題，研究人員提出了TDOA/AOA混合定位算法[5]。TDOA/AOA混合定位算法可以充分利用蜂窩網(wǎng)絡(luò)產(chǎn)生的對移動臺位置估計(jì)定位的優(yōu)良電波特征測量值，克服由時間同步和多徑傳播產(chǎn)生的部分誤差，減小環(huán)境對定位精度的影響。單一定位技術(shù)具有其局限性，因此混合算法結(jié)合不同定位算法的優(yōu)點(diǎn)，必定具有更加精確的定位性能。但TDOA是通過電波到達(dá)時間差對移動臺(MS，Mobile Station)的位置建立方程，AOA是通過信號到達(dá)角度對MS的位置建立方程，如何求解這兩種不同類型非線性方程聯(lián)立的非線性方程組，是各類TDOA/AOA混合定位方法的重點(diǎn)和難點(diǎn)。

1 相關(guān)工作

基于TDOA/AOA混合定位算法在對移動臺位置估計(jì)定位中具有更精確的定位性能，研究者加入了其他算法，來進(jìn)一步改良TDOA/AOA混合算法[6-8]。現(xiàn)有國內(nèi)外學(xué)者們進(jìn)行了深入的研究，首先針對減少其受測量誤差的影響，例如文獻(xiàn)[7]提出一種基于TDOA/AOA混合算法噪聲項(xiàng)新的權(quán)重最小二乘(WLS，Weighted Least Squares)方法，開發(fā)結(jié)構(gòu)化全局最小二乘(STLS)方法；文獻(xiàn)[8]提出構(gòu)建混合測量算法未知源位置之間的新關(guān)系，獲得的解的均方誤差矩陣可以獲得小誤差區(qū)域內(nèi)的CRB(Cramér-Rao bound)界限。其次對于混合定位中非線性方程組的問題，求解一般有兩種基本的方法：一是直接求解非線性方程組得到估計(jì)值，文獻(xiàn)[9]提出了運(yùn)用類正態(tài)分布密度曲線建立TDOA誤差模型，使TDOA誤差模型更加接近真實(shí)誤差，用卡爾曼濾波器對TOA測量值濾波使得TOA更加接近真實(shí)的到達(dá)時間，是一種實(shí)時、直接消除誤差的方法；二是通過引入與待求變量有關(guān)的附加變量，把待求的非線性方程組轉(zhuǎn)化為偽線性方程組，進(jìn)而求解，文獻(xiàn)[10]介紹的對最小二乘法進(jìn)行改進(jìn)，分離出引入的附加變量，使得方程兩邊分別是MS的坐標(biāo)和附加變量，最大的優(yōu)點(diǎn)是能夠避免對奇異矩陣求逆。

隨著智能優(yōu)化算法的深入發(fā)展，學(xué)者們也將智能算法應(yīng)用到TDOA/AOA混合定位算法中，處理其存在的問題。文獻(xiàn)[11]中提到了將遺傳算法(GA)運(yùn)用到TDOA/AOA定位系統(tǒng)中，以混合算法產(chǎn)生的定位誤差的CRLB為基準(zhǔn)，通過研究改進(jìn)GA的適應(yīng)度函數(shù)選擇和位置編碼，提高定位精度，達(dá)到尋找最佳的布站策略。文獻(xiàn)[12]中將模擬退火遺傳算法運(yùn)用到TDOA/AOA定位中，克服了運(yùn)用最小二乘法時存在的問題，提高了定位精度和穩(wěn)定性。文獻(xiàn)[13]中將粒子群算法與Chan算法結(jié)合，進(jìn)行協(xié)同定位。移動臺位置的初始解由粒子群算法估算出，基于初始解來構(gòu)建殘差方程，篩選基站后結(jié)合Chan算法對移動臺二次定位得到最終的估計(jì)位置。

本文借鑒文獻(xiàn)[13]提出的粒子群算法對移動臺位置初始解預(yù)先進(jìn)行估計(jì)的思想，提出將遺傳算法中的變異操作加入到粒子群算法的迭代過程中，再將改進(jìn)的變異粒子群(IMPSO)算法應(yīng)用到TDOA/AOA混合定位中，使粒子群算法能夠快速收斂，達(dá)到尋優(yōu)的目的[14]。該算法首先用最大似然法得到移動臺的最大似然估計(jì)函數(shù)，并將最大似然估計(jì)函數(shù)作為適應(yīng)度函數(shù)，然后對PSO算法中的適應(yīng)度方程進(jìn)行變異操作，同時對慣性權(quán)重進(jìn)行改進(jìn)，達(dá)到PSO算法在對適應(yīng)度函數(shù)進(jìn)行尋優(yōu)處理時不會出現(xiàn)陷入局部最優(yōu)的目的，使獲得的移動臺的目標(biāo)坐標(biāo)更加精準(zhǔn)。仿真和對比結(jié)果也表明提出改進(jìn)后的PSO算法具有更優(yōu)越的定位性能。

2 TDOA/AOA混合定位算法

TDOA/AOA混合定位算法就是綜合利用各種信號信息和特征測量值，估計(jì)MS的位置的算法，相對于單獨(dú)的TDOA定位算法或AOA定位算法，將兩種算法模型進(jìn)行結(jié)合使用，可以明顯提高定位精度，減少測量誤差帶來的影響。

建立TDOA/AOA混合定位的三維直角坐標(biāo)系，為了簡化計(jì)算，基站坐標(biāo)為(xi,yi,zi),移動臺MS坐標(biāo)(x,y,z)，如圖2所示。本文研究基站和移動臺在二維平面內(nèi)。

圖2 TDOA/AOA聯(lián)合定位系統(tǒng)模型

假設(shè)在二維平面布置了基站接收機(jī)M個，第i個基站BS的坐標(biāo)為(xi,yi)，移動臺MS的坐標(biāo)為(x,y),移動臺到基站的距離為ri，則根據(jù)(TOA)測量值可列出距離方程：

(1)

式中，c為電波傳播速度，τi為時間差。

一般選擇參考基站為第一個基站，根據(jù)TOA的測量值，可得到TDOA的測量值。假設(shè)距離差為ri,1，表示移動臺到基站i(i≠1)與到基站1的距離差，即：

(2)

式(2)中所示，i=2,3,..M，ni,1是測量TDOA時引入的噪聲，ni,1=ni-n1，ni是系統(tǒng)的測量誤差，r1是基站1到移動臺MS的距離。當(dāng)信噪比高的時候，可認(rèn)為TDOA的測量值近似服從正態(tài)分布，因此ni,1也可認(rèn)為近似服從正態(tài)分布，假設(shè)其均值為0，方差為σ2，假定服務(wù)基站BS總能提供MS的AOA測量值,根據(jù)AOA測量值α可建立方程：

(3)

式(3)中所示，nα是AOA的測量誤差，假設(shè)其服從均值為0，方差為α2的正態(tài)分布。設(shè)Δr=[r2,1,r3,1,…rM,1]T,r=[r2,r3,…rM]T,r1=[r1,r1,…r1]T,n=[n2,1,n3,1,…nM,1]T,據(jù)上式可得：

Δr=r-r1+n

(4)

本文采用最大似然法來確定移動臺MS的坐標(biāo)，因?yàn)閞i,1服從均值為(ri-r1)，方差為σ2的正態(tài)分布，α服從均值為arctan((y-y1)/(x-x1))，方差為α2的正態(tài)分布，假設(shè)各測量值相互獨(dú)立，則移動臺位置的最大似然估計(jì)為：

(5)

用一般方法求解非線性方程(5)，很難得到理想的結(jié)果，因此用IMPSO算法優(yōu)化處理后獲得坐標(biāo)的最優(yōu)解。

3 基于改進(jìn)變異粒子群算法

3.1 粒子群優(yōu)化算法

粒子群算法作為進(jìn)化算法中的一種，優(yōu)點(diǎn)是處理優(yōu)化問題十分有效并且被廣泛使用[15]。算法對于所優(yōu)化的目標(biāo)函數(shù)不存在依賴的關(guān)系，同時具有參數(shù)少、實(shí)現(xiàn)簡單等特點(diǎn)，因此廣泛應(yīng)用于解決非線性優(yōu)化問題。其基本思想為將一組系統(tǒng)已初始化的隨機(jī)粒子，每個粒子，都是表示目標(biāo)函數(shù)存在的可能解，通過計(jì)算分析某種迭代方式進(jìn)行尋優(yōu)，得到最優(yōu)解，即最優(yōu)解表示移動臺MS估計(jì)的位置。PSO算法的實(shí)現(xiàn)：

設(shè)種群中粒子的數(shù)量為S，在d維空間中，U=(uk1,uk2,…ukd)和Y=(yk1,yk2,…ykd)分別表示第k個粒子速度與位置，式中k=1,2,…,S，p=1,2,…,d,即p是維度，ykp∈[Lp,Hp],Lp和Hp分別代表空間維度的下界與上界，uSd∈[Umin,d,Umax,d],Umin,d和Umax,d表示粒子的速度，用Qk=(qk1,qk2,…,qkd)表示第k個粒子的最優(yōu)解，用Qg=(qg1,qg2,…qgd)表示所有種群中的全局最優(yōu)解，依據(jù)公式(6)、式(7)更新每個粒子的速度向量和位置向量。

ukp(z+1)=ωukp(z)+c1r1(qkp(z)-ykp(z))+
c2r2(qgp(z)-ykp(z))

(6)

ykp(z+1)=ykp(z)+ukp(z+1)p=1,2…d

(7)

(8)

式(6)中所示，c1和c2分別為加速因子；當(dāng)前迭代次數(shù)為z，最大迭代次數(shù)為T；r1和r2取[0,1]之間的隨機(jī)數(shù)；r(z+1)是第z次迭代時在[0,1]之間生成的實(shí)數(shù)，其中sigmoid函數(shù)為：

(9)

ω為慣性權(quán)重，取值為：

(10)

式(10)中隨著粒子的迭代進(jìn)化，ω∈(ωmin,ωmax)逐漸由大變小。

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是改進(jìn)變異粒子群算法指導(dǎo)搜索方向的依據(jù)，在算法中，適應(yīng)度最佳對應(yīng)的坐標(biāo)(x,y)即為移動臺坐標(biāo)。取適應(yīng)度函數(shù)為：

(11)

其值越小代表粒子對函數(shù)的適應(yīng)性越好，則粒子k的個體最優(yōu)位置由式(12)確定：

(12)

粒子k的全局最優(yōu)位置由式(13)確定：

qgk(z)∈{qg1(z),…,qgs(z)|fitness(qgs(z)) =
min{fitness(qg1(z)),…|fitness(qgs(z))}}

(13)

設(shè)粒子的坐標(biāo)矢量定義為:

(14)

式(14)中所示，(xi,yi)為移動臺待估計(jì)的坐標(biāo)點(diǎn)。設(shè)移動臺的坐標(biāo)為(x,y)是在基站所構(gòu)成的范圍內(nèi)，即：

(15)

式(15)中所示，xmin和xmax為基站構(gòu)成的范圍內(nèi)橫坐標(biāo)的最小值和最大值，ymin和ymax是基站構(gòu)成的范圍內(nèi)縱坐標(biāo)的最小值和最大值。

3.3 改進(jìn)變異粒子群優(yōu)化算法

傳統(tǒng)的PSO算法在求解復(fù)雜的多峰值的非線性優(yōu)化問題中，會出現(xiàn)容易陷入早熟收斂、陷入局部最優(yōu)等問題[16]。為了解決上述問題，本文結(jié)合慣性權(quán)重和遺傳算法中的變異操作對PSO算法進(jìn)行改進(jìn)。

(1)一般而言，慣性權(quán)重ω對粒子群算法的性能影響較大。當(dāng)慣性權(quán)重較大時，有利于全局搜索，當(dāng)慣性權(quán)重較小時，能夠加速算法收斂，有利于局部搜索。因此，在PSO算法中可以通過改變慣性權(quán)重來提升算法的性能。在混合定位中，因?yàn)樾枰治龅臄?shù)學(xué)模型是一個非線性方程組，因此根據(jù)式(10)提出一個改進(jìn)的慣性權(quán)重值，進(jìn)而優(yōu)化粒子群算法的全局和局部搜索能力：

(16)

式(16)中所示，ω為慣性權(quán)重，ωmax為最大慣性因子，ωmin為最小慣性權(quán)重，z為當(dāng)代迭代次數(shù)，T為最大迭代次數(shù)。

(2)基于粒子位置和速度的更新以及控制種群多樣性的基礎(chǔ)上，引入變異操作。在算法出現(xiàn)陷入局部聚集的問題時，變異能夠讓各個粒子重新搜索新的方向。變異操作的執(zhí)行節(jié)點(diǎn)，需根據(jù)群體適應(yīng)度方差值[17]的指標(biāo)為：

(17)

式(17)中所示，φS為全局最優(yōu)值的變異概率，ε2為適應(yīng)度方差，φmax表示變異概率上限，φmax表示變異概率下限。改進(jìn)后的算法中，當(dāng)粒子的位置呈現(xiàn)出局部聚集的不足時，算法會對粒子進(jìn)行變異操作，能夠?qū)⒕奂牧Ｗ又匦麓蛏?，進(jìn)行新的方向的搜索。

改進(jìn)變異粒子群優(yōu)化算法實(shí)現(xiàn)步驟，如圖3所示。

①初始化粒子群算法各參數(shù)：確定種群規(guī)模S，最大迭代次數(shù)T，加速因子c1和c2，最大慣性權(quán)重ωmax和最小慣性權(quán)重ωmin。

②依據(jù)式(6)、式(7)更新每個粒子的速度向量和位置向量。保證在[vmin,D,vmax,D]速度區(qū)間內(nèi)，若超出上下限，則分別換為vmin,D和vmax,D；

③根據(jù)適應(yīng)度函數(shù)式(11)評價(jià)每個粒子的適應(yīng)度值，將個體最優(yōu)粒子和全局最優(yōu)粒子存在Qk和Qg中；

④根據(jù)式(16)計(jì)算慣性權(quán)重ω；

⑤更新粒子的速度和位移，更新粒子的個體最優(yōu)值和全局最優(yōu)值；

⑥計(jì)算適應(yīng)度方差ε2以及變異概率φS并產(chǎn)生一個隨機(jī)數(shù)e，如果e<φS則按式(18)變異：

qdg=qgd(1+0.3ξ)

(18)

式(18)中，設(shè)ξ服從(0,1)的高斯分布，qgd就是移動臺位置；

⑦判斷算法是否收斂，滿足則繼續(xù)執(zhí)行；不滿足轉(zhuǎn)第②步；

⑧當(dāng)?shù)螖?shù)達(dá)到T，則停止迭代，輸出最優(yōu)解。

圖3 改進(jìn)變異粒子群優(yōu)化定位算法流程圖

4 計(jì)算機(jī)仿真及結(jié)果分析

本文的實(shí)驗(yàn)環(huán)境基于MATLAB2014a平臺，Windows7，64位系統(tǒng)的計(jì)算機(jī)。文中，為了體現(xiàn)提出的IMPSO算法的定位性能(均方根誤差RMSE和均方誤差MSE)，仿真結(jié)果與傳統(tǒng)的Chan算法[18]以及基于最小二乘的TDOA/AOA混合算法[19]進(jìn)行了比較。

圖4 基站與移動臺位置示意圖

(1)在視距環(huán)境下，三種參數(shù)對均方根誤差(RMSE)的影響。

均方根誤差根據(jù)式(19)所示：

(19)

①基站個數(shù)對定位性能的影響，由圖5可看出，在誤差取30m，半徑取3000m，隨著基站個數(shù)由4個到9個的增加。各個算法的定位性能隨著基站的增加出現(xiàn)不同的變化情況，如圖5所示。

圖5 標(biāo)準(zhǔn)誤差與基站關(guān)系

圖5中，當(dāng)基站個數(shù)在4～6個時，IMPSO算法的曲線明顯低于另外兩種算法，定位性能最佳，混合算法次之;在7～9個基站時，定位性能的差距不大，總體平均值，IMPSO算法相對于Chan算法、TDOA/AOA算法，定位的精度和準(zhǔn)確度有明顯的提升；圖中的粒子群算法曲線的平穩(wěn)性體現(xiàn)出了算法具有更好的穩(wěn)定性。

②半徑對定位性能的影響，由圖6可看出，在基站取7個，測量誤差為30m的情況下，隨著半徑的不斷增加，定位誤差呈現(xiàn)上升趨勢。

圖6 標(biāo)準(zhǔn)誤差與半徑關(guān)系

圖6中可以看出，IMPSO算法的定位性能和可靠性相對于其他兩種定位算法，具有明顯的優(yōu)越性，這是由于IMPSO算法是對TDOA/AOA的函數(shù)式進(jìn)行尋優(yōu)，消除了一定的誤差，一定程度上減小了由半徑變化帶來的誤差，提高了定位的精度。

③測量誤差對定位性能的影響，由圖7可以看出，在半徑取3000m，基站取7個的情況下，測量誤差方差在30m～240m，測量誤差x=σAOA×c,c為光速，隨著測量誤差的增加，其他兩種算法的標(biāo)準(zhǔn)誤差也隨之增加。

圖7 標(biāo)準(zhǔn)誤差與測量誤差關(guān)系

圖7中，IMPSO算法相對于其他兩種算法，在誤差小于120 m之前基本不受誤差的影響，這是由于IMPSO算法能夠有效的抑制誤差對定位精度的影響，使得定位性能得到明顯的提升。其他兩種方法，受誤差影響較大，由于隨著測量誤差的增加，最終的測量結(jié)果出現(xiàn)偏差的概率也就越大，算法表現(xiàn)出來的性能也就越不穩(wěn)定。

(2)在視距環(huán)境下，三種參數(shù)對均方誤差(MSE)的影響

均方誤差根據(jù)式(20)所示：

(20)

式(20)中所示，x(l)式x的第l次的估計(jì)位置值。

①基站個數(shù)與均方誤差的關(guān)系，如圖8所示。

圖8 基站與均方誤差關(guān)系

如圖8所示，基站在6個之前，本文提出的IMPSO算法的定位精度明顯高于其他兩種算法，在基站數(shù)大于6個數(shù)之后，精度受基站數(shù)量的影響不大，原因是修正了BS與MS之間的TDOA測量值，此時是AOA的測量偏差對定位性能起作用。

②半徑與均方誤差的關(guān)系，如圖9所示。

圖9 半徑與均方誤差關(guān)系

如圖9所示，本文提出的IMPSO算法定位性能優(yōu)于其他兩種算法，這是由于粒子群算法中經(jīng)過變異操作和改進(jìn)慣性權(quán)重后，避免了非線性在運(yùn)算過程中線性化，繼而導(dǎo)致算法陷入局部最優(yōu)解的問題，使得TDOA/AOA混合定位的定位性能得到了提高，所以將IMPSO算法用于TDOA/AOA混合定位中，能夠克服非線性問題，有效提高定位精度。

③測量誤差與均方誤差的關(guān)系，如圖10所示。

圖10 測量誤差與均方誤差關(guān)系

如圖10所示，隨著測量誤差的增加，均方誤差也隨之遞增，IMPSO算法在平均均方誤差中，表現(xiàn)出了良好的定位性能，這是由于IMPSO算法降低了測量誤差對定位的影響，使得定位更加精確。

(3)三種算法的三維對比關(guān)系，如圖11所示。

圖11 三維對比圖

如圖11中所示，當(dāng)半徑超過1500m時，本文提出的IMPSO算法比另外兩種算法取得更好的定位性能，定位精度得到了明顯的提升。

5 結(jié)論

文中對IMPSO應(yīng)用于TDOA/AOA混合定位算法中做了研究，通過運(yùn)用IMPSO算法，將TDOA/AOA混合定位的函數(shù)作為適應(yīng)度函數(shù)進(jìn)行尋優(yōu)，找到最佳適應(yīng)度對應(yīng)的坐標(biāo)點(diǎn)，有效的解決了TDOA/AOA混合定位中受誤差影響較大，以及非線性優(yōu)化的問題。從分析和仿真結(jié)果可以看出，相對于傳統(tǒng)的Chan算法以及TDOA/AOA混合算法，在不同的小區(qū)半徑和測量誤差的情況下，表現(xiàn)出更高的定位精度和可靠性，具有速度快，性能穩(wěn)定的優(yōu)點(diǎn)。因此，利用IMPSO對TDOA/AOA混合定位算法進(jìn)行改進(jìn)，對目標(biāo)進(jìn)行定位，能夠有效地獲得目標(biāo)的位置。同時，用IMPSO算法解決其他定位問題也具有一定的研究價(jià)值。