房嘉奇, 馮大政, 李　進(jìn)

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

?

存在基站誤差的穩(wěn)健時(shí)差定位算法

房嘉奇, 馮大政, 李進(jìn)

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

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

關(guān)鍵詞：時(shí)差定位; 基站誤差; Hessian矩陣; 正則化算法; 克拉美羅界

0引言

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

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

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

1系統(tǒng)模型

(1)

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

(2)

d=Gr+n

(3)

(4)

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

2本文方法

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

(5)

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

(6)

(7)

(8)

式中

(9)

(10)

(11)

(12)

(13)

(14)

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

(15)

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

(16)

(17)

(18)

(19)

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

(20)

(21)

經(jīng)過修正后的修正量為

(22)

3算法步驟與計(jì)算復(fù)雜度分析

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

本文算法步驟如下。

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

步驟 4置k:=k+1,轉(zhuǎn)步驟2。

步驟 7置l:=l+1,轉(zhuǎn)步驟5。

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

圖1　目標(biāo)位置為(280,325,275)時(shí)本文算法與傳統(tǒng)牛頓法受初值影響比較

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

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

5結(jié)論

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

參考文獻(xiàn)：

[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-),男,博士研究生,主要研究方向?yàn)闊o源定位與跟蹤。

E-mail:fangjiaqi123@hotmail.com

馮大政(1959-),男,教授,博士研究生導(dǎo)師,研究方向?yàn)闊o源定位、雷達(dá)成像、陣列信號(hào)處理、盲信號(hào)處理、神經(jīng)網(wǎng)絡(luò)。

E-mail:dzfeng@xidian.edu.cn

李進(jìn)(1985-),男,博士研究生,主要研究方向?yàn)槊ば盘?hào)處理。

E-mail:lijin342@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：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)

作者簡介：

中圖分類號(hào)：TN 97

文獻(xiàn)標(biāo)志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.03

基金項(xiàng)目：國家自然科學(xué)基金(61271293) 資助課題

收稿日期：2014-06-04；修回日期：2014-09-30；網(wǎng)絡(luò)優(yōu)先出版日期：2014-10-31。