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

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

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

0 引 言

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

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

1 TDOA算法

TDOA［9-10］算法是對到達(dá)時(shí)間（Time of Arrival，TOA）算法的改進(jìn)，它不是直接利用信號(hào)到達(dá)時(shí)間，而是用多個(gè)基站接收到信號(hào)的時(shí)間差［11-12］來確定移動(dòng)臺(tái)位置，與TOA算法相比，它不需要加入專門的時(shí)間戳，定位精度也有所提高。

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

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

2 改進(jìn)TDOA算法

2.1 速度受限定位算法

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

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

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

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

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

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

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

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

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

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

式中，i與c（i）為相鄰拐點(diǎn)。

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

式中：

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

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

化簡可得：

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

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

2.3 改進(jìn)TDOA算法

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

圖3 改進(jìn)TDOA算法流程圖

詳細(xì)步驟如下：

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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