基于改進(jìn)WKNN 的室內(nèi)定位算法

王修駒，姚善化

（安徽理工大學(xué) 電氣與信息工程學(xué)院，安徽 淮南 232000）

無(wú)線設(shè)備和移動(dòng)通信的快速發(fā)展給室內(nèi)定位服務(wù)帶來(lái)了廣泛的發(fā)展空間。隨著全球定位系統(tǒng)多年的發(fā)展與完善，中國(guó)北斗導(dǎo)航定位系統(tǒng)的組網(wǎng)應(yīng)用，室外定位技術(shù)已經(jīng)非常完善并能夠解決遇到的各種室外定位問(wèn)題。室內(nèi)定位技術(shù)相對(duì)薄弱，如今的室內(nèi)定位技術(shù)包括Wi-Fi, UWB[1], RFID[2], ZigBee, 藍(lán)牙定位技術(shù)，依據(jù)定位精度，硬件設(shè)備成本各有其優(yōu)缺點(diǎn)，在這些室內(nèi)定位技術(shù)中，其中基于Wi-Fi 指紋的室內(nèi)定位技術(shù)最易實(shí)現(xiàn)。在Wi-Fi 指紋庫(kù)確立下來(lái)之后，應(yīng)對(duì)環(huán)境的變化只需進(jìn)行相應(yīng)的參數(shù)測(cè)試便可完成適配。因Wi-Fi 網(wǎng)絡(luò)傳播范圍廣、定位精度高、成本低等優(yōu)點(diǎn)廣泛應(yīng)用于室內(nèi)定位。

Wi-Fi 的室內(nèi)定位主要有兩大方向，即基于測(cè)距和指紋。其中基于測(cè)距的定位技術(shù)又分為到達(dá)時(shí)間法（TOA）[3]和到達(dá)時(shí)間差法（TDOA）[4]兩種方法，但是考慮到環(huán)境空間繁瑣的結(jié)構(gòu)及多徑效應(yīng)帶來(lái)的干擾，基于指紋的方法不需要太多的硬件設(shè)施故受到更為廣泛的研究。通過(guò)接收信號(hào)強(qiáng)度指示（RSSI）[5]來(lái)替代物理位置，結(jié)合位置指紋匹配算法進(jìn)行定位。左仲亮[6]采用均值濾波對(duì)RSSI 進(jìn)行預(yù)處理來(lái)減少噪聲等因素對(duì)定位精度的影響，通過(guò)改進(jìn)加權(quán)K 近鄰（Weighted K-Nearest Neighbor，WKNN）[7]算法來(lái)提升定位效果，馮濤等[8]為了提高基于WKNN[9]的Wi-Fi 指紋定位算法的定位精度，將原始的定位特征不相關(guān)的RSSI，通過(guò)數(shù)學(xué)的手段將其相關(guān)，提出歸一化結(jié)合高斯濾波的定位算法大大提高了定位精度。以上算法主要在AP 選擇、RSSI 濾波及K 值的選擇上做出了改進(jìn)與創(chuàng)新。但他們基于近鄰算法的定位坐標(biāo)相似度距離度量上多采用歐氏距離的方法，信號(hào)特征的距離無(wú)法表征真實(shí)的物理距離。在復(fù)雜的室內(nèi)環(huán)境里信號(hào)的傳播易受噪聲、多徑等不確定性因素的影響，對(duì)RSSI 進(jìn)行濾波處理能夠減低其波動(dòng)性，但是會(huì)造成RSSI 信號(hào)失真。本文在RSSI 信號(hào)特征獲取上也進(jìn)行了改進(jìn)使定位更為精確。

1 算法描述

通常，K 近鄰（K-Nearest Neighbor，KNN）算法需要計(jì)算當(dāng)前測(cè)量的指紋數(shù)據(jù)與數(shù)據(jù)庫(kù)中的各個(gè)指紋數(shù)據(jù)之間的距離，然后通過(guò)排序來(lái)確定k 個(gè)距離最近的參考點(diǎn)，WKNN 算法通過(guò)加權(quán)平均估算進(jìn)一步來(lái)精確待定位點(diǎn)的位置。

