一種利用修正牛頓迭代的時(shí)差定位算法

朱國(guó)輝,馮大政,李 進(jìn),周 延

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

一種利用修正牛頓迭代的時(shí)差定位算法

朱國(guó)輝,馮大政,李 進(jìn),周 延

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

針對(duì)傳統(tǒng)基于迭代求解的時(shí)差定位算法中容易出現(xiàn)的發(fā)散問(wèn)題,提出了一種新的基于修正牛頓迭代的時(shí)差定位算法.該算法首先利用輔助變量將非線性時(shí)差定位方程組轉(zhuǎn)化為一組關(guān)于輻射源位置的偽線性方程,在此基礎(chǔ)上把時(shí)差定位問(wèn)題轉(zhuǎn)化為約束加權(quán)最小二乘優(yōu)化問(wèn)題;然后,利用基于特征值修正的牛頓法進(jìn)行定位解算,同時(shí)為了減少迭代次數(shù),通過(guò)二次插值法對(duì)一維優(yōu)化問(wèn)題進(jìn)行尋優(yōu)求解,給出了迭代步長(zhǎng)因子的求取過(guò)程;最后,通過(guò)仿真分析驗(yàn)證了所提算法的有效性.

無(wú)源定位;到達(dá)時(shí)間差;加權(quán)最小二乘估計(jì);修正牛頓法;二次插值法

與傳統(tǒng)的有源定位系統(tǒng)相比,無(wú)源定位技術(shù)具有隱蔽性強(qiáng)的優(yōu)點(diǎn),在雷達(dá)[1]、聲納[2]、無(wú)線通信和傳感器網(wǎng)絡(luò)[3]等領(lǐng)域有著廣泛的應(yīng)用.常用的無(wú)源定位技術(shù)包括基于到達(dá)時(shí)間、基于到達(dá)時(shí)間差和基于到達(dá)角的定位算法[4-7].基于多站時(shí)差的定位技術(shù)對(duì)接收系統(tǒng)的要求較低,具有定位成本低、精度較高等優(yōu)點(diǎn),因而受到越來(lái)越多的關(guān)注.

時(shí)差定位問(wèn)題本質(zhì)上是一個(gè)高度非線性估計(jì)問(wèn)題,可用最大似然估計(jì)方法處理.在測(cè)量噪聲服從高斯分布的前提下,最大似然估計(jì)將時(shí)差定位問(wèn)題轉(zhuǎn)化為非線性最小二乘求解問(wèn)題,通常是利用迭代方法進(jìn)行求解,且需要一個(gè)迭代初始值.目前常見(jiàn)的基于迭代求解的時(shí)差定位算法有泰勒級(jí)數(shù)法[8]、牛頓法[9]等,它們是一類需要初始估計(jì)位置的迭代算法,主要缺點(diǎn)是其收斂性非常依賴于目標(biāo)函數(shù)的非線性程度和迭代初始值的精度.當(dāng)用一組接近真實(shí)值的初始值進(jìn)行迭代求解時(shí),能夠獲得超線性乃至二次收斂速度[10],定位精度高.但是在初始值選擇不好的情況下,迭代過(guò)程中容易落入到局部極小點(diǎn),而且不能保證其收斂性.為此,筆者提出了一種新的基于迭代求解的時(shí)差定位算法.該算法首先通過(guò)對(duì)非線性時(shí)差定位方程進(jìn)行轉(zhuǎn)換,得到較規(guī)則的目標(biāo)函數(shù);然后在迭代過(guò)程中對(duì)海森矩陣進(jìn)行特征值修正,在一定程度上避免了傳統(tǒng)基于迭代求解的定位算法因矩陣奇異引起的發(fā)散現(xiàn)象,同時(shí)通過(guò)二次插值法求解迭代步長(zhǎng)因子,有效減少了迭代次數(shù).仿真結(jié)果驗(yàn)證了所提算法的有效性.

1 時(shí)差定位模型

輻射源u到接收站si的距離為

不失一般性,選取s1作為參考接收站,不考慮非視距傳播的影響,可以得到時(shí)差定位方程為

