论文部分内容阅读
摘 要：科技的发展带动了日常生活质量的提升，给予了室内定位广阔的发展前景。由于定位过程中不同AP存在差异，造成室内定位精度差、波动大等问题，文章在原有指纹数据库匹配算法的基础上，提出一种基于AP加权的K近邻算法，利用方差加权AP结合欧氏距离进行相似度匹配。实验结果表明，该方法较经典室内定位算法，存在更高的定位精度及稳定性。
关键词：室内定位;定位精度;稳定性
中图分类号：TN92;P228.4 文獻标识码：A 文章编号：2096-4706（2020）22-0071-03
Indoor Positioning Algorithm of WKNN Based on AP Weighting
ZHONG Chen，HAN Yuchen，NING Quanke，YU Dan，XIE Shicheng
（School of Space Information and Surveying Engineering，Anhui University of Science and Technology，Huainan 232001，China）
Abstract：The development of science and technology promotes the improvement of the quality of daily life，which gives a broad development prospect for indoor positioning. Due to differences between different APs in the positioning process，problems such as poor indoor positioning accuracy and large fluctuations are caused. Based on the original fingerprint database matching algorithm，this paper proposes a K-nearest neighbor algorithm based on AP weighting，which uses variance weighted AP combined with Euclidean distance for similarity matching. Experimental results show that this method has higher positioning accuracy and stability than the classical indoor positioning algorithm.
Keywords：indoor positioning;positioning accuracy;stability
0 引 言
如今，以GPS为主的室外定位技术已基本成熟且适用性极高，其定位精度可达米级，仅仅依靠随身携带的移动设备就可以满足人们出行游玩方面的需求。随着经济水平的不断提高，一些企业的建筑规模愈发庞大。在某些车间中，人们需要对贵重的设备及工作人员进行规划管理;在医院、幼儿园等特殊场所同样需要对重点人群进行轨迹定位。这使得人们对室内定位服务的需求更加迫切[1]。早在1996年，室内定位技术就被美国联邦通信委员会所提出，至今仍是众多学者的研究热点。室内定位的高精度实现相比室外定位而言更加复杂，首先GNSS信号很难通过墙体等障碍物传递到室内，因此需要利用室内的物理设备以及其他的信号介质途径进行定位，这种技术也被称为局域室内定位技术。其中包含Wi-Fi技术、蓝牙技术、紫蜂技术、超宽带技术、惯性单元技术、超声波定位技术、射频识别技术、地磁定位技术、可见光定位技术、红外线定位技术等[2]。其次，信号在室内传播过程中极易受到人群流动、金属物品等干扰，导致稳定性受到影响。而且参与室内定位的设备成本、普及性及损耗程度在研究过程中均需考虑。因此在上述局域室内定位技术中，Wi-Fi室内定位技术因其精度较高，覆盖面较大，使用广泛且成本较低等倍受关注，同样在智慧城市建设、商场消费引导等方面也有着极大的应用前景[3]。
Wi-Fi室内定位方法主要有两种：利用无线传播模型定位技术和指纹库匹配定位技术。在无线传播模型方法中，通过信号达到时间（TOA）、信号到达时间差（TDOA）、信号达到角（AOA）等模型估计AP和移动台之间的距离。虽然这种方法有助于距离估计，但由于Wi-Fi信号容易受周围环境的影响，相关参数波动较大而无法提供准确的定位。相比之下，指纹库匹配定位技术具有无需考虑接入点（Access Point，AP）位置无需计算视距、受信号强度（Received Signal Strength，RSS）波动影响小、容错率高等优点，定位精度甚至比无线传播模型定位技术高。
本文以安徽理工大学空间信息与测绘工程学院为分析案例，通过对比当前主要的室内定位方法，初步讨论了基于AP加权K近邻算法的实用性及稳定性，对室内定位研究进行展望。
1 传统室内定位算法
5G技术发展逐渐成熟、卫星导航定位系统组网成功以及Wi-Fi硬件的更新换代使得室内定位服务精度需求得以实现。从21世纪初期指纹数据库匹配技术初步应用于Wi-Fi室内定位至今，指纹数据库匹配定位技术一直是研究的热点，具有低成本、高精度、良好的穿透力等优点。
指纹数据库匹配定位技术[4]包括两个阶段：离线数据库建立阶段和在线数据定位阶段。离线数据库建立阶段，实验区域进行网格划分构建位置坐标，在每一个坐标点进行RSS采集并进行预处理，筛除波动较大的RSS，将位置坐标和多个AP的RSS组成有序向量作为参考点存储入数据库;在线数据定位阶段，定位目标通过仪器实时采集RSS，采用匹配算法与数据库中参考点数据进行相似度匹配，再将匹配点通过均值、加权等方法计算定位目标的实际位置。 加权K近邻算（WKNN）法是由最早的最近邻定位（NN）算法到K近邻（KNN）算法一步步演变来的，一般以欧氏距离作为RSS向量间相似度的比较，决定指纹库匹配点的位置[5]。欧氏距离常用来表示两向量之间的绝对距离。两向量之间的欧氏距离如式（1）所示：
其中，A1（x1，x2，…，xn）和A2（y1，y2，…，yn）为两向量，d为欧氏距离。
在指纹数据库离线匹配阶段，若在定位区域布设i个参考点并通过设备采集每一个参考点的RSS值，将RSS值与位置坐标组成指纹存储入指纹库中，构建完成所需指纹库。
若使用欧式距离表示待测点与i个参考点之间的相似度，则式（1）改为式（2）：
其中，di为待测点与第i个参考点之间的欧氏距离，Rij为定位区域中第i个参考点上采集的第j个AP的RSS值;Sj为待测点上采集的第j个AP的RSS值;n为定位区域内所有的AP个数。
在指纹数据库匹配在线阶段，典型WKNN算法中欧氏距离通过计算待测点与指纹库中每个参考点的距离，距离越近表示两点相似度越明显，利用距离大小排序，选择距离最小参考点，此方法称为NN算法，只能描述出待测点大致位置，无法真正表示点的实际位置坐标[6]。
由于距离相当于相似度，若取K（K≥2）个参考点作为预定位点，求取多个预定位点位置坐标的平均作为待测点的实际位置坐标，则此方法称为KNN算法，相对NN算法精度较高，选取K个参考点进行定位。计算方法如式（3）所示：
其中，（x，y）为KNN算法的定位坐标，（xi，yi）为第i个参考点的实际位置坐标。
KNN算法仍然不能满足室内定位精度要求，考虑到不同参考点对待测点位置预测的贡献程度不同，给予K个参考点位置坐标不同的权值即可获得精度更高的预测坐标，此方法称为WKNN算法，WKNN算法计算簡单，是指纹数据库匹配中的常用算法，计算方法如式（4）所示：
其中，ωi为预定位参考点的第i个权值，ω的数值根据参考点与待测点之间的欧氏距离大小变化而变化，是决定待测点定位精度的重要参数。计算方法如式（5）所示：
若ωi的数值为 ，即为K近邻方法。传统室内定位仅仅考虑到不同参考点对待测点的影响，并没有考虑到数据源对定位结果的影响。
2 改进室内定位算法
室内定位中不同AP传输信号稳定性不同，造成定位精度并不准确，不可以统一权值进行计算相似度。利用不同AP差异性进行距离加权，使不同AP对定位的贡献程度不同，提升定位精度及稳定性[7]。
在上述传统WKNN算法基础上，在同一点采集多次数据，计算每个AP的方差，匹配点的相似度利用方差表示，如式（6）所示：
其中，σj为第j个AP采集RSS的方差;t为在同一点采集RSS值的次数;rj（k）为第j个AP采集的第k个RSS值; 为在同一点采集第j个AP所有RSS的平均值。从而计算AP加权值vj和距离相似度Di，求取待测点位置坐标：
3 实验分析
选取安徽理工大学空间信息与测绘工程学院二层某一教室进行实验验证。该定位区域面积约为20 m×20 m，教室内有隔墙、桌椅以箱子等干扰因素。此楼层设置4个采用TP-Link型号热点的AP点并用小米手机进行信号采集。
首先对实验区域进行网格划分，离线阶段对所有参考点进行采集并记录相关位置坐标，建立指纹数据库，并在中心某一点多次采集，为后期AP加权提供数据基础;在线阶段把待测点RSS用欧氏距离进行加权表示相似度，再用WKNN算法求解位置坐标，将解算坐标与实际坐标运算得出误差值，分析累计误差分布。实验操作流程如图1所示。
由表1可得，基于AP加权的WKNN算法相较于传统的WKNN算法平均定位误差由3.1 m减小到了2.9 m，提升了5.2%;最大定位误差由9.3 m减小到8.5 m，提升了8.9%;最小定位误差由0.14 m减小到0.11 m，提升了21.9%。定位精度明显由于传统的WKNN算法。
图2表示的是改进后的算法与WKNN、KNN算法之间定位累积概率误差。由图可得，基于AP加权的WKNN算法在定位误差概率分布上均优于WKNN算法且误差80%在4 m以内，定位的稳定性明显优于传统室内定位算法。
4 结 论
分析了室内定位指纹匹配阶段存在的各种问题，进而提出一种基于AP加权的WKNN算法来提升室内定位精度。将AP差异性利用方差进行表示并作为权值加入定位算法的相似度计算中，有效的解决了AP不同而造成的衡量指标的差异。实验表示，该方法提高了定位精度和指纹匹配的稳定性，且易实现具有一定的实用价值。
但是，基于指纹库匹配的室内定位仍需改进。数据方面，信道状态信息相对于信号强度更稳定，但是适用于信道状态信息的装置仍未普及;KNN算法中，K值仍然需要调试，无法进行算法自适应，达不到最高精度;预处理阶段，参考点信号波动引起误差，进行粗差处理后重组数据，可明显提高定位稳定性。这些问题都是今后值得研究的方向。
参考文献：
[1] 陈空，宋春雷，陈家斌，等.基于改进WKNN的位置指纹室内定位算法 [J].导航定位与授时，2016（4）：58-64.
[2] 李新春，王欢.基于稀疏指纹采集和改进WKNN的定位算法 [J].重庆邮电大学学报（自然科学版），2019，31（4）：451-459.
[3] 吴虹，王国萍，彭鸿钊，等.一种基于KNN的室内位置指纹定位算法 [J].南开大学学报（自然科学版），2020，53（6）：5-9.
[4] 毕京学，汪云甲，纪冬华，等.RSS最小值动态补偿的室内WKNN指纹定位方法 [J].测绘科学，2020，45（12）：22-27.
[5] 朱正伟，蒋威，张贵玲，等.基于RSSI的室内WiFi定位算法 [J].计算机工程与设计，2020，41（10）：2958-2962.
[6] 康晓非，李梦梦，乔威.基于WiFi指纹的高精度室内定位融合算法 [J].西安科技大学学报，2020，40（3）：470-476.
[7] 党小超，马平川，郝占军.基于CSI的改进KNN室内定位方法 [J].传感器与微系统，2019（10）：51-53.
作者简介：仲臣（1997—），男，汉族，安徽马鞍山人，硕士在读，研究方向：室内定位。
关键词：室内定位;定位精度;稳定性
中图分类号：TN92;P228.4 文獻标识码：A 文章编号：2096-4706（2020）22-0071-03
Indoor Positioning Algorithm of WKNN Based on AP Weighting
ZHONG Chen，HAN Yuchen，NING Quanke，YU Dan，XIE Shicheng
（School of Space Information and Surveying Engineering，Anhui University of Science and Technology，Huainan 232001，China）
Abstract：The development of science and technology promotes the improvement of the quality of daily life，which gives a broad development prospect for indoor positioning. Due to differences between different APs in the positioning process，problems such as poor indoor positioning accuracy and large fluctuations are caused. Based on the original fingerprint database matching algorithm，this paper proposes a K-nearest neighbor algorithm based on AP weighting，which uses variance weighted AP combined with Euclidean distance for similarity matching. Experimental results show that this method has higher positioning accuracy and stability than the classical indoor positioning algorithm.
Keywords：indoor positioning;positioning accuracy;stability
0 引 言
如今，以GPS为主的室外定位技术已基本成熟且适用性极高，其定位精度可达米级，仅仅依靠随身携带的移动设备就可以满足人们出行游玩方面的需求。随着经济水平的不断提高，一些企业的建筑规模愈发庞大。在某些车间中，人们需要对贵重的设备及工作人员进行规划管理;在医院、幼儿园等特殊场所同样需要对重点人群进行轨迹定位。这使得人们对室内定位服务的需求更加迫切[1]。早在1996年，室内定位技术就被美国联邦通信委员会所提出，至今仍是众多学者的研究热点。室内定位的高精度实现相比室外定位而言更加复杂，首先GNSS信号很难通过墙体等障碍物传递到室内，因此需要利用室内的物理设备以及其他的信号介质途径进行定位，这种技术也被称为局域室内定位技术。其中包含Wi-Fi技术、蓝牙技术、紫蜂技术、超宽带技术、惯性单元技术、超声波定位技术、射频识别技术、地磁定位技术、可见光定位技术、红外线定位技术等[2]。其次，信号在室内传播过程中极易受到人群流动、金属物品等干扰，导致稳定性受到影响。而且参与室内定位的设备成本、普及性及损耗程度在研究过程中均需考虑。因此在上述局域室内定位技术中，Wi-Fi室内定位技术因其精度较高，覆盖面较大，使用广泛且成本较低等倍受关注，同样在智慧城市建设、商场消费引导等方面也有着极大的应用前景[3]。
Wi-Fi室内定位方法主要有两种：利用无线传播模型定位技术和指纹库匹配定位技术。在无线传播模型方法中，通过信号达到时间（TOA）、信号到达时间差（TDOA）、信号达到角（AOA）等模型估计AP和移动台之间的距离。虽然这种方法有助于距离估计，但由于Wi-Fi信号容易受周围环境的影响，相关参数波动较大而无法提供准确的定位。相比之下，指纹库匹配定位技术具有无需考虑接入点（Access Point，AP）位置无需计算视距、受信号强度（Received Signal Strength，RSS）波动影响小、容错率高等优点，定位精度甚至比无线传播模型定位技术高。
本文以安徽理工大学空间信息与测绘工程学院为分析案例，通过对比当前主要的室内定位方法，初步讨论了基于AP加权K近邻算法的实用性及稳定性，对室内定位研究进行展望。
1 传统室内定位算法
5G技术发展逐渐成熟、卫星导航定位系统组网成功以及Wi-Fi硬件的更新换代使得室内定位服务精度需求得以实现。从21世纪初期指纹数据库匹配技术初步应用于Wi-Fi室内定位至今，指纹数据库匹配定位技术一直是研究的热点，具有低成本、高精度、良好的穿透力等优点。
指纹数据库匹配定位技术[4]包括两个阶段：离线数据库建立阶段和在线数据定位阶段。离线数据库建立阶段，实验区域进行网格划分构建位置坐标，在每一个坐标点进行RSS采集并进行预处理，筛除波动较大的RSS，将位置坐标和多个AP的RSS组成有序向量作为参考点存储入数据库;在线数据定位阶段，定位目标通过仪器实时采集RSS，采用匹配算法与数据库中参考点数据进行相似度匹配，再将匹配点通过均值、加权等方法计算定位目标的实际位置。 加权K近邻算（WKNN）法是由最早的最近邻定位（NN）算法到K近邻（KNN）算法一步步演变来的，一般以欧氏距离作为RSS向量间相似度的比较，决定指纹库匹配点的位置[5]。欧氏距离常用来表示两向量之间的绝对距离。两向量之间的欧氏距离如式（1）所示：
其中，A1（x1，x2，…，xn）和A2（y1，y2，…，yn）为两向量，d为欧氏距离。
在指纹数据库离线匹配阶段，若在定位区域布设i个参考点并通过设备采集每一个参考点的RSS值，将RSS值与位置坐标组成指纹存储入指纹库中，构建完成所需指纹库。
若使用欧式距离表示待测点与i个参考点之间的相似度，则式（1）改为式（2）：
其中，di为待测点与第i个参考点之间的欧氏距离，Rij为定位区域中第i个参考点上采集的第j个AP的RSS值;Sj为待测点上采集的第j个AP的RSS值;n为定位区域内所有的AP个数。
在指纹数据库匹配在线阶段，典型WKNN算法中欧氏距离通过计算待测点与指纹库中每个参考点的距离，距离越近表示两点相似度越明显，利用距离大小排序，选择距离最小参考点，此方法称为NN算法，只能描述出待测点大致位置，无法真正表示点的实际位置坐标[6]。
由于距离相当于相似度，若取K（K≥2）个参考点作为预定位点，求取多个预定位点位置坐标的平均作为待测点的实际位置坐标，则此方法称为KNN算法，相对NN算法精度较高，选取K个参考点进行定位。计算方法如式（3）所示：
其中，（x，y）为KNN算法的定位坐标，（xi，yi）为第i个参考点的实际位置坐标。
KNN算法仍然不能满足室内定位精度要求，考虑到不同参考点对待测点位置预测的贡献程度不同，给予K个参考点位置坐标不同的权值即可获得精度更高的预测坐标，此方法称为WKNN算法，WKNN算法计算簡单，是指纹数据库匹配中的常用算法，计算方法如式（4）所示：
其中，ωi为预定位参考点的第i个权值，ω的数值根据参考点与待测点之间的欧氏距离大小变化而变化，是决定待测点定位精度的重要参数。计算方法如式（5）所示：
若ωi的数值为 ，即为K近邻方法。传统室内定位仅仅考虑到不同参考点对待测点的影响，并没有考虑到数据源对定位结果的影响。
2 改进室内定位算法
室内定位中不同AP传输信号稳定性不同，造成定位精度并不准确，不可以统一权值进行计算相似度。利用不同AP差异性进行距离加权，使不同AP对定位的贡献程度不同，提升定位精度及稳定性[7]。
在上述传统WKNN算法基础上，在同一点采集多次数据，计算每个AP的方差，匹配点的相似度利用方差表示，如式（6）所示：
其中，σj为第j个AP采集RSS的方差;t为在同一点采集RSS值的次数;rj（k）为第j个AP采集的第k个RSS值; 为在同一点采集第j个AP所有RSS的平均值。从而计算AP加权值vj和距离相似度Di，求取待测点位置坐标：
3 实验分析
选取安徽理工大学空间信息与测绘工程学院二层某一教室进行实验验证。该定位区域面积约为20 m×20 m，教室内有隔墙、桌椅以箱子等干扰因素。此楼层设置4个采用TP-Link型号热点的AP点并用小米手机进行信号采集。
首先对实验区域进行网格划分，离线阶段对所有参考点进行采集并记录相关位置坐标，建立指纹数据库，并在中心某一点多次采集，为后期AP加权提供数据基础;在线阶段把待测点RSS用欧氏距离进行加权表示相似度，再用WKNN算法求解位置坐标，将解算坐标与实际坐标运算得出误差值，分析累计误差分布。实验操作流程如图1所示。
由表1可得，基于AP加权的WKNN算法相较于传统的WKNN算法平均定位误差由3.1 m减小到了2.9 m，提升了5.2%;最大定位误差由9.3 m减小到8.5 m，提升了8.9%;最小定位误差由0.14 m减小到0.11 m，提升了21.9%。定位精度明显由于传统的WKNN算法。
图2表示的是改进后的算法与WKNN、KNN算法之间定位累积概率误差。由图可得，基于AP加权的WKNN算法在定位误差概率分布上均优于WKNN算法且误差80%在4 m以内，定位的稳定性明显优于传统室内定位算法。
4 结 论
分析了室内定位指纹匹配阶段存在的各种问题，进而提出一种基于AP加权的WKNN算法来提升室内定位精度。将AP差异性利用方差进行表示并作为权值加入定位算法的相似度计算中，有效的解决了AP不同而造成的衡量指标的差异。实验表示，该方法提高了定位精度和指纹匹配的稳定性，且易实现具有一定的实用价值。
但是，基于指纹库匹配的室内定位仍需改进。数据方面，信道状态信息相对于信号强度更稳定，但是适用于信道状态信息的装置仍未普及;KNN算法中，K值仍然需要调试，无法进行算法自适应，达不到最高精度;预处理阶段，参考点信号波动引起误差，进行粗差处理后重组数据，可明显提高定位稳定性。这些问题都是今后值得研究的方向。
参考文献：
[1] 陈空，宋春雷，陈家斌，等.基于改进WKNN的位置指纹室内定位算法 [J].导航定位与授时，2016（4）：58-64.
[2] 李新春，王欢.基于稀疏指纹采集和改进WKNN的定位算法 [J].重庆邮电大学学报（自然科学版），2019，31（4）：451-459.
[3] 吴虹，王国萍，彭鸿钊，等.一种基于KNN的室内位置指纹定位算法 [J].南开大学学报（自然科学版），2020，53（6）：5-9.
[4] 毕京学，汪云甲，纪冬华，等.RSS最小值动态补偿的室内WKNN指纹定位方法 [J].测绘科学，2020，45（12）：22-27.
[5] 朱正伟，蒋威，张贵玲，等.基于RSSI的室内WiFi定位算法 [J].计算机工程与设计，2020，41（10）：2958-2962.
[6] 康晓非，李梦梦，乔威.基于WiFi指纹的高精度室内定位融合算法 [J].西安科技大学学报，2020，40（3）：470-476.
[7] 党小超，马平川，郝占军.基于CSI的改进KNN室内定位方法 [J].传感器与微系统，2019（10）：51-53.
作者简介：仲臣（1997—），男，汉族，安徽马鞍山人，硕士在读，研究方向：室内定位。