基于稀疏指纹采集和改进WKNN的定位算法

李新春，王 欢

(1.辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105；2.辽宁工程技术大学 研究生院，辽宁 葫芦岛 125105)

0 引 言

随着物联网的发展和日益普及，基于位置服务的相关技术成为人们日常工作、生活的基本需求。在室外环境中，GPS可实施高精度定位，但在室内环境中，基于Wi-Fi位置指纹定位算法更具优势[1]。这种定位算法无需添加硬件、成本低、应用广泛，但仍面临着指纹采集工作量大、定位精度低的问题[2]。

位置指纹定位算法包括2个阶段：离线阶段和在线阶段。离线阶段，在参考点上逐一采集来自各接入点(access point，AP)的接收信号强度(received signal strength，RSS)，组成有序RSS向量，同其位置坐标构成位置指纹，存入指纹库中；在线阶段，定位目标实时采集RSS向量，并由匹配算法与指纹库中的指纹进行相似度匹配，最后计算定位位置。

在现有的研究中，对位置指纹定位算法的改进主要集中在基于空间和时间的信号模式、协作定位和运动辅助定位，但构建位置指纹库是不可避免的过程，那么降低现场指纹勘测开销成为亟待解决的问题[3]。文献[4-6]无需指纹现场勘测，利用众包方法将位置指纹与用户移动踪迹相结合构建逻辑平面图，通过匹配逻辑平面图和实际平面图来实现定位，该方法需要志愿者用户报告他们的数据，但非专业的勘测数据通常受到质疑，且会产生大量的冗余数据；文献[7-8]通过现场勘测获得部分指纹信息，利用地质学插值算法对其他指纹进行预测，由稀疏采集的指纹数据构建密集的指纹库，但插值算法要求区域化变量(RSS变量)满足二阶平稳，要求严格。

通过上述分析，本文考虑到现场勘测指纹数据的可靠性及RSS向量的非线性特征，以减少指纹采集工作量、提高定位精度为目标，利用机器学习的自主学习能力，提出基于稀疏指纹采集和改进WKNN的定位算法。离线阶段，稀疏采集指纹数据，训练优化的高斯过程回归模型，对未采集的指纹数据进行预测，构建密集指纹库；在线阶段，改进WKNN算法，用卡方距离代替欧氏距离计算RSS相似度，并根据各AP稳定性赋予不同的权值。实验结果表明，与其他算法相比，本文算法具有良好的指纹预测能力及定位性能，适用于室内静态定位。

1 基于稀疏指纹采集构建指纹库

基于稀疏指纹采集构建指纹库，需要以下几个步骤：指纹预处理、训练指纹预测模型、优化模型参数、指纹预测、构建指纹库。

由于传播过程中RSS易受影响，本系统采用容错四分位算法[9]检测RSS异常值并滤除，对指纹数据进行预处理；将定位区域内的参考点分成两部分：①稀疏分布于定位区域内，将其指纹数据作为高斯过程回归模型的训练集；②作为测试集，此设置要求两部分参考点不重叠；将训练集和测试集输入至模型中，利用训练集训练模型，并对测试集进行指纹预测；模型参数直接影响模型的预测能力，本文利用共栖生物搜索算法优化模型参数，以下小节分别介绍算法的具体实现过程。

1.1 高斯过程回归

高斯过程回归(Gaussian process regression，GPR)是机器学习的一种回归方法，具有严格的统计学习理论基础，与神经网络、支持向量机相比，易实现、超参数自适应获取以及输出具有概率意义，对于处理非线性复杂问题具有良好的适应性[10]。

高斯过程为随机过程，任何有限数量集合f(x)服从联合高斯分布。D={(x,y)|x∈Rn×d,y∈Rn}为训练集，其中，x=[x1,x2,…,xn]T为训练输入，y=[y1,y2,…,yn]T为输出，训练输入集合服从n维高斯分布，其概率函数用GP表示，性质由均值函数m(x)和协方差函数k(xi,xj)确定。为不失一般性，令均值为零，有f(x)～GP(0,k(xi,xj))[11]。

