一種線性校正到達(dá)時間差定位算法

朱國輝馮大政 周 延 趙海霞

(西安電子科技大學(xué)雷達(dá)信號處理國家重點(diǎn)實(shí)驗(yàn)室 西安 710071)

一種線性校正到達(dá)時間差定位算法

朱國輝*馮大政 周 延 趙海霞

(西安電子科技大學(xué)雷達(dá)信號處理國家重點(diǎn)實(shí)驗(yàn)室 西安 710071)

針對到達(dá)時間差(TDOA)定位中出現(xiàn)的非線性估計(jì)問題，該文提出一種線性校正TDOA定位算法。首先將高度非線性的TDOA定位方程組轉(zhuǎn)化為一組關(guān)于輻射源位置的偽線性方程，利用加權(quán)最小二乘(WLS)估計(jì)進(jìn)行初始求解；然后在此基礎(chǔ)上通過一階泰勒級數(shù)展開把偽線性方程組轉(zhuǎn)化為關(guān)于估計(jì)偏差的線性加權(quán)最小二乘問題并進(jìn)行求解，分析了所提算法在測量誤差較小時的有效性。最后提出了一種基于加權(quán)最小二乘估計(jì)的恒加速度運(yùn)動輻射源的定位方法，相應(yīng)的估計(jì)性能在測量誤差較小時也接近克拉美羅界(CRLB)。計(jì)算機(jī)仿真結(jié)果驗(yàn)證了該算法的有效性。

信號處理；無源定位；到達(dá)時間差；加權(quán)最小二乘估計(jì)；線性校正；恒加速度

1 引言

無源定位技術(shù)在跟蹤[1]、導(dǎo)航[2]、無線通信和傳感器網(wǎng)絡(luò)[3]等領(lǐng)域有著廣泛的應(yīng)用。就具體的定位參數(shù)信息而言，主要包括到達(dá)時間(Time Of Arrival, TOA)、到達(dá)時間差(Time Difference Of Arrival, TDOA)、到達(dá)角(Angle Of Arrival, AOA)和到達(dá)頻差(Frequency Difference Of Arrival, FDOA)等[4- 6]；其中基于多站TDOA信息的定位技術(shù)對接收系統(tǒng)的要求較低，具有定位成本低、精度較高[7]等優(yōu)點(diǎn)，因而受到越來越多的關(guān)注。

利用TDOA信息對輻射源進(jìn)行定位本質(zhì)上是一個非線性估計(jì)問題，可以利用迭代方法求解。目前常見的基于迭代求解的定位算法有泰勒級數(shù)法[8]和擬牛頓法[9]等，它們的收斂性依賴于初始值的選取和代價(jià)函數(shù)的非線性程度。當(dāng)初始值接近真實(shí)值時，算法能快速收斂；但是在代價(jià)函數(shù)高度非線性并且初始值選擇不好的情況下，容易落入到局部極小點(diǎn)，而且收斂性難以保證。基于封閉解的TDOA定位算法有球面相交(Spherical Intersection, SI) 法[10]、兩級加權(quán)最小二乘(Two-step Weighted Least Squares(WLS))法[11]、近似最大似然估計(jì)(Approximate Maximum Likelihood, AML)法[12]和多維尺度分析(MultiDimensional Scaling, MDS) 法[13]等；其中Two-step WLS法在第2級加權(quán)最小二乘估計(jì)時涉及到開方運(yùn)算，產(chǎn)生的定位結(jié)果具有模糊性 ，并且可能出現(xiàn)虛數(shù)解；而SI法和AML法將TDOA定位問題轉(zhuǎn)化為二次多項(xiàng)式求解問題，當(dāng)兩根均為正數(shù)或出現(xiàn)虛數(shù)解時，根的選取對定位精度有很大影響。MDS法在加權(quán)矩陣的求解過程中出現(xiàn)矩陣奇異的情況，加載因子的選取對定位結(jié)果影響較大。為此，本文提出了一種線性校正TDOA定位算法，該算法首先利用加權(quán)最小二乘估計(jì)對偽線性定位方程組進(jìn)行初始求解；然后將偽線性方程組轉(zhuǎn)化為關(guān)于位置估計(jì)偏差的線性方程組進(jìn)行求解；同時，本文分析了算法在測量誤差較小時的有效性，并將所提方法應(yīng)用到恒加速度運(yùn)動輻射源的定位上。仿真結(jié)果表明該算法較傳統(tǒng)算法有較好的定位性能。

2 多站TDOA定位模型

