TDOA中的修正牛頓及泰勒級數(shù)方法

房嘉奇，馮大政，李 進

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

?

TDOA中的修正牛頓及泰勒級數(shù)方法

房嘉奇，馮大政，李 進

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

在多站無源時差定位系統(tǒng)模型下，泰勒級數(shù)算法和牛頓算法在較差初始值條件下容易出現(xiàn)迭代發(fā)散問題．針對這一問題，提出了基于修正泰勒級數(shù)法和牛頓法的時差定位算法．該方法對于較差初始值引起的病態(tài)海森矩陣，運用正則化理論中的吉洪諾夫法或衰減奇異值分解法進行修正，其中控制海森矩陣修正量的重要的正則化參數(shù)由著名的L曲線理論確定．實驗結果證明:相對于原泰勒級數(shù)及牛頓算法，經(jīng)過改進后的算法對于較差的初始值，具有較高的概率使迭代算法的解穩(wěn)健地收斂到目標的真實位置，并擁有較強的能力移除局部最小值;相對于時差定位模型下的一些廣泛應用的線性解法，也成為閉式解法，在低信噪比環(huán)境下具有更高的定位精度．

無源定位;時差定位;修正泰勒級數(shù)算法;修正牛頓算法;正則化算法

多站無源定位技術是電子偵查、電子對抗的一個重要組成部分，被廣泛應用于雷達、導航、監(jiān)督、無線通信、無線傳感器網(wǎng)絡等領域．無源定位技術在測量參數(shù)方面可以分成接收信號強度(Received Signal Strength，RSS)、到達時間(Time Of Arrival，TOA)、到達角度(Angle Of Arrival，AOA)、到達時間差(Time Difference Of Arrival，TDOA)、到達頻差(Frequency Difference Of Arrival，F(xiàn)DOA)等方法．筆者主要研究的是到達時間差方法，也稱為時差定位技術．在三維空間中，該技術利用目標輻射源到兩個接收基站的到達時間差信息確定一個以兩基站為焦點的雙曲面，通過多個基站的時差測量值確定多個雙曲面，其交點即為目標位置．到達時間差目標位置估計方法有以下優(yōu)點:接收機上通常只需安裝單個天線；接收機與接收機之間不需要進行時間同步；定位精度較高．

由于基于到達時間差的定位問題高度非線性非凸特征，并不是一個能夠簡單求解的問題．到達時間差定位方法按照類型可以分為線性化方法和非線性化方法．目前大多數(shù)研究主要側重于線性化方法(閉式解方法)[1-4]，這些方法通過線性化到達時間差的非線性方程組來求解目標位置，它們可被歸類為線性最小二乘(Least Squares， LS)、兩次加權最小二乘(Two-Stage Weighted Least Squares， TSWLS) 和多維尺度分析(MultiDimensional Scaling analysis，MDS) 等．線性化方法的特點是計算量小，在信噪比較高時定位精度能夠達到克拉美羅界(Cramer-Rao Lower Bound， CRLB)，但線性化非線性方程組必然會帶來性能的損失．因此，所有的線性化算法都會受到門檻效應的影響，即在噪聲功率大到一定界限后定位精度誤差逐漸偏離克拉美羅界．針對這一缺點，線性化算法所求得的解可以被作為非線性迭代算法的初值，從而去獲取一個更精確的位置解．當前主要的迭代算法有泰勒級數(shù)法(Taylor-Series， TS)[5]以及牛頓法(NewTon， NT)[6]兩種，但是迭代算法的一個重要弊端在于，當?shù)跏贾递^差時(由線性化算法的解在大噪聲環(huán)境下產(chǎn)生的較大偏差引起)，迭代算法很容易發(fā)散．