GPR把系统噪声ε考虑其中，回归模型为

yi=f(xi)+ε

(1)

ε具有独立性，则y也属于高斯过程。在给定训练集D中，可以得到目标输出y的先验分布为

(2)

对于测试集D*={(x*,y*)|x*∈Rd,y*∈R}，其中，x*为测试输入；y*为测试输出，则训练输出y和测试输出y*的联合先验分布为

(3)

(3)式中，协方差矩阵为

K**=k(x*,x*)

协方差矩阵定义式中：K表示训练输入x的n×n阶协方差矩阵；k(xi,xj)为核函数，描述xi与xj的相关性；K*表示训练输入x与测试输入x*的1×n阶协方差矩阵；K**表示测试输入x*自身的协方差矩阵。

本文采用最常用的平方指数核函数描述不同位置xi与xj间RSS的相关性[12]为

(4)

根据贝叶斯后验概率公式，在已知测试输入x*与训练集D的条件下，对应的输出y*满足

(5)

(6)

(7)

超参数的取值直接影响模型的预测能力，传统超参数求解方法为共轭梯度法，但该方法在优化过程中过于依赖初值，容易陷入局部最优[13]。本文利用共栖生物搜索算法代替共轭梯度法优化超参数，将最优超参数回代入(6)式即得到指纹预测模型。

1.2 共栖生物搜索算法优化GPR超参数

1.2.1 共栖生物算法

2014年，Min Yuan Cheng等提出一种新颖的生物启发式算法——共栖生物搜索(symbiotic organisms search，SOS)算法。与其他生物启发式算法相比，SOS算法不需要任何特定参数，正是由于这一特点，陷入局部最优而出现早熟的可能性很小，得到全局最优的可能性很大[14-15]，非常适合参数优化。本文利用SOS算法优化超参数，模拟生态系统中物种的3种共栖关系，通过物种间交互规则产生新物种，搜索并保留具有最强生存能力的物种。

设生态系统的物种数量为N。第1种共栖关系为互利关系，指2个随机物种Xi，Xj均能通过交互规则产生新生物种，可以由(8)—(10)式表示为

Xinew=Xi+rand(0,1)×(Xbest-M×BF1)

(8)

Xjnew=Xj+rand(0,1)×(Xbest-M×BF2)

(9)

(10)

(8)—(10)式中：Xi,Xj为原始物种；Xinew,Xjnew为新生物种；Xbest为最优物种；rand(0,1)表示在(0,1)的随机数；BF1,BF2为受益因子，通常为1或2；M为物种Xi,Xj间关系特征。

第2种共栖关系为共生关系，指2个随机物种Xi,Xj中只有一个物种Xi能通过交互产生新生物种。该交互规则为

Xinew=Xi+rand(-1,1)×(Xbest-Xj)

(11)

第3种共栖关系为寄生关系，指生态系统中随机一个物种Xi充当寄生物，利用随机数更改维度产生新生寄生物，新生寄生物与物种Xj竞争生存。

1.2.2 适应度函数

SOS算法优化GPR超参数的适应度函数为训练集和待优化参数构成的对数似然函数对超参数的偏导数，其表达式为

(12)

适应度函数值最小的物种为最优物种，其对应的超参数即为最优超参数，比较新生物种与原始物种的适应度函数值可以表示为

(13)

1.2.3SOS算法优化GPR超参数

SOS算法优化GPR超参数的过程如下。

1)SOS算法初始化：随机生成N个d维数组作为物种的初始值X={X1,X2,…,XN}；迭代次数记t=0，设置最大迭代次数tmax；

2)计算各物种初始值的适应度函数，选择函数值最小的物种作为生态系统的最优物种Xbest；

