基于改進CHAN的超寬帶定位誤差校正算法

金仙力，趙道明

(南京郵電大學 計算機學院，江蘇 南京 210023)

0 引 言

在基于物聯網的服務中，物體的位置數據是位置相關服務的基本前提。人們在物聯網中部署大規模的設備，來感知物聯網中關于物體的方方面面的信息，深入挖掘這些信息以總結特征和規律，從而提供給用戶相關的業務服務，發揮物聯網的經濟價值。信息感知是物聯網應用的基礎[1]。在密集多徑環境中實現精確的定位，對于如大型商場、室內停車場等室內環境下的搜索和救援等緊急情況的處理至關重要[2]。利用無線通信技術，感知室內物體的位置，構建室內LBS[3]。現有的短距離無線通信技術中，超寬帶以其抗干擾能力強、高達幾個GHz的帶寬、功耗較小、穿透能力強和良好的保密性等優點，被許多公司用以實現室內實時定位系統(RTLS)。到目前為止，基于超寬帶技術的實時定位系統主要有Ubisens的Ubisense RTLS和Zebra Technologies的Dart RTLS等[4]。

利用超寬帶技術進行定位的過程無法規避定位誤差的出現。這些誤差會直接影響定位精度，在一些應急場景中定位誤差會導致安全隱患。導致超寬帶定位誤差產生的主要問題是NLOS(none-line-of-sight)。NLOS問題是指在信號多徑傳播過程中，沒有直射路徑，只存在反射和衍射路徑，或者檢測不到直射路徑的情況。與此相反，不經過任何障礙物直線傳播到達參考節點稱為LOS傳播。針對NLOS問題，當前的研究主要包含兩類解決方案。一種是NLOS識別，即通過算法判斷當前信號屬于NLOS傳播還是LOS傳播。另一種方案是不區分NLOS和LOS，對這些問題采用統一的校正方法進行校正[5-8]。

CHAN[9]是一種基于到達時間差的經典誤差校正算法。因其不需要遞歸即可給出雙曲線方程的閉式解，計算簡便，在理想高斯噪聲環境下精度高等，非常適合在實際工程中應用。相較于視距環境，CHAN算法在非視距環境下的定位性能下降明顯[10]。

文中從闡述TDOA算法原理出發，剖析不同分布NLOS誤差對CHAN算法性能的影響。先對非視距環境下的TDOA測量值進行分組，再加權平均CHAN算法對各TDOA測量結果集的估計結果以改善CHAN算法的性能，提出CHAN-LCCRW算法。文中將對CHAN算法在視距和非視距環境下的性能進行比較，并通過與CHAN算法和Taylor算法的對比來驗證CHAN-LCCRW算法的性能。

1 TDOA定位方法

1.1 TDOA定位原理

出于對TOA算法的改進，TDOA算法不是直接使用信號到達時間來定位，而是用不同基站之間接收到同一目標發來信號的時間差來估算移動臺位置。因此，與TOA算法相比，不需要在發送的信號中加入專門的時間戳，定位精度相對較高。信號的到達時間差的獲取，實際應用中最常用的方式是利用相關性運算的方法[11]。這種算法可以在基站和移動臺不同步時，估算出TDOA的值。由于做到基站與移動臺的同步十分復雜，所以借助相關估計產生TDOA測量值，而后利用定位算法得出估計坐標的方法的應用最為廣泛。

對于任意一個TDOA值，實際上表示的是來自移動臺的脈沖信號到達兩個基站的時間的差值。由于信號在空氣中傳輸的速率接近光速，故用TDOA值與光速的乘積可以表示移動臺到兩個基站之間的距離差為定值，滿足雙曲線方程的形式。兩組雙曲線方程聯立即可得到可行解。

1.2 TDOA定位模型

如果在一個二維空間內采用TDOA定位，那么為了得到空間中位置為[x,y]T的移動臺的坐標，至少需要三臺定位基站參與定位。空間內共有N(N≥3)個基站參與了移動臺的定位，假設每個基站的坐標分別為Pi=[xi,yi]T,i=1,2,…,N。為了方便應用，通常以一個基站的信號為基準，將其余基站的信號與之進行相關運算來產生TDOA值，假設為基站1。用ti,1表示基站i與基站1之間的信號到達時間差，di表示基站i到移動臺的距離，di,1表示基站i與基站1到移動臺的距離之差，則有下式：

di,1=cti,1=di-d1,i=1,2,…,N

(1)

另根據二維空間的歐氏距離公式有：

x2+y2,i=1,2,…,N

(2)

將式(1)帶入式(2)得：

(3)

(4)

其中，xi,1=xi-x1表示基站i與基站1橫坐標的差值；yi,1=yi-y1表示基站i與基站1縱坐標的差值。顯然，式(4)是關于未知數x,y和d1的線性方程。

