基于改進(jìn)最小二乘算法的TDOA/AOA定位方法

閆雷兵　陸音　張業(yè)榮

(1.南京郵電大學(xué)電子科學(xué)與工程學(xué)院,南京 210003;2.河南科技學(xué)院,新鄉(xiāng) 453003)

?

基于改進(jìn)最小二乘算法的TDOA/AOA定位方法

閆雷兵1,2陸音1張業(yè)榮1

(1.南京郵電大學(xué)電子科學(xué)與工程學(xué)院,南京 210003;2.河南科技學(xué)院,新鄉(xiāng) 453003)

摘要針對(duì)現(xiàn)有的兩步加權(quán)最小二乘(Two-stage Weighted Least Squares, TSWLS)和約束加權(quán)最小二乘(Constrained Weighted Least Squares,CWLS)在TDOA/AOA混合定位中可能產(chǎn)生測(cè)量矩陣奇異的情況,提出了一種改進(jìn)的CWLS算法來(lái)消除奇異矩陣求逆運(yùn)算.其主要思想是在約束條件下,用含有移動(dòng)臺(tái)位置坐標(biāo)的價(jià)值函數(shù)對(duì)移動(dòng)臺(tái)坐標(biāo)和附加變量分別取偏微分,分離出引入的附加變量,使移動(dòng)臺(tái)位置坐標(biāo)與附加變量分別位于線性方程的兩邊,求解關(guān)于附加變量的一元二次方程,因此避免了對(duì)奇異矩陣求逆的運(yùn)算.在零均值的高斯白噪聲環(huán)境下,且移動(dòng)臺(tái)位于或接近監(jiān)測(cè)基站陣列中心時(shí),通過(guò)MATLAB仿真驗(yàn)證了改進(jìn)的CWLS算法比TSWLS和CWLS算法均能取得更高的定位精度,可以達(dá)到克拉美-羅下界(Cramér-Rao Lower Bound,CRLB).

關(guān)鍵詞加權(quán)最小二乘;約束優(yōu)化;到達(dá)時(shí)間差;到達(dá)角

引言

目標(biāo)源定位技術(shù)在最近的幾十年來(lái)一直備受科研人員的關(guān)注,也是當(dāng)今世界科學(xué)領(lǐng)域的研究熱點(diǎn)之一.它廣泛應(yīng)用于雷達(dá)、聲納、導(dǎo)航、無(wú)線通信、傳感器網(wǎng)絡(luò)等領(lǐng)域,而快速發(fā)展的蜂窩移動(dòng)通信系統(tǒng),使人們對(duì)移動(dòng)臺(tái)的定位技術(shù)越來(lái)越感興趣,并且因政府的強(qiáng)制性要求和市場(chǎng)利益的驅(qū)動(dòng),基于定位服務(wù)的研究得到各大通信公司、大學(xué)和科研機(jī)構(gòu)的重視.由于通信系統(tǒng)中智能天線陣列的應(yīng)用,服務(wù)基站(Base-Station, BS)可以測(cè)量移動(dòng)臺(tái) (Mobile-Station,MS)電波到達(dá)角 (Angle-of-Arrival, AOA),從而可以準(zhǔn)確估計(jì)移動(dòng)臺(tái)的位置.到達(dá)時(shí)間差 (Time-Difference-of-Arrival, TDOA)的定位技術(shù),由于它能獲得比較高的定位精度而成為移動(dòng)臺(tái)定位常用的測(cè)量技術(shù)之一,基于Chan定位算法,文章提出了TDOA和AOA混合定位技術(shù),因此多個(gè)TDOA和AOA測(cè)量值就可以構(gòu)建關(guān)于移動(dòng)臺(tái)位置坐標(biāo)的雙曲線方程組[1-5].然而解算方程組定位移動(dòng)臺(tái)并不簡(jiǎn)單,因?yàn)門(mén)DOA測(cè)量方法是非線性的,產(chǎn)生的方程組一般為超定的非線性方程組,求解非線性方程組有兩種方法:一是直接解非線性方程組獲取估計(jì)值[6-7],文獻(xiàn)[6]提出了泰勒級(jí)數(shù)展開(kāi)算法求解非線性方程,具有精度高,穩(wěn)定性強(qiáng)等特點(diǎn),但是該算法要求迭代運(yùn)算的初始值必須接近真實(shí)值以防止發(fā)生局部收斂,并且算法的計(jì)算復(fù)雜度也比較高,在實(shí)際應(yīng)用中比較難以實(shí)現(xiàn).二是通過(guò)引入附加變量把非線性方程組轉(zhuǎn)化為偽線性方程組來(lái)求解[8-12](引入變量與待求變量有關(guān)系),文獻(xiàn)[8]和[9]就是引入附加變量而不考慮引進(jìn)變量與待求變量之間的關(guān)系進(jìn)行計(jì)算,定位誤差較大.文獻(xiàn)[11]和文獻(xiàn)[12]分別對(duì)文獻(xiàn)[8]進(jìn)行了改進(jìn)提出了兩步加權(quán)最小二乘 (Two Weighted Least Squares,TSWLS)算法和約束加權(quán)最小二乘 (Constrained Weighted Least Squares,CWLS)算法,改進(jìn)后的兩種算法在測(cè)量噪聲誤差較小的情況下,均能達(dá)到克拉美-羅下界(Cramér-Rao Lower Bound,CRLB).然而當(dāng)移動(dòng)臺(tái)到各個(gè)基站的距離相等或近似相等時(shí),上述兩種算法的測(cè)量矩陣都會(huì)出現(xiàn)奇異情況,此時(shí)測(cè)量矩陣變?yōu)槠娈惥仃?例如,當(dāng)所有基站的排列是均勻圓陣列 (Uniform Circular Array,UCA),而移動(dòng)臺(tái)恰好在或者靠近圓陣列的中心時(shí),TSWLS算法和CWLS算法的定位誤差很大,此時(shí)TDOA和AOA系統(tǒng)的測(cè)量矩陣出現(xiàn)異常產(chǎn)生奇異矩陣,文獻(xiàn)[11]和文獻(xiàn)[12]的定位性能得不到保證.而本文提出的分離變量的方法,避免了對(duì)奇異矩陣進(jìn)行求逆運(yùn)算,在測(cè)量誤差較小的情況下,仿真結(jié)果表明文中算法具有較高的精度.