3)令Xi=Xbest，增加迭代次数t=t+1；

4)互利阶段：随机物种Xj与Xi交互产生新生物种，计算新生物种的适应度函数值，与原始物种比较，保留最小函数值的物种；

5)共生阶段：随机物种Xj按交互规则使Xi产生新生物种，对比新生物种与原始物种的适应度函数值，保留最小函数值的物种；

6)寄生阶段：随机物种Xj作为寄生物，通过随机数更改维度产生新生寄生物并计算其适应度函数值，保留具有最小适应度函数值的物种；

7)搜索当前生态系统的最优物种Xbest；

8)判断是否达到tmax，若是，进行步骤9，若否，回到步骤3)继续迭代；

9)显示最优物种Xbest。

最优物种对应的超参数即为最优超参数，基于最优超参数得到SOS-GPR的预测模型，输入定位区域内非参考点的位置，预测对应位置上的RSS后，构建指纹存入指纹库中。

2 改进WKNN算法

在WKNN算法中，定位目标RSS向量与各参考点RSS向量之间的欧氏距离只能表示它们之间的绝对距离。因RSS易受环境变化的影响，绝对距离并不能反映定位目标与参考点之间的实际位置，需用相对距离来表示它们位置上的相似性，而卡方距离能够很好地体现特征量之间的相对距离。

用卡方距离(chi-square distance，CSD)描述定位目标与第i个参考点上接收来自第j个AP的RSS的相似度[16]有

(14)

(14)式中：RSSj为定位目标上接收第j个AP的RSS；rssij为第i个参考点上接收第j个AP的RSS。

用卡方距离代替欧氏距离，体现定位目标与各参考点上接收来自各AP的RSS之间的相对关系，接下来考虑AP加权问题。在位置指纹定位中，AP的稳定性影响定位结果，本文基于卡方距离对不同AP赋予不同的权值。

方差可以判别每个AP的稳定性，RSS方差较小表示该AP的稳定性较好，应赋予较大的权值。计算AP的RSS方差公式为

(15)

那么，第j个AP的RSS对应的权值vj及定位目标与各参考点的相对距离disti为

(16)

(17)

(17)式中，Dij为定位目标与第i个参考点接收来自第j个AP的RSS的卡方距离。

将相对距离disti升序排列，取前K个参考点进行位置估计的表达式为

(18)

(19)

3 实验与结果分析

3.1 实验准备

于辽宁工程技术大学行政楼一楼进行实验，该区域包括办公室、走廊、大厅，如图1。实验环境内有大厅装饰物、立柱等障碍物。本文将实验区域分成实验区域1和实验区域2，分别进行指纹预测实验和定位实验。实验过程均使用荣耀8手机作为数据采集移动终端，运行系统为Android 4.4，实验仿真在MATLAB R2013b上完成。

图1 实验区域布局Fig.1 Layout of the experimental area

为验证本文基于稀疏指纹采集建库方法的有效性，取大厅中面积为20 m×8 m的典型环境为实验区域1，将该区域划分成边长为1 m的网格，参考点布设于网格中心位置，在其四角和中心位置布设5个蓝牙beacon基站AP1—AP5，对该区域内160个参考点逐一作AP1—AP5的RSS采集，每个参考点上采集100次，并对采集到的数据进行预处理。

3.2 实验与结果分析

3.2.1 指纹预测实验与结果分析

对于SOS-GPR指纹预测模型来说，若定位区域内所选参考点数量过少，训练数据无法对整体数据分布进行估计，常常会导致过拟合，模型泛化能力差；若参考点数量过多，又违背了本文减小指纹采集工作量的初衷。所以，为找到最优训练数据数量，在实验区域1中均匀选择40,60,80,100,120个参考点作为模型训练点，其余120,100,80,60,40个参考点作为模型测试点，共同输入SOS-GPR模型预测RSS，计算估计误差[8]可以表示为

