基于改進最小二乘算法的TDOA/AOA定位方法

閆雷兵　陸音　張業榮

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

?

基于改進最小二乘算法的TDOA/AOA定位方法

閆雷兵1,2陸音1張業榮1

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

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

關鍵詞加權最小二乘;約束優化;到達時間差;到達角

引言

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

1定位模型

1.1TDOA定位模型

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

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

(1)

式中:ni,1=ni-n1,ni表示系統測量誤差;di,1=di-d1,di表示移動臺到第i個基站的距離,即

(2)

將式(2)代入式(1),并且引入一個中間變量 ，經過整理可得

(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的真實值.系統測量方位角與移動臺坐標和第i個基站坐標有如下的關系:

(6)

整理式(6)可以得到

(7)

(8)

式(7)經化簡合并誤差項可以用矩陣的形式表示為

Hx=K+δ.

(9)

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

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

1.3TDOA和AOA混合定位模型

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

Aθ=q+N.

(10)

N=δ+m′,

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

根據文獻[11]的TSWLS和文獻[12]的CWLS算法,θ可以通過式(11)求得:

s.t.

θTSθ= (x-x1)2+

(11)

(12)

對于式(11),一方面可以根據文獻[11]兩步加權最小二乘求解,結果為

(13)

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

(14)

式中,λ是拉格朗日乘子.通過約束加權最小二乘求解,結果為

(15)

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

(16)

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

1.4奇異矩陣

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

當ATWA出現奇異情況時,式(15)中λ的數學期望為零,即E{λ}=0,因此式(15)的解也是一個異常解.為了清楚上述矩陣的奇異情況,式(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,因為文獻[12]通過式(15)不能給出正確λ值,故無法獲得正確的θ估計值.

2改進CWLS算法

Gη=q-gR1+N.

(19)

根據式(19),SCWLS的價值函數可表示為

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

(20)

(21)

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

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

(22)

式中β是拉格朗日乘子.

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

(23)

根據式(14)和(15),移動臺的估計位置為

(24)

(25)

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

(26)

式中:

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

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

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

從上述公式可以看出沒有出現奇異矩陣ATWA求逆的運算.

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

① 如果兩根一正一負,那選擇正根.

1) 首先置W=IM.

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

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

3仿真結果

(27)

圖1　移動臺坐標為[4.9 5.1]T時的MSE

圖2　移動臺坐標為[2 8]T時的MSE

圖3在1 000次試驗中,移動臺在四個基站所組成方形區域內位置坐標隨機變化的MSE.從圖中可以看到SCWLS具有比TSWLS或者CWLS更小的MSE.由于發射源的位置是隨機的,它可能偶爾靠近[55]T,使得TSWLS和CWLS形成異常情況從而導致更大的MSE.

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

圖3　移動臺坐標為隨機分布下的MSE

圖4　移動臺坐標為[20　8]T時的MSE

4結論

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

參考文獻

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

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

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

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

[3] 范平志.蜂窩網無線定位[M].北京:電子工業出版社,2002:109-123.

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

[5] 鮑君海, 張曉林, 張秀強, 等.一種高精度移動多站無源 定位方法[J].電波科學學報, 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]郝本建, 李贊, 萬鵬武, 等. 傳感器網絡基于特征值分解的信號被動定位技術[J]. 物理學報, 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]章堅武, 唐兵, 秦峰.Chan定位算法在三維空間定位中的應用[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

中圖分類號TN929.53

文獻標志碼A

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

DOI10.13443/j.cjors.2015041901

作者簡介

閆雷兵 (1980-),男,河南人,南京郵電大學電子科學與工程學院在讀博士研究生，主要研究方向為蜂窩無線網絡定位、認知無線電技術.

陸音 (1970-),男,江蘇人,博士,南京郵電大學副研究員,碩士生導師，主要研究方向為無線通信與電磁兼容、認知無線電技術.

張業榮 (1963-),男,安徽人,博士,南京郵電大學電子科學與工程學院教授,博士生導師，主要研究方向為移動通信系統與設計、電磁場的數值計算、UWB信道等.

閆雷兵, 陸音, 張業榮. 基于改進最小二乘算法的TDOA/AOA定位方法[J]. 電波科學學報,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

資助項目: 國家自然科學基金(No.61271236)

聯系人： 張業榮 E-mail:zhangyr@njupt.edu.cn