1定位模型

1.1TDOA定位模型

假設(shè)二維平面內(nèi)分布著M個(gè)基站且M≥4,同樣也可以擴(kuò)展到三維空間[13].假定移動(dòng)臺(tái)坐標(biāo)為x=[x,y]T,第i個(gè)基站的坐標(biāo)為xi=[xi，yi]T(i=1,2,3,…,M),通常，將第一個(gè)基站作為參考基站.由到達(dá)時(shí)差TDOA的測(cè)量值，經(jīng)過(guò)轉(zhuǎn)換得到距離差ri,1，公式為

ri,1=di,1+ni,1,i=2,3,…,M.

(1)

式中:ni,1=ni-n1,ni表示系統(tǒng)測(cè)量誤差;di,1=di-d1,di表示移動(dòng)臺(tái)到第i個(gè)基站的距離,即

(2)

將式(2)代入式(1),并且引入一個(gè)中間變量 ，經(jīng)過(guò)整理可得

(xi-x1)(x-x1)+(yi-y1)(y-y1)+

ri,1R1

mi,1,i=2,3,…,M.

(3)

Eθ=h+m.

(4)

式中

: E=x2-x1y2-y1r2,1???xM-x1yM-y1rM,1é?êêêêù?úúúú;

θ=[x-x1y-y1R1];

m=[m2,1…mM,1]T;

1.2AOA定位模型

(5)

式中,φi為φi的真實(shí)值.系統(tǒng)測(cè)量方位角與移動(dòng)臺(tái)坐標(biāo)和第i個(gè)基站坐標(biāo)有如下的關(guān)系:

(6)

整理式(6)可以得到

(7)

(8)

式(7)經(jīng)化簡(jiǎn)合并誤差項(xiàng)可以用矩陣的形式表示為

Hx=K+δ.

(9)

式中:x=[x,y]T;

δ=[δ1,δ2,…,δM]T;

1.3TDOA和AOA混合定位模型

很顯然，不同的定位模型都有各自的優(yōu)缺點(diǎn),把兩種定位模型混合使用,可以提高定位的精度或者減少定位所用的基站數(shù)目.比較常用的是TDOA與AOA混合定位模型,聯(lián)合式(4)和式(9)得到混合定位的矩陣形式方程為

Aθ=q+N.

(10)

N=δ+m′,

