基于边界过滤和邻域均值滤波的室内定位算法

郭昕刚， 李 航， 宫 鸿

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

基于边界过滤和邻域均值滤波的室内定位算法

郭昕刚， 李 航*， 宫 鸿

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

在构建位置指纹库时，采用过滤法剔除数据采集阶段位于边界的位置指纹点，使用邻域均值算法滤除指纹库中指纹的噪声点。将指纹库k-means聚类为合适的k个指纹类以表示相似的位置指纹点，再用加权k近邻法实现精确定位。 实验证明，相对于传统未对RSSI信号做处理的定位算法，该算法平均定位精度提高了28.9%。

位置指纹定位； 邻域均值滤波；k-means聚类； 加权k近邻

0 引 言

近年来，室内定位成为当今定位技术的主要研究方向之一[1]。室内定位已成熟运用在各种场所，如大型超市、购物商场、产品仓库以及紧急事件的救援等[2]。室内定位常用的定位方法是：基于到达时间、到达角度和WIFI位置指纹的方法[3]，而基于到达时间和到达角度的方法对测量仪器的精度要求较高，限制了定位的条件，适应程度较低[4]。WIFI位置指纹定位方法对器材要求低，普适性好，覆盖范围广，已成为应用最为广泛的室内定位方法[5]。刘志鹏[6]等在采集位置指纹信息时，对指纹库的数据做均值处理，虽然一定程度上减小了边界值对定位效果的影响，但是仍然将影响定位精度的指纹点带入实验，对定位会造成一些不可控的结果。Altintas[7]等对采集的指纹数据进行取中值处理，避免了将边界数据引入实验，但是以中值的形式来作代表性数据稳定性较差，在实验中并不适合这样做。当取大量指纹点构建指纹库时，定位阶段会消耗大量时间对指纹点进行遍历，降低了定位的效率，对指纹库进行聚类处理可以有效地提高定位效率[8-9]。传统的定位方法主要是KNN算法，默认参与定位的指纹点对定位点的贡献度相同，没有考虑指纹点的特殊性。

对于以上问题，文中通过对采样的指纹点使用过滤法进行过滤，滤除边界指纹点，再对剩余指纹点做均值处理，避免了边界点对定位的影响；指纹库构建完成之后，对指纹库进行邻域均值滤波处理，确定邻域形状和范围，滤除邻域中因环境因素造成的指纹噪声点，对指纹库进行遍历，消除所有噪声点；定位阶段应用KNN算法的思想，引入权值对参与定位的指纹点进行贡献度的判定，对于贡献度大的指纹点取较大的权值，更有利于提高定位的稳定性。

1 边界过滤和邻域均值混合滤波

1.1 边界过滤法剔除边界噪声点

在空间中自由传播信号的强度值是具有连续性的，而当接收点离信号源的距离越来越远的时候，RSSI值会服从距离的损耗模型。同样，对于AP节点发射的信号，其强度值会随距离的增加而衰减。对此，引入对数-常态分布模型来分析信号的衰减。设p0为AP节点发射的信号功率，距离AP节点dm处接收到的信号强度为RSSI，则：

式中：p(d)----经过dm后的路径损耗。

式中：P(d0)----经过d0距离后的损耗。

设在d0处的信号强度为R，则可以得到：

d0通常取单位距离1 m，x0均值为0，可以简单表示为：

R和n都是环境参数，说明RSSI值随着距离增加呈对数衰减，当指纹点距离AP较远时，这些指纹点RSSI值波动较大，甚至会影响定位精度，使用过滤法将这些对定位贡献程度较低的指纹点过滤掉。

过滤法简单描述如下：在构建指纹库前，对各指纹点采集来自各个AP的RSSI值各100次，每隔1 s采集一次。因为某些指纹点距离AP较远，信号值波动较大，甚至出现对应相同的指纹点和AP，某些时刻扫描不到其RSSI值，这就是所谓的边界值；统计每个指纹点处对应各个AP信号出现的次数，出现次数在60次以下的判定为临近边界的指纹点，计算RSSI数据出现次数在60～70次的AP平均值作为阈值；对每个指纹点采集100次RSSI值做均值处理，当RSSI均值小于阈值时，剔除该指纹点上采集的对应AP的数据。

