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

蔣盼盼，林 瓊，謝林蓉

（1.南華大學(xué)，湖南 衡陽 421001；2.中國(guó)地質(zhì)大學(xué)，湖北 武漢 430074）

0 引言

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

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

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

1 相關(guān)算法介紹

1.1 WKNN 算法

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

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

1.2 卡爾曼濾波算法

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

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

卡爾曼濾波具體的計(jì)算公式[15]如下，預(yù)測(cè)估計(jì)階段：

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

校正更新階段：

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

2 WKNN-KF 算法原理

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

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

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

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

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

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

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

因?yàn)閃KNN 算法定位后的值僅含Px、Py所以觀測(cè)矩陣為：

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

3 算法性能仿真分析

3.1 仿真場(chǎng)景

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

圖2 AP 點(diǎn)位置分布

3.2 K 值選取

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

圖3 不同K 值的平均定位誤差測(cè)試

3.3 仿真結(jié)果分析

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

圖4 WKNN 算法和WKNN-KF 算法定位效果對(duì)比

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

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

通過計(jì)算平均定位誤差發(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 結(jié)語

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

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