基于GAWK-means的地铁车站指纹定位方法

金 霄，吴 飞，鄢 松，陆雯霞，张忠艺

(上海工程技术大学 电子电气工程学院,上海 201620)

随着城市轨道交通的不断发展[1]，在推进智慧地铁建设时，需要将地下空间的精准定位技术作为保障来实现人员和物资设备的精准定位，以便达到降本增效的目的。蓝牙技术虽发布于1998年，但直到2013年，基于低能耗蓝牙(Bluetooth Low Energy，BLE)的iBeacon室内定位系统才开始被用于定位。随着对市场和蓝牙技术的深入了解，蓝牙技术在基于位置服务(Location Based Services，LBS)领域有着越来越多的业务使用场景[2]。

在地铁车站环境下，利用无线定位技术实现定位主要采用多边定位法和指纹匹配定位法。其中，指纹匹配法相较于多边定位法具有更好的定位精度[3-4]。在2009年，日本名古屋大学设计了一种基于WiFi技术的地铁信息指纹定位系统[5]，通过对名古屋市地下83个站点，1 777个接入点(Access Point,AP)，共28 620个采样点指纹采集，在iPod Touch终端构建了7个地铁信息应用程序为市民的生活提供服务。此外，上海地铁也利用蓝牙技术对地铁车站空间内的定位导航平台进行了初步建设[6]。指纹匹配定位法凭借其较高的定位精度，被广泛应用于室内定位领域，但是在较大空间下使用指纹匹配定位容易降低匹配效率。针对此问题，国内外学者也展开了相应的研究。文献[7]提出利用最远空间数据的最小相关性和易于收敛的特点缩短聚类时间，提高聚类效果和定位精度。文献[8]提出通过层次聚类的思想对二分K-means聚类算法进行改进，并结合变色龙算法将部分划分过细的簇合并，减小了定位误差。文献[9]研究了欧式距离加权系数对K-means算法的影响，并利用Iris数据集对提出的4种权重系数进行聚类结果的比较，证明了利用加权系数可提升算法的整体效益。

基于此，本文主要通过研究地铁环境的iBeacon指纹定位技术，针对传统K-means容易陷入局部最优的缺陷，提出基于GAWK-means的地铁车站定位方法。该方法在传统K-means的误差准则函数欧式距离部分，根据数据本身的离散程度进行权重优化使其更好地体现类内相似度。为解决聚类结果陷入局部最优的问题，本文将改进的K-means结合遗传学思想来优化聚类结果。最后，在试点地铁车站现场采集数据并进行实验，结果表明本文所提出的优化算法提高了指纹定位的精度。

1 iBeacon指纹聚类定位技术

指纹定位技术是近年来室内定位技术的研究重点。指纹法虽然不需要在信号强度和距离中建立转化模型，但需要将环境的位置与特定的指纹联系起来[10-11]。相较于WiFi技术，iBeacon技术具有低功耗、易布置、定位精度高的特点。此外，在地铁车站环境下，WiFi路由器需要独立供电，故具有一定的建设复杂性。在实际定位中，iBeacon指纹定位过程主要分为两个阶段：离线阶段和在线阶段[12-13]。离线阶段中，首先需设定坐标系，并进行网格划分设定采样点。在所有采样点中，第i个位置，测量j次来自m个接入点的接收信号强度(Received Signal Strength，RSS)，最后汇总所有RSS数据，对数据清洗并对数据预处理。在得到原始指纹库后，利用聚类算法对指纹库聚类分类。在线阶段中，需要选择适合的匹配算法将实时采集的指纹数据和欧式距离最为接近的子指纹库匹配来获取最终位置。图1为iBeacon指纹聚类匹配整体流程。

目前指纹匹配算法中使用最广的是K近邻(K-Nearest Neighbor，KNN)。KNN是模式识别统计学方法，从定位角度理解，KNN是在在线阶段采集的RSS中选择前k个欧式距离最小的位置指纹，然后计算指纹对应位置坐标的平均值，并将其作为定位结果。其中欧式距离代表在线采集RSS和指纹库中RSS向量的接近程度[14]，即

(1)

(2)

式中，(xi,yi)为第i个采样点的位置坐标；(x,y)为待定位点坐标；di为待定位点和第i个采样点的欧式距离；i=1,2,…,m；j=1,2,…,n。

