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

金仙力，趙道明

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

0 引 言

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

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

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

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

1 TDOA定位方法

1.1 TDOA定位原理

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

對于任意一個TDOA值，實際上表示的是來自移動臺的脈沖信號到達兩個基站的時間的差值。由于信號在空氣中傳輸?shù)乃俾式咏馑伲视肨DOA值與光速的乘積可以表示移動臺到兩個基站之間的距離差為定值，滿足雙曲線方程的形式。兩組雙曲線方程聯(lián)立即可得到可行解。

1.2 TDOA定位模型

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

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

(1)

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

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

(2)

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

(3)

(4)

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

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

2.1 CHAN算法

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

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

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

(5)

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

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

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

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

(6)

其中，

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

(7)

(8)

(9)

2.2 CHAN-LCCRW算法的主要思想

文中提出的CHAN-LCCRW誤差校正算法，根據(jù)超寬帶定位系統(tǒng)產(chǎn)生的多組TDOA測量值，通過CHAN算法得到校正過系統(tǒng)誤差的初步估計坐標(biāo)，再采用殘差加權(quán)的方式來抑制NLOS誤差對定位結(jié)果的影響。

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

(10)

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

表1 兩種算法估計坐標(biāo)的計算次數(shù)對比

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

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

Step2:如果M=3，跳轉(zhuǎn)到Step8；如果M>3，跳轉(zhuǎn)到Step3；否則測量不足，結(jié)束。

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

Step5:如果P大于3，跳轉(zhuǎn)到Step6；否則，跳轉(zhuǎn)到Step7。

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

2.3 CHAN-LCCRW算法的流程圖

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

圖1 CHAN-LCCRW算法流程圖

3 仿真與分析

3.1 實驗設(shè)置

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

3.2 仿真結(jié)果分析

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

圖2 不同環(huán)境下CHAN算法的定位性能

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

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

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

圖4 各算法的累積分布函數(shù)

4 結(jié)束語

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

[1] 胡永利,孫艷豐,尹寶才.物聯(lián)網(wǎng)信息感知與交互技術(shù)[J].計算機學(xué)報,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] 周傲英,楊 彬,金澈清,等.基于位置的服務(wù):架構(gòu)與進展[J].計算機學(xué)報,2011,34(7):1155-1171.

[4] 班 賀.基于RFID技術(shù)的倉儲管理系統(tǒng)研究與應(yīng)用[D].南京:南京理工大學(xué),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] 賀遠華,黎洪生.無線傳感器網(wǎng)絡(luò)節(jié)點的非視距定位方案研究[J].計算機工程與應(yīng)用,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] 吳紹華, 張欽宇,張乃通. 密集多徑環(huán)境下UWB測距的NLOS誤差減小方法[J].電子學(xué)報,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環(huán)境下的定位研究[J].計算機技術(shù)與發(fā)展,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系統(tǒng)LOS和NLOS環(huán)境中的應(yīng)用研究[J].電子技術(shù)應(yīng)用,2007,33(11):110-113.

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

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