后验加权贝叶斯算法的WiFi室内定位

何 洋，吴 飞，张玉金，朱 海，蔡文炎

后验加权贝叶斯算法的WiFi室内定位

何 洋，吴 飞，张玉金，朱 海，蔡文炎

（上海工程技术大学 电子电气工程学院，上海 201620）

针对WiFi电磁指纹库方法的在线定位阶段中传统朴素贝叶斯算法对于定位数据样本的独立性假设具有主观性和局限性，且增加了计算开销的问题，提出基于后验加权贝叶斯算法的实时定位方法：加权贝叶斯算法为定位数据的特征属性分配适当的权值，考虑了定位数据之间的关联性；将其进一步优化，依据定位数据特性，加入后验概率估计过程以提高分类器的实时性；最后将改进后的加权贝叶斯算法与朴素贝叶斯算法和支持向量机算法进行比较分析。实验结果表明该方法能较好地提高在线定位阶段的实时性和精准性。

室内定位；属性权值；后验概率估计过程；实时性

0 引言

无线传感网络技术、大数据计算以及智能硬件等先进技术的迅速发展和应用成本的降低使得人们的日常出行变得更加智能便捷，很多应用以及活动行为均是基于位置信息进行个性化服务。室外开阔环境能够使用全球定位系统（global positioning system，GPS）或者北斗卫星导航系统（BeiDou navigation satellite system，BDS），这些精准的卫星系统为人们的行为活动提供优良的定位服务；而在场景错综复杂的室内环境下，卫星信号难以有效地接入终端设备：因此近年来室内定位已经成为人们关注的热点领域。

自从微软在2000年推出的Radar系统[1]和Maryland大学研发的Hours系统以来[2]，基于无线保真（wireless fidelity，WiFi）电磁信号的室内定位研究受到了广泛的关注，不同于利用超宽带（ultra wide band, UWB）、无线射频识别（radio frequency identification devices, RFID）和红外线等定位方式需要另外单独架设专门的传感设备，由于WiFi在现实生活中的普及程度和设备成本的因素，更有商用价值。根据文献[3]针对电磁信号的传播建立的损耗模型，WiFi信号在传播过程中经过不同区域会产生一定的质量衰减，正是利用这种信号的差异，依据接收信号强度（received signal strength, RSS）建立电磁指纹库的定位方式成为主流的方法之一。电磁指纹库的定位方式分为离线阶段和在线阶段，其中离线阶段扫描、采集周围区域中无线接入点（access point, AP）的RSS数值，并经由相关处理建立电磁指纹库。

在线阶段，运用相关的分类算法建立与电磁指纹库的数据映射关系，以实现定位功能。文献[4]针对RSS数值利用朴素贝叶斯（Naïve Bayes，NB）和三角形质心算法求解位置坐标，但是由于NB算法本身对于数据的独立性假设具有局限性，这一条件在实际运用中过于苛刻，且并未考虑数据分布本身的内在联系；所以文献[4-5]也存在相同的问题。同样从在线阶段考虑，文献[6]提出基于支持向量机（support vector machine, SVM）分类与回归的定位方法，其中SVM算法分类决策时仅考虑少量的支持向量，所以可以避免维数爆炸，且分类效果较好，在小数据集上表现优秀；但是在实际运用中，真实的定位数据集规模通常很大，所以并不适合实际运用[7]。

因此考虑在线定位阶段的定位区域分类效果和应用的普适性[8]，提出后验加权贝叶斯（posteriorweighted Naïve Bayes，PWNB）算法，结合定位数据自身特性为特征属性分配适当的权值，从数据之间的关联性考虑，能更有效地反映定位数据密度之间的真实关系，打破传统算法基于独立性假设的局限性。从定位实时性考虑，加入后验概率估计过程可减小计算开销、降低实际运用的延迟性。

1 基于WiFi电磁指纹库定位方法

利用WiFi电磁指纹库的定位方法主要分为离线阶段和在线阶段[9]。其中，离线阶段主要使用相关设备采集定位环境区域内WiFi的RSS数值，并对所采集到的数据做一定的处理，合理划分，形成离线电磁指纹数据库[10]。在线阶段，对于进入定位区域内的待定位目标，依据其获得的RSS值与离线电磁指纹数据库中的数值进行分类运算[11]，获取该目标当前所处的位置信息。图1为电磁指纹库方法原理图。

图1 电磁指纹库方法原理

2 朴素贝叶斯算法

朴素贝叶斯算法在很多实际应用中有着良好的效果，算法设计思想简单，主要基于贝叶斯理论[12]，其表达式为

根据机器学习理论，朴素贝叶斯算法分类器主要分为训练阶段和测试阶段：训练阶段的流程为

Input:定位数据集

3 后验加权贝叶斯算法