算法主要涉及3 個(gè)方面因素的影響即訓(xùn)練集、距離、相似度的衡量參數(shù)k 的大小。實(shí)際環(huán)境下，采集的信號(hào)具有波動(dòng)性，采集設(shè)備、采集時(shí)間和環(huán)境的變化等因素都會(huì)影響到算法的精度與穩(wěn)定性。所以對(duì)于RSSI 的獲取與處理需要提前處理，通常的方法是對(duì)RSSI 做均值濾波處理，盡可能地減少外界因素的影響。接入點(diǎn)AP 承擔(dān)Wi-Fi 的覆蓋和通信工作，類似于無(wú)線蜂窩網(wǎng)絡(luò)中的基站作用。指紋采集到不同AP 的RSS組成，分為TP 指紋和RP 指紋。TP 指紋在在線階段的測(cè)試獲得用以估計(jì)TP 的位置。RP 指紋在離線階段獲得用以存儲(chǔ)在數(shù)據(jù)庫(kù)當(dāng)中，并與坐標(biāo)一起來(lái)組成離線指紋數(shù)據(jù)庫(kù)。

對(duì)于AP 點(diǎn)的選擇，首先是要測(cè)量采集到那些受環(huán)境干擾小且其出現(xiàn)的概率高的AP 點(diǎn)，這樣會(huì)在一定程度上減少外在的定位精度誤差。另一方面雖然指紋定位的精度會(huì)隨著AP 的數(shù)量增加而升高，但考慮環(huán)境因素和計(jì)算量因素，AP 的數(shù)量不宜選的太大或太小，綜合考慮兩方面的因素通過(guò)實(shí)驗(yàn)得到相應(yīng)的數(shù)值。指紋相似度函數(shù)：

式中，erri代表定位坐標(biāo)誤差。

1.1 選取k 值以及它的影響

若選取的k 值很小，則模型復(fù)雜且難以實(shí)現(xiàn)，環(huán)境中的噪聲很容易干擾導(dǎo)致算法的功能得不到實(shí)現(xiàn)。若選取較大的k 值，即實(shí)驗(yàn)區(qū)域進(jìn)行預(yù)測(cè)，那么輸入實(shí)例較遠(yuǎn)的會(huì)起同樣的作用，從而預(yù)測(cè)發(fā)生錯(cuò)誤，k值的增大使得整體模型簡(jiǎn)單，同樣實(shí)現(xiàn)不了算法的功能。因此，需要依據(jù)實(shí)驗(yàn)參數(shù)進(jìn)行k 值的選取，調(diào)整超參數(shù)來(lái)得到一個(gè)符合實(shí)際情況的結(jié)果。

1.2 定位相似距離的度量

指紋定位的關(guān)鍵是測(cè)試指紋與參考指紋間信號(hào)域距離的表達(dá)。而較為常用的表征方法有歐式距離、曼哈頓距離、馬氏距離等。在二維坐標(biāo)系下，假設(shè)兩點(diǎn)坐標(biāo)分別為（ x1,y1）和（ x2,y2）。

歐氏距離表達(dá)為

曼哈頓距離表達(dá)為

采用哪種距離度量方法會(huì)獲取到不同的定位精度及誤差。歐氏距離相較于曼哈頓距離會(huì)有這種情況的發(fā)生，即當(dāng)計(jì)算得到的歐氏距離相等時(shí)，此時(shí)歐氏距離作為度量無(wú)法衡量出指紋的相似程度，那么此時(shí)曼哈頓距離就可以衡量指紋的相似度。曼哈頓距離的優(yōu)點(diǎn)是具有更高的穩(wěn)定性且能夠使信號(hào)的波動(dòng)較為平緩，這樣使得最大程度上減小對(duì)于定位誤差的增長(zhǎng)。應(yīng)該注意的是曼哈頓距離需要保證特征值差別不可以很大。若通過(guò)曼哈頓距離作為距離的度量過(guò)大，會(huì)導(dǎo)致掩蓋其他特征間的鄰近關(guān)系。因?yàn)閺?fù)雜的環(huán)境，采集到的信號(hào)會(huì)受到多種因素的干擾，一般情況下都會(huì)進(jìn)行指紋特征值歸一化處理。信號(hào)中的特征優(yōu)先級(jí)應(yīng)該保持一致，否則會(huì)導(dǎo)致定位精度衰減甚至誤判。由于本文選取的區(qū)域較小且指紋特征值可控，故這些因素可以忽略。

