基于兩步最小二乘定位的偏差改進算法

張杰， 蔣建中， 郭軍利 信息工程大學 信息系統工程學院， 鄭州 450002

基于兩步最小二乘定位的偏差改進算法

張杰*， 蔣建中， 郭軍利 信息工程大學 信息系統工程學院， 鄭州 450002

針對傳統最小二乘(LS)定位算法在噪聲較大時會出現有偏估計的問題。首先詳細推導了傳統兩步最小二乘算法在時差角度聯合定位場景下的理論偏差，給出了出現偏差的原因；其次對誤差均值加入二次約束條件，提出一種基于時差角度聯合定位的改進算法，并詳細推導新算法的理論偏差以及均方誤差。相比于其他加限制條件的方法，新算法能有效降低估計偏差，另外由于其不需要進行特征值分解且能得到閉式解，計算復雜度較小。仿真結果表明，新算法在保持原有均方誤差(MSE)的前提下能顯著降低估計偏差，其定位偏差與最大似然估計器相當。

多站無源定位； 有偏估計； 加權最小二乘； 時差角度聯合定位； 均方誤差

近年來，無源定位技術受到人們越來越多的關注。目前多站無源定位體制主要有測角交叉定位[1]，時差定位[2]以及綜合利用多種觀測信息的復合體制定位[3]。角度以及時差信息是無源定位中最基本的觀測量，測角定位設備簡單，然而當觀測距離較遠時不易實現精確定位；時差定位在現有的觀測條件下具有較高的定位精度。時差角度聯合定位能利用更多的觀測信息，有助于提高定位精度，因此本文主要研究到達時間差(TDOA)以及角度測量(AOA)結合的多站無源定位問題。

目前定位解算方法主要包括搜索法[4]、迭代算法[5-6]以及解析算法[7-8]等，相對于其他兩種算法，解析算法保證了收斂性，實時性較好。當觀測誤差較小時，均方誤差能逼近克拉美-羅下限(Cramér-Rao Lower Bound， CRLB)，故而許多學者致力于研究解析算法。Chan和Ho提出了基于兩步加權最小二乘(Weighted Least Square, WLS)的定位方法[2]，從理論和仿真兩個角度證明當噪聲較小且服從高斯分布時，其均方誤差能達到CRLB。由于性能優越，Chan算法得到了廣泛應用，并衍生出許多針對其他定位場景的無源定位算法，例如鄧平和Cheung等分別提出了基于TDOA以及AOA信息的混合定位算法[9-10]，Ho和Xu提出了基于時差以及頻差信息的兩步定位方法[11]。然而任何將非線性方程近似為線性方程的算法均存在誤差，因此文獻[2]提出的兩步最小二乘算法是有偏估計，當信噪比較高或觀測站位置排列很好時，估計偏差較小，均方誤差主要由估計方差產生；當信噪比較低或觀測站位置較為惡劣時，文獻[2]的估計偏差十分明顯；另外，在跟蹤過程中常常對不同時刻觀測到的數據取平均值來提高估計精度[12]，然而求均值只能降低估計方差并不能降低估計偏差。為了降低估計偏差，文獻[13]在求解最小二乘方程時加入二次約束條件，但是其需要進行迭代計算，計算量較大；文獻[14-15]利用總體最小二乘算法進行定位，其減少估計偏差的同時卻增大了估計方差；文獻[16]對基于TDOA信息的兩步最小二乘算法進行了詳細的偏差分析，提出了一種能有效消除估計偏差的改進算法。

本文借鑒文獻[16]的分析思路，針對TDOA-AOA結合的定位場景，詳細分析了兩步最小二乘定位的理論偏差。由文獻[16]可知，偏差主要由于以下兩個原因：① 最小二乘變量之間存在噪聲相關性；② 觀測量與輻射源位置之間存在非線性特性。針對上述原因對誤差均值加入限制條件，雖然利用限制條件降低估計偏差是比較常規的方法，但其通常需要迭代計算，而新算法能得到閉式解且不需要特征值分解，計算量較小。文章對新算法的性能進行詳細推導，從理論上證明新算法在不增加均方誤差的同時能有效降低估計偏差。

1 定位模型

(u-s1)T(u-s1)=-2xi,1x-

2yi,1y+Ki-K1

i=2,3,…,M

(1)

(y-yi)/(x-xi)i=1,2,…,M

(2)

步驟1

(3)

式中:

Q=

步驟2

(4)

式中：

其中：⊙表示向量的Schur積，最終定位結果為

(5)

2 傳統算法的偏差分析

