基于距離和屬性加權(quán)的FWKNN室內(nèi)定位方法

繆 穎，朱正偉，諸燕平

(常州大學(xué)微電子與控制工程學(xué)院，江蘇 常州 213164)

1 引言

室內(nèi)定位這一技術(shù)一直以來都是基于位置服務(wù)的研究熱點(diǎn)，并且在快速發(fā)展著，由于在室內(nèi)或蔭蔽處無法接收到衛(wèi)星信號(hào)，所以GPS和北斗等衛(wèi)星導(dǎo)航定位系統(tǒng)無法在室內(nèi)使用[1]。為了實(shí)現(xiàn)“最后一公里”的精確導(dǎo)航，各種室內(nèi)定位技術(shù)成為近年來大量科研工作者的研究熱點(diǎn)[2]。

按照傳輸信號(hào)不同，室內(nèi)定位技術(shù)可以分為基于WiFi、RFID、ZigBee、藍(lán)牙、超寬帶、紅外線、磁場(chǎng)、超聲波、偽衛(wèi)星等多種定位方式[3]。其中基于WiFi的定位技術(shù)由于WiFi硬件的普及而受到重視[4]。在基于WiFi技術(shù)的室內(nèi)定位中，K近鄰(K-nearest neighbor，KNN)憑借其算法簡(jiǎn)單且易于實(shí)現(xiàn)的優(yōu)勢(shì)而得到廣泛的研究，早在2000年的時(shí)候，微軟就開始進(jìn)行WiFi指紋室內(nèi)定位的研究工作，并將KNN方法首次運(yùn)用到室內(nèi)定位中。

微軟研究院的Bahl等人[5]提出使用KNN方法進(jìn)行指紋定位，將待測(cè)指紋與指紋庫(kù)進(jìn)行匹配得到K個(gè)最相似的指紋實(shí)現(xiàn)定位。基于KNN算法，香港科技大學(xué)的Lionel 、Liu 、Lau等人[6]提出了加權(quán)K近鄰法(weighted K-nearest neighbors，WKNN)，按照待測(cè)指紋和離線數(shù)據(jù)庫(kù)在信號(hào)空間上的歐氏距離分配權(quán)重，定位精度得到了提升。韓國(guó)世宗大學(xué)的Beomju等人[7]提出了改進(jìn)加權(quán)EWKNN算法，通過改變K值來提高指紋識(shí)別的準(zhǔn)確性，同樣改善了定位效果。北京航空航天大學(xué)的牛建偉[8]等人提出了屬性加權(quán)KNN算法，將無線接入點(diǎn)(access point，AP)之間的相關(guān)性運(yùn)用到權(quán)重調(diào)配中，得到較好的定位成果。中國(guó)礦業(yè)大學(xué)的畢學(xué)京[9]等人提出了高斯函數(shù)定權(quán)的GWKNN室內(nèi)定位方法，這種方法有效改善了定位精度。文獻(xiàn)[10]基于K近鄰算法提出了一種監(jiān)督特征選擇方法，結(jié)合了距離加權(quán)和屬性加權(quán)的優(yōu)點(diǎn)進(jìn)行特征選擇，具有較好的預(yù)測(cè)性能，本文借鑒了該論文利用最近鄰的最相關(guān)屬性確定目標(biāo)變量的思想，提出了基于距離和屬性加權(quán)的室內(nèi)定位方法FWKNN。利用主特征RSS的權(quán)重計(jì)算加權(quán)距離，由該距離取代傳統(tǒng)的歐式距離，對(duì)K個(gè)最近鄰加權(quán)距離分配權(quán)重，在此基礎(chǔ)上利用卡爾曼濾波精確定位結(jié)果，有效提高了定位精度。

2 KNN室內(nèi)定位

2.1 基于RSS的WiFi指紋定位技術(shù)

WiFi指紋定位算法分為離線采樣和在線定位兩個(gè)階段。在離線階段，按網(wǎng)格點(diǎn)采集對(duì)應(yīng)RSS值，構(gòu)建離線指紋數(shù)據(jù)庫(kù)。在在線階段，實(shí)時(shí)獲取當(dāng)前RSS值，運(yùn)用某種定位算法，通過與離線數(shù)據(jù)庫(kù)進(jìn)行匹配來定位，如圖1所示。

