K近鄰快速匹配的WiFi指紋定位方法*

羅宇鋒， 劉艷輝, 王國(guó)東

(1.河南理工大學(xué) 電氣工程與自動(dòng)化學(xué)院,河南 焦作 454003；2.無錫九宇建筑設(shè)計(jì)院有限公司,江蘇 無錫 214000)

0 引 言

無線局域網(wǎng)(WiFi)室內(nèi)指紋定位具有成本低、易部署、不受視線約束等優(yōu)點(diǎn)，已經(jīng)成為當(dāng)前室內(nèi)定位研究的熱點(diǎn)[1～3]。對(duì)室內(nèi)WiFi指紋定位的研究中，Yang Z等人[4]使用監(jiān)聽物理層信道的狀態(tài)進(jìn)而提高WiFi指紋定位的精度。Laouudias C等人[5]基于指紋匹配的基礎(chǔ)上，開發(fā)Airplace系統(tǒng)，使WiFi指紋定位的誤差減小到2～4 m。Fang S H等人[6]通過從已測(cè)得的接收信號(hào)強(qiáng)度指示(received signal strength indication,RSSI)信號(hào)強(qiáng)度中取出特征性較強(qiáng)的信號(hào)，從而降低了室內(nèi)多徑效應(yīng)對(duì)WiFi信號(hào)波動(dòng)的影響，使室內(nèi)指紋定位精度提高了40 %。Zandbergen P A等人[7]將WiFi與A-GPS、蜂窩定位進(jìn)行聯(lián)合，進(jìn)一步的提高室內(nèi)定位的精度。

本文采用高斯函數(shù)擬合和多次測(cè)量取平均值的方法來消除環(huán)境等因數(shù)對(duì)RSSI產(chǎn)生波動(dòng)，使指紋庫(kù)的數(shù)據(jù)更加準(zhǔn)確和可靠；以距離為相似性測(cè)度的方法對(duì)數(shù)據(jù)庫(kù)進(jìn)行優(yōu)化分類；通過引入相同接入點(diǎn)(access point,AP)數(shù)目作為參數(shù)，改進(jìn)了K近鄰匹配算法，并在對(duì)數(shù)據(jù)庫(kù)分類的基礎(chǔ)上，實(shí)現(xiàn)快速K近鄰匹配算法，算法能去除冗余的數(shù)據(jù)，從而有效提高了匹配的精確度和速度。

1 基于WiFi指紋定位描述

環(huán)境對(duì)WiFi信號(hào)的多徑傳播的制約性很強(qiáng)[8]，信號(hào)的特征性很強(qiáng)，對(duì)于每一個(gè)固定的采樣點(diǎn)，其信道的多徑結(jié)構(gòu)(即“指紋”)。定位卡在未知位置點(diǎn)上接收來自各個(gè)AP的信號(hào)強(qiáng)度與事先儲(chǔ)存在WiFi指紋庫(kù)中的信號(hào)強(qiáng)度進(jìn)行匹配，實(shí)現(xiàn)對(duì)未知位置點(diǎn)的最佳估計(jì)。

1.1 RSSI信號(hào)處理

RSSI在定位起到重要的作用，RSSI的值越大，表明信號(hào)強(qiáng)度越大。由于信號(hào)的多徑傳播受環(huán)境影響很大，RSSI的值隨測(cè)量距離的增大出現(xiàn)了不同程度的消減，隨著時(shí)間的推移對(duì)應(yīng)RSSI值也出現(xiàn)了不同程度的波動(dòng)[9]。為了保證指紋數(shù)據(jù)庫(kù)可靠性和準(zhǔn)確性，本文先利用高斯函數(shù)擬合對(duì)采集的RSSI信號(hào)進(jìn)行擬合，迅速選出高頻段的RSSI。對(duì)于RSSI值的波動(dòng)，用多次測(cè)量取平均值法對(duì)采樣點(diǎn)接收的信號(hào)進(jìn)行平滑處理。

高斯函數(shù)運(yùn)用于采樣點(diǎn)接收到的RSSI數(shù)據(jù)處理，可以去除一些小概率的數(shù)值(野值)，保留在正常范圍內(nèi)波動(dòng)的高頻WiFi信號(hào)值，使WiFi信號(hào)值接近真實(shí)的信號(hào)值。

高斯擬合函數(shù)為

(1)

