基于MWKNN-PF的两阶段室内蓝牙定位方法

Two⁃stage indoor bluetooth localization method based on MWKNN⁃PF

摘要

针对蓝牙行人定位中加权K近邻（WKNN）算法存在指纹匹配计算负荷大、定位精度受固定K值影响等问题，提出了一种改进的WKNN（Modified WKNN，MWKNN）算法，用于目标的初始定位。为进一步提高定位精度，又引入粒子滤波算法，将MWKNN算法的初始定位结果作为观测值对粒子进行更新，最终实现目标位置的精确估计。实验结果表明，所提出的MWKNN-PF算法与WKNN算法相比，定位精度提高了41.8%，计算时间减少59.6%，所提算法可为相关应用场景提供更精确、实时的室内行人定位服务。

Abstract

To address the issues of the high computational load for fingerprint matching and the dependence of positioning accuracy on the fixed K valuein the weighted K-nearest neighbor （WKNN） algorithm for bluetooth pedestrian localization， a modified WKNN （MWKNN） algorithm is proposed for the initial localization of the target. To further enhance positioning accuracy， a particle filtering algorithm is introduced， using the initial localization resultsfrom the MWKNN algorithm as measurement values to update the particles，and ultimately achieves precise target localization. Experimental results indicate that the proposed MWKNN-PF algorithm improves positioning accuracy by 41.8% and reduces computation time by 59.6%. This algorithm provides more accurate and real-time indoor pedestrian localization for related applications.

Graphical abstract

关键词

室内定位 / 蓝牙指纹 / K均值聚类 / 加权K近邻 / 粒子滤波

Key words

indoor localization / bluetooth fingerprint / K-means clustering / weighted K-nearest neighbor / particle filtering

0 引 言

蓝牙硬件成本低廉，且在移动设备中普及率高，因此，被广泛应用于室内位置服务。蓝牙定位主要分为测距定位和指纹定位两类^［1］。测距定位通过测量标签与多个基站之间的信号接收强度（RSSI）估算距离，并利用三边定位法将位置估计问题转化为一个非线性最小二乘问题。受室内信号多径效应及非视距传播等因素影响，测距定位在实际应用中误差较大^［2］。指纹定位无需估算距离，仅根据RSSI值实现数据库构建和定位匹配，因此被广泛采用。

国内外针对指纹定位展开了大量研究。加权K近邻（Weighted K-nearest neighbor， WKNN）是指纹定位中的常用算法。然而，该算法需要遍历定位区域内的所有指纹点进行匹配，计算负荷较大。同时，由于蓝牙信号覆盖不均匀，采用固定的K个指纹点进行位置估计易导致指纹点误匹配，进而引起估计位置跳动和突变^［3］。为提升定位精度，相关研究主要集中在指纹库优化、最佳K值选择以及指纹权值设定等方面。指纹库优化的方法包括设置区域约束^［4］或对指纹点进行聚类分区^［5］。针对K值的选择，王轩等^［6］提出一种基于离群因子检测的自适应动态K值获取方法，解决了可能出现的指纹误匹配问题。在指纹匹配权值设定方面，梁哲豪等^［7］提出了改进加权欧氏距离度量的权值设定方法；顾亚雄等^［8］引入贝叶斯估计算法，将各指纹点的后验概率作为其权值。上述方法虽在一定程度上提升了定位精度，但并未考虑指纹信息内部特征间的差异性。基于机器学习的指纹定位方法^［9，10］近年来备受关注。机器学习能够较好捕捉RSSI与坐标位置之间的复杂非线性关系，但其模型训练成本高昂，且对环境变化敏感，这些问题仍有待解决。此外，将指纹定位与卡尔曼滤波^［11］、粒子滤波算法^［12］等滤波算法融合是提高定位精度的又一手段。这类方法常用惯导单元提供状态转移模型所需的参数。与单一的指纹定位相比，融合算法能显著改善定位精度。

本文以基于蓝牙的室内行人定位为研究对象，针对WKNN算法所存在的局限性，以提升定位精度和降低计算负荷为目标对其进行改进，并将改进后的WKNN算法与粒子滤波算法融合，提出一种包含初始定位和精确定位的两阶段定位方法。同时，结合定位试验，评估所提方法的性能，以期为提高室内环境下的行人位置服务质量提供可行方案。

1 基于RSSI的蓝牙指纹定位

1.1　蓝牙指纹定位基本原理

指纹定位的基本原理是计算测量数据和数据库中参考指纹的差异，并得到最相似的匹配结果。指纹定位通常分为离线阶段和在线阶段。假设室内环境中布设了n个蓝牙基站和m个指纹点。在离线阶段，在每个指纹点上采集来自各基站的RSSI数据，形成RSSI向量，记为：

RSS{I}_i=\left(RSS{I}_{i\mathrm{1}},RSS{I}_{i\mathrm{2}},\cdots ,RSS{I}_{in}\right)

