高斯过程回归与参考点排序相结合的新WiFi室内定位系统

陶 冶，赵 龙

(1.北京航空航天大学自动化科学与电气工程学院，北京 100191； 2.北京航空航天大学数字导航中心，北京 100191)

0 引言

随着移动设备的发展，基于位置服务的需求越来越旺盛。在室外，可以通过卫星信号获得载体的高精度定位结果，但由于室内环境的复杂性，使得卫星信号在室内无法定位。而基于WiFi的室内定位技术不需要安装额外的硬件，使得该项技术成为常用的室内定位方案之一[1-2]。

基于WiFi的室内定位技术通常被分为两类，一类是基于三边测距的定位算法[3]，另一类是基于指纹的定位算法。但在非视距的情况下，三边测距的定位精度不如指纹定位。因此，WiFi指纹定位技术被广泛研究和应用。

通常WiFi指纹定位技术的流程分为两步[4]，第一步：线下指纹库的建立,该过程需要在线下采集不同点接收到的WiFi接入点(Access Point, AP)的信号强度，这些点又被叫作参考点；第二步：在线定位,该过程是将用户上传的测试数据与指纹库中的信号强度进行匹配，选择匹配度高的参考点进行加权平均定位。其定位步骤示意图如图1所示。

(a)离线采集 指纹库

(b)采集测试 数据库

(c)定位过程

WiFi指纹容易受到环境因素的影响，例如障碍物的移动、温度、湿度、AP发射功率和位置变化等，因此指纹库的时效性很低，需要不断地更新指纹库来保证定位精度[5]。此外，不同的指纹匹配算法也会影响定位精度[6]。

在指纹匹配算法方面，较为经典的算法有K近邻(K-Nearest Neighbor，KNN)[7]和加权K近邻(Weighted K-Nearest Neighbor，WKNN)算法[8]，但是这些算法都没有考虑环境和指纹动态特性对定位精度的影响，因此往往定位精度较低。针对部分AP休眠、位置改变和AP在线信号突然探测不到等现象引起的定位误差问题，DorFin[9]利用强回归(Robust Regression)修正在线接收到的信号强度；LAAFU(Localization with Altered APs and Fingerprint Updating)[10]利用不同APs的信号强度子集筛除出变化的AP;自适应区域搜索(Adap-tive Area Search，AAS)[11]利用参考点排序算法削弱这些现象对于定位的影响。但是这些算法都没有考虑信号本身所具有的动态变化问题。对于信号自身存在的动态变化问题，在采集指纹库时，往往通过在每一个参考点采集多组数据进行平均来解决。但由于在线定位阶段，用户一般只在一个点停留1～2s，因此上传的测试数据具有噪声，无法很好地反映当前测试点的真实信号强度。

在指纹库更新算法方面，基于Matern核的Zero_GPR[12]算法得到了广泛的研究，但是该算法没有考虑WiFi信号自身的传播特性；DNCIPS[13]利用在固定节点放置设备，实时采集信号强度，并通过WiFi信号传播拟合公式(LDPL模型)[13]和基于SE核的高斯过程回归(Gaussian Process Regres-sion，GPR)提出了LDPL_GPR算法进行指纹库更新，但是该算法需要在固定位置额外放置设备。

为了解决上述问题，本文提出了一种新的WiFi室内定位系统，该系统包括一个新的定位算法和指纹更新算法。新的定位算法改进了基础参考点排序算法，同时考虑了测试信号本身的动态变化特性。该改进算法将处于同一范围内的参考点排序视为与测试点具有相同的相似度，这是因为所获取的测试信号强度受到了噪声干扰，而这些噪声使得参考点排序结果不稳定，所以采用模糊化的方法会更好地刻画每一个参考点与测试点之间的信号强度相关性。指纹库自更新算法考虑了WiFi传播特性，利用其传播模型模拟每一个点的信号强度，并结合GPR算法以逼近真实的信号强度。与DNCIPS[13]不同的是，该算法利用上传的测试数据预测未知点的信号强度，而不需要在固定位置处放置设备来实时获得信号强度，这使得新的指纹更新算法更加灵活，且该算法利用Matern核更好地刻画了坐标点与相对应的信号强度之间的非线性关系。

为了验证系统的有效性，在北京航空航天大学新主楼4层采集了真实数据，并与已有的算法进行了大量的对比实验。实验结果显示，该系统可以很好地提高定位精度和指纹更新精度。

1 系统简介

本文提出的WiFi室内定位系统的实现过程示意图如图2所示，主要包括在线定位和在线指纹自更新两部分。

图2 WiFi定位系统实现过程Fig.2 Implementation process of WiFi positioning system