本節將推導TDOA-AOA結合的傳統兩步WLS算法的理論偏差，保留噪聲的二次項，下面依次對兩個步驟的偏差進行分析。

(6)

式中：nTDOA和nAOA分別為時差及角度信息的觀測誤差。對式(6)求期望即可得到φ1的偏差，然而由于G1以及h1中的數據含有相同的觀測噪聲，因此Δφ1的期望并不容易求得，為了突出重點，下面直接給出Δφ1的期望，具體步驟詳見附錄A。

(7)

式中:

其中：H1(i,:)、H1(:,j)分別為矩陣H1的第i行、第j列；qTDOA、qAOA分別為TDOA以及AOA觀測方差組成的列向量。式(7)的第1項來自于h1中噪聲的二次項，其余各項由于h1、G1中所含噪聲具有相關性，因此減小變量之間的噪聲相關性是降低偏差的關鍵。

(8)

由式(8)可知，φ1的偏差以及方差導致φ2出現偏差。與步驟1不同，步驟2中G2的元素均為常數，不存在誤差，然而由式(4)可知W2的求解需要用到步驟1的估計值φ1，因此求解φ2的偏差并不容易，為了突出重點，下面直接給出Δφ2的期望，具體步驟詳見附錄B。

E(Δφ2)=H2(c1+B2E(Δφ1)+

(9)

對Δu求期望可得

(10)

式中：cu為一列向量，其值由u的均方誤差矩陣Cu的對角線元素組成，由文獻[2]可知

綜上所述，文獻[9]的偏差可由式(7)、式(9)和式(10)求得。

3 算法改進

B1n=Avo

(11)

v的估計值應使誤差ε=vTATW1Av達到最小。將矩陣A表示為真實值加噪聲的形式，即

(12)

式中：

(13)

對式(13)求期望可得v的均值，由于ΔA的均值為零，可得

(14)

minvTATW1Av

s.t.vTΩv=k

(15)

ATW1Av=λΩv

(16)

(17)

4 改進算法的性能分析

(18)

(19)

(20)

(21)

(22)

保留噪聲的二次項，對式(21)化簡可得

(23)

當噪聲較小時，根據紐曼級數[19]

H1[E11nE12nE13n]H1B1n

(24)

(25)

5 仿真實驗

本文借鑒文獻[15]的仿真場景：假設有9個觀測站，位于原點的主觀測站計算TDOA數據，其他觀測站的坐標為

si=[1 000cos(2π(i-1)/8)

1 000sin(2π(i-1)/8)]Tm

i=2,3,…,9

圖1中實線和虛線分別表示傳統兩步WLS算法以及本文所提算法的理論偏差，由圖1可以看出：

1) 當σd≤20dB時，WLS算法以及本文算法的仿真值均能很好地與理論值吻合，由此證明第3節以及第5節理論偏差分析的正確性。

2)CWLS算法的估計偏差相比于WLS算法只有少許下降，這說明當觀測站位置排列較好時CWLS算法抑制偏差的效果并不明顯。

3)TLS算法由于考慮了最小二乘變量之間的噪聲相關性，能有效降低估計偏差，相比WLS算法偏差降低約7dB，但由圖2可知其RMSE無法達到CRLB。

4) 本文所提算法能大幅降低定位偏差，其精度與最大似然算法一致，相比傳統WLS算法偏差降低約20dB，與TLS算法相比也有較大的改進。

圖1 各算法的偏差隨噪聲的變化

Fig.1 Bias of the algorithms changing with noise

圖2 各算法的均方根誤差隨噪聲的變化

Fig.2 RMSE of the algorithms changing with noise

5) 當σd>20dB時，傳統WLS算法以及本文算法均出現門限效應，偏差的仿真值略低于理論值，這是因為隨著噪聲的增大，只考慮噪聲的二次項已經無法準確描述算法的理論偏差，因此算法的仿真值與理論值并不吻合。

6) 當25dB≤σd≤30dB時，TLS算法非但不能減小偏差，其偏差反而高于傳統WLS算法，當σd=35dB時，TLS算法的定位偏差略低于傳統WLS算法，說明當噪聲較大時，TLS算法并不穩定。

7) 當σd≤30dB時，最大似然算法由于利用輻射源的真實值作為高斯-牛頓迭代的初始值，因此依然保持穩定的定位效果，然而當σd=35dB時，由于TDOA以及AOA的噪聲較大，導致算法發散，偏差大幅上升。

由圖2可以看出：