先將采集到的RSSI矢量分別代入高斯擬合函數(shù)，用來保留可信的信號(hào)值然后對(duì)所保留的數(shù)據(jù)取均值，所得均值就是采樣點(diǎn)的RSSI矢量。由于RSSI矢量數(shù)據(jù)眾多，減少高斯擬合過程耗時(shí)，為了快速的篩選出想要的數(shù)據(jù)，采用近高斯擬合的方法

|RSSIi-μ|

(2)

式中μ為均值；σ為標(biāo)準(zhǔn)差；k為篩選區(qū)間RSSI值的個(gè)數(shù)，可根據(jù)數(shù)據(jù)保留的百分比M確定

(3)

式中N為采集的總次數(shù)。

若M取值過小，有可能破壞真實(shí)的數(shù)據(jù)，需適當(dāng)增加k值用來增大篩選區(qū)間，提高RSSI矢量的保留比。在保證RSSI矢量不是真的情況下，快速有效地剔除錯(cuò)誤數(shù)據(jù)。

1.2 WiFi指紋庫(kù)訓(xùn)練階段

1.2.1 定位區(qū)域的設(shè)定

首先，將定位的區(qū)域按照事先設(shè)計(jì)好的大小，分為若干個(gè)網(wǎng)格，每一個(gè)網(wǎng)格的頂點(diǎn)就是一個(gè)采樣點(diǎn)；其次，確定坐標(biāo)原點(diǎn)并按照一定規(guī)則對(duì)參考點(diǎn)進(jìn)行編號(hào)，確定采樣點(diǎn)的坐標(biāo)位置，如圖1所示。

圖1 定位區(qū)域表格建立的坐標(biāo)示意

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

1.2.3 指紋數(shù)據(jù)庫(kù)分類

1)在建立好的指紋庫(kù)中選取若干個(gè)采樣點(diǎn)與圓心點(diǎn)A(XA,YA)間的距離小于或等于R作為A類,即

(4)

選擇不同的分類圓心，依照上式進(jìn)行分類，可以在整個(gè)定位區(qū)域形成許多以R為半徑的分類圓。如圖2所示。

圖2 基于WiFi信號(hào)強(qiáng)度分類的示意

2)根據(jù)圓半徑進(jìn)行分類，將會(huì)有若干個(gè)的孤點(diǎn)無法分類，把剩下的所有孤點(diǎn)作為孤點(diǎn)數(shù)據(jù)庫(kù)。

1.3 未知位置點(diǎn)的分類

在定位匹配階段，當(dāng)移動(dòng)用戶走到一個(gè)未知的位置，定位卡首先掃描周圍的AP，得到自身的RSSI矢量，根據(jù)定位卡實(shí)時(shí)接收的RSSI矢量確定所屬的類，假定未知位置點(diǎn)的坐標(biāo)(XtYt)=[R1R2…Ri…RW]，分類的思想為：以未知位置點(diǎn)與類別中心點(diǎn)的信號(hào)強(qiáng)度的均方誤差最小P作為分類依據(jù)，如果均方誤差大于P就把此未知位置點(diǎn)歸到孤點(diǎn)數(shù)據(jù)庫(kù),P的取值是與實(shí)際地理環(huán)境和R的取值有關(guān)

(5)

1.4 改進(jìn)K近鄰匹配算法

WiFi指紋匹配最常用的是信號(hào)空間K近鄰算法。在線定位時(shí)，定位卡首先掃描各個(gè)AP得到信號(hào)強(qiáng)度矢量SR=[R1R2…Ri…Rw]，其中，Ri(1?i?w)表示接收第i個(gè)AP的信號(hào)矢量，然后根據(jù)上述的分類規(guī)則，計(jì)算與建立好的分類指紋庫(kù)中的每一個(gè)采樣點(diǎn)的相似度Li?？紤]到AP的傳輸距離為100 m，當(dāng)定位區(qū)域過大時(shí)采樣點(diǎn)就不能接收所有AP發(fā)出的信號(hào)，使得在空間距離相近的區(qū)域內(nèi)采集到相同AP數(shù)目較多，相反，使得在空間距離較遠(yuǎn)的區(qū)域內(nèi)采集到相同AP數(shù)目較少，因此，具有相同數(shù)目AP矢量在空間距離也相近。通過引入相同AP數(shù)目作為參數(shù)，計(jì)算相似度L，可以提高WiFi指紋匹配度

(6)

