用于WLAN室内定位的PCA聚类算法

2016-11-30杨明极刘恺怿邵丹

电信科学 2016年7期

关键词：白化定位精度指纹

杨明极，刘恺怿，邵丹

（哈尔滨理工大学测控技术与通信工程学院，黑龙江哈尔滨 150080）

用于WLAN室内定位的PCA聚类算法

杨明极，刘恺怿，邵丹

（哈尔滨理工大学测控技术与通信工程学院，黑龙江哈尔滨 150080）

在WLAN室内定位系统中，针对接收信号强度（RSS）的时变特征降低室内定位精度的问题，提出一种基于主成分分析（PCA）白化RSS的聚类算法，该算法首先对信号强度进行PCA白化处理，去除RSS信息的相关性，提高聚类中心的可靠性和合理性，然后通过K-means聚类方式对RSS信息进行聚类，能够有效地提高聚类精度，以此来提高定位精度。实验结果表明，该算法相比于没有经过PCA的传统聚类算法，能够使定位误差在2 m内的概率提高44.8%，性能更优良。

WLAN；室内定位；去相关性；主成分分析；聚类算法

1 引言

在通信技术迅速发展的今天，人们对位置的需求越来越大，无线定位服务在很多方面都有广泛的应用前景[1]。目前应用最为广泛的定位方式是GPS定位和蜂窝网定位，通常能够对室外环境有效地定位，但是对于建筑严重遮蔽的室内环境，这两种定位方式都达不到理想的效果，因此对室内定位的研究成为热门方向[2]。

当前主要研究的室内定位技术有射频识别技术、超宽带技术、ZigBee技术、红外线技术、超声波技术和WLAN技术等。这些技术中，射频识别技术对信噪比要求高，受限较严重；超宽带技术虽然定位精度高，但伴随的成本也较高，不宜普及；ZigBee技术成本较低，但是范围小，难以推广；红外线技术定位精度高，但传播距离短，易受荧光和房间灯干扰；超声波技术需要专门硬件，成本高且受非视距和多径传播影响大[3]。与这些技术相比，基于WLAN室内定位有覆盖面积大、无需额外定位设备、部署方便等优点，所以近些年对WLAN定位技术的研究越来越多[4]。

基于WLAN位置指纹的定位方法的核心是信号强度[5]。一般来说，系统的定位精度是随着可利用的AP数量的增加而提高的，但并不是随AP的增加而无限增加[6]。过多的AP数目，一方面导致RSS数据维数增加，影响解算速度，另一方面导致临近AP的RSS相关性较大[7]。从位置指纹定位技术精度和效率的影响因素入手，提出一种将指纹数据库中RSS先进行PCA去相关处理，然后采用K-means聚类算法将指纹数据库分类的技术，从而使得聚类精确度更准确，较大地提高了定位效率和精度[8]。

2 PCA聚类算法

基于WLAN的室内位置指纹定位是利用定位空间中多个AP的RSS数据来描述位置信息[9]，图1为基于 PCA聚类算法的WLAN室内定位系统架构。

该方法包括两个阶段：离线阶段和在线阶段。在离线过程中，第一步确定各个指纹的物理位置，然后在每个指纹点的位置上采集RSS数据，将位置信息和RSS信号值结合起来，形成对应的关系，该关系就是位置指纹，把位置指纹保存在数据库中，建立位置指纹数据库（radio map，RM）[10,11]。将位置指纹数据库中的RSS数据进行PCA去相关处理，然后进行K-means聚类。在线阶段，对定位终端接收到的RSS信息进行PCA去相关处理，通过最近邻（nearest neighbor，NN）法得到待测点所在的聚类类别，在该类别中用KNN算法匹配出测试点的估计位置。

2.1 PCA变换

由于当前大部分室内AP部署密集，很有可能导致相同指纹位置邻近AP的RSS信息相关性较大，导致聚类过程中出现很多相关性高的聚类中心。因此，在聚类之前，对RSS做去相关处理、提高聚类中心的可靠性是很有必要的。

