基于邊界過濾和鄰域均值濾波的室內(nèi)定位算法

郭昕剛， 李 航， 宮 鴻

(長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

基于邊界過濾和鄰域均值濾波的室內(nèi)定位算法

郭昕剛， 李 航*， 宮 鴻

(長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

在構(gòu)建位置指紋庫時，采用過濾法剔除數(shù)據(jù)采集階段位于邊界的位置指紋點，使用鄰域均值算法濾除指紋庫中指紋的噪聲點。將指紋庫k-means聚類為合適的k個指紋類以表示相似的位置指紋點，再用加權(quán)k近鄰法實現(xiàn)精確定位。 實驗證明，相對于傳統(tǒng)未對RSSI信號做處理的定位算法，該算法平均定位精度提高了28.9%。

位置指紋定位； 鄰域均值濾波；k-means聚類； 加權(quán)k近鄰

0 引 言

近年來，室內(nèi)定位成為當(dāng)今定位技術(shù)的主要研究方向之一[1]。室內(nèi)定位已成熟運(yùn)用在各種場所，如大型超市、購物商場、產(chǎn)品倉庫以及緊急事件的救援等[2]。室內(nèi)定位常用的定位方法是：基于到達(dá)時間、到達(dá)角度和WIFI位置指紋的方法[3]，而基于到達(dá)時間和到達(dá)角度的方法對測量儀器的精度要求較高，限制了定位的條件，適應(yīng)程度較低[4]。WIFI位置指紋定位方法對器材要求低，普適性好，覆蓋范圍廣，已成為應(yīng)用最為廣泛的室內(nèi)定位方法[5]。劉志鵬[6]等在采集位置指紋信息時，對指紋庫的數(shù)據(jù)做均值處理，雖然一定程度上減小了邊界值對定位效果的影響，但是仍然將影響定位精度的指紋點帶入實驗，對定位會造成一些不可控的結(jié)果。Altintas[7]等對采集的指紋數(shù)據(jù)進(jìn)行取中值處理，避免了將邊界數(shù)據(jù)引入實驗，但是以中值的形式來作代表性數(shù)據(jù)穩(wěn)定性較差，在實驗中并不適合這樣做。當(dāng)取大量指紋點構(gòu)建指紋庫時，定位階段會消耗大量時間對指紋點進(jìn)行遍歷，降低了定位的效率，對指紋庫進(jìn)行聚類處理可以有效地提高定位效率[8-9]。傳統(tǒng)的定位方法主要是KNN算法，默認(rèn)參與定位的指紋點對定位點的貢獻(xiàn)度相同，沒有考慮指紋點的特殊性。

對于以上問題，文中通過對采樣的指紋點使用過濾法進(jìn)行過濾，濾除邊界指紋點，再對剩余指紋點做均值處理，避免了邊界點對定位的影響；指紋庫構(gòu)建完成之后，對指紋庫進(jìn)行鄰域均值濾波處理，確定鄰域形狀和范圍，濾除鄰域中因環(huán)境因素造成的指紋噪聲點，對指紋庫進(jìn)行遍歷，消除所有噪聲點；定位階段應(yīng)用KNN算法的思想，引入權(quán)值對參與定位的指紋點進(jìn)行貢獻(xiàn)度的判定，對于貢獻(xiàn)度大的指紋點取較大的權(quán)值，更有利于提高定位的穩(wěn)定性。

1 邊界過濾和鄰域均值混合濾波

1.1 邊界過濾法剔除邊界噪聲點

在空間中自由傳播信號的強(qiáng)度值是具有連續(xù)性的，而當(dāng)接收點離信號源的距離越來越遠(yuǎn)的時候，RSSI值會服從距離的損耗模型。同樣，對于AP節(jié)點發(fā)射的信號，其強(qiáng)度值會隨距離的增加而衰減。對此，引入對數(shù)-常態(tài)分布模型來分析信號的衰減。設(shè)p0為AP節(jié)點發(fā)射的信號功率，距離AP節(jié)點dm處接收到的信號強(qiáng)度為RSSI，則：

式中：p(d)----經(jīng)過dm后的路徑損耗。

式中：P(d0)----經(jīng)過d0距離后的損耗。

設(shè)在d0處的信號強(qiáng)度為R，則可以得到：

d0通常取單位距離1 m，x0均值為0，可以簡單表示為：

R和n都是環(huán)境參數(shù)，說明RSSI值隨著距離增加呈對數(shù)衰減，當(dāng)指紋點距離AP較遠(yuǎn)時，這些指紋點RSSI值波動較大，甚至?xí)绊懚ㄎ痪龋褂眠^濾法將這些對定位貢獻(xiàn)程度較低的指紋點過濾掉。

過濾法簡單描述如下：在構(gòu)建指紋庫前，對各指紋點采集來自各個AP的RSSI值各100次，每隔1 s采集一次。因為某些指紋點距離AP較遠(yuǎn)，信號值波動較大，甚至出現(xiàn)對應(yīng)相同的指紋點和AP，某些時刻掃描不到其RSSI值，這就是所謂的邊界值；統(tǒng)計每個指紋點處對應(yīng)各個AP信號出現(xiàn)的次數(shù)，出現(xiàn)次數(shù)在60次以下的判定為臨近邊界的指紋點，計算RSSI數(shù)據(jù)出現(xiàn)次數(shù)在60～70次的AP平均值作為閾值；對每個指紋點采集100次RSSI值做均值處理，當(dāng)RSSI均值小于閾值時，剔除該指紋點上采集的對應(yīng)AP的數(shù)據(jù)。

過濾法的目的是得到最佳的定位指紋點，保證每一個指紋點接收到各個AP的RSSI值波動范圍較小，為構(gòu)建穩(wěn)定的指紋庫做好充分的準(zhǔn)備。

1.2 鄰域均值濾波濾除內(nèi)部噪聲點

鄰域均值濾波也是對指紋點進(jìn)行去噪處理，但是和過濾法不同的是鄰域均值濾波是在建立了指紋庫之后進(jìn)行的。在建立指紋庫階段，雖然通過過濾法采集到可靠性較高的數(shù)據(jù)，但是在采集過程中難免受到一些不可控因素的影響，比如人員的走動，障礙物暫時的干擾等，這樣會導(dǎo)致某一指紋點和周圍指紋點信號強(qiáng)度相差較大，這就是指紋庫中的噪聲點，為了濾除噪聲點，引入鄰域均值濾波算法進(jìn)行濾波處理。

鄰域均值濾波一般對一個指紋點周圍8或12個指紋點進(jìn)行分析濾波，鄰域形狀取規(guī)則的軸對稱形狀，內(nèi)部指紋點均勻分布，因為對指紋庫遍歷計算量較大，所以選擇8鄰域濾波。正方形鄰域的8和12鄰域分別如圖1和圖2所示。

圖1 正方形8鄰域

圖2 正方形12鄰域

圖中黑點為中心指紋點，選取鄰域的目的就是判斷中心點是否為噪聲。

為判斷中心點是否為噪聲點，這里引入信號強(qiáng)度相似度的概念。如果中心點為正常指紋點，則周圍的鄰域點與其相似度較高；若中心點為噪聲點，則與鄰域點的相似度較低。因此，判斷指紋點是否為噪聲點需要對指紋庫中各指紋點的鄰域進(jìn)行遍歷，對指紋庫中一個指紋點進(jìn)行判斷的示意圖如圖3所示。

圖3 指紋點噪聲判斷圖

點越大代表接收到信號越強(qiáng)。AP節(jié)點的信號符合距離的損耗模型，距離越遠(yuǎn)，信號強(qiáng)度越低，穩(wěn)定性越差，波動范圍越大。圖3中圈出的范圍內(nèi)，中心點的RSSI值明顯異于其鄰域內(nèi)的其他指紋點，初步假設(shè)中心點為噪聲點，如果中心點與其鄰域的各指紋點相似度的平均值大于鄰域范圍內(nèi)其他指紋點與各自的鄰域指紋點相似度的平均值，則可以判定該中心點為噪聲點。將圈出來的鄰域標(biāo)號，用DFc表示點Fc的鄰域，用D表示包含F(xiàn)c的整個區(qū)域。用R(x,y)表示x點和y點的信號相似度，Rx、Ry為x和y點處的RSSI值。

在指紋點Fc的鄰域中,Fi與Fi周圍的指紋點(包括Fc)相似度的和與平均值為：

在區(qū)域D中，除了中心點以外所有與其相鄰點相似度的平均值為：

Fc與其鄰域各點相似度的總和與平均值為：

2 k-means聚類

當(dāng)指紋庫中的指紋點數(shù)量較多時，定位階段對所有指紋點進(jìn)行遍歷是一件很繁瑣的事情，并且影響了定位的效率，文中在定位前對指紋庫先做k-means聚類，將指紋點聚類為k個大類，可以先實現(xiàn)定位點的粗略定位，然后再與待定位點最相似的類中對指紋點進(jìn)行遍歷定位。這里對指紋點聚類是使用RSSI值的歐式距離來判斷的，通過比較指紋點之間RSSI值歐式距離的大小來進(jìn)行聚類。

2.1 k個聚類簇中心點的選取

k-means聚類中，k為聚類中心的個數(shù)，k值的選取要根據(jù)聚類數(shù)據(jù)的分布和區(qū)域來定，當(dāng)k值選取不合適時，聚類會產(chǎn)生一定誤差。選取k個聚類中心最常用的方法是選取k個距離盡量遠(yuǎn)的中心點，先隨機(jī)選取一個聚類中心點，然后在指紋庫中選擇和這個中心點相距最遠(yuǎn)的點作為第二個中心點，同樣地選取到第k個中心點。

2.2 聚類過程

假設(shè)有m個指紋點，n個AP和k個聚類中心點，建立的指紋庫如下：

因為同一個AP發(fā)射的信號可能在距離很遠(yuǎn)的兩個指紋點接收到的RSSI值相似，所以在聚類的過程中引入物理坐標(biāo)加以輔助，避免距離較遠(yuǎn)的指紋點被分類到一起。

對于每一個指紋點進(jìn)行以上遍歷，直到把所有指紋點分類完成。分類完成后有k個類簇，假設(shè)第l(l≤k)個類簇中指紋點的個數(shù)為nl，則可計算新的k個聚類中心，第l個類簇的聚類中心RSSI值為：

式中：RSSIlp----第l個類簇中第p個指紋點的RSSI值，此值相當(dāng)于指紋庫中的一行RSSI值，仍然是一個點的指紋序列。

得到新的聚類中心后，再對每個指紋點做以上遍歷，當(dāng)中心點和上一次聚類中心相同，聚類趨于穩(wěn)定，確定最終的聚類中心。

3 加權(quán)k近鄰定位

以上濾波和聚類過程是位置指紋定位的離線階段，在定位的在線階段，KNN算法是被廣泛使用的較為經(jīng)典的算法之一。使用KNN算法來進(jìn)行定位的思想是：在指紋點中選出和定位點RSSI距離最近的k個指紋點，將這k個指紋點的物理坐標(biāo)取平均得到定位點坐標(biāo)。文中引入加權(quán)思想，將定位點坐標(biāo)進(jìn)行加權(quán)處理，使定位結(jié)果更為精確。將指紋庫中的RSSI值單獨提取出來為：

在得到的所有di中，選取k個最小值，k個最小值對應(yīng)的指紋點的坐標(biāo)用于確定定位點坐標(biāo)。將1/di作為權(quán)值，以確定每個指紋點對定位點定位過程的貢獻(xiàn)程度，即與定位點RSSI值越接近的指紋點，其權(quán)值越大，參與定位的貢獻(xiàn)度越大，這樣處理更有利于提高定位精度。定位點的估算位置(x,y)如下：

式中：(xi,yi)----用于判斷定位點的第i個指紋點的物理坐標(biāo)。

4 實驗與分析

4.1 實驗環(huán)境

以長春工業(yè)大學(xué)南湖校區(qū)科研樓一樓大廳和部分教室為實驗場地進(jìn)行定位實驗，實驗區(qū)域平面圖如圖4所示。

在該區(qū)域內(nèi)取14×12 m的范圍進(jìn)行指紋庫的構(gòu)建和定位實驗。以橫向為x軸，縱向為y軸，在橫縱坐標(biāo)每隔2 m設(shè)置一個指紋點，共56個指紋點。因為接收設(shè)備接收信號強(qiáng)度跟設(shè)備的朝向有關(guān)，所以在每個指紋點持智能手機(jī)按同一朝向進(jìn)行RSSI采集，每個指紋點采集100次數(shù)據(jù)，每隔1 s刷新一次數(shù)據(jù)。為了提高定位準(zhǔn)確性，對30個定位點進(jìn)行定位測試。

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

4.2 實驗分析

因為k-means聚類算法和KNN算法在不同實驗數(shù)據(jù)和不同實驗環(huán)境下需要做適當(dāng)調(diào)整，所以,文中先直接對采集的原始數(shù)據(jù)使用這兩種算法進(jìn)行仿真實驗，得到兩種算法k取值不同時的平均定位誤差見表1。

表1 k-means-KNN平均定位誤差表

如表1所示，在KNN算法k值取4，k-means算法k值取3時，平均定位誤差較小，在后續(xù)的實驗中將以相同的k值進(jìn)行定位實驗。實驗主要驗證3種算法之間的誤差和區(qū)別，分析文中算法的優(yōu)勢。第一種是直接采用KNN算法對原始指紋庫進(jìn)行定位；第二種是采用混合濾波算法后再進(jìn)行KNN算法定位，為了實驗圖表中便于表達(dá)，簡稱HF-KNN(Hybrid Filter WKNN)算法；第三種是利用混合濾波算法后，經(jīng)過k-means聚類再進(jìn)行WKNN定位，簡稱HFK-WKNN算法。

利用三種方法對30個定位點采集的數(shù)據(jù)進(jìn)行仿真定位，定位誤差如圖5所示。

圖5 定位誤差圖

從圖5中可以看出，直接利用原始數(shù)據(jù)進(jìn)行KNN定位時，定位誤差的波動范圍較大，穩(wěn)定性較差，在第3、9、24號測試點處的誤差值超過了5 m，定位效果不太理想，多數(shù)測試點誤差在1～3 m；使用HF-KNN算法對測試點進(jìn)行定位，即對原始數(shù)據(jù)先做混合濾波，定位的誤差較KNN算法而言有一定幅度減小，在KNN算法波動較大的幾個測試點處，定位誤差明顯減小。這是因為混合濾波算法剔除了指紋點中的邊界值，并更正了噪聲點的數(shù)據(jù)，使得在這些定位點處的誤差得到一定程度的減小。但是大多數(shù)定位點誤差仍然在1～3 m，總體定位效果的提高不夠明顯；使用HFK-WKNN算法對測試點進(jìn)行定位時，整體的定位誤差明顯降低，多數(shù)定位點誤差在2 m以內(nèi)，因為HFK-WKNN算法在定位時引用了權(quán)值，將貢獻(xiàn)度較高的指紋點坐標(biāo)取更大的比重，使定位結(jié)果更加穩(wěn)定精確。在某些測試點處定位誤差要稍大于前面兩種算法，但是該算法的總體定位穩(wěn)定度明顯大于前面兩種算法。為了表示算法的整體定位效果，三種算法的定位平均誤差和方差如圖6所示。

圖6 平均誤差和方差圖

從圖6中分析得到，HFK-WKNN算法的平均定位誤差較KNN和HF-KNN算法分別下降了28.9%和16.4%，定位精度有較明顯的提高。并且HFK-WKNN算法的方差也是最小，定位的穩(wěn)定程度也得到驗證。在三種算法的定位數(shù)據(jù)中，用平均定位誤差不能完全說明每種算法的優(yōu)劣，因此對實驗數(shù)據(jù)進(jìn)行累計分析，以百分比的形式分析定位的穩(wěn)定性。

累計誤差概率見表2。

表2 累計誤差概率表 %

累計誤差表對應(yīng)的累計誤差概率分布如圖7所示。

圖7 定位累計誤差概率分布

累計誤差概率分布圖能更直觀地表現(xiàn)定位算法的穩(wěn)定性和可靠性。HFK-WKNN算法的收斂速度明顯快于其他兩種算法，定位誤差在2 m以內(nèi)的定位點占63.3%，在3 m以內(nèi)高達(dá)90%。KNN和HF-KNN算法誤差在3 m以內(nèi)的定位點占66.7%和76.7%，證明新算法在定位精度上較這兩種算法也得到了提高，驗證了該算法的可行性。

5 結(jié) 語

結(jié)合混合濾波算法、k-means聚類以及WKNN算法提出的HFK-WKNN算法在室內(nèi)環(huán)境的數(shù)據(jù)中進(jìn)行定位，定位效果明顯優(yōu)于其它兩種算法，該算法的優(yōu)點主要在于過濾了RSSI邊界值，平滑了指紋庫內(nèi)部的噪聲點，使粗糙的原始數(shù)據(jù)變得更為精確，對指紋庫進(jìn)行離線處理，減小了在線定位階段的工作量。在定位時引入權(quán)值，得到的結(jié)果更加穩(wěn)定，通過實驗直觀地表現(xiàn)了算法定位精度和穩(wěn)定度的提高，驗證了算法的可靠性。

[1] Bellavista P, Küpper A, Helal S. Location-based services: back to the future [J]. IEEE Pervasive Computing,2008,7(2):85-89.

[2] 王青.WiFi室內(nèi)定位系統(tǒng)的設(shè)計與實現(xiàn)[D].北京:北京交通大學(xué),2014.

[3] 徐偉.基于Android手機(jī)的室內(nèi)定位技術(shù)研究與實現(xiàn)[D].武漢：華中師范大學(xué),2014.

[4] 陳斌濤，劉任任，陳益強(qiáng)，等.動態(tài)環(huán)境中的WiFi指紋自適應(yīng)室內(nèi)定位方法[J].傳感技術(shù)學(xué)報,2015(5):729-738.

[5] Zhang Minghua. A new positioning method for location-based services in wireless LANs [J]. Journal Electronics,2008(1):75-79.

[6] 劉志鵬,袁敏.一種基于WiFi的改進(jìn)型室內(nèi)位置指紋定位方法[J].計算機(jī)與現(xiàn)代化,2016(4):36-39.

[7] Altintas B, Serif T. Indoor location detection with a RSS-based short term memory technique (KNN-STM)[C]//International Conference on Pervasive Computing and Communications Workshops. [S.l.]: IEEE,2012:794-798.

[8] 唐洋,白勇,馬躍,等.基于WiFi的指紋匹配算法在室內(nèi)定位中的應(yīng)用研究[J].計算機(jī)科學(xué),2016,43(5):73-75.

[9] 孫苑瑩.無線網(wǎng)絡(luò)的移動節(jié)點定位方法研究[J].長春工業(yè)大學(xué)學(xué)報,2015,36(1):57-60.

Indoorlocationalgorithmbasedonboundaryfilterandneighborhoodmeanfilter

GUO Xingang, LI Hang*, GONG Hong

(School of Computer Science and Engineering, Changchun University of Technology, Changchun 130012， China)

To build a fingerprint database, the edge fingerprint points are removed with filter at sampling stage and the noise spots are removed with neighborhood mean filter algorithm. The dataset is classified intokfingerprint types withk-means clustering algorithm to represent the similar fingerprint points, and then precisely localized the points. Experiments indicate that the mean positioning accuracy of the algorithm increase 28.9%, being compared with the traditional location algorithm without RSSI signal processing.

fingerprint location; neighborhood mean filter;k-means cluster; weightedknearest neighbor.

Signal Strength Indication, RSSI)是至關(guān)重要的，這直接影響到定位階段的定位精度和穩(wěn)定性。基于WIFI的位置指紋定位方法分為離線采集階段和在線定位階段。在離線采集階段主要任務(wù)是確定指紋庫中指紋點的范圍、分布形式以及采集各指紋點處接收到的AP節(jié)點發(fā)射的無線信號強(qiáng)度值，在線定位階段主要是運(yùn)用定位算法對采集數(shù)據(jù)進(jìn)行分析并實現(xiàn)定位。如果對離線階段的數(shù)據(jù)不進(jìn)行濾波處理，指紋庫中就會存在邊界指紋點以及與周圍指紋點相差較大的奇異值點。因此，文中使用改進(jìn)的濾波算法----邊界過濾和鄰域均值混合濾波算法來對采集信號進(jìn)行濾波處理，保證定位數(shù)據(jù)的準(zhǔn)確性，以提高定位精度。

2017-08-20

吉林省科技攻關(guān)計劃基金資助項目(20150204020SF)

郭昕剛(1979-)，男，漢族，吉林長春人，長春工業(yè)大學(xué)副教授,碩士，主要從事汽車電子、醫(yī)療電子方向研究,E-mail:6889068@qq.com.*通訊作者：李 航(1992-)，男，漢族，江蘇淮安人，長春工業(yè)大學(xué)碩士研究生，主要從事室內(nèi)定位和汽車電子方向研究,E-mail:956445025@qq.com.

10.15923/j.cnki.cn22-1382/t.2017.5.03

TP 393

A

1674-1374(2017)05-0426-07