一种改进型WiFi位置指纹室内定位方法.docx

    一种改进型WiFi位置指纹室内定位方法    陈蒙 千博Summary：针对现有WiFi定位技术位置指纹匹配算法存在搜索空间大、WiFi信号不稳定分布导致定位误差大的问题，文章提出一种改进型位置指纹定位算法，该算法基于仿射传播聚类和改进型加权1：近邻实现实验分析表明，该算法降低了参考点匹配数目，提升了室内定位精度Key：室内定位；位置指纹：仿射传播聚类；改进型加权K近邻法随着移动通信技术的不断发展，位置感知服务的需求日益增加，定位技术是实现位置感知的基础GPS卫星导航定位系统无法应用于室内环境，因此需要借助其他技术手段实现室内定位目前典型的用于室内定位的硬件设备有蓝牙、RFID、超宽带、ZigBee、传感器、LED可见光等，基于这类设备的定位系统定位成本高，在实际应用中难以普及[1-2]由于WiFi信号广泛存在于各种建筑物中，无线接入点（AccessPoint，AP）覆盖范围广，基于WiFi的室内定位技术成为热点研究问题目前，在基于WiFi的室内定位技术中常用基于接收信号强度（Received Signal Strength IndicationRSSDI）的方法[3]，基于RSSI的方法又可分為基于RSSI测距定位和位置指纹法。

测距定位的思想是根据RSS在空间的传播损耗模型估计智能终端与AP的距离，根据三边测量方法可以计算智能终端的位置但是由于WiFi信号在室内传播存在折射、散射、多径衰落等问题，基于RSSI测距的方法难以满足实际应用中的定位精度位置指纹法被国内外很多学者研究，微软在2000年最早进行位置指纹的研究工作[4]目前，室内定位的主要目标是如何在改善定位精度的同时降低计算复杂度，现有研究表明，聚类处理位置指纹库可以达到降低计算复杂度的目的[5-7]1 定位原理1.1算法基本流程本文提出的基于仿射传播聚类和改进型WKNN位置指纹定位算法包括离线阶段和阶段离线采样阶段，使用移动设备采集某一区域己知参考点（ RespectivePoint，RP）的RSS信息，经预处理得到原始指纹库，应用仿射传播聚类优化处理位置指纹库定位阶段，移动终端在当前测试点接收到一组RSS信息，与指纹库RSS进行相似性匹配，匹配过程包括粗定位和精定位两个过程，粗定位过程确定测试点所在类指纹库，精定位过程估计出测试点最终位置1.2仿射传播聚类算法室内环境下选择M个参考点，在所有参考点处离线采样并经预处理后获取原始指纹库，用Ψ表示其中：M表示参考点个数：N表示AP个数；Rn表示移动终端在第i个参考点采样的来自第i个AP的平均信号强度；Vij表示移动终端在第i个参考点采样获取到来自第j个AP的信号强度方差；Ri=[Rn，R12，…，RiN]表示在参考点i处的平均信号强度向量；Vi=[Vi1，Vi2，…，ViN]表示在参考点i处的信号方差；向量R；和R，是任意两个参考点的平均信号强度向量，参考点i和参考点/之间的相似度函数表示为：（2）仿射传播聚类（A伍nity Propagation Clustering，APC）是由Frey等[8]提出的一种聚类算法。

聚类特征选择为M个参考点之间的相似度，M个参考点之间的相似度可以组成MXM的相似度矩阵sAPC算法中在参考点间传递归属度r（i，j）（ Responsibility）和吸引度a（i，j） （Availability）两种类型的消息，r（i，j）表示参考点j作为参考点i的聚类中心的可信程度，a（i，j）表示参考点；选择参考点j作为其聚类中心的可信程度如果r（i，j）与a（i，j）的值越大，则表明参考点j就越有可能作为聚类中心APC算法的迭代过程如下：输入相似度矩阵SM×M，由公式（2）算出参考点i和参考点j之间的相似度，s（i，j）=sim（i，j），i≠j； s（i，j）设置为矩阵SM×M的中值；更新吸引度消息：r（i，j）=s（i，j）-max{a（i，j）+s（i，j）}j≠j（3） 更新归属度消息： a（i，j）=min{o，r（j，j）+∑i≠i，jmax{0，r（i，j）}}（4） 以上两种消息在参考点之间不断迭代完成聚类中心和归属点的划分，最终完成聚类仿射传播聚类处理后的指纹库表示如下：（5）其中Rab和Vab分别表示聚类中心参考点接收到的来自第6个AP的信号强度均值和信号强度方差，1≤a≤P，1≤6≤N，聚类个数为P。

