基于歸一化RSS和約束WKNN的WiFi指紋定位算法*

馮 濤， 阮 超， 郭凱旋， 盧彥霖， 余 敏

(1.江西師范大學 計算機信息工程學院，江西 南昌 330022； 2.江西師范大學 軟件學院，江西 南昌 330022)

0 引 言

利用WiFi進行室內定位為一項低成本、易實現(xiàn)的技術[1,2]。文獻[3]將現(xiàn)有的室內定位方法分成3類：基于特定設備的定位方法、基于WiFi的定位方法和基于移動傳感器的定位方法；文獻[4]提出了改進的加權K最近鄰(weighted K-nearest neighbor,WKNN)匹配算法進行定位，定位精度和穩(wěn)定性方面較傳統(tǒng)WiFi指紋定位算法有大幅提高；文獻[5]提出了表征點位幾何特性的點散發(fā)性強度(geometric strength of sporadic,GSS)概念，利用最鄰近樣本點的GSS判別移動終端所在控制網(wǎng)結構，動態(tài)地選擇K最近鄰(K-nearest neighbor,KNN)算法中的關鍵參數(shù)K，約束KNN能夠有效地提高室內定位精度；文獻[6]提出了自適應匹配預處理WKNN算法，可獲得30 %以上的定位誤差改善；文獻[7]提出了利用眾包來更新位置指紋庫，針對用戶的錯誤修正提出了基于密度的(density-based spatial clustering of applications with noise,DBSCAN)聚類的錯誤檢測方法，該方法可以長時間保持較高的定位性能；文獻[8]在高斯模型的基礎上提出了一種改進高斯模型的濾波算法，再結合交點質心法得出一種新的距離估計方法，該方法能夠準確定位并具有較高的定位精度和穩(wěn)定性。

本文提出了基于歸一化和的平方根(root-sum square,RSS)和約束 WKNN的WiFi指紋定位算法，運用高斯濾波歸一化了WiFi無線信號權值，降低了信號的隨機誤差；并采用基于4—域系統(tǒng)WKNN匹配定位算法，防止離待測點較遠的參考點參與匹配造成的誤差。

1 WiFi位置指紋定位算法

1.1 離線建庫階段

1)將待測試區(qū)域劃分若干網(wǎng)格，以每個網(wǎng)格的頂點作為參考點(reference point，RP)；

2)將每個RP的特征信息(包括坐標、RSS值)作為一組位置指紋存入位置指紋數(shù)據(jù)庫。位置指紋庫數(shù)據(jù)可表示為

(1)

1.2 在線定位階段

1)實時測量待測點接收WiFi信號源的RSS值；

2)利用一定的匹配算法，包括確定性匹配算法：最近鄰(nearest neighbor，NN),KNN,WKNN等，以及概率性匹配算法：樸素貝葉斯、最小均方誤差(minimum mean square error,MMSE)[9]等，以及一些其他算法。與位置指紋數(shù)據(jù)庫中的指紋數(shù)據(jù)進行匹配，估計最優(yōu)的待測點位置信息。

2 改進的WiFi指紋定位算法

算法流程如圖1所示。

圖1 本文算法流程

2.1 離線—在線信號采集誤差修正

本文提出了一種基于歸一化RSS值權值的離線—在線信號采集誤差修正算法。保留高概率的RSS值，對其概率進行歸一化處理，提高高概率的RSS值的權值，將加權后求得的加權均值[10]作為其RSS值，使得結果更接近于真實值，確保定位精度。歸一化處理過程如式(2)所示

(2)

求解更新后的RSS值

(3)

式中Ri為高概率RSS值,j為某一RP采集某一AP的RSS值。

2.2 約束WKNN的匹配定位過程

本文提出了一種確定性匹配算法WKNN,在KNN算法的基礎上引入了權重系數(shù)，以權重系數(shù)代表不同位置指紋點在定位匹配中的重要程度，同時引入鄰域的概念，用以提高定位精度。

1)待測點與參考點RP的相似度Li為

(4)

式中Rm為定位時接收到來自第m個AP的RSS值。

對Li進行升序排序，各指紋點所對應的坐標可以表述為Pi={P1,P2,…,Pk,…,Pi}，1≤k≤i。

2)鄰域確定

圖2 鄰域

3)4—域系統(tǒng)判定

4)約束WKNN的匹配定位過程

5)待測點估算結果P

(5)

提出的約束WKNN的匹配定位過程來進一步約束選擇參與最終匹配定位的參考點，有效減少了錯誤的參考點給定位帶來的不利影響，再結合WKNN進行匹配，得到待測點的估算結果，提高了定位精度。

3 實驗與結果分析

3.1 實驗條件

定位區(qū)域的平面圖如圖3所示(包括4間辦公室和2條走廊)。參考網(wǎng)格設置為2 m×2 m，無線AP型號采用TL-WR885N(按照圖3所示，布置9個無線AP)，移動采集終端為華為榮耀6，在每個采樣點采集RSS值15次。

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

3.2 實驗結果分析

1)離線—在線信號采集誤差修正效果

針對室內無線信號頻繁的跳變現(xiàn)象，本文采用高斯濾波對RSS值進行濾波處理來提高定位精度。濾波后的效果如圖4所示，其中橫坐標為距離WiFi信號源的距離，縱坐標為RSS值的絕對值。

圖4 高斯濾波效果

可以看出,歸一化RSS值權值的離線—在線信號采集誤差修正效果良好，濾波RSS值曲線逼近理想值。

2)約束WKNN算法對WKNN和KNN算法的優(yōu)化效果

實驗中，WKNN的關鍵參數(shù)K設置為3。約束WKNN算法(基于4—域系統(tǒng)的WKNN算法)、WKNN算法和KNN算法的累積誤差分布(cumulative error distribution,CED)如圖5所示?？梢钥闯?，約束WKNN算法的收斂距離為1.8 m左右，WKNN算法的收斂距離為2.4 m左右，KNN算法的收斂距離為2.8 m左右。在誤差的整體分布上，約束WKNN算法的定位誤差比WKNN算法和KNN算法低。

圖5 累積誤差分布

3)本文算法優(yōu)化效果

從平均定位誤差上來看：WKNN匹配算法為1.75 m、基于歸一化RSS的WKNN匹配算法為1.66 m、約束WKNN匹配算法為1.5 m、本文定位算法為1.41 m。本文定位算法的定位優(yōu)化效果明顯，平均定位誤差降低19.4 %。

4 結 論

提出的算法可以更好地估計用戶的實際位置，平均定位誤差降低了19.4 %，對基于WiFi的室內定位的發(fā)展起到了積極的推動作用。下一步工作將考慮采用眾包更新的方式減輕離線數(shù)據(jù)采集和更新的工作量。