PCA算法的基本原理是：根据霍特林变换在另一空间中确定一组正交向量，该正交向量可以最大限度地表现原始数据，从原来的p维空间将原始信息映射到该组正交向量形成的n（n＜p）维空间上，从而完成对数据的去相关和维数的压缩。

图1 基于PCA聚类算法的WLAN室内定位系统架构

通过PCA处理后，基本消除了Z中各数据间的相关性，保留Z中包含X的大部分信息的前n个主成分，Z′=[S1′,S2′,…,St′]T，其中，St′=(st1,st2,…,stn)，因为 n＜p，因此同时完成了对数据的压缩。

2.2 聚类算法

RM中的每个位置指纹均值通过PCA白化处理后，新样本集为

白化的K-means算法的工作流程说明如下。

步骤1 整个RM中选取k个指纹作为初始聚类中心（R1,R2,…,Rk），Rk=[rk1,rk2,…,rkn]。由于初始聚类中心的随机选择可能导致聚类过于集中或过于分散，因此在选择k个聚类中心时要尽量地在定位范围内均匀选择。

步骤2 对于除k个聚类中心之外的其他所有经过PCA白化处理的RSS均值，它们与每个聚类中心的欧式距离di为：

将它们分别分配给与其欧式距离最近的聚类。

步骤3 将所有的指纹都分配完成后，获得新的聚类，因为K-means聚类算法可能会出现空的聚类，为避免这种情况，在每次迭代过程中，将每次聚类中的全部RSS取平均值，当作新的聚类中心，该方法被称为聚类中心的抑制更新方法。

步骤4 不断重复步骤2和步骤3，直到k个聚类中心固定不变，终止迭代。

聚类过程结束，每个位置指纹都被划分至与之最近的聚类中心，每个聚类都被当做一个子区域。

2.3 匹配算法

离线定位阶段，每个聚类中心和相对应的位置指纹数据形成一个个独立的子位置指纹数据库。在线定位阶段，将测试点处获得的RSS{xi1,xi2,…,xin}做PCA去相关处理，然后与各个聚类中心进行比较分析，利用最近邻法获取待测点所在的聚类类别。

将d1,d2,…,dk从小到大进行排序，选出最近的聚类中心所在的类族作为参考点的类族。选取的类族记为{C1,C2,…,Cm}，m表示该类中带权值的位置指纹参考点的个数。

在所确定的类别中，各参考点与测试点进行算法匹配，进而利用KNN算法实现对待测点的位置估计。

步骤1 应用欧几里德距离计算测试点与聚类指纹数据集中的每个参考点{C1,C2,…,Cm}之间的距离。其中，

步骤2 对步骤1得到的{d1,d2,…,dm}由小到大进行排序，选取前k个参考点。

步骤3 对步骤2得到的k个指纹参考点的位置坐标求平均值，把得到的值作为待测点的估算位置坐标。

改进后的算法在定位阶段只需跟位置指纹库中的某个子集进行计算比较，使得KNN算法的匹配效率得到极大的提高，更能满足客户实时性的要求。

3 实验测试

3.1 实验环境建立

为了验证PCA聚类算法的有效性，在哈尔滨理工大学8公寓3楼进行实验，3楼局部平面示意如图2所示。实验采用13个CMCC信号发射器作为AP，使用联想Z460的笔记本电脑采集各AP的RSS信号值，信号采集软件为inSSIDer。实验选取了253个指纹点和 50个测试点，相邻指纹点间距为1 m，50个测试点的位置是随机选择的，每个位置能接收到来自5～7个AP的 RSS，采集30次为一组，采集2组，采集的时间间隔为2 s。定义定位误差为：

其中，(xi,yi)表示第 i个测试点的实际物理坐标，(xi′,yi′)表示第i个测试点的估算物理坐标。

3.2 结果分析