由于传统的朴素贝叶斯算法主要基于独立性假设进行分类器的设计，但是现实中的定位数据之间必然存在一定的关联性[15]；因此使用朴素贝叶斯分类器显然并不合理。实际运用的室内定位系统将会处理大量的定位数据集，并且为了保证良好的用户体验度，要求功能具有实时性，否则也将失去意义。根据传统朴素贝叶斯算法的不足，提出改进加权贝叶斯算法，作出了以下2点改进。

3.1 增加后验概率估计过程

图2 传统算法与改进算法区别

因此根据方差的波动程度，不同的定位分类单元根据自身对应的分类区域能够有效区别自身的定位类型，减小了计算开销，从宏观上提升了定位的实时性。

3.2 依据特征属性分配适当权值

真实的定位数据之间存在有效的关联性，根据每个样本属性的贡献程度为其分配适当的权值，从而缓解了传统朴素贝叶斯算法中主观的独立性假设。

考虑特征属性之间的关联，加入适当权重后的贝叶斯分类方法为

所以改进后的加权贝叶斯算法流程为：

Input: 定位数据样本、标签数据；

依式（4）、式（5）进行后验概率估计；通过式（6）判别最大后验概率

Output: 定位区域location

改进后的加权贝叶斯算法设计思路简单，没有增加复杂的公式计算。算法相比于朴素贝叶斯的独立性假设，改进后的算法为相关的特征分配合适的权重，从数据之间的关联性考虑更符合数据的真实意义，从而提高了定位的精准性。并且，加入后验概率估计过程让不同的定位分类单元能够有效辨识自身分类元素特征，避免了对所有数据后验概率重复性的计算，降低了计算开销，从宏观体验上提高了定位的实时性。

4 实验与结果分析

4.1 实验设计

为了更好地验证改进算法对于室内定位的效果，本次实验共采集986个WiFi电磁信号形成电磁指纹库，连续采集100组数据，采集时间间隔为1 s，以1.5 m×1.5 m为基准划分网格。其中实验场地选自实训楼走廊，如图3所示。

图3 实验场地

为了便于对定位效果进行更好的分析，引入用于评判的误差函数，其表达式为

4.2 实验分析

本实验利用本文所提出的PWNB算法同经典的NB算法和SVM算法进行合理有效的对比，其中区域1~5如图3所示，相关实验数据如表1所示。

表1 实验定位指纹数据

续表1

为了更好地分析上述算法在实际定位中的效果，实验数据均经过去噪、缺失值等预处理。实验结果表明，所提出的PWNB算法相比于NB算法和SVM算法，在不同定位区域的定位性能有很大程度的提高。

图4所示为定位误差分析，提出的PWNB算法同经典的NB算法相比，对于后验概率的求解并未使用独立性假设策略，而是充分考虑了定位数据特征属性之间的相互影响，显然更符合实际情况。SVM算法对于二分类的小数据集问题上表现优异，但是对于实际中大量的定位数据进行多区域分类处理则显得较为吃力；而PWNB算法主要依据统计的思想，针对大数据集反而能够进一步提升其精确度。实验表明PWNB算法有93.2%的定位误差可控制在1.5 m范围内，而NB算法和SVM算法，误差在1.5 m内的定位误差分别为53%和74%，显然提出的PWNB算法效果最优。

图4 定位误差分析

为了更进一步对上述3种算法在实际定位应用中进行效果的比较，特选取区域1中的位置，选择50组定位序列进行仿真，结果如图5所示。

经过实验分析，表明运用PWNB算法相比于NB算法精度提高了2.3 m，与SVM算法相比提高了1 m；所以提出的PWNB算法明显优于其他二者。

从定位在线阶段的实时性进行分析，由于PWNB算法相比于传统NB算法而言，加入了后验概率估计过程；与相关特征属性关联的分类单元能够有效识别是否为自身属性，避免了对不属于自身属性的概率计算，从用户定位体验度来看，提高了定位的时效性。从图6不同区域定位时间对比图可以看到：PWNB算法平均定位时间均在14.6 s，SVM在针对大规模定位数据集处理时，需要将所有的数据一次性读入内存进行计算，显然对设备性能有极高的要求，降低了定位的时效性，相比之下NB算法的计算开销稍低。因此，从定位的时效性考究，PWNB算法性能最好。

图5 定位结果误差

图6 不同区域定位时间对比

5 结束语

经过以上算法分析和实验总结，针对WiFi室内定位的在线阶段使用PWNB算法的定位性能明显优于同类的分类算法。结合后验概率估计过程，让针对不同定位特征属性的分类单元发挥最优效率，降低了计算开销，提升了在线定位的时效性。同时，从定位数据的真实意义考虑，强调了定位数据之间的关联性，更切合实际场景的运用。

