基于Wi-Fi指紋和隨機森林的定位算法

韓學法　吳飛　時瑤佳　胡銳　聶大惟

摘 要： 針對Wi-Fi信號強度的相似性對室內定位的影響，本文提出一種基于Wi-Fi指紋和隨機森林的室內定位算法。該算法采用Wi-Fi作為信號源，以接收信號強度指示和基本服務集標識符來構建Wi-Fi指紋庫，從而建立隨機森林模型用于室內位置感知。仿真實驗表明，該算法的定位誤差約為2.26 m， 與同類算法相比，在執行時間和定位精度上具有較好的優越性，算法精度提高約3.2%。

關鍵詞： 室內定位; Wi-Fi指紋; 指紋數據庫; 隨機森林; 位置感知

文章編號： 2095-2163（2021）07-0102-05中圖分類號：TP393文獻標志碼： A

Location algorithm based on Wi-Fi fingerprint and Random Forest

HAN Xuefa， WU Fei， SHI Yaojia， HU Rui， NIE Dawei

（School of Electronic and Electrical Engineering， Shanghai University of Engineering Science， Shanghai 201620， China）

【Abstract】Aiming at the influence of the similarity of Wi-Fi signal strength on indoor positioning， this paper proposes an indoor positioning algorithm based on Wi-Fi fingerprint and Random Forest. The algorithm uses Wi-Fi as a signal source to construct theWi-Fi fingerprint library by receiving signal strength indication and basic service set identifiers， thereby establishing a Random Forest model for indoor location sensing. The simulation results show that the positioning error of the algorithm is about 2.26 m. Compared with similar algorithms， it has better performance in execution time and positioning accuracy， and the accuracy of the algorithm is improved by about 3.2%.

【Key words】indoor positioning; Wi-Fi fingerprint; fingerprint database; Random Forest; location perception

0 引 言

隨著智能手機的普及，基于位置服務（Location Based Services，LBS）的應用在日常生活中備受關注，高精度的室內定位技術已經成為現階段的研究熱點[1]。室內定位技術主要包括藍牙技術[2]、Wi-Fi技術[3]、UWB[4]技術及RFID[5]技術等。

基于Wi-Fi的定位技術因具有硬件部署成本低、計算開銷小、定位精度相對較高的優點[6]，目前被廣泛用于室內定位。國內外學者對室內Wi-Fi指紋定位技術進行了大量的研究。文獻[7]提出一種基于密度聚類的隨機森林的室內定位算法，采用網格搜索和交叉驗證技術，降低了定位誤差;文獻[8]提出一種基優化隨機森林模型的改進算法，提高定位算法的預測能力;文獻[9]提出一種結合Wi-Fi指紋和無線接入點（Wireless access point，AP）的選擇的室內定位方法，有效地降低多徑效應的對定位結果的影響。

然而，上述方法只是單一考慮接收信號強度指示值（Received Signal Strength Indication，RSSI），但定位結果會受到Wi-Fi信號強度相似性的影響[10]。因此，針對這一問題，本文提出一種基于Wi-Fi指紋和隨機森林的室內定位算法。與同類算法相比，該算法在執行時間和定位精度具有較好的優越性，且定位準確率提高了約3.2%。

1 Wi-Fi指紋定位技術

Wi-Fi指紋定位技術是利用空間位置Wi-Fi信號的唯一性進行位置指紋匹配的定位方法，從而得到定位點的位置信息。指紋匹配定位是一種常用的室內定位方法，包括離線階段和在線階段[11]。

離線階段的任務是采集各個無線接入點（Wireless access point，AP）的RSSI值，將參考點的RSSI值與位置信息結合起來建立指紋庫;在線階段的任務是在定位點采集各個AP的RSSI值，通過匹配算法從指紋庫中匹配出最相似的指紋并得到定位點的位置信息[12]。Wi-Fi指紋定位技術流程如圖1所示。

指紋匹配算法是室內Wi-Fi指紋定位過程中最為重要的環節，常用的算法包括NN算法、KNN算法、WKNN算法和統計概率算法[12]。

2 基于Wi-Fi指紋和隨機森林的定位算法

考慮到Wi-Fi信號強度的相似性，本文以RSSI值和基本服務集標識符（BSSID）來構建指紋數據庫，提出一種基于隨機森林和Wi-Fi指紋的定位算法。

2.1 隨機森林

