基于IRF-PF算法的WLAN室內定位方法

柴海瓏,王小鵬,龍 良

(蘭州交通大學 電子與信息工程學院,蘭州 730070)

隨著無線網絡、移動計算和普適計算等技術的普及,基于位置的服務引起了人們的廣泛關注。雖然全球定位系統和北斗衛星導航系統已被廣泛應用于室外定位[1],但在室內或者高層建筑密集的地區,無線電信號易受到建筑物墻壁的阻擋而被衰減或反射,導致全球衛星導航系統在室內的定位精度大幅下降,無法滿足人們對定位服務精度的要求[2]。當前主流的室內定位技術有射頻識別[3]、ZigBee[4]、超聲波、超寬帶[5]和無線局域網(wireless local area networks,WLAN)[6]等技術。隨著WLAN廣泛應用于居民、辦公和商業區,基于WiFi的指紋定位成為最流行的室內定位技術之一[7]。該方法由離線階段和在線階段組成[8]:離線階段通過在參考點(reference point,RP)標記其坐標并采集可檢測到的接入點(access point,AP)的接收信號強度(received signal strength,RSS),構建由位置坐標和RSS組成的指紋庫[9];在線階段利用待定位點記錄不同AP的實時RSS值,通過與離線指紋庫互匹配估計待定位點的位置[10]。

目前常用的室內定位算法有K近鄰(K-nearest neighbor,KNN)、神經網絡和支持向量機等[11-13]。然而,這些方法存在一定的缺陷:KNN算法需要存儲所有的RSS訓練值且定位精度很大程度上依賴于K值;神經網絡算法訓練需要大量的數據和計算資源,且容易受到過擬合等問題的影響;支持向量機算法通過尋找最優的超平面,將RSS值映射到高維空間中進行分類,雖然具有較好的泛化能力和魯棒性,但需要選擇合適的核函數和正則化參數。Varma等[14]指出,隨機森林(random forest,RF)算法相較于KNN、支持向量機和決策樹等算法具有更好的位置匹配和定位偏差性能。然而,在實際的室內環境中,由于電磁干擾和障礙物造成AP的RSS值波動,傳統的RF算法會將空間中所有AP的RSS值作為決策樹候選劃分點,并且忽略強弱決策樹之間的差異性,給予決策樹相同權重后進行投票決策,這將會影響RF算法的分類正確率。因此,李兵等[15]引入聚類思想中的自適應窗口,根據特征集合構造變異系數,自適應地調整窗口長度,以控制滑動均值的變化;然后計算各個滑動均值的基尼系數,并選取具有最優基尼系數的滑動均值作為決策樹的劃分點。另外,楊宏宇等[16]采用bagging方法,以剩余樣本作為決策樹性能的評價指標,并根據評價指標賦予決策樹不同的投票權重,以增加算法模型的整體穩定性。針對室內定位的特殊應用環境,本文提出一種改進的隨機森林算法(improved random forest,IRF)。該算法能選取有效AP作為指紋特征值,用于構建分類回歸樹模型(classification and regression tree,CART),并根據AP的重要性賦予不同的投票權重,從而提高位置映射模型的穩定性和準確性。此外,該算法還采用粒子濾波(particle filter,PF)算法對位置進行校正,以獲得更為精確的二次定位坐標。

1 數據預處理

WLAN指紋定位離線階段的主要任務是建立指紋庫。為了建立健壯的指紋數據庫,需要先對原始RSS值進行預處理,以消除異常數據和粗大誤差。

假設R(i,j)是在j處的RP連續p次采集來自第i個AP的RSS,測量值集合S如式(1)所示。

(1)

測量值R(i,j)的平均值為:

(2)

(3)

計算剩余誤差的標準偏差σ,如式(4)所示。

(4)

2 改進隨機森林算法

RF算法首先采用bagging方法生成訓練子集;然后選取基尼系數最小值作為節點分裂的最佳分類特征來構建二叉決策樹;最后,將生成的決策樹集成為CART分類器,通過投票機制取眾數作為最終的定位結果[18]。在理想情況下,使用更多AP的RSS作為特征,可以提高定位精度;但是,在實際環境中,由于障礙物和多徑效應的影響,RSS值波動較大,因此,將所有AP的RSS作為定位特征,反而會降低定位精度。此外,RF算法的投票決策過程決定了最終定位預測結果,然而RF算法忽略CART決策樹強弱分類器差異,直接將單決策樹預測結果取眾數機制投票后作為最終定位結果。這種機制也會因為RSS波動的影響對室內定位系統整體判別性能造成一定偏差。因此,需要對隨機森林算法進行優化,以滿足室內高精度定位需求。

