基于改进WKNN 的蓝牙室内定位方法

沈天盛，陈文莹，朱彬斌，王 燕，周勇良，艾 青

（1.国网上海市电力公司，上海 200122；2.上海电力大学，上海 201306）

0 引 言

随着人工智能和移动通信技术的高速发展，定位技术[1]也得到了空前关注，尤其是以全球定位系统（Global Positioning System, GPS）[2]为基础的室外定位技术渗透在了人们日常生活的方方面面。相较于日趋完善的室外定位技术，室内定位技术的发展则稍显逊色。目前主流 的 室 内 定 位 技 术 主 要 有WiFi[3]、UWB[4]、RFID[5]、ZigBee[6]、蓝牙[7]等，但这些技术各有优缺点[8]，比如UWB技术定位精度最高，但硬件成本也过高，不适于推广；WiFi 技术成本低但定位精度尚待改进；蓝牙技术作为近几年来不断兴起的室内定位技术，尤其是低功耗蓝牙技术[9]不仅功耗低续航能力强，而且便于部署，受到室内定位研究领域的热捧。综合以上发展现状，本文选择将传统基于WiFi 技术的定位算法与低功耗蓝牙定位技术相结合的方式，对现有室内定位算法进行改进。

蓝牙定位可分为基于测距和非测距（指纹）两大类。基于测距的室内定位方法涉及到信号发射器和接收器设备，所要定位的设备通常是人（或智能手机），通过估计其与室内部署的其他发射器/接收器设备的距离（范围）来获得定位信息，常用的方法有基于到达时间（TOA）[10]、到达时差（TDOA）[11]、到达角度（AOA）[12]；基于非测距的室内定位方法不需要连续估计信号发射和接收设备之间的距离，仅根据信号接受强度值RSSI 来实现数据库的构建和定位匹配[13]，常用的方法是基于指纹的定位方法。

本文采用基于指纹的定位方法，利用低功耗蓝牙信标建立RSSI 数据库，提出一种将欧氏距离与曼哈顿距离融合，对WKNN 算法中的权值进行改进的方法，并且利用粒子群滤波对WKNN 算法得出的定位结果进行优化。实验结果表明，本文的改进WKNN 算法具有较好的定位性能，结合粒子群滤波算法可滤除跳变较大的位置点，使预测轨迹更贴合真实轨迹。

1 基于RSSI 指纹数据库的定位方法

基于RSSI 指纹数据库的匹配定位技术分为两个阶段[14]：离线数据采集阶段和在线数据匹配阶段。离线数据采集阶段即建立数据库阶段，采集前将实验场景划分为网格构建位置坐标，从而进行每个坐标点的位置坐标和RSSI 数据的采集[15]；将位置坐标和不同接入点即预定位点（Access Point, AP）对应的RSSI 数据组成向量储存在数据库中，即实现了参考点的数据收集工作。在线数据匹配阶段，通过蓝牙信标实时收集待测人员在不同位置时的RSSI 数据。根据匹配定位算法将实时采集到的数据与数据库中的已有数据集进行相似度匹配。再将匹配点通过均值、加权等方法确定最终要输出的定位点坐标，实现待测人员位置的预测。

从早期的NN 算法（Nearest Neighbour, NN）到K 近邻算法（K Nearest Neighbour, KNN），再到现在的加权K近邻算法（Weighted K Nearest Neighbour, WKNN），定位技术不断发展，但算法原理都是以欧氏距离作为指纹数据相似度的标准进行定位匹配。也有学者[16]提出用曼哈顿距离取代欧氏距离对相似度标准进行改进，并取得一定成效。

欧氏距离和曼哈顿距离表示的都是两个指纹向量之间的绝对距离，只是在计算方法上有所不同，欧氏距离的计算公式为：

曼哈顿距离的计算公式为：

式中：(x1,y1)为参考点1 的坐标；(x2,y2)为参考点2 的坐标；d为欧氏距离；m为曼哈顿距离。

离线数据采集阶段，假设共有i个参考点，n个AP，则利用欧氏距离表示待定位人员和参考点之间的相似度的公式为：

