基于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