存在基站誤差的穩健時差定位算法

房嘉奇, 馮大政, 李　進

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

?

存在基站誤差的穩健時差定位算法

房嘉奇, 馮大政, 李進

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

摘要：針對存在基站誤差的目標無源定位問題,提出了一種基于修正牛頓算法的時差定位技術。眾所周知,牛頓法對初值要求較高,較差初值會導致迭代發散,而且基站位置誤差也會導致牛頓算法Hessian矩陣維數擴大和目標函數的緩慢下降,使運算量變大。該算法利用最大似然方法確定目標函數,運用牛頓法對目標位置進行迭代求解,對于計算過程中可能出現的病態Hessian矩陣,引入正則化理論修正病態的Hessian矩陣,使保證迭代收斂,同時簡化算法降低Hessian矩陣的維數并且加速目標函數的下降趨勢,使目標位置解脫離局部最小值,算法能夠穩健高效的運行。實驗結果表明:相對于傳統牛頓法,此算法在初始值的選取上具有穩健性,對誤差選取較大的初始值,仍能夠保證算法的收斂性,同時加速了收斂速度,降低了計算量;相對于現有閉合式定位方法,此算法在噪聲較大時具有較好的定位精度。

關鍵詞：時差定位; 基站誤差; Hessian矩陣; 正則化算法; 克拉美羅界

0引言

對未知發射源的無源定位問題,由于其在導航、跟蹤監視、移動通信、無線傳感器網絡等方面的廣泛應用,一直都是信號處理領域的研究熱點。目前常用的無源定位技術可以分為到達角度(angle-of-arrival, AOA)、到達時間(time-of-arrival, TOA)、到達時間差(time-difference-of-arrival, TDOA)、到達頻差(frequency-difference-of-arrival, FDOA)等方法。對于目標輻射源來說,TDOA定位技術利用目標到2個基站的到達時差信息來確定一條以兩基站為焦點的雙曲線,通過多個基站之間的測量值確定多條雙曲線,其交點即為目標位置,在二維空間至少需要3個基站,三維空間至少需要4個基站來確定目標的位置。相對于TOA技術需要知道目標發送信號的準確時間,以及目標的接收基站的時鐘同步等要求,TDOA定位技術不需要建立目標與基站的合作關系,因而在現實中得到廣泛的應用。

因為需要求解的時差等式是非線性的,目標的定位問題并不是一個簡單問題。最大似然(maximum likelihood, ML)估計能夠對非線性問題能夠提供漸進無偏解,但它需要進行格點搜索,計算量很大,在實際應用中難以實現。泰勒展開式(Taylor-series, TS)方法通過將時差頻差非線性等式線性化[1]來求解該問題,但它需要具備一個良好的,接近目標實際位置的初值來保證迭代收斂。近年來,許多閉合式算法被提出用來解決TDOA定位問題[2-13],其中廣泛應用的二次加權最小二乘(two-step weighted least squares， WLS)算法[2-5]引入關于目標位置的附加參數,采用WLS算法給出了定位方程組的非迭代解析解,該方法在噪聲較小的時候具有較高的定位精度。一些學者通過引入半定規劃(semi-definite programming, SDP)技術[12-13]利用凸優化方法對目標初始位置進行求解,然后通過迭代確定目標位置,該方法計算量較大,如果初始值不夠精確,目標位置可能陷入局部最小解中。上述算法均假設接收基站位置精確已知,但在實際應用中,即使通過全球定位系統所獲得的基站位置與真實位置之間也存在著誤差。然而,TDOA定位問題的非線性特征又使目標定位精度對基站的位置精度非常敏感,基站位置微小的偏差可能導致目標定位精度較大的損失。在此基礎上,一個擴展的WLS[14-16]算法被提出用于求解存在基站誤差情況下的目標定位問題,該算法在小噪聲下能夠對目標進行精確定位。

閉合式方法的本質思想是將非線性問題線性化,但線性化非線性問題必然會帶來性能的損失,因此閉合式方法都會面臨所謂的“門檻效應”,當噪聲功率超過一定值時, 通過閉合式算法得到的目標位置精度變差,將目標位置作為初值再通過迭代方法求解時,又會因為較差的初值導致迭代發散;如果考慮基站位置誤差,迭代算法又會由于高維度Hessian矩陣和慢速下降的目標函數而使計算量變得很大。本文提出了修正牛頓算法,解決了牛頓算法的初值問題以及由基站誤差引起的計算復雜性問題。首先利用最大似然估計確定目標函數,運用牛頓法作為優化方法對目標位置進行迭代求解,對于計算過程中可能出現的病態Hessian矩陣,運用正則化理論構修正病態的Hessian矩陣,從而保證算法的迭代收斂性。對于基站誤差造成的高維度Hessian矩陣和慢速下降的目標函數,首先假設基站平臺不存在誤差,在此情況下先對目標位置進行求解,然后再考慮基站位置誤差,對平臺及基站誤差進行聯解精確估計。上述的簡化步驟能夠降低Hessian矩陣維數,加快收斂速度,使求解的目標位置脫離局部最小值,從而使本文算法變得可行高效。

