基于到達時間差的兩步最小二乘定位算法

謝勝東 胡愛群 黃 毅 姜 禹

(1東南大學信息科學與工程學院, 南京 210096)

(2南京信息工程大學計算機與軟件學院, 南京 210044)

自1996年美國聯(lián)邦通信委員會要求無線蜂窩系統(tǒng)必須能夠?qū)Πl(fā)出緊急呼叫的移動用戶實現(xiàn)定位后,定位技術便吸引了眾多學者的關注,并得到了迅速發(fā)展．現(xiàn)有定位技術可以分為基于信號強度(RSS)的定位[1]、基于信號到達時間(TOA)[2]或時間差(TDOA)的定位[3],以及基于信號到達角度(DOA)的定位[4]．由于TOA或TDOA能以稍微復雜的硬件電路來換取較高的定位精度,具有RSS和DOA兩者的優(yōu)點,因此被廣泛應用于GSM，LTE等系統(tǒng)中．

TDOA定位主要采用約束線性最小二乘(CLS)算法,此類算法經(jīng)歷了3個發(fā)展階段.第1階段為非全局最優(yōu)階段,即無法獲得目標函數(shù)的全局最優(yōu)值．例如,Schau等[5]提出的球面相交法(SX)獲得了CLS退化問題的一個全局最優(yōu)解,然而該全局解并不是原始CLS的最優(yōu)解．Chan等[6]提出的二次糾正最小二乘法(QCLS)通過第1次丟棄約束條件以及第2次將嚴格約束條件松弛為最小二乘意義上的約束條件來估計目標節(jié)點的位置,由于采用了加權,使得其性能優(yōu)于SX．第2階段為全局最優(yōu)階段,在該階段中,算法能夠獲得目標函數(shù)的全局最優(yōu)解．例如,Huang等[7]基于拉格朗日乘子法提出的線性糾正最小二乘法(LCLS)以及Amir等[8]利用廣義信任域法(GTRS)分別獲得了CLS的全局最優(yōu)解．第3階段為總體最小非全局最優(yōu)階段．事實上,由于基于最小二乘TDOA定位算法中不相容矩陣的元素存在誤差,因此這類算法不再屬于CLS問題,而是一個約束總體最小二乘(TLS)問題,上述所有算法的解都不再是TLS問題的最優(yōu)解．為此,Weng等[9]在丟棄約束條件的基礎上,給出了TLS問題的封閉解;Yang等[10]提出了基于牛頓迭代法的約束總體最小二乘定位算法(CTLS),從而獲得了目標節(jié)點的位置估計值的局部最優(yōu)解;Cao等[11]在CTLS算法的基礎上引入了權重因子,提出了加權約束總體最小二乘定位法(WCTLS),進一步提高了CTLS算法的估計性能．

然而,在目標節(jié)點到達不同基站的距離差上,CTLS與WCTLS均使用測量值來代替實際值,當測量誤差較大時,會對定位效果產(chǎn)生嚴重的影響．為解決上述問題,本文提出了一種兩步最小二乘定位算法(TSLS),即首先利用LCLS算法對目標位置進行初次估計,從而計算出目標節(jié)點到達不同基站的距離差,并用該距離差來近似實際距離差,最后利用CTLS算法來對目標位置再次進行估計．

1 系統(tǒng)模型

本文以二維空間中的目標為定位對象．假設在二維空間中,存在N+1個基站,第0個基站為參考基站,其坐標為(x0,y0),其余基站的坐標記為(xi,yi),i=1,2,…,N;同時存在一個位置未知的目標節(jié)點,其坐標記為(x,y)．盡管本文研究的是二維空間中的定位方法,但該方法很容易擴展到三維空間．

通過TDOA測量,可以得到目標節(jié)點到達基站i與基站0之間的時間差ti,0,該時間差乘以信號的傳播速度,即可獲得目標節(jié)點到達基站i與基站0之間的距離差ri,0．由于信號傳播速度固定,因此下文用距離差來代替時間差．距離差ri,0的表達式為

(1)

式中,ri表示目標節(jié)點到達基站i的距離．

將式(1)中r0移到等號左邊,并對等號兩側(cè)進行平方運算后可得

(2)

(3)

寫成矩陣形式為

Aθ=b

(4)

2 兩步最小二乘定位算法

對式(4)進行觀察不難發(fā)現(xiàn):由于矩陣A和向量b中均存在需要通過測量才能得到其值的元素ri,0,i=1,2,…,N,因此矩陣A和向量b中均存在誤差,于是對式(4)的求解將不再是一個普通的約束最小二乘問題,而屬于總體最小二乘問題．

(5)

