一种改进型几何聚类指纹室内定位方法

李石荣， 符茂胜， 张峰辉， 何富贵

(皖西学院电子与信息工程学院， 安徽 六安 237012)

引 言

随着物联网技术的不断应用和发展，基于实时位置服务的需求越来越多[1]。由于GPS系统受到室内障碍物的遮挡使得其不能较好地应用于室内环境，关于室内定位技术的应用和研究成为位置服务的一大热点[2-3]。目前室内定位技术较多，其中基于WLAN的指纹定位方法由于其较低的成本和较高定位精度而得到广泛的研究和应用。基于指纹的定位方法主要分为两个阶段：离线阶段和在线阶段。离线阶段主要通过定位设备采集指纹点的信号强度和位置信息构建数据信息和位置信息之间的映射关系；在线阶段利用映射关系对定位点信号强度信息处理获取定位结果。文献[4]提出一种“动态多雷达搜索策略”自适应选取近邻K值，解决K值选取局限性；文献[5]提出了一种动态调整定位字典方法，使模型动态适应环境和接收信号强度(Received Signal Strength， RSS)变化。文献[4-5]解决了室内定位过程中环境变化、位置变化、RSS变化和K值动态选取问题，然而并未考虑指纹分布中几何位置关系。文献[6-10]分别对信号特征性问题提出了相应的解决方法。文献[6]提出了一种利用核判别和混洗蛙跳方法解决信号时变性问题，减小信号冗余和噪声；文献[7]提出了一种利用过滤选取固定的AP点的RSS进行定位；文献[8]提出了利用KPCA算法和APC算法进行特征提取和聚类减小冗余并解决非线性问题，进行分类并缩小定位范围；文献[9]提出了利用RSS统计特性克服信道干扰问题；文献[10]提出了一种基于相关向量机的非线性偏最小二乘法来解决多径效应和阴影效益问题。文献[6-10]充分考虑信号时变性对定位的影响，提出特征提取、统计分布和聚类等方法解决了信号时变性对定位的影响问题，然而并未考虑到信号时变性是信号传播过程中的固有特性，无法消除由于AP设备和复杂的环境影响而产生的部分冗余性和噪声。文献[11-15]利用SVM(Support Vector Machine)在非线性问题和高维度问题的优势，使用分类或回归算法获取定位结果，然而由于信号时变性的影响可能会产生个别定位点位置误差较大而无法及时发现产生定位误差较大的问题。文献[16-17]分别提出了一种基于几何聚类和多边形的室内定位方法，解决传统加权K最近邻算法WKNN(Weighting K-Nearest Neighbor)存在误差较大点的问题，然而其只考虑到规则的几何聚类多边形，并未考虑复杂条件下(如边界位置附近)几何聚类图形，边界位置附近的定位点误差较大。

WKNN方法是指纹定位方法中算法较简单、系统较易实现的一种室内定位方法。文献[16]通过在几何网状结构内自适应选取近邻指纹点，构建最佳多边形区域后缩小定位区域范围来提高定位精度，但该模型只考虑了网状几何结构中矩形或正方形定位结构。文献[17]提出一种对定位区域进行网格区域划分后，利用SVM多分类将位置确定在投票数最多的四边形区域内并通过WKNN进行定位，该算法并未考虑可进一步优化定位区域，且算法运算时间较长。文献[18]通过判断周围信号强度的大小筛选信号较强的前M个定位AP参与定位并计算结果，该算法并未考虑WKNN算法中K的优化，应用上具有一定的局限性。文献[4]考虑了在利用WKNN定位过程中固定K值可能存在的定位局限性，在确定没有新的不确定参数下利用 “多雷达搜索策略”确定K值获取定位结果，该算法并未考虑定位点在网格边界线上的临界情况；在实际定位过程中，由于定位点可能出现在网格区域边界位置附近，固定多边形形状和K值会降低定位效果。

