基于K-Means和FCM的增强型Wi-Fi指纹定位策略①

陈 英,单文杰,杨丰玉

1(南昌航空大学 软件学院,南昌 330063)

2(南昌航空大学 物联网技术研究所,南昌 330063)

基于K-Means和FCM的增强型Wi-Fi指纹定位策略①

陈 英1,2,单文杰1,杨丰玉1

1(南昌航空大学 软件学院,南昌 330063)

2(南昌航空大学 物联网技术研究所,南昌 330063)

研究了通过数据处理算法以提高Wi-Fi指纹库室内定位性能的问题.首先采集Wi-Fi指纹样本,将其放入MySQL数据库中和R工程;其次将Wi-Fi指纹库分成若干个簇,使用K-均值聚类(K-Means)和模糊C-均值聚类(FCM)对待定位的Wi-Fi指纹进行聚类分析;最后,提出增强型的聚类策略(ECS)应用于Wi-Fi指纹匹配定位中.实验结果表明,ECS较仅使用FCM算法,其定位耗时缩短约50%-80%,且定位精度上有所改善;ECS较仅使用K-Means算法,其定位精度提高约20%-40%,且定位稳定性较强并自动更新Wi-Fi指纹库.

Wi-Fi指纹;K-均值聚类;模糊C-均值聚类;增强型定位策略

随着物联网技术的发展和移动互联网的普及,无处不在的位置服务也越来越被人们需要.据诺基亚公司的数据表明,人们87%-90%的时间在室内度过.但目前室内定位还处于初级阶段,无论在定位精度、速度、鲁棒性等方面还都不能够满足日益增长的智能位置服务的需求.基于Wi-Fi指纹匹配的无线室内定位技术[1]一定程度上解决了定位精度问题,且基础设备应用广泛,成本较低,深受研究人员的关注.但由于Wi-Fi无线设备大多应用于人类活动最为频繁的室内环境,无线室内定位易受室内布局变动、无线信号的多径效应等因素影响,其无线信号具有较强的波动性,严重影响定位性能.而基于Wi-Fi指纹匹配的定位方法首先通过不同位置上多次采集Wi-Fi RSSI信号建立指纹模型,然后利用匹配算法估计待定位点的具体位置,此方法避免了有信号特征转化为距离带来的误差,故基于Wi-Fi指纹匹配的定位算法成为近年来室内定位的研究热点.

1 国内外研究现状

基于指纹匹配的无线室内定位技术[2]是利用物理空间内不同位置具有不同RSSI的特征,作为唯一识别此位置的方法,一般分为离线采样和在线定位这两个阶段.离线采样时通过采集在多个参考点(reference points,RP)的不同接入点的信号强度值,形成关于位置的指纹数据库(RSSI与位置的映射关系).在线定位阶段,采集待定位点信息,利用相关匹配算法与指纹库中指纹进行匹配计算,来估计待定位点的最佳位置的坐标点.

然而,室内环境的复杂且多变导致了信号的非视距传播,研究发现基于传播模型的定位算法精度,一般情况为10米以上,而基于指纹匹配的定位方法通过获取更多的样本信息,在80%-90%的可信区间内,其定位精度可到5-8米左右.2000年微软公司开发了基于Wi-Fi网络的RADAR定位系统[3],此系统利用Wi-Fi指纹匹配的方法,使用K-NN算法,取最近k个邻居的坐标平均值为位置估计值,并基于RSSI信号的统计特性,采用贝叶斯原理,通过计算目标位置的后验概率分布进行定位.Zhou提出了基于本地信息熵的方法来实现Wi-Fi指纹匹配定位,研究表明增加接入点,可提高定位的精度[4].王凤使用聚类的方法对射频的接收信号强度进行时间、位置、设备异构等因素进行聚类分析,并使用朴素贝叶斯模型,定位精度达4m,准确率达80%,定位速度提高50%[5].张勇提出一种SVM和加权质心相结合的算法,定位精度和准确度较高,但定位时间较长[6].王超使用KNN方法实现基于指纹匹配的室内定位,定位平均误差达3.25m[7].周瑞提出将支持向量机(SVM)分类与回归分析相结合的Wi-Fi指纹定位算法,以提高定位精度[8].田增山采用径向基函数插值的方法,利用一部分 RSS被重新测量的参考点,拟合出接收信号强度曲面,估计出邻近未知参考点 RSS值,从而更新指纹数据库[9].Joaquín针对基于距离函数、RSS值的数据表现方式以及阈值策略的Wi-Fi指纹的机器学习和专家系统进行了探讨[10].

