一種基于數學模型的TDOA定位算法

杜娟 李時文

基金項目：“國家質檢總局科技計劃項目（2012QK244）”。

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

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

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

1 基于數學模型的TDOA算法

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

圖1 TDOA定位原理圖

設BS1，BS2，BS3的坐標分別為（X1，Y1）， （X2，Y2）， （X3，Y3），接收時候分別為t1，t2，t3；

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

（1）

（2）

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

1）將坐標原點平移至最先收到信號的基站（x1，y1），將（x1，y1），（x2，y2），（x3，y3）轉換成相對坐標（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，解方程即可得到目標的相對坐標，將相對坐標轉化為絕對坐標即為所求。

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

基于數學模型的TDOA算法實現。本文實現的定位系統是通過TDOA方式，借助定位AP、WiFi電子標簽和預設的地圖與場地模型信息，實現對電子標簽的定位功能。系統結構如圖2所示，系統由多個無線接入點、一個定位服務器和一個帶有WiFi接口的終端組成。當終端發出定位請求時，各AP的時間處理模塊記錄信號到達時間點并上報服務器。由定位服務器根據算法計算出終端所在的位置。其主要功能包括以下兩個方面：

1）在同一系統中實現所有AP的時間同步。利用各AP坐標已知，用專用的WiFi終端在某個已知位置點發送數據；AP接收到定位終端的數據并上報服務器，由服務器根據AP和已知終端的坐標計算相對某固定AP的時間差，即為各AP的同步時間誤差。

2）實際定位時，服務器將某個時候各AP發送的接收時候減去該AP對應的同步時間誤差，即可求出某時候終端信號到達各AP的時間差，然后根據算法求出坐標。

圖2 系統結構圖

程序中實現的基于數學模型的TDOA算法，用threePointDoCal（）函數來封裝，其核心代碼如下：

//根據3個AP接收到終端的時間差計算坐標

int threePointDoCal（CParam_TDOA* tagParam， Coordinate& result）

{

//根據時間差計算距離差

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

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

//將絕對坐標轉換成相對坐標

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 實驗結果與性能分析

為了測試系統性能，獲得定位算法的精度，搭建實驗環境如圖3所示。為了表示測試點位置和實際目標點的真實位置，系統以圖的左下角為坐標原點，水平向右為X軸正向，垂直向上為Y軸正向建立直角坐標系，長度以厘米為單位。經測量AP1，AP2，AP3的位置分別為（1329，807），（3386，807），（2370，2663）。

圖3 實驗場景圖

實驗過程中一共選取了5個點進行測試，詳細數據如表1所示。從實驗結果分析，本文設計的算法在實驗環境中定位精度在1米之內，在3個AP構成的區域外定位精度相對較低。與傳統的RSSI算法[9]和Chan算法等相比，定位精度有明顯的提高；且該算法不存在遞歸運算，也不存在似然估計中大量的矩陣運算，因而計算量小，具有良好的實用性能。

在無線定位技術迅速發展的今天，如何提供高效的、可靠的高精度定位服務成為新的研究熱潮。本文從數學模型出發，提出了一種基于TDOA的定位算法，并通過實驗來驗證該算法具有定位精度高、計算量小且容易實現等優點，在電波環境較好的區域具有良好的實用性。

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