1) 算法的RMSE隨噪聲的升高而升高，當σd≤20dB時，TLS算法的RMSE比CRLB高約3dB，而其他算法的RMSE均能達到CRLB，說明本文算法能保持原有均方根誤差的前提下有效降低估計偏差。

2) 當σd>20dB時，TLS算法的RMSE大幅增大，說明當噪聲較大時，TLS算法失效。

3) 當σd=20dB時，傳統WLS算法以及CWLS算法已經出現門限效應，而此時本文算法以及ML算法的RMSE依然能達到CRLB，說明本文算法對于噪聲具有一定的魯棒性，當σd=35dB時，本文算法的RMSE大幅增大，其RMSE高于傳統WLS算法，如何在強噪聲條件下提高本文所提算法的性能是下一步研究的方向。

下面考慮各算法的偏差以及均方誤差隨觀測距離的變化情況。假設噪聲為20dB，觀測站呈圓形排列，坐標與上文保持一致，令輻射源到位于原點的主觀測站的距離為d，觀測站半徑r=1 000m，令觀測距離L=d/r從0.5到10變化，其他實驗條件同上。圖3和圖4分別為各算法的偏差以及RMSE隨觀測距離的變化曲線。

圖3 各算法的偏差隨L的變化

Fig.3 Bias of the algorithms changing with L

圖4 各算法的均方根誤差隨L的變化

Fig.4 RMSE of the algorithms changing with L

觀察圖3和圖4依然可以得到類似于圖1和圖2的結論，這里不再贅述。另外，由圖3和圖4可知隨著輻射源逐漸遠離觀測站，偏差以及RMSE均逐漸增大。

由圖3可知，當L≤1時，TLS算法的估計偏差反而高于傳統WLS以及CWLS算法，說明當輻射源位于觀測站組成的圓內或者十分接近觀測站時，TLS算法的優勢無法體現，而本文所提算法的仿真值雖然略高于理論值以及最大似然估計器，但仍低于其他算法，這是由于式(7)～式(10)需要用到輻射源的真實位置，而實際中輻射源的位置并不知道，需要利用估計值代替真實值，當輻射源位于觀測站內或接近觀測站時，上述近似容易出現誤差[2,11]。當輻射源逐漸遠離觀測站(L≥2)，上述誤差迅速減小，相比于傳統WLS算法，新算法能大幅降低估計偏差。

由圖4可知無論輻射源是否接近觀測站，TLS算法的RMSE均高于CRLB，而其他算法的RMSE均能達到CRLB，這也與圖2保持一致。圖1～圖4給出了算法性能較好時的仿真效果，由文獻[20]可知，當輻射源位于觀測站內部或十分接近觀測站時，新算法抑制偏差的能力將大大下降，偏差大約只能減小7dB。

圖5 各算法的偏差隨AOA噪聲的變化

Fig.5 Bias of the algorithms changing with AOA noise

圖6 各算法的均方根誤差隨AOA噪聲的變化

Fig.6 RMSE of the algorithms changing with AOA noise

由圖5可以看出：

1) 由于TDOA的觀測誤差固定，因此TDOA定位算法的仿真值均為定值。當ratio≤3×10-6時，TDOA-AOA聯合定位算法的定位偏差低于TDOA定位算法，然而當ratio>3×10-6時，TDOA定位算法的偏差小于聯合定位算法，這說明當AOA噪聲較大時，角度信息已經失效，其非但不能給定位精度帶來任何增益，反而會增大定位偏差。

2) 隨著AOA噪聲的不斷上升，各算法的偏差均逐漸增大，但其上升的趨勢逐漸變緩，這是因為各算法的權值與噪聲協方差矩陣成反比，觀測值的噪聲越大其對定位結果的貢獻越小。

3) 無論ratio如何變化，本文算法的定位偏差始終低于TDOA定位算法，說明當噪聲較大時，本文所提算法依然能有效抑制定位偏差。其他結論與前面一致，這里不再贅述。

由圖6可以看出，各算法的RMSE均隨AOA噪聲的增大而不斷上升，當ratio≤3×10-6時，除了TDOA定位算法外，各算法的RMSE均達到CRLB，當ratio>3×10-6時，TDOA-AOA聯合定位算法以及CWLS算法均出現門限效應，其RMSE逐漸偏離CRLB。當ratio=3×10-5時，TDOA-AOA聯合定位算法的RMSE與TDOA定位算法重合，說明此時角度信息已經失效，而本文算法以及ML算法的RMSE依然能達到CRLB，說明本文所提算法對于AOA誤差具有較強的魯棒性。