其中,ni1=cΔti1,表示相應(yīng)的距離差測(cè)量誤差.令fi1(u)=ri-r1,將式(3)寫(xiě)成矢量形式為

最大化式(5),似然函數(shù)可以轉(zhuǎn)換為極小化二次型目標(biāo)函數(shù)[11],即

式(6)為關(guān)于輻射源位置的非線性目標(biāo)函數(shù),沒(méi)有封閉解.

圖1 無(wú)源時(shí)差定位示意圖

2 基于修正牛頓迭代的時(shí)差定位算法

2.1 加權(quán)最小二乘估計(jì)

由式(1)可知,時(shí)差定位模型式(3)是關(guān)于目標(biāo)位置的高度非線性函數(shù),由此得到的目標(biāo)函數(shù)式(6)的幾何結(jié)構(gòu)很不規(guī)則,并且存在局部極小點(diǎn)[12].為此,首先將時(shí)差定位問(wèn)題轉(zhuǎn)化為約束加權(quán)最小二乘問(wèn)題,將式(3)右端的r1移至左端,兩邊同時(shí)平方,得

其中,η=2Bn,B=diag{r2,…,rM}.對(duì)近似方程Aθ≈b,進(jìn)行加權(quán)最小二乘估計(jì)求解,可得

其中,g=[g2,…,gM]T.可在式(11)的基礎(chǔ)上進(jìn)行迭代求解.

2.2 基于修正牛頓迭代的時(shí)差定位算法

其中,Gu0和Hu0分別為目標(biāo)函數(shù)在給定初始值u0下的梯度矢量和海森矩陣.將式(10)得到的結(jié)果作為初始值進(jìn)行迭代,直到收斂.當(dāng)初始值u0距極小點(diǎn)較遠(yuǎn)時(shí),可能出現(xiàn)海森矩陣奇異的情形,此時(shí)不能確定下一步的迭代值;即使海森矩陣可逆,也可能是非正定矩陣,由此得到的搜索方向不一定是下降方向,如按式(12)進(jìn)行迭代,目標(biāo)函數(shù)值可能上升,這就導(dǎo)致算法失效.針對(duì)這些問(wèn)題,提出一種基于特征值修正的牛頓法.

2.2.1 特征值修正

將矩陣Hu進(jìn)行特征值分解得:Hu=UΛUT,其中,Λ=diag{ρ1,ρ2},U為相應(yīng)的特征向量組成的矩陣.設(shè)ρ1和 ρ2已按從大到小的順序排列,若ρ1和ρ2均為正數(shù),則Hu為正定矩陣,取搜索方向若ρ1和ρ2均為負(fù),取?Λ=-Λ;若ρ2＜0,取?Λ=diag{ρ1,ρ1},則修正后的海森矩陣為修正后的海森矩陣的特征值均大于零,取搜索方向即為下降方向.給定任意迭代初始值,修正后的海森矩陣滿足對(duì)稱正定性.

2.2.2 步長(zhǎng)因子λ的選取

引入迭代步長(zhǎng)因子λ,使得每次迭代過(guò)程中,目標(biāo)函數(shù)在下降方向上更接近極小值.一般來(lái)說(shuō),將代入目標(biāo)函數(shù)使目標(biāo)函數(shù)最小的λ即為所求.這種精確搜索往往需要進(jìn)行迭代求解,計(jì)算量大,特別是當(dāng)初始值遠(yuǎn)離最優(yōu)解時(shí),效率很低;而且很多優(yōu)化算法的收斂速度并不依賴于精確的搜索過(guò)程.因此,提出了一種基于二次插值法的步長(zhǎng)因子選取方法,令構(gòu)造二次多項(xiàng)式p(λ)=a+bλ+cλ2,將其極小點(diǎn)作為φ(λ)真實(shí)極小點(diǎn)的近似.當(dāng)λ=0時(shí),令

修正牛頓法的步驟如下:

(1)根據(jù)式(10)求取初始值u0,允許誤差ε＞0[12],令k∶=0.

