基于快速K-medoids聚类的WLAN室内定位算法

陶 峥，宋 强，金许烨

（1.解放军92124部队 辽宁 大连116023；2.解放军91550部队 辽宁 大连116023；3.解放军第210医院 辽宁 大连116021）

基于快速K-medoids聚类的WLAN室内定位算法

陶 峥1，宋 强2，金许烨3

（1.解放军92124部队 辽宁 大连116023；2.解放军91550部队 辽宁 大连116023；3.解放军第210医院 辽宁 大连116021）

在WLAN位置指纹定位技术中，K-means聚类算法一直被用于离线训练阶段的参考点聚类，文中针对该法对噪声数据和孤立点数据非常敏感等缺点，采用快速K-medoids聚类算法来对定位区域内的参考点进行聚类。快速K-medoids参考点聚类算法先选取初始类中心参考点，再通过迭代方式在每一类中选取与其他位置指纹信息距离之和最小的那条位置指纹信息对应的参考点作为类中心参考点。最后通过实验数据分析表明，相比K-means参考点聚类算法，从平均误差、标准差和累积误差曲线图3个方面可以看出快速K-medoids参考点聚类算法在去除噪声数据和孤立点数据上具有更好的鲁棒性，可有效地提升定位精度。

室内定位；无线局域网；位置指纹；聚类算法；快速K中心点

随着电脑网络的兴起，用户共享诸如打印机、磁盘存储器等设备的需求随之增多。过去，这些共享需求基于有线连接，以以太网为最流行的手段，然而，自从无线连接问世以来，从方便性、可购性、移动性及生产力优势的角度分析，无线局域网（Wireless Local Area Networks，WLAN）被推到了网络应用的前列[1]。本论文聚焦WLAN其中的一项服务，就是如何在复杂多变的室内环境下对人和物进行高效定位。

位置信息在情景感知服务上有很多潜在的应用[2]。基于位置信息的情景感知服务利用客户的位置信息提供很多有用的服务，比如，当客户行走在大型公用设施或购物商场内的时候，他们的移动设备终端就可以在电子地图上显示客户的实际位置。

文中研究的对象就是基于WLAN提供一种低成本、高精度的定位系统，让设施的管理者可以向进入设施内的用户提供基于位置信息的服务。本文将研究的焦点放在位置指纹定位 （Position Fingerprint Localization）技术上。

1 位置指纹定位技术

一般来说，基本的位置指纹定位系统划分为两个阶段，离线训练阶段和在线定位阶段。在离线训练阶段，将各参考点获得来自各AP的的RSS向量作为位置指纹信息存入数据库；在在线定位阶段，利用模式匹配算法估算用户的实际物理位置信息[3-4]。该技术的具体操作步骤如下所示：

1.1 位置指纹定位离线训练阶段

1）从定位区域内的各AP上采集RSS值

首先，用户移动终端在每一个参考点从定位区域内的R个AP获取一组RSS值，将第j个参考点采集到RSS值，j=1，2，…，M，以及时间τ表示为dj（τ）=[d1，j（τ），…，dR，j（τ）]T，τ=1，…，t，t＞1，其中，di，j（τ）为j个参考点在时间点上接收到第i个AP的RSS值，t为采样时段。

2）将位置指纹信息发送至数据库

3）训 练

在离线训练阶段的最后一步，服务器根据模式匹配算法的要求将在各参考点上采集的RSS信息训练成指定的指纹格式。最终，将位置指纹信息的训练结果存入数据库。

1.2 位置指纹定位在线定位阶段

1）实时采集RSS值

当用户请求获取物理位置信息时，用户移动终端先在未知位置点[x，y]上从定位区域内的各AP采集实时RSS值。

2）将实时采样发送至服务器

服务器接收到来自用户移动终端的实时RSS信息，并将实时RSS信息训练成指定的指纹格式。

3）执行模式匹配算法

在这一步，服务器通过模式匹配算法比较用户实时的位置指纹信息和数据库中的位置指纹信息估算用户的实际物理坐标。

4）发送物理坐标信息给用户移动终端

