基于回归近邻成分分析和GBRT的室内定位方法*

王斌涛，冷腾飞，王益涵，郑家骅

（上海工程技术大学工程训练中心，上海 201620）

0 引 言

随着智能手机和无线网络的广泛应用，基于位置的服务（location-based service，LBS）应用越来越广泛［1］。作为LBS的重要组成部分，室内定位技术在工业和商业应用中展现了巨大潜在价值，因此引起了许多研究者的关注［2］。

近年来，研究者相继提出了多种室内定位技术，如基于超声波的定位技术、基于可见光的定位技术、基于地磁的定位技术以及基于无线信号的定位技术。基于无线信号的定位技术（几何测距和位置指纹）由于实现成本较低，被最广泛采用。常用的几何测距定位方式有到达时间（time of arrival，TOA）、到达角（angle of arrival，AOA）以及到达时间差（time difference of arrival，TDOA）［3］。几何测距定位方式的性能很大程度上依赖于视线条件。然而，室内环境中信号传播存在多径效应，由于多径效应的影响，信号传播会产生噪声，往往会使得测距值远远大于实际距离，定位精度会产生巨大误差。为了避免多径效应和非视距误差的影响，通常利用位置指纹定位替代几何测距定位。位置指纹定位是一种模式匹配的方法，其主要原理是收集待定位区域内所有潜在位置的信号特征，建立位置指纹数据库［4］。

许多研究者针对位置指纹定位提出了各种基于机器学习的算法。其中被广泛采用的是K 近邻（K-nearest neighbor，KNN）算法和加权KNN（weighted KNN，WKNN）算法以及基于变异系数改进的WKNN（VWKNN）算法［5］。这些算法基本原理是通过匹配待定位点的实时接收信号强度指示（received signal strength indication，RSSI）测量值与离线指纹数据库里欧氏距离最小的K个参考点，然后取这K个参考点坐标的平均值作为待定位点的估计位置［6］。此类算法定位精度能够满足基本需求，但是大型室内场景下接入点（access point，AP）个数和参考点的个数较多，因而离线指纹数据库规模庞大，在线定位时通常会遍历整个离线指纹数据库进行参考点匹配，导致计算量激增，使得这类算法在实际定位时耗时过长。综上，与传统方法相比，基于机器学习的定位方法提高了定位精度，但这些方法在处理数据量较大且含有噪声的数据时定位效果并不理想。由于信号噪声的影响导致位置指纹与坐标呈现非线性关系，此种情况下欧氏距离度量并非最优。

为此，本文改进了近邻成分分析（nearest neighbor component analysis，NCA）算法，通过NCA 算法得到最佳度量，再结合渐进梯度回归树（gradient boost regression tree，GBRT）算法，提出了NCA-GBRT 定位算法。缩短了训练时间，加快了训练速度，提高了预测精度。首先，利用基于距离度量学习NCA算法对离线指纹数据库进行特征提取并得到转换矩阵，降维重构后的数据比原始数据具有更好的空间特性。然后利用梯度提升回归树算法集成多个弱学习器得到参考点指纹与参考点坐标的映射关系，构建定位模型。

1 位置指纹定位

1.1 基本原理

位置指纹是指将每个参考点收到的所有AP信号强度作为一个特征，则每个预设参考点能够得到不同的信号强度特征，这些得到的特征称为位置指纹信息［7］。基于RSSI的位置指纹法实现定位分为2 个阶段：离线阶段和在线阶段［8，9］。图1为位置指纹定位流程。

图1 位置指纹定位流程

1.2 离线阶段

在待测区域中选择合理的参考点，并测量每个参考的坐标，在每个参考点处采集所有AP 的RSSI，假设有n个AP，m个参考点，则最终得到的位置指纹数据库的结构如下

式中D为离线指纹库，包含每个参考点的坐标及其所能接收到的每个AP 的RSSI，此数据库中共有m×n个记录；（rssi1m，rssi2m，…，rssinm）为在参考点（xm，ym）处接收到的n个AP的RSSI。

1.3 在线阶段

在待定位点处测量每个AP 的RSSI，与离线阶段构建的位置指纹数据进行匹配，得到相似度最高的样本，样本位置即为待定位点的位置。位置指纹定位问题可以概括为寻找一个映射，使得待定位点的指纹和位置指纹数据库通过这个映射得到的估计值和待定位点的实际坐标期望误差最小。与数据库进行匹配的阶段，常用的算法有确定型算法和概率型算法［10］。其中KNN算法是最常用的确定型匹配算法，其原理是比较待定位点的位置指纹和离线数据库中的所有参考点位置指纹，计算它们之间的欧氏距离或者是曼哈顿距离等，得到前K个最相似的参考点，计算其平均位置的坐标，即为待定位点的坐标。

2 NCA-GBRT定位算法

2.1 离线位置指纹数据预处理