假定3維空間中任意分布的M個接收站，第i個接收站的位置坐標(biāo)為si=[xi, yi, zi]T, i=1, 2,…,M，輻射源位置坐標(biāo)為u=[x, y, z]T。輻射源u到接收站si的距離為

不失一般性，本文選取s1作為參考接收站，不考慮非視距傳播的影響，根據(jù)TDOA定位原理可得式中~ti1為TDOA測量值，ti1表示信號從輻射源u到接收站si和參考接收站s1之間的真實(shí)時間差，c為真空中電磁波傳播速度，Δti1為TDOA測量誤差。

用c同時乘以式(2)兩端，可以得到距離差定位方程：式中ni 1=cΔti 1表示相應(yīng)的距離差測量誤差。令fi1(u)=ri-r1，將式(3)寫成矢量形式為

3 線性校正TDOA定位算法

3.1 加權(quán)最小二乘估計(jì)

由式(1)可知，距離差定位模型式(3)是關(guān)于輻射源位置u的高度非線性方程，將式(3)右端第2項(xiàng)r1移至左端，兩邊同時平方得

式(7)為關(guān)于φ的線性方程，對其進(jìn)行加權(quán)最小二乘求解可得

這個過程是在假設(shè)u與r1相互獨(dú)立的前提下進(jìn)行的，而事實(shí)上，它們受限于方程式(1)。

3.2 線性校正TDOA定位算法

由式(8)得到的輻射源位置?u只是一種粗估計(jì)，本文利用u和r1之間的關(guān)系，提出一種線性校正定位方法。考慮到實(shí)際值u與估計(jì)值?u之間存在偏差，不妨設(shè)此偏差為Δu，則實(shí)際位置矢量為=?-uu

進(jìn)行一階泰勒級數(shù)展開可得

式中

對式(12)進(jìn)行加權(quán)最小二乘求解可得

則校正后的輻射源位置為

下面求估計(jì)~u的偏差及協(xié)方差矩陣。將=Δ hGu +η和分別代入式(13)和式(14)可得

3.3 性能分析

克拉美羅界是所有無偏估計(jì)所能達(dá)到的下界，由文獻(xiàn)[11]可知基于TDOA定位問題的克拉美羅界為

根據(jù)G,B的定義可知矩陣-1B G的第i-1行，

根據(jù)式(9)可將Δu表示為測量誤差n21,n31,…,nM -1線性組合的形式，由文獻(xiàn)[15]可知在條件式(18)下有

3.4 復(fù)雜度分析

采用浮點(diǎn)運(yùn)算次數(shù)(floating-point operations, flops)作為算法復(fù)雜度的度量，1個flop表示一次加、減、乘、除或開方運(yùn)算。由文獻(xiàn)[16, 17]可知，對n×n維矩陣求逆需要(2n3-2n2+n)flops，對m×n維矩陣進(jìn)行奇異值分解需要(4m2n+22n2)flops。因此，兩級WLS法、MDS法和本文方法的復(fù)雜度分別約為9M2+33M+214,8M3+25M2+137和15M2+56M+94。可見，本文方法的復(fù)雜度介于兩級WLS法和MDS法之間，但從下面的仿真中可以看出本文方法的性能要明顯優(yōu)于這兩種方法；而泰勒級數(shù)法的復(fù)雜度約為(50M+19)l，其中l(wèi)表示迭代次數(shù)，其取值依賴于初始值的選取；一般情況下，與閉式解相比，迭代算法需要更多的運(yùn)算量。

4 基于多時刻TDOA測量值的運(yùn)動輻射源定位算法

4.1 運(yùn)動輻射源參數(shù)矢量加權(quán)最小二乘估計(jì)

常見的目標(biāo)運(yùn)動模型有勻速運(yùn)動模型、勻加速運(yùn)動模型以及變加速運(yùn)動模型。其中，勻加速運(yùn)動是一種典型的運(yùn)動形式，在水下目標(biāo)運(yùn)動分析、SAR成像及目標(biāo)跟蹤等領(lǐng)域[1,18,19]有著重要的應(yīng)用。基于此，本文提出一種利用加權(quán)最小二乘估計(jì)的恒加速度運(yùn)動輻射源的定位方法。不妨設(shè)運(yùn)動輻射源的初始位置、速度及加速度矢量分別為在第tk時刻，輻射源和接收站位置可表示為其中si,0和vi,0分別為第i個接收站的初始位置和速度，ai為加速度矢量。令時間矩陣為，則在t時刻輻射源和第i個接收站的位置k可分別表示為此時輻射源u到第i個接收站si, k的距離為相應(yīng)的距離差定位方程為其中0,1,,

kK =…,1,2,,

iM =… 。將式(25)寫成矢量形式可得

