基于LCS/GA-WKNN算法的指纹室内定位聚类区域划分及性能评估

刘 辉，沙立成，王泽众，李 聪，樊 亮

（国网北京市电力公司，北京010000）

随着智慧城市的发展，人们获得了更优的位置服务，促进了与位置服务产业链快速拓展。考虑到建筑物会对卫星信号传输路径造成遮挡，从而引起能量损耗，因此采用卫星导航系统并不能实现对室内的精确定位[1-3]。考虑到室内区域存在广泛覆盖的Wi-Fi 局域网，因此可以利用该方式来实现室内定位的功能，从而显著降低定位成本。大量智能终端设备也被持续开发出来，大幅提升了用户覆盖率，同时针对智能终端设备集成了大量的Wi-Fi 模块。由于大部分建筑物中都设置了密集Wi-Fi 接入点，从而形成更多的RP 指纹特征维数，产生大量冗余数据，显著增加了搜索过程的复杂性[4-7]。

由于Wi-Fi 信号会产生多径效应，从而引起RSSI 值发生波动的现象，导致定位精度明显降低。由于室内环境一直发生动态变化，从而形成了不确定的噪声分布[8-11]。本文通过多尺度核主成分分析的过程提取得到定位区域内RP 指纹特征，对WKNN室内定位算法利用遗传算法进行优化处理获得目标节点位置。采用上述方法能够克服传统室内定位算法存在的限制，从而降低噪声引起的定位偏差，实现定位精度的显著提升。

1 定位架构设计

图1 给出了定位算法的具体架构，包含离线指纹数据库、指纹库区域、最长公共子序列（LCS）粗定位以及GA-WKNN 在线匹配算法[12-13]。

图1 定位算法架构图Fig.1 Location algorithm architecture

（1）建立初始离线指纹数据库。利用定位区内的RP 测试AP 的RSSI 与MAC，并通过AKF 滤波与中值滤波方式对RSSI 数据实施预处理，达到噪声去除的功能，同时记录RP 位置参数。

（2）划分离线指纹数据库。根据RSSI 值完成指纹特征向量的排序，测试了RP 间指纹特征向量与AP 序列之间的LCS 相似度，利用聚类算法完成RP 的区域划分。划分得到子区域之后，各区域按照LCS 统一指纹特征向量维数建立分区指纹的数据库。

（3）LCS 粗定位。采集目标节点指纹，再计算此节点根据RSSI 值进行排序得到的AP 序列和子区域对应的LCS 相似度，选择达到最高相似度的子区域，并跟指纹数据项保持统一维度。

（4）GA-WKNN 匹配算法。对子区域中形成的指纹特征进行分析，选择最佳尺度核主成分模型实现目标节点指纹与子区域指纹库的特征转换，从中选择稳定且具备较大区分度的指纹特征子集实施定位。利用遗传算法寻找的方式确保候选RP指纹特征线性目标节点指纹特征达到最优权值，根据该权值并利用WKNN 算法对目标节点进行预测。

2 基于遗传算法优化的WKNN 定位算法

2.1 遗传算法

GA 算法根据遗传学以及自然选择的原理，利用适应度函数对参数候选对象优劣性进行判断，从而在确定参数空间内以混合重组的方式建立多种参数组合方式，进化得到高质量后代，经过多个周期进化后直至满足预定义适应度，计算多维目标函数最大值[14]。

2.2 GA-WKNN 算法

以GA 算法作为候选RP 搜索线性表达目标节点指纹最优权值并计算目标节点的位置，以下为算法的实现步骤：

（1）根据式（1）计算出F 跟RP 之间的指纹相似度，选择k 个达到最大相似度的候选RP，对RP 按照随机初始化的方式计算权值。

（2）构建目标模型（2），通过GA 算法搜寻的方式使候选RP 指纹特征获得目标节点指纹最佳权值，以RSSI 表示目标节点对应的指纹特征向量，RSSIi表示第i 个候选RP 对应的向量。

（3）根据步骤（2）获得的权值通过式（3）计算得到目标节点所在的部位。

3 实验结果与分析

3.1 实验环境

本文在室内环境下开展测试，完成定位算法性能的评价，图2 给出了实验环境的平面布局及其区域布置结构。

图2 实验环境及参考点布局图Fig.2 Experimental environment and reference point layout

此楼层发生了人员的大量流动，同时环境呈现无规则动态改变的特征。测试过程在2.4 m×38 m 尺寸的走廊内完成，测试区面积接近90 m2。在图3 中以黑点表示间距固定的参考点，通过这些参考点组成平行四边形。为实验区构建坐标系时选择西南角作为原点，沿正东作为正方向。其中，首个参考点坐标（1，1.7），设定最后一个参考点坐标（37，1.7）。此区域中各参考点约能够检测出的10～15 个AP，各AP 都按照2.4 GHz 频段并以IEEE802.11n 模式运行，每个AP 都存在唯一SSID 以及对应的MAC 地址。