(4)根據(jù)式(19)求取迭代步長(zhǎng)因子λk.

3 性能分析

由于泰勒級(jí)數(shù)法和高斯牛頓法在實(shí)質(zhì)上等價(jià)[12],為方便討論,稱基于目標(biāo)函數(shù)的泰勒級(jí)數(shù)法為高斯牛頓法.為了檢驗(yàn)文中算法對(duì)輻射源位置估計(jì)的性能,進(jìn)行了下述的仿真實(shí)驗(yàn),并將該算法與基于J(u)的泰勒級(jí)數(shù)法、基于的高斯牛頓法、牛頓法及克拉美羅界的仿真結(jié)果進(jìn)行比較,各算法的迭代停止條件均為.假設(shè)有4個(gè)接收站參與定位,坐標(biāo)分別為[20,1]T,這里及下面仿真實(shí)驗(yàn)中的輻射源坐標(biāo)單位均為米.噪聲協(xié)方差矩陣Q是對(duì)角線元素為非對(duì)角線元素[13]為的對(duì)稱矩陣.采用位置估計(jì)的均方根誤差對(duì)各算法的定位性能進(jìn)行衡量,其定義式為

仿真1輻射源位置坐標(biāo)為[10,30]T,x∈[-100,100],y∈[-100,100].取(4BQBT)-1.圖2(a)～(c)分別給出了目標(biāo)函數(shù)J(u)在權(quán)W0及目標(biāo)函數(shù)在權(quán)W0和最優(yōu)權(quán)W1下隨x和y變化的函數(shù)取值示意圖.從圖2(a)可以看出,目標(biāo)函數(shù)J(u)的幾何結(jié)構(gòu)很不規(guī)則,這就對(duì)迭代初始值的選取要求很高,用傳統(tǒng)優(yōu)化算法進(jìn)行迭代求解時(shí)較難得到正確結(jié)果.從圖2(b)和圖2(c)可以看出,目標(biāo)函數(shù))在權(quán)W0和最優(yōu)權(quán)W1下的幾何結(jié)構(gòu)相似,在y軸方向上較為平坦,但避免了局部極小點(diǎn),與圖2(a)相比有很大改善,幾何結(jié)構(gòu)較為規(guī)則,能較易收斂到正確的結(jié)果,這也在下面的仿真中得到驗(yàn)證.

圖2 目標(biāo)函數(shù)J(u)及隨x和y變化的函數(shù)取值示意圖

仿真2近場(chǎng)輻射源位置坐標(biāo)為[20,12]T,噪聲功率從10-3.5變化到101.2,將式(10)所得結(jié)果作為各算法的迭代初始值.圖3(a)和圖3(b)分別為各算法隨噪聲功率變化的平均迭代次數(shù)和均方根誤差的統(tǒng)計(jì)結(jié)果,式(11)中W=W0.從圖3(a)和圖3(b)可以看出,在噪聲功率較小時(shí),各算法對(duì)輻射源位置估計(jì)的均方根誤差均接近克拉美羅界,所需平均迭代次數(shù)也相當(dāng).隨著噪聲功率的增加,泰勒級(jí)數(shù)法的平均迭代次數(shù)保持最小,但其估計(jì)均方根誤差迅速增加,而文中算法并沒(méi)有出現(xiàn)性能急劇下降的現(xiàn)象,定位精度與高斯牛頓法、牛頓法相當(dāng),說(shuō)明了目標(biāo)函數(shù)具有較好的幾何結(jié)構(gòu).但高斯牛頓法和牛頓法理論上仍然存在發(fā)散的可能性.文中算法的單步迭代計(jì)算量要小于高斯牛頓法和牛頓法的計(jì)算量,但從圖3可以看出,當(dāng)噪聲功率較大時(shí),迭代次數(shù)要明顯小于它們.最后,文中算法、高斯牛頓法和牛頓法的均方根誤差會(huì)出現(xiàn)低于克拉美羅界的現(xiàn)象,這是因?yàn)樵跍y(cè)量誤差較大時(shí),式(7)中的高階誤差項(xiàng)不能忽略不計(jì),這時(shí)各算法是有偏估計(jì)的,而克拉美羅界是所有無(wú)偏估計(jì)所能達(dá)到的下界.