(20)

图2为SOS-GPR模型在不同训练点数量下的RSS估计误差，为了验证本文指纹预测模型的性能，将其与克里金(Kriging)算法、文献[8]的改进克里金(SA-Kriging)算法进行实验对比。

图2 不同训练点数的指纹估计误差Fig.2 Fingerprint estimation errors of different training node numbers

由图2可看出，随着训练点数量增加，3种指纹预测方法的估计误差都在减小。当训练点数量为80时，SOS-GPR，SA-Kriging，Kriging算法预测指纹的估计误差分别为3.8%，4.9%，5.8%，此时指纹采集工作量为传统全采集法的50%；当训练点数量继续增加，SOS-GPR的估计误差几乎不再减小，而SA-Kriging算法在训练点数为100时估计误差达到3.9%，此时采集工作量为传统全采集法的62.5%。

实验区域1内选取25个定位目标进行定位实验，定位匹配阶段采用传统WKNN算法，考虑到最近邻点选择太多，其中可能掺杂着实际距离较远的“假最近邻点”，且K值一般选取3或4[17]，故本文设置K=3。图3为基于不同训练点数的定位误差与全采集法定位误差的对比。

图3 不同训练点数的定位误差Fig.3 Positioning errors of different training node numbers

由图3可知，当训练点数达到80时，基于SOS-GPR建立指纹库的定位精度最先趋于全采集法的定位精度，随着训练点数的继续增加，其定位误差几乎不变。考虑尽量减小指纹采集量，且估计误差在可接受范围内，本文选择全采集法50%的参考点训练SOS-GPR模型并建立指纹库。

为了验证更大区域内基于SOS-GPR建库方法的效果及改进WKNN算法的定位性能，本文在实验区域2进行定位实验，包括大厅和走廊的实验环境。在实验区域均匀布设150个参考点，参考点间距为2 m，通过稀疏指纹采集和SOS-GPR算法构建指纹库。但为了检验算法的性能，通过全采集法采集300个参考点的指纹数据建立另一个指纹库，此时参考点间距为1 m，并在定位区域选取55个定位目标，验证定位算法的性能。利用楼内WLAN基础设施，移动终端可检测到22个AP，这些AP的类型和位置未知。当在参考点上无法检测到某AP的RSS时，设置其RSS值为-95 dBm。

对于AP现存的问题：受多径效应影响严重的AP稳定性差，可能导致定位精度下降；参与定位的AP数越多计算量越大。为了提高定位精度同时减小计算开销，通过RSS方差选择n个稳定性好的AP参与定位。分别统计定位区域内参考点上来自各AP的RSS值并计算每个AP的RSS方差，RSS方差越小表示各参考点上检测到来自AP的RSS值偏离其平均值越小，该AP的稳定性越好，适合于定位匹配，否则表示该AP稳定性差，不应参与定位匹配。确定适合参与定位的AP后，在线阶段对定位目标进行特定AP的RSS选择，形成RSS向量与指纹库中的指纹进行定位匹配。

为确定参与定位的最佳AP数，基于全采集法构建的指纹库计算各AP的RSS方差并按升序排列，取前n个AP进行实验，对比不同AP数(3～22)对定位精度的影响，实验结果如图4，定位匹配阶段本文依然选择WKNN(K=3)算法。

图4 不同AP数量的定位结果对比Fig.4 Positioning accuracy comparison of different APs

由图4可看出，当参与定位的AP数在3～12时，随着AP数增加，定位误差减小；当AP数为12时，定位误差最小2.021 m；但AP继续增加，定位误差不再减小，甚至出现增大，例如，AP数为14或16时对应的定位误差分别为2.078 m和2.113 m。虽然每个AP都能提供位置信息，但并不是参与定位的AP数越多定位效果越好，稳定性好的AP对定位贡献较大，而稳定性弱的AP反而会影响定位精度，本文选取前12 个AP参与定位。