式(28)的加權(quán)最小二乘估計(jì)為

由于測量誤差n為零均值，E[Δp]=09× 1，即由式(29)所得估計(jì)p?在測量誤差較小時為無偏估計(jì)。由式(30)和W的定義可得估計(jì)p?的協(xié)方差矩陣為

4.2 性能分析

基于多時刻TDOA測量值的運(yùn)動輻射源定位問題的克拉美羅界為[11]

由3.3節(jié)中的式(22)及ρa(bǔ), b的定義可得

將式(35)和式(36)分別代入式(32)和式(34)可知

即由式(29)所得的估計(jì)?p近似為有效估計(jì)。

5 仿真實(shí)驗(yàn)

為了檢驗(yàn)文中方法對輻射源的定位性能，將該方法與兩級WLS法、泰勒級數(shù)法、MDS法及克拉美羅界的仿真結(jié)果進(jìn)行比較。采用估計(jì)均方根誤差和估計(jì)偏差對各算法的定位性能進(jìn)行衡量，其定義式分別為式中為第l次估計(jì)的輻射源初始位置、速度或加速度，L=104為蒙特卡羅仿真實(shí)驗(yàn)次數(shù)。表1 給出了5個接收站的初始位置si,0、速度vi,0及恒加速度ai信息。

表1 接收站初始位置、速度及恒加速度

假設(shè)各個時刻TDOA測量值服從均值為零、方差為σ2的高斯分布，則Qk滿足對角線元素為c2σ2，非對角線元素為0.5c2σ2[11]。首先利用k=0時刻的TDOA測量值對輻射源初始位置u0進(jìn)行估計(jì)。為了對比公平，用式(8)所得初始估計(jì)計(jì)算兩級WLS法和MDS法的權(quán)值及作為泰勒級數(shù)法的迭代初值。

仿真1 近場輻射源初始位置坐標(biāo)為u0=[285, 325,275]T，噪聲功率c2σ2從10-1變化到102.5。圖1(a)，圖1(b)分別為各算法隨噪聲功率變化時的輻射源位置估計(jì)偏差和均方根誤差的統(tǒng)計(jì)結(jié)果。從圖1(a)，圖1(b)可以看出，在噪聲功率較小時，各算法對輻射源位置的估計(jì)偏差均接近零，這說明了文中方法在噪聲功率較小時近似為無偏估計(jì)；另外，文中方法和兩級WLS法、泰勒級數(shù)法及MDS法的均方根誤差均接近克拉美羅界。隨著測量誤差的增加，各算法的估計(jì)偏差和均方根誤差都會有所增加，其中兩級WLS法最先偏離克拉美羅界，泰勒級數(shù)法的估計(jì)偏差和均方根誤差均出現(xiàn)急劇增加的現(xiàn)象；而文中方法的估計(jì)偏差和均方根誤差一直保持最小，具有較好的定位性能。

仿真2 遠(yuǎn)場輻射源的初始位置坐標(biāo)為u0= [3000,2500,2000]T，噪聲功率c2σ2從10-4變化到100。圖2(a)，圖2(b)分別給出了各算法對遠(yuǎn)場輻射源位置估計(jì)隨噪聲功率變化的估計(jì)偏差和均方根誤差的統(tǒng)計(jì)結(jié)果。從圖2(a)，圖2(b)可以得出與仿真1中類似的結(jié)論，在噪聲功率較小時，各算法對遠(yuǎn)場輻射源位置的估計(jì)偏差均較小，近似為無偏估計(jì)；幾種方法的均方根誤差都能夠很好的達(dá)到克拉美羅界。隨著噪聲功率的增加，各算法的估計(jì)偏差和均方根誤差均有所增加，而文中方法的估計(jì)偏差和均方根誤差一直保持最小。

圖1 各算法對近場輻射源位置的定位性能示意圖

接下來利用多個時刻TDOA測量值對運(yùn)動輻射源參數(shù)矢量進(jìn)行估計(jì)。

仿真3 設(shè)運(yùn)動輻射源的初始位置、速度及加速度分別為u0=[600,650,550]T, v0=[-200,150, 400]T,a=[30,20,-20]T。將式(29)所得結(jié)果作為泰勒級數(shù)法的迭代初始值，噪聲功率c2σ2從10-2變化到100.8，圖3(a)，圖3(b)和圖3(c)分別給出了文中方法與泰勒級數(shù)法對運(yùn)動輻射源參數(shù)矢量估計(jì)隨噪聲功率變化的均方根誤差的統(tǒng)計(jì)結(jié)果。可以看出，K=5時的克拉美羅界要明顯低于K=2時，這是因?yàn)樵贙=5時具有更多能利用的TDOA測量信息。文中方法與泰勒級數(shù)法在噪聲功率較小時均接近克拉美羅界，這也驗(yàn)證了4.2節(jié)中關(guān)于所得輻射源參數(shù)矢量估計(jì)的協(xié)方差矩陣近似等于克拉美羅界的結(jié)論。隨著噪聲功率的增加，泰勒級數(shù)法的均方根誤差在兩種情況下均出現(xiàn)急劇增加的現(xiàn)象；而文中方法的均方根誤差一直接近克拉美羅界，具有較好的定位性能。