为解决以上问题，本文提出了一种改进型几何聚类指纹室内定位方法。首先，利用网格分布在定位区域内确定定位指纹点几何位置并采集指纹点RSS和位置信息，利用SVM算法建立指纹RSS数据和位置之间的映射关系，构建指纹分类数据库；然后，采集定位点RSS信息并利用映射关系分类获取定位点多个近邻指纹点，计算近邻指纹点对定位点的贡献度大小，对贡献度大小进行排序，选取最佳几何聚类多边形定位区域；最后利用WKNN算法获取定位结果。实验结果表明，本文提出的方法可解决传统WKNN定位算法固定K值和固定多边形区域存在局限性以及选取近邻指纹点存在误差较大影响定位精度的问题，降低了定位误差。

1 改进型WKNN定位方法

1.1 改进型WKNN定位方法

传统指纹点分布大多数基于网格分布结构，将定位区域划分成矩形等规则的四边形区域结构中，利用算法将定位点确定在某个固定的区域中，通过WKNN算法对定位点进行定位。传统方法忽略了定位点在临界边上的情况，影响了定位精度。同时，传统WKNN算法中的K值的选取也存在较大的局限性。

为解决以上问题，提出了一种基于贡献度的改进型几何聚类定位结构。如图1所示，网格上分布圆圈为指纹点，五角星为某个定位测试点。传统WKNN定位过程中通常选取指纹点1、2和7围成的三角形区域或指纹1、2、6和7围成的四边形区域。当定位点位置靠近网格线边界位置时，固定区域和K值会引起较大定位误差。由于RSS的时变性，定位结构可能存在如图1所示几种类型的结构情况，通过计算指纹点贡献度可动态选取定位点指纹定位区域。

图1 指纹点位置与定位结构图

1.2 支持向量机

指纹点和定位点接受信号强度数据分别为D={RSS1,RSS2,…,RSSN}和RSS，位置信息L={L1,L2,…,LN}，类别yi∈{-1,1}； 构造最优线性判别函数：

g(RSS)=ωT·RSS+b

(1)

其中：ω为分类超平面垂直向量，b为构造最优分类平面常数。

为解决凸函数和非线性问题，引入拉格朗日乘子α={α1,α2,…,αN}和高斯核函数K(·)。构造拉格朗日函数：

(2)

将对偶问题转化为求极值问题：

(3)

对ω,b求偏导可得：

(4)

将对α的极大值问题转换成对偶问题：

(5)

α*为对偶问题的解，根据KKT条件可以将分类超平面转化为：

(6)

SVM可解决指纹点分类过程中高维度和非线性问题[19]。

1.3 定位贡献度计算

根据SVM分类算法获取定位点近邻指纹点，利用欧氏距离计算定位区域上的近邻指纹点对定位点的贡献度，再通过改进WKNN算法重新构建定位区域结构，计算定位结果。具体定位贡献度计算过程如下：

(1) 首先利用SVM多分类算法获取定位点M(M>6)个近邻指纹点，计算定位点RSS到所有近邻指纹点的欧氏距离，记为d1,d2,…,dM，di=|RSS-RSSi|,i=0,1,…,M。

(3) 将近邻指纹点贡献度进行排序，判断选取定位结构。主要分为以下几种情况：

(a) 当前4个近邻指纹点位置结构满足结构1～结构3时，利用结构1～结构3对定位点进行定位。

(b) 当不满足情况a时，增加近邻指纹点的选取，当选取的近邻指纹点中可组成结构1～结构3位置时，停止选取，构造结构1～结构3进行定位。

(c) 当近邻指纹点不低于6个且可构造结构4时，选取结构4定位。

(d) 对选取指纹点贡献度进行二次贡献度分配，重现获取对定位的权值。

(f) 当选取的近邻指纹点不能满足结构1～结构4几何图形时，说明定位点数据误差较大，重新采集定位点数据。

(4) 利用WKNN算法对定位点进行定位。

2 定位流程

定位流程图如图2所示：