筆者將研究的重點放在解決迭代算法中最關鍵的收斂性問題上，利用最大似然估計(Maximum Likelihood， ML)確定目標函數(shù)，然后采用牛頓法進行求解．牛頓法是泰勒展開式的二階近似，它忽略了泰勒展開式中的高階項，然而在高度非線性的時差定位問題中，較差的初始值會導致高階項對解的貢獻變得比較重要，因而忽略高階項很容易致使迭代發(fā)散．筆者提出了修正牛頓算法(Modified NewTon， MNT)用于克服該問題，對于由較差初值引起的病態(tài)海森矩陣，運用正則化理論中常用的吉洪諾夫(TIkhonov，TI)法或衰減奇異值分解法(Damped Singular Value Decomposition， DSVD)[7]將該病態(tài)矩陣轉化為良態(tài)矩陣，其中控制海森矩陣修正量的重要的正則化參數(shù)由著名的L曲線理論[8]確定，并將其同另一種確定正則化參數(shù)的方法——廣義交叉檢驗法(Generalized Cross Validation， GCV)進行對比．需要注意的是，泰勒級數(shù)算法相比較于牛頓算法只用到了一階泰勒展開，因此正則化理論也可以應用到泰勒級數(shù)算法中．筆者同時提出了修正泰勒級數(shù)法(Modified Taylor-Series， MTS)對原泰勒級數(shù)算法進行改進．經(jīng)過改進的修正泰勒級數(shù)法、修正牛頓算法同改進前的算法相比，在收斂性上具有穩(wěn)定性，具有較好的移除局部最小值的能力，能夠穩(wěn)健地收斂到全局最優(yōu)點; 同改進前算法和線性化算法相比，在低信噪比環(huán)境下具有更高的定位精度．

1 到達時間差定位模型

在多站無源時差定位系統(tǒng)下，假設待測目標輻射源位置x=[x，y，z]T，第i個已知接收基站的位置 si= [xi，yi，zi]T，i=1，…，M，M為參與定位的基站數(shù)目，在三維空間內(nèi)至少需要4個不在同一平面之內(nèi)的基站來確定目標的位置．目標和第i個基站之間的距離為

其中，·表示2范數(shù)．選定中心基站為第1個基站，則基站1和基站i之間的時差信息測量值為

其中，c為電磁波傳播速度，ti1為基站1與基站i之間的到達時間差測量值，di1為與測量時差信息對應的測量距離差(Range Difference Of Arrival， RDOA)，ni1c為到達時間差測量誤差．用測量距離差來代替到達時間差．將到達時間差測量等式方程組采用向量形式表達，即

其中，d=[d21，d31，…，dM1]T，r=[r1，r2,…，rM]T，n=[n21，n31，…，nM1]T．G為第1列均為 -1 的 (M- 1)×1 的列向量與維數(shù)為 (M-1) 的單位矩陣所合并的 (M-1)× M的矩陣，G= [-1M-1，IM-1]．噪聲n為零均值、協(xié)方差矩陣 E(n nT)= Qt的向量．根據(jù)最大似然估計，目標函數(shù)可寫為

2 牛頓法及修正牛頓法

牛頓法和泰勒級數(shù)法的本質相同，泰勒級數(shù)法只比牛頓法少用到了泰勒展開式中的二階展開項．因此，首先研究牛頓法，去除二階項即可得到泰勒級數(shù)法．牛頓法是一種經(jīng)典的迭代算法，在每次迭代中通過二階泰勒近似來改進估計值．令迭代次數(shù) k=1，2，…，n，每次迭代后新的更新的估計值xk+1可表示為

xk+1=xk+Δxk=xk-2f(xk)-1

其中,

式(10)中的?表示Kronecker積，vec(·)表示將矩陣沿列向量化．文獻[9-10]中分析了海森矩陣病態(tài)的原因并提出了正則化理論解決辦法，在此基礎上，筆者不僅僅對牛頓法，也對泰勒級數(shù)法進行了改進，并同時對正則化的方法以及正則化參數(shù)的選擇進行了更深入的研究．令 A=2f(x)，b= -f(x)，矩陣A奇異值分解為

其中，U和V為單位正交矩陣，UTU=VTV=In，Σ=diag(σ1，σ2，…，σn)，σi和向量ui，vi為特征值和特征向量．由式(5)得到每次迭代的改變量