圖3 本文方法與泰勒級數(shù)法對運(yùn)動輻射源的定位性能示意圖

MDS法在求解過程中采用奇異值分解技術(shù)，并將最小奇異值作為對角加載因子，一方面會增加運(yùn)算量，另一方面加載量的大小會對定位精度產(chǎn)生影響[6]。兩級WLS法在第2步求解過程中利用u與r1之間的關(guān)系對初始估計(jì)u?進(jìn)行優(yōu)化，同時忽略了Δu和Δr1的高階項(xiàng)，并且由于涉及到開方運(yùn)算，會產(chǎn)生模糊解，甚至產(chǎn)生復(fù)數(shù)解；而本文方法對偽線性方程組進(jìn)行線性化，進(jìn)而求取偏差Δu?對估計(jì)u?進(jìn)行校正。線性化過程中只忽略了Δu的高階項(xiàng)，不涉及開方運(yùn)算，因此不會產(chǎn)生模糊解及復(fù)數(shù)解，這也是本文方法性能優(yōu)于兩級WLS法的主要原因。從仿真實(shí)驗(yàn)也可以看出，本文方法要明顯優(yōu)于兩級WLS法。由于TDOA定位問題高度非線性，泰勒級數(shù)法很容易出現(xiàn)發(fā)散或者局部收斂的現(xiàn)象，這在仿真實(shí)驗(yàn)中也得到了驗(yàn)證。

6 結(jié)束語

針對傳統(tǒng)TDOA定位中出現(xiàn)的非線性參數(shù)估計(jì)問題，提出了一種線性校正TDOA定位算法。通過引入中間變量將高度非線性定位方程轉(zhuǎn)化為關(guān)于輻射源位置的偽線性方程，并進(jìn)行加權(quán)最小二乘求解；然后在此基礎(chǔ)上把偽線性方程組轉(zhuǎn)化為關(guān)于輻射源位置估計(jì)偏差的線性方程進(jìn)行求解并對初始估計(jì)進(jìn)行線性校正。本文分析了文中方法在測量誤差較小時對輻射源位置的估計(jì)近似為有效估計(jì)。最后，提出了一種基于加權(quán)最小二乘估計(jì)的恒加速度運(yùn)動輻射源的定位算法。實(shí)驗(yàn)結(jié)果表明所提方法具有較好的定位性能。

聯(lián)合多種量測值進(jìn)行定位能夠提高定位精度，目前的聯(lián)合定位場景如TDOA/FDOA及TDOA/ AOA等場景[3,6]受到廣泛關(guān)注，本文方法的線性校正思想同樣可以應(yīng)用到這些定位場景。下一步將以本文結(jié)論為基礎(chǔ)，針對接收站位置存在誤差的情況，深入研究適用于接收站位置誤差情況下的穩(wěn)健定位方法。

[1] Dogancay K and Sakhtsari A H. Target tracking by time difference of arrival using recursive smoothing[J]. Signal Processing, 2005, 85(4): 667-679.

[2] Zhang H Q and Zhang Y G. A robust algorithm for multiple disjoint moving sources localization with erroneous sensor locations[J]. Journal of Communications, 2013, 8(6): 345-350.

[3] Gholami M R, Gezici S, and Strom E G. Improved position estimation using hybrid TW-TOA and TDOA in cooperative networks[J]. IEEE Transactions on Signal Processing, 2012, 60(7): 3770-3785.

[4] Huang J, Xue Y B, and Yang L. An efficient closed-form solution for joint synchronization and localization using TOA[J]. Future Generation Computer Systems, 2013, 29(3): 776-781.

[5] Chan Y T, So H C, Lee B H, et al.. Angle of arrival localization of an emitter from air platforms[C]. Proceedings of the 26th Annual IEEE Canadian Conference of Electrical and Computer Engineering, Regina, Canada, 2013: 1-5.

[6] Wang G, Li Y M, and Ansari N. A semidefinite relaxation method for source localization using TDOA and FDOA measurements[J]. IEEE Transactions on Vehicular Technology, 2013, 62(2): 853-862.