过滤法的目的是得到最佳的定位指纹点，保证每一个指纹点接收到各个AP的RSSI值波动范围较小，为构建稳定的指纹库做好充分的准备。

1.2 邻域均值滤波滤除内部噪声点

邻域均值滤波也是对指纹点进行去噪处理，但是和过滤法不同的是邻域均值滤波是在建立了指纹库之后进行的。在建立指纹库阶段，虽然通过过滤法采集到可靠性较高的数据，但是在采集过程中难免受到一些不可控因素的影响，比如人员的走动，障碍物暂时的干扰等，这样会导致某一指纹点和周围指纹点信号强度相差较大，这就是指纹库中的噪声点，为了滤除噪声点，引入邻域均值滤波算法进行滤波处理。

邻域均值滤波一般对一个指纹点周围8或12个指纹点进行分析滤波，邻域形状取规则的轴对称形状，内部指纹点均匀分布，因为对指纹库遍历计算量较大，所以选择8邻域滤波。正方形邻域的8和12邻域分别如图1和图2所示。

图1 正方形8邻域

图2 正方形12邻域

图中黑点为中心指纹点，选取邻域的目的就是判断中心点是否为噪声。

为判断中心点是否为噪声点，这里引入信号强度相似度的概念。如果中心点为正常指纹点，则周围的邻域点与其相似度较高；若中心点为噪声点，则与邻域点的相似度较低。因此，判断指纹点是否为噪声点需要对指纹库中各指纹点的邻域进行遍历，对指纹库中一个指纹点进行判断的示意图如图3所示。

图3 指纹点噪声判断图

点越大代表接收到信号越强。AP节点的信号符合距离的损耗模型，距离越远，信号强度越低，稳定性越差，波动范围越大。图3中圈出的范围内，中心点的RSSI值明显异于其邻域内的其他指纹点，初步假设中心点为噪声点，如果中心点与其邻域的各指纹点相似度的平均值大于邻域范围内其他指纹点与各自的邻域指纹点相似度的平均值，则可以判定该中心点为噪声点。将圈出来的邻域标号，用DFc表示点Fc的邻域，用D表示包含Fc的整个区域。用R(x,y)表示x点和y点的信号相似度，Rx、Ry为x和y点处的RSSI值。

在指纹点Fc的邻域中,Fi与Fi周围的指纹点(包括Fc)相似度的和与平均值为：

在区域D中，除了中心点以外所有与其相邻点相似度的平均值为：

Fc与其邻域各点相似度的总和与平均值为：

2 k-means聚类

当指纹库中的指纹点数量较多时，定位阶段对所有指纹点进行遍历是一件很繁琐的事情，并且影响了定位的效率，文中在定位前对指纹库先做k-means聚类，将指纹点聚类为k个大类，可以先实现定位点的粗略定位，然后再与待定位点最相似的类中对指纹点进行遍历定位。这里对指纹点聚类是使用RSSI值的欧式距离来判断的，通过比较指纹点之间RSSI值欧式距离的大小来进行聚类。

2.1 k个聚类簇中心点的选取

k-means聚类中，k为聚类中心的个数，k值的选取要根据聚类数据的分布和区域来定，当k值选取不合适时，聚类会产生一定误差。选取k个聚类中心最常用的方法是选取k个距离尽量远的中心点，先随机选取一个聚类中心点，然后在指纹库中选择和这个中心点相距最远的点作为第二个中心点，同样地选取到第k个中心点。

2.2 聚类过程

假设有m个指纹点，n个AP和k个聚类中心点，建立的指纹库如下：

因为同一个AP发射的信号可能在距离很远的两个指纹点接收到的RSSI值相似，所以在聚类的过程中引入物理坐标加以辅助，避免距离较远的指纹点被分类到一起。

对于每一个指纹点进行以上遍历，直到把所有指纹点分类完成。分类完成后有k个类簇，假设第l(l≤k)个类簇中指纹点的个数为nl，则可计算新的k个聚类中心，第l个类簇的聚类中心RSSI值为：

式中：RSSIlp----第l个类簇中第p个指纹点的RSSI值，此值相当于指纹库中的一行RSSI值，仍然是一个点的指纹序列。

得到新的聚类中心后，再对每个指纹点做以上遍历，当中心点和上一次聚类中心相同，聚类趋于稳定，确定最终的聚类中心。

3 加权k近邻定位