圖3 各算法對(duì)近場(chǎng)輻射源位置的定位性能示意圖

仿真3遠(yuǎn)場(chǎng)輻射源位置坐標(biāo)為[300,220]T,噪聲功率從10-6變化到10-2,各算法迭代初始值的選取同仿真2.圖4(a)和圖4(b)分別給出了各算法對(duì)遠(yuǎn)場(chǎng)輻射源位置估計(jì)隨噪聲功率變化的平均迭代次數(shù)和均方根誤差的統(tǒng)計(jì)結(jié)果.從圖4(a)和圖4(b)可以得出與仿真2類似的結(jié)論,在噪聲功率較小時(shí),各算法對(duì)輻射源位置估計(jì)的均方根誤差均接近克拉美羅界.基于目標(biāo)函數(shù)J(u)的泰勒級(jí)數(shù)法平均迭代次數(shù)較少,但是隨著測(cè)量誤差的增加,其均方根誤差迅速增加.而基于目標(biāo)函數(shù)的文中算法并沒(méi)有出現(xiàn)性能急劇下降的現(xiàn)象,迭代次數(shù)要明顯小于高斯牛頓法和牛頓法的迭代次數(shù),定位精度稍優(yōu)于高斯牛頓法的定位精度,這是因?yàn)楦咚古ｎD法等價(jià)于目標(biāo)函數(shù)的一階近似.最后,文中算法、高斯牛頓法和牛頓法的均方根誤差會(huì)出現(xiàn)類似于仿真2中低于克拉美羅界的現(xiàn)象,原因同仿真2中的說(shuō)明.

圖4 各算法對(duì)遠(yuǎn)場(chǎng)輻射源位置的定位性能示意圖

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)基于迭代求解的時(shí)差定位算法中出現(xiàn)的發(fā)散問(wèn)題,提出了一種基于修正牛頓迭代的時(shí)差定位算法.通過(guò)引入輔助變量將高度非線性定位問(wèn)題轉(zhuǎn)化為約束加權(quán)最小二乘問(wèn)題,求取較規(guī)則的目標(biāo)函數(shù),并在此基礎(chǔ)上利用修正牛頓法進(jìn)行迭代求解.所提算法一方面采取特征值修正避免了傳統(tǒng)迭代算法因矩陣奇異出現(xiàn)的發(fā)散問(wèn)題,另一方面采用二次插值法求取迭代步長(zhǎng)因子減少了迭代次數(shù),具有較好的定位性能.當(dāng)測(cè)量誤差較大時(shí),文中算法忽略了高階誤差項(xiàng)對(duì)均值和其他統(tǒng)計(jì)特性帶來(lái)的影響.如何根據(jù)高階誤差項(xiàng)的統(tǒng)計(jì)特性進(jìn)行更好的定位,是今后研究的方向.

參考文獻(xiàn):

[1]Min Jiang,Niu Ruixin,Blum R S.Bayesian Target Location and Velocity Estimation for Multiple-input Multiple-output Radar[J].IET Radar,Sonar and Navigation,2011,5(6):666-670.

[2]Fluckiger M,Neild A,Nelson B J.Optimization of Receiver Arrangements for Passive Emitter Localization Methods [J].Ultrasonics,2012,52(3):447-455.

[3]Gholami M,Cai Ningxu,Brennan R W.Evaluating Alternative Approaches to Mobile Object Localization in Wireless Sensor Networks with Passive Architecture[J].Computers in Industry,2012,63(9):941-947.

[4]牛新亮,趙國(guó)慶,劉原華,等.低空目標(biāo)高精度無(wú)源時(shí)差定位方法[J].西安電子科技大學(xué)學(xué)報(bào),2009,36(5):862-866.

Niu Xinliang,Zhao Guoqing,Liu Yuanhua,et al.High Precision Passive TDOA Location Method for Low-altitude Targets[J].Journal of Xidian University,2009,36(5):862-866.