綜合考慮到歐式距離在度量指紋相似度上帶來(lái)的誤差，本文通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證曼哈頓距離度量的優(yōu)勢(shì)。

2 Wi-Fi 定位與RSSI 信號(hào)特征處理

將定位技術(shù)應(yīng)用到室內(nèi)環(huán)境會(huì)存在很大的誤差，定位環(huán)境的復(fù)雜變化會(huì)導(dǎo)致定位系統(tǒng)的不穩(wěn)定運(yùn)行，所以在進(jìn)行定位信息收集前需要對(duì)周圍環(huán)境噪聲干擾進(jìn)行處理。本文的做法是在信號(hào)濾波之前進(jìn)行高斯擬合的預(yù)處理之后采用KF 濾波對(duì)Wi-Fi 定位環(huán)境噪聲處理，高斯擬合與KF 濾波減少了環(huán)境因素帶來(lái)的誤判提高了算法的定位精度和穩(wěn)定性。

2.1 Wi-Fi 指紋定位模塊

首先在實(shí)驗(yàn)區(qū)域內(nèi)設(shè)置一定數(shù)量的AP（AccessPoint, AP）點(diǎn),并根據(jù)實(shí)際的計(jì)算力和數(shù)據(jù)存儲(chǔ)力選擇參考點(diǎn)（Reference Point, RP）。通過(guò)軟件設(shè)備離線采集信號(hào)強(qiáng)度（Received Signal Strength, RSS），RSS 一般為-150～0 dBm，本文通過(guò)數(shù)學(xué)的方法將RSS 轉(zhuǎn)化為便于計(jì)算的RSSI，依據(jù)式(4)得到RP 的位置坐標(biāo)，通過(guò)多次測(cè)試計(jì)算將坐標(biāo)數(shù)據(jù)取均值得到位置坐標(biāo)，作為指紋數(shù)據(jù)庫(kù)的一部分。在線定位時(shí)，通過(guò)模擬機(jī)器人移動(dòng)來(lái)獲取測(cè)試指紋，通過(guò)離線階段RP 獲得的RSSI 與真實(shí)物理位置的映射關(guān)系對(duì)比來(lái)得出在線測(cè)試階段的位置坐標(biāo)，即實(shí)時(shí)位置坐標(biāo)( x , y) 。這些是Wi-Fi 指紋定位模塊的主要內(nèi)容。

2.2 RSSI 信號(hào)特征處理模塊

高斯擬合（GF）作為卡爾曼濾波階段之前的步驟，其要求獲得的RSSI 分布特性符合高斯分布。對(duì)其進(jìn)行總體分布類高斯擬合可以得到較為真實(shí)的RSSI 信號(hào)特征。其GF 公式如下：

3 算法總體流程

離線階段和在線階段兩個(gè)階段組成了該算法。圖1 為定位算法的整體流程。

離線階段：指紋數(shù)據(jù)采集、GF 與KF 預(yù)處理、指紋庫(kù)優(yōu)化、離線指紋庫(kù)。

在線階段：待測(cè)點(diǎn)RSS 采集、二次濾波、定位匹配算法、累計(jì)誤差比較、輸出定位坐標(biāo)。

本文的指紋定位算法主要由上面的兩個(gè)階段來(lái)實(shí)現(xiàn)，其中離線階段經(jīng)過(guò)GF 與KF 處理采用已知的指紋庫(kù)等方法，在線階段通過(guò)改進(jìn)的WKNN算法來(lái)實(shí)現(xiàn)進(jìn)而減少了誤差與提升了定位精度。

4 實(shí)驗(yàn)仿真