圖1 基于RSS WiFi指紋定位技術(shù)原理

2.2 KNN室內(nèi)定位

KNN室內(nèi)定位算法是將在線測(cè)試點(diǎn)處的RSS值與離線數(shù)據(jù)庫(kù)中的RSS值進(jìn)行匹配，先計(jì)算測(cè)試點(diǎn)和參考點(diǎn)的RSS距離，然后選取K個(gè)最小距離，以及其對(duì)應(yīng)的參考點(diǎn)，最后對(duì)其坐標(biāo)取均值由此得出在線測(cè)試點(diǎn)的估計(jì)位置。

在離線階段要完成離線數(shù)據(jù)庫(kù)的構(gòu)建，將定位區(qū)域分為n個(gè)網(wǎng)格點(diǎn)，第i個(gè)網(wǎng)格點(diǎn)由坐標(biāo)Li(xi，yi)表示，i=1，2，…，n，假設(shè)該區(qū)域由m個(gè)WiFi AP覆蓋，在第i個(gè)網(wǎng)格點(diǎn)接收到的RSS值表示為Fi(ri1，ri2，…，rim)，rim表示該樣本中接收到來自第m個(gè)AP的RSS值，由此構(gòu)建離線指紋數(shù)據(jù)庫(kù)D=(Li，F(xiàn)i)。

(1)

(2)

3 距離和屬性加權(quán)的FWKNN

3.1 距離加權(quán)

距離加權(quán)的KNN算法的基本思想是：在線測(cè)試點(diǎn)與離線樣本的距離越小關(guān)系越密切，根據(jù)它們之間的距離大小給離線樣本賦予不同的權(quán)重，距離越小權(quán)重越大。權(quán)重是通過函數(shù)w(·)實(shí)現(xiàn)的距離變換而得到的。那么，用于預(yù)測(cè)的式(2)可以重寫為式(3)

(3)

對(duì)距離進(jìn)行權(quán)重賦值最簡(jiǎn)單的方法就是權(quán)重定義為距離的倒數(shù)，但是這種方法在距離很小時(shí)權(quán)重會(huì)很大甚至無限大，對(duì)算法造成干擾。為了克服這種缺點(diǎn)，選擇使用高斯函數(shù)來進(jìn)行權(quán)重計(jì)算，其形式如下

本文使用其標(biāo)準(zhǔn)正態(tài)分布形式，即b=0，c=1。為了保證距離為0時(shí)權(quán)重為1，令a=1，即函數(shù)w(·)可以表示為式子(4)，距離與權(quán)重的關(guān)系圖像如圖2所示。

(4)

圖2 距離與權(quán)重關(guān)系圖像

函數(shù)w∈[0，1]，滿足一下性質(zhì)

1)w(0)=1

2)函數(shù)w(·)遞減(較大的距離意味著較低的函數(shù)值)

3)limd→infw(d)=0

3.2 屬性加權(quán)

按屬性加權(quán)的KNN算法的基本思想是：當(dāng)屬性比較多的時(shí)候，這些屬性對(duì)結(jié)果的影響并不相同，可能會(huì)有一些無貢獻(xiàn)的屬性，所以不能對(duì)這些屬性一視同仁，如果沒有區(qū)別的去對(duì)待它們，那么在計(jì)算歐式距離時(shí)，一些關(guān)鍵屬性對(duì)結(jié)果的影響就會(huì)被削弱，使得最終結(jié)果出現(xiàn)較大偏差，所以需要對(duì)不同的屬性賦予不同的權(quán)重[8]。

