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

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

0 引言

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

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

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

1 指紋庫的構(gòu)建與擴充

1.1 稀疏采樣構(gòu)建指紋庫

指紋庫的指紋質(zhì)量影響在線匹配階段的定位效率和精度，構(gòu)建穩(wěn)定可靠的指紋庫是指紋定位關(guān)鍵[18-19].

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

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

圖1 RSS觀測值波動情況

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

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

1.2 Kriging 插值擴充指紋庫

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

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

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

1.3 位置指紋的定位流程

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

圖2 位置指紋定位流程

2 RSS指紋數(shù)據(jù)擬合與修正方法

2.1 基于高斯濾波的數(shù)據(jù)擬合

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

圖3 高斯擬合RSS信號

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

2.2 基于卡爾曼濾波的數(shù)據(jù)修正

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

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

3 基于FDE-IRF的定位算法設(shè)計

3.1 RF定位算法

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

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

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

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

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

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

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

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

圖4 RF算法流程

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

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

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

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

3.2 IRF 定位算法

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

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

IRF算法步驟如下：

Step1：同RF算法Step1～Step3.

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

3.3 FDE-IRF定位算法

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

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

圖5 FDE-IRF定位算法流程

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

離線階段：

Step1：部署6 個AP下的2.4 m 和1.2 m 網(wǎng)格的實驗環(huán)境.

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

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

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

在線階段：

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

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

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

4 實驗過程及分析

4.1 數(shù)據(jù)采集

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

圖6 實驗環(huán)境

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

4.2 數(shù)據(jù)預(yù)處理

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

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

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

通過表2結(jié)合圖7可知，Kriging 插值法充分考慮空間信號的相關(guān)性，在最大誤差、最小誤差和平均誤差評價標(biāo)準(zhǔn)上均優(yōu)于反距離插值法，插值結(jié)果更準(zhǔn)確.

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

圖8 濾波對比示意圖

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

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

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

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

4.3 結(jié)果分析

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

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

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

為進一步分析指紋庫自動擴充的有效性，本文在4.1節(jié)實驗環(huán)境中，比較了基于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，基本滿足在線室內(nèi)指紋定位的誤差要求.FDE方法在滿足定位誤差可接受的同時，節(jié)省構(gòu)建指紋庫的成本.由圖6實驗環(huán)境的布設(shè)RP點數(shù)可知，指紋庫自動擴充方法采集的RP個數(shù)比全采樣減少60.4%，采集時間相應(yīng)地減少相同的比例.

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

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

圖11 累積分布概率對比

圖12 數(shù)據(jù)離散情況對比

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

5 結(jié)束語

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