基于FDE-IRF的室內指紋定位方法

張雯濤，吳飛，朱海，通雁輝，陸雯霞

( 上海工程技術大學電子電氣工程學院，上海 201620 )

0 引言

室內定位解決的是全球衛星導航系統(GNSS)信號弱、缺失的定位問題.在一些公共區域，如大型商場、地鐵站、地下停車場和大型醫院等，需要精確度高的位置定位服務[1]，因此，提高室內定位精度的需求變得日益迫切.許多室內定位技術已經成為研究熱點，主要包括超寬帶(UWB)、藍牙、射頻(RF)、Wi-Fi、地磁和行人航跡推算[2].隨著無線局域網(WLAN)在大范圍內大量覆蓋，基于Wi-Fi 的定位方法因其具有無需額外部署硬件設備且成本低的優勢得到廣泛應用[3-4].

基于接收信號強度(RSS)的室內定位技術[5]是目前最常用的方法，主要分為兩種：基于距離衰減模型的三邊法和基于指紋圖譜的指紋法[6].基于指紋圖譜的定位方法不需要知道無線訪問接入點(AP)位置和信號衰減模型，是常用的RSS位置匹配方法[7].指紋識別方法通常包括兩個階段：離線訓練和在線匹配.在離線訓練階段，構建可靠穩定的指紋庫通常需要在同一參考點(RP)不同時刻反復采集指紋樣本.隨著待定位區間增大，采樣過程耗費大量的時間和人力[8-9].為減少指紋庫構建時間，提高稀疏指紋庫定位精度，文獻[10]和文獻[11]采用Kriging 插值方法，減少指紋數據的采集，但未有效處理干擾信號，導致采集的RP缺乏代表性.由于室內信號多徑傳播和非視距的影響，RSS在一段時間內產生波動.文獻[12]將離線指紋庫存儲多時間段的指紋數據與平均值并用，考慮AP信號的波動性，結合K近鄰算法(KNN)獲得更準確的位置估計，但K值固定容易出現誤匹配.空間中大部分干擾信號被認為是高斯噪聲，均值濾波不能有效處理干擾信號，高斯濾波和卡爾曼濾波算法[13-14]被認為能更好地處理含高斯噪聲的信號.傳統隨機森林(RF)模型對具有不同泛化能力的決策樹擁有相同的投票權重，影響模型的整體穩定性.文獻[15]采用RF算法實現系統的識別功能，但精度較低.為提高RF算法的識別精度，文獻[16]對傳統RF模型中的決策樹根據ROC曲線下方的面積大小(AUC)值計算相似度矩陣，選出AUC最大的決策樹組成新的RF模型.文獻[17]利用Kappa 系數評價RF決策樹分類能力，通過決策樹加權策略改進模型，解決數據不平衡帶來的少數樣本識別率低的問題.此類策略和模型是基于分類任務做的改進，無法直接用于室內定位中的位置識別回歸任務.

基于文獻[16]和文獻[17]優化分類決策樹權重的思想，利用袋外數據(OOB)評價決策樹回歸能力，并為其分配權重，將稀疏采樣方法和Kriging 插值方法組合，提出了一種基于指紋庫擴充的改進隨機森林(FDE-IRF)方法.本文稀疏采樣定位范圍內的RP，對離線階段的采樣數據進行高斯濾波濾除部分噪聲，采用高斯變異函數擬合的Kriging 插值算法自動生成缺失RP的指紋.在在線階段，對采樣數據進行卡爾曼濾波，利用OOB數據計算每棵決策樹的定位誤差，為預測能力強的決策樹分配更高的權重.在實驗階段，進行稀疏采樣、擴充指紋庫和全采樣三種環境下的算法對比實驗，證明本文算法的準確性和有效性.

1 指紋庫的構建與擴充

1.1 稀疏采樣構建指紋庫

指紋庫的指紋質量影響在線匹配階段的定位效率和精度，構建穩定可靠的指紋庫是指紋定位關鍵[18-19].

傳統指紋庫的構建方法是在RP 建立一條指紋信息，極大地節省在線匹配的時間，但只存儲一條指紋信息不能充分體現RP的信號波動.由于信號受多徑干擾及其他無線電信號的影響，使在線匹配不同時間段的匹配誤差增大.

為建立可靠穩定的指紋庫，便攜式電腦在不同RP對同一AP的Wi-Fi列表進行掃描，觀察信號強度的波動，RSS值的變化趨勢如圖1所示.

圖1 RSS觀測值波動情況

由圖1可知，Wi-Fi 信號的RSS 值隨采樣時間變化不停波動，為選擇更有代表性的RP指紋信息，本文采用每個RP 多條指紋的指紋庫方法，使RP處的指紋更能表示該點的信號波動.假設在區域中有n個AP和s個RP，對RSS信號進行高斯濾波后構建初始階段指紋庫，如表1所示.

