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

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

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

文章編號(hào)： 2095-2163（2021）07-0102-05中圖分類號(hào)：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ì)算開銷小、定位精度相對(duì)較高的優(yōu)點(diǎn)[6]，目前被廣泛用于室內(nèi)定位。國(guó)內(nèi)外學(xué)者對(duì)室內(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ù)測(cè)能力;文獻(xiàn)[9]提出一種結(jié)合Wi-Fi指紋和無(wú)線接入點(diǎn)（Wireless access point，AP）的選擇的室內(nèi)定位方法，有效地降低多徑效應(yīng)的對(duì)定位結(jié)果的影響。

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

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

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

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

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

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

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

2.1 隨機(jī)森林

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

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

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

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

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

RF生成步驟如圖2所示。由圖2可知，隨機(jī)森林生成過(guò)程中關(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)境因素反映每個(gè)網(wǎng)格位置的信號(hào)強(qiáng)度并加以區(qū)分。因此，本文以RSSI值和BSSID共同作用來(lái)區(qū)分網(wǎng)格位置的信號(hào)強(qiáng)度，構(gòu)建包括位置坐標(biāo)、RSSI和BSSID的Wi-Fi指紋庫(kù)。

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

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

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

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

Step 3 選取強(qiáng)度最大5個(gè)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指紋庫(kù)D作為樣本集輸入隨機(jī)森林模型進(jìn)行預(yù)測(cè)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[1]李華蓉，趙一. 室內(nèi)定位導(dǎo)航地圖一體化設(shè)計(jì)[J]. 測(cè)繪通報(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]毛萬(wàn)葵， 吳飛， 張玉金， 等. 基于改進(jìn)BKM聚類算法的WiFi室內(nèi)定位方法[J]. 測(cè)控技術(shù)， 2019，38（5）：44-47.

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

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

作者簡(jiǎn)介： 韓學(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