在室内环境中，信号观测值包含高斯噪声和非高斯噪声，噪声的存在会影响定位精度［11］，因此在数据预处理过程中需要对测量得到的信号进行滤波。常用的信号滤波方法有均值滤波、中值滤波、狄克逊检验法滤波和高斯滤波等。由于卡尔曼滤波（KF）能在一定程度上削弱由于噪声叠加造成的RSSI观测值偏离，经过KF算法处理后的RSSI值，具有更好的稳定性［12］。因此，本文在构建指纹数据库前采用KF算法对数据进行处理。KF算法利用最小均方误差作为优化估计准则，采用信号和噪声的状态空间模型，然后使用前一时刻的估计值和当前时刻的观测值更新状态变量，并计算当前时刻的估计值，如图2所示。

图2 KF过程

2.2 改进NCA算法对原始数据特征提取

当大量的AP分布于定位区域时，待定位点只能接收到部分AP的信号，其他AP 由于距离待定位点较远，或者是信号受到墙壁等障碍物阻挡，待定位点接收到的部分AP的RSSI较弱，RSSI 向量中存在冗余值，且RSSI 存在时变特性，使得传统算法的定位效果不理想。为了提升定位效率和精度，利用NCA算法进行特征提取，使得特征提取后的离线指纹数据更好地反映位置指纹的空间特性。

本文使用NCA算法将原始的位置指纹数据通过最大化目标函数得到位置指纹数据的特征。NCA算法的原理是最大化样本点的分类正确数目，但本文中样本的标签为连续值，因此需要对NCA算法改进，使得NCA 算法适用于本文中的回归问题。重构后的指纹数据维度会影响最终定位精度，若保留的特征维度过少会导致定位精度较低，而特征维度过多则无法有效去除冗余信息。因此NCA 算法需要选择合适的维度进行特征提取。

2.3 GBRT定位模型

GBRT算法预测精度高，适合低维数据，通过选择合适的损失函数，可以降低异常值对定位精度的影响。因此，本文利用其构建通过学习NCA 特征提取后的新指纹数据与参考点位置坐标的映射关系得到最终的定位模型，如表1。

表1 构建定位模型

2.4 定位流程描述

本文提出的NCA 结合梯度提升回归树算法的定位算法过程如图3所示。

图3 本文算法定位过程

3 实验与分析

本文采用MATLAB对提出的定位算法进行仿真，实验数据来自文献［13］，该数据采集地点为某大楼地下停车场，测试区域面积为30 m×30 m，采样间隔为1 s，该室内环境一共分布有多个AP，以1 m为采样间隔，将该室内区域划分成相同大小的网格，以网格交叉点作为采样参考点，共726 个参考点。对每个采样点的4 个方向各测量100 次，然后利用KF算法进行处理后作为该参考点的最终RSSI 值，以下以其中某一AP为例，区域内参考点接收到此AP的RSSI值分别如图4所示。

图4 测试区域收到的某个AP的RSSI

3.1 特征提取维度对定位精度的影响

本文通过对比NCA 算法降维后的维度对定位精度的影响进行分析，以平均定位误差作为性能指标，结果如图5所示。当dim ＝2 时，只保留了原始指纹数据库的少量特征，因此平均定位误差达到了3.162 m。随着dim 增大，保留原始数据的特征增加，平均定位误差随之下降；当dim ＝5时，平均定位误差相比dim ＝2 时减小了0. 462 m 达到2.7 m；而当dim ＝10 时，平均定位误差达到了最小，为2.66 m，随着维度的增加，更多的冗余特征影响了定位精度，使得定位误差逐渐增大。在本文实验条件下，dim ＝10为最佳的特征维度。

图5 不同特征提取维度定位精度比较

3.2 不同特征提取算法对定位精度的影响

以累积分布函数（cumulative distribution function，CDF）为性能指标，将本文NCA混合GBRT定位算法和局部线性嵌入结合GBRT定位算法比较，如表2。图6展示了特征维度dim ＝10条件下两种定位算法的CDF。如图所示，本文算法定位过程中有60%的概率小于2 m，与此同时，对比算法仅有52%的概率小于2 m。此外，本文算法有90%的概率定位误差小于4 m，而对比算法仅有80%。结果表明，本文算法明显优于对比算法。

图6 不同特征提取算法定位精度的比较

3.3 本文算法与同类算法比较

利用CDF和参考点定位精度作为性能指标，将本文算法与WKNN、VWKNN 和监督自适应局部判别嵌入（supervised adaptive local discriminant embedding，SALDE）+支持向量机（support vector machine，SVM）算法进行对比，对比CDF和各个测试点的定位误差，结果如表3 和图7、图8所示。

表3 不同定位算法对定位性能的比较

图7 不同定位算法定位效果的比较

图8 不同测试点定位误差的比较

4 结 论

本文针对室内无线信号波动的影响导致位置指纹存在冗余噪声因而定位精度不足的问题，提出了一种新的基于NCA和GBRT的定位算法，该算法利用NCA算法重构指纹数据库提取特征，增大不同参考点的指纹特征的差异性。再通过迭代构造多个CART TREE，即通过每一个CART TREE的损失函数的负梯度值构造下一个CART，通过集成多个CART TREE 得到最终的GBRT 定位模型，通过该定位模型实现对待定位点的位置预测。本文通过实验证明了所提出的NCA-GBRT 定位算法性能明显优于其他算法。