一旦服务器完成了用户物理坐标的估算，服务器便将估算结果[x，y]T发送至用户移动终端，物理位置信息将在用户移动终端上通过可视界面显示。

2 基于快速K-medoids聚类的位置指纹定位算法

在WLAN位置指纹定位工程应用中，利用加权K近邻[5]、概率分布[6]、人工神经网络[7]等经典的模式匹配算法都可以取得良好的定位性能。但是这些算法也有明显的缺点：

加权K近邻法等模式匹配算法在在线定位阶段都需要计算待定位点位置指纹信息和所有参考点位置指纹信息之间的相似度，训练时间长短和参考点的数量成正比。因此在参考点数量众多的情况下，这些算法的运行效率就会大幅度下降，几乎失去实用性[8]。

针对这一问题，可以应用聚类算法对加权K近邻算法等模式匹配算法进行改进。以达到减小计算开销的目的。

2.1 聚类算法在指纹定位中的应用

假设定位区域内有M条位置指纹信息，定义M为不用聚类算法时的搜寻成本，K为定位区域内的位置指纹信息被划分为簇的数量，那么在在线定位阶段用户设备的平均搜寻成本如式（1）所示：

考虑到以上所述原因，很多学者提出用聚类算法来优化在线定位阶段的模式匹配算法。其中，研究最多的是K-means聚类算法。

K-means聚类算法是最简单的聚类算法之一，该聚类算法通常应用在类中心元素和其它元素都具有相同特征的情况下，这样我们就可以轻易获得两个元素之间的距离[9]。文献[10]、[11]和[12]均在离线训练阶段利用K-means聚类算法对定位区域内的位置指纹信息进行聚类。

但是K-means聚类算法在位置指纹定位领域也有自身的弊端，主要体现为利用参考点位置指纹信息均值的方法来更新类中心可能会导致定位系统对噪声数据和孤立点数据非常敏感[13-14]。

2.2 引入快速K-medoids聚类算法

为了提高定位系统的运算效率和对环境噪声的处理能力，文中创新性的将快速K-medoids聚类算法[15]引入室内定位系统中来改进K-means聚类算法的不足，定位系统分为离线训练和在线定位两个阶段。

2.2.1 离线训练阶段

在离线训练阶段，我们应用快速K-medoids聚类算法依照定位区域内各参考点的位置指纹信息对参考点进行聚类，方法如下所示：

假设在定位环境中有M个参考点，每个参考点对应其接收来自R个AP的RSS值，我们可以将M个参考点分成Koffline个簇（在聚类算法里，我们为了区分离线训练阶段的的簇数和在线定位阶段的预定位参考点数，将离线训练阶段的簇数定义为Koffline，将在线定位阶段的预定位参考点数定义为Konline。），其中Koffline的确定方法如式（2）所示：

我们利用的精确值向下取整作为簇数就能够利用聚类算法最大程度的降低在线定位阶段用户移动终端的计算负担[12]。

我们定义第j个参考点接收来自第i个AP的RSS值为dij（i=1，…，R；j=1，…，M）。欧式距离通常被用作相异度的测量，在定位环境中，参考点h和参考点j分别对应RSS向量之间的欧式距离如式（3）所示：

对定位环境中的参考点进行快速K-medoids聚类，聚类过程包含以下3个步骤：

第一步：在参考点中选择初始类中心参考点

1）在定位环境中计算每两个参考点RSS向量之间的欧式距离。

2）计算vj（参考点j），方法如式（4）所示

3）将vj按升序排列，挑选Koffline个vj值最小的参考点作为初始类中心参考点。

4）将定位环境中每一个参考点都分到与它最近的初始类中心参考点所属的类中。

5）计算每一个类中所有参考点位置指纹信息与他们类中心参考点位置指纹信息的欧式距离之和。

第二步：更新类中心参考点

在每一个类中寻找新的类中心参考点，方法是计算类中每一个参考点位置指纹信息和所有其它参考点位置指纹信息的欧式距离之和，挑选类中与其它参考点位置指纹信息之和为最小的那个参考点作为类中心参考点，并用新的类中心参考点取代原来的类中心参考点。

