基于TL-LFL的UWB室內(nèi)定位算法

劉 文，趙 旭，李連鵬，劉福朝，褚昕悅，代 牮

(北京信息科技大學(xué)，高動(dòng)態(tài)導(dǎo)航技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100192)

0 引言

隨著人工智能技術(shù)的快速發(fā)展，物聯(lián)網(wǎng)系統(tǒng)信息化程度不斷提高，其對(duì)室內(nèi)高精度定位的需求也在持續(xù)上升。目前室內(nèi)定位技術(shù)有WiFi、射頻技術(shù)、ZigBee、超寬帶(ultra wide band，UWB)等[1]，UWB技術(shù)中信號(hào)頻譜由多個(gè)子頻帶組成，目的是提高無(wú)線通信的數(shù)據(jù)速率和穿墻的傳播能力[2],超寬帶具有高時(shí)間分辨率(ns級(jí))，有助于精確的距離測(cè)量，超寬帶以其優(yōu)良的性能在通信領(lǐng)域具有較廣闊的應(yīng)用。

傳統(tǒng)的三邊定位算法原理簡(jiǎn)單，計(jì)算量較小，具有運(yùn)算速度快的優(yōu)點(diǎn)[3]，被廣泛研究。游小榮等通過(guò)設(shè)定優(yōu)化目標(biāo)函數(shù)求解的方法找到定位目標(biāo)[4]；高莉等提出一種改進(jìn)的三邊定位算法，通過(guò)求解利用加權(quán)最小二乘算法和損失定位信息構(gòu)建的模型實(shí)現(xiàn)定位[5]；周杰等采用Eddyst-one技術(shù)優(yōu)化后的質(zhì)心算法解決三邊測(cè)量算法的不足，并選擇10個(gè)定位節(jié)點(diǎn)進(jìn)行驗(yàn)證[6]。位置指紋是另一種廣泛應(yīng)用的UWB定位技術(shù)，通常包括2個(gè)階段：離線階段包括位置或與位置有關(guān)的相關(guān)信號(hào)參數(shù)(如信號(hào)飛行時(shí)間、接收信號(hào)強(qiáng)度)建立一個(gè)具有位置特征的指紋數(shù)據(jù)庫(kù)；在線階段目標(biāo)節(jié)點(diǎn)與存儲(chǔ)在指紋數(shù)據(jù)庫(kù)中的指紋點(diǎn)進(jìn)行比較得到目標(biāo)節(jié)點(diǎn)估計(jì)位置[7]。李世銀等提出了一種MeanShift與加權(quán)K近鄰相結(jié)合的指紋定位方法，平均定位誤差在0.5 m左右[8]；孫建強(qiáng)等在指紋算法中引入了模糊推理和加權(quán)KNN處理的方法，定位誤差在10 cm左右[9]；指紋定位算法中數(shù)據(jù)匹配算法一般都是使用歐氏距離進(jìn)行相似度計(jì)算，找出K值，雖然歐氏距離能直觀反映信號(hào)的差異性，但信號(hào)的波動(dòng)也會(huì)導(dǎo)致歐氏距離的改變，而且容易出現(xiàn)2個(gè)點(diǎn)歐氏距離較近而物理距離較遠(yuǎn)的情況。

本文結(jié)合三邊定位和指紋定位的優(yōu)點(diǎn)加以改進(jìn)，提出了一種基于TL-LFL (trilateral location and location fingerprint location)的室內(nèi)定位算法。主要分為2個(gè)階段：離線階段通過(guò)克里金插值法構(gòu)建離線數(shù)據(jù)庫(kù)；在線定位分為兩步：粗定位和精定位，粗定位采用三邊定位來(lái)約束目標(biāo)區(qū)域，得到初次定位坐標(biāo)和定位區(qū)域S；精定位結(jié)合指紋定位算法，采用K-Means算法對(duì)區(qū)域S內(nèi)指紋點(diǎn)聚類(lèi)，找出與在線實(shí)測(cè)距離信息最近的聚類(lèi)中心，最后結(jié)合粗定位坐標(biāo)根據(jù)其離散度進(jìn)行加權(quán)計(jì)算得到最終定位坐標(biāo)。既可以降低最終定位結(jié)果的誤差，又可以降低指紋定位的復(fù)雜計(jì)算量。

