一种基于位置指纹定位的K-均值聚类算法的改进

孔港港,杨力,孙聃石,吴雨

(1.信息工程大学 导航与空天目标工程学院,郑州,450001;2.北斗导航应用技术河南省协同创新中心,郑州 450001)



一种基于位置指纹定位的K-均值聚类算法的改进

孔港港1,2,杨力1,2,孙聃石1,2,吴雨1,2

(1.信息工程大学 导航与空天目标工程学院,郑州,450001;2.北斗导航应用技术河南省协同创新中心,郑州 450001)

位置指纹定位的K-均值聚类算法将参考点分为K个子类,将相似对象聚集在一起,从而减少指纹搜索空间,提高效率。本文在K-均值聚类算法的基础上对选取的子类中邻近点进行加权计算,提高高相关性参考点的计算比重,从而达到提高定位精度的目的。实验结果表明,改进后的算法具有更高定位精度,其精度提高了18.5%。

指纹定位;K-均值聚类;加权

0 引 言

随着无线局域网基础设施的不断增加,Wi-Fi热点现在正广泛布设于商场、校园、车站等公共场所,据统计,2015年全球公共Wi-Fi热点总数已达5000万[1]。人们对Wi-Fi的研究也开始由组网能力扩展到定位应用等方面,Wi-Fi定位的定位过程可分为信号采集阶段和坐标解算阶段。而位置指纹定位方法由于其无需测距的优点成为了Wi-Fi定位中常用的方法之一,对于Wi-Fi定位的研究具有重要意义[2]。本文在位置指纹定位方法中的K-均值(K-means)聚类算法的基础上对所选子类中的邻近点加权,提升高相关点坐标所占比重,实验结果表明:改进后的算法定位精度更优,达到了预期目的。

1 K均值聚类算法

1.1 位置指纹定位原理

位置指纹定位分为离线建立指纹库和在线定位两个阶段[3]。离线阶段,在实验区域内建立二维直角坐标系,根据定位精度的要求和实验区的实际环境按照一定间隔选择L个参考点并记录坐标(xi,yi),i=1,2,…,L,并采集参考点处接收到的信号强度(RSSI)形成指纹并构建指纹库,然后采集参考点处收到的M个无线端口(AP)的RSSI样

本RSSi,1,…,RSSi,M形成该参考点处的指纹并建立指纹库,库中每个指纹表示其对应的参考点RSSI信息。在线阶段,将待测目标的RSSI信息与指纹库中参考点的RSSI信息进行匹配,取RSSI信息的欧氏距离相近的点作为坐标计算基准,进一步计算获得待测点坐标。位置指纹定位的原理如图1所示。

图1 位置指纹定位原理

1.2 位置指纹库

假设在实验区域内选择了L个参考点,参考点处可以获取M个AP的RSSI,即每个指纹包含M个RSSI值,采集所有参考点的指纹即可形成指纹库。

(1)

(2)

(3)

其中: RSSi,j表示在第i个参考点处获取的第j个AP的RSSI信息; FDi表示第i个参考点的指纹。

假设每个参考点的坐标用(x,y)表示,那么,指纹库对应的坐标信息为

(4)

1.3 K-均值聚类

K-均值聚类算法首先要对指纹库内的参考点进行分类处理,即随机选择k个参考点,每个被选参考点代表一个子类的初始中心,其余的参考点根据其与各初始中心的欧氏距离,归纳到欧氏距离最近的中心,形成k个子类。然后重新计算每个子类的新均值,不断重复该过程至其准则函数收敛[4-5]。通常采用平方误差准则,定义为

(5)

K-聚类算法流程如图2所示。

图2 K-聚类流程图

聚类完成之后,将待测点归纳到信息相接近的子类中,将子类作为一个指纹库,在子类内利用K-邻近(KNN)算法计算坐标[6-7],

(6)

式中: (xe,ye)为待测点坐标;k1为K-邻近算法选择的k值; (xi,yi)为最邻近点坐标。

2 加权K-聚类算法定位

加权K-聚类算法是在聚类完成、待测点归纳入信息相似的子类之后。将该子类中参考点信息作为一独立的数据库,在该数据库的基础上,用加权K-邻近(WKNN)算法计算坐标。

假设选取了k1个最邻近点,即:

Fp*=(Fp*1,Fp2,…,Fp*k1)T,

(7)

Fpi*=(RSSi*,1,RSSi*,2,…,RSSi*,M),

i*=1,2,…,k,

(8)

式中:Fpi*表示第i*个邻近点。

假设待测点的RSSI信息为

Fpe=(RSS1,RSS2,…,RSSM).

(9)

分别计算每个邻近点与待测点指纹信息的欧氏距离。

(10)

图3 加权K-邻近算法流程图

(11)

那么待测目标的位置计算为

(12)

式中,(xi*,yi*)表示第i*个邻近点的坐标。