以上滤波和聚类过程是位置指纹定位的离线阶段，在定位的在线阶段，KNN算法是被广泛使用的较为经典的算法之一。使用KNN算法来进行定位的思想是：在指纹点中选出和定位点RSSI距离最近的k个指纹点，将这k个指纹点的物理坐标取平均得到定位点坐标。文中引入加权思想，将定位点坐标进行加权处理，使定位结果更为精确。将指纹库中的RSSI值单独提取出来为：

在得到的所有di中，选取k个最小值，k个最小值对应的指纹点的坐标用于确定定位点坐标。将1/di作为权值，以确定每个指纹点对定位点定位过程的贡献程度，即与定位点RSSI值越接近的指纹点，其权值越大，参与定位的贡献度越大，这样处理更有利于提高定位精度。定位点的估算位置(x,y)如下：

式中：(xi,yi)----用于判断定位点的第i个指纹点的物理坐标。

4 实验与分析

4.1 实验环境

以长春工业大学南湖校区科研楼一楼大厅和部分教室为实验场地进行定位实验，实验区域平面图如图4所示。

在该区域内取14×12 m的范围进行指纹库的构建和定位实验。以横向为x轴，纵向为y轴，在横纵坐标每隔2 m设置一个指纹点，共56个指纹点。因为接收设备接收信号强度跟设备的朝向有关，所以在每个指纹点持智能手机按同一朝向进行RSSI采集，每个指纹点采集100次数据，每隔1 s刷新一次数据。为了提高定位准确性，对30个定位点进行定位测试。

图4 定位区域平面图

4.2 实验分析

因为k-means聚类算法和KNN算法在不同实验数据和不同实验环境下需要做适当调整，所以,文中先直接对采集的原始数据使用这两种算法进行仿真实验，得到两种算法k取值不同时的平均定位误差见表1。

表1 k-means-KNN平均定位误差表

如表1所示，在KNN算法k值取4，k-means算法k值取3时，平均定位误差较小，在后续的实验中将以相同的k值进行定位实验。实验主要验证3种算法之间的误差和区别，分析文中算法的优势。第一种是直接采用KNN算法对原始指纹库进行定位；第二种是采用混合滤波算法后再进行KNN算法定位，为了实验图表中便于表达，简称HF-KNN(Hybrid Filter WKNN)算法；第三种是利用混合滤波算法后，经过k-means聚类再进行WKNN定位，简称HFK-WKNN算法。

利用三种方法对30个定位点采集的数据进行仿真定位，定位误差如图5所示。

图5 定位误差图

从图5中可以看出，直接利用原始数据进行KNN定位时，定位误差的波动范围较大，稳定性较差，在第3、9、24号测试点处的误差值超过了5 m，定位效果不太理想，多数测试点误差在1～3 m；使用HF-KNN算法对测试点进行定位，即对原始数据先做混合滤波，定位的误差较KNN算法而言有一定幅度减小，在KNN算法波动较大的几个测试点处，定位误差明显减小。这是因为混合滤波算法剔除了指纹点中的边界值，并更正了噪声点的数据，使得在这些定位点处的误差得到一定程度的减小。但是大多数定位点误差仍然在1～3 m，总体定位效果的提高不够明显；使用HFK-WKNN算法对测试点进行定位时，整体的定位误差明显降低，多数定位点误差在2 m以内，因为HFK-WKNN算法在定位时引用了权值，将贡献度较高的指纹点坐标取更大的比重，使定位结果更加稳定精确。在某些测试点处定位误差要稍大于前面两种算法，但是该算法的总体定位稳定度明显大于前面两种算法。为了表示算法的整体定位效果，三种算法的定位平均误差和方差如图6所示。

图6 平均误差和方差图

从图6中分析得到，HFK-WKNN算法的平均定位误差较KNN和HF-KNN算法分别下降了28.9%和16.4%，定位精度有较明显的提高。并且HFK-WKNN算法的方差也是最小，定位的稳定程度也得到验证。在三种算法的定位数据中，用平均定位误差不能完全说明每种算法的优劣，因此对实验数据进行累计分析，以百分比的形式分析定位的稳定性。

累计误差概率见表2。

表2 累计误差概率表 %

累计误差表对应的累计误差概率分布如图7所示。

图7 定位累计误差概率分布