图2 定位流程图

具体定位计算过程如下：

(1) 利用SVM获取定位点前M(M>6)个近邻指纹点，计算定位点RSS到近邻指纹点欧氏距离分别为D1,D2,…,DM。

(7)

(2) 根据指纹点欧氏距离计算对定位点的贡献度从大到小依次为W1,W2,…,WM，选取前K(3≤K≤6)个贡献度较大的指纹点并根据改进WKNN方法构建定位结构区域；

(8)

(3) 利用前K个指纹点的贡献度和位置信息，计算定位结果P。

(9)

3 实验结果分析

3.1 实验环境

为验证本文提出的改进WKNN室内定位方法的效果，在皖西学院实验实训部一楼实验室进行了实验，实验环境如图3所示。实验区域长36 m、宽18 m，指纹点之间间隔距离选取为2 m，测试点位置选取定位区域内，每次数据采集次数为30次，取平均值作为RSS指纹数据和定位数据。

图3 实验环境

3.2 实验结果分析

3.2.1 实验数据

表1和表2分别给出的一组指纹点和定位实验数据，分别有4个AP上的特征信号数据。

表1 指纹点信号强度数据(单位：dBm)

表2 定位点信号强度数据(单位：dBm)

3.2.2 不同定位方法结果对比

本文对四种基于WKNN算法的不同定位方法的结果进行了对比。定位方法分别为：

(1) 传统WKNN算法：固定K值获取定位结果。

(2) WKNN+四边形：将定位点固定在某个四边形区域中进行定位。

(3) WKNN+几何聚类：利用最佳多边形几何聚类原理动态选取多边形区域和K值。

(4) 改进WKNN算法：本文提出的利用近邻指纹点对定位的贡献度重构定位区域获取定位结果。

定位结果统计见表3，对比如图4所示。表3为一组7个定位点数据的多次数据处理定位误差统计结果。图4是利用传统WKNN算法(固定K值为4)、WKNN+四边形、WKNN+几何聚类和改进WKNN算法对定位点多次数据处理获取的平均定位误差分别为1.81 m、1.55 m、1.53 m和1.38 m左右[16-17]。

表3 定位误差累计概率统计结果

图4 定位结果对比

3.2.3 K值对定位结果的影响

本文从不同K值对传统WKNN算法和改进WKNN算法下的定位精度进行了对比。不同的K值影响的定位精度的变化如图5所示。从图5可以看到，当K值在3～6之间时，改进WKNN方法可构建最佳多边形结构定位区域，当K值超过这个范围时，定位误差较大。传统WKNN算法由于在选择K值过程中未对定位结构区域作优化处理，存在误差较大的近邻指纹点使得定位误差较大。当K值取3、4、5和6时，与传统WKNN方法相比下平均定位误差分别减小了0.57 m、0.45 m、0.56 m和0.17 m。

图5 不同K值对定位误差影响

3.2.4 边界近邻定位点测试

在网格分布临界边上选取7个定位点进行测试，经过多次反复的采集数据、处理数据和计算并获取定位结果。7个不同位置的定位点在传统WKNN算法和改进WKNN算法下定位误差的对比如图6所示。从图6可以出，当定位点在临界边附近时，传统WKNN算法定位误差较大，而本文提出的改进WKNN方法可较好地适应边界附近定位点。

图6 临界定位点定位结果对比

4 结束语

本文针对传统WKNN算法在定位过程中由于K值和定位结构区域选取过程中存在误差的问题，提出了一种改进型WKNN室内定位方法。该方法首先构建最佳多边形定位结构区域，接着利用SVM分类获取近邻指纹点并根据指纹点的贡献度大小构建最佳定位区域，最后利用WKNN算法获取定位结果。实验结果表明，本文提出的方法优于传统基于WKNN的定位方法。本文在研究过程中并未考虑定位点移动的情况，关于定位点移动条件下如何解决信号时变性的问题有待下一步研究。