圖1測得的RSS隨時間變化波動比較大，因此，在每個RP存m條指紋數據，使指紋數據更具體真實，充分體現信號的空間特性.

1.2 Kriging 插值擴充指紋庫

稀疏采樣構建指紋庫解決了建庫工作量大的問題，但稀疏采樣使得網格劃分變大，定位精度降低.基于文獻[10]和文獻[11]的分析，采用Kriging 插值法.Kriging 插值是一種地學統計格網化方法，其試圖挖掘隱含在數據中的趨勢，對插值點進行無偏估計，同時滿足無偏估計條件，插值公式如式(1)所示：

通過變異函數來考量采樣點與插值點的空間關系.根據樣本數據計算的半方差，選用高斯變異函數擬合模型，如式(4)所示：

式中，半方差γ(·)由式(3)求得，權重系數λi通過求解方程組式(9)求得，代入式(1)即求得待估計點的屬性Z?(X) ，即AP在待估計點的RSS值.

1.3 位置指紋的定位流程

圖2是FDE-IRF室內指紋定位流程，首先稀疏采樣多時間段的指紋數據進行高斯濾波預處理完成指紋庫構建，然后考慮到Wi-Fi 信號相關性引入Kriging 插值方法完成指紋庫擴充，最后在在線匹配時，應用FDE-IRF匹配準則，完成二維位置坐標解算，定位流程如圖2所示.

圖2 位置指紋定位流程

2 RSS指紋數據擬合與修正方法

2.1 基于高斯濾波的數據擬合

圖3是一段時間內RSS觀測值的頻率分布直方圖，呈現高斯分布.為使指紋庫更可靠準確，本文對采集的RSS信號進行高斯擬合.

圖3 高斯擬合RSS信號

如圖3所示，采集到的信號總體滿足高斯分布.本文考慮Wi-Fi 信號的分布特性，對離線采集到的數據進行高斯濾波，將RSS范圍在[μ?σ,μ+σ]的值保留.文中方法有效過濾跳變大且異常的數據，一定程度上解決了RSS數據穩定性差的問題.本文在構建指紋庫時使用高斯濾波，在采集完所有數據后對總體數據進行濾波.

2.2 基于卡爾曼濾波的數據修正

卡爾曼濾波的誤差獨立存在，濾波自身誤差不受測量數據的影響.卡爾曼濾波以最小均方誤差為估計，利用觀測值對預測值進行修正以獲得最佳估計值，通過遞推得到優化后的結果.具體操作是將上一時刻的最優估計RSS值作為這一時刻的預測值，再用這一時刻的RSS觀測值修正預測值.本文應用卡爾曼濾波完成在線階段RSS數據的修正.卡爾曼濾波過程分為兩個階段：預測階段和測量更新階段.

預測階段公式如式(14)和式(15)所示：

3 基于FDE-IRF的定位算法設計

3.1 RF定位算法

RF是由大量的決策樹構成的，決策樹的生成就是遞歸地構建二叉樹的過程.對回歸樹用平方誤差最小化準則，進行特征選擇，生成二叉樹.

假設X、Y分別為輸入和輸出變量，并且Y是連續變量，給定訓練數據集如式(19)所示：

將輸入空間劃分為M個單元R1,R2,···,RM，并且在每個單元Rm上有一個固定的輸出值cm.

回歸樹模型可表示為式(20)：

用平方誤差來表示回歸樹的預測誤差，用平方誤差最小準則求解每個單元上的最優輸出值.單元Rm上的cm的最優值c?m是Rm上的所有輸入實例xi對應的輸出yi的均值，如式(21)所示：

采用啟發式的方法，選擇第j個變量xj和它的取值s，作為切分變量和切分點，并定義兩個區域，如式(22)和式(23)所示：

RF是一種集成學習方法[20]，它通過訓練時構建多棵決策樹來完成分類、回歸等任務，以改進決策樹過擬合現象.RF預測結果以每棵決策樹輸出的均值為最終結果，每棵樹的建立依賴于一個獨立抽取的樣品.森林中的每棵樹具有相同的分布，預測誤差取決于每棵樹的回歸能力和相關性.

如圖4所示，RF算法的步驟如下：

圖4 RF算法流程

Step1：樣本選擇.每棵決策樹從原始訓練集N中有放回地重復隨機抽取k個樣本生成新的訓練樣本集合(k個訓練集之間相互獨立，元素可重復).

Step2：特征選擇.RF選擇一個最優的特征劃分點來劃分決策樹.

Step3：構建決策樹.在構建決策樹時，每個節點的分裂都要按照Step2進行，直到無法分裂為止.