1系統模型

(1)

不考慮非視距傳播的影響,為計算方便以第1個接收基站為中心基站,根據多個TDOA測量值可建立方程組

(2)

d=Gr+n

(3)

(4)

式中，Qt,Qs為TDOA測量噪聲與基站位置誤差噪聲的協方差矩陣E(nnT)=Qt,E(ΔsΔsT)=Qs。

2本文方法

牛頓法是一種需要初始估計值的迭代算法,在每一次迭代中通過求解目標函數的局部最小二乘解來改進估計值,直到搜索到正確解上。每次迭代的改變量

(5)

更新的迭代點x(k+1)可表示為

(6)

(7)

(8)

式中

(9)

(10)

(11)

(12)

(13)

(14)

由式(5)和式(6)可得

(15)

可以看到,求得的θ不僅包括了目標的位置信息,還包含了基站的位置信息,θ中的前3個元素即為所求的目標位置。通過式(8)可以看出,在考慮基站誤差時,矩陣維度變為3+3M的方陣,其矩陣求逆運算量較大,而且受基站誤差影響,目標函數的下降趨勢會變得非常緩慢。本文算法提出了一種改進方法,首先假設基站位置不存在誤差,在此情況下對目標位置進行求解,將求解目標位置作為初值,再考慮基站位置誤差,對目標及基站位置進行聯解精確估計。上述步驟能夠使目標位置解脫離局部最小值,從而加快了收斂速度,降低Hessian矩陣維數,實驗結果驗證了本文算法的有效可行性。當不考慮基站誤差時,目標函數可退化為

(16)

(17)

(18)

(19)

式中，U為單位正交矩陣UTU=In；Σ=diag(σ1,…,σn);σi和向量ui為特征值和與其相對應的特征向量,由式(5)我們得到迭代的改變量為

(20)

(21)

經過修正后的修正量為

(22)

3算法步驟與計算復雜度分析

在實際中我們并不知道目標的真實位置,因此隨機選取迭代的初值是不合理的,通常迭代算法的初始值都是通過閉合式算法求得,因此本文通過在閉合式算法中廣泛應用的two-stepWLS算法來獲得目標的初始位置。

本文算法步驟如下。

步驟 1給定初始值x(1),允許誤差Δ=10-6,置k=1,l=1。

步驟 4置k:=k+1,轉步驟2。

步驟 7置l:=l+1,轉步驟5。

4仿真實驗

圖1　目標位置為(280,325,275)時本文算法與傳統牛頓法受初值影響比較

圖2　目標位置為(2 800,3 250,2 750)時本文算法與傳統牛頓法受初值影響比較　　　　　　圖3　目標位置為(280,325,375)時本文算法與傳統牛頓法收斂性能比較

圖4　目標位置為(280,325,275)時本文算法與WLS算法性能比較　　　　　圖5　目標位置為(2 800,3 250,2 750)時本文算法與WLS算法性能比較

5結論

對于目標的無源時差定位問題,本文在牛頓法的基礎上引入了正則化理論來修正由較差初值而帶來的病態Hessian矩陣,在存在基站位置誤差的情況下,通過2次牛頓法,減少了迭代次數,降低了運算量,高效而準確的求解目標的位置。通過分析和仿真結果表明,本文算法與傳統牛頓法相比,在初始值誤差較大的情況下仍能夠對目標進行精確定位,算法具有較強的穩定性,同時加速了目標函數的下降速度,減少了計算量。與閉合式算法相比,在噪聲較大的情況下本文算法能夠對目標位置精度進行再次提高,定位誤差更接近于CRLB下界,而且該算法收斂較快,計算量小,具有良好的實用價值。

參考文獻：

[1] Kovavisaruch L, Ho K C. Modified Taylor-series method for source and receiver localization using TDOA measurements with erroneous receiver positions[C]∥Proc.oftheIEEEInternationalSymposiumonCircuitsandSystems, 2005:2295-2298.

[2] Ho K C, Xu W. An accurate algebraic solution for moving source location using TDOA and FDOA measurements[J].IEEETrans.onSignalProcessing, 2004, 52(9):2453-2463.

[3] Ho K C. Bias reduction for an explicit solution of source localization using TDOA[J].IEEETrans.onSignalProcessing, 2012, 60(5):2101-2114.

[4] Wang Y, Ho K C. TDOA source localization in the presence of synchronization clock bias and sensor position errors[J].IEEETrans.onSignalProcessing, 2013, 61(18):4532-4544.

[5] Sun M, Yang L, Ho K C. Accurate sequential self-localization of sensor nodes in closed-form[J].IEEETrans.onSignalProcessing, 2012, 92(12):2940-2951.

