基于改進TDOA算法的設計與仿真

吳端坡， 李俊杰， 許曉榮， 馮 維， 劉兆霆

（杭州電子科技大學通信工程學院，杭州310018）

0 引 言

隨著移動通信和無線傳感技術的發展，基于位置的服務應用廣泛［1］。眾所周知，人們在室內環境下的活動時間占據其生活極大比重。人們希望可以獲得更加精準的室內位置信息。一種比較常見且簡單有效的定位方法是到達時間差（Time Difference of Arrival，TDOA）［2-3］算法，它是一種基于測距的定位方法，通過測量節點間的距離信息來計算節點的位置，其對定位基站與移動目標之間的時鐘同步要求不是十分嚴格。本文選取不要求基站和移動目標之間嚴格同步的TDOA算法，使得其應用范圍更加廣泛。

TDOA算法在定位領域廣泛應用，但傳播信號受非視距等因素的影響，定位精度不可避免地有所降低。為減小定位誤差，Kolakowski［4］利用TDOA計算結果以及相應加速度計測量值來優化定位精度。Li 等［5］分析TDOA算法與非視距（Non-line-of-sight，NLOS）的相關性來定位靜態目標問題。Choi 等［6］在時間遞歸的魯棒最小二乘估計框架下，提出了一種TDOA 位置估計器。該法可以將一組不同時間的測量值遞歸地組合在一起，產生更精確的定位結果。Yang 等［7］提出了一種考慮視距的TDOA改進方法，引入一個傳遞函數，將給定接收機的場與源的場作為頻率和位置的函數聯系起來，緩解了NLOS效應，并將傳播通道校準回自由空間。Kim［8］則將障礙物信息考慮進去，提出了一種合理、時間有效的輻射源估計方法。從上述的算法設計中，可以發現它們對定位區域范圍、行人最大移動速度等實驗環境的固有信息運用很少。本文在TDOA算法的基礎上引入了速度受限和區域受限的定位模型，提出基于速度和區域受限的改進TDOA 算法，并在Matlab仿真平臺上進行驗證。

1 TDOA算法

TDOA［9-10］算法是對到達時間（Time of Arrival，TOA）算法的改進，它不是直接利用信號到達時間，而是用多個基站接收到信號的時間差［11-12］來確定移動臺位置，與TOA算法相比，它不需要加入專門的時間戳，定位精度也有所提高。

假定室內基站位置為A1（0，0）、A2（m2，0）和A3（m3，n3），移動目標位置為（xt，yt），t 為采樣間隔可得［13-14］：

式中：R1，t、R2，t和R3，t分別為基站與移動目標之間的距離。求解式（1）可得目標位置（xt，yt）。

2 改進TDOA算法

2.1 速度受限定位算法

由先驗知識可知，實際室內環境是復雜多變的（如錯落的桌椅、人流等），人們在室內移動速度緩慢，可視為一種低速的移動狀態，即速度受限狀態。假設使用速度受限算法優化和未優化的定位結果分別為Tt（xt，yt）和，目標移動軌跡如圖1 所示。圖中：dt，t-1為Tt和T′t之間的距離；和分別平行于y軸和x 軸，D 為它們的交點。若目標最大移動速度為vmax，采樣頻率為f，則目標單位采樣間隔內的最大移動距離為dmax＝vmax／f。

圖1 定位目標移動軌跡示意圖

如果dt，t-1的值大于目標的最大移動距離為dmax，那么Tt將會約束到圖1 中的T′t點。根據相似三角形定理，可得：

2.2 區域受限定位算法

室內環境中存在有一些不可逾越的障礙，包括床、衣柜和墻壁等。室內環境可以看作是有限的區域。將區域受限定位算法分為內部移動和區域轉換兩個案例。并將算法的研究場景設置為矩形區域。

圖2 區域受限定位算法分析示意圖

分析內部移動場景，算法分析示意如圖2 所示。圖中：Bi（i ＝1，2，3，4）為區域邊界點；Tt和分別表示使用和未使用區域受限定位算法的定位結果；D1D2為房門；I1和I2分別為射線D1和射線D2與圓T′t-1的交點；R1和R2分別為線段T′t-1Tt與墻壁的交點和線段TtD2與圓D2的交點；UR1和UR2為陰影區域。wi（i ＝1，2，3，4）根據直線B1B3和B2B4將可移動區域外圍分為4 個部分。

若假設目標移動時，不存在房門D1D2，那么根據區域邊界的限制，需將Tt點約束到R1，該點即為修正點T′t。根據相似三角形定理，可得：

式中，J 為線段T′tR1和T′tTt的比值。化簡式（4）可得：