本文提出的IRF算法加入了特征選擇、樣本權重調整機制:通過特征選擇算法可以自動選擇與定位相關的特征,以提高模型的精度;而樣本權重調整則可以對不同的決策樹賦予不同的權重,從而更好地處理不平衡RSS的問題。

2.1 改進CART決策樹

假設μ(m,n)表示從預處理集合S*中第m處坐標為(xm,ym)的RP采集到的第n個AP的RSS,用RP坐標和AP的RSS構建用于定位的位置指紋數據庫F,如式(5)所示。

(5)

將第m個RP所接收到的μ(m,n)值降序排列,得到集合Pm={μ(m,1),μ(m,2),…,μ(m,n)}。滑動窗口長度ω從初始值開始滑動,窗口內的特征均值為:

(6)

特征均值增長率為:

c=|aj-aj-1|/|aj-1|

(7)

假設特征均值增長率閾值域為[F1,Fh)。當c

采用bagging取樣方法,從位置指紋樣本訓練集中有放回地隨機抽取新的樣本子集,作為決策樹的訓練子集D,Q為RSS向量集。在訓練子集中,創建不同決策樹,利用式(8)遞歸計算各候選劃分點的基尼系數G(D)。選取基尼系數G(D)的最小值作為劃分點,建立決策樹T(Q),生成CART模型。

(8)

其中:pb為b位置樣本的概率,B為b位置樣本數量。

在傳統的隨機森林算法中,每個CART決策樹都是基于所有特征進行構建的,這可能導致決策樹在處理噪聲和重疊特征時出現過擬合或欠擬合的情況。改進的隨機森林算法采用了特征選擇策略,選擇最相關的特征來構建決策樹,減少特征空間的噪聲,從而提高室內定位的精度。

2.2 改進的投票決策

在使用bagging方法從訓練集中訓練生成決策樹的過程中,每個樣本未被抽取到的概率為E=(1-Z-1)Z,Z為樣本總數。當樣本總數Z無限大時,即lim(1-Z-1)Z=0.368,說明對于單個決策樹而言,大約有37%的訓練數據未參與該決策樹的訓練生成,稱這部分數據為袋外數據(out-of-bag data,OOBD)。

T為已完成訓練的決策樹集。因單個決策樹對應的OOBD樣本位置已知,故可以利用OOBD檢驗所對應的單個決策樹分類的正確率At。將分類正確率作為決策樹的權重,可以增強決策樹之間的差異性,提高RF算法總判別性能。圖1為改進的投票決策流程。

圖1 改進的投票決策流程

隨機森林算法是一種集成學習方法,通過組合多個決策樹的結果來減少誤差。在傳統的隨機森林算法中,每個決策樹的結果是相互獨立的,這可能增加集成結果的方差。改進的隨機森林算法采用了樣本權重調整策略,通過引入權重來增加決策樹之間的差異性,從而減少集成結果的方差。

3 融合PF的IRF定位算法

首先,通過改進的隨機森林位置估計模型將待定位點的RSS與離線階段建立的位置指紋庫中的RSS進行互匹配,得出初步的定位結果;然后,采用PF算法進行二次定位,對初步定位結果進行位置修正和濾波,以獲得更為精確的目標點位置。

3.1 IRF匹配定位模型

在待定位點采集能夠接收到AP的RSS,構建RSS向量Q,利用IRF算法將向量Q與離線階段建立的位置指紋數據庫F進行互匹配,計算待定位點的位置坐標。利用IRF算法對待定位點的RSS進行定位的步驟如下:

步驟1：對于位置指紋數據庫F,利用式(6)和閾值域計算候選劃分點,并利用式(1)遞歸計算各候選劃分點的基尼系數。選取基尼系數的最小值作為劃分點,建立v棵決策樹集T(Q),將得到的v棵決策樹組成一個CART森林決策系統。

