基于两步最小二乘定位的偏差改进算法

张杰， 蒋建中， 郭军利 信息工程大学 信息系统工程学院， 郑州 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

*