式中，wi（i ＝1，2，3，4）為目標所在不可移動的區域，可以根據離目標最近兩相鄰拐點和最小值決定。因而，可得：

式中，i與c（i）為相鄰拐點。

其次，分析區域轉化場景下的定位修正方法。若邊界B2B3存在房門D1D2，那么目標除了UR1和UR2區域，其他都可能到達。若目標超出可移動區域邊界，則將其約束到圓Dk（Dk表示門的邊界點，k ＝1，2）上的R2點，那么該點即為所求的修正點。若G 為線段和DkTt線段的比值，那么G的值為：

式中：

P1和P2為區域UR1和UR2。Pi（i ＝1，2）的確定可依據目標離門邊界點Dk的距離，可得：

設Fi＝［gk，hk］，根據三角形相似定理可得：

化簡可得：

故而，區域受限定位算法可整理為：

式中：w ＝w1∪w2∪w3∪w4；p ＝ ｛（x，y）｜ （x -g1）2＋。

2.3 改進TDOA算法

速度受限定位算法適用于區域內部的目標定位，而區域受限定位算法適用于區域邊界的目標定位，所以將兩種算法融合使用可以更好地實現室內目標的定位功能。利用TDOA算法獲得目標定位坐標信息。使用速度受限定位算法分析目標的可移動區域，根據其與上一定位點之間的距離dt，t-1，判斷目標點是否超過最大移動距離閾值dmax。若超過閾值，則將目標點約束到同方向、距離上一定位點dmax的位置，該點即為速度受限定位算法的修正結果。將該結果傳入區域受限定位算法進行進一步約束，以修正穿墻的異常定位點，并將目標的可移動區域進一步細化，進一步修正定位結果。算法流程如圖3 所示。

圖3 改進TDOA算法流程圖

詳細步驟如下：

步驟1使用式（1）計算得目標位置Tt（xt，yt）。

步驟2分析dmax和dt，t-1之間的大小，將Tt的值代入式（3）中修正超出可移動范圍的異常值。

步驟3分析｜T′tDk｜和dmax的大小，若｜T′tDk｜ ＜dmax，根據式（9）計算k，代入式（8）得到G。將G 和步驟2 中得到的修正值代入式（11）中可得區域受限定位算法優化后的修正值。若｜T′tDk｜＞dmax，則根據式（7）計算i，將其代入式（6）確定J，將J 和步驟2 中得到的修正值代入式（5）得區域受限定位算法優化后的修正值。

步驟4步驟3 中的修正值即為改進TDOA算法的優化結果。

3 實驗結果

本文分析了影響定位精度的3 種因素，分別為測量誤差、目標最大移動速度和采樣頻率。本文設置的實驗環境為10 m×10 m的正方形區域，實驗的測量誤差設置為0.1 m，目標的最大移動速度為1 m／s，采樣頻率為10 Hz。對比算法為TDOA算法。

本實驗定位目標的移動軌跡設置為B1-B2-B3，如果分別控制目標的測量誤差、采樣頻率和最大移動速度的變化，可以得到3 組數據進行分析。平均定位誤差（Mean Positioning Error，MPE）eMPE與測量誤差（Measuring Error，ME）eME變化關系仿真結果如圖4 ～6 所示。

圖4 測量誤差對定位精度的影響

圖5 目標最大移速對定位精度的影響

圖6 采樣頻率對對定位精度的影響

由圖4 可見，改進TDOA 算法和速度受限定位算法受測量誤差的影響不大，而區域受限定位算法和TDOA算法則隨測量誤差的增大而增大。改進TDOA算法平均定位誤差一直保持最小，定位精度最高。

由圖5 可見，改進TDOA 算法和速度受限定位算法都隨著移動速度的提高而不斷增大，而區域受限定位算法和TDOA算法則不受移動速度的影響，基本保持不變。明顯可以看到改進TDOA算法有著最好的定位精度。

由圖6 可見，改進TDOA 算法和速度受限定位算法都隨著采樣頻率的提高而不斷減少，而區域受限定位算法和TDOA算法則不受采樣頻率的影響，基本保持不變。總體而言，改進TDOA 算法的平均定位誤差最小，定位精度最高。

總之，當測量目標的測量誤差、目標最大移動速度和采樣頻率發生改變時，改進TDOA 算法都保持這最低的平均定位誤差，有著最高的定位精度，減弱了非視距等環境因素對定位精度的影響。

4 結 語

本文提出了一種基于速度受限和區域受限的改進TDOA算法。仿真結果表明，該算法可以明顯改善非視距等環境因素對TDOA算法定位結果的影響。并且通過對改進TDOA算法的虛擬仿真，可以啟發學生對實驗仿真方法和改進方法的思考。