2 传统K-means聚类算法

K-means聚类算法是一种无监督学习的迭代求解聚类分析算法，由于具有简洁性和高效性在工程应用中被广泛使用[15]。假设定义一个由n个数据构成的原始数据集合(p1,p2,…,pn)，每个pi为m维向量。K-means算法的目的是在给定分类组数为K的条件下，将原始数据分成K类。K值一般通过手肘方法[16]确定，并在数值模型上求平方误差准则函数E的最小值

(3)

式中，p为数据集中的对象；zi为簇Ci的均值。

其算法步骤主要由以下几部分组成：

步骤1从原始数据集合中随机取K个元素，作为K个簇各自的中心；

步骤2分别计算剩下的元素到K个簇中心的平方误差值E1，将这些元素分别划归到相异度最低的簇；

步骤3根据聚类结果，重新计算K个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数；

步骤4将数据集合中全部元素按照新的中心重新聚类，计算平方误差值E2；

步骤5若|E1-E2|≤e，则迭代结束，否则E2赋值给E1，转入步骤4；

步骤6将结果输出。

传统K-means算法在聚类过程中容易由于初始值的随机性而陷入局部最优[17]，这将导致聚类效果不准确，影响定位精度。为解决这一问题，本文接下来将对传统K-means算法进行改进。

3 遗传算法和改进的K-means算法结合

3.1 遗传算法

遗传算法(Genetic Algorithms，GA)是一种自适应全局优化搜索算法[18]。GA算法源于生物学遗传进化原理，包括生物的繁殖、交配、变异3个现象。其在搜索过程中使用适应度函数来度量群体中各个个体的优化计算中有可能达到最优解的优良程度，因此有可能会跳出局部最优解，从而达到全局最优的效果。

首先采用GA算法对数据进行编码操作，将问题解空间的可行解表示成遗传空间的基因型染色体串结构数据。串结构数据的不同组合构成了不同的可行解。接下来进行遗传迭代过程，其中遗传算法主要构成要素包括个体适应度评价函数、选择算子、交叉算子、变异算子，其中3个算子在一定的概率参数控制下产生后代，用后代群体替换双亲群体，产生新一代个体并保持数目不变。然后重新进行适应度函数计算，不断循环，直至满足终止条件。最后，解码获得最优解，代表问题获得解决。

3.2 GAWK-means算法

在离线阶段，传统K-means聚类各个采样点的指纹向量和每次聚类中心的相似程度多采用欧式距离表示。本文从不同AP的RSS数据本身角度出发，通过分析不同AP的离散程度来确定加权系数的大小，例如AP1的离散程度比AP2大，则认为AP1在聚类中起着重要作用，给予其较高的权重来调整特征空间。这样操作可以体现出较好的类内相似度，从而提高聚类效果。本文描述离散程度的指标为变异系数(Coefficient of Variation，CV)。CV为标准差与其平均数之比，不仅可以比较两组数据的离散程度，还可以消除测量尺度和量纲的影响。本文定义每个AP的加权系数为(w1,w2,…,wc)，则利用CV获得的加权系数为

(4)

式中，sj表示第j个AP对应数据对象的标准差；avr表示第j个AP对应数据对象的平均值；rssij表示第j个AP对应的第i个采样点的RSS值。

加权后的欧式距离为

(5)

式中，wj为权重系数。

由于初始聚类中心的设置是随机的，所以聚类容易陷入局部最优，于是研究人员常将全局优化算法机制引入聚类分析。本文将GA算法与改进的 K-means 算法结合，利用GA 算法的全局寻优能力来弥补 K-means 算法容易陷入局部最优的不足。本文GA优化K-means编码方式采用基于聚类划分的整数编码，适应度函数f的定义如式(6)所示。类内离散度和越小，适应度值越大。

(6)

式中，E为簇内误差平方和。

本文GAWK-means算法步骤如下：

步骤1输入聚类指纹数据集，类别数量为K，群体规模为M，交叉概率为Pc，变异概率为Pm，当前迭代次数为lcur，最大迭代次数为lmax，随机产生初始群体包含M个个体；

步骤2开始循环，lcur>lmax；

步骤3计算改进后的误差准则函数E，记录各代最优值，计算串适应度函数f；