利用曼哈顿距离表示的待定位人员与参考点之间的相似度公式为：

式中：Tij为实验场景中第i个参考点上采集到的第j个AP 的RSSI 数值；Uj为在待定位人员的位置上采集到的第j个AP 的RSSI 数值。

在线数据匹配阶段，传统的定位算法通过比较欧氏距离即相似度的大小来计算匹配程度，即相似度数值越大，匹配程度越高，越接近真实位置。

早期的NN 算法通过将计算出的待定位点与数据库中的每个参考点之间的相似度数值进行由大到小排列[17]，选出匹配程度最高的数值对应的参考点坐标作为待定位点坐标。但是这种方法只能进行粗略定位，与真实位置存在一定的误差。

KNN 算法对NN 算法进行了改进。由于RSSI 受环境影响较大，仅用一个指纹来表示待测点的坐标会带来非常大的定位误差，因此，KNN 算法取匹配度最高的前k（k≥2）个参考点作为预定位点，通过求取这k个预定位点坐标的平均值来表示待定位点坐标，达到减小定位误差的目的。KNN 算法的计算公式为：

式中，(xi,yi)表示序号为i的参考点坐标。

随着时代的发展，人们对室内定位精度要求的不断提升，KNN 算法也无法满足人们的高定位精度需求，WKNN 算法应运而生[18]。WKNN 算法不再只是对k个指纹的坐标和求平均，而是依据k个指纹对待测点不同的贡献程度，给予这k个指纹k个权值。一般而言，贡献程度与计算得到的欧氏距离的大小成反比，即欧氏距离越小时，表示贡献程度越大，分配的权值w越大。WKNN 算法的计算公式为：

式中：wk为定位参考点的第k个权值；(xk,yk)为通过KNN 算法求得的待定位点坐标。

权值w的大小随参考点与待定位点之间的欧氏距离的变化而变化，是对定位精度起决定性作用的存在，w多取相似度数值的倒数，即：

当wi等于k时，即为KNN 算法。

2 基于改进WKNN 的蓝牙室内定位系统框架

本文提出一种改进WKNN 定位和粒子群滤波（Particle Filter, PF）的定位方法。系统主要包括RSSI 滤波模块、基于改进WKNN 的定位模块和粒子群滤波模块三部分。室内定位框图如图1 所示。

图1 室内定位框图

1）RSSI 滤波模块。室内环境复杂多变，信号在传播过程中受室内障碍物影响较大，导致低功耗蓝牙信标测得的RSSI 数据波动较大，若直接将测得的数据存入指纹数据库进行匹配定位，由此产生的定位结果与真实位置间会存在较大的定位误差。为减小此影响，本文采用一维卡尔曼滤波技术（Kalman Filtering, KF）[19]对原始采集到的RSSI 信号进行去噪处理。

2）基于改进WKNN 的定位模块。改进的WKNN定位算法由k值选取、w值选取和坐标计算组成，其中k值是由RSSI 数据集大小决定；w值直接影响到权值的计算。因此，k值和w值是影响WKNN 算法定位精度的关键因素，确定完k值和w值后就可以根据相关公式进行待测点坐标的计算。

3）粒子群滤波模块。利用粒子群滤波适合大数据量处理以及适合非线性系统的特点对定位算法获得的坐标进行优化处理，使预测轨迹更贴合真实行走轨迹。

2.1 改进的WKNN 定位算法

WKNN 定位算法中k值和w值的选取是影响精度的两个关键因素。在以往研究中，往往忽略了k值对定位精度的影响。k值大小应根据采集到的数据集大小而定，若k值过小，不仅会增加定位模型的复杂程度，而且也会受环境中的噪声干扰；若k值过大，会导致定位模型整体过于简单，使输出的定位结果准确度不高。因此，在实验中需要通过不断调整数据集的超参数来确定最合适的k值大小。