综上所述,目前国内外学者的持续关注和深入研究运用机器学习方法来提高室内定位精度、鲁棒性、定位速度.但由于无线信号的波动性给高精度鲁棒性定位带来较大的挑战,基于Wi-Fi指纹的定位技术还需解决的核心问题包括数据的采集和数据的预处理,所以本文的主要研究内容将包括:采集和搭建基于Wi-Fi RSSI的室内定位指纹库以及设计增强型的聚类算法对Wi-Fi指纹定位库进行聚类分析,旨在使定位精度和定位速度达到平衡.

2 基于Wi-Fi指纹库的定位算法研究

2.1 研究架构

本文研究分为三个阶段,分别是Wi-Fi指纹样本采集并存储、机器学习算法应用和实验结果及定位性能分析.本文的研究架构如图1所示.

图1 架构流程图

其中Wi-Fi指纹样本采集存储阶段主要功能为Wi-Fi RSSI信息的采集,其他因素的采集和与真实物理点建立映射关系,并将数据存于wifi_location数据库中.定位阶段主要功能是使用K-Means、FCM 对Wi-Fi指纹定位库进行聚类分析,并使用自定义的匹配算法RSSMatch,对经过K-Means的待定位点进行指纹匹配,得出最佳位置估计值.实验结果及性能分析阶段主要是通过对定位结果的分析,得到定位性能各类指标,并自动更新wifi_location数据库.

2.2 样本采集及搭建数据库

数据采集的实际场景的部分平面图如图2所示.接入点(AP)覆盖广且密集,AP信号易受其他信号干扰(zigbee、蓝牙等),网络环境复杂.

如图2所示,黄色方格为Wi-Fi的AP,每层约有18个左右的AP.实验采用工具Xirrus Wi-Fi Inspector对实验场地内Wi-Fi信号的进行抓包处理,每个采样位置点进行约10-20次采样,其中每个方向按早中晚三个时间段进行3次采样,得到如表1所示数据.

图2 数据采集的实际场景的部分平面图

表1 部分Wi-Fi信息

其中“连接”为是否连接AP;SSID为AP的名称;“强度”为接收信号值,其单位为dbm.

从采集后的数据分析可知,Wi-Fi RSSI在单个位置上存在约-10dbm的数据波动和某个短时间的数据跳变现象.但长时间内在室内环境无较大变化情况下,各AP的RSSI在某位置保持相对稳定.于是将当前此地点的各AP的Wi-Fi RSSI进行保存,生成Wi-Fi _network_report.csv文件作为Wi-Fi信号原始数据.并通过wifi_location进行缺损值及非法变量进行过滤,得较完整的原始数据.

通过Node.js和Express搭建web服务.此web服务为用户提供输入当前坐标值、方向、运动速率、是否遮蔽和是否为热点路径的数据接口,并使用MySQL数据库对数据进行存储,并过滤非法数据.将Wi-Fi的_network_report.csv数据和通过web服务得到的数据加载在基于MySQL的wifi_location数据库中.使用RODBC组件,将数据库wifi_location中数据导入到R工程中,数据库数据导入R工程.

2.3 基于K-Means的定位过程

由于Wi-Fi指纹库中数据量庞大,直接使用指纹匹配算法会导致计算量激增,耗时严重,并且定位精度低.本文首先基于K-Means方法对Wi-Fi指纹库进行聚类分析,具体实现步骤为:

(1)对当前Wi-Fi指纹库提取指纹信息,包括RSSI、位置、AP名称、AP的MAC、方向、是否遮蔽等信息,加载于矩阵wifio中;

(2)使用R中K-Means算法,以欧式距离作为距离函数模型,分别选取不同的聚类数对RSSI、位置、AP名称、AP的MAC等进行聚类分析处理;

(3)比较得到不同的聚类中心,选择最优的聚类中心保存于wifidata中;

(4)使用RSSMatch算法将聚类中心与待定位点的指纹进行匹配,得到位置的估计值;

(5)与真实的位置点进行比较,评估定位性能.在定位阶段,对当前待测点的Wi-Fi RSSI和其他因素使用K-Means方法,进一步减少计算量,加快定位时间,并在聚类后,剔除部分异常数据,提高定位精度.具体实现如下:

(1)对待测点进行每0.25s采集一次样本,采集2s,共4次样本;

(2)将样本导入R工程中,进行K-Means聚类;

(3)提取各聚类中心中子集数最多的2个簇中心,作为当前此位置Wi-Fi指纹;

(4)使用自定义匹配算法RSSMatch,与Wi-Fi指纹库中的已完成的聚类中心进行匹配,估计当前位置坐标值;

(5)与该地点的真实坐标值进行比较,得出定位结果、精度误差和定位时间.

