基于层次聚类和贝叶斯的室内定位算法

来源:用户上传      作者:

　　摘  要： 针对目前基于WiFi的位置指纹室内定位算法精度不高，计算消耗时间过长，实时性差的问题，提出一种改进的室内定位算法。首先利用层次聚类的算法进行预匹配，缩小定位区域，达到降低匹配数据，提高实时性的目的，然后利用贝叶斯算法进行定位。实验结果表明，所提出的定位算法在精度和定位实时性方面都有了很大的改善。
　　关键词： 室内定位; 层次聚类; 贝叶斯; 实时性
　　中图分类号：TP39          文献标志码：A    文章编号：1006-8228（2019）02-05-04
　　Indoor location algorithm based on hierarchical clustering and Bayesian
　　Chang Jinming， Wang Honglei
　　（School of Electrical Engineering， Guizhou University， Guiyang， Guizhou 550025， China）
　　Abstract： In order to solve the problems of low precision， long computation time and poor real-time of WiFi-based position fingerprint indoor location algorithm， an improved indoor location algorithm is proposed. Firstly， the hierarchical clustering algorithm is used to pre-match， reduce the location area， reduce the matching data and improve the real-time performance. Then， Bayesian algorithm is used to locate. The experimental results show that the proposed location algorithm has a great improvement in accuracy and real-time positioning.
　　Key words： indoor location; hierarchical clustering; Bayesian; real-time
　　0 引言
　　目前，随着全球卫星定位系统（GPS）的日益成熟，室外位置服务也变得越来越完善，但是GPS信号只有在目标与位置间无遮挡才能准确定位，然而越来越多的高楼大厦出现在城市中，这使得GPS在高楼之间的定位结果不准确，甚至出现无法定位的情况，单纯的室外定位服务已无法满足需求，因此，室内定位技术的地位日益重要[1]。
　　国内外学者针对室内定位做了大量的研究，传统的室内定位技术有基于蓝牙、RFID、地磁、红外线、超宽带、WiFi等方法，前几种方法都存在相应的缺陷，要么需要特殊的传感器，导致成本过高，要么定位区域有限制，使得精度过低等。基于WiFi的室内定位技术由于其成本低廉，不需要额外的传感器，并且精度可靠等原因，成为了研究的热点。WiFi定位技术主要分为：①基于传播模型的定位方法;②基于位置指纹的定位方法[2]。其中，基于位置指纹的方法不需要知道AP（信号发射器）具体位置，且由于算法简单精度较高，受到了广泛的关注和研究。高仁强[3]等人结合模糊数学理论的方法对传统的定位算法进行改进，提高了定位精度;李军等[4]人利用随机森林算法对指纹数据进行训练和分类，缩短了定位时间，提高了系统的可靠性;曹晓祥等[5]人针对位置指纹的几何结构对传统的WKNN算法进行改进，提高了定位的精度。
　　众多的算法在匹配临近点的时候，大多会由于WiFi信号的波动，导致定位偏差，并且定位算法在匹配过程中依靠单一变量，这也造成精度不够。针对此，提出一种融合层次聚类和朴素贝叶斯的新算法，先利用层次聚类算法进行预匹配降低搜索范圍，达到提高定位速度的目的[6]，然后利用改进的贝叶斯算法求解出结果，从而提高精度。
　　1 基于层次聚类和改进贝叶斯的定位算法
　　基于WiFi的位置指纹定位算法通常分为两个阶段，离线阶段和在线阶段。本算法在离线阶段，首先对待定位区域进行均匀划分，最终得到M个参考点，然后记录每个参考点的坐标，并采集信号，信号为来自各个AP的信号值（RSSI）及MAC地址，最终经过处理，存储到数据库中作为匹配数据。每个参考点的信号记录的格式为：{（xi，yi），（MAC1，RSSIi1），（MAC2，RSSIi2）…}，通过层次聚类质心距离算法对参考点进行划分，最终得到N个簇。在线阶段，则是用户实时采集数据，预处理数据后，传输到服务器端，首先进行预匹配，计算信号与每个簇头之间的距离，找距离最短簇作为匹配范围，服务器经过对参考点利用改进贝叶斯算法计算出用户的实际位置。算法的具体流程如图1所示。
　　1.1 离线阶段层次聚类划分
　　层次聚类可以分为凝聚法和分裂法，其中凝聚法的基本思想是将每个对象均看作单独的原子簇，然后合并原子簇成为越来越大的簇，当满足某一条件时停止，分裂法则与之相反，将所有对象均置于一个簇中，然后逐渐分裂为越来越小的簇，当达到某个条件时终止。其中有四个广泛采用的簇间距离度量方法，其中|Q-Q'|代表两个对象Q和Q'之间的距离，ni是簇Ai的均值，mi是簇Ai中对象的数目。
　　最小距离（单连接算法）：
　　⑴
　　最大距离（全连接算法）： 　　⑵
　　均值距离（ML层次聚类）：
　　⑶
　　平均距离（AL层次聚类）：
　　⑷
　　本文选取均值距离ML层次聚类算法作为划分依据，选择该算法主要是因为单连接算法和全连接算法在距离度量中处于两个极端，对离群点和噪声数据过分敏感，而均值距离和平均距离属于折中办法，在最大最小距离中可以有效克服离群点的敏感问题，同时均值距离较平均距离更能衡量两个类之间的简单距离，更加贴合室内定位场景。初始时将每个元素看作一类，设置距离阈值K，将质心距离最小的两个类进行合并，当质心距离大于K则停止聚类。离线阶段的层次聚类划分共分为三个步骤。
　　⑴ 将定位区域均匀划分后，设置参考点，并在参考点采集数据，进行处理后存储。
　　⑵ 按参考点距离进行划分，首先计算参考点两两之间的欧氏距离Dij。
　　 ⑸
　　计算完成后将距离最近的点进行合并，当类的质心距离满足条件后停止合并。
　　⑶ 最终划分完之后，计算出每个簇的质心所在位置的信号强度，并存储。
　　⑹
　　其中，k表示该簇中元素的个数，RSSIin表示在i位置参考点接收来自APn的信号值。
　　1.2 改进的贝叶斯算法
　　贝叶斯算法是一种依据贝叶斯和全概率公式进行计算的一种方法，其中先验概率和后验概率是核心概念，假设待定位区域有N个参考点，每个参考点的坐标为Ni=（xi，yi），（i=1，2…，N）。指纹数据为（RSSIi1，RSSIi2，…，RSSIin），则待定位点在参考点的坐标概率为P（Ni|m），m代表待定位点的信号强度。则概率求解为：
　　 ⑺
　　其中p（Ni）为参考点出现概率，故为常量。P（m|Ni）则是参考点Ni出现m的概率，选取具有最大概率的参考点作为匹配节点。
　　由于单个的参考点考虑不合理，所以将所有点概率从大到小排列，然后选取K个最大概率的点，将其概率作为权值赋予对应的点，加权平均最终求取坐标位置。
　　综上所述，在线定位阶段的步骤为以下。
　　⑴ 首先根据离线阶段的聚类结果，将待定位区域采集的实时信号m=（RSSIi1，RSSIi2，…，RSSIin）与离线阶段聚类结果的质心信号进行欧式距离的运算，计算方法为：
　　 ⑻
　　找出与M点最近的质心所在的簇C。
　　⑵ 根据无线信号强度的区域相似性，可以表明待定位点处于C所在的子区域中，利用改进贝叶斯算法计算待定位点与C中元素概率大小，如式⑺所示，选取K个概率最大的点。
　　⑶ 将K个参考点的概率作为权值赋予其对应的坐标进行加权平均，计算公式为：
　　⑼
　　其中（x，y）为最终坐标。
　　2 实验分析及性能评估
　　2.1 实验环境和数据采集
　　为了验证该算法的定位性能，本文在贵州大学教学楼区域进行了实验，实验区域为该学院楼的第五层F5走廊区域。利用该楼现存的WLAN无线网络进行数据采集，AP具体位置未知。其中实验区域物理结构，如图2所示，利用华为手机进行信号采集，每个采样点采集信号20次，每次间隔2s，求出均值作为该位置参考信号，每个参考点间隔约3m。
　　考虑到区域实际结构和大小，采样点分布如图2所示。为了得到较好的分类效果，在聚类的过程中选取了不同的阈值T进行对比，同时将采集的实时定位数据输入进行实验（采集数据步骤将在后面介绍），实验数据如表1所示。
　　由针对实验阈值T的选取实验结果可知，当T在6、7、8、9时，定位判别准确率随着T的增大而不断提高，当T>9时，精度开始降低，从定位平均时间上看，由于采集的样本数以及定位面积的限制，时间没有明显的大变化，但是可以看出花费时间的整体趋势是不断减少的，综合考虑，此次实验中，选取T为9，即当类聚类距离为9时，停止聚类。
　　测试定位效果时候，采集定位数据的方法如下：实验者手持手机匀速走在实验区域，每隔三秒记录一次数据，共记录500次，同时记录下采集信号的坐标号，并将仿真程序运行到如下配置的PC上：处理器CORE i5，内存：2.0GB，操作系统：Windows 10，MATLAB R2014b。随机抽取手机记录的数据作为输入，进行坐标判别，重复300次，统计精度和误差。
　　2.2 实验结果及分析
　　将采集好的数据输入matlab程序中，先利用层次聚类进行划分，然后将采集好的数据依次输入到程序中，得到仿真结果，将其与传统的加权最近邻算法（WKNN）和贝叶斯算法进行比较，通过统计误差和定位时间，所得结果如表2所示。
　　经过仿真分析可知，本文提出的层次聚类贝叶斯判别算法，在实验区域进行定位实验，相比于传统贝叶斯算法和WKNN算法，判别精度有了一定的提升。这是由于改进的算法通过对多个值进行权值赋予，并且通过预匹配缩小范围，排除了不相关性的干扰。从判别时间上看，由于传统的贝叶斯算法需要对比每个参考点的信号概率值，所以计算量在三个算法中最大，消耗时间最多，而基于层次聚类的方法，只需要对比每个类的元素概率即可，大大減少了计算量，消耗时间有较大的降低。此外，传统WKNN算法虽然在时间的消耗上与传统贝叶斯方法相比减少很多，但是由于精度不够高，并且需要计算所有参考点与待定位节点信号之间的欧氏距离，定位时间也不如本文算法，故整体效果不如基于层次聚类的改进贝叶斯算法。
　　3 总结
　　为了提高定位判别正确率，以及提高定位速度，本文提出了一种基于层次聚类质心距离的聚类方法，通过计算每类质心所包含的无线信号强度与实时信号强度的欧氏距离大小，选取距离最近的类作为预匹配的结果，并在该区域内利用改进贝叶斯进行进一步判定，经过在相关区域进行实验，验证了该方法的可行性。与传统贝叶斯算法和传统WKNN算法进行了比较，结果显示，本文方法可以在一定程度上提高定位判别率，并且在定位时间方面有了很大的降低，提高了实时性。
　　本文研究的方法主要针对二维平面位置，大多数情况下不仅需要知道平面位置，还需要知道楼层号码，所以接下来，主要针对楼层判别方法进行研究。进一步的研究将对救援、根据位置提供服务、防止人员走丢等方面都有巨大的作用。
　　参考文献（References）：
　　[1] Winternitz L M B，Bamford W A，Heckler G W.A. GPSreceiver for high satellite navigation. IEEE Journal of Selected Topics in Signal Processing，2009.3（4）：541-556
　　[2] 汪伦杰，廖兴宇，潘伟杰等.基于信号均值滤波+ k-means+WKNN的Wifi指纹定位算法研究[J].微电子学与计算机，2017.34（3）：30-34
　　[3] 高仁强，张晓盼，熊艳，吴水平，晏磊.模糊数学的WiFi室内定位算法[J].测绘科学，2016.41（10）：142-148
　　[4] 李军，何星，蔡云泽，徐琴.基于K-means和Random Forest的WiFi室内定位方法[J].控制工程，2017.24（4）：787-792
　　[5] 曹晓祥，陈国良.一种改进的组合定权的指纹定位算法[J].测绘通报，2018.2：6-10
　　[6] 王怡婷，郭红.基于层次聚类的WiFi室内位置指纹定位算法[J].福州大学学报（自然科学版），2017.45（1）：8-15
转载注明来源:https://www.xzbu.com/8/view-15334446.htm