式(7)中的第2項即式(10)為二階項．若忽略二階項，牛頓法退化為泰勒級數(shù)法，因此只需將式(7)中第2項忽略，其他計算步驟不變，可在原泰勒級數(shù)法的基礎上得到修正的泰勒級數(shù)法．其表達式可與牛頓法寫成相同的形式，即式(5)～(7)，只需將式(7)中的第2項刪去即可．

3 正則化理論

3.1 正則化方法

正則化理論是一種解決不適定問題的有效方法，它用一種與原不適定問題相鄰近的適定問題的解去逼近原問題的解．常用的正則化方法有吉洪諾夫正則化法、截斷奇異值分解法(Truncated Singular Value Decomposition，TSVD)和衰減奇異值分解法等．吉洪諾夫法正則化等價于求解式(13)在二次約束下的惟一最小二乘解，即將該問題轉化為求解下述二次優(yōu)化問題:

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

經(jīng)過修正后的改變量ΔxTI，其實質相當于在原參量前加入了濾波器fi．特征值越小，濾波器fi也越小，其小特征值對應項的貢獻也越?。渲笑藶檎齽t化參數(shù)，用來控制式(14)中前項(數(shù)據(jù)能量)與后項(穩(wěn)定能量)之間的比例．

截斷奇異值分解方法僅采用矩陣A的大特征值對應的特征空間來構造方程組的解，舍棄了小特征值對應的特征向量．假設A有m個大特征值，則選取m作為截斷參數(shù)．滿足條件σ1，σ2，…，σm≥ λ的特征值保留，舍棄σ1，σ2，…，σm< λ的特征值．因此，采用截斷奇異值分解法得到的修正量可以寫為

衰減奇異值法就是常用的對角加載法，它是一種常用的穩(wěn)健技術，可以有效地解決病態(tài)矩陣求逆問題．對式(13)直接應用對角加載，得到

這3種算法中截斷奇異值分解法主要應用于區(qū)分信號和噪聲空間的多特征值矩陣，而對于到達時間差目標定位問題，要求的海森矩陣在不考慮速度及基站誤差的情況下維數(shù)很小，因此截斷奇異值分解法這種直接濾除小特征值的方法對于本問題不適用．對于吉洪諾夫法和衰減奇異值分解法兩種方法來說，吉洪諾夫方法適用于秩虧情況，而衰減奇異值分解法更適用于病態(tài)矩陣情況．

3.2 正則化參數(shù)

上節(jié)提到的3種方法的性能都十分依賴正則化參數(shù)λ的選擇．正則化參數(shù)的選擇方法有L曲線法和廣義交叉檢驗法．L曲線理論將殘差范數(shù)A Δx-b和正則化范數(shù)Δx的和作為變量取對數(shù)畫圖，通過對比結果確定正則化參數(shù)．該方法所繪制的尺度圖形中會出現(xiàn)一條明顯的L曲線．將曲線中的最大曲率作為其拐點，通過尋找該拐點求得與之相對應的λ．令 ρ= lg A Δx-b，θ= lg Δx，該曲率定義為

廣義交叉檢驗法也是一種常用的確定正則化參數(shù)λ的方法，它的原理是假定將任意的觀測值bi從原觀測序列b中去除，在此時通過剩余觀測值求得的正則化解能夠較好地預測b中被去掉的這個觀測值bi．它等效為求解下面函數(shù)的最小值問題:

矩陣Al滿足關系式Δx=Alb．廣義交叉檢驗法在理論上能夠選擇最優(yōu)的參數(shù)λ，但某些時候廣義交叉檢驗法函數(shù)的變化趨勢非常平緩，這時很難找到它的最小值．而相比較而言，L曲線法能夠快速準確地找到最佳正則化參數(shù)．因此，筆者采用L曲線法作為確定正則化參數(shù)的方法．

對一些值得注意的問題進行如下解釋說明:

