基于改進TDOA算法的設(shè)計與仿真

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

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

0 引 言

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

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

1 TDOA算法

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

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

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

2 改進TDOA算法

2.1 速度受限定位算法

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

圖1 定位目標(biāo)移動軌跡示意圖

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

2.2 區(qū)域受限定位算法

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

圖2 區(qū)域受限定位算法分析示意圖

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

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

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

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

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

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

式中：

P1和P2為區(qū)域UR1和UR2。Pi（i ＝1，2）的確定可依據(jù)目標(biāo)離門邊界點Dk的距離，可得：

設(shè)Fi＝［gk，hk］，根據(jù)三角形相似定理可得：

化簡可得：

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

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

2.3 改進TDOA算法

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

圖3 改進TDOA算法流程圖

詳細(xì)步驟如下：

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

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

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

步驟4步驟3 中的修正值即為改進TDOA算法的優(yōu)化結(jié)果。

3 實驗結(jié)果

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

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

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

圖5 目標(biāo)最大移速對定位精度的影響

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

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

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

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

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

4 結(jié) 語

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