m′=[0,m2,1，…，mM,1]；

根據(jù)文獻(xiàn)[11]的TSWLS和文獻(xiàn)[12]的CWLS算法,θ可以通過(guò)式(11)求得:

s.t.

θTSθ= (x-x1)2+

(11)

(12)

對(duì)于式(11),一方面可以根據(jù)文獻(xiàn)[11]兩步加權(quán)最小二乘求解,結(jié)果為

(13)

另一方面根據(jù)文獻(xiàn)[12],引入最小化拉格朗日乘子求解式(11)得

(14)

式中,λ是拉格朗日乘子.通過(guò)約束加權(quán)最小二乘求解,結(jié)果為

(15)

式中λ是四階多項(xiàng)式式(16)的根

(16)

式中: [u1u2u3]T=UTSATWq; [w1w2w3]T=U-1ATWq; ATWAS=UAdiag(ζ1ζ2ζ3)U-1.

1.4奇異矩陣

混合TDOA和AOA定位過(guò)程中假定基站的分布符合UCA分布,且被定位的移動(dòng)臺(tái)恰好位于該圓周的圓心或靠近圓心,這時(shí)移動(dòng)臺(tái)到所有定位基站的距離都相等或近似相等,所以式(1)中的所有ri,1=0,而式(13)和(15)中都出現(xiàn)了(ATWA)-1奇異矩陣求逆的問(wèn)題.現(xiàn)實(shí)定位中,移動(dòng)臺(tái)和基站的位置分布并不是確切的UCA模型,并且還伴有系統(tǒng)測(cè)量噪聲誤差,然而,當(dāng)噪聲足夠小時(shí),近似UCA分布問(wèn)題,同樣也會(huì)遇到奇異矩陣的問(wèn)題.

當(dāng)ATWA出現(xiàn)奇異情況時(shí),式(15)中λ的數(shù)學(xué)期望為零,即E{λ}=0,因此式(15)的解也是一個(gè)異常解.為了清楚上述矩陣的奇異情況,式(15)可以變化為

(17)

(18)

由于E{ΔA}=0(M-1)×3,E{Δq}≈0(M-1)×1,0m×n表示m×n階0矩陣,E{Δθ}=03×1,由此我們得到E{λ}=0,因?yàn)槲墨I(xiàn)[12]通過(guò)式(15)不能給出正確λ值,故無(wú)法獲得正確的θ估計(jì)值.

2改進(jìn)CWLS算法

Gη=q-gR1+N.

(19)

根據(jù)式(19),SCWLS的價(jià)值函數(shù)可表示為

J(η～ R1)= (Gη～-q+gR1)T

(20)

(21)

求解式(21)最小值問(wèn)題等同于求解拉格朗日函數(shù)最小值問(wèn)題:

L(η～,β,R1)= (Gη～-q+gR1)TWGη～(-

(22)

式中β是拉格朗日乘子.

?L(η～,β,R1)/?η～= 2GTW(Gη～-q+gR1)+

(23)

根據(jù)式(14)和(15),移動(dòng)臺(tái)的估計(jì)位置為

(24)

(25)

把式(24)代入約束條件式(21)得到一個(gè)一元二次方程

(26)

式中:

a=(GTWg)T(GTWG+βI2)-2GTWg-1;

b=-2(GTWq)T(GTWG+βI2)-2GTWg;

c=(GTWq)T(GTWG+βI2)-2GTWq.

從上述公式可以看出沒(méi)有出現(xiàn)奇異矩陣ATWA求逆的運(yùn)算.

1) Δ<0或式(26)有復(fù)數(shù)根:

① 如果兩根一正一負(fù),那選擇正根.

1) 首先置W=IM.

2) 求解式(16)獲取實(shí)根β,記作β(l),l=1,2,…,L(L≤4).

7) 重復(fù)步驟2)～6)直到滿足條件為止.

3仿真結(jié)果

(27)

圖1　移動(dòng)臺(tái)坐標(biāo)為[4.9 5.1]T時(shí)的MSE

圖2　移動(dòng)臺(tái)坐標(biāo)為[2 8]T時(shí)的MSE

圖3在1 000次試驗(yàn)中,移動(dòng)臺(tái)在四個(gè)基站所組成方形區(qū)域內(nèi)位置坐標(biāo)隨機(jī)變化的MSE.從圖中可以看到SCWLS具有比TSWLS或者CWLS更小的MSE.由于發(fā)射源的位置是隨機(jī)的,它可能偶爾靠近[55]T,使得TSWLS和CWLS形成異常情況從而導(dǎo)致更大的MSE.