當n的每個元素均遠小于其對應的距離差時,則可忽略n的二次方所帶來的影響,故式(5)可近似寫成

(6)

令G=r1IN+diag([r1,0r2,0…rN,0]),基于約束完全最小二乘的相關理論[12],目標節(jié)點的位置則為如下問題的解:

(7)

然而,矩陣G和向量Aθ-b均含有元素ri,0,式(7)中的約束條件本質(zhì)上同樣具備總體最小二乘的形式．如果直接采用CTLS算法[10],即將約束條件看成普通最小二乘形式,忽略矩陣G中的誤差,而令n=G?(Aθ-b),其中“?”表示偽逆,那么將降低位置估計的精度．

顯然,減少矩陣G中的元素誤差必然可以提高CTLS算法的估計精度．為了減少該誤差,須盡可能準確地獲得目標節(jié)點到達不同基站的距離差．為此,本文提出采用計算距離差來代替測量距離差．如果計算距離差的精度大于測量距離差,那么必然能夠減少矩陣G中的誤差,從而提高CTLS算法的估計精度．為此,需要盡可能準確地估計出目標節(jié)點的位置．

考慮到LCLS算法[7]能夠獲得普通約束最小二乘模型中目標函數(shù)的最優(yōu)解,因此,本文采用LCLS算法來對目標節(jié)點的位置進行初步估計．根據(jù)LCLS算法,目標節(jié)點的位置可以通過最小化拉格朗日函數(shù)L(θ,λ)得到,即

L(θ,λ)=(Aθ-b)T(Aθ-b)+λθTΣθ

(8)

其中,Σ=diag(1,1,-1)．將L對θ以及λ求導,并令求導結果為0,通過求解方程組,可獲得有限個滿足條件的θ和λ的值,將這些值代入到式(8)中,使得拉格朗日函數(shù)最小的θ中的前2個元素即為目標節(jié)點位置的估計值．

在獲得目標節(jié)點位置的估計值后,可利用式(1)計算出目標節(jié)點到達不同基站的距離差．將該距離差代入到矩陣G中,同時將式(7)中的約束條件看成普通最小二乘形式,令n=G?(Aθ-b),從而目標節(jié)點的位置為式(9)的解[10],即

F(?)=(A1?+A2(?T?)1/2-b)T(GGT)-1·
(A1?+A2(?T?)1/2-b)

(9)

式中,?={x,y}T;A1為A的前2列;A2為A的第3列．式(9)是一個非線性最優(yōu)化問題,由于前面已經(jīng)利用LCLS算法對目標節(jié)點位置進行了估計,因此可將該估計值作為式(9)的初始點,利用牛頓迭代法即可獲得式(9)的局部最優(yōu)解,從而獲得目標節(jié)點的位置．

從過程上看,本文的兩步最小二乘定位算法首先利用LCLS算法來初次對目標節(jié)點的位置進行估計,從而計算出目標節(jié)點到達不同基站的距離差;接著再利用CTLS算法來對目標節(jié)點的位置進行二次估計．但從本質(zhì)上講,TSLS是通過減少CTLS中矩陣G的誤差來提高其位置估計精度,因此可以看成是一種增強型CTLS算法．

3 性能分析

本文的仿真環(huán)境參考文獻[10]．在一個100m×100m的二維矩形區(qū)域中,存在一個目標節(jié)點,其坐標為(42,12)m,同時存在10個基站,其坐標分別為(0,0)、(16,42)、(34,52)、(58,30)、(78,18)、(66,48)、(30,-12)、(22,12)、(57,-3)、(12,-28)m．在仿真中,基站按照上述順序,從4個逐漸增加到10個．TDOA測量噪聲服從0均值,方差為δ2的高斯分布．

在仿真圖中,測量噪聲方差為10lgδ2．用定位誤差e來衡量算法的性能,其計算公式為

(10)

圖1是基站數(shù)目分別為5,7,9,TDOA測量噪聲方差從0dB變化到20dB時3種算法的定位誤差．從圖中可以看到，TSLS算法的性能始終優(yōu)于CTLS算法，這主要是因為在上述情況下,通過LCLS算法獲得的計算距離差的精度高于測量值.但當測量噪聲大于18dB時,TSLS的性能存在下降的趨勢．這是因為在式(6)中,CTLS算法忽略了測量誤差的二次項,當測量誤差變大時,忽略該二次項而帶來的影響也會逐漸增加,從而導致CTLS算法不適合高測量誤差的情況,進而引起TSLS算法性能的下降．盡管如此,TSLS算法的性能始終優(yōu)于CTLS算法．