表1 不同超参数取值对指纹估计误差的影响

3.2.2 定位实验

表2展示了3种指纹库，它们的区别在于参考点个数：库1以稀疏全采集法采集了150个参考点；库2在库1的数据基础上由SOS-GPR预测了150个参考点，库2共有300个参考点；库3以密集全采集法采集了300个参考点。

表2 3种位置指纹库

为验证改进算法的定位性能，选取参与定位的AP 数为12，WKNN算法中K值为3，将基于卡方距离和AP加权的WKNN算法(WKNN algorithm based on chi-square distance and AP weighting,CSW-WKNN)、传统WKNN算法、基于卡方距离改进的WKNN算法(WKNN algorithm based on chi-square distance,CS-WKNN)以及文献[18]的M-WKNN(modified-WKNN matching algorithm)算法进行基于表2中3种指纹库的定位仿真，图5为4种算法定位结果的比较。

经过仿真实验，CSW-WKNN算法的定位误差均比其他3种算法低。在库1、库2、库3中，CS-WKNN算法在1.5 m时定位精度累计概率分别为36.3%，47.2%和45.4%，分别高出传统WKNN算法10.9%，12.7%和12.7%，表明卡方距离比欧氏距离对环境噪声的敏感度低；在库1、库2、库3中，CSW-WKNN算法在1.5 m定位精度累计概率分别为56.3%，72.7%，67.2%，分别高出CS-WKNN算法20%，25.5%，21.7%，高出M-WKNN算法9.1%，16.4%，14.6%，表明加权AP对定位结果具有影响。

图6为库1、库2、库3中4种定位算法在累积概率分别为30%，50%，80%时所对应的定位误差。

图5 4种算法定位精度对比Fig.5 Comparison of four algorithms positioning accuracy

由图6可看出，库2、库3的定位误差均小于库1，表明在定位区域内参考点布设密集程度对定位结果具有影响；库2与库3定位精度相近，表明基于SOS-GPR建立指纹库的方法具有可行性；库2的定位精度略高于库3的原因在于边界位置指纹采集的RSS易受外界因素的影响，而本文的指纹预测模型考虑了噪声影响因素，故边界区域预测的指纹较采集到的指纹具有稳定性。

图6 定位误差对比Fig.6 Comparison of positioning errors

在库1、库2、库3中CSW-WKNN算法的平均定位误差分别为1.514 m，1.091 m，1.181 m，相较于M-WKNN的1.745 m，1.482 m，1.469 m提高了13.23%，26.32%，19.61%。实验环境存在的多径效应影响定位精度，本文的CSW-WKNN算法利用卡方距离表示定位目标与参考点位置的相似度，降低信号对环境的敏感性，对不同AP赋予不同权值提高定位精度。

4 结束语

针对位置指纹采集工作量大及定位精度低的问题，本文提出了基于稀疏指纹采集和改进WKNN的定位算法。离线阶段，将定位区域内稀疏参考点上采集的RSS进行预处理，利用预处理后的指纹数据训练GPR模型，为提高模型的泛化能力，采用SOS算法优化模型超参数；最后SOS-GPR模型预测非参考点上的RSS，实现由稀疏指纹数据构建密集指纹库。在线阶段，将WKNN算法中表示定位目标RSS与参考点RSS相似度的欧氏距离换为卡方距离，并对各AP根据其RSS方差赋予不同的权值。实验结果表明，基于SOS-GPR算法在参考点个数为全采集法50%的情况下即能得到与之相近的定位精度，且改进WKNN算法能进一步减小定位误差。

SOS-GPR指纹预测模型减少了指纹采集工作量，所付出的代价是构建指纹库阶段计算量的增加，但指纹预测模型的训练数据是经过预处理的，减少了原指纹采集过程中会因环境变化等外界因素产生RSS异常值的情况，提高了指纹库的可靠性。