基于AP加权的自适应动态室内定位方法

仲 臣，余学祥，邰晓曼，肖星星，韩雨辰，刘清华

基于AP加权的自适应动态室内定位方法

仲 臣1,2,3，余学祥1,2,3，邰晓曼1,2,3，肖星星1,2,3，韩雨辰1,2,3，刘清华1,2,3

（1. 安徽理工大学 空间信息与测绘工程学院,安徽 淮南 232001；2. 安徽理工大学 矿山采动灾害空天地协同监测与预警安徽普通高校重点实验室,安徽 淮南 232001；3. 安徽理工大学 矿区环境与灾害协同监测煤炭行业工程研究中心,安徽 淮南 232001）

针对传统定位算法存在大量不同接入点（AP）的冗余信息，且在定位范围较大时定位时效性差的问题，提出一种基于卡方距离的AP加权自适应动态定位算法。指纹匹配阶段利用卡方距离代替传统加权近邻算法（WKNN）中的欧式距离，用AP方差对相似度进行加权，从而自适应调整距离阈值，并引入动态值，精确提取数据库信息。实验结果表明，与传统定位算法相比，该算法更有利于去掉冗余的AP，使定位误差范围缩小，可显著提高定位精度与稳定性。

室内定位；自适应加权近邻；指纹匹配；定位精度

0 引言

随着科学技术的高速发展，卫星定位系统在室外导航应用上极其广泛，定位精度已经达到毫米级，但在大型建筑中进行室内定位，其精度仍不满足要求。为了追求更加高效、智能的生活方式，基于位置服务（location based services, LBS）的室内定位技术正展现着广泛的应用前景。室内定位技术主要包括蓝牙、地磁、射频识别、无线保真（wireless fidelity,WiFi）定位、惯性导航、超宽带、超声波等方法。WiFi室内定位凭借着精度相对较高、WiFi接入点部署简单和成本低等特点成为目前研究热点。

文献[1]提出基于数据库扩充的-均值（-means）聚类结合加权近邻（weighted-nearest neighborhood，WKNN）算法，解决了WiFi信号波动大和抗干扰能力差的问题。文献[2]针对环境易变性引起的WiFi信号不稳定性，在数据库中添加接收信号强度（received signal strength，RSS）均值和二阶矩阵，提出一种基于中心距加权改进的WKNN匹配算法。文献[3]利用最小值动态补偿处理RSS的室内定位方法，提高了WKNN算法的定位精度和稳定性。文献[4]在原始近邻（-nearest neighborhood，KNN）基础上，融合朴素贝叶斯概率算法，对指纹库匹配定位误差大、稳定性差做出了改进。对于经典欧氏距离仅考虑到各RSS之间的绝对距离，忽略了相对距离的影响，文献[5]提出一种基于卡方距离赋予各接入点（access point, AP）权重的室内定位算法；文献[6]将自适应修正曼哈顿距离代替欧氏距离作为相似性距离，再利用AP选择算法，采用干扰程度小且出现频率高的AP下的RSS，使定位结果更稳定。在传统近邻KNN算法中，使用偏差大的参考点匹配邻近点导致待测点误差大，文献[7]通过邻近点的几何结构去除几何中心较远参考点，提出改进的组合定权室内定位算法。

由上述学者对于指纹数据库的研究可知，目标区域WiFi信号波动及来自不同AP的RSS值稳定性差别引起的定位误差依然需要深入研究。因此，为更好地描述参考点与待测点的相似度、实现加权近邻算法无需再调试值，本文提出一种自适应动态值AP加权定位算法。通过实验验证，本文算法有效提高了定位精度和待测点的预测能力，可完成自适应调整值。

1 WiFi指纹库匹配定位技术

在指纹库匹配研究方向中，以指纹向量相似度匹配研究为主，算法包括多种改进近邻算法、反向传播（back propagation, BP）神经网络、高斯过程回归模型、概率分布、支持向量机等，因近邻定位算法运算速度快、精度较高，众多学者一直以此为研究热点。

1.1 加权K近邻算法

加权近邻算法是由最近邻定位算法到近算法一步步演变来的，一般以欧氏距离作为RSS向量间相似度的比较，决定指纹库匹配点的位置[8]。加权近邻算法已基本满足室内定位精度要求，但仍然存在技术问题。就相似度表示而言，WKNN算法中使用欧氏距离，仅考虑了参考点与待测点RSS值之间的绝对距离，忽略了RSS向量之间的相对距离；就AP权重分配而言，不同AP之间的稳定性不同，使得不同AP下的RSS信号准确度不同，最终导致会因AP不同造成的误差；就值而言，值不同，定位精度也不同，需进行多次调试才能寻找到最佳值。因此，在已有的研究基础上，仍能改进WKNN算法，减小误差提高室内定位精度。

1.2 基于AP加权的自适应动态WKNN