步骤4采用轮盘赌策略进行选择操作；

步骤5以概率Pc生成一个交叉位，从中间群体随机选择两个个体，单点交叉操作，直至全被选择；

步骤6对所有个体以概率Pm对染色体中的每一位进行变异运算，生成子代群体；

步骤7再对新生成的子代群体进行评估；

步骤8保留M个个体，形成下一代群体；

步骤9更新lcur=lcur+1，若lcur>lmax则结束循环，否则返回步骤3；

步骤10将总的最优个体的染色体解码，返回给各个样本类别号；

步骤11输出最优聚类划分。

4 实验验证与分析

4.1 实验环境

本文的实验场地为上海地铁诸光路站站厅层。区域采样点分布如图2所示，其中实验区域长度为101 m，宽度为19 m。实验测试环境的AP为地铁站厅层已布置的AP，共42个iBeacon。实验中不会随意更改AP或者加入其他AP。信号采集工具为自主开发的软件，采集RSS信息的设备为华为P20。每4个小网格组成1个大网格，以大网格中心为采样点，共有289个采样点，时长为60 s，采集的频率为5 Hz，每个采样点采集到120个左右的蓝牙节点，其中包括用于指纹定位的42个iBeacon。本文对除了42个iBeacon外的其他蓝牙数据进行删除，对重复数据作均值处理，部分缺失数据统一用-99表示，以构建一个较为健壮的指纹库。在定位结果方面，为将定位结果量化，利用真实值与测量值之间的距离定义为误差，即

图2 AP站厅层付费区采样点分布

(7)

式中，(xi,yi)为测试点的实际物理位置；(x′i,y′i)为测试点的估算位置坐标。

4.2 实验结果分析

本文对站厅层289个采样点构成的指纹库利用GAWK-means算法进行聚类优化，目的是获得K个较优的子指纹库，并将提出的算法与未聚类和传统K-means算法进行定位误差比较。将实验中参数设置为M=100，lmax=800，Pc=0.8，Pm=0.2。根据肘方法对K值进行设定，根据反复实验，将KNN算法中的K值选择为4。本文中的289个采样点部分指纹信息如表1所示。

表1 采样点部分指纹信息

图3表示利用手肘法的指纹数据集K值曲线。由图可知，K值取4～6时较优。图4表示本文提出的GAWK-means优化算法在K值为5的情况下误差准则函数迭代图。优化后的簇内误差准则函数相比优化前更小，且通过实验可知在K取5时迭代效果较好，故K值取5。

图3 手肘法K值选择

图4 遗传算法优化迭代曲线

图5是K取5时，传统K-means和改进聚类算法聚类结果在二维坐标的映射。由图可以看出，本文所提算法下的聚类分布更加均衡。

(a)

图6所示为本文提出的聚类算法、传统K-means聚类算法和未聚类处理的定位误差累计概率分布图。表2所示为3种方法的匹配定位时间对比。从图6可以看出，本文提出的GAWK-means聚类的总体定位效果更好，算法整体稳定且明确。由表2可见经过聚类后的指纹匹配时间效率更高。结合定位误差累计分布概率图可直观地看出，本文提出的GAWK-means定位系统平均定位误差达到1.52 m，比传统K-means聚类和未经聚类的定位系统平均定位误差缩小了0.41 m以上，具有更优的定位精度和匹配效率。

图6 不同方法的定位误差累积概率分布图

表2 不同方法定位时间对比

5 结束语

本文在地铁环境下利用iBeacon技术进行定位。采用指纹匹配法，在离线指纹库建立阶段，提出了一种基于GAWK-means的指纹聚类方法。该方法在传统K-means的误差准则函数部分，根据数据本身的离散程度进行欧式距离权重优化来更好地体现类内相似度。为减少聚类结果陷入局部最优的情况，本文将改进K-means结合遗传算法优化聚类结果，并对聚类结果利用KNN算法进行定位评估。对比验证可知本文提出的算法定位系统的性能优于传统K-means聚类和未聚类的定位系统。GAWK-means可以有效提高在地铁空间下蓝牙指纹定位系统的定位精度和定位效率。在今后的研究中，可以通过在聚类初始点的选择上进行优化，使得指纹聚类更加合理，从而获得更优的定位效果。