2 CHAN-LCCRW定位誤差校正算法

2.1 CHAN算法

CHAN算法對于移動臺的估計位置的解法分為兩種情況：

(1)只有三個基站接收到目標信號。

當系統中只有三個基站接收到移動臺的脈沖信號，即i=2和i=3時，將式(4)組成矩陣方程然后求解可得：

(5)

將式(5)帶入式(2)可以得到關于d1的兩個候選解，根據可行域限制排除掉一個解后，可以得到d1的解，帶入式(5)得到估計坐標。

(2)存在四個或更多基站接收到目標信號。

當存在四個及以上基站接收到移動臺的脈沖信號時，令za=[x,y,d1]T。首先假設za的各元素之間相互獨立，那么其最大似然估計為：

za=argmin{(h-Gaza)TΨ-1(h-Gaza)}=

(6)

其中，

式(6)可以近似表示為：

(7)

(8)

(9)

2.2 CHAN-LCCRW算法的主要思想

文中提出的CHAN-LCCRW誤差校正算法，根據超寬帶定位系統產生的多組TDOA測量值，通過CHAN算法得到校正過系統誤差的初步估計坐標，再采用殘差加權的方式來抑制NLOS誤差對定位結果的影響。

殘差是用來描述一個定位估計結果與一組TDOA測量之間的接近程度，通常在NLOS誤差是系統的主要誤差來源時，一組TDOA測量中受到NLOS影響越大，其計算出的殘差值越大[12]。殘差值還受到一組測量元素個數的影響，因此文中采用標準化殘差來衡量一組TDOA測量受到NLOS的影響。標準化殘差是指殘差的平方和除以該組的元素個數，定義如下：

(10)

為了減小計算量以提高系統的實時性，對殘差加權算法進行了改進，采取一種低計算量的殘差加權方法[13]。當系統中有很多基站接收到來自移動臺的信號時，能夠大幅減少計算數。其與傳統殘差加權的計算估計坐標次數對比如表1所示。

表1 兩種算法估計坐標的計算次數對比

以在二維空間為例，假設共有M個基站接收到來自移動臺的信號。CHAN-LCCRW算法的步驟描述如下：

Step1:處理M個基站檢測到的待測目標信號。以某一基站為參考站，通過相關運算產生了M-1個TDOA測量值。

Step2:如果M=3，跳轉到Step8；如果M>3，跳轉到Step3；否則測量不足，結束。

Step4:假設Smin中共有P個元素，分別將第i個元素從Smin中移除，共產生P個包含P-1個元素的測量值的組合，記作Ctemp={S1,S2,…,SP}。

Step5:如果P大于3，跳轉到Step6；否則，跳轉到Step7。

Step8:將候選集Sc中所有的坐標和對應的標準化殘差值的倒數按式(11)相乘再求和后除以標準化殘差的倒數和，最后得到移動臺的估計坐標。

2.3 CHAN-LCCRW算法的流程圖

根據CHAN-LCCRW算法的步驟，繪制該算法的流程圖，如圖1所示。

圖1 CHAN-LCCRW算法流程圖

3 仿真與分析

3.1 實驗設置

尋找合適的評價指標來表示出定位的精度對于定位誤差校正算法的性能分析至關重要。在現有的研究中，廣泛采用誤差累積分布函數和均方根誤差來衡量一個定位方法的定位精度和一種誤差校正算法的性能。均方根誤差(root mean square error，RMSE)是指在有限次的測量中，將每次測量值與對應的真實值誤差的平方值求和后，再取平均值，最后求平方根后的結果。累積分布函數(cumulative distribution function，CDF)給出與某個分布相關聯的累積概率。累計分布函數可以給出誤差低于特定值的概率，所以其在實際工程應用中常用于描述定位系統的精度范圍。

3.2 仿真結果分析

圖2中給出了在視距以及非視距環境下CHAN算法定位性能與參與定位的基站數的關系。結果表明，隨著接收到目標信號的基站數的增加，CHAN算法的RMSE不斷降低。這是由于基站數的增加可以提供更多的冗余TDOA測量值，使得CHAN算法的結果更加準確。在NLOS誤差分別服從高斯分布、瑞利分布和指數分布時，CHAN算法定位的RMSE值均遠大于LOS環境下的RMSE值，在參與定位的基站數較少時，定位誤差由厘米級增加到米級。

圖2 不同環境下CHAN算法的定位性能