式中：i（i=1，2，…，m）为指纹点的序号；RSS{I}_{in}为在第i个指纹点上采集的第n个基站的RSSI。

对每个指纹点上采集的RSSI数据与其位置坐标结合，形成指纹，记为：

\mathit{F}{\mathit{P}}_i=\left[x_i,y_i,RSS{I}_{i\mathrm{1}},RSS{I}_{i\mathrm{2}},\cdots ,RSS{I}_{in}\right]

式中： \mathit{F}{\mathit{P}}_i为指纹点F{P}_i的指纹信息；\left(x_i,y_i\right)为第i个指纹点的位置坐标。

将所有指纹点信息按行向量形式存储至数据库中，建立指纹库，如下：

\mathit{F}\mathit{P}=\left[\begin{array}{c}\mathit{F}{\mathit{P}}_{\mathrm{1}}\\ \mathit{F}{\mathit{P}}_{\mathrm{2}}\\ ⋮\\ \mathit{F}{\mathit{P}}_m\end{array}\right]=

\left[\begin{array}{c}{x}_{\mathrm{1}},\\ x_{\mathrm{2}},\\ ⋮\\ x_m,\end{array}\begin{array}{c}{y}_{\mathrm{1}},\\ y_{\mathrm{2}},\\ ⋮\\ y_m,\end{array}\begin{array}{c}RSS{I}_{\mathrm{11}},\\ RSS{I}_{\mathrm{21}},\\ ⋮\\ RSS{I}_{m\mathrm{1}},\end{array}\begin{array}{c}RSS{I}_{\mathrm{12}},\\ RSS{I}_{\mathrm{22}},\\ ⋮\\ RSS{I}_{m\mathrm{2}},\end{array}\begin{array}{c}\dots ,\\ \dots ,\\ \\ \dots ,\end{array}\begin{array}{c}RSS{I}_{\mathrm{1}n}\\ RSS{I}_{\mathrm{2}n}\\ ⋮\\ RSS{I}_{mn}\end{array}\right]（1）

在线阶段，通过移动终端上的蓝牙信标实时采集待测点上各基站的RSSI数据，并利用指纹匹配算法将采集的RSSI数据与指纹数据库中的RSSI数据进行相似度匹配，最终输出待定点的位置坐标。

1.2　加权K近邻算法

假设在待测点上采集得到的RSSI数据记为\mathit{r}\mathit{s}\mathit{s}\mathit{i}=\left[rss{i}_{\mathrm{1}},rss{i}_{\mathrm{2}},\cdots ,rss{i}_n\right]。在线阶段，WKNN算法首先利用RSSI欧氏距离评价待测点与指纹点的相似度。距离越小，相似度越高。待测点与第i个指纹点的RSSI欧氏距离计算公式为：

D_{E,i}=\sqrt[]{{{\displaystyle \sum _{j=\mathrm{1}}^n}\left(rss{i}_j-RSS{I}_{i,j}\right)}^{\mathrm{2}}}（2）

式中：RSS{I}_{i,j}为第i个指纹点上来自第j个基站的RSSI值。

对所有欧氏距离按升序排序，选择前K个相似度最高的指纹点作为近邻指纹点，各近邻指纹点的权重设置如下：

w_i=\frac{\mathrm{1}/D_{E,i}}{{\displaystyle \sum _{i=\mathrm{1}}^K}\mathrm{1}/D_{E,i}}（3）

式中：i为所选K个近邻指纹点的序号。

最终，待定点的位置坐标计算如下：

\left(x,y\right)={\displaystyle \sum _{i=\mathrm{1}}^K}{w}_i\left(x_i,y_i\right)（4）

WKNN算法需计算待定点与指纹库中所有指纹点的RSSI欧氏距离，即每次定位均需遍历所有样本数据。当指纹库数据量较大或指纹维度较高时，将带来较大的计算负荷，影响定位实时性。同时，WKNN算法的定位精度在很大程度上受K值选择的影响。使用固定K值会降低算法对定位环境变化的适应能力。该算法基于RSSI欧氏距离设置权重，未考虑各基站RSSI特征的差异，易引入较远指纹点，导致定位误差增大。

2 MWKNN-PF算法

本文提出一种基于MWKNN-PF的两阶段室内定位方法。该方法包括基于信号-坐标双因子相似度的K-means （DFS-K-means）聚类指纹库构建模块、基于MWKNN的初始定位模块和基于粒子滤波的定位优化模块。

2.1　基于DFS-K-means聚类的指纹库构建

首先将定位区域划分为等间距网格，确定指纹数据库的采样点，然后在各指纹点进行一定次数的RSSI数据采集，并计算其均值和协方差。假设在第i个指纹点处进行了N次数据采集，则该指纹点RSSI向量表示为：

\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_i=