1 指紋定位算法

指紋定位算法主要分為2個(gè)階段：離線階段構(gòu)建指紋數(shù)據(jù)庫(kù)；在線階段進(jìn)行數(shù)據(jù)匹配、實(shí)時(shí)定位?；玖鞒倘鐖D1所示。

圖1 指紋定位原理示意圖

離線階段：使用采集設(shè)備獲取定位區(qū)域中基站與標(biāo)簽之間的距離信息，將其作為該參考節(jié)點(diǎn)的指紋量存儲(chǔ)到指紋數(shù)據(jù)庫(kù)中[10]。在線匹配階段：將標(biāo)簽實(shí)時(shí)獲取的各個(gè)基站的距離信息與指紋數(shù)據(jù)庫(kù)內(nèi)指紋點(diǎn)距離信息進(jìn)行匹配，找到相似度最高的一個(gè)或多個(gè)指紋量，根據(jù)一定的匹配算法得出標(biāo)簽的估計(jì)坐標(biāo)。常用的匹配算法主要有K最近鄰算法、加權(quán)K最近鄰算法、神經(jīng)網(wǎng)絡(luò)和支持向量機(jī)等。

2 TL-LFL定位算法

TL-LFL算法主要包括建立離線數(shù)據(jù)庫(kù)；進(jìn)行在線數(shù)據(jù)匹配，采用粗精定位結(jié)合。

2.1 建立指紋數(shù)據(jù)庫(kù)

建立指紋數(shù)據(jù)庫(kù)由采樣和插值2個(gè)階段構(gòu)成。其中采樣階段主要完成采樣點(diǎn)的選取、指紋信息采集以及指紋信息處理3個(gè)功能[11]。根據(jù)UWB信號(hào)分辨率高、測(cè)距值精確且波動(dòng)性小的優(yōu)點(diǎn)，提出選取UWB測(cè)距信息作為指紋量。

插值階段實(shí)現(xiàn)對(duì)未采樣區(qū)域的指紋量估計(jì)，包括插值點(diǎn)選取、變異函數(shù)擬合和克里金插值估計(jì)3個(gè)部分[11]。最后，將采樣的測(cè)距信息和插值估計(jì)的測(cè)距信息存儲(chǔ)到指紋數(shù)據(jù)庫(kù)中以實(shí)現(xiàn)在現(xiàn)階段數(shù)據(jù)匹配。

2.1.1 定位信息采樣

采用雙邊雙向測(cè)距方法得到基站和標(biāo)簽之間的距離，需要標(biāo)簽和基站單獨(dú)進(jìn)行通信，其中A代表標(biāo)簽，B代表基站，測(cè)距流程圖如圖2所示。

圖2 雙邊雙向測(cè)距流程圖

(1)標(biāo)簽發(fā)送Poll包，記錄發(fā)送時(shí)間T1，打開(kāi)接收。

(2)基站要提前打開(kāi)接收，在接收到Poll包后，記錄到達(dá)時(shí)間T2。

(3)基站在T3(T3=T1+T2)時(shí)刻發(fā)送Reply包，完成后等待數(shù)據(jù)接收。

(4) 標(biāo)簽收到Reply包，記錄時(shí)間T4。

(5)標(biāo)簽在T5(T5=T3+T4)時(shí)刻發(fā)送Finally包。

(6)基站接收到Finally包，記錄時(shí)間T6，然后計(jì)算出4個(gè)時(shí)間差，可推出信號(hào)飛行時(shí)間，如式(1)所示：

(1)

式中：T1為標(biāo)簽發(fā)出Poll包到接收基站的Reply包的時(shí)間；T2為基站發(fā)送Reply包到接收標(biāo)簽的Finally包的時(shí)間；T3為基站接收標(biāo)簽的Poll包到發(fā)送Reply包的時(shí)間；T4為標(biāo)簽接收基站的Reply包到發(fā)送Finally包的時(shí)間。

距離計(jì)算公式為

d=Tp×c

(2)

式中c為光速。

