基于K-IDPC算法的Wi-Fi室内定位方法*

何 洋, 吴 飞, 贺成成, 朱 海, 毛万葵

(1.上海工程技术大学 电子电气工程学院,上海 201620;2.上海华测导航技术股份有限公司,上海 201702)

0 引 言

由于卫星信号[1]在室内环境受到钢筋水泥等建筑掩体的遮挡等影响严重,所以,基于电磁信号的室内定位研究开始受到广泛关注。

Wi-Fi在日常生活环境中大多实现全覆盖,已经成为目前室内定位技术研究的热点之一[2]。其中被广泛关注的是基于电磁指纹库的定位方法,利用Wi-Fi电磁信号在空间中的传播与分布规律,建立特征数据库作为定位基础[3]。文献[4]提出在固定的区域范围内,定位阶段根据被搜索到的接收信号强度(received signal strength,RSS)数值的大小进行排序,筛除较小的值降低了计算量,再用K-means算法得到位置信息,但是K-means算法在定位数据集差异较大时,在误差消除阶段容易陷入局部最优,因此无法得到广泛的运用。文献[5～9]均是基于K-means算法进行室内定位,所以依然存在K-means算法固有的中心点k选取难和对异常值敏感等缺点,导致最终定位精度受到很大的影响。同时,文献[10,11]提出基于密度峰值聚类(density peak clustering,DPC)算法融合网格查寻算法来获取类中心,一定程度上解决了因为聚类中心个数k值选取不当从而导致定位结果不理想的情况,但网格搜索效率较低且依然从数据的局部分布考虑,并未用到数据之间的关联性,不适用于带有位置特性的定位数据。

本文结合K-NN算法,合理处置了离群点归属问题,并且利用关联系数解决了定位精度不高的缺陷。

1 基于Wi-Fi指纹库定位方法

基于Wi-Fi电磁指纹库的室内定位方法,主要分为离线阶段和在线阶段。离线阶段,通过对定位区域进行网格划分,采集RSS信号,创建标准化电磁指纹库,并且结合实际位置信息作为定位标签,对采集数据进行聚类处理[12]。在线阶段,对于进入定位区域内的用户采集到的电磁指纹信息和指纹库数据进行映射匹配,从而实现室内用户定位[13～17]。

2 DPC算法

DPC算法基于两种假设:1)与周围点相比聚类中心的密度最高；2)聚类中心与其他高密度区域之间有较大的距离。

假设待处理定位指纹库数据为X,规模为M×N,数据集中任意数据xi,该点的分布情况可由局部密度ρi和与其他高密度区域相对距离δi描述。

局部密度定义

(1)

式中φ(x)为分段函数,dij为数据点xi到数据点xj之间的距离,dc为截断距离,ρi可理解为在距离dij内数据点xi的个数。由于式(1)存在统计误差,所以文献[3]提出式(2)来表示局部密度

(2)

并给出截断距离dc的选择标准是每个样本点的邻居样本点的平均个数是数据集样本点的1 %～2 %[3]。

相对距离定义

(3)

图1 DPC算法

3 改进DPC算法

为了解决传统DPC算法面对大范围定位数据集,无法以较好识别度区分电磁指纹数据的聚类中心,改进后的DPC算法和之前只关注局部密度不同,本文从数据分布的整体考虑,引入关联系数来评判各数据点对当前点密度的影响。常用的做法是在高斯核函数中加入关联系数来计算局部密度,建立数据样本的全局性关系,然后再进行聚类中心的计算。并且结合K-NN的思想,针对聚类中心以外的离群点,根据K-NN的分布信息采用统计概率分配的方式对离群点进行处理。算法的具体实现步骤如下:

1)获取每个样本点xi的局部密度ρi:

改进后的DPC算法,从定位数据的整体分布考虑,密度的计算公式为

(4)

式中r为关联系数,表示密度函数与样本点之间的关联程度,r值越大则表示其余样本点离xi距离越近,对其密度ρi贡献程度越大,σ取数据样本的2 %[3]。

2)与传统密度峰值算法相同,利用式(3)计算数据点xi和其他高密度区域之间的相对距离。

3)经过步骤(1)和步骤(2)的计算可以得到局部密度值ρi和相对距离δi,再由决策图γ=ρ×δ,统计前M个最大的值,选取统计值M作为局部聚类中心。

4)根据步骤(3)选取的聚类中心,规定各聚类中心邻域内的点为中心点Xcore,其余点称为离群点,Xcore定义为

(5)

式中ε变量为邻域分隔阈值,o为类中心,um为局部类Cm中各点与类中心o的平均距离,定义为

(6)

为了将离群点正确分类,需要结合K-NN思想做进一步的处理。

5)通过计算每个离群点属于相关局部类Cm的概率进行分配。首先需要计算样本点xi和xj之间的相似度Sij

(7)

(8)

K-IDPC算法实现如下:

Input:数据集X。

Output:类别标签labels。

Initial:

关联系数r=1,近邻个数k=4。

Main:

Do:

利用式(3)和式(4)计算相对距离δi和局部密度ρi；

通过决策图γ得到聚类中心；

根据式(5)和式(6)得到中心点数组:Xcore=[xcore1,xcore2,…,xcorem]和离群点数组X’core=[x’core1,x’core2,…,x’coreN-m]；