其中RSSMatch算法主要流程为:

(1)将wifidata中的RSSI进行归一化处理;

(2)将指纹库中的聚类中心、当前Wi-Fi指纹和递归步长输入,一般为0.1;

(3)通过阈值计算,分别用Wi-Fi指纹的各因素与聚类中心进行比较;

(4)得到5个及以上的位置估计点,则转(6);

(5)以步长进行递归操作,直到得到5个及以上的位置估计点;

(6)得到的位置估计点,再次进行数据过滤,得到真正的位置估计点,输出.

2.4 基于FCM的定位过程

由于K-Means存在不能发现大小差别很大的簇或非凸形状的簇,对离群点和噪声比较敏感等缺点,本文接着基于FCM算法对Wi-Fi指纹定位库进行聚类分析.具体实现步骤为:

(1)对当前Wi-Fi指纹库提取指纹信息,包括RSSI、位置、AP名称、AP的MAC、方向、是否遮蔽等信息,加载于矩阵wifio中;

(2)使用FCM算法,选择欧式距离作为距离模型,设置单一簇最大子集数,一般为100,设置初始簇数.分别选取不同的聚类数对RSSI、位置、AP名称、AP的MAC、方向等进行聚类分析处理;

(3)分别得到不同的聚类中心,并进行比较,选择最优的聚类中心保存于wifidata中;

(4)使用RSSMatch算法将聚类中心与待定位点的指纹进行匹配,得到位置的估计值;

(5)与真实的位置点进行比较,评估定位性能.

2.5 基于ECS的定位过程

实验结果表明,由于FCM在定位精度优于K-Means,但在消耗时间方面,却明显劣于K-Means.本文结合FCM和K-Means各自的优势,提出增强型的聚类算法(ECS)应用于Wi-Fi指纹匹配定位中,旨在使定位精度和定位速度达到平衡.具体实现步骤如下:

(1)对Wi-Fi指纹定位库进行K-Means分析,其中簇数Nk为300-5000,得簇中心点{Rk1,Rk2...Rkn},其中kn=Nk;

(2)对簇中心{Rk1,Rk2...Rkn}使用FCM 分析,其中簇数Nf为20-100,得簇中心{Rf1,Rf2...Rfn},其中fn=Nf;

(3)使用自定义匹配算法RSSMatch与簇中心{Rf1, Rf2...Rfn},其中fn=Nf,进行匹配,得到定位估计值,并评估定位性能.

3 实验结果分析

使用R绘制的聚类效果如图3所示.从该图可知, FCM的聚类效果要好于K-Means的聚类效果,ECS的聚类效果最佳.

图3 Wi-Fi指纹聚类中心图

当Wi-Fi指纹定位库聚类数分别为10,20,50,75, 100,150,200,300时,表2和表3分别为基于K-Means和FCM得到定位性能表.如表可知,当指纹库的聚类数为50-100时均得到较好的定位效果,定位精度和定位速度均较好.在定位精度上FCM总体优于K-Means,但消耗时间要明显劣于K-Means算法.在聚类数为75时,估计点为1个,精度误差为0.9966m,为最佳定位效果.

表2 K-Means定位性能表

表3 FCM的定位性能表

ECS的定位性能如表4所示,从该表的数据可知,随着聚类数的增加,运行时间也增加,但整体提高了定位性能.较仅使用FCM算法,ECS算法的时间缩短约50%-80%,且定位精度上有所改善;在定位精度方面,较仅使用K-Means算法,ECS算法的定位精度提高约20%-40%,且定位稳定性较强.

表4 ECS的定位性能表

为了进一步确定K-Means和FCM选取的初始最佳聚类数,本文将估计位置个数少于4,平均精度小于8.000m,最小精度小于 1.5000m,最大精度小于10.000m,进行数据整理,得到的数据如表5所示.

表5 ECS的较佳定位性能表

由表5的数据可知,在K-Means聚类数较小时,定位精度较高且定位速度较快.而FCM的聚类数一般保持在50左右,定位效果最佳.其中当K-Means的聚类数为300,FCM的聚类数为50时,估计位置个数为1个,平均精度为0.6884m,运行时间为1.38s.为了达到定位精度和定位速度的平衡,本文在结合K-Means和FCM优势的实验过程中,以K-Means为主,FCM为辅的策略,一般选择K-Means的聚类数为300-1000, FCM聚类数为50-75.这策略的平均精度可达4m以内,最小精度误差达1m以内,并且估计位置数较少,运行时间较少.

本文使用K-Means聚类数为300,FCM聚类数为75,在实际场景中,随机定位50次,验证此策略的准确性.图4为部分待定位点的定位性能表.