為了保證數(shù)據(jù)的有效性來(lái)驗(yàn)證算法的定位精度，本文先采用限幅濾波再采用滑動(dòng)濾波來(lái)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，確定每個(gè)采樣點(diǎn)對(duì)應(yīng)一組距離信息，并保存數(shù)據(jù)。

在實(shí)驗(yàn)場(chǎng)地內(nèi)布置一定數(shù)目的UWB基站，將實(shí)驗(yàn)范圍均勻劃分為若干網(wǎng)格，每個(gè)網(wǎng)格的中心作為距離信息采樣點(diǎn)，將該采樣點(diǎn)的物理位置及經(jīng)預(yù)處理后的各個(gè)基站的測(cè)距信息共同構(gòu)成一個(gè)位置指紋。

(3)

2.1.2 插值數(shù)據(jù)估算

使用指紋定位方法時(shí)，如果手動(dòng)確定地面真實(shí)坐標(biāo)，在大規(guī)模環(huán)境中需要大量時(shí)間。這一問(wèn)題在基于UWB的定位中更嚴(yán)重，在這種情況下，密集的指紋數(shù)據(jù)庫(kù)是實(shí)現(xiàn)高精度定位的關(guān)鍵。為了減少數(shù)據(jù)采樣的工作量，本文采用克里金插值法從稀疏收集的測(cè)距信息中構(gòu)建完整的指紋數(shù)據(jù)庫(kù)[12]。

克里金插值算法是有限區(qū)域內(nèi)對(duì)區(qū)域變量的一種無(wú)偏最優(yōu)估計(jì)，在空間插值的地理統(tǒng)計(jì)原理中得到了廣泛的應(yīng)用，但在無(wú)線網(wǎng)絡(luò)領(lǐng)域中應(yīng)用并不廣泛。與傳統(tǒng)的插值方法相比，克里金插值法在數(shù)據(jù)網(wǎng)格化的過(guò)程中，考慮到了描述對(duì)象的空間相關(guān)性結(jié)果更能真實(shí)地表示實(shí)際情況[13]，克里金插值的計(jì)算公式為

(4)

首先構(gòu)建稀疏的采集指紋數(shù)據(jù)庫(kù)，建立克里金插值算法模型，完成變異函數(shù)擬合。然后利用構(gòu)建的算法模型和采集指紋數(shù)據(jù)庫(kù)對(duì)預(yù)測(cè)點(diǎn)的3個(gè)距離值進(jìn)行估算，最后將估算值與預(yù)測(cè)點(diǎn)實(shí)際物理坐標(biāo)進(jìn)行組合存儲(chǔ)到指紋數(shù)據(jù)庫(kù)，因此構(gòu)建指紋數(shù)據(jù)庫(kù)的離線工作量可以顯著減少。

2.2 在線定位階段

2.2.1 粗定位階段

粗定位階段采用三邊定位算法，估計(jì)和確定鄰近的參考點(diǎn)，減少了指紋定位階段在距離誤差下需要計(jì)算的參考點(diǎn)。這一步將篩選和過(guò)濾距離目標(biāo)節(jié)點(diǎn)較遠(yuǎn)的參考點(diǎn)。

三邊定位算法是一種坐標(biāo)變換的定位算法，原理和實(shí)現(xiàn)比較簡(jiǎn)單，以每個(gè)基站為圓心，標(biāo)簽到基站的距離為半徑，3個(gè)圓相交的點(diǎn)即為標(biāo)簽坐標(biāo)。4個(gè)坐標(biāo)關(guān)系為

(5)

在實(shí)際定位中，由于非視距、噪聲、多徑等因素的影響，實(shí)際測(cè)量一般存在誤差，如圖3所示，動(dòng)態(tài)相交區(qū)域記為S，三邊定位結(jié)果記為T(mén)。

di=ri+ei

(6)

式中：di為標(biāo)簽到基站的測(cè)量距離；ri為實(shí)際距離；ei為測(cè)距誤差。

圖3 三邊定位算法原理圖

2.2.2 精定位階段