[1] BAHL P, PADMANABHAN V N. RADAR: an in-building RF-based user location and tracking system[EB/OL]. [2018-08-28]. http://www.cs.columbia.edu/~drexel/CandExam/RADAR_in_building_RF.pdf.

[2] YOUSSEF M, AGRAWALA A. The Horus WLAN location determination system[EB/OL]. [2018-08-28]. https://www.cs.umd.edu/~moustafa/papers/horus_usenix.pdf.

[3] WANG Y, JIA X, LEE H K. An indoor wireless positioning system based on wireless local area network infrastructure [EB/OL].[2018-08-28]. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.1364&rep=rep1&type=pdf.

[4] 郭菲菲. 基于贝叶斯学习的RFID室内定位方法的研究[D].哈尔滨: 哈尔滨工业大学, 2008.

[5] 焦瑞强. 贝叶斯惩罚回归中正则化参数的选择[D]. 成都: 西南交通大学, 2017.

[6] 华海亮. 基于WiFi和蓝牙的室内定位技术研究[D]. 锦州: 辽宁工业大学, 2016.

[7] 朱荣, 白光伟, 沈航,等. 基于贝叶斯过滤法的CSI室内定位方法[J].计算机工程与设计, 2015(3):567-571.

[8] 彭玉旭, 杨艳红.一种基于RSSI的贝叶斯室内定位算法[J].计算机工程, 2012, 38(10):237-240.

[9] 桑楠, 袁兴中, 周瑞. 基于SVM分类和回归的WiFi室内定位方法[J].计算机应用研究, 2014, 31(6):1820-1823.

[10] 杨萌, 修春娣, 邹坤,等.一种基于感知概率的室内定位匹配算法[J]. 导航定位学报, 2014, 2(4):49-53.

[11] JOHN G H,LANGLEY P. Estimating continuous distributions in Bayesian classifiers[EB/OL].[2018-08-28]. http://web.cs.iastate.edu/~honavar/bayes-continuous.pdf.

[12] 雷雨伟, 修春娣, 杨威,等. WiFi与MEMS-IMU融合定位方法在室内定位中的应用[J]. 导航定位学报, 2016, 4(4): 81-87.

[13] 李帅鑫，李广云，符京杨，等. 室内移动定位与测图系统的高精度标定[J]. 导航定位学报, 2018, 6(3): 23-30．

[14] DAS K, WYMEERSCH H. Censoring for Bayesian cooperative positioning in dense wireless networks[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(9): 1835-1842.

[15] OUYANG R W, WONG K S, LEA C T, et al. Indoor location estimation with reduced calibration exploiting unlabeled data via hybrid generative/discriminative learning[J]. IEEE Transactions on Mobile Computing, 2012, 11(11): 1613-1626.

WiFi indoor positioning based on posterior weighted Bayesian algorithm

HE Yang, WU Fei, ZHANG Yujin, ZHU Hai, CAI Wenyan

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

Aiming at the problems that it is liable to subjectivity and limitations on the independence of positioning data samples and to large computational overhead in the online positioning stage of WiFi electromagnetic fingerprint library method for traditional Naïve Bayes (NB) algorithm, the paper proposed a real-time localization method based on posterior weighted Naïve Bayes (PWNB) algorithm: the feature attributes of the positioning data were assigned the appropriate weights by weighted NB considering the correlation between the positioning data; and further optimization was carried out, then the posterior probability estimation process was added to improve the real-time performance of the classifier according to the characteristics of the positioning data; finally the modified weighted Bayesian algorithm was compared with NB algorithm and spport vector machine (SVM) algorithm. Results showed that the proposed method could efficiently improve the real-time and the accuracy of the online positioning phase.

indoor positioning; attribute weight; posterior probability estimation process; real-time

P228

A

2095-4999(2019)03-0051-06

2018-10-22

国家自然科学基金资助项目（61272097）；上海市科技学术委员会重点项目（18511101600）；上海市自然科学基金项目（17ZR1411900）；上海市信息安全综合管理技术研究重点实验室项目（AGK2015006）；上海高校青年教师培养资助计划项目（ZZGCD 15090）；上海工程技术大学科研启动项目（2016-56）。

何洋(1995—)，男，安徽合肥人，硕士生，研究方向为无线定位。

吴飞（1967—），男，上海人，博士，教授，研究方向为计算机网络与计算机能耗优化。

何洋，吴飞，张玉金，等.后验加权贝叶斯算法的WiFi室内定位[J].导航定位学报,2019,7(3):51-56.（HE Yang, WU Fei, ZHANG Yujin,et al.WiFi indoor positioning based on posterior weighted Bayesian algorithm[J].Journal of Navigation and Positioning,2019,7(3):51-56.）

10.16547/j.cnki.10-1096.20190309.