Step4：位置預測.通過Step1～Step3的迭代，構建大量決策樹構成森林.將測試樣本作為輸入，RF模型對測試樣本進行回歸運算，得到最終的位置坐標.

3.2 IRF 定位算法

在N個樣本的原始訓練集的隨機采樣中，被抽取的數據成為訓練集，而k次采樣都沒有被采集到的數據成為OOB數據.利用OOB數據估計決策樹的預測能力從而評價RF的性能.OOB數據未被抽樣的概率，表示為

RF算法在構建過程中，以每棵決策樹輸出的均值為最終結果，但實際每棵決策樹的回歸能力不同.在構建RF模型過程中，決策樹的OOB估計與決策樹的構建串行完成，即在完成構建RF模型的同時，所有決策樹獲得一個相應的OOB估計數值.本文在此基礎上優化決策樹的投票策略進而優化RF模型.

IRF算法步驟如下：

Step1：同RF算法Step1～Step3.

Step2：決策樹權重分配.計算決策樹的預測位置與真實位置的歐式距離，將距離平方的倒數作為權重，再將權重歸一化作為決策樹的權重系數，依次為決策樹分配相應的權重wi，如式(30)～(32)所示：

3.3 FDE-IRF定位算法

在室內指紋匹配方法中，全采樣構建指紋庫費時費力，而傳統RF算法由于其固有的決策樹平均投票機制使得算法在位置匹配時準確率低，基于此，本文提出一種基于FDE-IRF的室內指紋定位算法.

FDE-IRF室內指紋定位方法的整體算法流程，如圖5所示.算法基于2.1節的理論推理，利用高斯濾波剔除異常值，根據1.1節的分析，考慮RSS波動性存儲多時間段指紋數據完成指紋庫構建.文中算法通過1.2節Kriging 插值的推理，補全在離線階段稀疏采樣的未采樣點，得到擴充的指紋庫.基于此，本文根據2.2節卡爾曼濾波的理論分析對待測點RSS向量實時修正，基于3.1節RF 模型框架分析，在3.2節引入OOB數據評價手段，根據預測位置與真實位置的歐式距離，為每棵決策樹分配權重，改進決策樹平均投票策略，優化RF模型，最終解算得到位置坐標.

圖5 FDE-IRF定位算法流程

本文所提FDE-IRF室內指紋定位方法的具體實驗步驟如下.

離線階段：

Step1：部署6 個AP下的2.4 m 和1.2 m 網格的實驗環境.

Step2：在RP點多時間段采集RSS，分析信號類高斯分布特性，采用高斯濾波剔除異常值.

Step3：分析RSS波動性，存儲多時間段RSS向量，構建強代表性指紋庫.

Step4：利用Kriging 插值的空間相關性補全2.4 m稀疏采樣的未采樣點，完成1.2 m 指紋庫自動擴充.

在線階段：

Step1：在待測點采集RSS向量，采用卡爾曼濾波算法實時修正RSS.

Step2：RF模型訓練擴充指紋庫，生成100棵決策樹.

Step3：利用OOB數據的評估手段代入式(30)～(32)計算100棵決策樹的權重，將權重代入式(33)得到基于決策樹加權的IRF模型.Step4：使用FDE-IRF 算法將實時修正的RSS向量在線匹配，得到解算坐標.

4 實驗過程及分析

4.1 數據采集

為驗證文中算法的有效性，設計對比實驗以評估算法的定位誤差.圖6是設計的實驗環境，實驗時偶有人員走動.在地面標定2.4 m×2.4 m 方格，設置參考點21個，測試點12個.實驗所用AP 型號為Howay2000Q87，實驗的信號采集設備為戴爾便攜式計算機，型號為Inspiron 15-5557，電腦網卡型號為Intel(R)Dual Band Wireless-AC 3165，采集程序為Python 腳本.

圖6 實驗環境

圖6中圓形點表示原始指紋點，三角形點表示插值指紋點，星形點表示測試點.在每個原始指紋點處采集400條數據，經過高斯濾波后，選取20條質量較好的數據作為該點指紋數據，存入指紋庫.將2.4 m稀疏指紋庫每隔1.2 m 進行插值，指紋樣本約是之前的2.5倍，將插值數據存入指紋庫.

4.2 數據預處理

采用的Kriging 插值屬于一種最優內插方法，得到的插值面較為光滑，其內插值的可信度依賴于實際指紋采集點的數據密度.選用一組RSS 值進行插值操作，如圖7所示.

反距離插值法中點到估計像元的中心越近，則其在平均過程中的影響或權重越大.在相同實驗環境下，采用反距離插值法和Kriging 插值法對2.4 m 網格進行1.2 m 插值處理，對12個測試點的AP1的信號強度進行對比，實驗結果如表2所示，結果保留整數.

