一種基于數(shù)學(xué)模型的TDOA定位算法

杜娟 李時文

基金項(xiàng)目：“國家質(zhì)檢總局科技計(jì)劃項(xiàng)目（2012QK244）”。

近年來隨著無線局域網(wǎng)（WLAN）的興起，以及支持WIFI接入的移動終端的普及，基于WLAN的各種應(yīng)用得到迅速發(fā)展，基于WLAN的無線定位技術(shù)也引起了國內(nèi)外學(xué)者的廣泛關(guān)注[1]。目前，現(xiàn)有無線定位技術(shù)主要基于TOA（Time of Arrival）， AOA （Angle of Arrival），RSSI（Received Signal Strength Indicator）和TDOA（Time Difference of Arrival）等定位技術(shù)[2-3]。TOA定位時要求基站和移動終端之間有非常精確的同步時鐘，這一點(diǎn)實(shí)現(xiàn)起來相當(dāng)困難。AOA方法受限于非視線問題對信號傳播的影響，且需要增加額外的硬件設(shè)備用于角度測量。

基于RSSI 的方法定位精度不夠，受無線電波傳播環(huán)境的影響非常大。基于TDOA的定位算法，只要求基站間同步，而不要求基站與移動終端間同步。基站位置是固定的，基站間實(shí)施同步比移動終端與基站間同步要容易。因此，TDOA定位相比其他方法更具有適用性，應(yīng)用也相對廣泛。由于TDOA 方程組是非線性方程組，通常需要先將其轉(zhuǎn)化為線性方程組后再求解。Y. T. Chan 提出了一種兩步最大似然估計(jì)算法[4-5] ，該算法在高斯噪聲下具有較好的定位估計(jì)，但是當(dāng)誤差較大時，特別是存在NLOS 誤差時，其定位性能顯著下降。泰勒級數(shù)展開法具有定位精度高、頑健性強(qiáng)的優(yōu)點(diǎn)，但是需要迭代運(yùn)算的初始值必須接近真值，否則就會導(dǎo)致算法不收斂[6]。另外，上述算法都存在參與計(jì)算的基站數(shù)較少時（3個）定位精度明顯下降，而參與計(jì)算的基站較多時計(jì)算量大的問題。

本文首先介紹時差定位的基本原理，然后取3個基站得出非線性方程組并進(jìn)行線性化處理，求解方程組；利用移動臺到達(dá)時間的先后，將計(jì)算結(jié)果代入原方程組、剔除不符合要求的解。最后編碼實(shí)現(xiàn)了該算法，并通過實(shí)驗(yàn)驗(yàn)證了該算法的定位精度與性能。

1 基于數(shù)學(xué)模型的TDOA算法

TDOA定位的基本原理。TDOA定位算法又稱為雙曲線定位，它是定位目標(biāo)向多個基站發(fā)送信號，從第一個接收到信號的基站處開始計(jì)時，分別記錄下信號到達(dá)其余各個基站的時刻，這些時刻便是第一個接收到信號的節(jié)點(diǎn)與其余節(jié)點(diǎn)信號到達(dá)的時間差，根據(jù)這些時間差可以列出雙曲線方程組。目標(biāo)位置將位于以兩個接收基站為焦點(diǎn)的雙曲線的某一分支上，確定目標(biāo)的二維坐標(biāo)需要兩個或以上雙曲線方程，兩個雙曲線的交點(diǎn)即為定位目標(biāo)的二維位置坐標(biāo)。因此TDOA定位最少需要3個基站。在通常情況下，一般兩個雙曲線會交于兩點(diǎn)，但利用一些先驗(yàn)知識可剔除其中不符合要求的一點(diǎn)。其定位原理如圖1所示。

圖1 TDOA定位原理圖

設(shè)BS1，BS2，BS3的坐標(biāo)分別為（X1，Y1）， （X2，Y2）， （X3，Y3），接收時候分別為t1，t2，t3；

目標(biāo)位置坐標(biāo)為（X，Y），c為電波傳播速度，則可列方程組如下：

（1）

（2）

基于數(shù)學(xué)模型的TDOA算法設(shè)計(jì)。求解以上雙曲線方程組就可得到目標(biāo)終端的估計(jì)位置。由于雙曲線方程組不是線性方程組，因此，求解它并不容易。目前，己經(jīng)提出了多種具有不同精度和計(jì)算復(fù)雜性的TDOA無線定位算法[7，8]。本文將詳細(xì)介紹一種基于數(shù)學(xué)模型的TDOA定位算法，并用實(shí)驗(yàn)數(shù)據(jù)來驗(yàn)證算法的性能和精度。其算法的詳細(xì)設(shè)計(jì)過程如下：