在线定位时，将接收到的测试点信号强度与指纹库进行对比，通过改进的参考点排序算法进行匹配得到定位结果(x,y)。由于改进的参考点排序算法可以提供较高的定位精度，因此在线进行指纹自更新时，LDPL_GPR+Matern算法将定位结果(x,y)作为真实位置，并利用对应接收到的信号强度去预测其余未知点的信号强度，从而实现了指纹库的在线自更新。

2 新定位系统的理论和算法

本节在简单介绍参考点排序算法的基础上，重点介绍了改进的参考点排序定位算法和指纹更新算法。

2.1 参考点排序

对于同一AP，首先计算参考点与测试点接收到的信号强度差的绝对值，其计算公式为[11]

errorji=|sij-tj|

(1)

式中，errorji表示第i个参考点接收到的第j个AP的信号强度与测试点接收到的第j个AP的信号强度之间差的绝对值；sij表示第i个参考点接收到的第j个AP的信号强度；tj表示测试点在线接收到的第j个AP的信号强度。

然后，将信号强度差的绝对值转换为从1～m的排序，其转换公式为[11]

rank(RPij)=find(errorji=sort(errorj))

(2)

式中，rank(RPij)表示第i个参考点接收到的第j个AP的信号强度与测试点接收到的第j个AP的信号强度之间的差在所有参考点与测试点信号强度差中的排序；errorj=[errorj1,errorj2,…,errorjm]；sort(*)表示对向量由小到大进行排序；find(A==B)表示元素A在向量B中的索引；m表示参考点的数量。

同理，逐一计算参考点在每一个AP下的排序，然后计算每一个参考点在所有AP下的排序平均值，并将其作为该参考点的最终排序。其第i个参考点的综合排序计算公式为[11]

(3)

式中，n表示AP的数量。

最后，根据每一个参考点的综合排序，选择排名靠前的k个参考点进行加权平均定位，其对应权重可表示为[11]

(4)

于是，最终的定位结果可表示为

(5)

式中，loci=(xi,yi)为所选取的第i个参考点的坐标；loct为最终预测的测试点的位置结果。

2.2 改进的参考点排序算法

图3所示为1min内在同一点连续接收同一AP的信号强度值的统计直方图。从图3中可以看出，信号强度会随着时间的变化而变化，因此直接将绝对差值转换为排序，忽略了信号强度动态变化带来的误差，这会导致系统的定位精度降低。

图3 1min收集到的定点信号强度分布Fig.3 Distribution of RSS collected at a fixed point in one minute

为解决该问题，本文提出了一种改进的算法，该算法采用模糊的思想，将处在同一个范围内的排序结果视为相同的排序，其数学表达式为

(6)

式中，β为长度参数，控制排名的范围。

由于参考点与测试点位置越接近，其对应的参考点会在更多的AP下具有更好的排序。基于这一事实，本文提出的改进算法重新定义了参考点的综合排序计算方法，其中第i个参考点的综合排序计算公式可表示为

(7)

于是权重表示为

(8)

2.3 指纹更新算法

Zero_GPR[12，14]是一种适合非线性回归问题的无参数模型，可通过训练数据的输入限制先验分布实现贝叶斯框架下的后验分布状态预测，输出预测的均值和方差，预测结果具备不确定表达能力。其回归模型可表示为

s=f(w)+η

(9)

假设有m个训练数据，其输入为w，则观测值s的先验分布可表示为

f(w)～GP(0,k(wi,wj))

(10)

式中，核函数k(wi,wj)一般表示为SE核函数，其表达式为

(11)

且当wi=wj时，有

(12)

式中，σf表示协方差因子；l表示长度参数。

对于未知点w*处信号强度的预测值s*和观测值s之间服从联合分布

(13)

式中

预测值的后验分布模型为

(14)

因此，未知点处信号强度的预测均值为

s*=K*K-1s

(15)

在文献[12]中发现，基于高斯过程回归的GPR模型，使用Matern核对信号强度的预测效果要优于使用SE核的预测效果，Matern核的表达式为

(16)

而单独使用Zero_GPR预测未知点的信号强度时，在预测远离训练点的未知点的信号强度的预测均值在0附近，这显然不符合WiFi信号强度的传播特性。本文结合WiFi传播模型，对基于Matern核的Zero_GPR算法进行了改进，并提出了LDP_GPR+Matern预测模型。WiFi传播模型可表示为LDPL模型[13]，其表达式为

(17)

式中，wAP=[xAP,yAP]；C表示参考点距离AP为1m时接收到的信号强度；α为衰减系数。

对于w*接收到第j个AP的信号强度的预测表达式为

(18)

本文利用最小残差思想求解Cj、α、xAPj、yAPj，其目标函数表达式为

(19)

本文利用最大似然估计求解LDPL_GPR+Matern算法的最优参数l、σn，其目标函数表达式为

(20)

式中，z=s-m(w)。

