Chan定位算法與TDOA估計精度的關系

丁宏毅， 柳其許， 王 巍

0 引言

1996年，美國FCC明確要求各移動通信運營商為移動用戶提供E-911服務[1]，因此多個基站利用移動臺無線信號到達時刻 TOA（Time-of-Arrival）[2]和到達時間差 TDOA(Time-Difference-of-Arrival)進行定位的方式在近年來受到了廣泛關注[3-4]。

在眾多基于TDOA的定位算法[5]中，Chan算法[6]得到了廣泛的應用。這主要是因為該算法具備三大優勢：①算法不需要初值；②僅進行兩次迭代就可求得最終結果；③算法的定位精度在視距環境下能夠達到克拉美羅下限。可見，Chan定位算法是一種相當實用的方法，適合實際工程。

Chan利用TDOA觀測值在文獻[6]中分析了算法的估計誤差，但是沒有分析 TDOA觀測值的精度對最終定位精度的影響，也沒有推導一定定位精度下TDOA允許的最大誤差值。本文主要研究定位估計精度與 TDOA估計精度之間的關系，為工程實踐提供理論參考，并進一步提高 Chan算法的實用性。

1 定位估計誤差與TDOA估計精度的關系

本節直接引入 Chan算法及其推導的定位估計誤差的協方差等結果，不再對其進行詳細的解釋。

假設MS當前坐標的真實值為(x0, y0)，Chan算法的估計結果為(?x, ?y)。定位系統中，參與定位的基站數為M，其坐標分別為(xm, ym)，1≤m ≤M。令rm,0表示各基站與MS的真實距離值，即：

由文獻[6]，估計誤差的協方差矩陣為：

其中，c = 3*108(m/s)，且

式（2）中，矩陣Q表示TDOA估計誤差的協方差矩陣，其維數為(M-1)× (M-1)；[.]T表示取矩陣的轉置；[.]-1表示求矩陣的逆。式（3）中，[.](M-1)×2中的下標表示矩陣的二維維數。式（2）的結果同時也表示以第一個基站作為系統的參考基站。

假設M-1個TDOA的估計值都具有相同的方差值大小，且各TDOA估計值之間是相互獨立的，則有：

其中，I(M-1)×(M-1)為(M-1)× (M-1)維的單位矩陣；σ2為 TDOA估計精度的方差。

將式（3）和式（4）代入式（2）中，可得：

其中：

現需對式（5）所表示的2×2階矩陣求逆。

假設λ為式（5）中[.]的行列式的值，則有：

由式（7），可以得到Chan算法的定位估計誤差的方差為：

其中，?D表示Chan算法定位估計的誤差且大于等于0。令：

將式代（9）入式（8），可得：

根據式（10），能夠得到Chan算法定位估計誤差與TDOA估計精度的關系為：

式（11）表示給定?D時TDOA允許的最大估計誤差。因此，本文對其修正，采用下式表示 Chan算法的定位估計誤差與TDOA估計精度的關系：

其中：

2 物理意義和算法流程

式（12）具有的物理含義非常重要。通過分析，本文得到以下幾個結論：

結論1 在給定定位估計誤差?D下，TDOA允許的最大估計誤差和定位系統的拓撲結構存在關聯。在式（13）中，本文采用了余弦的形式表達了系統的拓撲結構，使其更加直觀和清晰。顯然，拓撲結構是由定位系統各基站的布站結構和目標移動臺的位置來共同決定的。它們共同影響著 TDOA允許的最大誤差值。

結論2 當所有的基站與目標手機呈直線排列時，σmax趨向于無窮大。這個結論實際上說明，在此種情況下，無論 TDOA估計的精度有多高，最后的定位誤差都會為無窮大。

結論3 在給定定位估計誤差?D下，TDOA估計精度的要求與基站數有關。由式（13）可以看出，當基站數目不同時，即使在相同的?D下，σmax會可能不同。具體的關系可以從數值仿真中看出。

基于式（12），當給定定位估計誤差?D時，可以求出TDOA允許的最大估計誤差，算法的具體流程如下：