在粗定位結(jié)果的基礎(chǔ)上結(jié)合指紋定位算法，在S1區(qū)域存在分布較遠(yuǎn)的指紋點(diǎn)時(shí)，直接在S1區(qū)域內(nèi)取均值或者通過(guò)加權(quán)方法估計(jì)坐標(biāo)會(huì)容易受到干擾，得到的估計(jì)坐標(biāo)與實(shí)際的物理位置會(huì)有較大偏差，對(duì)屬于S1區(qū)域內(nèi)的指紋點(diǎn)采用K-Means聚類(lèi)方法進(jìn)行區(qū)域劃分，由于S1區(qū)域內(nèi)指紋點(diǎn)較少，根據(jù)S1區(qū)域特征，設(shè)置聚類(lèi)總數(shù)為3，相對(duì)于對(duì)所有指紋點(diǎn)進(jìn)行聚類(lèi)加權(quán)計(jì)算減少了計(jì)算量，也使區(qū)域劃分更加精確。K-Means聚類(lèi)效果如圖4所示。

最后結(jié)合粗定位坐標(biāo)T進(jìn)行加權(quán)計(jì)算得到最終估計(jì)坐標(biāo)，精定位階段流程如圖5所示。

圖4 S區(qū)域內(nèi)K-Means聚類(lèi)后效果

圖5 精定位階段流程圖

圖5中本文采用基于參考位置指紋離散程度的WKNN定位算法discrete degree WKNN，DD-WKNN)計(jì)算權(quán)重系數(shù)，依據(jù)指紋點(diǎn)離散程度對(duì)位置估算的參考權(quán)重進(jìn)行權(quán)值設(shè)定，離散程度用變異系數(shù)表示，如式(8)所示。權(quán)重系數(shù)的大小與離散程度成反比。利用位置指紋的變異系數(shù)來(lái)表示在K個(gè)指紋數(shù)據(jù)中的離散程度，位置指紋的離散程度越小具有的參考價(jià)值越高[14]。

(7)

(8)

根據(jù)得到的權(quán)重系數(shù)，對(duì)K個(gè)指紋點(diǎn)加權(quán)求和估算位置坐標(biāo)。

TL-LFL算法整體流程如圖6所示，圖6(a)粗定位階段；圖6(b)精定位階段中使用K-Means聚類(lèi)進(jìn)行區(qū)域劃分；圖6(c)選取與在線實(shí)測(cè)距離信息最相似的聚類(lèi)中心；圖6(d)結(jié)合坐標(biāo)T加權(quán)得到估計(jì)坐標(biāo)。

圖6 TL-LFL算法步驟

3 實(shí)驗(yàn)仿真與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文算法的s有效性，設(shè)計(jì)了如圖7所示的模擬測(cè)試方案，數(shù)據(jù)采集定位區(qū)域選擇8 m×6 m的實(shí)驗(yàn)室會(huì)議室，可以看到室內(nèi)有較多的桌椅，符合一般室內(nèi)環(huán)境的靜態(tài)干擾條件[15]。其內(nèi)部結(jié)構(gòu)和采樣點(diǎn)分布如下：會(huì)議室內(nèi)每隔1.2 m設(shè)置一個(gè)采樣點(diǎn)，共計(jì)34個(gè)采樣點(diǎn)，各采樣點(diǎn)與基站之間通過(guò)UWB進(jìn)行通信。對(duì)采樣點(diǎn)和基站之間的距離信息進(jìn)行采樣。本次實(shí)驗(yàn)采用2個(gè)標(biāo)簽共采集19次以獲取實(shí)驗(yàn)場(chǎng)地UWB距離數(shù)據(jù)，為保證每個(gè)采樣點(diǎn)數(shù)據(jù)的穩(wěn)定性，采集數(shù)據(jù)時(shí)基站和標(biāo)簽擺放好靜置5 s，并采用限幅-滑動(dòng)濾波處理每個(gè)采樣點(diǎn)的數(shù)據(jù)，然后讀取出現(xiàn)頻次最高的100組數(shù)據(jù)求均值作為采樣點(diǎn)最終的距離值，將各個(gè)采樣點(diǎn)的數(shù)據(jù)錄入采樣指紋數(shù)據(jù)庫(kù)。

(a)實(shí)物圖

(b)平面圖圖7 室內(nèi)采樣點(diǎn)分布平面圖

3.2 實(shí)驗(yàn)分析