\left[\frac{{\displaystyle \sum _{k=\mathrm{1}}^N}RSS{I}_{i,k}^{\mathrm{1}}}{N},\frac{{\displaystyle \sum _{k=\mathrm{1}}^N}RSS{I}_{i,k}^{\mathrm{2}}}{N},\cdots ,\frac{{\displaystyle \sum _{k=\mathrm{1}}^N}RSS{I}_{i,k}^n}{N}\right]（5）

式中：RSS{I}_{i,k}^n为第i个指纹点上第k次数据采集所得到的第n个基站的RSSI值。

由于各指纹点上的数据采集过程相互独立，第i个指纹点RSSI值的协方差矩阵可表示为对角矩阵形式如下：

{\mathit{S}}_i=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\left({\sigma }_{i,\mathrm{1}}^{\mathrm{2}},{\sigma }_{i,\mathrm{2}}^{\mathrm{2}},\cdots ,{\sigma }_{i,n}^{\mathrm{2}}\right)（6）

式中：{\sigma }_{i,n}^{\mathrm{2}}为在第i个指纹点上的第n个基站的RSSIRSSI方差。

{\sigma }_{i,n}^{\mathrm{2}}=\frac{\mathrm{1}}{N-\mathrm{1}}{\displaystyle \sum _{j=\mathrm{1}}^N}{\left(RSS{I}_{i,j}^n-\frac{\mathrm{1}}{N}{\displaystyle \sum _{k=\mathrm{1}}^N}RSS{I}_{i,k}^n\right)}^{\mathrm{2}}（7）

在数据采集的同时，记录指纹点位置坐标，将RSSI数据、协方差矩阵及相应的指纹点坐标存入指纹库。为了提高后续在线定位阶段指纹匹配的可靠性并降低计算负荷，本文对K-means聚类算法进行改进，提出了一种DFS-K-means聚类算法，用来对离线指纹数据进行聚类划分。

首先从m个指纹点中随机选择q个指纹点作为聚类中心，然后计算剩余的m-q个指纹点与这q个聚类中心的相似度。为了提高指纹点间聚类的准确性，本文考虑了接收信号强度和位置坐标两种因子，利用RSSI马氏距离与坐标间的欧氏距离的乘积作为指纹点与聚类中心相似度度量参数，公式如下：

S\left(F{P}_A,F{P}_B\right)=-D_M\left(\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_A,\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_B\right)\times d_{AB}（8）

式中：S\left(F{P}_A,F{P}_B\right)为指纹点A和聚类中心B的相似度度量参数；d_{AB}为二者坐标间的欧氏距离；D_M\left(\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_A,\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_B\right)为二者RSSI值的马氏距离，定义为：

D_M\left(\mathit{R}\mathit{S}\mathit{S}\mathit{I}{}_A{}^{},\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_B\right)=

\sqrt[]{\left(\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_A-\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_B\right){\mathit{S}}^{-\mathrm{1}}{\left(\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_A-\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_B\right)}^{\mathrm{T}}}（9）

式中： RSSI_A 和 RSSI_B 分别为指纹点A和聚类中心B上的RSSI向量； S 为聚类中心B的协方差矩阵。

对于剩余的m-q个指纹点，按照式（8）计算其与q个聚类中心的相似度，将其划分至q个聚类中心中相似度最大的簇中，直至所有指纹点完成聚类划分。待所有指纹点聚类完成后，对所形成的每个簇，需重新计算其质心点。假设第s(s=\mathrm{1,2},\cdots ,q)个簇中包含m_s个指纹点，考虑各指纹点上的RSSI数据相互独立，则新聚类中心处的RSSI向量及其协方差矩阵可表示为：

\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_s=\frac{\mathrm{1}}{m_s}{\displaystyle \sum _{i=\mathrm{1}}^{m_s}}\mathit{R}\mathit{S}\mathit{S}\mathit{I}s,i（10）

{\mathit{S}}_s=\frac{\mathrm{1}}{m_s^{\mathrm{2}}}{\displaystyle \sum _{i=\mathrm{1}}^{m_s}}\mathit{S}s,i（11）

式中：\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_{s,i}和{\mathit{S}}_{s,i}分别为第s个聚类簇中第i个指纹点的RSSI向量和协方差矩阵。

对于每个新的聚类质心，再次按照前文步骤重新对每个指纹点进行聚类计算，直至新的聚类质心和前一次迭代产生的聚类质心相同。此时，聚类迭代结束，所有指纹点被划分为q个聚类簇。

传统K-means聚类算法仅考虑了两个指纹点间的RSSI欧氏距离，而未考虑不同基站RSSI数据特征的差异性。由于马氏距离能够通过协方差矩阵对距离进行缩放，这使马氏距离在处理具有不同分布和方差的指纹特征时更有效。DFS-K-means聚类在相似度计算中同时考虑了两个指纹点的RSSI马氏距离以及二者的位置坐标，这可以促使相近的指纹点归入同一聚类簇，从而提升聚类准确性。