隨機森林（Random Forest，RF）是在2001年提出的一種基于決策樹分類器的機器學習算法[13]，采用Bagging方法[14]在訓練樣本集D中抽取N個自助樣本集，為每一個樣本集訓練一個決策樹。RF的生成步驟下如圖1所示[15]，算法具體過程描述如下：

Step 1 在樣本集D選取N個子訓練樣本集D1、D2、…、DN，并預建N棵決策樹。

Step 2 在決策樹的子節點上隨機地從n個指標中選取m個，選取最優分割指標進行分割。

Step 3 重復步驟Step 2遍歷預建的N棵分類樹。

Step 4 由N棵分類樹形成RF。

RF生成步驟如圖2所示。由圖2可知，隨機森林生成過程中關鍵是確定N值，N值直接影響投票決定的最優結果。

2.2 定位算法

傳統的室內Wi-Fi指紋定位算法，采用隨機森林模型時只考慮采樣室內空間網格中的RSSI值，這樣難以依據環境因素反映每個網格位置的信號強度并加以區分。因此，本文以RSSI值和BSSID共同作用來區分網格位置的信號強度，構建包括位置坐標、RSSI和BSSID的Wi-Fi指紋庫。

由于在每個位置采集到所有AP的BSSID（MAC地址）是相同的，但其強度大小不同，所以可通過RSSI值和BSSID共同作用過濾掉強度差的AP。從而減少后期在線階段的匹配次數，提高執行效率。本文所提出的定位算法與指紋匹配定位算法原理相似，其流程如圖3所示。

在上述流程圖中，A為采集Wi-Fi數據的室內區域縮略圖，B為過濾前采集的Wi-Fi指紋數據，C為過濾后采集的Wi-Fi指紋數據，D為用于隨機森林進行學習訓練的Wi-Fi指紋庫。本文所提出的基于Wi-Fi指紋和Wi-Fi指紋的定位算法的步驟描述如下：

Step 1 執行算法，采集A區Wi-Fi實測數據，將其記為B。B中包括位置坐標信息、RSSI和BSSID。

Step 2 位置篩選，將每個位置的BSSID序列和B中進行對比。若一致，則以RSSI值降序方式保存RSSI和BSSID到C中，否則刪除不一致的數據。

Step 3 選取強度最大5個AP，構建Wi-Fi指紋，將其作為隨機森林進行學習的樣本集D。

Step 4 采用2.1節所提出的隨機森林算法構建隨機森林，進行學習訓練。

Step 5 定位階段將保存的Wi-Fi指紋庫D作為樣本集輸入隨機森林模型進行預測。

Step 6 得出預測的定位結果（xi，yi）。

3 仿真實驗與分析

為了驗證本文所提的基于隨機森林和Wi-Fi指紋的定位算法的可行性以及與同類算法相比的優勢，進行仿真實驗與分析。

3.1 實驗設計

實驗硬件設備為TinkPad T480筆記本電腦一臺，以MATLAB R2018a為仿真實驗平臺構建一個長20 m、寬15 m、高4 m的開放的室內空間，將其劃分為大小為1 m的方格進行仿真實驗。通過一次仿真實驗得到指紋樣本集C的部分信息見表1。

在表1中的樣本集C中選取信號強度最大5個AP構建Wi-Fi指紋庫D，并將其作為隨機森林模型的樣本集，樣本集D的具體信息見表2。

表2中存儲參考節點（待定位點）處信號強度最強的5個AP的RSSI值，作為隨機森林進行學習的樣本集。

3.2 實驗分析

由在2.1節中隨機森林生成算法可知，確定N值尤為重要。每個定位點采用歐式距離計算誤差，其公式為：

其中，（x0i，yoi）為參考點的實測坐標，（xi，yi）為各定位算法解算的參考點坐標。然而，本文算法的誤差由每顆決策樹的均值誤差共同作用，其計算公式為：

確定合適的N值。為了確定合適的N值進行3次實驗，具體信息見表3。

由表3可知，隨著N值的不斷增大，模型的訓練時間和預測時間也會增加。對于定位效果來說，實時性是至關重要，減少誤差的同時不能忽略執行時間。為了更加直觀，對3次實驗的誤差取均值作圖，如圖4所示。

由圖4可知，當N為30～40間的誤差趨于穩定，N大于40時，誤差有所減低但執行時間也增加了。對于定位來說，要考慮時效性，故N值取30是比較合適的。

當N=30時，將本文的算法和基于RSSI和隨機森林的同類算法相比，對比效果如圖5和圖6所示。