(1) 同泰勒級數(shù)算法相比，牛頓算法因為存在式(7)中的第2項，能夠提供一個較為精確的海森矩陣，因此具有較高的定位精度．然而當初值較差時，牛頓算法中的海森矩陣可能負定導致迭代發(fā)散．對于泰勒級數(shù)算法，因為式(7)中的第1項一直為對稱正定矩陣，因此具有較高的收斂概率，但因海森矩陣表達的不完全，其定位結果可能陷入局部最小值中．筆者提出的修正牛頓算法和修正泰勒級數(shù)算法繼承了原算法的特點，相比于修正泰勒級數(shù)算法，修正牛頓算法具有較高的定位精度和較差的收斂性．

(2) 眾所周知，迭代算法需要一個初值，它完全隨機選取是不合適的．在實際應用中，閉合式算法的解通常被作為初值帶入迭代算法．筆者采用著名的兩次加權最小二乘算法來求得初值．在噪聲較大時，兩次加權最小二乘算法的解可能存在較大誤差，此時多維尺度分析算法被用來取代兩次加權最小二乘算法以獲得一個誤差相對較小的初值．

(3) 當目標函數(shù)值f(xk+1)>f(xk)時，認為迭代的過程中出現(xiàn)了發(fā)散的現(xiàn)象；反之，則認為迭代收斂，繼續(xù)觀察，并設定迭代的終止條件為梯度f(xk)< ε．由于時差定位問題的高度非線性特征，因此有時候盡管迭代收斂，但其結果可能陷入局部最小值中．當使用閉合式算法的解作為迭代算法的初值時，若迭代的最終結果為全局最優(yōu)解，則迭代只需要非常少的次數(shù)就可以收斂; 若最終結果為局部最小值，則需要多次迭代才能收斂．在這里需要設定一個迭代次數(shù)的門限用來移除局部最小值．如果該門限設置較為寬松，則少量的局部最小解仍然存在于全局最優(yōu)解中，致使平均值變差; 反之，如果該門限設置較嚴，則許多全局最優(yōu)解將被遺棄，算法實用性降低．筆者提出的正則化算法通過對海森矩陣的修正，在實際上會減慢目標函數(shù)的收斂速度，對于全局最優(yōu)解影響很?。鴮τ诰植孔钚〗鈦碚f，由于其本身收斂速度就較慢，再經(jīng)過文中算法的減緩，收斂速度進一步降低，很容易就能夠超出所設置的迭代門限．相對于文獻[6]中所設置的較嚴格的兩次迭代門限(超過兩次迭代的結果都當做局部最小值被移除，會導致很多全局最優(yōu)解的遺失)，筆者所設置的門限為較為寬松的5次．由于筆者提出的算法具有較強的辨識局部最小值的能力，因此在保證算法實用性的同時，又能夠獲得較好的性能．

4 仿真實驗

實驗中假設5個基站的位置分別為 (300 m，100 m，150 m)，(400 m，150 m，100 m)，(300 m，500 m，200 m)，(350 m，200 m，100 m)，(-100 m，-100 m，-100 m)，設置基站1為中心基站，近距離目標和遠距離目標位置分別為 (280 m，325 m，275 m) 或 (2 800 m，3 250 m，2 750 m)．目標的定位精度以均方誤差(Root Mean Square Error， RMSE)形式表示．實驗中的測量距離差為零均值，協(xié)方差矩陣 σ2R 的高斯噪聲，σ2為時差測量中噪聲的功率，R為對角線元素為1而其余元素為0.5的矩陣，設置迭代次數(shù)門限為5．實驗為 5 000 次蒙特卡羅實驗的平均數(shù)據(jù)．

圖1和圖2描述了近距離和遠距離目標情況下泰勒級數(shù)法、牛頓法、修正泰勒級數(shù)法和修正牛頓法的收斂概率值．從圖中可以看到，根據(jù)說明(1)中的解釋，泰勒級數(shù)法、修正泰勒級數(shù)算法在收斂性上相比于牛頓法，修正牛頓算法的更好．在圖1中，泰勒級數(shù)法和牛頓算法隨著噪聲的變大，很容易導致迭代發(fā)散，而筆者所提出的修正泰勒級數(shù)法和修正牛頓算法具有較強的性能來保證迭代的收斂．在噪聲較大時，收斂概率可以提高大概10%．在圖2中，泰勒級數(shù)法、修正泰勒級數(shù)法和修正牛頓算法都具有較好的收斂概率，只有牛頓法的收斂性較差．

