一種基于UWB TDOA定位模式的迭代最小二乘算法

何成文 袁運斌 潭冰峰

1 中國科學院精密測量科學與技術創新研究院大地測量與地球動力學國家重點實驗室，武漢市徐東大街340號，430077 2 中國科學院大學，北京市玉泉路19號甲，100049

對TDOA定位模式下的LOS信號場景的算法研究很多[1-14]，包括兩步加權最小二乘(two-step weighted least squares，TSWLS)算法[1]、線性修正最小二乘(linear-correction least-squares，LCLS)算法[2]、約束加權最小二乘(constrained weighted least squares，CWLS)算法[3-4]、分離約束加權最小二乘(separated CWLS，SCWLS)算法[5]和迭代約束加權最小二乘(iterative CWLS，ICWLS)算法[6]等。但這些方法難以同時兼顧精度和抗噪性能。為此，本文提出一種簡單有效的非約束迭代優化算法，并用實驗驗證其效果。

1 算法描述

結合室內定位的特點，考慮采用N個UWB基準站去定位UWB標簽的2維坐標。假設si=[xi,yi]T為已知UWB基站坐標，u0=[x,y]T為待求標簽位置，通常選擇第1個基站作為參考站，則常規TDOA-LOS定位方程為：

(1)

式中，di,1為標簽到第i個基站和到第1個基站之間的距離差，ηi為均值為0的高斯白噪聲。對式(1)移項后進行平方展開，忽略高斯白噪聲的影響，可將其轉化為線性形式Gu1=h，其中，

(2)

u1=[x,y,R]T

(3)

(4)

由于R與u0和s1之間存在如下關系：

R2=(u0-s1)T(u0-s1)

(5)

因此，傳統CWLS算法[3-5]的表達形式可寫為：

min(h-Gu1)TW(h-Gu1)

s.t.R2=(u0-s1)T(u0-s1)

(6)

式中，W為加權矩陣。

CWLS算法已有較為快速的解法，但在定位精度方面仍存在較大的提升空間。為進一步提高CWLS算法的定位精度和運算速度，并解決約束方程的非凸問題，Qu等[6]提出迭代約束加權最小二乘(ICWLS)算法。該算法通過新的等式變換，將具有非凸特性的CWLS算法表達式轉化成具有凸性的新表達式。盡管仿真實驗證實了該算法的有效性，但在大噪聲環境下卻存在定位發散的缺點。

為解決定位發散的問題，本文提出一種簡單且適用于大噪聲環境下的TDOA定位算法。首先假設基準站坐標位于笛卡爾坐標系原點(即便真實場景中基準站坐標不在原點，也可通過坐標變換來實現)，因此，式(1)可被重新寫為：

(7)

通常在室內環境中，觀測值不會很大且白噪聲較小，而白噪聲的分析常用于計算加權矩陣，由于本文算法不屬于加權類算法，因此可忽略式(7)中噪聲項的影響。利用勾股定理，可將式(7)轉化為：

(di,1+R)2=(x-xi)2+(y-yi)2

(8)

展開移項后可得到：

(9)

令

(10)

(11)

(12)

則式(9)可寫為如下線性形式：

2AR=C-2BX*

(13)

(14)

(15)

當式(15)多次迭代后達到式(16)的迭代停止準則時，即可停止迭代，從而輸出最終定位結果：

(16)

式中，ε為誤差閾值，數值一般比較小。

(17)

通常初值可以由最小二乘算法得到，而最小二乘解是無偏的，因此式(17)中每步迭代解的期望都等于最小二乘解，是無偏估計解。

2 仿真實驗

通常情況下，室內環境相對復雜，視距條件下的基站總數相對有限。為保證UWB定位算法的可行性，僅采用4個UWB基站定位標簽的位置，坐標分別為A1(0,0)、A2(10,0)、A3(10,10)和A4(0,10)，標簽接收來自各個基站的信號中含有均值為0、方差為σ2的高斯白噪聲ηi。由于本文的主要目的是評價算法在大噪聲環境下的性能，故將噪聲方差分別設置為0.1、0.25、0.5、0.75和1以進行綜合評價，將每個噪聲方差下的蒙特卡洛仿真實驗次數和迭代閾值ε分別設置為2 000和0.000 01。

基于Qu等[6]的仿真實驗結論可知，ICWLS算法的定位精度優于TSWLS算法、SDR算法、CWLS算法和迭代似然估計法，因此本文僅選擇該算法與本文算法進行對比。在定位初值方面，2種算法均采用最小二乘解作為迭代初值；在精度評價指標方面，本文采用均方根誤差(RMSE)來評估2種算法的性能，計算公式為：

2.1 實驗1

為充分對比2種算法在邊緣點和中心點處的定位精度，在LOS信號環境下選擇近基站點L1(1, 1)和近中心點L2(5, 6)進行測試，2種算法在測試點處的定位精度見圖1。由圖可知，當噪聲方差σ2≤0.25時，ICWLS算法的精度性能與本文算法大致相同。然而，當σ2>0.25時，ICWLS算法的性能誤差開始急劇上升，而本文算法則緩慢上升，且誤差低于ICWLS算法。因此，總體而言，本文算法在定位精度和抗噪聲性能方面表現更好。

圖1 2種算法在不同點處的定位精度

2.2 實驗2

為進一步測試2種算法的定位精度，在4個基站圍成的矩形區域中隨機生成標簽的位置，實驗結果見圖2。可以看出，本文算法顯著優于ICWLS算法，在數值方面，本文算法的相應誤差大約只有ICWLS算法的一半。此外，實驗發現，本文算法迭代到收斂的平均迭代次數為15次。

圖2 2種算法在隨機點環境下的定位精度

2.3 實驗3

基于實驗1和實驗2的仿真結果，通過定位散點圖來探究ICWLS算法定位性能較差的原因。將標簽位置分別固定在L1(1,1)和L2(5,6)處，并將其噪聲方差分別設為低噪聲σ2=0.1和高噪聲σ2=0.8，結果見圖3。從圖中可以看出，在低噪聲條件下，2種算法的定位坐標基本分布在同一區域內，變化不大；在高噪聲條件下，本文算法的定位結果接近真值，但ICWLS算法的定位結果分布在2個不同的區域，產生嚴重的發散。結合2種實驗場景的定位結果認為，ICWLS算法存在一定的發散現象，這種發散現象在低噪聲環境下不明顯，在高噪聲環境下相對明顯，而本文提出的定位算法具有良好的收斂性和抗噪聲性能。

圖3 2種算法在不同點處的定位坐標

由此認為：1)本文提出的算法優于ICWLS算法；2)無論噪聲方差是多少，本文算法的定位結果都與真實位置更接近，說明本文算法具有良好的抗噪聲性能；3)ICWLS算法存在定位發散的缺點，這可能是其定位性能不如本文算法的根本原因。

3 結 語

針對傳統TDOA算法因抗噪性能弱而導致定位發散的缺點，本文提出一種簡單的TDOA定位算法。該算法首先將TDOA定位方程轉化為LS形式來得到初始解，然后通過迭代思想得到收斂坐標。本文算法原理簡單、抗噪聲性能好、易于實現，可推廣到工業領域，且仿真結果也驗證了本文算法具有可行性和有效性，定位精度優于ICWLS算法。