累计误差概率分布图能更直观地表现定位算法的稳定性和可靠性。HFK-WKNN算法的收敛速度明显快于其他两种算法，定位误差在2 m以内的定位点占63.3%，在3 m以内高达90%。KNN和HF-KNN算法误差在3 m以内的定位点占66.7%和76.7%，证明新算法在定位精度上较这两种算法也得到了提高，验证了该算法的可行性。

5 结 语

结合混合滤波算法、k-means聚类以及WKNN算法提出的HFK-WKNN算法在室内环境的数据中进行定位，定位效果明显优于其它两种算法，该算法的优点主要在于过滤了RSSI边界值，平滑了指纹库内部的噪声点，使粗糙的原始数据变得更为精确，对指纹库进行离线处理，减小了在线定位阶段的工作量。在定位时引入权值，得到的结果更加稳定，通过实验直观地表现了算法定位精度和稳定度的提高，验证了算法的可靠性。

[1] Bellavista P, Küpper A, Helal S. Location-based services: back to the future [J]. IEEE Pervasive Computing,2008,7(2):85-89.

[2] 王青.WiFi室内定位系统的设计与实现[D].北京:北京交通大学,2014.

[3] 徐伟.基于Android手机的室内定位技术研究与实现[D].武汉：华中师范大学,2014.

[4] 陈斌涛，刘任任，陈益强，等.动态环境中的WiFi指纹自适应室内定位方法[J].传感技术学报,2015(5):729-738.

[5] Zhang Minghua. A new positioning method for location-based services in wireless LANs [J]. Journal Electronics,2008(1):75-79.

[6] 刘志鹏,袁敏.一种基于WiFi的改进型室内位置指纹定位方法[J].计算机与现代化,2016(4):36-39.

[7] Altintas B, Serif T. Indoor location detection with a RSS-based short term memory technique (KNN-STM)[C]//International Conference on Pervasive Computing and Communications Workshops. [S.l.]: IEEE,2012:794-798.

[8] 唐洋,白勇,马跃,等.基于WiFi的指纹匹配算法在室内定位中的应用研究[J].计算机科学,2016,43(5):73-75.

[9] 孙苑莹.无线网络的移动节点定位方法研究[J].长春工业大学学报,2015,36(1):57-60.

Indoorlocationalgorithmbasedonboundaryfilterandneighborhoodmeanfilter

GUO Xingang, LI Hang*, GONG Hong

(School of Computer Science and Engineering, Changchun University of Technology, Changchun 130012， China)

To build a fingerprint database, the edge fingerprint points are removed with filter at sampling stage and the noise spots are removed with neighborhood mean filter algorithm. The dataset is classified intokfingerprint types withk-means clustering algorithm to represent the similar fingerprint points, and then precisely localized the points. Experiments indicate that the mean positioning accuracy of the algorithm increase 28.9%, being compared with the traditional location algorithm without RSSI signal processing.

fingerprint location; neighborhood mean filter;k-means cluster; weightedknearest neighbor.

Signal Strength Indication, RSSI)是至关重要的，这直接影响到定位阶段的定位精度和稳定性。基于WIFI的位置指纹定位方法分为离线采集阶段和在线定位阶段。在离线采集阶段主要任务是确定指纹库中指纹点的范围、分布形式以及采集各指纹点处接收到的AP节点发射的无线信号强度值，在线定位阶段主要是运用定位算法对采集数据进行分析并实现定位。如果对离线阶段的数据不进行滤波处理，指纹库中就会存在边界指纹点以及与周围指纹点相差较大的奇异值点。因此，文中使用改进的滤波算法----边界过滤和邻域均值混合滤波算法来对采集信号进行滤波处理，保证定位数据的准确性，以提高定位精度。

2017-08-20

吉林省科技攻关计划基金资助项目(20150204020SF)

郭昕刚(1979-)，男，汉族，吉林长春人，长春工业大学副教授,硕士，主要从事汽车电子、医疗电子方向研究,E-mail:6889068@qq.com.*通讯作者：李 航(1992-)，男，汉族，江苏淮安人，长春工业大学硕士研究生，主要从事室内定位和汽车电子方向研究,E-mail:956445025@qq.com.

10.15923/j.cnki.cn22-1382/t.2017.5.03

TP 393

A

1674-1374(2017)05-0426-07