圖1 目標位置為(280m，325m，275m)時幾種算法收斂概率的比較 圖2 目標位置為(2800m，3250m，2750m)時幾種算法收斂概率的比較

圖3和圖4分別展現(xiàn)了近距離和遠距離目標情況下泰勒級數(shù)法、牛頓法、 修正泰勒級數(shù)法和修正牛頓算法的定位精度估計，同時和兩種經(jīng)典的閉合式算法兩次加權最小二乘和多維尺度分析進行比較．從圖3可以看到，所有的算法在高信噪比時都能夠達到克拉美羅界．隨著噪聲的提升，閉合式算法兩次加權最小二乘、多維尺度分析受門檻效應的作用，所求的位置解誤差逐漸變大; 泰勒級數(shù)法和牛頓算法的定位精度也嚴重地偏離了克拉美羅界，這是因為結果中存在的局部最小值大大提升了平均均方誤差估計值．筆者提出的修正泰勒級數(shù)法、修正牛頓算法相比于其他算法在大噪聲環(huán)境下具有較高的定位精度，從圖中可以注意到，修正泰勒級數(shù)算法的定位精度相比于多維尺度分析算法的略差，這是因為在實驗中設置的迭代次數(shù)門限較為寬松，致使結果中依然存在少量的局部最小值從而拉高了平均估計精度．門限選取越嚴格，修正泰勒級數(shù)法的估計精度越趨近于修正牛頓算法．在圖4中可以看到，修正泰勒級數(shù)法和修正牛頓算法的定位精度優(yōu)于其他算法的，由于式(7)中的第2項的值在遠距離目標情況下會變得很小，因此筆者提出的兩種算法結果趨于一致．定位精度在噪聲非常大時略低于克拉美羅界，這是因為噪聲過大時的估計不再是無偏估計的．

圖3 目標位置為(280m，325m，275m)時幾種算法定位精度的比較 圖4 目標位置為(2800m，3250m，2750m)時幾種算法定位精度的比較

圖5給出了修正牛頓算法中的兩種正則化算法——吉洪諾夫法、衰減奇異值分解法的比較結果，實驗從均方誤差和收斂概率兩方面分別驗證了算法的性能．由于初值由閉合式算法給出，相比于隨機給出的初值更為準確．從圖中可以看出，在定位精度方面，兩種方法幾乎相同；在收斂概率方面，吉洪諾夫算法的收斂性要略好于衰減奇異值分解算法的．

圖5 目標位置為(280m，325m，275m)時修正牛頓法中吉洪諾夫法、衰減奇異值分解法的比較結果 圖6 目標位置為(2800m，3250m，2750m)時L曲線和廣義交叉檢測法的性能比較(較差情況)

5 結 束 語

對到達時間差定位問題，筆者在原迭代算法基礎上提出了修正泰勒級數(shù)法以及修正牛頓法，運用正則化理論中的吉洪諾夫技術修正病態(tài)海森矩陣，解決了迭代方法中關鍵的收斂性問題．同原方法相比，經(jīng)過改進的修正泰勒級數(shù)法、修正牛頓算法能夠更加穩(wěn)健地收斂到全局最優(yōu)解; 與兩次加權最小二乘、多維尺度分析等線性算法相比，盡管由于迭代算法的特性使其計算量相對較大，但在低信噪比環(huán)境中定位誤差更接近于克拉美羅界．文中算法的核心思想在于對病態(tài)海森矩陣的正則化處理，此算法可用于多種觀測模型，如到達時間、到達角度等．當目標運動時，此算法也能夠結合到達頻差方程組求解目標的位置及速度，具有良好的實用價值和廣泛的適用范圍．

[1] WANG Y, HO K C. TDOA Source Localization in the Presence of Synchronization Clock Bias and Sensor Poition Erors[J]. IEEE Transactions on Signal Processing, 2013, 61(18): 4532-4544.

