基于聚類和TDOA的無線基站定位算法研究*

方煥陽，李 燁

（上海理工大學 光電信息與計算機工程學院，上海 200093）

0 引 言

隨著無線通信網絡和移動互聯網的蓬勃發展，提供基于地理位置信息的服務（Location Based Service，LBS）已經成為最具市場前景和發展潛力的業務之一。從傳統的GPS導航到大眾點評、微信等基于地理位置的消費信息服務和社交軟件，實現其功能的基礎就是要通過手機、導航儀等終端設備收發信號，以獲得距離、角度等測量信息，并利用定位算法將這些測量信息轉換成坐標信息。以全球定位系統（Global Positioning System，GPS）為代表的衛星定位技術盡管已能在室外開闊環境下提供高精度的定位服務，但在室內、地下等封閉環境，由于衛星定位信號受到障礙物阻擋、存在多徑傳播等影響，難以有效定位[1]。這些應用環境大多位于市區，運營商通信基站分布較為密集，因此基于通信基站的定位系統能夠發揮其優勢。依托無線定位技術的發展，基于地理位置信息的服務可以實現高精度導航、室內定點業務推送、大數據分析、人流疏導及客流分析、智能安防管理等新型業務，具有廣闊的應用前景[2]。此外，無線通信基站的定位系統能夠彌補GPS系統無法精確定位 的盲區。

無線網絡中，定位問題的研究涉及許多技術[3]和理論[4]，國內外科研工作者做出了大量貢獻。目前，主要存在三類非視距誤差抑制的定位算法。第一類，試圖對非視距誤差進行精確建模，然后根據所建模型估計移動終端（MS）的位置[5-6]。由于實際中很難得到一個精確的非視距模型用于描述復雜多變的傳輸環境，這一類算法難以廣泛應用。第二類算法認為，LOS傳輸的基站有別于NLOS傳輸的基站，因而可以識別NLOS基站，最后只利用LOS基站進行位置估計[7-8]。此類算法需要實際環境中存在一定數目的LOS基站，且NLOS基站識別的虛警率無法控制，因此難以確保定位精度。第三類算法嘗試對測量距離或中間估計量進行加權，權值來源于基站和終端之間的幾何關系和代數關系。該類算法最典型的是以殘差為代價函數，以真實距離和測量距離之間的關系為約束條件建立最優化問題，終端的位置估計可以通過解決該問題獲得[9-11]。這一類算法的優點在于無論MS處于何種環境，總可以估計其位置，但缺點是估計精度并不高。針對基于通信基站的無線定位技術中存在的上述問題，本文提出基于聚類和TDOA的基站定位優化算法，從而提高NLOS環境下的定位精度，并通過多組仿真實驗檢驗其性能，以滿足日益增長的定位導航應用需求。

1 無線定位技術

1.1 無線定位技術分類

基于基站的無線定位方法如果按測量值的種類進行歸類，主要可分為Cell-ID定位、場強模型定位、到達時間定位、到達時間差定位和入射角定位技術等。本文將采用聚類算法對到達時間差定位技術進行研究與優化。

1.2 TDOA定位基本原理

TDOA定位技術又稱雙曲線相交法，通過測量目標源信號到達多個傳感器的時間差值即時差，確定相應的距離差值，可以表示為一組雙曲線方程。由于到達時間差方法只要求各探測傳感器之間時間同步，不要求目標源與傳感器之間時間同步，因而實用性較強[12]。

到達時間差定位技術利用移動終端到各基站的時間差的測量值乘以無線電波的傳播速度，得到移動終端到各定位基站的距離差值，然后在此基礎上對移動終端進行定位。幾何學中，平面上一個動點到兩個定點的距離差為一常數的軌跡是一條雙曲線。由于它的定位原理與雙曲線類似，因此該方法被稱為基于雙曲線模型的TDOA定位。

基于到達時間差定位的原理，如圖1所示。

圖1 基于到達時間差定位的原理

假設移動終端MS到基站BS1、BS2、和BS3的距離分別為R1、R2和R3。選取BS1為定位服務基站，通過計算BS1、BS2與MS的距離差R2,1=R2-R1，確定一組以基站BS1、BS2為焦點，且與這兩個基站的距離差為R2,1的雙曲線。在蜂窩網絡中，利用不同基站接收機間的到達時間得到時間差（TDOA），然后將該時間差乘以信號的傳播速度得到距離差R2,1。通過兩個基站能得到一組雙曲線，而要對MS進行定位至少需要兩條雙曲線且兩者相交，因此實際定位過程中必須有兩組基站，即至少需要三個定位基站進行定位。