克拉美羅下界(Cramér-Rao low bound，CRLB)是對于參數估計問題提出的，為所有無偏估計量的方差提供了一個下限。圖3為NLOS誤差滿足不同均值的指數分布時，對CHAN算法、Taylor算法和CHAN-LCCRW算法的均方根誤差情況進行仿真的結果，并與克拉美羅下界進行比較。在NLOS誤差較小時，三種算法的定位性能相當。隨著NLOS誤差的增大，CHAN-LCCRW算法的定位性能與CHAN算法相比優勢較大，體現了對NLOS誤差較好的抑制作用。文中算法具有與Taylor算法較為接近的均方根誤差值，但較Taylor算法解決了初值難以選取和需要迭代計算的問題。

圖3 不同NLOS誤差下各算法的定位性能

圖4展示了在NLOS誤差服從均值為2m的指數分布時，各算法的定位誤差的累計分布函數。CHAN-LCCRW算法有約50%的概率將定位誤差控制在1m以內，而對于Taylor算法和CHAN算法，其概率分別為40%和30%。定位誤差小于2m時，表明NLOS誤差受到了抑制。CHAN-LCCRW算法有效抑制NLOS誤差的概率為97%左右，超過Taylor算法和CHAN算法10%以上。綜上所述，CHAN-LCCRW算法具有較高的定位精度，適合應用到實際工程。

圖4 各算法的累積分布函數

4 結束語

定位精度一直是基于超寬帶的室內定位系統的關鍵性能屬性，提高定位精度的主要手段就是對定位誤差進行校正。為了進一步提高非視距環境下CHAN算法的精度，分析了不同分布的NLOS誤差使CHAN算法精度衰退的程度。利用殘差加權的思想對CHAN算法進行改進，提出了CHAN-LCCRW算法，對誤差實施了校正，最后應用Matlab完成該算法的仿真實驗。結果表明，CHAN-LCCRW算法有效抑制了NLOS誤差，提高了CHAN算法在非視距環境下的定位精度。

[1] 胡永利,孫艷豐,尹寶才.物聯網信息感知與交互技術[J].計算機學報,2012,35(6):1147-1163.

[2] GEZICI S,TIAN Z, GIANNAKIS G B,et al. Localization via ultra-wideband radios:a look at positioning aspects for future sensor networks[J].IEEE Signal Processing Magazine,2005,22(4):70-84.

[3] 周傲英,楊 彬,金澈清,等.基于位置的服務:架構與進展[J].計算機學報,2011,34(7):1155-1171.

[4] 班 賀.基于RFID技術的倉儲管理系統研究與應用[D].南京:南京理工大學,2015.

[5] KHODJAEV J，PARK Y，MALIK A S.Survey of NLOS identification and error mitigation problems in UWB-based positioning algorithms for dense environments[J].Annals of Telecommunications,2010,65(5):301-311.

[6] 賀遠華,黎洪生.無線傳感器網絡節點的非視距定位方案研究[J].計算機工程與應用,2010,46(25):82-84.

[7] BARTOLETTI S,GIORGETTI A,WIN M Z,et al.Blind selection of representative observations for sensor radar networks[J].IEEE Transactions on Vehicular Technology,2015,64(4):1388-1400.

[8] 吳紹華, 張欽宇,張乃通. 密集多徑環境下UWB測距的NLOS誤差減小方法[J].電子學報,2008,36(1):39-45.

[9] CHAN Y T,HO K C.A simple and efficient estimator for hyperbolic location[J].IEEE Transactions on Signal Processing,1994,42(8):1905-1915.

[10] 陸 音,王寶全,丘覲瑋.CHAN算法在LOS和NLOS環境下的定位研究[J].計算機技術與發展,2015,25(9):61-65.

[11] CARTER G C.Coherence and time delay estimation[J].Proceedings of IEEE,1987,75(2):236-255.

[12] CHEN P C.A non-line-of-sight error mitigation algorithm in location estimation[C]//Wireless communications and networking conference.[s.l.]:[s.n.],1999:316-320.

[13] JIAO L,XING J,ZHANG X,et al.LCC-Rwgh:a NLOS error mitigation algorithm for localization in wireless sensor network[C]//International conference on control and automation.[s.l.]:IEEE,2007:1354-1359.

[14] BING L,WEI C,BIN W.A robust wireless sensor network localization algorithm in mixed LOS/NLOS scenario[J].Sensors,2015,15(9):23536-23553.

[15] 鄭 飛,鄭繼禹.基于TDOA的CHAN算法在UWB系統LOS和NLOS環境中的應用研究[J].電子技術應用,2007,33(11):110-113.

[16] 王建輝,崔維嘉,胡捍英.基于神經網絡的魯棒NLOS誤差抑制算法[J].計算機工程,2011,37(24):7-9.

[17] 肖 竹,譚光華,李仁發,等.無線傳感器網絡中基于超寬帶的TOA/AOA聯合定位研究[J].計算機研究與發展,2013,50(3):453-460.