第三步：分配参考点至它们的类中心参考点

1）分配每一个参考点至离它们位置指纹信息最近的那个类中心参考点。

2）计算所有参考点位置指纹信息和它们类中心参考点位置指纹信息之和，如果其和不变，那么算法将会停止。否则重回第二步继续更新类中心参考点。

2.2.2 在线定位阶段

在这里我们以加权K近邻法这个最经典的模式匹配算法为例说明在线定位阶段的具体步骤，因此，整个算法可以命名为：Fast K-medoids clustered WKNN位置指纹定位算法。

第一步：划定待定位点所属的类。

定义待定位点位置指纹信息和各类中心参考点位置指纹信息的欧式距离，计算方式如式（5）所示：

其中si为待定位点用户移动终端测到第i个AP的信号强度，dij（medoids）为位置指纹库中第 j个类中心参考点接收到第i个AP的信号强度。

第二步：在待定位点所属的类中确定其物理坐标。

定义待定位点位置指纹信息和其所属类中各参考点位置指纹信息的欧式距离，计算方式如式（6）所示：

其中si为待定位点用户移动终端测到第i个AP的信号强度，dij（cluster）为待定位点所属类中第 j个参考点接收到第i个AP的信号强度。

利用Lj（cluster）搜索待定位点所属类中的每一个参考点的位置指纹信息并找到距离待定位点位置指纹信息最近的 Konline（Konline≥2）个参考点作为预定位参考点，最终结果计算方式如式（7）所示：

其中wj为预定位参考点j的权重因子，计算方式如式（8）所示：

3 实验验证

定位实验在大连创新园大厦C区2楼走廊处进行，实验区域包括1个长走廊，2个短走廊，一些办公室和实验室。该区域电器设备较多，工作日课间人员流动量较大。整个定位区域的环境示意图如图1所示。

图1 定位实验环境示意图

本次实验的目是用实验结果验证快速 K-medoids聚类算法在位置指纹定位中的应用效果。

为了实现上述目的，我们在图1中网格区域内按图2所示布置参考点，其中左下角为坐标原点，箭头所指方向即为X轴和Y轴方向，空心圆点即为定位区域内的参考点，坐标内每一个正方形方格的边长为0.6m。在定位区域内一共布置24个参考点。在离线训练阶段采样频率设置为1次/秒，在每一个参考点处采集 RSS信息，在在线定位阶段分别在（1.2，1.2）、 （2.4，1.2）、 （3.6，1.2）、 （4.8，1.2）、（6.0，1.2）、 （7.2，1.2）、 （8.4，1.2）、 （9.6，1.2）、（10.8，1.2）、（12.0，1.2）、（13.2，1.2）这11个待定位点逐一采集RSS信息。

图2 参考点布置方法示意图

按照 2.2.1和 2.2.2的方法将 Fast K-medoids clustered WKNN定位算法的得出的定位结果和K-means clustered WKNN定位算法得出的定位结果从定位精度方面比较。

定位精度方面，主要比较平均定位误差、标准差和累积分布函数，比较的结果如表1和图3所示。

表1 平均误差及标准差对比

图3 累积误差曲线对比

从表 1和图 3可以看出，相比 K-means clustered WKNN 算法，Fast K-medoids clustered WKNN算法拥有更高的定位精度。

4 结 论

快速K-medoids聚类算法和WKNN算法结合的位置指纹定位算法相比 K-means聚类算法和WKNN算法相结合的位置指纹定位算法拥有更高的定位精度，在WLAN指纹定位的中可以用快速K-medoids聚类替代K-means聚类来对参考点进行聚类，快速K-medoids聚类可以降低在线阶段算法复杂度，并拥有超越K-means聚类算法的定位精度。

[1]Crow B P，Widjaja I，Kim J G，et al.IEEE 802.11 wireless local area networks[J].Communications Magazine，IEEE，1997，35（9）:116-126.

[2]KolodziejK W， Hjelm J.Localpositioning systems:LBS applications and services[M].CRC press，2006.