假設有二維定位模型如下：蜂窩網絡中共有M個基站，其中基站BS1為服務基站，系統經過測量得到各基站與服務基站BS1的差分到達時間。設MS的二維平面坐標為(x,y)，各定位服務基站的坐標為(xi,yi)(i=1,2,…,M)，那么MS與第i個定位基站間的距離可表示為：

第i個定位基站到MS的距離與服務基站到MS的距離的差可表示為：

其中，c表示無線電波的速度，di表示第i個定位基站與MS的距離，τi,1表示MS與基站BS1和BS2的到達時間差值。以此類推，多個基站組合可得到多個方程，聯立M-1個雙曲線方程的非線性方程組并計算，即可獲得移動終端的坐標信息。

2 經典Fang算法

Fang算法是一種具有解析表達式解的算法，通過對雙曲線方程進行線性近似，估計移動終端的坐標信息。

對于二維平面定位，假設基站的坐標信息為基站1(0,0)、基站2(X2,0)和基站3(X3,Y3)。Fang算法將雙曲線模型計算公式簡化如下：

其中：

式（3）與式（4）相減，消去R1簡化，有：

式中：

將式（8）代入（4）并化簡，可得：

式中：

對式（11）進行求解，即可獲得移動實體的橫坐標x：

代入式（8）并計算，可獲得移動終端的縱坐標y。利用該算法求解可能會出現一個解或雙解的情況。若所求解唯一，所求結果即為移動終端的位置估計；若所求結果為雙解，可利用先驗知識選取較精確的位置坐標。此外，可根據基站服務小區的范圍設置移動終端坐標的閾值，篩選出閾值范圍內的定位結果，進一步提高無線定位的精確度，并提高算法的運行效率。

3 基于聚類思想的TDOA定位改進算法

聚類是無監督學習的一種重要形式，主要任務是將數據對象分為多個類或簇，而同一簇內的數據對象相似度盡可能大，不同簇間的數據對象相似度盡可能小。其中，K-means聚類是解決聚類問題的一種經典算法。

目前，對NLOS誤差的識別與抑制是基于通信基站定位技術的重點與難點。由于LOS環境下的誤差服從均值為0的高斯分布，且NLOS環境下的誤差遠大于LOS環境下的測量誤差，因此通過視距環境下的測量值求得的定位結果往往集中在某一區域內且接近真實值，而通過NLOS環境下的測量值求得的定位結果則相對分散。根據這一特性，本文對測量結果進行聚類分析，從中找出定位結果最集中的最大類簇。對測量結果進行多次聚類，取每次聚類最大簇的交集作為最終的類簇，則該類簇中的定位結果取平均會更接近移動終端的真實位置。

基于K-means聚類的改進算法中，采用多個基站組合獲得TDOA，利用Fang算法求出移動終端的多個估計位置，通過對這些估計位置進行聚類。本文算法將輸入數據表示為移動終端所有估計位置去除誤差解后的數據集合X={x1,x2,…,xn}，聚類數目為k，那么對應的輸出為k個類簇Cj（其中j=1,2,…,k）。

具體步驟如下：

（1）從數據集合X中隨機選擇k個數據點，將這些數據點分別看做k個類簇的初始聚類中心(m1,m2,…,mk)；

（2）對于數據集合中的每個數據點，找到最接近該點的聚類中心，并把它劃分到該類簇中；

（5）判斷收斂性，如果j值收斂，那么輸出聚類中心(m1,m2,…,mk)，算法結束；否則，轉至步 驟（2）；

（6）對上述步驟進行i次聚類，每次聚類結束后選取最大的簇mmax,i∈X，其中mmax,i表示第i次聚類最大簇包含的估計位置數據點；

（7）篩選完離群點后位置估計的數據集合Z={Xa,Xa+1,…,Xb}=mmax,1∩mmax,2∩…∩mmax,i，其 中1≤a≤b≤n；

（8）數據集合Z的平均值即為最終的輸出定位結果。

本文算法定位流程，如圖2所示。

圖2 本文算法流程

4 仿真實驗

本文主要針對基于K-means聚類的定位改進算法和經典Fang算法進行仿真對比，采用定位誤差CDF曲線67%位置的誤差值分析算法的定位性能。

基站與移動終端的位置分布如圖3所示，假設系統中定位基站的數量為7，各基站呈正六邊形的拓撲結構進行分布。其中，定位服務基站處于中心，移動終端在服務小區內均勻分布，小區半徑為R，基站的坐標分別表示為：