由圖5可知，本文算法的預測時間不會隨著指紋數量的增多而增加，而同類算法則會指紋數量呈線性增長趨勢。對于定位來說，實時性相當重要，所以本文所提的算法在實時性是滿足要求的。

由圖6可知，本文算法在不同位置的定位準確率高于同類算法約3.2%左右。因此，本文算法在不影響執行時間的情況下，提高了室內定位的準確率。

4 結束語

Wi-Fi信號強度的相似性會對定位效果產生影響，同一點處采集Wi-Fi信號來都自于相同的AP，單一考慮Wi-Fi信號的RSSI值是無法確定Wi-Fi信號強度對定位結果的影響。因此，本文提出一種基于Wi-Fi指紋和隨機森林的定位算法，該算法以RSSI和BSSID共同作用來選取強度最大的5個AP用于構建指紋庫。將Wi-Fi指紋庫輸入隨機森林進行學習，從而構建隨機森林模型。仿真實驗表明，本文算法的定位誤差約為2.26 m，與同類算法相比，算法的執行時間不會隨樣本集大小而變化，且定位準確率提高約3.2%。然而，由于Wi-Fi信號中含有一種受墻壁或障礙物影響而產生的噪聲，因此未來研究需要解決噪聲問題。

參考文獻

[1]李華蓉，趙一. 室內定位導航地圖一體化設計[J]. 測繪通報，2015（ 9） ： 32-35.

[2]KWAK J， SUNG Y. Beacon-based indoor location measurement method to enhanced common chord-based trilateration[J]. Journal of Information Processing Systems， 2017，13（6）：1640-1651.

[3]MA Zixiang， WU Bang， POSLAD S. A WiFi RSSI ranking fingerprint positioning system and its application to indoor activities of daily living recognition[J]. International Journal of Distributed Sensor Networks， 2019，15（4）：155014771983791.

[4]De ANGELIS G， MOSCHITTA A， CARBONE P. Positioning techniques in indoor environments based on stochastic modeling of UWB round-trip-time measurements[J]. IEEE Transactions on Intelligent Transportation Systems， 2016，17（8）：2272-2281.

[5]MONTASER A， MOSELHI O. RFID indoor location identification for construction projects[J]. Automation in Construction， 2014，39：167-179.

[6]HU Xujian， WANG Hao. WIFI indoor location optimization method based on position fingerprint algorithm[C]//2017 International Conference on Smart Grid and Electrical Automation（ICSGEA）.Changsha， China ：IEEE，2017：585-588.

[7]張萌， 呂艷， 倪益華， 等. 基于密度峰值聚類的隨機森林室內定位[J]. 計算機工程與設計， 2018，39（05）：1490-1496.

[8]郭妍， 陳曉， 任曉曄. 一種優化隨機森林模型的室內定位方法[J]. 激光雜志， 2018，39（10）：70-74.

[9]LI Qiyue， LI Wei， SUN Wei， et al. Fingerprint and assistant nodes based Wi-Fi localization in complex indoor environment[J]. IEEE Access， 2016，4：2993-3004.

[10]LEE S， MOON N. Location recognition system using random forest[J]. Journal of Ambient Intelligent and Humanized Computing， 2018，9（4SI）：1191-1196.

[11]毛萬葵， 吳飛， 張玉金， 等. 基于改進BKM聚類算法的WiFi室內定位方法[J]. 測控技術， 2019，38（5）：44-47.

[12]李航. 基于位置指紋方法的WIFI室內定位技術研究[D]. 吉林：長春工業大學， 2018.

[13]BREIMAN L. Random Forests[J]. Machine Learning， 2001， 45（1）：5-32.

[14]BREIMAN L. Bagging predictors[J]. Machine Learning， 1996， 24（2）：123-140.

[15]賴成光， 陳曉宏， 趙仕威， 等. 基于隨機森林的洪災風險評價模型及其應用[J]. 水利學報， 2015，46（1）：58-66.

基金項目： 上海市高校研究生創新項目（19KY0216）; 上海市科技學術委員會重點項目（18511101600）; 國家科學基金青年基金項目（61902237）; 上海市科委青年科技英才“揚帆計劃”項目（19YF1418200） 。

作者簡介： 韓學法（1994-），男，碩士研究生，主要研究方向：室內定位與導航; 吳 飛（1968-），男，博士，教授，主要研究方向：計算機網絡與計算機能耗優化。

通訊作者： 韓學法Email：hxf_edu@edu.com

收稿日期： 2020-12-14