基于到達(dá)時(shí)間差的兩步最小二乘定位算法

謝勝東 胡愛群 黃 毅 姜 禹

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

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

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

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

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

1 系統(tǒng)模型

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

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

(1)

式中,ri表示目標(biāo)節(jié)點(diǎn)到達(dá)基站i的距離．

將式(1)中r0移到等號(hào)左邊,并對(duì)等號(hào)兩側(cè)進(jìn)行平方運(yùn)算后可得

(2)

(3)

寫成矩陣形式為

Aθ=b

(4)

2 兩步最小二乘定位算法

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

(5)

當(dāng)n的每個(gè)元素均遠(yuǎn)小于其對(duì)應(yīng)的距離差時(shí),則可忽略n的二次方所帶來的影響,故式(5)可近似寫成

(6)

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

(7)

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

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

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

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

(8)

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

在獲得目標(biāo)節(jié)點(diǎn)位置的估計(jì)值后,可利用式(1)計(jì)算出目標(biāo)節(jié)點(diǎn)到達(dá)不同基站的距離差．將該距離差代入到矩陣G中,同時(shí)將式(7)中的約束條件看成普通最小二乘形式,令n=G?(Aθ-b),從而目標(biāo)節(jié)點(diǎn)的位置為式(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)是一個(gè)非線性最優(yōu)化問題,由于前面已經(jīng)利用LCLS算法對(duì)目標(biāo)節(jié)點(diǎn)位置進(jìn)行了估計(jì),因此可將該估計(jì)值作為式(9)的初始點(diǎn),利用牛頓迭代法即可獲得式(9)的局部最優(yōu)解,從而獲得目標(biāo)節(jié)點(diǎn)的位置．

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

3 性能分析

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

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

(10)

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

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

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

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

4 結(jié)語

為了提高CTLS算法的性能,本文提出了TSLS算法．該算法首先通過LCLS算法對(duì)目標(biāo)節(jié)點(diǎn)的位置進(jìn)行估計(jì),進(jìn)而利用估計(jì)值來計(jì)算目標(biāo)節(jié)點(diǎn)到達(dá)不同基站的距離差,并將該計(jì)算值來代替測(cè)量值,最后通過CTLS算法再次估計(jì)目標(biāo)節(jié)點(diǎn)的位置．本質(zhì)上講,由于TSLS算法減少了CTLS算法中矩陣的誤差,從而提高了其性能,因此是一種增強(qiáng)型CTLS算法．仿真結(jié)果表明,當(dāng)TDOA測(cè)量噪聲小于18dB時(shí),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.