圖4是移動(dòng)臺(tái)坐標(biāo)為[208]T時(shí)MSE,超出了基站形成圓形邊界.從圖中可以看出這種分布下閾值降到p≈-8dB,對(duì)于p>0dB,算法給出了帶有偏差的估值,且它們的MSE低于CRLB.有可能是估計(jì)值存在偏差,它的MSE比CRLB更小.

圖3　移動(dòng)臺(tái)坐標(biāo)為隨機(jī)分布下的MSE

圖4　移動(dòng)臺(tái)坐標(biāo)為[20　8]T時(shí)的MSE

4結(jié)論

由于TSWLS和CWLS方法存在對(duì)奇異矩陣求逆的問(wèn)題,文章提出了SCWLS方法,無(wú)論移動(dòng)臺(tái)離基站陣列中心的距離遠(yuǎn)與近,甚至于剛好位于陣列中心的情況下,實(shí)驗(yàn)證明SCWLS算法都是最優(yōu)化的算法,而其他兩種算法的MSE都在CRLB之上.仿真結(jié)果同時(shí)表明重新構(gòu)建一個(gè)合適的價(jià)值函數(shù)是很必要的,它能在移動(dòng)臺(tái)靠近UCA中心時(shí)表現(xiàn)出更好的性能,獲得更小的閾值.改進(jìn)算法不僅可以優(yōu)化TDOA和AOA混合定位模型中的測(cè)量數(shù)據(jù)，而且也可以優(yōu)化其他引入了附加變量的混合定位模型中的測(cè)量數(shù)據(jù)。

參考文獻(xiàn)

[1]曹軼超, 方建安, 羅賢云. 一個(gè)基于TDOA的無(wú)線定位新算法[J].電波科學(xué)學(xué)報(bào), 2008, 23(5): 841-846.

CAOYC,FANGJA,LUOXY.Constrainedleast-squaresandwirelesslocationbasedonTDOAmeasurements[J].Chinesejournalofradioscience, 2008, 23(5):841-846. (inChinese)

[2] 鄧平, 李莉, 范平志. 一種TDOA/AOA混合定位算法及其性能分析[J].電波科學(xué)學(xué)報(bào),2002,17(6):632-636.

DENGP,LIL,FANPZ.AhybridTDOA/AOAlocationalgorithmanditsperformanceanalysis[J].Chinesejournalofradioscience, 2002, 17(6):632-636. (inChinese)

[3] 范平志.蜂窩網(wǎng)無(wú)線定位[M].北京:電子工業(yè)出版社,2002:109-123.

[4]LIUCF,YANGJ,WANGFS.JointTDOAandAOAlocationalgorithm[J].Journalofsystemsengineeringandelectronics, 2013, 24(2):183-188.

[5] 鮑君海, 張曉林, 張秀強(qiáng), 等.一種高精度移動(dòng)多站無(wú)源 定位方法[J].電波科學(xué)學(xué)報(bào), 2014, 29(3):424-430.

BAOJH,ZHANGXL,ZHANGXQ,etal.Newmethodwithhighaccuracyformobilemulti-stationpassivelocation[J].Chinesejournalofradioscience, 2014, 29(3): 424-430. (inChinese)

[6]FOYWH.PositionlocationsolutionsbyTaylor-seriesestimation[J].IEEEtransactionsonaerospaceandelectronicsystems, 1976, 12(2): 187-194.

[7]QUBP,SHAOG,JINGZR.AnimprovedTDOAlocationalgorithminLOSenvironment[C]//2012 4thInternationalConferenceonIntelligentHuman-MachineSystemsandCybernetics(IHMSC),Nanchang,August26-27,2012.IEEE, 2012: 70-73.DOI:10.1109/IHMSC.2012.23.

[8]HUAGANGYU,GAOMINGHUANG,JUNGAO.AnefficientconstrainedweightedleastsquaresalgorithmformovingsourcelocationusingTDOAandFDOAmeasurements[J].IEEEtransactionsonwirelesscommunications, 2012, 11(1): 44-47.

[9]SMITHJO,ABELJS.Closed-formleast-squaressourcelocationestimationfromrange-differencemeasurements[J].IEEEtransactionsonacousticsspeech&signalprocessing, 1988, 35(12):1661-1669.