待定位的移動終端均勻分布在圖3網格部分所示的區域內，選取其中200個位置進行仿真分析。定位基站提供的TDOA的測量誤差服從高斯分布，均值為μ（通常為0）、標準差為σ。為了便于分析，TDOA測量誤差用時間測量誤差乘以信號傳播速度所得的距離誤差表示。非視距誤差也服從高斯分布，均值為μ′（通常為正值）、標準差為σ′。

圖3 基站與移動終端的位置分布

4.1 定位誤差CDF曲線分析

假設仿真環境中小區半徑R=200 m，TDOA測量誤差均值μ=0、標準差σ=5 m，在7個定位基站中，BS6～BS7帶有NLOS誤差，其均值μ′=20 m，標準差σ′=50 m。

本文結合聚類思想，采用改進的Fang算法對移動終端進行仿真，定位誤差CDF曲線如圖4所示。Fang算法定位誤差CDF曲線67%位置的誤差值為13.364 m，即100個定位點中，有67個定位結果的定位誤差在13.364 m范圍內，而同樣場景下，本文算法定位誤差CDF曲線67%位置的誤差值為 7.285 m，遠遠小于經典算法的定位誤差。這說明本文算法在一定程度上能夠較好的抑制NLOS誤差。

圖4 算法定位誤差CDF曲線對比

4.2 小區半徑對定位性能的影響

圖5為小區半徑由200 m增加至3 000 m的情況下，經典Fang算法和本文算法定位誤差CDF67曲線的仿真對比圖。仿真條件中，假設TDOA測量誤差均值μ=0、標準差σ=5 m。在7個定位基站中，BS6～BS7帶有NLOS誤差，其均值μ′=20 m，標準差σ′=50 m。

由圖5可知，當小區半徑從200 m增加至 3 000 m時，Fang算法和本文算法定位誤差的CDF67曲線整體上都呈現上升趨勢，說明兩種算法均會受到小區半徑的影響，但本文算法對該影響的抑制效果更明顯，定位結果的誤差保持在較低水平，定位精度遠高于Fang算法產生的結果。

4.3 TDOA測量值誤差對定位性能的影響

圖6為非視距環境中，到達時間差測量值誤差的標準差從10 m增加至80 m時，經典Fang算法和本文算法定位誤差CDF67曲線的仿真對比圖。仿真中，小區半徑R=1 000 m，TDOA測量誤差均值μ=0、標準差σ根據仿真場景進行調整。在7個定位基站中，BS6～BS7帶有NLOS誤差其均值μ′=200 m，標準差σ′=200 m。

圖5 不同小區半徑時定位誤差CDF67曲線對比

圖6 不同TDOA測量值誤差時定位誤差CDF67曲線對比

從仿真結果看，隨著TDOA測量值誤差的增加，本文算法定位誤差值的CDF67曲線呈現上升趨勢，定位誤差不斷增加。雖本文算法CDF67定位誤差值均低于經典算法，但是值越來越接近，說明當TDOA測量值誤差越來越大時，NLOS信號誤差和LOS信號誤差的區分度變小。實際生活中，非視距誤差通常遠遠大于視距環境下的TDOA測量值誤差，所以本文算法的定位精度在生活中大多場景下要優于經典算法。

4.4 NLOS誤差對定位性能的影響

圖7為NLOS誤差的標準差從10 m增加至80 m 的情況下，經典Fang算法和本文算法定位誤差CDF67曲線的仿真對比圖。仿真中，小區半徑R=1 000 m， TDOA測量誤差均值μ=0、標準差σ=5 m。在7個定位基站中，BS6～BS7帶有NLOS誤差，其均值μ′=20 m，標準差σ′根據仿真場景進行調整。

圖7 不同NLOS誤差時定位誤差CDF67曲線對比

從仿真結果看，經典Fang算法受NLOS誤差的干擾，精度下降明顯，而本文算法可以很好地抑制NLOS誤差，定位精度保持在10 m左右，且定位結果的精度遠遠高于經典算法，說明本文算法能更好地識別誤差較大的非視距信號，從而有效提高非視距環境下的定位精度。

5 結 語

針對當前算法在非視距環境下無法精確定位的問題，提出了基于聚類和TDOA的基站定位優化算法，并采用仿真對比實驗測試算法的性能。仿真實驗過程表明，小區半徑、TDOA測量值誤差以及NLOS誤差均會對無線定位的精度產生一定程度影響。相比經典Fang算法而言，本文算法在NLOS環境下具有較好的定位性能，能夠較好地抑制各方面的干擾以提高無線定位的精度，具有重要的理論價值和現實意義。