采用python為仿真工具,根據(jù)克里金插值算法進(jìn)行插值估計(jì)，為了驗(yàn)證插值算法的可行性，在采樣指紋數(shù)據(jù)庫(kù)中取12個(gè)采樣點(diǎn)作為已知點(diǎn)指紋集，對(duì)剩余的23個(gè)采樣點(diǎn)用克里金插值算法估計(jì)距離信息，計(jì)算3個(gè)基站的均值誤差，如圖8所示?？梢钥闯隹死锝鸩逯捣椒ń⒅讣y數(shù)據(jù)庫(kù)大約有91%的指紋點(diǎn)距離誤差小于1 m。

圖8 克里金插值距離估計(jì)誤差圖

本文根據(jù)采樣的34個(gè)指紋點(diǎn)采用插值算法將間距縮短為0.3 m，得到覆蓋整個(gè)會(huì)議室的指紋信息，節(jié)省了大部分工作量，所有指紋點(diǎn)測(cè)距誤差均值如圖9所示，可以看出大約99%的指紋點(diǎn)誤差均值在0.8 m內(nèi)，因此采用克里金插值估計(jì)性能較好，具有一定的有效性。

圖9 指紋點(diǎn)測(cè)距誤差均值

為了驗(yàn)證提出的TL-LFL算法的可行性和有效性，利用同一組數(shù)據(jù)分別用三邊定位、KNN、DD-WKNN和TL-LFL算法估算標(biāo)簽的位置坐標(biāo)，對(duì)比最終的定位結(jié)果。

常用的定位性能評(píng)價(jià)指標(biāo)有幾何精度因子、均方誤差和方均根誤差、克拉美羅下界、累積概率分布函數(shù)等[16]。本文采用均方誤差和累積概率分布函數(shù)驗(yàn)證算法的精準(zhǔn)性，對(duì)測(cè)試樣本100組數(shù)據(jù)進(jìn)行多次實(shí)驗(yàn)取均值，結(jié)果如圖10、圖11所示。

圖10 4種算法定位均方誤差示意圖

從圖10可以看出，TL-LFL算法定位均方誤差比三邊定位、KNN和DD-WKNN算法小，定位精度最高；從圖11來(lái)看，本文算法誤差在0.35 m內(nèi)概率達(dá)到87%，優(yōu)于其他2種算法。表明在一定程度上改善了信號(hào)不穩(wěn)定帶來(lái)的定位誤差問(wèn)題。

圖11 3種算法定位誤差累積概率分布圖

4種定位方法誤差對(duì)比如表1所示，TL-LFL算法的定位誤差在0.7 m內(nèi)，平均定位誤差為0.2 m，定位效果優(yōu)于其他3種算法。本文算法具有良好的穩(wěn)定性，相比DD-WKNN算法精度提升了約30%，對(duì)比三邊定位算法精度改善了約47%。

表1 4種定位方法誤差對(duì)比 m

根據(jù)以上實(shí)驗(yàn)結(jié)果可以得出，本文提出的TL-LFL算法的最小定位誤差、最大誤差、平均誤差都小于其他3種算法，定位效果和定位穩(wěn)定性均有提升，更適用于復(fù)雜環(huán)境中使用。

4 結(jié)論

本文提出了一種基于TL-LFL的室內(nèi)定位方法，該算法在采樣點(diǎn)UWB距離信息的基礎(chǔ)上采用克里金插值法構(gòu)建離線指紋數(shù)據(jù)庫(kù)，在指紋定位算法的基礎(chǔ)上引入了三邊定位算法，通過(guò)三邊定位算法獲得初始定位坐標(biāo)和定位區(qū)域；精定位結(jié)合指紋定位算法，采用K-Means算法對(duì)區(qū)域S內(nèi)指紋點(diǎn)聚類(lèi)，找出與在線實(shí)測(cè)距離信息最近的聚類(lèi)中心，最后結(jié)合粗定位坐標(biāo)根據(jù)其離散度進(jìn)行加權(quán)計(jì)算得到最終定位坐標(biāo)。實(shí)驗(yàn)表明，該算法定位誤差小于0.7 m，相比DD-WKNN算法精度提升了約30%，對(duì)比三邊定位算法精度改善了約47%。該算法減少工作量的同時(shí)又具有較好的穩(wěn)定性和精準(zhǔn)度。