依据式(8)并结合K近邻算法计算每个离群点所属类的概率值,存入概率矩阵Pk×M；

选取max(P[index])对应的数据点x0归为类I[o]；

更新Pk×M,P,I；

While:

P中所有值均为零

输出聚类结果

改进后的DPC算法,思路简单,没有复杂的公式计算。算法首先引入关联系数,从定位数据集样本分布整体考虑,更好地界定聚类中心,使得聚类过程更加稳定。同时结合K-NN思想针对离群点依统计概率进行所属归类,提高了算法针对密度不均的定位数据处理能力。

考虑计算机的实际运算过程,K-IDPC算法和传统的聚类算法一样,在执行运算过程是需要将数据一次性读入内存单元,无疑对运行设备的内存有较为严苛的要求。但是在实际定位场景中,每天都存在很大的数据流量,仅凭单独的聚类算法很难处理大规模的定位数据,所以在上述优化后的K-IDPC聚类方法的基础上继续优化,融合数据切割的思想,使得算法能够适应大规模的定位数据。

基于数据切割的K-IDPC算法,即将大数据集合理划分为若干小数据块,然后提取、合并每个数据块的特征元素,得到全局特征量,再对原大规模定位数据聚类。即假定大小为n的数据集D,将其分割为m个数据块,并满足

D1∪D2∪D3…∪Dm=D,Di≠Ø

(9)

Od=max(f(n1),f(n2),…,f(nm))

(10)

由于n>ni,且f(n)′>0,所以Od(n)

经由分析可知,大数据集被切割后能够减小计算开销,但是显然需要进行合理的划分。切割的过大,分割后的数据块在特征提取时会耗费更大的计算开销。同理,切割过细,那么在特征元素合并阶段也会造成极大的开销,所以,需要找到合适的切割点。数据块切割大小与聚类耗时如图2所示。

图2 不同数据规模下聚类时间与数据块大小关系

采用数据规模分别为1×103,1×104,1×105和1×106,从上图可以看到,针对不同规模的数据集的切割,其聚类时间和数据块大小的肘点值在50～80之间,所以，在数据切割时可以以此规则为参考对数据块进行划分。

4 实验验证与分析

4.1 实验设计

本次实验共采集783个Wi-Fi电磁信号组成指纹库数据,每个无线接入点(access point,AP)连续采集100组数据,采样时间间隔为1 s,以1.2 m×1.2 m为指纹库网格划分基准。其中实验所在走廊的平面图按比例如图3所示。

图3 实验区域平面图

为了便于对定位效果进行更好的分析,引入用于评判的误差函数

(11)

式中 (xtrue,ytrue)为真实位置,(xi,yi)为所测得的位置坐标,根据均方误差求得误差函数MSE。

4.2 实验分析

本实验通过本文提出的改进算法和经典的K-means、DBSCAN和DPC聚类算法进行有效对比。相关实验参数如表1所示。

表1 实验算法参数

为了更好分析上述算法对于实际应用中的效果,对获得的实验数据进行去噪、缺失值等预处理。实验表明相比于传统的K-means、DBSCAN和DPC算法,所提出的K-IDPC算法对于不同区域的定位准确率有明显的提高。

如图4定位误差分析,改进后的K-IDPC算法相比于DPC算法,加入了关联系数,从定位数据全局分布考虑,更好利用定位数据集的位置关联信息,同时结合K-NN思想,合理处理定位数据离群点,增强了定位精度。其中DPC算法和K-means算法相比,融合决策图解决了聚类中心选择问题,定位效果优于K-means算法,且与DBSCAN对比,其类中心点的选取效果更好。实验得到K-IDPC算法约91.2 %的定位误差可以控制在1.5 m左右。其他三种算法,1.5 m内定位误差概率分别48 %,57 %和66 %,明显改进后的算法定位效果最优。

图4 定位误差分析

从不同定位区域的准确率去衡量上述4种算法的性能。表2为在不同定位区域内不同算法各自的准确率,K-IDPC算法针对4个不同区域的定位指纹数据,引入关联系数,聚类中心的界定清晰合理,最高可达到97 %的定位准确率,相比于其他三种定位算法有了很大程度上的提高。

表2 不同定位区域的准确率

在定位的时效性上,本文在改进后的K-IDPC算法的基础上进一步优化,使用数据切割的方法,先提取每个小数据块的特征元素,再对这些特征元素进行聚类分析,降低了聚类算法的计算复杂度。从图5不同区域定位时间对比图可以看到,改进后的K-IDPC算法平均定位时间均在15.5 s,由图可知K-IDPC算法定位时效性最佳。

图5 不同区域定位时间对比

5 结 论

经过上述理论研究和4.2节实验分析,在实际定位场景运用中,K-IDPC算法在定位效果上明显优于同类相关算法。引入关联系数和K-NN思想,充分利用了定位数据集的全局信息,并且合理处置了离群点,大幅的提高了室内定位的精度。同时从定位时效性考量,运用数据切割的方法,将庞大的定位数据集合理分割,降低了计算开销,从宏观上来看削减了定位时间。所以,可以很好地运用到实际室内定位场景。