2.2　基于MWKNN算法的目标初始定位

为克服固定K值的局限性，本文对WKNN算法的K值选择进行改进，以实现动态自适应优选。

首先，计算待定点与各聚类簇质心点的马氏距离，并对q个聚类质心进行排序，选择马氏距离最小的聚类质心所在的聚类簇。假设所选中的聚类簇中包含m_s个指纹点，计算待定点与该聚类簇中各指纹点的马氏距离：

D_M\left(\mathit{r}\mathit{s}\mathit{s}\mathit{i},\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_i\right)=

\sqrt[]{\left(\mathit{r}\mathit{s}\mathit{s}\mathit{i}-\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_i\right){\mathit{S}}^{-\mathrm{1}}{\left(\mathit{r}\mathit{s}\mathit{s}\mathit{i}-\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_i\right)}^{\mathrm{T}}}（12）

式中：D_M\left(\mathit{r}\mathit{s}\mathit{s}\mathit{i},\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_i\right)\left(i=\mathrm{1,2},\cdots ,m_s\right)为待定点与聚类簇中第i个指纹点的马氏距离； rssi 和\mathit{R}\mathit{S}\mathit{S}{\mathit{I}}_i分别为待定点和第i个指纹点上的RSSI向量； S 为指纹点RSSI协方差矩阵。

依据马氏距离的计算结果对聚类簇中的指纹点进行升序排序\left\{F{P}_{\mathrm{1}},F{P}_{\mathrm{2}},\cdots ,FP{}_{m_s}{}^{}\right\}，其中F{P}_{\mathrm{1}}为马氏距离最小（即相似度最大）的指纹点。计算指纹点F{P}_{\mathrm{1}}与其余指纹点\left\{F{P}_{\mathrm{2}},\cdots ,FP{}_{m_s}{}^{}\right\}之间的坐标欧氏距离均值\overline{d}及标准差{\sigma }_d：

\overline{d}=\frac{{\displaystyle \sum _{i=\mathrm{2}}^{m_s}}{d}_{\mathrm{1}i}}{m_s-\mathrm{1}}（13）

{\sigma }_d=\sqrt[]{\frac{{\displaystyle \sum _{i=\mathrm{2}}^{m_s}}{\left(d_{\mathrm{1}i}-\overline{d}\right)}^{\mathrm{2}}}{m_s-\mathrm{1}}}（14）

式中：d_{\mathrm{1}i}为指纹点F{P}_{\mathrm{1}}与F{P}_i之间的坐标欧氏距离。

根据计算所得的标准差，筛选出d_{\mathrm{1}i}小于或等于{\sigma }_d的K个指纹点作为用于近邻匹配点，由此实现K近邻匹配中K值的自适应动态优选。

然后，采用加权K近邻算法对待定点坐标进行初始估计。根据式（12）计算待定点与K个近邻指纹点的马氏距离，计算权重：

w_i=\frac{\mathrm{1}/D_{M,i}}{{\displaystyle \sum _{i=\mathrm{1}}^K}\mathrm{1}/D_{M,i}}（15）

最后，利用式（4）计算，得到待定点的坐标位置初始估计值，记为\left(x_{FP},y_{FP}\right)。

2.3　基于粒子滤波算法的目标精确定位

利用MWKNN算法计算得到的定位结果在部分时刻可能存在较大误差。粒子滤波（Particle filtering， PF）能够结合目标状态转移模型和实测数据进行状态估计，从而提供更接近真实情况的目标状态。相比卡尔曼滤波，PF对非线性、非高斯噪声问题具有更强的适应性。本文在PF框架下引入行人航位推算（Pedestrian dead reckoning， PDR）算法进行目标位置预测，将基于MWKNN算法得到的初始定位结果作为测量值，用于粒子的赋权和更新，最终实现目标位置的精确定位。

利用手机中的惯性测量单元（IMU）可测得目标行进路线上的加速度和角速度，据此计算行人位置坐标。计算公式为：