① 確定定位系統的基站坐標和目標手機的坐標；

② 計算式（5）中[.]的行列式值，得到λ；

③ 由式（13），求出TDOA允許的最大估計誤差。

3 仿真和分析

考慮幾種具有對稱結構的定位網絡，坐標的單位都為米。A類（三角形）基站的坐標分別為：(200,200)、(-200,200)和(0,-282.8)，此時M=3；B類（四邊形）基站的坐標分別為：(200,200)、(-200,200)、(-200,-200)和(200,-200)，此時 M = 4；C類（六邊形）基站的坐標分別為：(200,200)、(-200,200)、(-200,-200)、(200,-200)、(-282.8,0)和(282.8,0)，此時 M=6。A1類（三角形）基站的坐標分別為(2000,2000)、(-2000,2000)和(0, -2828)，此時M=3；B1類（四邊形）基站的坐標分別為：(2000,2000)、(-2000,2000)、(-2000,-2000)和(2000,-2000)，此時M=4；C1類（六邊形）基站的坐標分別為：(2000,2000)、(-2000,2000)、(-2000,-2000)、(2000,-2000)、(-2828,0)和(2828,0)，此時M=6。A1類到C1類的坐標值分別是A類到C類坐標值的10倍。

考慮幾種非對稱結構的定位網絡。D類（三角形）基站的坐標分別為：(-200,200)、(0,180)和(-20,-300)；E類（四邊形）基站的坐標分別為：(-200,200)、(0,180)、(-10,-20)和(400,-100)；F類（六邊形）基站的坐標分別為：(-200,200)、(0,180)、(-10,-20)、(400,-100)、(10，200)和(-50,150)。D1 類、E1類和F1類基站的坐標分別是D類、E類和F類坐標值的10倍。

圖 1給出了目標移動臺位置固定為(4,6)時，不同定位網絡在給定定位誤差下TDOA允許的最大估計誤差。圖2給出了目標移動臺的橫坐標在區間[-40 40]，縱坐標在區間[-40 40]之內隨機選取（均勻分布）時，不同定位網絡在給定定位誤差下TDOA允許的最大估計誤差。

從圖1可以看出，對于對稱定位網絡，基線長度對TDOA精度的要求影響很小；非對稱定位網絡，基線長度對 TDOA精度的要求影響很大。圖2表明了當定位系統與移動臺間的拓撲結構發生變化時，TDOA允許的最大誤差的變化情況。圖2同樣說明了對稱定位網絡的基線長度要求比非對稱定位網絡要低。

圖1 移動臺坐標給定時，不同定位網絡TDOA允許的最大誤差值

圖2 移動臺坐標隨機選擇時，不同定位網絡TDOA允許的最大誤差值

4 結語

Chan算法在移動臺定位技術中得到了廣泛的應用和研究。本文推導了Chan算法定位估計誤差和TDOA估計精度之間的關系，通過該關系的表達式可以直接計算出系統所必須的最小時延估計精度，為工程實踐提供理論參考，并進一步提高了Chan算法的實用性。

[1] Reed J H, Krizman K J, Woerrer B D,etal. An Overview of the Challenges and Progress in Meeting the E-911 Requirement for Location Service[J]. IEEE Communication Magazine,1998,36(04)：30-37.

[2] 張毅,羅元,汪經鋒,等.基于移動臺無線定位的研究[J].通信技術,2000(04)：37-40.

[3] Caffery J J Jr, Stuber G L. Overview of Radiolocation in CDMA Cellular Systems[J]. IEEE Communication Magazine,1998,36(04)：38-45.

[4] Christopher D,Malcolm M. Positioning GSM Telephones[J]. IEEE Communication Magazine,1998(36)：46-59.

[5] 羅磊, 田增山,孫冬梅,等.基站幾何布局對定位誤差的影響[J].通信技術,2008,41(02)：126-128.

[6] Chan Y T, Ho K C.A Simple and Efficient Estimator for Hyperbolic Location[J]. IEEE Trans on Signal Processing, 1994,42(08)：1905-1915.