[2]WEI H W, PENG R, WAN Q, et al. Multidimensional Scaling Analysis for Passive Moving Target Localization with TDOA and FDOA Measurements[J]. IEEE Transactions on Signal Processing, 2010, 58(3): 1677-1688.

[3]LIN L, SO H C, CHAN F K W, et al. A New Constrained Weighted Least Squares Algorithm for TDOA-based Localization[J]. Signal Processing, 2013, 93(11): 2872-2878.

[4]朱國輝, 馮大政, 周延. 一種利用多運動接收站的時差定位算法[J]. 西安電子科技大學學報, 2015, 42(2): 35-39.

ZHU Guohui, FENG Dazheng, ZHOU Yan. New TDOA Localization Algorithm Using Multiple Moving Receivers[J]. Journal of Xidian University, 2015, 42(2): 35-39.

[5]KOVAVISARUCH L, HO K C. Modified Taylor-series Method for Source and Receiver Localization Using TDOA Measurements with Erroneous Receiver Positions[C]//Proceedings of the IEEE International Symposium on Circuits and Systems: 3. Piscataway: IEEE, 2005: 2295-2298.

[6]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]. IEEE Transactions on Wireless Communications, 2012, 11(1): 44-47.

[7]HANSEN P C. Regularization Tools: a Matlab Package for Analysis and Solution of Discrete Ill-posed Problems[J]. Numerical Algorithms, 1994, 6(1): 1-35.

[8]HANSEN P C, JENSEN T K, RODRIGUEZ G. An Adaptive Pruning Algorithm for the Discrete L-curve Criterion[J]. Journal of Computational and Applied Mathematics, 2007, 198(2): 483-492.

[9]房嘉奇, 馮大政, 李進. 穩(wěn)健收斂的時差頻差定位技術[J]. 電子與信息學報, 2015, 37(4):798-803.

FANG Jiaqi, FENG Dazheng, LI Jin. A Robustly Convergent Algorithm for Source Localization Using TDOA and FDOA[J]. Journal of Electronics & Information Technology, 2015, 37(4): 798-803.

[10]房嘉奇, 馮大政, 李進. 存在基站誤差的穩(wěn)健時差定位算法[J]. 系統(tǒng)工程與電子技術, 2015, 37(5):998-1003.

FANG Jiaqi, FENG Dazheng, LI Jin. Robust Source Location Algorithm Using TDOA in the Presence of Sensor Position Errors[J]. Systems Engineering and Electronics, 2015, 37(5): 998-1003.

(編輯：郭 華)

Research on modified Newton and Taylor-series methods in TDOA

FANGJiaqi，F(xiàn)ENGDazheng，LIJin

(National Key Lab. of Radar Signal Processing, Xidian Univ., Xi’an 710071, China)

In the Time Difference Of Arrival (TDOA) source localization model, based on the Taylor-series (TS) method and Newton (NT) method, this paper presents the Modified Taylor-series(MTS) method and the Modified Newton method(MNT), which solve the critical convergent problem caused by the bad initial value in the original algorithms. The proposed algorithms modify the ill-condition Hessian matrix caused by the bad initial value using the Tikhonov (TI) or the Diagonal Singular Value Decomposition technique (DSVD) in the Regularization theory. The regularization parameter which controls the properties of the regularized solution is determined by the L-curve method. Simulation results show that compared with the TS and NT methods, the proposed methods ensure that the solution of the iterative methods converges on the source location, improves the convergent probability and has a better capability to remove the local minima. The proposed methods also give superior performances of the location accuracy comparing with the closed-form algorithms in low SNR environment.

source localization; time-difference-of-arrival; modified Taylor-series method; modified Newton method;regularization method

2015-10-11

時間：2016-04-01

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

房嘉奇(1984-)，男，西安電子科技大學博士研究生，E-mail: fangjiaqi123@hotmail.com．

http://www.cnki.net/kcms/detail/61.1076.tn.20160401.1622.010.html

10.3969/j.issn.1001-2400.2016.06.005

TN97

A

1001-2400(2016)06-0027-07