表2 兩種插值方法誤差對比dBm

通過表2結合圖7可知，Kriging 插值法充分考慮空間信號的相關性，在最大誤差、最小誤差和平均誤差評價標準上均優于反距離插值法，插值結果更準確.

為比較濾波算法效果，在同一參考點選取一個AP的RSS數據，對其進行卡爾曼濾波、高斯濾波、均值濾波，如圖8所示.

圖8 濾波對比示意圖

由圖8知，卡爾曼濾波、高斯濾波之后的數據波動更為平緩，濾除大部分異常跳變點，減輕由于信號異常對定位產生的影響.卡爾曼濾波是基于前一狀態對后一狀態的預測，時延較高，高斯濾波的時延較小，在不考慮在線匹配的情況下，高斯濾波的效果更好.

為對比在離線階段不同濾波方法對指紋數據匹配精度的影響，在相同實驗環境下，用RF算法進行在線匹配實驗，實驗結果如表3所示.

由表3可知，高斯濾波和均值濾波的平均誤差較小，但高斯濾波和均值濾波不適用于在線匹配，因為這兩種濾波方式要在全部數據上做濾波.若不考慮在線匹配情況，在離線情況下，即建立指紋庫時，使用高斯濾波和均值濾波.在線匹配時，選擇卡爾曼濾波進行實驗數據的處理.

表3 三種濾波方法誤差對比m

4.3 結果分析

為驗證指紋庫自動擴充的準確性和有效性，比較基于2.4 m 稀疏采樣+插值的指紋庫擴充(FDE)方法和2.4 m 稀疏采樣方法在在線匹配時的定位精度，本文按照4.1節部署的實驗環境進行實驗，RF算法選用100棵決策樹.

圖9是不同算法指紋庫自動擴充前后的平均定位誤差對比，用Kriging 插值方法補充未采樣的RP，更多的RP參與在線指紋的匹配.指紋庫擴充后的加權K近鄰(WKNN)、RF、支持向量機(SVM)、IRF算法的平均定位誤差均小于擴充前，比擴充前分別提高26.4%、19.0%、7.0%和23.2%.結果表明，指紋庫擴充方法在本文實驗環境下真實有效，定位精度更高，定位結果更加穩定.

圖9 指紋庫擴充前后算法定位精度對比

為進一步分析指紋庫自動擴充的有效性，本文在4.1節實驗環境中，比較了基于2.4 m 稀疏采樣+插值的指紋庫擴充方法和1.2 m 全采樣(AS)方法的定位誤差.如圖10所示，基于FDE方法的WKNN、RF、SVM、IRF 算法的平均定位誤差比AS方法分別提高8.6%、降低3.4%、提高0.7%和降低5.0%，平均誤差最多降低0.06 m，基本滿足在線室內指紋定位的誤差要求.FDE方法在滿足定位誤差可接受的同時，節省構建指紋庫的成本.由圖6實驗環境的布設RP點數可知，指紋庫自動擴充方法采集的RP個數比全采樣減少60.4%，采集時間相應地減少相同的比例.

圖10 指紋庫擴充與全采樣定位誤差對比

為驗證本文所提IRF算法的準確性，基于2.4 m稀疏采樣+插值的指紋環境，評估IRF算法與WKNN、RF、SVM 算法在一定誤差范圍內的定位精度，繪制不同定位方法的誤差累積分布概率和誤差離散情況，如圖11和圖12所示.

圖11 累積分布概率對比

圖12 數據離散情況對比

由圖11～12可知，在指紋庫擴充情況下，同RF、WKNN、SVM 算法相比，FDE-IRF算法在線匹配時所有的測試點定位誤差都在3 m 內，定位誤差的最大值和最小值都最小，且誤差離散程度小，定位效果最好，驗證了算法的準確性.由圖9可知，本文所提算法其誤差較FDE-WKNN、FDE-RF、FDE-SVM算法分別減少14.9%、17.6%和14.3%.使用決策樹加權的RF模型的預測精度高于傳統RF模型且比隨機森林算法穩定，說明通過評估決策樹回歸能力的大小分配權值的方法合理、可行，引入決策樹權重后，提高RF 模型的泛化能力，驗證了算法的有效性.

5 結束語

本文提出一種基于FDE-IRF的室內指紋定位方法，通過綜合利用稀疏采樣、Kriging 插值和IRF算法，有效提高位置指紋算法的定位精度.在離線階段通過采用自動擴充指紋庫的方式，保證定位精度的同時，降低指紋庫構建成本；在在線匹配階段，IRF算法，利用RF隨機抽樣的OOB數據，評價決策樹的回歸能力，并根據決策樹的回歸能力分配相應的權重，優化RF結構，有效地提高了定位精度.