步驟2：使用bagging方法得到訓練樣本集Du。對CART進行訓練時,將OOBD檢驗生成的決策樹的正確率At作為單個決策樹的權重,以增強定位分類器間的差異性。

步驟3：將待定位點的RSS向量Q作為IRF模型的輸入,利用IRF計算出位置分類結果決策樹集。依據OOBD對不同決策樹賦予不同權重值,通過加權投票,最終計算出的定位結果為:

(9)

3.2 PF優化的定位結果

粒子濾波是一種基于蒙特卡洛仿真的近似貝葉斯遞歸濾波算法[19],可以處理線性高斯噪聲,也可以處理非線性和非高斯噪聲。利用粒子濾波算法對位置一次定位結果進行校正,可以降低由室內障礙物和多徑現象引起的RSS突變波動帶來的定位誤差。粒子濾波優化一次定位的算法步驟如下:

(10)

預測位置和觀測位置之間距離的標準差為dstd,利用式(11)計算第k次預測位置與觀測位置的歐式距離的概率密度。

(11)

(12)

步驟3：自由化重采樣。根據式(13)計算有效粒子數Ne。

(13)

(14)

4 仿真分析

4.1 實驗場景

本文使用的Zenodo數據集是從西班牙Universitat Jaume I的圖書館由專業人士從第3層和第5層分別測量得到[21]。數據集包含了多個采樣點,其中每個RP都記錄了WLAN接入點的RSS值和位置。由于圖書館第3層和第5層結構相同,所以本文選用第3層數據集對提出的定位方法進行性能研究。

圖2中三角形代表無線網絡設備,數據測量范圍是在如圖3所示的書架區域。該數據集在48個RP(每層24個RP)連續采集25個月來自不同網絡設備的RSS(每個無線網絡設備有多個以MAC地址和SSID唯一標識的AP),為了防止測量的隨機誤差,在每個RP處共采集RSS值的次數L=6。

圖2 無線網絡設備位置拓撲圖

圖3 數據采集點空間位置圖

圖3中,矩形位置代表書架區域,菱形位置表示訓練集和測試集的數據采集位置。RP間距最大約為4.2 m,最小約為1.8 m。

4.2 算法參數分析

在本研究中,將第3層書架區域劃分為由x軸和y軸組成的平面空間坐標系。針對指紋數據集中第3層第15個月的trn01數據庫,對RP采集編號為7的AP短時連續RSS進行可視化分析,如圖4所示,可以看出,在同一位置下的同一AP短時間內的RSS值會存在最大約19 dBm的波動。這種波動會在指紋匹配時造成較大的定位誤差,從而影響定位精度。因此,特征維度并不是越高,定位精度就越高。為提高定位精度,需要剔除RSS波動較大的AP。這個過程通過使用本文提出的改進CART決策樹方法來實現,使得數據更加平滑,減少噪聲的影響。

圖4 RSS波動圖

圖5顯示了指紋數據庫中第3層第15個月的trn01數據集的部分數據。在指紋庫中,如果RP處沒有檢測到AP的RSS值,則該位置的RSS設置為-105 dBm。通過對圖5中的數據進行分析可知:在同一RP處接收到不同AP的RSS的最小差約為1 dB,增長率約為2.0%,最大差值約為62 dB,增長率約為59.0%。基于以上分析及實驗驗證,滑動窗口平均增長率閾值設置為4.7%～9.5%之間,將有助于濾除RSS值變化過大的AP。

圖5 RP接收的RSS

本文所提出的算法中,滑動窗口長度會對有效AP的數量產生影響,進而影響指紋匹配定位的結果。若滑動窗口長度過大,則會減小有效AP的指紋特征數量;若滑動窗口長度過小,則會增大無效AP的指紋特征數量。因此,在實驗中,將滑動窗口長度初始值從1開始增加,觀察定位誤差的變化,分析最優初始滑動窗口長度值。實驗結果如圖6所示。

圖6 不同滑動窗口長度的定位誤差

由圖6可知:隨著滑動窗口長度ω由1逐漸增大時,定位誤差值逐漸減小;當滑動窗口長度ω=8時,定位誤差有最大的改善,75%概率誤差和平均誤差分別為1.983 m和1.632 m;然而,當滑動窗口長度繼續增大時,定位誤差反而增大。這是因為窗口增大時,有效AP指紋特征數量減少,影響了定位精度,因此,ω=8是該環境下的最佳值。