綜上所述，當輻射源距離觀測站較遠時，本文所提算法在不增加RMSE的同時能大幅降低估計偏差，另外其對AOA觀測誤差具有較強的魯棒性。

6 結 論

1) 本文詳細推導了基于TDOA-AOA信息的傳統兩步WLS算法的理論偏差，通過分析發現偏差主要由于步驟1中最小二乘變量之間存在噪聲相關性，針對這一問題，在步驟一對誤差均值加入二次約束條件，有效降低最終的估計偏差。新算法能大幅降低估計偏差，不需要特征值分解且能得到閉式解，有效降低了計算量。

2) 仿真結果表明，當輻射源距離觀測站較遠時，新算法在保持原有RMSE的同時能有效降低估計偏差，其精度與最大似然估計器一致。今后可研究如何在強噪聲條件下提高新算法的性能。

[1] 王鼎, 張莉, 吳瑛. 基于角度信息的結構總體最小二乘無源定位算法[J]. 中國科學F輯： 信息科學, 2009, 39(6): 663-672. WANG D, ZHANG L, WU Y. Structured total least squares algorithm for passive location based on bearing only measurements[J]. Science in China F: Information Sciences, 2009, 39(6): 663-672 (in Chinese).

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

[3] HAO B J, LI Z, SI J B, et al. Joint source localization and sensor refinement using time differences of arrival and frequency differences of arrival[J]. IET Signal Processing, 2014, 8(6): 588-600.

[4] WEISS A J. Direct geolocation of wideband emitters based on delay and Doppler[J]. IEEE Transactions on Signal Processing, 2011, 59(6): 2513-2521.

[5] 王鼎. 觀測站位置狀態擾動下Taylor級數迭代定位方法及性能分析[J]. 宇航學報, 2013, 34(12): 1634-1643. WANG D. The Taylor-series location and its performance analysis with erroneous observer positions[J]. Journal of Astronautics, 2013, 34(12): 1634-1643 (in Chinese).

[6] 張杰, 蔣建中, 郭軍利. 校正源狀態擾動下Taylor級數迭代定位方法[J]. 應用科學學報, 2015, 33(3): 274-289. ZHANG J, JIANG J Z, GUO J L. Source localization using Taylor-series iteration with erroneous calibration emitters state[J]. Journal of Applied Science, 2015, 33(3): 274-289 (in Chinese).

[7] SUN M, YANG L, HO K C. Efficient joint source and sensor localization in closed-form[J]. IEEE Signal Processing Letters, 2012, 19(7): 399-402.

[8] HO K C, SUN M. Passive source localization using time differences of arrival and gain ratios of arrival[J]. IEEE Transactions on Signal Processing, 2008, 56(2): 464-477.

[9] 鄧平, 李莉, 范平志. 一種TDOA/AOA混合定位算法及其性能分析[J]. 電波科學學報, 2002, 17(6): 633-636. DENG P, LI L, Fan P Z. A hybrid TDOA/AOA location algorithm and its performance analysis[J]. Chinese Journal of Radio Science, 2002, 17(6): 633-636 (in Chinese).

[10] CHEUNG K W, SO H C, MA W K, et al. A constrained least squares approach to mobile positioning: Algorithms and optimality[J]. EURASIP Journal on Applied Signal Processing, 2006, 2006(5): 1-23.

[11] HO K C, XU W W. An accurate algebraic solution for moving source location using TDOA and FDOA measurements[J]. IEEE Transactions on Signal Processing, 2004, 52(9): 2453-2463.

[12] RUI L Y, HO K C. Bias analysis of source localization using the maximum likelihood estimator[C]//Proceeding of the 2012 IEEE International Conference on Acoustics, Speech and Signal Processing. Piscataway, NJ: IEEE Press, 2012: 2605-2608.

[13] YU H G, HUANG G M, GAO J, et al. An efficient constrained weighted least squares algorithm for moving source location using TDOA and FDOA measurements[J]. IEEE Transactions on Wireless Communication, 2012, 11(1): 44-47.

[14] 王鼎, 吳瑛, 田建春. 基于總體最小二乘算法的多站無源定位[J]. 信號處理, 2007, 23(4): 611-614. WANG D, WU Y, TIAN J C. Multi-station passive location based on TLS algorithm[J]. Signal Processing, 2007, 23(4): 611-614 (in Chinese).

[15] BARTON R J, RAO D. Performance capabilities of long-range UWB-IR TDOA localization systems[J]. ESRASIP Journal on Advances in Signal Processing, 2008, 2008(1): 1-17.

