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

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

0 引言

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

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

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

1 指紋定位算法

指紋定位算法主要分為2個階段：離線階段構(gòu)建指紋數(shù)據(jù)庫；在線階段進(jìn)行數(shù)據(jù)匹配、實時定位。基本流程如圖1所示。

圖1 指紋定位原理示意圖

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

2 TL-LFL定位算法

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

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

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

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

2.1.1 定位信息采樣

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

圖2 雙邊雙向測距流程圖

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

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

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

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

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

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

(1)

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

距離計算公式為

d=Tp×c

(2)

式中c為光速。

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

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

(3)

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

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

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

(4)

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

2.2 在線定位階段

2.2.1 粗定位階段

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

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

(5)

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

di=ri+ei

(6)

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

圖3 三邊定位算法原理圖

2.2.2 精定位階段

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

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

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

圖5 精定位階段流程圖

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

(7)

(8)

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

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

圖6 TL-LFL算法步驟

3 實驗仿真與結(jié)果分析

3.1 實驗環(huán)境

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

(a)實物圖

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

3.2 實驗分析

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

圖8 克里金插值距離估計誤差圖

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

圖9 指紋點測距誤差均值

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

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

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

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

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

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

表1 4種定位方法誤差對比 m

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

4 結(jié)論

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