把定位點(diǎn)接收到的RSS稱為主特征，因?yàn)镽SS在定位中是十分重要的，如圖3，假設(shè)有六個(gè)AP，一個(gè)定位點(diǎn)可以接收到來自六個(gè)AP的RSS值，即六個(gè)主特征，但這六個(gè)特征對(duì)定位結(jié)果的貢獻(xiàn)并不相同，如圖所示b點(diǎn)與AP6之間有障礙物的阻擋，此時(shí)b點(diǎn)接收到的來自AP6的RSS值并不準(zhǔn)確，會(huì)影響近鄰點(diǎn)a的選擇，造成定位結(jié)果的偏差。當(dāng)b點(diǎn)位于靠近AP6的角落時(shí)，受墻壁的折射影響也會(huì)更大，接收到來自AP6的RSS值同樣對(duì)定位結(jié)果的貢獻(xiàn)不大，會(huì)對(duì)更相關(guān)的主特征RSS定位造成影響。

圖3 RSS對(duì)定位性能的影響

受屬性加權(quán)思想的啟發(fā)，對(duì)Fi(ri1，ri2，…，rim)中的所有主特征分配一個(gè)權(quán)重，該權(quán)重確定主特征對(duì)于預(yù)測(cè)測(cè)試點(diǎn)坐標(biāo)的可靠性，這個(gè)可靠性使用在線測(cè)試點(diǎn)和離線樣本對(duì)應(yīng)RSS值的差(特征距離)來衡量，對(duì)不同的特征距離賦予不同的權(quán)重，特征距離越大所賦予的權(quán)重就越小，減小不相關(guān)主特征RSS對(duì)定位性能的影響。

(5)

采用高斯函數(shù)確定不同距離的特征的權(quán)重，即為特征權(quán)重，表示為式(6)

(6)

3.3 距離和屬性

本文提出的距離和屬性加權(quán)定位方法FWKNN結(jié)合了距離加權(quán)和屬性加權(quán)兩種方法的優(yōu)點(diǎn)，由最近鄰的最相關(guān)主特征RSS來預(yù)測(cè)在線測(cè)試點(diǎn)的位置。

(7)

此距離用于選擇最近鄰的K個(gè)坐標(biāo)Lj(j=1，2，…，K)，加權(quán)距離能夠更準(zhǔn)確的計(jì)算各點(diǎn)的距離并選擇合適的最近鄰點(diǎn)。

利用式(8)計(jì)算預(yù)測(cè)坐標(biāo)

(8)

為了說明所提出的加權(quán)距離的優(yōu)勢(shì)，本文基于仿真數(shù)據(jù)對(duì)傳統(tǒng)歐式距離和加權(quán)距離進(jìn)行了比較?？紤]4個(gè)測(cè)試點(diǎn)，2個(gè)參考點(diǎn)和4個(gè)WiFiAP接入點(diǎn)，由仿真獲取各點(diǎn)的坐標(biāo)及RSS值并進(jìn)行計(jì)算，如圖4所示。分別計(jì)算測(cè)試點(diǎn)與兩個(gè)參考點(diǎn)之間的實(shí)際坐標(biāo)距離比值rd，信號(hào)歐式距離比值ed、加權(quán)距離比值wed。表1是4個(gè)測(cè)試點(diǎn)與2個(gè)參考點(diǎn)間的信號(hào)歐氏距離和加權(quán)距離的比較?？梢钥闯觯c歐式距離相比，測(cè)試點(diǎn)和參考點(diǎn)間的加權(quán)距離的比值更接近于實(shí)際坐標(biāo)距離的比值，因此使用加權(quán)距離來選擇近鄰點(diǎn)是優(yōu)于傳統(tǒng)歐式距離的。

圖4 仿真獲取數(shù)值進(jìn)行計(jì)算

表1 信號(hào)歐式距離和加權(quán)距離

FWKNN算法的流程圖如圖5所示。

圖5 FWKNN算法流程圖

由上述定位方法可以得到在線測(cè)試點(diǎn)的一個(gè)位置估計(jì)，然后可以根據(jù)上一時(shí)刻的位置和速度來預(yù)測(cè)出當(dāng)前位置。綜合這個(gè)預(yù)測(cè)位置和定位方法所得的估計(jì)位置，對(duì)它們做一個(gè)加權(quán)平均作為最終定位結(jié)果，權(quán)值的大小由估計(jì)位置和預(yù)測(cè)位置的不確定性程度決定，本文按照卡爾曼濾波的方法做加權(quán)，由此得到一個(gè)更加精確的定位結(jié)果。