[16] HO K C. Bias reduction for an explicit solution of source localization using TDOA[J]. IEEE Transactions on Signal Processing, 2012, 60(5): 2101-2114.

[17] ANTONIOU A, LU W S. Practical optimization algorithms and engineering application[M]. New York: Springer, 2007: 287-290.

[18] REES E L. Graphical discussion of the roots of a quartic equation[J]. The American Mathematical Monthly, 1922, 29(2): 51-55.

[19] MOON T K, STIRLING W C. Mathematical methods and algorithms for signal processing[M]. Upper Saddle River, NJ: Prentice-Hall, 2000: 235.

[20] XU B, QI W D, LI W. Turbo-tswls: Enhanced two-step weighted least squares estimator for TDOA-based localization[J]. Electronics Letters, 2012, 48(25): 1597-1598.

張杰 男， 碩士研究生。主要研究方向： 無源定位。

Tel: 0371-81622197

E-mail: hpzj242411@163.com

蔣建中 男， 碩士， 教授。主要研究方向： 通信中的信號處理。

Tel: 0371-81622197

E-mail: jiang3721@sina.com

郭軍利 男， 碩士， 副教授。主要研究方向： 通信中的信號處理。

Tel: 0371-81622197

E-mail: gjl@163.com

附錄A

由于G1中含有觀測噪聲，因此

所以

(A1)

(A2)

將式(A1)和式(A2)代入Δφ1的表達式,可得

(A3)

由于

根據ΔG1的表達式可得

(A4)

(A5)

(A6)

式中：C2、D2、C3和D3如式(7)所示，將式(A4)～(A6)代入式(A3)并求期望，可得φ1的偏差如式(7)所示。

附錄B

(B1)

當觀測噪聲不大且輻射源距離觀測站較遠時，根據紐曼級數[18]有

代入W2可得

(B2)

將式(B2)代入式(8)并省略3次及3次以上的噪聲項，φ2的偏差為

(B3)

式中：H2和c1如式(9)所示；P3=I-G2H2，將ΔW2的表達式代入式(B3)可得

(B4)

利用式(A1)以及式(A3)可得

(B5)

式中:

H1(:,M:2M-1)BAOA

同理由式(B1)可得

(B6)

Received： 2015-01-30； Revised： 2015-04-10； Accepted： 2015-06-15； Published online： 2015-07-20 08:53

URL： www.cnki.net/kcms/detail/11.1929.V.20150720.0853.001.html

Foundation item： National Natural Science Foundation of China (61104036)

*Corresponding author. Tel.： 0371-81622197 E-mail: hpzj242411@163.com

Improved bias algorithm for localization using two-step least square

ZHANG Jie*, JIANG Jianzhong, GUO Junli

CollegeofInformationSystemEngineering,UniversityofInformationandEngineering,Zhengzhou450002,China

Bias of a source location estimate using classical least square (LS) algorithm is significant when the noise is large. This paper started by deriving the theoretical bias of the time-differences-of-arrival (TDOA) and angle-of-arrival (AOA) positioning which used the classical two-step LS algorithm and found the reason which caused the bias. Then the improved TDOA and AOA algorithm was proposed by adding the quadratic constraints to the expectation of the error. Compared to other methods with constraints, the novel algorithm can reduce the bias considerably. Furthermore, because the new algorithm does not require eigenvalue decomposition and can obtain the closed-form solution, it has little computation load. Simulation shows that the new method can reduce the bias significantly and obtain the original mean-square error (MSE). The improved algorithm is able to lower the bias to the same level as the maximum likelihood estimator.

multi-station passive localization; bias estimate; weighted least square; TDOA and AOA jointed localization; mean-square error

2015-01-30；退修日期：2015-04-10；錄用日期：2015-06-15； < class="emphasis_bold">網絡出版時間：

時間： 2015-07-20 08：53

www.cnki.net/kcms/detail/11.1929.V.20150720.0853.001.html

國家自然科學基金 (61104036)

.Tel.： 0371-81622197 E-mail: hpzj242411@163.com

張杰， 蔣建中， 郭軍利． 基于兩步最小二乘的偏差改進算法[J]． 航空學報, 2016, 37(2): 695-705. ZHANG J, JIANG J Z, GUO J L. Improved bias algorithm for localization using two-step least square[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(2): 695-705.

http://hkxb.buaa.edu.cn hkxb@buaa.edu.cn

10.7527/S1000-6893.2015.0182

V247.5； TN911.7

： A

： 1000-6893(2016)02-0695-11

*