w值是待定位点与参考点之间的距离大小，即相似度的倒数，因此w值的选取最终取决于待定位点与参考点之间的距离。最常用的表征距离的方法是欧氏距离，但是在基于导航和地图的应用中，该方法表现理想化，和现实距离之间的差距较大，并且当计算出的欧氏距离相同时，欧氏距离就丧失了衡量指纹数据相似程度的功能。针对这种情况，有学者提出利用曼哈顿距离代替欧氏距离，曼哈顿距离具有更高的稳定性，能有效减小信号的波动性，从而降低定位误差。但是该算法也存在一定的局限性，即只有当信号的特征值差别不大时才适用，而且曼哈顿距离如果过大，会对其他特征间的临近关系造成掩盖影响。

对幼儿差异性的关注也是声势教学所要注意的问题之一。因为幼儿对音乐的理解程度各不相同，所以教师一定要关注幼儿的差异性，对不同的幼儿要用不同的方法来教学，比如说话的力度、语气等。对待那些理解能力较差以及注意力不集中的幼儿要有耐心。要按照幼儿的自身条件、兴趣爱好等来确定教学目标，因材施教，让幼儿能够主动参与到课堂学习中，增强幼儿学习的信心。

因此，本文提出一种融合曼哈顿距离与欧氏距离的方法对w值进行改进，即采用多次测量的方法，计算待定位点与每个参考点间的欧氏距离与曼哈顿距离的平均值，即匹配坐标的相似度，公式如下：

式中：n为AP 个数；t为在同一待定位点采集RSSI 数据的次数；di(q)为在第i个参考点上计算得到的第q次欧氏距离；mi(q)为第i个AP 采集的第q个RSSI 数据。则权值w的计算公式为：

待定位点坐标为：

式中：wi为第i个权值；(xi,yi)为序号为i的参考点坐标。

2.2 粒子群滤波

针对室内定位中数据量非常庞大且计算出的定位坐标中存在跳变幅度较大的问题，本文选取了粒子群滤波对最终计算出的定位结果进行进一步的过滤处理。粒子群滤波相较于传统的卡尔曼滤波，在大数据量下处理性能更优，并且粒子群滤波不仅满足卡尔曼滤波适用的线性系统，还适合对非线性系统进行处理[20]。具体而言，卡尔曼滤波是对系统做线性假设以及对后验概率做高斯假设时才适用，而粒子群滤波则无需以上约束条件。因此，无论是从可靠性还是普适性方面分析，粒子群滤波均优于卡尔曼滤波。

粒子群滤波对输出的定位结果进行优化处理的步骤如下：

1）初始状态。用大量粒子模拟运动状态，使粒子在空间内分布均匀[21]。

对于K=0：根据状态先验分布p(X0)建立初始状态粒子集，其中

对于k=1，2，…，K，从状态转移概率采样得到新的粒子集，即从状态转移概率分布上抽取N个独立样本。

3）校正（权值计算）阶段。对预测粒子进行评价（计算权重），越接近于真实状态的粒子，其权重越大。

权重计算公式如下：

进行归一化处理得：

4）重采样。根据粒子权重对粒子进行筛选[22]，筛选过程中，既要大量保留权重大的粒子，又要有一小部分权重小的粒子。即根据粒子的权重ω(ki)从粒子集重新抽取N个粒子，并令，建立新的粒子集

5）滤波。将重采样后的粒子代入状态转移方程得到新的预测粒子，即步骤2）。

3 算法流程

本文方法的室内定位流程如图2 所示，主要包括离线和在线两个阶段。在离线阶段，首先对RSSI 数据和采样点坐标进行采集，之后将采集到的RSSI 数据通过KF 进行平滑处理，最大程度上减小噪声带来的影响，最后保存好经KF 后的RSSI 数据，与采样点坐标一一对应好后完成指纹库的构建。待测人员所在位置的RSSI 数据采集完毕后，进入在线阶段，利用本文提出的改进WKNN 定位算法计算并输出待定位点坐标，再进行粒子群滤波，滤除跳动较大的定位点，保证预测轨迹较贴合真实轨迹，此时组成预测轨迹的各点坐标即为预测的待定位点坐标。

图2 本文方法室内定位流程