在此基础上，本文利用烟花算法[15]进行寻优求解以获得所求参数。

3 实验验证与分析

3.1 实验环境与测试条件

为了验证系统中算法的有效性，在北京航空航天大学新主楼4层采集数据，并进行了实验验证。图4所示为实验环境的布局，长为70m，宽为15m。图4中，红色圆圈表示线下建库时的指纹参考点，一共125个，每一个参考点的采样时间为60s；绿色方框点表示在线测试点，一共79个，实验过程中每一个测试点的采样时间为1～2s。为了测试算法在陌生环境下的工作性能，没有对AP的相关信息(位置、发射功率等)进行提前调研，所探测到的AP的信息均是未知的，在这样的环境下进行实验测试更能说明算法的普适性。本文利用熵信息[16]筛选出50个区分度大的AP进行定位，以减少在线定位运算时间。

图4 实验区域分布图Fig.4 Layout of experimental area

3.2 定位实验结果及分析

为验证定位算法的有效性，本次实验利用参考点预测79个测试点的位置，且实验时设置了不同的β值进行了多次定位实验，最终取平均结果代表该改进排序算法的最终定位精度，β=(0.04,0.08,0.12,0.16,0.20,0.24,0.28,0.32)。将所提算法的定位结果与KNN、WKNN和已有的参考点排序算法进行对比分析。文中KNN与WKNN算法使用测试点与参考点之间信号强度的欧式距离筛选与测试点相似的参考点，且将欧氏距离的倒数作为WKNN算法中相似参考点的权重。当k=5时，不同算法的累计误差概率分布(Cumulative Distribu-tion Function，CDF)如图5所示。

图5 不同算法的累计误差概率分布图Fig.5 Cumulative distributions of positioning error of different algorithms

从图5中可以看出，基于参考点排序和改进的参考点排序算法的定位结果曲线几乎都位于KNN和WKNN定位曲线的上方，这说明基于参考点排序算法是有效的，而且改进算法的定位结果相对于参考点排序算法在均值误差和标准差方面均有所提升。为了进一步量化所提算法的优越性，对定位结果进行了相应的统计，统计结果如表1所示。

表1 不同算法的定位结果统计

为进一步说明改进算法的优势，本次实验统计了k取不同值时不同算法的定位精度，其结果分别如图6和表2所示。其中，图6所示为k取不同值时不同算法的均值误差；表2所示为k取不同值时不同算法的均值误差和标准差。从图6和表2中可以看出，在均值误差方面，改进的参考点排序算法相对于KNN、WKNN和参考点排序算法分别提升了25.52%、25.52%和4.05%；在标准差方面，改进的算法相对于KNN、WKNN和参考点排序算法分别提升了33.86%、30.86%和8.70%。

图6 不同算法下的平均定位误差Fig.6 Mean positioning errors with different algorithms

表2 不同算法的定位结果统计

3.3 指纹更新实验结果及分析

为了验证指纹更新算法的有效性，本次实验利用参考点预测40个测试点的位置，在定位的基础上，利用40个点的信息和指纹更新算法预测剩下39个测试点的信号强度，并与真实信号强度进行对比，得到信号强度的预测误差。本次实验将LDPL_GPR+Matern的预测结果分别与ZERO_GPR+SE和ZERO_GPR+Matern进行对比，不同算法预测结果的均值误差和标准差如表3所示。

表3 不同算法的信号强度预测误差统计

从表3中可以看出，ZERO_GPR+Matern算法的均值误差和标准差比ZERO_GPR+SE算法的都小，这说明Matern核相较于SE核确实更适用于预测WiFi信号的信号强度。与ZERO_GPR+Matern相比，LDPL_GPR+Matern的标准差几乎保持不变的同时，均值误差降低了34.52%，这说明结合LDPL模型和GPR模型可以有效提高对于未知点信号强度的预测精度。

4 结论

本文提出了一种新的WiFi指纹定位系统，该系统可以长期封闭式运行，且保持较高的定位精度。该系统在定位方面，改进了参考点排序算法，以提升定位精度；在指纹更新方面，利用LDPL模型和基于Matern核的GPR算法在线进行指纹自更新，以避免线下指纹库更新的繁琐。根据相关分析及实验结果表明：

1)所提出的基于模糊思想的参考点排序算法，考虑了WiFi自身的动态特性。相较于传统的定位算法(KNN和WKNN)，该算法能够提升25%以上的定位精度。

2)所提出的指纹更新算法利用Matern核更好地刻画了参考点坐标和RSS之间的非线性关系，且使用LDPL模型克服了Zero-GPR的零均值问题。相较于已有的指纹更新算法，该算法能够提升34%以上的指纹还原精度。

在未来的工作中，将探索不同的长度参数β对于定位结果的影响，以及尝试寻找合适的参数自适应确定方法。