图4 部分待定位点的定位性能分析

由实验可知,各待定点的定位效果不尽相同,84%的定位点的平均误差小于8m,71%的定位点的最小误差小于5m,28%的定位点的平均误差小于2m,平均聚类数为1.53个.实验发现,各待定位点的定位性能与该待定位点在Wi-Fi指纹定位库中的指纹的稀疏程度有关,如果待定位点附近的指纹越密集,定位效果越好,如待定位点(-27,40)和(0,0);反之,如果待定位点附近指纹稀疏,则定位效果较差,如待定位点(-36,-82)和(10,-65).

图5 平均耗时比较

图6 定位点误差的标准方差比较

同时,在机器配置为Intel core i3 3.4G CPU和4G内存的情况下,把本文的策略和已发表算法就定位处理的平均耗时和定位点误差的标准方差进行算法的性能比较,得到如图5和图6所示的结果,从图中可以看出,相对于其它的算法,本文所提出的策略具有更有的定能性能.

4 总结

本文基于Wi-Fi指纹库,研究了基于Wi-Fi指纹匹配方法的室内定位技术.此研究提高了室内定位的精度,减少定位的时间,增强定位的稳定性,达到了预期的效果.但随着采样数据的增加,指纹库不断变化和越发庞大,使用K-Means和FCM都需要提前确定簇数,如何动态自适应选择簇数,来尽可能实现更好的聚类分析,提供可靠的位置估计值,提高定位性能,是下一阶段的研究重点.同时,如何较均匀地采集Wi-Fi指纹,以进一步提高定位性能,也是以后研究的方向.

1颜俊杰.基于Wi-Fi的室内定位技术研究[硕士学位论文].广州:华南理工大学,2013.

2其宽.基于位置指纹的无线室内定位技术研究[硕士学位论文].秦皇岛:燕山大学,2015.

3 Bahl P,Padmanabham V.RADAR:An in-buliding RF-based user location and tracking system.Institute of Electrical& Electronics Engineers Inc,2000,2:775–784

4 Zhou M,Tian Z,Xu K,Yu X,Wu H.Theoretical entropy assessment of fingerprint-based Wi-Fi localization accuracy. Expert Systems withApplications,2013,40(15):6136–6149.

5王凤.基于聚类的射频指纹定位技术研究[硕士学位论文].北京:北京邮电大学,2014.

6张勇,徐小龙,徐科宇.基于加权质心法的WLAN室内定位系统.电子测量与仪器学报,2015,29(7):1–4.

7王超.基于WLAN室内定位的分类算法研究与实现[硕士学位论文].北京:北京邮电大学,2015.

8周瑞,袁兴中,黄一鸣.基于卡尔曼滤波的WiFi-PDR融合室内定位.电子科技大学学报,2016,45(3):399–404.

9田增山,代海鹏.基于曲面拟合的 WiFi指纹数据库更新.计算机应用,2016,36(5):1192–1195.

10 Joaquín TS,Raúl M,Sergio T.Comprehensive analysis of distance and similarity measures for Wi-Fi fingerprinting indoor positioning systems.Expert Systems with Applications, 2015,42(23):9263–9278.

Enhanced Positioning Strategy Based on K-Means and FCM for Wi-Fi Fingerprint

CHEN Ying1,2,SHAN Wen-Jie1,YANG Feng-Yu1

1(School of Software,Nanchang Hangkong University,Nanchang 330063,China)
2(Internet of Things Technology Institute,Nanchang Hangkong University,Nanchang 330063,China)

The data processing algorithm is studied to improve Wi-Fi fingerprint indoor positioning performance.Firstly, Wi-Fi fingerprint samples are collected and then are put into MySQL database and R project.Secondly,the Wi-Fi fingerprint data is divided into several clusters,and the K-mean clustering(K-Means)and fuzzy C-means clustering (FCM)are used to cluster the Wi-Fi fingerprint respectively.Finally,an enhanced clustering strategy(ECS)is proposed to for Wi-Fi fingerprint matching.Experimental results show that ECS reduces the positioning time-consuming about 50%-80%than that consumed by only using FCM and the positioning accuracy is also improved;ECS improves about 20%-40%than that obtained by only using K-Means in terms of positioning accuracy and it proves positioning stability and can automatically update the Wi-Fi fingerprint database.

Wi-Fi fingerprint;K-Means;FCM;enhanced positioning strategy

江西省自然科学基金(20161BAB212034);南昌航空大学博士启动基金(EA201520009)

2016-09-01;收到修改稿时间:2016-10-12

10.15888/j.cnki.csa.005771