圖2是在TDOA測量噪聲方差分別為5,10,15dB,基站數(shù)目從4個逐漸增加到10個時不同算法的定位誤差．從圖中可以看到:① 當基站數(shù)目為4時,TSLS算法的性能遜于CTLS算法,而其余情況下TSLS算法的性能都優(yōu)于CTLS算法．這是因為在基站個數(shù)較少的情況下,LCLS算法的定位誤差較大,從而導致計算距離差的精度小于測量值,使得式(7)矩陣G中的誤差增加,導致TSLS算法的性能下降．但隨著基站數(shù)的增加,LCLS算法定位精度也隨之增加,因此減少了矩陣G中的誤差,從而使得TSLS算法的性能得到迅速提高.② 當基站數(shù)為6時,TSLS算法的性能遜于LCLS算法,而其余情況下TSLS算法的性能都優(yōu)于LCLS算法．這是因為基站的分布會對CTLS算法忽略式(6)中測量誤差二次項后的性能產(chǎn)生影響[13],但這種影響并不顯著,從圖中可以看到TSLS算法的性能只是略遜于LCLS算法．總體而言,TSLS算法的性能要優(yōu)于LCLS和CTLS算法．

圖1 不同TDOA測量噪聲方差下的定位誤差

圖2 不同基站數(shù)下的定位誤差

4 結語

為了提高CTLS算法的性能,本文提出了TSLS算法．該算法首先通過LCLS算法對目標節(jié)點的位置進行估計,進而利用估計值來計算目標節(jié)點到達不同基站的距離差,并將該計算值來代替測量值,最后通過CTLS算法再次估計目標節(jié)點的位置．本質(zhì)上講,由于TSLS算法減少了CTLS算法中矩陣的誤差,從而提高了其性能,因此是一種增強型CTLS算法．仿真結果表明,當TDOA測量噪聲小于18dB時,TSLS算法總體上的性能要優(yōu)于CTLS算法和LCLS算法．

)

[1] Liu C, Fang D Y, Yang Z, et al. RDL: a novel approach for passive object localization in WSN based on RSSI [C]//IEEE2012InternationalConferenceonCommunications. Ottawa, Canada, 2012: 586-590.

[2] Ma Z H, Ho K C. TOA localization in the presence of random sensor position errors [C]//Proceedingsofthe2011IEEEInternationalConferenceonAcoustics,Speech,andSignalProcessing. Prague, Czech Republic, 2011: 2468-2471.

[3] Qu X M, Xie L H. Source localization by TDOA with random sensor position errors—part Ⅱ: mobile sensors [C]//15thInternationalConferenceonInformationFusion. Singapore, 2012: 54-59.

[4] Jonathan B, Anne F, Pascal L. A space time array processing for passive geolocalization of radio transmitters [C]//Proceedingsofthe2011IEEEInternationalConferenceonAcoustics,Speech,andSignalProcessing. Prague, Czech Republic, 2011: 2596-2599.

[5] Schau H C, Bobinson A Z. Passive source localization employing intersecting spherical surfaces from time of arrival differences [J].IEEETransactionsonAcousticsSpeechandSignalProcessing, 1987,35(8): 1223-1225.

[6] Chan Y T, Ho K C. A simple and efficient estimator for hyperbolic location [J].IEEETransactionsonSignalProcessing, 1994,42(8): 1905-1915.

[7] Huang Y, Elko G W, Mersereau R M. Real time passive source localization: a practical linear correction least squares approach [J].IEEETransactionsonSpeechandAudioProcessing, 2001,9(8): 943-956.

[8] Amir B, Petre S, Li J. Exact and approximate solutions of source localization problems [J].IEEETransactionsonSignalProcessing, 2008,56(5): 1770-1778.

[9] Weng Y, Xiao W D, Xie L H. Total least squares method for robust source localization in sensor networks using TDOA measurements [J].InternationalJournalofDistributedSensorNetworks, 2011,2011: 172902-01-172902-08.

[10] Yang K, An J P, Bu X Y, et al. Constrained total least squares location algorithm using time difference of arrival measurements[J].IEEETransactionsonVehicularTechnology, 2010,59(3): 1558-1562.

[11] Cao J M, Wei H W, Yu J. Weighted constrained total least square algorithm for source localization using TDOA measurements [J].FutureWirelessNetworksandInformationSystems, 2012,143: 739-746.

[12] Golub G H, Loan C F V. An analysis of the total least squares problem [J].SIAMJNumerAnal, 1980,17(6): 883-893.

[13] Xu B, Qi W D, Wei L, et al. Turbo TSWLS: enhanced two-step weighted least squares estimator for TDOA based localization [J].ElectronicsLetters, 2012,48(25): 1597-1598.