卡爾曼濾波器預(yù)測(cè)原理如下：

1)由上一時(shí)刻的狀態(tài)加上外界的輸入預(yù)測(cè)當(dāng)前狀態(tài)。

2)預(yù)測(cè)過程增加的新的不確定性，加上之前存在的不確定性構(gòu)成預(yù)測(cè)結(jié)果的不確定性。

3)計(jì)算卡爾曼增益(權(quán)重)，根據(jù)預(yù)測(cè)值和觀測(cè)值的不確定性來計(jì)算。

4)對(duì)預(yù)測(cè)值和觀測(cè)值這兩個(gè)結(jié)果做加權(quán)平均，得到當(dāng)前的一個(gè)狀態(tài)估計(jì)。

5)更新本次狀態(tài)估計(jì)的不確定性。

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

4.1 獲取RSS數(shù)據(jù)

本文使用實(shí)際測(cè)量的RSS數(shù)據(jù)建立離線指紋數(shù)據(jù)庫(kù)進(jìn)行定位算法的驗(yàn)證分析，定位環(huán)境設(shè)置在某實(shí)驗(yàn)樓五樓實(shí)驗(yàn)室，實(shí)驗(yàn)室放置了6個(gè)WiFiAP用于RSS數(shù)據(jù)的采集。定位區(qū)域長(zhǎng)為9.6m，寬為6.6m，測(cè)量時(shí)每隔0.3m進(jìn)行RSS數(shù)據(jù)測(cè)量，共673個(gè)參考點(diǎn)，以1s的頻率采集RSS值，在每個(gè)參考點(diǎn)處測(cè)量20s，然后取20次測(cè)量數(shù)據(jù)的平均值作為該參考點(diǎn)的測(cè)量結(jié)果，建立離線指紋庫(kù)。另外又測(cè)量了五個(gè)行走軌跡作為測(cè)試數(shù)據(jù)，每個(gè)軌跡包含40個(gè)測(cè)試點(diǎn)，如圖6所示。

圖6 定位區(qū)域示意圖

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

本文采用距離誤差作為性能指標(biāo)，對(duì)KNN、GWKNN[9]和FWKNN等定位算法進(jìn)行計(jì)算和比較，并且比較了FWKNN算法在卡爾曼濾波前后的結(jié)果，同時(shí)將FWKNN算法與多種定位模型進(jìn)行了比較。

圖7 不同數(shù)量最近鄰點(diǎn)下的平均定位誤差

為了驗(yàn)證所提出的算法能夠顯著提高定位精度，以軌跡1為測(cè)試數(shù)據(jù)進(jìn)行驗(yàn)證。首先對(duì)最近鄰點(diǎn)個(gè)數(shù)以及WiFiAP個(gè)數(shù)對(duì)定位性能的影響進(jìn)行探究。圖7是FWKNN算法在不同數(shù)量的最近鄰點(diǎn)下的平均定位誤差，從圖中可以看出結(jié)果隨著近鄰點(diǎn)個(gè)數(shù)的不同呈現(xiàn)出一個(gè)波動(dòng)的狀態(tài)，過大過小都會(huì)導(dǎo)致誤差增大，當(dāng)最近鄰點(diǎn)數(shù)為9時(shí)平均定位誤差最優(yōu)。圖8顯示了不同數(shù)量的WiFiAP對(duì)不同定位方法影響，可以看出6個(gè)AP足以用來進(jìn)行定位算法的驗(yàn)證比較。當(dāng)選取的最近鄰點(diǎn)個(gè)數(shù)為9時(shí)，F(xiàn)WKNN、GWKNN和KNN的定位誤差累計(jì)概率分布如圖9所示，從概率分布圖中可以得出FWKNN的平均誤差在2m以內(nèi)的概率約為70%，GWKNN的平均誤差在2m以內(nèi)的概率約為50%，KNN的平均誤差在2m以內(nèi)的概率為40%左右。

圖8 AP數(shù)量的影響

圖9 定位誤差累積概率分布圖