针对WKNN算法存在的问题，本文提出基于AP加权的自适应动态WKNN算法。由于使用不同的距离表示相似度，会对参考点分类有所影响。相对于欧氏距离，卡方距离并不是绝对距离，它表示向量间的相对距离，对向量间的特性差值和向量中特征值相对于距离的变化有较好的说明，能有效反映参考点与待测点的实际位置。本文选取卡方距离代替欧氏距离，可明显发现参考点与待测点的相似度。相似度可表示为

在指纹数据库匹配定位中，每个AP具有不同的稳定性，稳定性高的AP对于待测点位置坐标的预测影响大。因此，将稳定性高的AP赋予数值大的权值，反之，赋予数值小的权值[9]。对同一点多次采集RSS值，通过计算不同AP的方差来表示每个AP的稳定性，方差小的AP稳定性高，方差大的AP稳定性低。AP采集RSS的方差的计算公式为

由AP加权后的卡方距离计算坐标权值ω为

基于AP加权的自适应动态室内定位算法实现如图1所示。通过计算点与点之间的卡方距离与方差，确定权值及相似度，由排序确定阈值，获取自适应动态值，提取数据库相应坐标，计算待测点位置。

图1 定位流程

2 实验与结果分析

2.1 实验环境与方法

构建算法后需进行实验验证算法精度，选取安徽理工大学空间信息与测绘工程学院如图2所示的一间长为11 m、宽为11 m教室作为实验区域，并将其划分为1 m×1 m组成的格网进行数据采集，图1中黑色圆点为AP位置。

图2 实验区域

笔记本电脑作为信号接收器，实测指纹数据信息为4个AP的RSS值组成的向量，将实测指纹信息存储进数据库，采用5折交叉验证[10]，保证定位结果的准确性。在网格交点处采集数据，随机选取实测数据作为待测点，设置18个待测点和72个参考点，18个待测点即为验证集，占所有数据的20%，可避免随机误差影响定位精度的准确性，记录所有点位的位置坐标。选择网格内中间任意一点位采集100次数据，计算4个AP的方差，以此作为每个AP的稳定性。利用上述自适应动态值原理，计算基于卡方距离的AP方差加权后的相似度值，得到待测点的位置坐标[11-12]。

2.2 实验结果分析

为验证本文算法定位精度，分别利用基于卡方距离的WKNN算法（WKNN algorithm based on Chi square distance，CS-WKNN）和基于卡方距离AP加权的WKNN算法（WKNN algorithm based on Chi square distance AP weighting，CSW-WKNN），对同一指纹库进行待测点预测定位，分析每一个待测点的最大定位误差、最小定位误差与平均定位误差。根据本文算法原理，三种方法待测点具体定位结果如图3所示，显然本文算法可准确预测待测点实际位置，为未知点位的轨迹预测提供位置基础。

图3 预测点位

由图4可知，通过选择不同值对同一指纹数据库进行待测点位置预测，当值为4时，CS-WKNN算法和CSW-WKNN算法平均定位误差存在最低值。本文算法处理同一数据集时，值存在自适应变化（如图5所示），有利于去掉冗余的AP，使定位误差范围缩小。为减少算法计算量，将最优（=4）值代入实验，分析累计误差分布如图6所示。

对比三种算法的定位误差范围占比、具体误差数值以及算法完成所需时间，验证本文算法的可行性，如表1至表3所示。

图4 不同K值平均定位精度

图5 自适应K值大小

图6 累计误差分布

表1 误差范围比例

表2 算法误差对比 单位：m

表3 算法完成所需执行时间 单位：s

分析表1可知，本文算法和CSW-WKNN算法误差均在4 m以内，1 m以内误差占比过半。结合图6分析，CS-WKNN算法定位误差集中在2～4 m，说明不同AP确实存在稳定性差别，对室内定位结果存在影响。

通过表2的最大定位误差、最小定位误差和平均定位误差比较，本文算法平均定位误差较CSW-WKNN算法降低了5.8%，较CS-WKNN算法降低了41.9%；此外，最大定位误差较CSW-WKNN算法降低了4.6%，较CS-WKNN算法降低了35.2%；但本文算法误差多集中于1 m以内，且平均误差为1.2346 m，误差波动较小。

三种算法完成定位所需时间（如表3所示）均满足实际工程需求，当定位范围较大且数据库信息复杂时，本文算法更有利于去除冗余的AP信息，解决定位时效性差的问题。综合分析，本文算法定位精度与CSW-WKNN算法接近且有所提升，对于值存在更高的稳定性且降低了分析匹配最佳值的时间。

3 结束语