[10]郝本建, 李贊, 萬(wàn)鵬武, 等. 傳感器網(wǎng)絡(luò)基于特征值分解的信號(hào)被動(dòng)定位技術(shù)[J]. 物理學(xué)報(bào), 2014, 65(5): 054304.

HAOBJ,LIZ,WANPW,etal.PassivesourcelocalizationusingRROAbasedoneigen-valuedecompositionalgorithminWSNs[J].Actaphysicasinica,2014, 65(5): 054304.(inChinese)

[11]CHANYT,HOKC.Asimpleandefficientestimatorforhyperboliclocation[J].IEEEtransactionsonsignalprocessing, 1994, 42(8):1905-1915.

[12]CHEUNGKW,SOHC,MAWK,etal.Aconstrainedleastsquaresapproachtomobilepositioning:algorithmsandoptimality[J].Eurasipjournalonappliedsignalprocessing, 2006(1):020858.

[13]章堅(jiān)武, 唐兵, 秦峰.Chan定位算法在三維空間定位中的應(yīng)用[J]. 計(jì)算機(jī)仿真,2009,26(1):323-325.

ZHANGJW,TANGB,QINF.ApplicationofChanlocationalgorithmin3-dimensionalspacelocation[J].Computersimulation, 2009, 26(1): 323-325. (inChinese)

Improved least-squares algorithm for TDOA/AOA-based localization

YAN Leibing1,2LU Yin1ZHANG Yerong1

(1.CollegeofElectronicScience&Engineering,NanjingUniversityofPostsTelecommunication,Nanjing210003,China;2.HenanInstituteofScienceandTechnology,Xinxiang453003,China)

AbstractThe two-stage weighted least squares (TSWLS) and constrained weighted least squares (CWLS) are used to locate mobile station with TDOA/AOA hybrid model, and they both have the same measurement matrix that become ill-conditioned when base-station present circular array distribution and Mobile-Station is close to the array center. An improved constrained weighted least square algorithm is proposed to circumvent this problem. The main strategy is to separate the mobile station coordinates and the additional variable to different sides of the linear equations, the additional variable is first solved via a quadratic equation in order to avoid the inverse operation of ill-conditioned matrix. Under the zero mean Gaussian white noise environment and the mobile station is located in or near the array center, the simulation results evaluate its localization accuracy by comparing with the existing TSWLS and CWLS algorithms as well as the Cramér-Rao lower bound.

Keywordsweighted least squares; constrained optimization; time-difference-of-arrival; angle-of-arrival

收稿日期：2015-04-19

中圖分類(lèi)號(hào)TN929.53

文獻(xiàn)標(biāo)志碼A

文章編號(hào)1005-0388(2016)02-0394-07

DOI10.13443/j.cjors.2015041901

作者簡(jiǎn)介

閆雷兵 (1980-),男,河南人,南京郵電大學(xué)電子科學(xué)與工程學(xué)院在讀博士研究生，主要研究方向?yàn)榉涓C無(wú)線網(wǎng)絡(luò)定位、認(rèn)知無(wú)線電技術(shù).

陸音 (1970-),男,江蘇人,博士,南京郵電大學(xué)副研究員,碩士生導(dǎo)師，主要研究方向?yàn)闊o(wú)線通信與電磁兼容、認(rèn)知無(wú)線電技術(shù).

張業(yè)榮 (1963-),男,安徽人,博士,南京郵電大學(xué)電子科學(xué)與工程學(xué)院教授,博士生導(dǎo)師，主要研究方向?yàn)橐苿?dòng)通信系統(tǒng)與設(shè)計(jì)、電磁場(chǎng)的數(shù)值計(jì)算、UWB信道等.

閆雷兵, 陸音, 張業(yè)榮. 基于改進(jìn)最小二乘算法的TDOA/AOA定位方法[J]. 電波科學(xué)學(xué)報(bào),2016,31(2):394-400. DOI: 10.13443/j.cjors.2015041901

YAN L B, LU Y, ZHANG Y R. Improved least-squares algorithm for TDOA/AOA-based localization [J]. Chinese journal of radio science,2016,31(2):394-400. (in Chinese). DOI: 10.13443/j.cjors.2015041901

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

聯(lián)系人： 張業(yè)榮 E-mail:zhangyr@njupt.edu.cn