[5]Annibale P,Filos J,Nyalor P,et al.TDOA Based Speed of Sound Estimation for a Temperature and Room Geometry Inference[J].IEEE Transactions on Audio,Speech,Language and Signal Processing,2013,21(2):234-246.

[6]Cheung K W,So H C.A Multidimensional Scaling Framework for Mobile Location Using Time-of-arrival Measurements [J].IEEE Transactions on Signal Processing,2005,53(2):460-470.

[7]同非,王俊,李紅偉.Memetic優(yōu)化的外輻射源雷達(dá)方位-多普勒定位方法[J].西安電子科技大學(xué)學(xué)報(bào),2012,39(4): 46-51.

Tong Fei,Wang Jun,Li Hongwei.Novel Passive Radar Location Algorithm Based on Memetic Optimization by Using the Bearing-and-Doppler Frequency[J].Journal of Xidian University,2012,39(4):46-51.

[8]Foy W H.Position-location Solution by Taylor-series Estimation[J].IEEE Transactions on Aerospace and Electronic Systems,1976,12(2):187-194.

[9]Liu Ying,Zhang Xu,Liu Dan,et al.Study of Location Algorithm for Wireless Sensor Networks Based on Newton Iteration[J].Advanced Materials Research,2013,645:285-289.

[10]袁亞湘,孫文瑜.最優(yōu)化理論與方法[M].北京:科學(xué)出版社,1997.

[11]Torrieri D J.Statistical Theory of Passive Location Systems[J].IEEE Transactions on Aerospace and Electronic Systems,1984,20(2):183-198.

[12]Dogancay K,Sakhtsari A H.Target Tracking by Time of Difference of Arrival Using Recursive Smoothing[J].Signal Processing,2005,85(4):667-679.

[13]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.

(編輯:齊淑娟)

簡(jiǎn) 訊

近日,在“2014年英特爾杯嵌入式系統(tǒng)專題邀請(qǐng)賽”中,西安電子科技大學(xué)應(yīng)邀參賽的4支代表隊(duì)全部獲獎(jiǎng).其中,“基于視覺(jué)體感雙平衡的防暈動(dòng)系統(tǒng)”奪得本次大賽的最高獎(jiǎng)項(xiàng)“Intel杯”.嵌入式系統(tǒng)專題邀請(qǐng)賽自2002年舉辦首屆競(jìng)賽以來(lái),到2014年已成功舉辦了七屆.今年共有來(lái)自15個(gè)國(guó)家和地區(qū)的83所高校,170支隊(duì)伍參加.我校另三支參賽隊(duì)分獲二、三等獎(jiǎng).

(摘自《西電科大報(bào)》2014.8.14)

TDOA location algorithm based on modified Newton iterations

ZHU Guohui,FENG Dazheng,LI Jin,ZHOU Yan
(National Key Lab.of Radar Signal Processing,Xidian Univ.,Xi’an 710071,China)

For the divergence problem of traditional iterative process based location algorithms,a new modified Newton algorithm for the passive location from time differences of arrival(TDOA)is proposed. The proposed algorithm firstly reorganizes the nonlinear TDOA equations into pseudo-linear ones by using an auxiliary parameter,and a constrained weighted least-squares minimization is developed for the positioning problem instead of the Maximum Likelihood estimator.A modified Newton method based on eigenvalue modification is then applied to obtain the emitter position.In order to reduce the number of iterations,an appropriate iteration step size is computed via one-dimensional optimization by the quadratic interpolation method.Simulation results demonstrate the effectiveness of the proposed algorithm.

passive location;time difference of arrival;weighted least squares estimates;modified Newton algorithm;quadratic interpolation method

TN97

A

1001-2400(2014)05-0036-06

2013-06-24< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2014-01-12

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

朱國(guó)輝(1987-),男,西安電子科技大學(xué)博士研究生,E-mail:zhugh@stu.xidian.edu.cn.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.007.html

10.3969/j.issn.1001-2400.2014.05.007