\left\{\begin{array}{l}{x}_{PDR,t+\mathrm{1}}=x_{PDR,t}+d_t\mathrm{c}\mathrm{o}\mathrm{s}{\theta }_t\\ y_{PDR,t+\mathrm{1}}=y_{PDR,t}+d_t\mathrm{s}\mathrm{i}\mathrm{n}{\theta }_t\end{array}\right.（16）

式中：\left(x_{PDR,t},y_{PDR,t}\right)为第t步的位置坐标；{\theta }_t为第t步的航向角；d_t为第t步的步长，可由Weiberg非线性步长估算模型^［13］得到。

在行人定位问题中，构造状态空间模型：

\left\{\begin{array}{l}{\mathit{x}}_k=\mathit{F}{\mathit{x}}_{k-\mathrm{1}}+\mathit{G}{\mathit{w}}_k\\ {\mathit{z}}_k=\mathit{H}{\mathit{x}}_k+\mathit{I}{\mathit{v}}_k\end{array}\right.（17）

式中：\mathit{F}=\left[\begin{array}{cccc}\mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right]；\mathit{G}=\left[\begin{array}{cc}\begin{array}{c}\mathrm{0}\\ \mathrm{1}\end{array}& \begin{array}{c}\mathrm{0}\\ \mathrm{0}\end{array}\\ \begin{array}{c}\mathrm{0}\\ \mathrm{0}\end{array}& \begin{array}{c}\mathrm{0}\\ \mathrm{1}\end{array}\end{array}\right]； \mathit{H}=\left[\begin{array}{c}\begin{array}{cccc}\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\\ \begin{array}{cccc}\mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\end{array}\end{array}\right]；\mathit{I}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(\mathrm{1,1})；{\mathit{x}}_k={\left[x_k,d_k\mathrm{c}\mathrm{o}\mathrm{s}{\theta }_k,y_k,d_k\mathrm{s}\mathrm{i}\mathrm{n}{\theta }_k\right]}^{\mathrm{T}}为状态向量；\mathit{F}为状态转移矩阵；\mathit{G}为过程噪声驱动矩阵；{\mathit{z}}_k={\left[x_{FP},y_{FP}\right]}^{\mathrm{T}}为测量向量，即MWKNN算法得到的目标初始位置；\mathit{H}为观测矩阵；\mathit{I}为测量噪声驱动矩阵；{\mathit{w}}_k和{\mathit{v}}_k为过程噪声和测量噪声。

粒子滤波分为初始化、预测、更新和重采样4个阶段。初始化阶段中，在定位空间内生成N_p个相同权重的粒子，记为{\left\{{\mathit{x}}_{\mathrm{0}}^i,\mathrm{1}/N_p\right\}}_{i=\mathrm{1}}^{N_p}。预测阶段中，利用状态转移模型获得k时刻的先验粒子{\left\{{\mathit{x}}_k^i,\mathrm{1}/N_p\right\}}_{i=\mathrm{1}}^{N_p}。更新阶段中，利用测量模型计算各粒子权重并进行归一化，公式为：

{\tilde{w}}_k^i={\tilde{w}}_{k-\mathrm{1}}^{i}p\left({\mathit{z}}_k|{\mathit{x}}_k^i\right)（18）

w_k^i={\tilde{w}}_k^i/{\displaystyle \sum _{i=\mathrm{1}}^{N_p}}{\tilde{w}}_k^i（19）

式中：w_k^i为粒子{\mathit{x}}_k^i的归一化权重；p\left({\mathit{z}}_k|{\mathit{x}}_k^i\right)为似然函数。

p\left({\mathit{z}}_k|{\mathit{x}}_k^i\right)=\frac{\mathrm{1}}{\sqrt[]{\mathrm{2}\mathrm{\pi }}{\left(\mathrm{d}\mathrm{e}\mathrm{t}\left|\mathit{R}\right|\right)}^{\frac{\mathrm{1}}{\mathrm{2}}}}·

\mathrm{e}\mathrm{x}\mathrm{p}\left[-\frac{\mathrm{1}}{\mathrm{2}}{\left({\mathit{z}}_k-\mathit{H}{\mathit{x}}_k^i\right)}^{\mathrm{T}}{\mathit{R}}^{-\mathrm{1}}\left({\mathit{z}}_k-\mathit{H}{\mathit{x}}_k^i\right)\right]（20）

式中： R 为测量噪声的协方差矩阵，可通过实际测试获取。

此时得到k时刻的后验粒子集{\left\{{\mathit{x}}_k^i,w_k^i\right\}}_{i=\mathrm{1}}^{N_p}。最终，对粒子加权求和求得k时刻的目标状态估计：

{\widehat{\mathit{x}}}_k={\displaystyle \sum _{i=\mathrm{1}}^{N_p}}{\mathit{x}}_k^i{w}_k^i（21）

式中：{\widehat{\mathit{x}}}_k为目标状态向量的估计值。

提取该向量中的坐标分量，由此得到目标精确的位置坐标。为防止粒子退化导致滤波性能下降，滤波后需进行重采样。将重采样后的粒子代入状态转移方程，可得到下一时刻的预测粒子，从而实现算法迭代。

3 基于MWKNN-PF算法的两阶段定位流程

本文提出的MWKNN-PF定位方法流程如图1所示，包括离线与在线两个模块。

离线模块的具体流程如下。

（1）在定位空间内划分网格，在各网格点采集RSSI数据与位置坐标。

（2）在各指纹点上计算RSSI向量均值作为该点的RSSI数据，并求取协方差矩阵。将各指纹点上的RSSI向量、协方差矩阵连同位置坐标上传至服务器，构建指纹数据库。

（3）利用DFS-K-means算法将指纹库划分为q个聚类，并计算每个聚类簇的质心点坐标和RSSI向量。

在线模块分为初始定位和精确定位两个阶段，具体流程如下：

（1）采集待定点上的RSSI数据，计算待定点与各聚类质心点的RSSI马氏距离，并选择马氏距离最小的聚类质心点所在的聚类簇。

（2）在步骤（1）所选择的聚类簇中，计算待定点与各指纹点的马氏距离，并根据结果对各指纹点按相似度大小进行排序。计算相似度最大的指纹点与剩余指纹点的坐标欧氏距离均值及标准差。

（3）筛选出坐标欧氏距离小于或等于标准差的K个指纹点作为近邻匹配点，利用加权K近邻匹配算法计算出目标的初始位置。

（4）利用IMU测得目标行进路线上的加速度和角速度，依据状态转移模型计算目标位置的预测值，将基于MWKNN算法的初始定位结果作为测量值并进行粒子滤波，从而得到k时刻目标的精确位置。

与WKNN算法相比，本文算法主要具有以下三方面特点。

（1）本文算法对指纹库进行聚类操作，相比WKNN算法，在线阶段的指纹匹配工作计算量大幅下降。同时，所提出的DFS-K-means聚类算法基于信号-坐标双因子相似度，以RSSI马氏距离与坐标欧氏距离的乘积作为指纹点与聚类质心点相似度评价指标，理论上聚类效果更佳。

（2）在同一聚类簇中，本文算法基于剩余指纹点与相似度最优指纹点之间的欧氏距离实现动态优选自适应K值方法。相比WKNN算法中的固定K值，本文算法对近邻点的选取更加灵活。

（3）本文算法利用IMU测得的加速度和角速度进行步长估计与位置预测，并以MWKNN算法的初始定位结果为测量值，在粒子滤波框架下对目标状态向量进行滤波估计，进而得到目标精确位置估计。相比WKNN算法，本文算法理论上定位精度更高。

4 定位实验与分析

4.1　实验场景

本文实验在宁波诺丁汉大学理工楼中庭进行。实验选取了12 m×10 m的室内空间作为定位区域，如图2所示。实验中，在距离地面约1.5 m处布设了6个低功耗蓝牙5.0信标用于发射信号。在区域内建立1.0 m×1.0 m 的网格，共布设143个指纹点，每个指纹点的位置坐标已知。实验预先设定一矩形行走轨迹。该轨迹上设有52个位置已知的待测点（其中有14个待定点与指纹点的位置重合），相邻两待定点的间距为0.5 m。

在离线阶段，在每个指纹点上采样20次RSSI数据，并求取其RSSI均值与协方差矩阵。将各指纹点的RSSI向量、协方差矩阵及位置坐标上传至服务器，构建指纹库。随后利用DFS-K-means算法对指纹点进行聚类。根据现场环境，聚类数目q设为4。在在线阶段，实验人员使用华为Mate40智能手机结合BeaconSET与MATLAB mobile软件进行数据采集，蓝牙和惯性传感器的采样率均设置为20 Hz。数据采集过程中，实验人员将手机放置在胸前，从起点开始，沿着轨迹线行走，步长约为0.5 m，每前进一步到达下一个待测点。整个路径共计行进52步，最终返回至起点。

为了验证算法的定位性能，将MWKNN-PF算法的实验结果与WKNN算法、MWKNN算法以及文献［1］中提出的改进WKNN算法进行对比。为控制变量，实验中两个非自适应K值算法（即WKNN和文献［1］算法）的K值均设为4。同时，为了平衡定位精度和定位时间，实验中两个粒子滤波类算法（即MWKNN-PF和文献［1］算法）的粒子数设置为2 000。

4.2　试验结果分析

4.2.1　定位精度分析

图3为4种算法得出的目标运动轨迹。由图3可知，WKNN的轨迹最为杂乱，而MWKNN-PF算法的轨迹与目标真实运动轨迹最为契合。

为进一步定量分析算法的定位精度，计算各算法在52个待定点上位置估计的均方根误差，结果如表1所示。与其他3个定位算法相比，WKNN算法的均方根误差最大。MWKNN算法通过DFS-K-means聚类及动态优选自适应K值方法，所得到的初始定位坐标的均方根误差为1.291 m，较WKNN提升了约22.4%。MWKNN-PF算法在MWKNN算法基础上引入PF，并通过PDR算法预测下一时刻的粒子分布，从而有效约束了目标的空间位置。因此，MWKNN-PF算法相比MWKNN和WKNN算法，其定位精度分别提高约24.9%和41.8%。文献［1］算法在精确定位阶段虽也采用PF算法，但与MWKNN-PF算法不同，其在初始定位阶段的指纹库未经聚类处理，且指纹匹配中采用固定K值。二者相比，MWKNN-PF算法较文献［1］算法的定位精度提高约12.6%，由此证明本文在初始定位阶段所执行的指纹聚类操作和动态优选自适应K值方法能有效提升定位精度。

图4为4种算法的定位误差累积分布情况。在相同指纹库的条件下，本文的MWKNN-PF算法误差累积函数收敛速度最快，MWKNN及文献［1］算法次之，而WKNN算法的误差累积函数收敛最慢。MWKNN-PF算法定位误差小于1.5 m的概率达到90.57%，优于WKNN算法的52.83%、MWKNN算法的61.67%及文献［1］算法的78.33%。由此可见，MWKNN-PF算法在定位精度上有明显改善。

4.2.2 定位时间分析

为充分评估本文算法实际应用的可行性及实用性，对其时间复杂度进行分析，MWKNN-PF算法的在线阶段各步骤的复杂度分析如下：

（1）计算待定点与各聚类质心点的马氏距离，并选择距离最小的聚类簇。假设将所有指纹点划分为q个聚类簇，由于马氏距离的计算是矩阵乘法，则该过程的复杂度为C_{\mathrm{1}}=O\left(q{d}^{\mathrm{2}}\right)。其中，d为RSSI向量的维度。

（2）计算待定点与聚类簇中各指纹点的马氏距离，并根据结果对各指纹点按相似度大小进行排序。假设所选定的聚类簇中包含m_s个指纹点，马氏距离的计算复杂度为O\left(m_s{d}^{\mathrm{2}}\right)，排序的复杂度为O\left(m_s\mathrm{l}\mathrm{o}\mathrm{g}{m}_s\right)，则该过程的总体复杂度为C_{\mathrm{2}}=O\left(m_s{d}^{\mathrm{2}}+m_s\mathrm{l}\mathrm{o}\mathrm{g}{m}_s\right)。

（3）计算剩余指纹点与相似度最大指纹点间的欧氏距离，动态优选自适应K值，并利用加权K近邻算法计算初始位置。该过程中，欧氏距离的计算复杂度为O\left(m_{s}d\right)，优选K个指纹点的复杂度为O\left(m_s\right)，计算加权K近邻的复杂度为O\left(Kd\right)。由于K值通常远小于m_s值，因此保留主导项后该过程的总体复杂度可简化为C_{\mathrm{3}}=O\left(m_{s}d\right)。

（4）粒子滤波。该过程复杂度取决于粒子数目N_p和状态向量维度。本算法中状态向量维度为4，测量向量维度为2，则初始化、状态预测、粒子更新的复杂度均为O\left(\mathrm{4}{N}_p\right)，权重归一化及重采样的复杂度均为O\left(N_p\right)，因此该过程总体复杂度可简化为C_{\mathrm{4}}=O\left(N_p\right)。

综上， MWKNN-PF算法的总体计算复杂度可表示为：

C=O\left(q{d}^{\mathrm{2}}+m_s{d}^{\mathrm{2}}+m_s\mathrm{l}\mathrm{o}\mathrm{g}{m}_s+m_{s}d+N_p\right)

为评估各算法在线阶段的实际计算负荷，利用MATLAB程序中的“tic”和“toc”函数计算各算法在一个待定点上进行位置估计所需要消耗的计算时间，结果见表1。WKNN和文献［1］算法由于需将待定点与定位区域中的所有指纹点进行依次匹配，因此消耗的时间较长。而MWKNN和MWKNN-PF算法由于在离线阶段已对指纹点进行了聚类处理，在线阶段中仅与相似度最佳的聚类簇中的指纹点进行匹配，因此所消耗的时间大幅下降。在本实验环境中，MWKNN-PF算法的计算时间约为0.502 s，较WKNN算法减少了约59.6%。该运算时间可基本满足定位的实时性需求。

4.2.3　 K值对比分析

为了验证MWKNN-PF算法中所采用的动态优选自适应K值的有效性，将算法中的K值人为设定为1至10，并观察在不同K值下算法定位均方根误差的变化情况，结果如图5（a）所示。由图可知，K值过小或过大均会导致定位精度的下降。当K值为4时，算法的定位误差最小，为1.102 m。本文所采用的动态优选自适应K值可将定位精度提升至0.969 m，与K=4时的MWKNN-PF算法相比，定位精度提升约12.1%。这充分说明，动态优选的自适应K值可根据邻近指纹点的分布，自适应调节每个待定点处的最佳K值，从而有效提高定位精度。

4.2.4　滤波粒子数影响分析

MWKNN-PF算法因引入粒子滤波，其收敛性受粒子数量影响。通过设置不同的粒子数量（100、200、300、500、800、1 000、2 000、3 000、5 000、8 000、10 000），观察其均方根误差变化，以评估算法收敛性。如图5（b）所示，当粒子数量不足时，粒子无法较好地反映目标的真实位置，导致定位精度较低。在一定的范围内，增加粒子数可提高定位精度。然而，当粒子数量达到2 000时，再增加粒子数对精度提升的作用较为有限，此时算法误差趋于稳定。此后，增加粒子数并不能明显提高定位精度，反而会增加计算负荷。

5 结束语

为解决蓝牙指纹定位中加权K近邻（WKNN）算法存在的缺陷，将改进的WKNN（MWKNN）算法与粒子滤波（PF）算法结合，提出了一种MWKNN-PF算法。室内定位实验结果表明，该算法在定位精度和计算负荷上均明显优于传统WKNN及部分文献中的算法。本文所提算法在室内定位领域具有一定的应用价值，尤其适用于大型室内广场等公共场合中的行人定位。后续研究将对粒子滤波的建议分布函数选择进行更深入地优化，使其在不同环境中具有更强的鲁棒性。

参考文献

[1] 沈天盛, 陈文莹, 朱彬斌, 等. 基于改进WKNN的蓝牙室内定位方法[J]. 现代电子技术, 2023, 46(10): 11-16.

[2] Shen Tian-sheng, Chen Wen-ying, Zhu Bin-bin, et al. Method of bluetooth indoor positioning based on improved WKNN[J]. Modern Electronics Technique, 2023, 46(10): 11-16.

[3] 孙大洋, 王雪莹, 韩双雪, 等. 虚拟锚点高维坐标的非视距识别及定位优化[J]. 吉林大学学报:工学版, 2021, 51(6): 2207-2215.

[4] Sun Da-yang, Wang Xue-ying, Han Shuang-xue, et al. Non⁃line⁃of⁃sight identification and optimization based on virtual coordinates of anchors[J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(6): 2207-2215.

[5] 杨海峰, 张勇波, 黄裕梁, 等. 基于空间特征分区和前点约束的WKNN室内定位方法[J]. 软件学报, 2019, 30(11): 3427-3439.

[6] Yang Hai-feng, Zhang Yong-bo, Huang Yu-liang, et al. WKNN indoor positioning algorithm based on spatial characteristics partition and former location restriction[J]. Journal of Software, 2019, 30(11): 3427-3439.

[7] Li X, Dai Z, He L. A K-nearest neighbor indoor fingerprint location method based on coarse positioning circular domain and the highest similarity threshold[J]. Measurement Science and Technology, 2022, 34(1): 015108.

[8] Chen B, Ma J, Zhang L, et al. An improved weighted KNN fingerprint positioning algorithm[J]. Wireless Networks, 2024, 30: 6011-6022.

[9] 王轩, 陈国良, 曹晓祥, 等. 自适应K值及指纹库扩充的WLAN室内定位方法[J]. 测绘科学, 2020, 45(7): 26-32.

[10] Wang Xuan, Chen Guo-liang, Cao Xiao-xiang, et al. Research on WLAN indoor positioning method based on adaptive K value fingerprint database expansion[J]. Science of Surveying and Mapping, 2020, 45(7): 26-32.

[11] 梁哲豪, 石磊, 唐杰, 等. 室内可见光指纹定位系统中改进的加权K最近邻算法[J]. 激光与光电子学进展, 2022, 59(17):123-127.

[12] Liang Zhe-hao, Shi Lei, Tang Jie, et al. Improved weighted K nearest neighbor algorithm for indoor visible light fingerprint positioning system[J]. Laser & Optoelectronics Progress, 2022, 59(17): 123-127.

[13] 顾亚雄, 钟文. 混合滤波与改进贝叶斯相融合的室内可见光指纹定位方法[J]. 测绘通报, 2023(6): 104-109, 128.

[14] Gu Ya-xiong, Zhong Wen. Indoor visible light fingerprint location method based on GF-KF and improved-Bayes[J]. Bulletin of Surveying and Mapping, 2023(6): 104-109, 128.

[15] Yang X, Wu Z, Zhang Q. Bluetooth indoor localization with Gaussian-Bernoulli restricted boltzmann machine plus liquid state machine[J]. IEEE Transactions on Instrumentation and Measurement, 2022, 71: 1000208.

[16] Philips D, Salami E, Ramiah H, et al. Location accuracy optimization in bluetooth low energy (BLE) 5.1-based indoor positioning system (IPS)—a machine learning approach[J]. IEEE Access, 2023, 11: 140186-140201.

[17] Liu Y, Wu C, Kong X, et al. A tightly-coupled method for indoor vehicle navigation based on smartphone IMU and BLE[J]. IEEE Transactions on Instrumentation and Measurement, 2024, 73: 8509612.

[18] Xia H, Zuo J, Liu S, et al. Indoor localization on smartphones using built-in sensors and map constraints[J].IEEE Transactions on Instrumentation and Measurement, 2019, 68(4): 1189-1198.

[19] Zhang J, Yu B, Ge Y, et al. An effective GNSS/PDR fusion positioning algorithm on smartphones for challenging scenarios[J]. Sensors, 2024, 24:1452.

基金资助

国家自然科学基金项目(42204016)

宁波市自然科学基金一般项目(2023J284)

宁波市公益性科技计划项目(2023S171)