针对传统WKNN算法中固定值和AP稳定性不同导致的定位精度低，本文提出一种基于卡方距离的AP加权自适应动态值WKNN算法。通过参考点与待测点之间的距离差，给予不同AP不同权值，决定相似度距离的阈值，由阈值剔除由于空间结构引起的误差点，自适应获得个参考点，精确计算待测点真实位置坐标，实现了动态值室内定位算法。实验结果表明，相比CSW-WKNN、CS-WKNN算法采用固定值，本文算法可避免疏远参考点和AP不同稳定性引起的偏差，有效提高了室内定位的稳定性和定位精度，能更好地应用于实际生活中。

[1] 秦国威, 孙新柱, 陈孟元. 基于Wi-Fi指纹的改进型室内定位算法研究[J]. 陕西理工大学学报(自然科学版), 2018, 34(3): 28-34.

[2] 于洋, 陈光, 单志勇, 等. 基于中心矩改进的WiFi室内定位算法[J]. 计算机应用与软件, 2018, 35(2): 130-133, 160.

[3] 毕京学, 汪云甲, 纪冬华, 等. RSS最小值动态补偿的室内WKNN指纹定位方法[J]. 测绘科学, 2020, 45(12): 22-27.

[4] 何志爽, 万亚平, 赵庆, 等. WiFi的室内定位技术的改进研究[J]. 南华大学学报(自然科学版), 2018, 32(3): 60-64.

[5] 陶峥, 王洪玉. 基于卡方距离改进的WLAN室内定位算法[J]. 计算机技术与发展, 2016, 26(9): 50-55.

[6] 陈亦奇, 周蓉, 滕婧, 等. 基于自适应修正曼哈顿距离的室内定位方法[J]. 导航定位与授时, 2019, 6(6): 94-102.

[7] 曹晓祥, 陈国良. 一种改进的组合定权的指纹定位算法[J]. 测绘通报, 2018(2): 6-10.

[8] 敬振宇, 熊兴中, 张维, 等. 改进动态K的WKNN的室内定位方法[J]. 现代电子技术, 2021, 44(7): 22-27.

[9] 仲臣, 韩雨辰, 宁全可, 等. 基于AP加权的WKNN室内定位算法[J]. 现代信息科技, 2020, 4(22): 71-73.

[10] 赵芳. 基于参考位置指纹离散程度的WKNN定位方法[J]. 沈阳工业大学学报, 2021, 43(2): 203-207.

[11] 徐逸轩, 余松森, 苏海, 等. 基于差分修正的WKNN室内定位方法[J]. 电脑知识与技术, 2020, 16(4): 256-258.

[12] 康静怡, 韩中豪, 何玉美, 等. 一种基于WKNN定位的改进算法[J]. 成都信息工程大学学报, 2018, 33(1): 8-12.

Adaptive dynamic indoor positioning method based on AP weighting

ZHONG Chen1,2,3, YU Xuexiang1,2,3, TAI Xiaoman1,2,3, XIAO Xingxing1,2,3, HAN Yuchen1,2,3, LIU Qinghua1,2,3

(1. School of Geomatics, Anhui University of Science and Technology, Huainan, Anhui 232001, China；2. Key Laboratory of Aviation-aerospace-ground Cooperative Monitoring and Early Warning of Coal Mining-induced Disasters of Anhui Higher Education Institutes, Anhui University of Science and Technology, Huainan, Anhui 232001, China；3. Coal Industry Engineering Research Center of Mining Area Environmental And Disaster Cooperative Monitoring, Anhui University of Science and Technology, Huainan, Anhui 232001, China)

In view of the redundant information of different Access Points (AP) in traditional location algorithm, and the time-effective error of location in the large location range, an AP weighted adaptive dynamic location algorithm based on the square distance is proposed. In fingerprint matching stage, the chi square distance is used to replace the European distance in the traditional Weighted-Nearest Neighborhood (WKNN) algorithm, and the AP variance is weighted to the similarity, so as to adjust the distance threshold adaptively, and dynamicvalue is introduced to extract the database information accurately. The experimental results show that the algorithm is more advantageous to remove redundant AP, reduce the range of positioning error and improve the positioning accuracy and stability.

indoor location; adaptive weighted-nearest neighbor; fingerprint matching; positioning accuracy

P228

A

2095-4999(2022)02-0053-05

仲臣，余学祥，邰晓曼，等. 基于AP加权的自适应动态室内定位方法[J]. 导航定位学报, 2022, 10(2): 53-57.（ZHONG Chen, YU Xuexiang, TAI Xiaoman, et al. Adaptive dynamic indoor positioning method based on AP weighting[J]. Journal of Navigation and Positioning, 2022, 10(2): 53-57.）

10.16547/j.cnki.10-1096.20220207.

2021-06-30

国家自然基金面上项目（41474026）；安徽省自然科学基金项目（2008085MD114）。

仲臣（1997—）,男,安徽马鞍山人,硕士研究生，研究方向为空间信息与定位。

余学祥（1965—），男，安徽太湖人，博士，教授，研究方向为空间信息与定位。