一種改進的WIFI位置指紋室內(nèi)定位算法

謝世成,余學(xué)祥,趙佳星,汪 濤,童子良

(1.安徽理工大學(xué) 空間信息與測繪工程學(xué)院,安徽 淮南 232001; 2.安徽理工大學(xué) 礦山采動災(zāi)害空天地協(xié)同監(jiān)測與預(yù)警安徽普通高校重點實驗室,安徽 淮南 232001; 3.安徽理工大學(xué) 礦區(qū)環(huán)境與災(zāi)害協(xié)同監(jiān)測煤炭行業(yè)工程研究中心,安徽 淮南 232001)

隨著移動智群感知技術(shù)與物聯(lián)網(wǎng)技術(shù)的發(fā)展,人們對于位置信息的需求日益迫切[1]。室外環(huán)境下,全球?qū)Ш叫l(wèi)星系統(tǒng)(global navigation satellite system,GNSS)憑借其出色的表現(xiàn),滿足各種位置服務(wù)的需求。但是對于建筑物內(nèi)或大型遮蔽場所內(nèi)的導(dǎo)航定位，由于衛(wèi)星信號被遮擋而不具有持續(xù)的精確位置測算能力[2]。相對于室外,室內(nèi)環(huán)境中信號傳播的多徑和陰影效應(yīng)等因素導(dǎo)致定位難度更大。由于人類大部分活動都處于室內(nèi)環(huán)境,實現(xiàn)精確的室內(nèi)定位,既有技術(shù)需求，同時也有十分重要的現(xiàn)實意義[3]。目前主要的室內(nèi)定位技術(shù)有基于WIFI、低功耗藍牙[4]、射頻識別[5]、超寬帶[6]、ZigBee[7]、超聲波[8]、視覺[9]等,隨著無線局域網(wǎng)(wireless local area networks,WLAN)技術(shù)的發(fā)展,基于WIFI的位置指紋定位逐漸成為主流技術(shù)。該技術(shù)主要包含離線采集和在線定位2個階段[10]。離線階段通過接收端接收的接收信號強度(received signal strength,RSS)構(gòu)造與參考點之間的一一映射關(guān)系;在線階段,待定位點通過RSS匹配算法實現(xiàn)位置估計,在WIFI覆蓋率足夠高的情況下,僅通過軟件即可實現(xiàn)定位,避免了硬件成本的增加,具有低成本、高精度等優(yōu)點。

確定待定位點的位置是位置指紋定位方法最關(guān)鍵的一步,即通過實時接收的信號強度與數(shù)據(jù)庫進行匹配,找出相似度最高的若干個數(shù)據(jù)。目前,典型的匹配算法主要有最近鄰法、核函數(shù)法、最大似然概率法、神經(jīng)網(wǎng)絡(luò)法、樸素貝葉斯法、支持向量回歸法等[11]。最近鄰算法(K-nearest neighbor,KNN)作為最基本的匹配算法,最先應(yīng)用在微軟的RADAR[12]系統(tǒng),但是其存在定位精度不高且系統(tǒng)穩(wěn)定性差等缺點。人們在此基礎(chǔ)上提出了加權(quán)K最近鄰(weightedK-nearest neighbor,WKNN)算法。相比KNN算法,WKNN算法通過賦予權(quán)重選擇K值,能夠提高邊緣位置點的定位精度,因而成為目前最常用的匹配算法。

本文針對室內(nèi)環(huán)境對接入點信號強度造成干擾的情況,采用基于方差修正距離的加權(quán)KNN匹配算法。根據(jù)參考點RSS的均值和方差信息,重新定義了歐式距離,通過對不同誤差的信號強度值進行不同幅度的修正,使計算的歐式距離更加準(zhǔn)確,從而可以更準(zhǔn)確地選擇K值進行定位。

1 位置指紋定位原理

基于WIFI信號強度的位置指紋定位算法主要原理[13]是:離線階段,將定位區(qū)域離散化,在每個離散點(參考點)采集RSS信息,提取其特征向量作為唯一的指紋信息,并與實際物理位置一一對應(yīng),存入數(shù)據(jù)庫;定位時,通過匹配算法找到數(shù)據(jù)庫中與待定位點RSS特征相似度最高的點進行位置估計。