4.3 算法性能對比分析

IRF算法通過優化的CART準則,選取對預測定位結果有重要貢獻的AP特征,剔除RSS信號受干擾較大的AP。通過OOBD對決策樹投票加權,提高算法對關鍵特征的識別能力。在傳統RF算法中,各個決策樹對關鍵特征的識別能力可能存在差異。有些決策樹可能對某些關鍵特征的識別能力較弱,導致這些特征的重要性得不到充分體現。IRF算法通過對決策樹進行投票加權,可以對這些決策樹的影響進行削弱,從而提高算法對關鍵特征的識別能力。融合粒子濾波的IRF-PF算法先利用改進的隨機森林算法對WiFi信號進行特征選擇和分類,然后將分類結果作為粒子濾波的觀測量,利用粒子濾波對目標位置進行估計和預測。具體來說,改進的隨機森林算法可以剔除一些噪聲較大的WiFi信號,提高分類準確率,從而為粒子濾波提供更加準確的觀測量,同時粒子濾波可以對WiFi信號的時空特性進行建模,對隨機森林算法中可能存在的誤差進行校正,從而進一步提高定位精度。

為了驗證本文提出的IRF-PF算法相較于傳統RF、IRF算法的優越性,在選取的16個目標定位測試點進行定位精度對比實驗。圖7為基于這3種算法計算出的位置與目標定位測試點的定位誤差。圖8為基于RF算法和IRF-PF算法的估計位置與目標位置定位對比圖。

圖7 定位誤差

圖8 位置估計對比圖

由圖7可知:RF算法的定位誤差浮動較大,說明定位精度受環境影響較大;相比之下,融合粒子濾波的IRF-PF算法的定位誤差浮動較小,平均定位誤差約為1.72 m。進一步觀測圖8可以看出:IRF-PF定位算法的估計位置與目標位置更接近,聚集度更高。實驗結果表明:本文所提出的算法能夠有效平滑RSS波動帶來的定位誤差,并且具有較高的定位精度和良好的穩定性,進一步證明了本文所提算法的優越性和實用性。

為了驗證本文算法與其他主流定位算法的性能差異,在上述實驗環境中25個月以來所測量的數據集中,每個月選取24個測試點,將本文的IRF-PF算法與其他常見的4種算法在隨機選取的600個測試樣本中進行定位性能對比分析。圖9為嶺回歸(ridge regression,RR)、KNN、貝葉斯嶺回歸(Bayesian ridge regression,BRR)、RF和IRF-PF等5種定位算法的估計誤差累計分布函數性能比較。表1為5種定位算法的性能統計分析,其中:n為指紋樣本數量,m為特征維度,d為樹的最大深度,t為粒子數。

表1 誤差統計

由圖9和表1可以看出:相較于RR、KNN、BRR和RF算法,本文提出的IRF-PF算法將定位平均誤差分別降低了約40.93%、38.06%、35.34%、14.33%,且中值誤差更小,75%的概率誤差達到了1.983 m;結合各個算法的時間復雜度可以看出, 基于IRF-PF的定位算法在實時性方面表現良好。綜上所述,基于IRF-PF的室內定位算法較其他方法性能較優。

5 結論

針對AP的RSS波動導致定位精度不高的問題,提出了一種基于RSS特征選擇的WLAN室內定位算法。該算法利用滑動窗口思想選取RSS信號波動較小的AP作為構造CART的候選劃分節點,依據OOBD已知的空間位置信息,賦予決策樹不同的權值,增大單個決策樹之間的差異性;同時,引入PF算法,對IRF的一次定位結果進行校正解算,得到目標位置的二次定位結果,進一步提升了算法的精度。仿真結果表明:IRF-PF方法的平均定位誤差為1.632 m,能有效彌補RF算法定位缺陷;與其他方法相比,也具有更好的定位精度,能夠滿足室內環境中的目標定位需求。

考慮到不同室內環境中AP的RSS值波動不一致情況,后續實驗將在不同的室內環境中驗證本文算法的可靠性。同時,未來的研究將進一步探索如何挖掘RSS的高階特征,建立低復雜度的指紋庫,以減少定位誤差。這些研究工作將進一步提高算法的性能和實用性,為室內定位技術的應用提供更加可靠和精準的解決方案。