式中Mi為在線匹配階段定位卡在未知位置點(diǎn)的AP和在第i個(gè)采樣點(diǎn)AP的總數(shù)目；Msi為在線匹配階段定位卡在未知位置點(diǎn)的AP和在第i個(gè)采樣點(diǎn)相同AP的數(shù)目。圖3為接收WiFi信號(hào)的示意，R1，R2為采樣點(diǎn)，R1接收AP1，AP2，AP4，AP5的信號(hào)，R2接收AP2，AP3，AP5，AP6的信號(hào)。定位手機(jī)接收AP2，AP5的信號(hào)，在計(jì)算R1的相似度時(shí)，M1=6，Ms1=2。

圖3 接收WiFi信號(hào)的示意

對(duì)所求的L進(jìn)行排序并選取前K個(gè)較小的L所對(duì)應(yīng)的坐標(biāo){P1,P2,…，Pi,Pk}(1?i?K),最終的定位結(jié)果為

(7)

本文采用改進(jìn)的K近鄰快速匹配定位原理如圖4。

圖4 K近鄰快速匹配算法原理

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

2.1 實(shí)驗(yàn)部署

實(shí)驗(yàn)區(qū)域?yàn)殚L(zhǎng)12 m，寬12 m，每隔3 m取一個(gè)采樣點(diǎn)，共有25個(gè)采樣點(diǎn)，在每個(gè)采樣點(diǎn)處分別采集100次RSSI值經(jīng)高斯擬合后取均值存入指紋庫(kù)。實(shí)現(xiàn)快速的K近鄰匹配算法分類的半徑R=3 m,建立A，B，C，D和所有的孤點(diǎn)為一大類的孤點(diǎn)數(shù)據(jù)庫(kù)。如圖5所示。

圖5 實(shí)驗(yàn)部署

實(shí)驗(yàn)采用基于Android平臺(tái)開發(fā)的WiFi分析儀采集監(jiān)測(cè)區(qū)域內(nèi)的信號(hào)強(qiáng)度，采用SQL Serve 2008創(chuàng)建指紋數(shù)據(jù)庫(kù)，將其配置到定位服務(wù)器，給服務(wù)器端程序提供數(shù)據(jù)支持，采用基于J2EE平臺(tái)開發(fā)出的定位服務(wù)器負(fù)責(zé)接收客戶端上傳的數(shù)據(jù)并對(duì)其進(jìn)行解析、計(jì)算、匹配最終實(shí)現(xiàn)定位。

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

2.2.1 定位精度

在實(shí)驗(yàn)區(qū)域進(jìn)行了多次定位實(shí)驗(yàn)，并記錄了定位的結(jié)果。如圖6所示從定位結(jié)果的最大誤差分析，經(jīng)過分類后的定位最大誤差有了很大改善，可以看出，經(jīng)過數(shù)據(jù)分類后的K近鄰匹配在定位精度上明顯優(yōu)越于傳統(tǒng)的K近鄰匹配，最大平均誤差從4.17 m降到了2.12 m，其中最大的改善從8.8 m降到1.9 m。說明分類后改進(jìn)的K近鄰使得定位結(jié)果跳動(dòng)范圍縮小。

圖6 單點(diǎn)定位誤差效果

2.2.2 定位時(shí)間

K近鄰法主要耗時(shí)用于均方誤差的計(jì)算。在實(shí)驗(yàn)中將25個(gè)采樣點(diǎn)，分為A，B，C，D類和孤點(diǎn)的一大類，圓類別中有5個(gè)采樣點(diǎn)，孤點(diǎn)數(shù)據(jù)庫(kù)有9個(gè)采樣點(diǎn)。傳統(tǒng)的K近鄰需要遍歷整個(gè)數(shù)據(jù)庫(kù)，計(jì)算25次均方誤差，分類別后最多進(jìn)行9次均方誤差的計(jì)算。隨著數(shù)據(jù)庫(kù)中的采樣點(diǎn)不斷增多，分類改進(jìn)后K近鄰算法的優(yōu)勢(shì)就越來越明顯。2種算法平均定位耗時(shí)K近鄰為52.8 ms，改進(jìn)K近鄰為19.6 ms。

3 結(jié) 論

本文提出基于WiFi信號(hào)強(qiáng)度分類的快速K近鄰匹配定位法，詳細(xì)地介紹了該算法的實(shí)現(xiàn)原理和步驟,并對(duì)提出的算法進(jìn)行了實(shí)測(cè)。實(shí)驗(yàn)結(jié)果表明本文算法定位花費(fèi)的時(shí)間減少了62.8 %,定位的精度比傳統(tǒng)的K近鄰匹配也有所提高，能有效提高WiFi指紋定位系統(tǒng)的性能。