一種改進的Wi-Fi 位置指紋室內(nèi)定位算法*

蔣盼盼，林 瓊，謝林蓉

（1.南華大學，湖南 衡陽 421001；2.中國地質大學，湖北 武漢 430074）

0 引言

室內(nèi)定位技術能為室內(nèi)導航、人員物資精準定位管理、消防緊急救援、建筑智能化管理等多種服務提供數(shù)據(jù)支持。根據(jù)有關機構調(diào)研顯示，自2020年起，近5 年來全球室內(nèi)定位市場規(guī)模將以22.5%的復合年增長率保持增長[1]，室內(nèi)定位技術成為近些年研究的最熱門技術之一。

基于Wi-Fi 的位置指紋定位算法是目前比較常用的定位技術之一，它主要通過接收信號強度指示值（Received Signal Strength Indication，RSSI）與物理位置的對應關系進行定位[2]。該算法主要包括離線指紋庫建立和在線匹配定位兩個階段。離線指紋庫建立階段中，首先，在待定位空間里放置N個無線訪問接入點（Access Point，AP）和多個位置已知的采樣點；其次，依次記錄在各采樣點處接收到的不同AP 點的Wi-Fi 信號RSSI 值；最后，將該值連同采樣點的位置信息一并儲存到數(shù)據(jù)庫中，便完成Wi-Fi 離線位置指紋庫的建立。在線匹配定位階段先通過移動設備獲取待定位點收到的多個AP 點的RSSI 值，與上述離線指紋庫中指紋點的RSSI 值進行匹配，通過算法匹配到與待定位點最為接近的指紋點，提取出位置信息即為待定位點的坐標[3-5]。

目前，常用的位置指紋匹配算法有最鄰近法（Nearest Neighborhood，NN)、K 最近鄰法（K-Nearest Neighborhood，KNN）和加權K 近鄰算法（Weighted K-Near Neighborhood，WKNN）[6]。NN 算 法[7]、KNN 算法[8]、WKNN 算法[9]每次定位計算都是相互獨立的離散的過程，并沒有考慮物體的運動連續(xù)性，比較適合對于靜止不動的對象進行定位，但如果是對移動對象進行定位的話，容易導致定位目標漂移、運動軌跡定位不準的情況[10]。基于此，本文提出一種卡爾曼濾波和加權K 近鄰算法融合的改進定位算法。該算法充分考慮待定位對象運動的連續(xù)性，在加權K 近鄰定位算法的基礎上引入卡爾曼濾波，通過卡爾曼濾波對定位結果進行修正，濾除掉環(huán)境干擾因素和偏離運行軌跡較遠的點，實現(xiàn)對待定位目標運動路徑的平滑處理，提高定位精度和準確度。

1 相關算法介紹

1.1 WKNN 算法

WKNN 算法是將實時采集的AP 點的RSSI 值與指紋庫中各指紋點的RSSI 值進行比較，計算兩者的歐氏距離進行排序，找出歐式距離最小的前K個指紋點，求K個指紋點坐標的加權平均值[11]。考慮各坐標對待定位點的影響程度相同，分配K個指紋的權值，權值取自于歸一化之后的歐氏距離倒數(shù)，指紋點距待定位點RSSI 的歐氏距離越小，則權值越大。待定位點的最終坐標為：

式中：k為選取的歐氏距離最近的指紋點的個數(shù)；disj為待定位點RSSI 與指紋點RSSI 的歐氏距離；ε為一個不為零的很小的實數(shù)，為了避免disj在趨于0 時，權重系數(shù)出現(xiàn)奇異值的情況。

1.2 卡爾曼濾波算法

卡爾曼濾波（Kalman Filter，KF）適用于估計一個動態(tài)系統(tǒng)的最優(yōu)狀態(tài)，它能濾除狀態(tài)觀測值的噪聲，從而對狀態(tài)真實值進行最優(yōu)估計[12]。KF 最初是1960 年匈牙利數(shù)學家Rudolf Emil Kalman[13]提出來的，目前廣泛應用于定位、物體跟蹤和導航等各種領域。

KF 算法實質上是通過預估值和觀測值對真實值進行估計的過程。它有預測估計和校正更新兩個階段。在預測估計階段，它是將k-1 時刻的最優(yōu)估計值進行狀態(tài)變換后再加入控制量和噪聲構成當前k時刻的先驗估計值；而校正更新階段則是將當前k時刻的觀測值和先驗估計值進行加權平均，以此來計算當前時刻的最優(yōu)估計值，其中的權值就稱為卡爾曼增益[14]。預測估計和校正更新兩個過程將隨時間的推移進行迭代，直到滿足遞歸結束的條件為止。

卡爾曼濾波具體的計算公式[15]如下，預測估計階段：

式中：zk為系統(tǒng)k時刻的觀測值；H為觀測矩陣；vk為k時刻的觀測噪聲，服從高斯分布的隨機變量，其均值為0；協(xié)方差為Rk。

校正更新階段：

式中：Kk為k時刻的卡爾曼增益，如果觀測值的誤差遠遠大于先驗估計值的誤差，那么Kk就要調(diào)小，反之Kk要調(diào)大，調(diào)節(jié)Kk實際上是通過調(diào)節(jié)Qk和Rk來實現(xiàn)的；x^k為k時刻最優(yōu)估計值，其協(xié)方差 為P^k。

2 WKNN-KF 算法原理

WKNN-KF 算法主要是在線匹配階段通過卡爾曼濾波算法對WKNN 定位后的軌跡進行修正，濾除掉漂移點，并充分考慮移動目標的運動特性，利用卡爾曼濾波算法結合預估值和觀測值進而對真實值進行估計。其中預估值是上一時刻對當前值的預測，觀測值是使用WKNN算法后當前時刻的定位值，最后將觀測值和預估值進行加權求和，得到最優(yōu)的估計坐標值。該算法主要應用于對移動對象的定位中，具體的流程如圖1 所示。