離線階段主要工作分為兩步:

(1) 在定位區(qū)域選取適當(dāng)數(shù)量的參考點,然后在每個參考點采集來自不同訪問接入點(access point,AP)的信號強度。

(2) 對采集的原始數(shù)據(jù)進行離群值剔除、濾波等預(yù)處理,提取處理后的數(shù)據(jù)特征作為指紋信息,并與參考點的位置關(guān)聯(lián),存入數(shù)據(jù)庫。

設(shè)R為指紋數(shù)據(jù)庫的集合,結(jié)構(gòu)如下:

(1)

(2)

PFDB=[Loc,R]

(3)

在線階段,在定位區(qū)域隨機采集信號強度,預(yù)處理后利用匹配算法計算采集的數(shù)據(jù)與數(shù)據(jù)庫中數(shù)據(jù)的相似性,選取相似度高的信號強度所對應(yīng)的位置,將其賦予該點。具體流程如圖1所示。

圖1 位置指紋定位流程

實時定位階段目前常采用加權(quán)K最近鄰算法匹配位置。通常來說,就是通過移動終端實時采集信號強度組成RSS向量,計算指紋庫中對應(yīng)RSS向量的相似度,選擇K個相似度高的向量對應(yīng)的參考點,進行加權(quán)平均得到待定位點的估計位置。

(4)

2 基于方差修正距離的WKNN算法

加權(quán)K最近鄰算法中,通常使用歐式距離衡量2個信號強度向量之間的相似性[14],將歐式距離的倒數(shù)作為權(quán)值代入后面的計算。由于室內(nèi)環(huán)境中障礙物遮擋、人員流動、多徑效應(yīng)等復(fù)雜環(huán)境的影響,采樣點上采集到的RSS會有一定程度的波動,使得計算的歐式距離并不準(zhǔn)確。因此本文采用了一種基于方差的WKNN匹配算法對歐式距離進行修正。

2.1 傳統(tǒng)歐式距離

離線采集階段,定位區(qū)域中某一參考點j接收到的N個AP的信號強度值為:

(5)

則定位點i與參考點j的歐式距離Dij為:

(6)

雖然歐式距離能夠直觀反映同一空間中2種信號強度的差異性,但是信號強度的變化不僅僅受定位點物理位置的影響,信號自身的波動也會導(dǎo)致歐式距離的改變。

2.2 方差加權(quán)歐式距離

針對歐氏距離受RSS波動影響的問題,對(6)式改進得到:

(7)

其中,dk為針對每個AP信號值的改正權(quán)值,通過賦予測量準(zhǔn)確的信號較大的權(quán)值,使得計算的歐式距離更加準(zhǔn)確。然而僅通過測量值并不能得到誤差,因此在建庫階段根據(jù)每個AP采集的RSS值計算誤差信息,將其作為標(biāo)準(zhǔn)與定位階段采集的RSS值對比,從而計算測量誤差。文獻[15]通過實驗發(fā)現(xiàn),距離AP越近,信號強度值越大,信號波動的概率越小;距離AP越遠,信號強度值越小,波動概率越大,同時信號強度的方差也較大;信號強度的方差與均值之間存在如下線性關(guān)系:

Var=aMean+b

(8)

建庫階段利用采集的信號強度值的方差和均值計算每個AP的a、b,其中a和b是線性函數(shù)的參數(shù)，并與參考點位置一起存入數(shù)據(jù)庫,離線階段將實時采集的RSS均值代入(9)式,計算近似方差值。通過上面的分析可知,數(shù)據(jù)的方差越小,表明此時的信號越穩(wěn)定,可靠性越高。在計算歐式距離時應(yīng)該賦予較大的權(quán)重,因此利用方差的倒數(shù)作為實時測量值的權(quán)重,即

(9)

2.3 改進WKNN算法流程