[6] Wei H W, Peng R, Wan Q, et al. Multidimensional scaling analysis for passive moving target localization with TDOA and FDOA measurements[J].IEEETrans.onSignalProcessing, 2010, 58(3):728-734.

[7] Huang J, Wan Q. Analysis of TDOA and TDOA/SS based geolocation techniques in a non-line-of-sight environment[J].JournalofCommunicationsandNetworks, 2012, 14(5):533-539.

[8] Hara S, Anzai D, Yabu T, et al. A perturbation analysis on the performance of TOA and TDOA localization in mixed LOS/NLOS environments[J].IEEETrans.onCommunications, 2013, 61(2):679-689.

[9] Lin L, So H C, Chan F K W, et al. A new constrained weighted least squares algorithm for TDOA-based localization[J].IEEETrans.onSignalProcessing, 2013, 93(11):2872-2878.

[10] Xu B, Sun G, Yu R, et al. High-accuracy TDOA-based localization without time synchronization[J].IEEETrans.onParallelandDistributedSystems, 2013, 24(8):1567-1576.

[11] Yu H, Huang G, Gao J, et al. An efficient constrained weighted least squares algorithm for moving source location using TDOA and FDOA measurements[J].IEEETrans.onWirelessCommunications, 2012, 11(1):44-47.

[12] Yang K, Wang G, Luo Z Q. Efficient convex relaxation methods for robust target localization by a sensor network using time differences of arrivals[J].IEEETrans.onSignalProcessing, 2009, 57(7):2775-2784.

[13] Wang G, Chen H. An importance sampling method for TDOA-based source localization[J].IEEETrans.onWirelessCommunications, 2011, 10(5):1560-1568.

[14] Ho K C, Lu X, Kovavisaruch L. Source localization using TDOA and FDOA measurements in the presence of receiver location errors:analysis and solution[J].IEEETrans.onSignalProcessing, 2007, 55(2):684-696.

[15] Yang L, Ho K C. Alleviating sensor position error in source localization using calibration emitters at inaccurate locations[J].IEEETrans.onSignalProcessing, 2010, 58(1):67-83.

[16] Sun M, Ho K C. An asymptotically efficient estimator for TDOA and FDOA positioning of multiple disjoint sources in the presence of sensor location uncertainties[J].IEEETrans.onSignalProcessing, 2011, 59(7):3434-3440.

[17] Hansen P C. Regularization tools:A matlab package for analysis and solution of discrete ill-posed problems[J].NumericalAlgorithms, 1994, 6(1):1-35.

[18] Hansen P C, Jensen T K, Rodriguez G. An adaptive pruning algorithm for the discrete L-curve criterion[J].JournalofComputationalandAppliedMathematics, 2007, 198(2):483-492.

房嘉奇(1984-),男,博士研究生,主要研究方向為無源定位與跟蹤。

E-mail:fangjiaqi123@hotmail.com

馮大政(1959-),男,教授,博士研究生導師,研究方向為無源定位、雷達成像、陣列信號處理、盲信號處理、神經網絡。

E-mail:dzfeng@xidian.edu.cn

李進(1985-),男,博士研究生,主要研究方向為盲信號處理。

E-mail:lijin342@163.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141031.0949.001.html

Robust source location algorithm using TDOA in the presence of

sensor position errors

FANG Jia-qi, FENG Da-zheng, LI Jin

(NationalLabofRadarSignalProcessing,XidianUniversity,Xi’an710071,China)

Abstract:For the source localization problem in the presence of sensor position errors, this paper presents a time-difference-of-arrival(TDOA)technique based on the modified Newton(MNT)algorithm. It is known that the NT algorithm suffers from the initialization problem. A bad initial may cause the iteration divergence. In addition, inaccurate sensor position condition also causes the NT algorithm computationally intensive due to the high-dimension matrix and the slow downtrend of the objective function. The new algorithm uses the maximum likelihood method to determine the objective function. For the problem of the ill-condition Hessian matrix caused by the bad initial, the algorithm introduces the regularization theory to modify the Hessian matrix, which ensures the iteration convergence. Meanwhile, the proposed algorithm reduces the degree of the high-dimension matrix and increases the downtrend of the objective function, and makes the solution escape from the local minimum value via a simplified iterative criterion. Experiment results show that compared with the classical Newton method, this new algorithm is robust to the initial value, and is still able to ensure its convergence even with an inaccurate initial value of large errors, it also speeds up the convergent rate and cuts the computation. Compared with some other closed-form source location methods, the new algorithm has better accuracy in large noise levels.

Keywords:time-difference-of-arrival(TDOA); sensor position errors; Hessian matrix; regularization method; Cramer-Rao low bound (CRLB)

作者簡介：

中圖分類號：TN 97

文獻標志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.03

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

收稿日期：2014-06-04；修回日期：2014-09-30；網絡優先出版日期：2014-10-31。