[3]Wang L，Wong W C.A RSS based statistical localization algorithm in WLAN[C].Signal Processing and Communication Systems（ICSPCS），2012 6th International Conference on.IEEE，2012:1-5.

[4]Bshara M，Orguner U，Gustafsson F，et al.Fingerprinting localization in wireless networks based on received-signal-strength measurements:A case study on WiMAX networks[J].Vehicular Technology，IEEE Transactions on，2010，59（1）:283-294.

[5]Yang L，Chen H，Cui Q，et al.Probabilistic-KNN:A Novel Algorithm for Passive Indoorlocalization Scenario [C]//Vehicular Technology Conference （VTC Spring）， 2015 IEEE 81st. IEEE，2015:1-5.

[6]Kasebzadeh P，Granados G S，Lohan E S.Indoor localization via WLAN path-lossmodelsand Dempster-Shafer combining[C]//Localization and GNSS（ICL-GNSS），2014 International Conference on.IEEE，2014:1-6.

[7]Borenovi M N，Ne kovi A M.Positioning in WLAN environment by use of artificial neural networks and space partitioning [J].annals of telecommunications-annales des télécommunications，2009，64（9-10）:665-676.

[8]Ding G，Zhang J，Zhang L，et al.Overview of received signal strength based fingerprinting localization in indoor wireless LAN environments[C]// Microwave，Antenna，Propagation and EMC Technologies for Wireless Communications（MAPE），2013 IEEE 5th InternationalSymposium on. IEEE，2013:160-164.

[9]Wishart D.K-means Analysis[J]//Encyclopedia of Statistics in Behavioral Science，2005.

[10]Laoudias C，Kemppi P，Panayiotou C G.Localization using radial basis function networks and signal strength fingerprints in WLAN [C]//Global telecommunications conference，2009.GLOBECOM 2009.IEEE.IEEE，2009:1-6.

[11]Altintas B，Serif T.Improving rss-based indoor positioning algorithm via k-means clustering[C]// WirelessConference2011-SustainableWireless Technologies（European Wireless），11th European. VDE，2011:1-5.

[12]Bai S，Wu T.Analysis of K-Means algorithm on fingerprint based indoor localization system[C]// Microwave，Antenna，Propagation and EMC Technologies for Wireless Communications（MAPE），2013 IEEE 5th InternationalSymposium on. IEEE，2013:44-48.

[13]Singh S S，Chauhan N C.K-means v/s K-medoids: A Comparative Study[C]//National Conference on RecentTrendsin Engineering& Technology. 2011，13.

[14]Gullo F，Ponti G，Tagarelli A.Clustering uncertain data via k-medoids[M].Scalable Uncertainty Management.Springer Berlin Heidelberg，2008: 229-242.

[15]Park H S，Jun C H.A simple and fast algorithm for K-medoids clustering[J].Expert Systems with Applications，2009，36（2）:3336-3341.

WLAN indoor localization algorithm based on fast K-medoids clustering

TAO Zheng1，SONG Qiang2，JIN Xu-ye3
（1.PLA 92124 Unit，Dalian 116023，China；2.PLA 91550 Unit，Dalian 116023，China；3.No.210 Hospital of PLA，Dalian 116021，China）

In WLAN position fingerprint localization algorithms，K-means clustering algorithm is always used to cluster the RPs in the offline training phase.Aiming at the fact that it is very sensitive to noise and outliers，this thesis uses Fast K-medoids algorithm to cluster the RP.In the offline phase，the Fast K-medoids RP clustering algorithm selects initial medoids among the RP fingerprints first，then finds the medoid of each cluster，which is the fingerprint minimizing the total distance to other fingerprints in its cluster by using iterative method.Finally，the experiment indicates that Fast K-medoids based position fingerprint localization algorithm has greater robustness and localization accuracy than K-means based position fingerprint localization algorithm in the view of average error，STD and CDF.

indoor localization；WLAN；fingerprint；clustering；fast K-medoids

TN92

：A

：1674－6236（2017）06-0109-05

2016-03-10稿件编号：201603125

陶 峥（1984—），男，辽宁大连人，硕士，助理工程师。研究方向：通信技术。