1）將坐標(biāo)原點(diǎn)平移至最先收到信號的基站（x1，y1），將（x1，y1），（x2，y2），（x3，y3）轉(zhuǎn)換成相對坐標(biāo)（0，0），（X1，Y1），（X2，Y2），令d1 = c（t2 - t1），d2 = c（t3 - t1）簡化方程組為：

（3）

（4）

2）將（3）式平移、開方化簡得：

（5）

將（4）式平移、開方化簡得：

（6）

3）令，，（6） - （5）得

（7）

令， 得 X = a – bY，代入（3）式化簡得

（8）

4）令，，，可得AY2 + BY + C = 0，解方程即可得到目標(biāo)的相對坐標(biāo)，將相對坐標(biāo)轉(zhuǎn)化為絕對坐標(biāo)即為所求。

根據(jù)如上算法所求的目標(biāo)位置理論上存在無解，有唯一解，有兩解三種情況，但實(shí)際的目標(biāo)位置是唯一的。對于無解的情況，從圖1的定位原理圖來分析，式（1）和式（2）所對應(yīng)的雙曲線必有一個公共焦點(diǎn)，且離心率相同。只要不存在三個基站位于同一直線的情況，二條雙曲線必然相交，即雙曲線方程組有解。該文原載于中國社會科學(xué)院文獻(xiàn)信息中心主辦的《環(huán)球市場信息導(dǎo)報(bào)》雜志http：//www.ems86.com總第539期2014年第07期-----轉(zhuǎn)載須注名來源對于有二解的情況，由于在列方程時，已選定最先到達(dá)的基站為相對坐標(biāo)原點(diǎn)，故d1、d2均應(yīng)大于等于零，利用這一先驗(yàn)條件可以過濾掉不符合要求的解。

基于數(shù)學(xué)模型的TDOA算法實(shí)現(xiàn)。本文實(shí)現(xiàn)的定位系統(tǒng)是通過TDOA方式，借助定位AP、WiFi電子標(biāo)簽和預(yù)設(shè)的地圖與場地模型信息，實(shí)現(xiàn)對電子標(biāo)簽的定位功能。系統(tǒng)結(jié)構(gòu)如圖2所示，系統(tǒng)由多個無線接入點(diǎn)、一個定位服務(wù)器和一個帶有WiFi接口的終端組成。當(dāng)終端發(fā)出定位請求時，各AP的時間處理模塊記錄信號到達(dá)時間點(diǎn)并上報(bào)服務(wù)器。由定位服務(wù)器根據(jù)算法計(jì)算出終端所在的位置。其主要功能包括以下兩個方面：

1）在同一系統(tǒng)中實(shí)現(xiàn)所有AP的時間同步。利用各AP坐標(biāo)已知，用專用的WiFi終端在某個已知位置點(diǎn)發(fā)送數(shù)據(jù)；AP接收到定位終端的數(shù)據(jù)并上報(bào)服務(wù)器，由服務(wù)器根據(jù)AP和已知終端的坐標(biāo)計(jì)算相對某固定AP的時間差，即為各AP的同步時間誤差。

2）實(shí)際定位時，服務(wù)器將某個時候各AP發(fā)送的接收時候減去該AP對應(yīng)的同步時間誤差，即可求出某時候終端信號到達(dá)各AP的時間差，然后根據(jù)算法求出坐標(biāo)。

圖2 系統(tǒng)結(jié)構(gòu)圖

程序中實(shí)現(xiàn)的基于數(shù)學(xué)模型的TDOA算法，用threePointDoCal（）函數(shù)來封裝，其核心代碼如下：

//根據(jù)3個AP接收到終端的時間差計(jì)算坐標(biāo)

int threePointDoCal（CParam_TDOA* tagParam， Coordinate& result）