改进WKNN 定位算法的流程如图3 所示。首先，调整数据集大小确定预定位点（AP）个数，即k值；并根据实时采集到的RSSI 数据与指纹库中已有数据进行数据匹配，确定k个与真实位置最相近的指纹。接着，计算欧氏距离与曼哈顿距离，通过融合两距离确定相似度大小，从而计算权值w。最后，将计算得到的k值和w值代入式（10），实现待定位点坐标的输出。

图3 改进WKNN 算法流程

本文的室内定位算法通过离线阶段的数据采集和数据预处理完成了指纹数据库的搭建。尤其是利用卡尔曼滤波对采集到的数据进行去噪处理，提升了采集数据的质量，保证了数据的可靠性，为后面在线阶段输出高精度的定位结果奠定了基础。在线阶段通过改进的WKNN 算法对w值和k值的选取方法都进行了改进优化，并且对输出的定位结果又进行了粒子群滤波，过滤跳动较大的定位点，大大减少了定位误差。

4 实验分析

本文选取14 m×14 m 的区域搭建实验场景，四个角落分别有一间房间，如图4 所示。在此实验场景中共布置了5 个低功耗蓝牙5.1 信标作为信号发射装置，分别部署在四个房间房门上和实验区域中心位置，本文统一将信标部署在距地面1 m 位置。利用蓝牙探针和便携式计算机作为蓝牙信号接收和显示装置。

图4 实验场景图

由前文可知，k值的选取对最终的定位结果影响很大，而合理地选取k值是减小定位误差的有效方法。本文通过不断实验，得到k值的选取曲线，如图5 所示。最终确定当k值取29 时造成的定位误差最小、准确度最高。故本实验中AP 的个数为29。

图5 k 值的选取

k值确定后本文进行了3 组对比实验，分别是传统WKNN 算法、本文提出的经粒子群滤波后的改进WKNN算法（改进WKNN+PF）、经卡尔曼滤波后的改进WKNN算法（改进WKNN+KF），得出的轨迹与真实轨迹之间的比较结果如图6 所示。

由图6 可以看出：未经任何滤波处理的传统WKNN轨迹杂乱无章；经过本文对权值进行改进和增加离线阶段数据预处理，以及经过粒子群滤波的WKNN+PF 算法的轨迹最贴合原始轨迹；改进WKNN+KF 算法得出的轨迹与真实轨迹间的贴合程度介于传统WKNN 和本文算法之间。

数据量与定位精度的关系曲线如图7 所示。由图7可见，数据量越大，定位精度越高。由前文论述可知，粒子群滤波更适合大数据量时的优化处理，因此，在对改进WKNN 算法进行优化的工作中，经粒子群滤波后的定位性能优于卡尔曼滤波。

图7 数据量与定位精度的关系

由表1 所示的不同定位算法间的定位精度对比结果可知，相较于传统的利用欧氏距离计算权值的WKNN算法（传统WKNN），本文提出的通过融合曼哈顿距离与欧氏距离并经过数据预处理与粒子群滤波优化处理的改进算法的定位精度得到了显著提升，大约提高40 cm。对于经过不同滤波技术的改进算法而言，经过了PF 处理后的本文算法定位精度比经过KF 处理后的改进WKNN+KF 算法精度提升了约4 cm。

表1 不同定位算法间的定位精度对比

5 结 语

本文首先通过低功耗蓝牙定位模块在超低功耗下进行RSSI 数据的采集；再结合卡尔曼滤波算法减小室内复杂环境的干扰，平滑采集到的原始RSSI 数据，提高数据的可靠性。接着，通过融合曼哈顿距离和欧氏距离代替传统的欧氏距离，对传统WKNN 算法计算权值的方法进行改进，克服了欧氏距离不适用于非线性系统的缺点，提高定位精度的同时也大大提高了改进算法的普适性。最后，通过比较粒子群滤波与卡尔曼滤波对输出定位结果的优化效果，得出粒子群滤波的优化效果更好，定位精度更高，更贴合真实轨迹的结论。因此，本文提出的改进WKNN 算法在室内定位领域具有一定的应用价值，尤其适用于大型商超和地下停车场等公共场合。