以軌跡1為測(cè)試數(shù)據(jù)，最近鄰點(diǎn)數(shù)為9對(duì)KNN、GWKNN和FWKNN進(jìn)行具體分析。表2是三種算法的定位誤差。從表中可以看出，從均值和最大值誤差來看，F(xiàn)WKNN方法都是優(yōu)于KNN和GWKNN的，誤差最小值較KNN和GWKNN大，但也沒有相差多少。以軌跡1為測(cè)試數(shù)據(jù)，就平均定位誤差而言，本文所提出的距離和屬性加權(quán)的定位方法FWKNN的定位精度與GWKNN相比提升了27.5%，與KNN相比提升了37.1%。

表2 定位誤差對(duì)比 m

本文嘗試使用卡爾曼濾波方法來精確FWKNN算法的定位結(jié)果，圖10為FWKNN在卡爾曼濾波前后的定位誤差累積概率分布圖對(duì)比，測(cè)試數(shù)據(jù)為軌跡1，最近鄰點(diǎn)數(shù)為9。表3是濾波前后定位誤差。經(jīng)卡爾曼濾波后的FWKNN算法雖然定位誤差均值較濾波前大，但是從定位誤差累積概率分布圖中可以看出，在2m內(nèi)的定位精度濾波后較濾波前是有明顯提升的，濾波后FWKNN算法的定位精度在2m以內(nèi)的概率提升到80%左右，而濾波前只有70%左右。

圖10 卡爾曼濾波前后定位誤差累積概率分布圖

表3 濾波前后定位誤差對(duì)比 m

為了更直觀的顯示本文所提出的FWKNN算法能有效提高定位精度，以五個(gè)行走軌跡為測(cè)試數(shù)據(jù)，對(duì)KNN、GWKNN和FWKNN等定位算法進(jìn)行計(jì)算和比較，圖11給出了測(cè)試點(diǎn)數(shù)為40～200時(shí)不同算法的平均定位誤差。從圖中可以看出，F(xiàn)WKNN算法的定位誤差始終低于其它兩種算法。總體而言，當(dāng)選取的最近鄰點(diǎn)個(gè)數(shù)為9，測(cè)試點(diǎn)個(gè)數(shù)為200時(shí)，本文所提出的FWKNN算法的平均定位誤差為1.96m，與KNN和GWKNN相比分別提升了34.6%和27.1%。

圖11 不同個(gè)數(shù)測(cè)試點(diǎn)的平均定位誤差比較

表4是當(dāng)測(cè)試點(diǎn)個(gè)數(shù)為200時(shí)，本文提出的FWKNN定位算法與多種定位模型的定位均值誤差表。由表4可以看出本文提出的FWKNN定位算法的定位精度優(yōu)于支持向量回歸等多種定位模型。

表4 多種定位方法的均值誤差比較 m

5 結(jié)語

本文提出了距離和屬性加權(quán)的KNN室內(nèi)定位方法FWKNN，結(jié)合了距離加權(quán)和屬性加權(quán)這兩者的優(yōu)點(diǎn)，利用主特征RSS的權(quán)重計(jì)算加權(quán)距離，該距離取代了傳統(tǒng)的歐式距離，對(duì)K個(gè)最近鄰加權(quán)距離分配權(quán)重，加權(quán)均值，由最近鄰的最相關(guān)主特征RSS預(yù)測(cè)測(cè)試點(diǎn)坐標(biāo)。與KNN、GWKNN等定位算法相比，考慮到了主特征RSS的權(quán)重，能夠更準(zhǔn)確的計(jì)算各點(diǎn)的距離并選擇合適的最近鄰點(diǎn)，平均定位精度分別提高了34.6%和27.1%。并且實(shí)驗(yàn)證明了卡爾曼濾波能夠精確定位結(jié)果，濾波后FWKNN算法的平均定位誤差在2m以內(nèi)的概率由原來的70%左右提升到80%左右。同時(shí)實(shí)驗(yàn)結(jié)果還表明，F(xiàn)WKNN算法與其它多種定位模型相比都具有一定優(yōu)勢(shì)。