[7] 李萬春, 魏平, 肖先賜. 一種新的穩(wěn)健的TDOA定位算法[J].電子與信息學(xué)報(bào), 2006, 28(11): 2019-2021.

[8] Fard H T, Atashbar M, Norouzi Y, et al.. Multireference TDOA-based source localization[J]. Turkish Journal of Electrical Engineer & Computer Sciences, 2013, 21(11): 1920-1929.

[9] Hao B and Li Z. BFGS quasi-Newton location algorithm using TDOAs and GROAs[J]. Journal of Systems Engineering and Electronics, 2013, 24(3): 341-348.

[10] Smith J O and Abel J S. Closed-form least-squares source location estimation from range-difference measurements [J]. IEEE Transactions on Acoustics, Speech, and Signal Processing, 1987, 35(12): 1661-1669.

[11] Y Chan T and Ho K C. A simple and efficient estimator for hyperbolic location[J]. IEEE Transactions on Signal Processing, 1994, 42(8): 1905-1915.

[12] Chan Y T, Hang H Y C, and Ching P C. Exact and approximate maximum likelihood localization algorithms[J]. IEEE Transactions on Vehicular Technology, 2006, 55(1): 10-16.

[13] Wei H W, Peng R, Wan Q, et al.. Multidimensional scaling analysis for passive moving target localization with TDOA and FDOA measurements[J]. IEEE Transactions on Signal Processing, 2010, 58(3): 1677-1688.

[14] 段凱宇, 張力軍. 基于到達(dá)角Kalman濾波的TDOA/AOA定位算法[J]. 電子與信息學(xué)報(bào), 2006, 28(9): 1710-1713.

[15] Yang L and Ho K C. An approximately efficient TDOA localization algorithm in closed-form for locating multiple disjoint sources with erroneous sensor positions[J]. IEEE Transactions on Signal Processing, 2009, 57(12): 4598-4615. [16] Chan F K W, So H C, and Ma W K. A novel subspace approach for cooperative localization in wireless sensor networks using range measurements[J]. IEEE Transactions on Signal Processing, 2009, 57(1): 260-269.

[17] Meyer C D. Matrix analysis and applied linear algebra [M]. Philadelphia: Siam, 2000: 119-120.

[18] Zhang Y J and Xu G Z. Bearings-only target motion analysis via instrumental variable estimation[J]. IEEE Transactions on Signal Processing, 2010, 58(11): 5523-5533.

[19] 孫兵, 周蔭清, 陳杰, 等. 基于恒加速度模型的斜視SAR成像CA-ECS算法[J]. 電子學(xué)報(bào), 2006, 34(9): 1595-1599.

朱國輝： 男，1987年生，博士生，研究方向?yàn)闊o源定位技術(shù).

馮大政： 男，1959年生，教授，博士生導(dǎo)師，研究方向?yàn)槊ば盘柼幚怼⒗走_(dá)信號處理、無源定位和陣列信號處理等.

周 延： 男，1987年生，博士生，研究方向?yàn)榭諘r自適應(yīng)信號處理.

A Linear-correction Based on Time Difference of Arrival Localization Algorithm

Zhu Guo-hui Feng Da-zheng Zhou Yan Zhao Hai-xia
(National Key Laboratory of Radar Signal Processing, Xidian University, Xi’an 710071, China)

A novel Time Differences Of Arrival (TDOA) localization algorithm based on linear-correction is proposed to address the nonlinear problem of TDOA positioning. Firstly, the proposed algorithm reformulates the highly nonlinear TDOA equations into a set of pseudo-linear ones and the Weighted Least Squares (WLS) estimator is used to obtain the initial emitter position estimation. Then a linear weighted least squares problem with respect to the estimation bias is formulated through utilizing first-order Taylor-series expansion to the pseudo-linear equations. The effectiveness of the proposed method is theoretically analyzed under small noise postulation. Finally, the extension to the general case of moving emitter with constant acceleration localization scenario is also presented and the corresponding estimation accuracy can achieve the Cramer-Rao Lower Bound (CRLB) as well. Computer simulation results demonstrate the effectiveness of the proposed algorithm.

Signal processing; Pssive location; Time Difference Of Arrival (TDOA); Weighted Least Squares (WLS) estimates; Linear-correction; Constant acceleration

TN971

A

1009-5896(2015)01-0085-06

10.11999/JEIT140313

2014-03-10收到，2014-06-13改回

國家自然科學(xué)基金(61271293)資助課題

*通信作者：朱國輝 zhugh@stu.xidian.edu.cn