计算流程如图3所示。

3 实验结果分析

为了验证改进后算法的定位效率及定位精度,选取学校某俱乐部、会议室及附属走廊31.6m×15.2m的空间,以2m×2m为间隔,选定了16×8个参考点建立数据库,参考点布设如图4所示。

图4 试验区参考点布设

图5 参考点聚类结果

根据场地实际环境,实验将K-均值聚类的k值取3,聚类结果如图5所示,聚类结果显示子类归属与空间格局具有很高相关性。

试验区域内扫描到的AP信息如表1所示,本实验选取6个AP,即每个指纹有6个RSSI信息。

表1 实验区域AP信息

以左下角点为原点建立二维直角坐标系,在试验区域内选择8个待测点,坐标如表2所示。

待测点坐标分别利用加权K-邻近(WKNN)、K-聚类(K-means)、加权K-聚类(WK-means)(最邻近点数取3)三种算法计算,定位坐标如表3所示。所耗时间及定位精度分别如图6、图7所示。其中,定位耗时在MATLAB平台下测量,MATLAB运行在联想Z470笔记本上,其硬件配置为:英特尔i5-2410M 2.3 GHz处理器,4G内存。

表2 待测点真实坐标

表3 三种定位方法计算的点坐标

图6 三种定位方法平均耗时比较

图7 三种定位方法定位误差比较

根据图6、图7可以看出:

1) 加权K-means算法与K-means算法相比,在定位耗时上分别为0.82 s和0.61 s,慢了34.4%;定位误差平均值0.53 m和0.65 m,定位精度提高了18.5%.

2) 加权K-means算法与WKNN算法相比,定位耗时分别为0.82 s和1.32 s,定位速度提高了22.7%.定位误差平均值分别为0.53 m和0.45 m,定位精度降低了17.8%.

因此,综合定位的精确度和定位速度两方面考虑,本文结合了加权的K-聚类算法在较高定位性能的基础上取得了较好的定位结果,定位效果优于单纯的WKNN算法和K-聚类算法。

4 结束语

本文在K-聚类算法的基础上,结合提高高相关性点权重的思想,提出K-聚类结合WKNN计算待测点坐标的算法,在聚类完成后、待测点归类之后,在归入的子类中用WKNN算法计算待测点坐

标。实验结果表明,改进后的算法能够在保持高效定位的基础上提高定位精度。由于场地及设备限制,实验环境较为简单并且定位结果仅是二维坐标上的定位,继续改进算法并实现三维空间上的定位是今后研究的重点。

[1] 王淑婷. 基于位置指纹的WiFi定位算法研究[D].吉林:吉林大学,2015.

[2] 孙永亮. 基于位置指纹的WLAN室内定位技术研究[D].哈尔滨:哈尔滨工业大学,2014.

[3] 张明华. 基于WLAN的室内定位技术研究[D].上海:上海交通大学,2009.

[4] 毛红文. 基于模糊聚类的位置指纹室内定位优化技术研究[D].昆明:云南大学,2014.

[5] 陈望,贾振红,覃锡忠,等. 基于改进K-means聚类算法的室内WLAN定位研究[J]. 激光杂志,2014(7):11-14.

[6] 于睿,陆南. 基于K均值聚类算法的位置指纹定位技术[J]. 信息技术,2015(10):185-188,191.

[7] 汤丽. 基于模糊聚类KNN的室内WLAN定位算法研究[D].哈尔滨:哈尔滨工业大学,2009.

Research on an Algorithm of Fingerprint Location Based on K-means and WKNN

KONG Ganggang1,2,YANG Li1,2,SUN Danshi1,2,WU Yu1,2

(1.CollegeofNavigationandAerospaceEngineering,InformationEngineeringUniversity,Zhengzhou450001,China;2.BeiDouNavigationTechnologyCollaborativeInnovationCenterofHenan,Zhengzhou450001,China)

K-mean clustering algorithm based on fingerprint is divided the reference point into K subclass. The similar objects are clustered together to reduce the search space and improve the efficiency. In this paper, we weighted the nearest neighbor of the choose subclass based on the K-means clustering algorithm. Increase the proportion of high correlation reference point while calculating, so as to achieve the purpose of improving the accuracy of location. The experimental results show that the accuracy of the new algorithm has improved 18.5 percent.

Fingerprint localization; K-means clustering; weighting

10.13442/j.gnss.1008-9268.2016.05.018

2016-03-15

P228.4

A

1008-9268(2016)05-0089-04

孔港港 (1993-),男，硕士生,主要从事导航、制导与控制研究。

杨力 (1965-),男，教授,主要从事卫星精密定轨研究。

孙聃石 (1990-),男，硕士生,主要从事WLAN室内定位研究。

吴雨 (1992-),男，硕士生,主要从事无线传感器定位研究。

联系人： 孔港港 E-mail: 1171470624@qq.com