圖1 基于卡爾曼濾波的WKNN 定位算法流程

現(xiàn)假定待定位目標運動是大致勻速的，上一時刻的位置加上速度與時間差的乘積等于當前時刻的預測值。則狀態(tài)矩陣x可以表示為：

式中：Px、Py為待定位點的x軸坐標與y軸坐標，初始值為WKNN 算法的第一個預測值；vx,vy為待定位點x、y軸方向上的分速度，設初始值為0。在此系統(tǒng)中，時間差取1，狀態(tài)變換矩陣可表示為：

在該系統(tǒng)中，外部控制輸入為零，則預測估計方程為：

式（12）中q的值決定于對預測估計值的信任度，若對預測估計值得信任度不高，可以將q值調(diào)大，反之，可以將q值調(diào)小，在該系統(tǒng)中，q值為0.001。

由此，預測估計過程狀態(tài)的協(xié)方差方程為：

因為WKNN 算法定位后的值僅含Px、Py所以觀測矩陣為：

式中：r的大小決定于對觀測值的信任程度，若觀測值比較精確，r值調(diào)小，反之，r的值調(diào)大，在該系統(tǒng)中，r的值取2。結合式（10）、式（11）、式（12）、式（13）、式（14）、式（15），隨之不斷地進行迭代，最終得到優(yōu)化后的定位軌跡。

3 算法性能仿真分析

3.1 仿真場景

算法采用MATLAB 進行仿真實現(xiàn)，軟件模擬1個20×15×4 m3的房間作為定位區(qū)域，設有10 個AP。為了減小各個AP 之間的干擾作用，AP 點的位置需盡量分散且均勻，現(xiàn)將AP 設備分布于室內(nèi)的4 個角以及倉庫長邊的中點處，并且布置在離地面1 m 高處，具體位置如圖2 所示。

圖2 AP 點位置分布

3.2 K 值選取

WKNN 算法的K 值對定位精度有直接影響，需要對不同K值進行定位精度的測試以得到K的最優(yōu)值。通過進行多次測試最終得到WKNN 算法的定位平均誤差與K值的關系圖，如圖3 所示，可以發(fā)現(xiàn)K等于8 和9 時，算法的定位平均誤差最小。本文選擇K=8 來進行后續(xù)的仿真分析。

圖3 不同K 值的平均定位誤差測試

3.3 仿真結果分析

經(jīng)過仿真發(fā)現(xiàn)，如圖4 所示，跟實際路徑相比，WKNN 算法定位后的路徑比較分散，點與點之間呈跳躍式分布，整體上看路徑走向不明確，軌跡不清晰；而WKNN-KF 算法定位后的路徑走向清晰，相鄰定位點之間并沒有很明顯的漂移位。這是因為卡爾曼濾波算法考慮到了物體運動的連續(xù)性，所以最終定位路徑的曲線平滑。另外，由于WKNN-KF 算法利用預測值和觀測值來同時對待定位點進行位置估計和修正，在一定程度上對環(huán)境干擾因素進行了濾除，使得最終定位路徑與實際路徑也更為相近，定位結果精度更高。

圖4 WKNN 算法和WKNN-KF 算法定位效果對比

如圖5 所示，進一步對比分析NN、KNN、WKNN 和WKNN-KF 4 種算法的誤差累積分布函數(shù)，可以看到WKNN-KF 算法可以在65%的概率下定位精度達到2 m 以內(nèi)。從整體上說，NN 算法的誤差累積分布函數(shù)最為平緩，在90%的定位準確度下，定位精度可以控制在7.5 m 以內(nèi)；KNN 算法和WKNN 算法精度相差不大，在90%的定位準確度下，兩種算法的定位精度控制在6 m 以內(nèi)；WKNN-KF算法的函數(shù)圖形收斂速度最快，在90%的定位準確度下，定位誤差控制在3.4 m 以內(nèi)。因此，從誤差累積分布函數(shù)明顯可以看出WKNN-KF 算法的定位響應速度最快，定位精度最高。

圖5 NN、KNN、WKNN 和WKNN-KF 算法的誤差累積函數(shù)分布

通過計算平均定位誤差發(fā)現(xiàn)，NN 算法平均定位誤差最大為4.049 m，KNN 算法和WKNN 算法的定位平均誤差分別為3.489 m 和3.481 m，WKNNKF 算法平均定位誤差最小為1.891 m。WKNN-KF算法相較于NN 算法、KNN 算法和WKNN 算法的定位性能分別提升了52.3%、45.9%以及45.7%。

4 結語

針對WKNN 算法未考慮物體運動連續(xù)性的問題，本文提出了WKNN-KF 算法。該算法先利用WKNN 算法計算待定位目標的坐標，然后將其作為卡爾曼濾波算法的觀測值，再結合前一時刻的估計值，將兩者進行加權求和，得到最終的定位坐標值。經(jīng)仿真實驗發(fā)現(xiàn)，改進的算法定位軌跡平滑，點與點之間無明顯跳變，與WKNN 算法對比，該算法定位精度提高了45.7%。

該算法還有很多可以改進的地方，如可結合環(huán)境因素和定位路徑，將固定K值改成動態(tài)K值。此外，本文定位時沒有考慮同一個位置不同方向的RSSI 值的波動情況，后續(xù)在建立離線指紋庫時，除了保存采集到的RSSI 值，還需加入對應的數(shù)據(jù)采集方向，豐富離線指紋庫的數(shù)據(jù)內(nèi)容，進一步提高算法的精確度。