{

//根據(jù)時間差計(jì)算距離差

dis_2 = calDiffDistance（tempParams[2]，tempParams[0]）；

dis_1 = calDiffDistance（tempParams[1]， tempParams[0]）；

//將絕對坐標(biāo)轉(zhuǎn)換成相對坐標(biāo)

X2 = calRelativeValue（apInfo[0].m_horiCoor， apInfo[2].m_horiCoor）；

X1 = calRelativeValue（apInfo[0].m_horiCoor， apInfo[1].m_horiCoor）；

Y2 = calRelativeValue（apInfo[0].m_vertCoor， apInfo[2].m_vertCoor）；

Y1 = calRelativeValue（apInfo[0].m_vertCoor， apInfo[1].m_vertCoor）；

DIS_2= sqrt（dis_2*dis_2 - H2*H2）；

DIS_1= sqrt（dis_1*dis_1 - H1*H1）；

if（DIS_2 == DIS_1 && DIS_2！=0）{ DIS_2 += 5； }

if（DIS_2 ！= 0） { c2 = （X2*X2 + Y2*Y2 - DIS_2*DIS_2）/（2*DIS_2）； }

if（DIS_1 ！= 0） { c1 = （X1*X1 + Y1*Y1 - DIS_1*DIS_1）/（2*DIS_1）； }

a = （DIS_2*DIS_1*（c2-c1））/（DIS_1*X2-DIS_2*X1）；

b = （DIS_1*Y2-DIS_2*Y1）/（DIS_1*X2-DIS_2*X1）；

float A = （（b*X2 -Y2）/DIS_2）*（（b*X2-Y2）/DIS_2）-b*b -1；

float B = 2*（（c2-a*X2/DIS_2）*（（b*X2-Y2）/DIS_2）+a*b）；

float C = （c2-a*X2/DIS_2）*（c2-a*X2/DIS_2）-a*a；

double deitar = B*B-4*A*C；

if（deitar < 0） { return RETURN_ERROR； }

else if（deitar == 0）

{

Y = （int）（-B/（2*A））；

X = （int）（a-b*Y）；

s_point1.m_X = （int）calabsoluteValue（apInfo[0].m_horiCoor， X）；

s_point1.m_Y = （int）calabsoluteValue（apInfo[0].m_vertCoor， Y）；

}

else

{

Y = （int）（（-B + sqrt（deitar））/（2*A））；

X =（int）（a - b*Y）；

s_point1.m_X = （int）calabsoluteValue（apInfo[0].m_horiCoor， X）；

s_point1.m_Y = （int）calabsoluteValue（apInfo[0].m_vertCoor， Y）；

Y = （int）（（-B - sqrt（deitar））/（2*A））；

X =（int）（a - b*Y）；

s_point2.m_X = calabsoluteValue（apInfo[0].m_horiCoor， X）；

s_point2.m_Y = calabsoluteValue（apInfo[0].m_vertCoor， Y）；

}

}

2 實(shí)驗(yàn)結(jié)果與性能分析

為了測試系統(tǒng)性能，獲得定位算法的精度，搭建實(shí)驗(yàn)環(huán)境如圖3所示。為了表示測試點(diǎn)位置和實(shí)際目標(biāo)點(diǎn)的真實(shí)位置，系統(tǒng)以圖的左下角為坐標(biāo)原點(diǎn)，水平向右為X軸正向，垂直向上為Y軸正向建立直角坐標(biāo)系，長度以厘米為單位。經(jīng)測量AP1，AP2，AP3的位置分別為（1329，807），（3386，807），（2370，2663）。

圖3 實(shí)驗(yàn)場景圖

實(shí)驗(yàn)過程中一共選取了5個點(diǎn)進(jìn)行測試，詳細(xì)數(shù)據(jù)如表1所示。從實(shí)驗(yàn)結(jié)果分析，本文設(shè)計(jì)的算法在實(shí)驗(yàn)環(huán)境中定位精度在1米之內(nèi)，在3個AP構(gòu)成的區(qū)域外定位精度相對較低。與傳統(tǒng)的RSSI算法[9]和Chan算法等相比，定位精度有明顯的提高；且該算法不存在遞歸運(yùn)算，也不存在似然估計(jì)中大量的矩陣運(yùn)算，因而計(jì)算量小，具有良好的實(shí)用性能。

在無線定位技術(shù)迅速發(fā)展的今天，如何提供高效的、可靠的高精度定位服務(wù)成為新的研究熱潮。本文從數(shù)學(xué)模型出發(fā)，提出了一種基于TDOA的定位算法，并通過實(shí)驗(yàn)來驗(yàn)證該算法具有定位精度高、計(jì)算量小且容易實(shí)現(xiàn)等優(yōu)點(diǎn)，在電波環(huán)境較好的區(qū)域具有良好的實(shí)用性。

（作者單位：1.濟(jì)寧市衡器管理所；2.濟(jì)寧市山推公司）