韓學(xué)法　吳飛　時(shí)瑤佳　胡銳　聶大惟

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

關(guān)鍵詞： 室內(nèi)定位; Wi-Fi指紋; 指紋數(shù)據(jù)庫; 隨機(jī)森林; 位置感知

文章編號： 2095-2163（2021）07-0102-05中圖分類號：TP393文獻(xiàn)標(biāo)志碼： 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 引 言

隨著智能手機(jī)的普及，基于位置服務(wù)（Location Based Services，LBS）的應(yīng)用在日常生活中備受關(guān)注，高精度的室內(nèi)定位技術(shù)已經(jīng)成為現(xiàn)階段的研究熱點(diǎn)[1]。室內(nèi)定位技術(shù)主要包括藍(lán)牙技術(shù)[2]、Wi-Fi技術(shù)[3]、UWB[4]技術(shù)及RFID[5]技術(shù)等。

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

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

1 Wi-Fi指紋定位技術(shù)

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

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

指紋匹配算法是室內(nèi)Wi-Fi指紋定位過程中最為重要的環(huán)節(jié)，常用的算法包括NN算法、KNN算法、WKNN算法和統(tǒng)計(jì)概率算法[12]。

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

考慮到Wi-Fi信號強(qiáng)度的相似性，本文以RSSI值和基本服務(wù)集標(biāo)識符（BSSID）來構(gòu)建指紋數(shù)據(jù)庫，提出一種基于隨機(jī)森林和Wi-Fi指紋的定位算法。

2.1 隨機(jī)森林

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

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

Step 2 在決策樹的子節(jié)點(diǎn)上隨機(jī)地從n個指標(biāo)中選取m個，選取最優(yōu)分割指標(biāo)進(jìn)行分割。

Step 3 重復(fù)步驟Step 2遍歷預(yù)建的N棵分類樹。

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

RF生成步驟如圖2所示。由圖2可知，隨機(jī)森林生成過程中關(guān)鍵是確定N值，N值直接影響投票決定的最優(yōu)結(jié)果。

2.2 定位算法

傳統(tǒng)的室內(nèi)Wi-Fi指紋定位算法，采用隨機(jī)森林模型時(shí)只考慮采樣室內(nèi)空間網(wǎng)格中的RSSI值，這樣難以依據(jù)環(huán)境因素反映每個網(wǎng)格位置的信號強(qiáng)度并加以區(qū)分。因此，本文以RSSI值和BSSID共同作用來區(qū)分網(wǎng)格位置的信號強(qiáng)度，構(gòu)建包括位置坐標(biāo)、RSSI和BSSID的Wi-Fi指紋庫。

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

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

Step 1 執(zhí)行算法，采集A區(qū)Wi-Fi實(shí)測數(shù)據(jù)，將其記為B。B中包括位置坐標(biāo)信息、RSSI和BSSID。

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

Step 3 選取強(qiáng)度最大5個AP，構(gòu)建Wi-Fi指紋，將其作為隨機(jī)森林進(jìn)行學(xué)習(xí)的樣本集D。

Step 4 采用2.1節(jié)所提出的隨機(jī)森林算法構(gòu)建隨機(jī)森林，進(jìn)行學(xué)習(xí)訓(xùn)練。

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

Step 6 得出預(yù)測的定位結(jié)果（xi，yi）。

3 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證本文所提的基于隨機(jī)森林和Wi-Fi指紋的定位算法的可行性以及與同類算法相比的優(yōu)勢，進(jìn)行仿真實(shí)驗(yàn)與分析。

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

表2中存儲參考節(jié)點(diǎn)（待定位點(diǎn)）處信號強(qiáng)度最強(qiáng)的5個AP的RSSI值，作為隨機(jī)森林進(jìn)行學(xué)習(xí)的樣本集。

3.2 實(shí)驗(yàn)分析

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

其中，（x0i，yoi）為參考點(diǎn)的實(shí)測坐標(biāo)，（xi，yi）為各定位算法解算的參考點(diǎn)坐標(biāo)。然而，本文算法的誤差由每顆決策樹的均值誤差共同作用，其計(jì)算公式為：

確定合適的N值。為了確定合適的N值進(jìn)行3次實(shí)驗(yàn)，具體信息見表3。

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

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

當(dāng)N=30時(shí)，將本文的算法和基于RSSI和隨機(jī)森林的同類算法相比，對比效果如圖5和圖6所示。

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

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

4 結(jié)束語

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

參考文獻(xiàn)

[1]李華蓉，趙一. 室內(nèi)定位導(dǎo)航地圖一體化設(shè)計(jì)[J]. 測繪通報(bào)，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ī)森林室內(nèi)定位[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2018，39（05）：1490-1496.

[8]郭妍， 陳曉， 任曉曄. 一種優(yōu)化隨機(jī)森林模型的室內(nèi)定位方法[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]毛萬葵， 吳飛， 張玉金， 等. 基于改進(jìn)BKM聚類算法的WiFi室內(nèi)定位方法[J]. 測控技術(shù)， 2019，38（5）：44-47.

[12]李航. 基于位置指紋方法的WIFI室內(nèi)定位技術(shù)研究[D]. 吉林：長春工業(yè)大學(xué)， 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ī)森林的洪災(zāi)風(fēng)險(xiǎn)評價(jià)模型及其應(yīng)用[J]. 水利學(xué)報(bào)， 2015，46（1）：58-66.

基金項(xiàng)目： 上海市高校研究生創(chuàng)新項(xiàng)目（19KY0216）; 上海市科技學(xué)術(shù)委員會重點(diǎn)項(xiàng)目（18511101600）; 國家科學(xué)基金青年基金項(xiàng)目（61902237）; 上海市科委青年科技英才“揚(yáng)帆計(jì)劃”項(xiàng)目（19YF1418200） 。

作者簡介： 韓學(xué)法（1994-），男，碩士研究生，主要研究方向：室內(nèi)定位與導(dǎo)航; 吳 飛（1968-），男，博士，教授，主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與計(jì)算機(jī)能耗優(yōu)化。

通訊作者： 韓學(xué)法Email：hxf_edu@edu.com

收稿日期： 2020-12-14