1.3粗定位策略粗定位过程用于确定测试点所在类指纹库范围，为后面的精确定位过程所用粗定位策略的实施可以缩小定位时精定位的匹配搜索范围，从而有效降低了计算的复杂度本文采用基于聚类中心的类匹配机制，根据公式（2）计算待测点RSS向量与离线指纹库φ中所有类中心RSS向量间相似度定义阂值相似度β，选择相似度大于阈值β的类中心将β定义为某一比例下最大相似度与最小相似度的线性组合，表示为： β=α·max{s（i，j）} +（l-α）-min{s（i，j）}（6） 在本文的实验中，α=0.95 根据选择的一个或多个类中心，可以确定匹配类中心的集合，以及类中心对应的类成员集合，即确定了待测点所在的类指纹库1.4改进的WKNN算法匹配算法常用的有近邻法、K近邻法（K NearestNeighborhood，KNN）和基于K近邻法改进的加权K近邻法（Weighted K Nearest Neighbo血ood，WKNN）在匹配范围内计算待测点与所有参考点的距离，选取前K个与待测点距离最近的参考点Rl=[Rj1，Rj2，…，RjN]表示在待测点j接收到的N个AP的信号强度，则待测点j与参考点i的距离一般用欧氏距离表示：（7）由于WiFi信号容易受到外界环境的干扰，信号的分布不稳定，不同位置检测到的RSS信号稳定性差异较大，导致定位阶段出现的偶然误差较大。

简单的欧式距离无法完全表征实际的空间距离，基于此，考虑加入参考点信号采样方差来表征距离在参考点改」接收到来自某-AP的信号强度方差越小，表明该AP信号越稳定，则给予当前AP对待测点到参考点距离更大的贡献度改进后的距离计算公式为：（8）式中，Vil移动终端在参考点；采样获取的来自第J个AP的信号强度方差最后通过公式（8）计算得到前K个与待测点位置距离最近的参考点，并由这K个参考点估计待测点位置，计算公式为：式中，xi为参考点的横坐标，Di为待测点到参考点i的距离，待测点的纵坐标计算公式同公式（9）2 实验结果分析为了验证本文所提算法的性能，本文选取西安电子科技大学97号楼5楼走廊作为实验区域（面积约为42X1.5 m2），整个区域可检测到的AP共79个，实验WiFi信号接收器采用VIVO X6A （Android5.0系统）实验采集2 m×0.5m的网格数据，共采集64个位置点，其中44个固定参考点，20个位置点作为待测点在每个位置点扫描所有可检测到的AP，来自每个AP的RSS值采集30组，构建原始数据库使用MATLAB软件搭建仿真实验平台实验采用累积误差分布函数、定位误差距离、定位搜索参考点数目来分析定位算法性能，分别与KNN和WKNN算法进行对比，实验结果见图1、表1、表2。

从图3可以看出，本文提出的算法的定位误差在2m以内的概率约为60%，传统的KNN和WKNN算法定位误差在2m以内的概率分别约为24%，27%从表1可以看出，本文提出的算法的平均误差和最大误差小于KNN和WKNN算法，最小定位误差距离稍大于KNN和WKNN算法从表2可以看出，KNN和WKNN算法所需搜索的参考点数目平均值、最大值、最小值均为44个，本文提出的算法平均搜索数目为16个，最大搜索数目为28个，最小搜索数目为10个，说明本文提出的算法大幅度降低了参考点搜索数目，通过减少参考点的搜索数目，达到降低定位复杂度的目的3 结语本文通过仿射传播聚类对室内定位指纹库的位置指纹进行聚类处理，以减少定位时搜索的参考点数目针对WiFi信号的时变性导致的定位阶段出现的偶然误差大的现象，在線阶段采用改进的基于参考点信号强度采样方差的WKNN算法通过实验得到以下结论：本文提出的基于仿射传播聚类和改进型WKNN算法可以有效改善定位精度，同时减少参考点匹配数目，降低计算复杂度[Reference][1]张明华基于WLAN的室内定位技术研究[D].上海：上海交通大学，2009[2]陈丽娜基于WLAN的位置指纹室内定位技术[M]北京：科学出版社，2015[3]张明华，张申生，曹健无线局域网中基于信号强度的室内定位[J].计算机科学，2007 （6）：68-71[4]BAHL P，PADMANABHAN V N.RADAR： an In-Building RF-based user location and tracking system[C].TelAviv： Nineteenth JointConference ofthe IEEE Computer and Communications Societies， 2000[5]MOUSTAFA Y， ASHOK A.The horus， location determination system[J].Wireless Networks， 2008（3）：357-374.[6]张俪文，汪云甲，王行风.仿射传播聚类在室内定位指纹库中的应用研究[J].测绘通报，2014 （12）：36-39.[7]唐笑谋，唐佳杰基于仿射传播聚类的概率分布室内定位算法[J].电信工程技术与标准化，2013（8）：62-67.[8]FREY， BRENDANJ， DELBERT D.Clustering by passing messages between data points[J].Science， 2007（ 5814）： 972-976  -全文完-。