假設(shè)選取20m×15m的區(qū)域作為實(shí)驗(yàn)的區(qū)域如圖2 所示，區(qū)域中有個(gè)9 個(gè)AP 點(diǎn)、9 個(gè)房間，按照所規(guī)劃的區(qū)域分配AP 點(diǎn)坐標(biāo)分別為(1,1), (10,1), (19,1), (1,7), (10,7), (19,7), (19,14),(10,14), (19,14)，各AP 點(diǎn)分布在各個(gè)房間的門口發(fā)射設(shè)備上，圖2 中的圓點(diǎn)為測(cè)試點(diǎn)。

圖1 算法的整體流程

圖2 實(shí)驗(yàn)的模擬平面圖

由前文可知K 的取值對(duì)定位精度產(chǎn)生重要的影響，下面通過(guò)實(shí)驗(yàn)來(lái)獲取本文的K 值。

表1 不同K 值下的定位誤差對(duì)比

由表1 不同K 值下的定位誤差可以看出，改進(jìn)WKNN 算法在K 值為4 時(shí)發(fā)生了拐點(diǎn)為誤差的最小值，同理WKNN 算法在K 值為4 時(shí)定位誤差也為最小。故本文的AP 的個(gè)數(shù)為4 即K=4。

K 值確定后實(shí)驗(yàn)分3 組進(jìn)行仿真，首先是KNN 算法在沒有應(yīng)用濾波處理的定位跟蹤與應(yīng)用卡爾曼濾波的定位跟蹤的對(duì)比仿真，第2 組是NN, KNN, WKNN 定位仿真對(duì)比，第3 組是WKNN，改進(jìn)WKNN 定位仿真對(duì)比。

如圖3 經(jīng)過(guò)卡爾曼濾波與未經(jīng)過(guò)卡爾曼濾波的定位跟蹤對(duì)比可以看出，濾波對(duì)于環(huán)境的噪聲的消除有很大的作用。未經(jīng)過(guò)濾波處理的行跡路線是雜亂無(wú)章的，經(jīng)過(guò)濾波處理過(guò)后，環(huán)境的主要噪聲被過(guò)濾掉，在一定程度上消除了環(huán)境因素的影響。

由圖4 仿真實(shí)驗(yàn)可知相較于NN 算法，KNN 算法誤差有較大的改善；WKNN 算法與KNN 算法相比，WKNN 算法稍好于KNN 算法。由圖5 仿真實(shí)驗(yàn)可以得出改進(jìn)的WKNN 算法較WKNN 算法有了明顯的提升，相較于經(jīng)典的應(yīng)用歐氏距離的度量方法曼哈頓距離度量有更大的改進(jìn)，響應(yīng)速度更快更加趨于平穩(wěn)。

圖3 KNN 算法經(jīng)過(guò)卡爾曼濾波與否的對(duì)比

圖4 NN, KNN, WKNN 定位誤差比較

圖5 WKNN 與改進(jìn)WKNN 定位誤差比較

5 結(jié)束語(yǔ)

相較于傳統(tǒng)的定位方法，K-近鄰算法有其獨(dú)特的優(yōu)勢(shì)，簡(jiǎn)單便于操作，易于其他算法的融合。通過(guò)結(jié)合Wi-Fi 指紋定位和卡爾曼濾波，高斯擬合算法來(lái)減少環(huán)境的干擾，進(jìn)而提升算法的定位精度減少誤差。通過(guò)改進(jìn)WKNN 算法的距離測(cè)量的方法，即應(yīng)用曼哈頓距離來(lái)代替歐式距離為算法距離的度量，應(yīng)用曼哈頓距離的優(yōu)點(diǎn)彌補(bǔ)了歐氏距離存在的缺點(diǎn)，在定位誤差的改進(jìn)上有了很大的提升，符合預(yù)期的要求。

綜合來(lái)看本算法仍然有許多需要改進(jìn)和攻克的難點(diǎn)，比如環(huán)境及周邊障礙物的反射阻隔等因素依然是干擾RSSI 的主要因素，當(dāng)實(shí)驗(yàn)區(qū)域足夠大的時(shí)候，選取的距離度量就會(huì)產(chǎn)生很大的誤差，此時(shí)的度量就不可用了，因此在實(shí)驗(yàn)區(qū)域上也有很大的局限性。