一種線性校正到達時間差定位算法

朱國輝馮大政 周 延 趙海霞

(西安電子科技大學雷達信號處理國家重點實驗室 西安 710071)

一種線性校正到達時間差定位算法

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

(西安電子科技大學雷達信號處理國家重點實驗室 西安 710071)

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

信號處理；無源定位；到達時間差；加權最小二乘估計；線性校正；恒加速度

1 引言

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

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

2 多站TDOA定位模型

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

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

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

3 線性校正TDOA定位算法

3.1 加權最小二乘估計

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

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

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

3.2 線性校正TDOA定位算法

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

進行一階泰勒級數展開可得

式中

對式(12)進行加權最小二乘求解可得

則校正后的輻射源位置為

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

3.3 性能分析

克拉美羅界是所有無偏估計所能達到的下界，由文獻[11]可知基于TDOA定位問題的克拉美羅界為

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

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

3.4 復雜度分析

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

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

4.1 運動輻射源參數矢量加權最小二乘估計

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

kK =…,1,2,,

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

式(28)的加權最小二乘估計為

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

4.2 性能分析

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

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

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

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

5 仿真實驗

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

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

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

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

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

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

接下來利用多個時刻TDOA測量值對運動輻射源參數矢量進行估計。

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

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

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

6 結束語

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

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

[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] 李萬春, 魏平, 肖先賜. 一種新的穩健的TDOA定位算法[J].電子與信息學報, 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] 段凱宇, 張力軍. 基于到達角Kalman濾波的TDOA/AOA定位算法[J]. 電子與信息學報, 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]. 電子學報, 2006, 34(9): 1595-1599.

朱國輝： 男，1987年生，博士生，研究方向為無源定位技術.

馮大政： 男，1959年生，教授，博士生導師，研究方向為盲信號處理、雷達信號處理、無源定位和陣列信號處理等.

周 延： 男，1987年生，博士生，研究方向為空時自適應信號處理.

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改回

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

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