在線階段，在參考點處采集各個AP的信號強度值,經(jīng)過卡爾曼濾波后計算均值和方差,并與該點位置一起存入數(shù)據(jù)庫;利用實時采集的RSS均值計算每個AP的近似方差,同時根據(jù)每個AP的修正權(quán)重對歐式距離進行改正;最后按照K-最近鄰算法確定待定位點的估計位置。改進的WKNN算法流程如圖2所示。

圖2 改進的WKNN算法流程

3 實驗驗證與分析

3.1 實驗環(huán)境

實驗選取安徽理工大學(xué)測繪學(xué)院南103實驗室為測試環(huán)境,實驗區(qū)域大小約為9 m×9 m,定位區(qū)域平面圖如圖3所示。

圖3 定位區(qū)域平面圖

在房間4個角分別部署4個AP,以1 m為間隔,布設(shè)100個參考點。在每個參考點采集100次數(shù)據(jù),經(jīng)過卡爾曼濾波后,計算RSS的均值和方差,與參考點位置一起存入數(shù)據(jù)庫。實時定位階段,在定位區(qū)域選取24個點,每個點采集10次數(shù)據(jù),經(jīng)過處理后計算定位點位置。

為了驗證本文提出的WKNN算法的可行性和有效性,利用同一組數(shù)據(jù)分別使用普通加權(quán)K最近鄰算法、K最近鄰算法和K-means-EWKNN計算待定點位置,對比最終的定位結(jié)果。

3.2 數(shù)據(jù)預(yù)處理

WIFI接收信號強度屬于鏈路層信息,易受多徑傳播、人體吸收、陰影效應(yīng)等因素的影響[16]。本文對所采集信號強度的特征進行分析,采用卡爾曼濾波方法進行降噪。

以定位區(qū)域內(nèi)某一AP為例,采集500次數(shù)據(jù)進行統(tǒng)計分析,可以看出RSS易受環(huán)境干擾,波動較大,同時存在少量離群值。針對這種問題,本文首先使用3σ檢測法剔除離群值,然后利用卡爾曼濾波對數(shù)據(jù)進行降噪,結(jié)果表明卡爾曼濾波對信號起到良好的平滑作用。

圖4 卡爾曼濾波結(jié)果

3.3 結(jié)果與分析

本文采用定位誤差,累計誤差概率分布和平均定位誤差,評價4種方法的定位精度，結(jié)果如圖5、圖6所示。

圖5 定位誤差

圖6 累計誤差概率分布

4種定位方法誤差對比見表4所列。

從圖5、圖6、表1可見,改進的WKNN算法在面對RSS信號非線性波動時,具有良好的穩(wěn)定性,能夠減小定位誤差,提高定位精度。改進的WKNN算法的平均定位精度為1.248 m,相比普通WKNN算法精度提升了20.3%,相比KNN算法精度提升1倍左右。對比最新的位置指紋算法,改進的WKNN算法整體性能優(yōu)秀,雖然個別點的定位精度落后于K-means-EWKNN算法,但是改進的WKNN算法具有定位時間短、誤差波動小等優(yōu)勢。

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

從誤差分布來看,改進的WKNN算法誤差在2 m以內(nèi)的概率達到80%左右,優(yōu)于其他3種定位算法，表明結(jié)合了卡爾曼濾波的方差修正距離的WKNN算法在一定程度上改善了WIFI信號不穩(wěn)定帶來的定位誤差問題。

4 結(jié) 論

本文針對指紋定位過程中RSS信號不穩(wěn)定的問題,設(shè)計了一種基于方差修正距離的WKNN匹配算法。首先采用卡爾曼濾波對指紋庫進行預(yù)處理,剔除誤差較大的數(shù)據(jù);然后通過實時測量的RSS均值計算方差修正權(quán)值;最后通過加權(quán)K最近鄰算法實現(xiàn)定位。

實驗結(jié)果表明,改進的WKNN算法平均定位精度達到1.248 m,對比普通WKNN算法以及K-means-EWKNN算法有效提高了定位精度,在一定程度上降低了由于RSS信號不穩(wěn)定產(chǎn)生的誤差。