陈蒙 千博

摘要：针对现有WiFi定位技术位置指纹匹配算法存在搜索空间大、WiFi信号不稳定分布导致定位误差大的问题，文章提出一种改进型位置指纹定位算法，该算法基于仿射传播聚类和改进型加权1：近邻实现。实验分析表明，该算法降低了参考点匹配数目，提升了室内定位精度。

关键词：室内定位；位置指纹：仿射传播聚类；改进型加权K近邻法

随着移动通信技术的不断发展，位置感知服务的需求日益增加，定位技术是实现位置感知的基础。GPS卫星导航定位系统无法应用于室内环境，因此需要借助其他技术手段实现室内定位。目前典型的用于室内定位的硬件设备有蓝牙、RFID、超宽带、ZigBee、传感器、LED可见光等，基于这类设备的定位系统定位成本高，在实际应用中难以普及[1-2]。由于WiFi信号广泛存在于各种建筑物中，无线接入点（AccessPoint，AP）覆盖范围广，基于WiFi的室内定位技术成为热点研究问题。

目前，在基于WiFi的室内定位技术中常用基于接收信号强度（Received Signal Strength Indication。RSSDI）的方法[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的相似度矩阵s。APC算法中在参考点间传递归属度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算法可以有效改善定位精度，同时减少参考点匹配数目，降低计算复杂度。

[参考文献]

[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