在室内传播过程中RSS不可避免地受遮挡、多径效应等影响，在同一位置上接收到AP的RSS会随时间变化存在程度不一的波动，导致距离较近的指纹点之间的RSS信号均值相近[15]。此时通过PCA白化处理数据，不仅可以解决以上问题，还将数据维度进行了压缩，增加K-means聚类算法的可靠性，同时为后面的聚类和匹配算法降低了复杂程度。在实验过程中，原始RSS数据的维数为6，经过PCA白化处理后，RSS值保留90%的主要信息，维数降为 4（n=4）。

图2 WLAN室内定位环境

首先，为了证明对RSS进行PCA白化处理有利于聚类的准确性，比较了有无经过PCA处理的K-means聚类的分块精准度，如图3所示。

图3 K-means聚类算法经PCA前后聚类精度比较

图3为聚类中心由1到8时，经过PCA处理和没有PCA处理的聚类分块精度对比。首先，信号经过PCA处理后的K-means算法在聚类精度上要高于没有经过PCA处理的信号的聚类精度。特别是当k值慢慢增大，提高得就更加明显，因为在定位范围一定时，聚类中心k值越大，则定位子区域越多，因此相邻的子区域之间RSS强度相关性越大，通过PCA变换，消除信号之间的相关性，可以较大地提升聚类精度。其次，从图3可以看出，k的取值越小，聚类的准确率越高，但是k取值过小，类内的信息相似程度低，不利于提高室内定位精度和降低计算复杂度。当k=4时，聚类的准确率达到96.9%。随着k值增大，所有PCA前后的K-means聚类算法的聚类精度都在快速下降，因为k的取值在大于5以后，k值越大，分块越多，每个类的定位子区域越小，各个类之间的相似度越大，不但会降低聚类准确率，还会降低室内定位精度。

如图4所示是当聚类中心k的取值由1取到8时对应的定位精度概率累积分布。

图4 k取不同值时系统定位精度概率累积分布

由图4可以发现，聚类算法可以提高定位精度，当聚类中心 k的取值为 2、3、4、5时都高于 k=1（无聚类）时的定位精度。但是聚类中心取值大于6时，低于无聚类时的定位精度概率，聚类算法的优势渐渐消失。其中，聚类中心k=4时，整体的定位精度高于k取其他值，虽然k=4时，定位精度小于 3 m概率不如k=5时高，但是并不影响k=4时系统定位的整体优势。实际上，k=5时累计概率最高为80.1%，k=4时累计概率为77.2%，虽然此处k=5时的概率略高于k=4时，但是由图3可知，k=5时的聚类精度概率为93.8%，明显比k=4时的聚类精度概率97.1%要低，并且k=5时在定位精度小于2 m和小于4 m处的累积概率并不高，整体考虑定位精度和聚类精度两个因素，当聚类中心值k=4时定位系统的可靠性和有效性最高。

以上分析说明，聚类中心k的取值严重影响系统的定位性能，因此为了既能提高定位精度，缩小搜索的定位范围，又能保证聚类精度和聚类有效性，将聚类中心取为4。当k=4时，比较了K-means聚类算法在RSS进行PCA处理前后的定位精度，如图5所示。

图5 最优聚类下信号PCA处理对定位精度的影响

从图5可以看出，经过PCA处理后的系统在2 m内的定位精度概率达到60.1%，比没有经过PCA的系统定位精度概率提高了44.8%；经过PCA处理处理后的聚类定位精度在3 m内的概率为77.3%，比没有经过PCA处理的定位精度概率高11.2%；在定位精度为1 m时定位精度概率也有所提高。所以，信号经过PCA白化处理后再进行聚类，能够明显提高定位精度。

为了更清晰地说明PCA的作用，图6对PCA处理前后系统定位误差的最大值、最小值、平均值和定位误差的标准方差做了对比。

由图6可发现，最大定位误差由未经过PCA的7.92 m下降到6.28 m，降了26.1%；而信号经过PCA处理后系统的平均定位误差为2.22 m，未经过PCA处理的平均误差为2.75 m，定位误差下降了23.9%，此外，PCA处理前的误差范围为0.92～7.92 m，经过PCA处理的聚类定位误差范围为0.62～6.26 m，由于定位误差范围越小，则误差与均值的偏离度越小，定位误差的标准方差由未经过PCA处理的1.86 m降至1.36 m，表明PCA算法可以降低偏离平均定位误差的程度。