3.2 数据采集

AP 按照周期性方式进行广播，实现Wi-Fi 信息帧的发送，在信息帧中存在AP 的MAC 地址、时间戳、SSID、RSSI、通信模式等多项内容。因为RSSI存在一定的时变性，最终考虑对各参考点分别进行2 min 数据采集，保存各项信息与RP 位置坐标，以此作为原始指纹特征参数。

利用逐一测量的方式对图2 定位区域部署的RP 实施采样。本次测试的智能手机上安装了无线信号探测软件，由此实现Wi-Fi 指纹信号的采集，能够对各个信道进行扫描并可以访问AP，测试的手机型号是RedmiNote7。对各参考点分别测试2 min的时间，同时各AP 共收集60 个初始RSSI。以自适应卡尔曼滤波的方式计算RSSI 均值，再利用参考点位置坐标建立得到离线指纹库。以随机方式从实验区域选择20 个未知节点实施定位分析，分别从不同维度采用本文定位方法评价室内环境定位特性。

3.3 聚类区域划分分析

3.3.1 RP 间隔确定

图3 显示了对0.8 m～1.6 m 间距测试所得的结果。可以看到，逐渐增加RP 间距后，发生了定位误差先降低再上升的变化趋势，其中，RP 间距为1.2 m时，达到了最低平均定位误差，因此本文设定RP 间距为1.2 m。

图3 RP 间隔对定位精度的影响Fig.3 Influence of RP interval on positioning accuracy

3.3.2 子区域个数确定

利用LCS 聚类算法对离线指纹库RP 实施区域分类，设定聚类簇数k 依次为1、2、3、4 的条件再对其实施测试，图4 给出了各测试节点对应的定位误差概率密度测试结果，可以看到，当k 增大后，平均定位误差发生了先降低再上升的变化规律。其中，k为3 时，形成了与Y 轴相距很近的概率密度曲线，达到了最小平均定位误差，显著改善了控制性能，因此将实验区域划总共分成3 个子区域。

图4 子区域划分数对定位精度的影响Fig.4 Influence of sub region partition number on positioning accuracy

3.4 结果分析

以随机方式选择20 个测试点，分别以LCSGAWKNN、PCA-WKNN、WKNN、PCA-GAWKNN 算法完成定位，测试得到的定位误差见图5。

图5 定位误差图Fig.5 Positioning error diagram

从表1 中可以看到分别以最小定位误差Emin、最大定位误差Emax、误差均值AVG、标准差AVEDEV、定位时间Time 对各算法进行定位的情况。

表1 四种定位算法的性能比较Tab.1 Performance comparison of four localization algorithms

采用WKNN 算法得到的误差均值为2.44 m，以PCA-WKNN 算法得到误差均值为1.301 m，最大定位误差由3.82 m 减小至2.17 m，经分析发现采用PCA指纹特征提取模型能够提取得到精确位置指纹特征，从而降低定位结果受到噪声因素的影响，实现定位精度以及稳定性的显著提升。采用PCA-GAWKNN算法得到的误差均值是1.225 m，GAWKNN 算法是以GA 算法作为候选指纹计算得到最优权值，获得更高定位精度，同时减小了定位误差的标准差。采用LSC-GAWKNN 算法获得的误差均值是0.95 m，最大与最小定位误差分别是2.2 m 与0.37 m，总共经过0.76 s 完成定位过程，经测试发现，以LCS 聚类方法进行定位区域分类能够显著降低在线定位阶段与离线指纹空间进行匹配时的计算量，相对于PCA-GAWKNN，能够缩短约35%的定位时间。测试阶段控制相邻两个RP 距离为1.5 m，本文设计的算法估计误差区间介于0.37 m～2.35 m，其中，比例为86.6%的定位误差可以控制在1.2 m 以内。

4 结语

以随机方式从实验区域选择20 个未知节点实施定位分析，分别从不同维度采用本文定位方法评价室内环境定位特性。经过参数优化确定：RP 间距为1.2 m，子区域个数3 个是最优的。

采用PCA 指纹特征提取模型能够提取得到精确位置指纹特征，从而降低定位结果受到噪声因素的影响，实现定位精度以及稳定性的显著提升。本文设计的算法估计误差区间介于0.37 m～2.35 m，其中，比例为86.6%的定位误差可以控制在1.2 m 以内。