图6 最优聚类下信号是否PCA的定位误差比较

4 结束语

通过对实验结果的分析可以看出，PCA能够有效地对接收信号强度去除相关性和进行维数压缩；经过PCA的K-means聚类算法比没有经过PCA的聚类算法聚类精度更高，并且当聚类中心k=4时既能保证定位精度，又能保证可靠性最高。在最优聚类情况下进行PCA处理能有效地提高定位精度，给用户带来更好的定位结果。

[1]FANG S H,LIN T N.A dynamic system approach for radio location fingerprinting in wireless local area networks[J].IEEE Transactions on Communications,2010,58(4):1020-1025.

[2]BORENOVIC M,NESKOVIC A,BUDIMIR D.Space partitioning strategies for indoor WLAN positioning with cascade-connected ANN structures[J].International Journal of Neural Systems,2011,21(1):1-15.

[3]GU Y,LO A,NIEMEGEERS I.A survey of indoor positioning systems for wireless personal networks[J].IEEE Communications Surveys and Tutorials,2009,11(1):13-32.

[4]SUN Y,LA PORTA T F,KERMANIP.A flexible privacy-enhanced location-based services system framework and practice[J].IEEE Transactions on Mobile Computing,2009,8(3):304-321.

[5]CHON M,CHA H.Life map:a smartphone-based context provider for location-based services [J].IEEE Pervasive Computing,2011,10(2):58-67.

[6]TAGASHIRA S,KANEKIYO Y,ARAKAWA Y,etal.Collaborative filtering for position estimation error correction in WLAN positioning systems [J]. IEICE Transactions on Communications,2011,94(3):649-657.

[7]SERTTHIN C,FUJIIT,OHTSUKIT,etal.Multi-band received signal strength fingerprinting based indoor location system[J].IEICE Transactions on Communications,2010,93(8):1993-2003.

[8]KUSHKI A,PLATANIOTIS K N,VENETSANOPOULOS A N.Intelligent dynamic radio tracking in indoor wireless local area networks[J].IEEE Transactions on Mobile Computing,2010,9(3):405-419.

[9]YOO J W,PARK K H.A cooperative clustering protocol for energy saving of mobile devices with WLAN and bluetooth interfaces[J].IEEE Transactions on Mobile Computing,2011,10(4):491-504.

[10]CHAVALIT K,KOMWUT W,KAMOL K.Indoor localization improvement via adaptive RSS fingerprinting database[C]//International Conference on Information Networking,Jan 28-30,2013,Bangkok,Thailand.New Jersey:IEEE Press,2013:412-416.

[11]WANG T.Novel sensor location scheme using time-of-arrival estimates[J].IET Signal Processing,2012,6(1):8-13.

PCA clustering algorithm for indoor positioning in WLAN

YANG Mingji,LIU Kaiyi,SHAO Dan
School of Measure-Control Technology and Communication Engineering,Harbin University of Science and Technology,Harbin 150080,China

In WLAN indoor location system,aiming at the problem of time-varying characteristic of

signal strength (RSS)which reduces indoor positioning accuracy,a clustering algorithm based on principal component analysis (PCA)albino RSS was put forward.The algorithm firstly treated the RSS with PCA whitening treatment to remove the correlation and improve reliability and rationality of the cluster centers.Then,K-means clustering method was used to cluster the RSS and the clustering accuracy was improved effectively,so as to improve positioning accuracy.Experimental results show that compared with the traditional clustering algorithm without PCA,probability of positioning error within 2 meters has improved 44.8%in positioning accuracy,and the performance of positioning system has been more excellent.

WLAN,indoor positioning,remove the correlation,PCA,clustering algorithm

TN929.5

10.11959/j.issn.1000-0801.2016186

2016-05-12；

2016-07-05