基于空间划分的K-means 聚类室内定位垂直精度优化方法

李 冰，杨珊珊，刘春刚，赵 华，王 翔

（1.河北师范大学 中燃工学院，石家庄 050024；2.河北省信息融合与智能控制重点实验室，石家庄 050024）

随着物联网的快速发展，高精度室内定位技术的需求愈发强烈，目前室内定位技术有很多，其中超宽带（Ultra-Wideband,UWB）定位技术凭借功耗低、穿透能力强、时间分辨率高、定位精度高[1]等优点，逐渐成为室内定位技术研究的热点。

UWB 室内定位技术在水平方向上已经获得很高的定位精度。Poulose 等人[2]提出了一种长短期记忆网络（Long Short Term Memory,LSTM）预测标签位置的方法，将测距值作为LSTM 模型输入，输出为标签位置预测值，实现了水平方向0.07 m 的定位精度。Fu等人[3]提出了一种自适应无迹卡尔曼滤波（Unscented Kalman Filter,UKF）高精度室内定位方法，通过构造状态补偿函数，结合UKF 算法，能够对定位区域中的标签任何位置执行自适应实时补偿，水平方向定位精度小于0.07 m。Guo 等人[4]设计了模拟退火和聚类融合的室内定位优化算法，该算法利用模拟退火算法的良好局部搜索能力来优化聚类效果，快速确定采样数据的最佳结果，以实现准确定位，水平方向定位误差小于0.1 m。由此可见，水平方向定位精度可以通过机器学习方法、滤波算法或智能优化算法得到显著提高。然而，以上方法只提高了水平方向精度，对垂直方向的定位精度没有改善。

三维室内定位中，垂直方向的精度受到锚节点的几何精度因子[5]（Geometric Dilution of Precision,GDOP）的影响。由于水平方向锚节点布设空间更为宽广，因此水平精度因子（Horizontal Dilution of Precision,HDOP）更小。相比之下，垂直方向的锚节点布设范围较窄，导致垂直精度因子（Vertical Dilution of Precision,VDOP）更大，使得定位方程组出现病态情况，从而导致垂直方向误差较大。Li 等人[6]针对传统最小二乘法在垂直方向定位中存在不稳定性的问题，提出鲁棒脊估计方法，解决了到达时间差（Time Difference of Arrival,TDOA）定位算法的发散问题。复杂环境中，垂直方向定位精度小于1.85 m，但是该方法未分析导致方程病态的原因，容易出现解算错误的情况。徐晓苏等人[7]提出二次解析的室内定位垂直方向精度优化方法，通过第一次解析得到标签水平方向坐标，然后通过二次解析过程中的Tikhonov 正则化方法修正垂直方向上的偏差。该方法垂直方向定位精度小于0.35 m，但计算复杂，而且如果一次解析出的水平方向误差过大，也会对二次解析的垂直方向定位精度造成影响。Yang 等人[8]针对垂直方向定位误差比水平方向定位误差大的问题，采用改进粒子群优化算法确定卡尔曼滤波的最佳参数，优化前置校正点位置，可以实现0.25 m 的垂直方向定位精度，但该方法需要先验信息，不能直接使用于未知区域或实时定位场景。所以在受限的环境下，垂直方向定位精度还有待进一步提高。

针对上述问题，本文提出基于空间划分的K-means 聚类（Space Grid Division K-means,SGDK）室内定位垂直精度优化方法。首先，采集锚节点到标签的TDOA 数据，利用拉依达准则进行异常值筛选，通过Chan 算法解算标签的估计位置，得到原始标签数据集。然后，采用网格聚类方法将原始标签数据集划分成空间网格单元，根据设定的距离阈值合并近邻空间网格单元，通过密度原则和K-means++聚类中心选取方法，选取密度大且距离远的候选空间网格单元，从中确定初始聚类中心。接下来，使用K-means 聚类算法将原始标签数据集划分为k个子区域，并确定子区域可信度高的参考位置。最后，计算参考位置与中心位置离散程度，根据离散程度对参考位置赋予权重因子。对可能有偏差的参考位置赋予较小的权重，对接近中心位置赋予较大权重，加权质心定位算法确定标签最优位置。

1 定位方法

1.1 TDOA 定位原理

TDOA 定位算法[9]通过测量待测标签与锚节点间距离差来实现标签位置的解算，其几何原理是基于双曲线或双曲面相交解析定位，原理如图1 所示。

图1 TDOA 定位原理图Fig.1 TDOA positioning schematic diagram

图1 中，主锚节点为BS1，从锚节点为BS2、BS3、BS4。以BS1 为基准建立三条双曲线，交点为待测标签 MS的位置，其中锚节点坐标为(xℓ,yℓ,zℓ)，ℓ=1～4；MS 坐标为(x,y,z)。由上述分析可得：

其中，R1为主锚节点到MS 的距离；Rℓ为从锚节点到MS 的距离；Rℓ,1为MS 到从锚节点和主锚节点间的距离差；τℓ,1为MS 发送信号到达从锚节点和主锚节点的时间差；c为信号传播速度。

1.2 Chan 算法

Chan 算法是一种基于TDOA 算法的定位方法，通过求解非线性双曲线方程组来确定标签位置，并采用多次加权最小二乘（Weighted Least Square,WLS）对定位误差进行修正。当测距误差符合高斯分布时，该算法能够实现较高的定位精度。然而，复杂室内环境中，非视距误差（Non-line-of-sight,NLOS）的存在将影响到测距误差的分布特性，使其不服从高斯分布[10]，所以Chan 算法的定位精度还有待提高。

假设在三维实验环境中存在N个锚节点，位置为(xi,yi,zi)，i=1,2…N。标签位置为(x,y,z)，标签与锚节点之间的距离为Ri，有：

联立式(3)(4)可得：

整理式(5)可得：

由于观测噪声的存在，导致h≠Gza，误差向量表示为：

假设za中各个元素相互独立，对式(8)进行WLS得到标签的第一次估计位置：

za中的元素可以表示为：

实际上za中各个元素并不相互独立，为了得到更加精确的标签位置，需要对上述结果进一步优化，建立第二次估计的线性方程：

对式(11)进行WLS 得到标签的第二次估计位置：

最终得到标签位置为：

2 基于SGDK 聚类的垂直精度优化方法

K-means 聚类算法[11]是一种无监督聚类算法，通过计算样本点与簇中心的距离，将相似度高的样本划分为同一个簇。处理较大数据时间复杂度低、效率高，但随机初始聚类中心没有考虑数据分布情况，容易达到局部最优值，影响聚类效果。故本文对K-means 聚类算法初始聚类中心的选取进行改进，在网格聚类与K-means 聚类方法基础上，提出SGDK 聚类的室内定位方法。将定位问题转化为三维样本聚类问题，用于提升室内定位垂直方向定位精度。总体算法流程如图2 所示。

图2 算法流程图Fig.2 Flowchart of the algorithm

2.1 数据预处理与标签位置估计

对标签进行多次重复实验，采集300 组TDOA 数据。受室内环境因素影响，其中包含了一些异常数据。为了便于后续的定位分析，采用拉依达准则（3σ准则）来判断和筛选异常值[12]。

3σ准则：以给定的置信概率99.73%为标准，若数据的偏差超过3 倍标准偏差，就会被当作粗大误差，含有此误差的数据称为异常值，需要从数据集中剔除。计算公式为：

剔除TDOA 异常值后，通过Chan 算法求解出标签估计位置，得到原始标签数据集，记为dataα(α=1,2 …300)。在UWB 室内定位锚节点布设时，对水平方向的限制比较小，可以布置在比较合理的范围，而对垂直方向的限制比较大，导致标签估计位置在垂直方向波动范围比水平方向更大，如图3 所示。为了进一步提高垂直方向定位精度，需要对标签估计位置进行处理，采用聚类算法的目的就是对标签数据集分层划分，从中确定标签的最优位置。

图3 估计位置分布情况Fig.3 Estimated location distribution

2.2 SGDK 聚类算法

在传统K-means 聚类算法中，随机初始聚类中心导致每次聚类结果不同，严重影响标签数据集聚类的准确性，使得标签最终定位精度也受到影响。因此本文提出SGDK 聚类算法，通过网格聚类方法对原始标签数据集进行空间网格划分，并结合密度原则和K-means++聚类中心选取方法，从中确定初始聚类中心。

2.2.1 数据空间网格划分

SGDK 聚类算法通过网格聚类方法，进行数据集空间网格划分，将原始标签数据集中的样本点映射到各空间网格单元中。但是如果空间网格划分过于细化，不仅会导致计算效率降低，甚至还会出现某些网格中的样本点数量过少的情况。因此，本文结合原始标签数据集分布特点，通过确定聚类个数k值来划分原始标签数据集。

定义 1原始标签数据集空间为L×W×H，空间网格单元记为Si,j,r，标签估计位置分布在每一空间网格单元内。

定义 2网格边长

设原始标签数据集dataα三个维度范围为[xmin,xmax]、[ymin,ymax]、[zmin,zmax]。将数据集按各维度划分k3个均等不相交网格。数据空间为：

其中，ε为足够小的阈值。

定义 3标签估计位置与空间网格单元存在如式(19)所示的关系：

定义 4网格密度

空间网格划分后，网格单元样本点个数记为网格密度ρg(g=1,2…k3)。

定义 5近邻网格

存在公共边的空间网格单元，记为近邻空间网格单元。

定义 6网格质心

若落入网格m个样本点，网格质心为网格单元中所有样本点的均值，记为ηg。

其中，Cie为网格单元中第i个样本点。

2.2.2 K-means 初始聚类中心的确定

数据空间网格划分后，需要在空间网格单元中选取候选初始聚类中心网格，从中确定初始聚类中心。然而，在候选初始聚类中心网格集中，同一簇可能存在多个候选网格。为了避免初始聚类中心出现在同一簇中，本文根据文献[13]的网格距离设置方法，设定距离阈值ω。如果任意近邻空间网格质心之间的距离小于ω，则合并两个空间网格单元。

密度原则：各空间网格单元密度按照从高到低顺序排序，选取前k2个密度最高的空间网格单元作为候选初始聚类中心网格单元DCP(P=1,2…k2)。

K-means 初始聚类中心选取步骤如下：

步骤1：设定聚类个数k，划分k3个空间网格单元，根据定义4 和定义6 计算网格密度ρg和网格质心ηg。

步骤2：若任意近邻空间网格质心之间的距离小于距离阈值ω，则合并两个空间网格单元。

步骤3：再次计算空间网格单元密度，并根据密度原则确定候选初始聚类中心网格DCP，其中最高密度空间网格质心被选为第一个初始聚类中心center1。

步骤4：根据K-means++初始聚类中心选取方法，在候选初始聚类中心网格中选择与第一个初始聚类中心距离最远的空间网格质心作为新的聚类中心，直到选定k个聚类中心。初始聚类中心空间网格选取如图4所示，深色虚线部分空间网格中样本数最多并且它们的距离较远。

图4 初始聚类中心空间网格选取Fig.4 Initial cluster center spatial grid selection

其中，datat为第t个初始聚类中心空间网格内坐标样本点；ρt为空间网格密度。

2.3 算法步骤

综合上述过程，基于SGDK 聚类的室内定位垂直精度优化方法具体实现步骤为：

步骤1：采集标签TDOA 数据，利用3σ准则剔除异常值，使用Chan 算法解算标签估计位置，确定原始标签数据集dataα。

步骤2：标签数据集聚类划分为k个子区域，确定各子区域参考位置。

设定聚类中心个数k，根据K-means 初始聚类中心选取规则确定初始聚类中心。

其中，centerq=(xq,yq,zq),q=1,2…k。

计算标签数据集中样本点dataα到各聚类中心的距离d，将样本点划分到距离最近的簇中。

取每个簇数据的均值，获得新的聚类中心。

其中，Pj为聚类后第j个簇样本点总个数；为第j个簇中样本点数据之和。

若聚类中心不再变化或者达到最大迭代次数，则停止迭代，得到最终聚类中心。聚类中心即为每个簇的代表点，也被称为标签数据集k子区域参考位置。

步骤3：加权质心定位算法确定标签优化位置。

计算各子区域参考位置到数据集中心位置μ的离散程度，中心位置为标签估计位置的均值。二者距离越近，相关性越高，离散程度越小，越具有参考价值。各参考位置与中心位置距离的倒数定义为权重因子σj。

将参考位置作为质心定位算法中的多边形顶点，分别为k个参考位置赋予权重因子σj，加权质心法确定标签最终优化位置。

2.4 算法复杂度分析

SGDK 聚类算法的时间复杂度主要包括数据空间网格化过程和K-means 聚类过程。假设原始标签数据集在空间大小为L×W×H的区域内共有n个样本点，划分N个空间网格单元，每个空间网格单元中有m个样本点。算法在数据空间网格化的时间复杂度为O(N+m)，统计空间网格单元密度的时间复杂度为O(n)，计算各空间网格单元与其近邻网格单元距离的时间复杂度为O(n2)，K-means 聚类过程时间复杂度为O(knT)，k是聚类个数，T是迭代次数。算法总时间复杂度为：

由式(29)可以看出，算法的计算量主要与空间网格单元数量N、聚类个数k和迭代次数T相关。

算法总空间复杂度为O(Nm+m)，其中数据空间网格化过程为O(Nm)，K-means 聚类过程为O(m) 。

3 实验分析与验证

3.1 实验环境

本实验采用的UWB 定位芯片为易百德微电子有限公司研发的EB1003，测距误差小于0.1 m，主控芯片为国民技术的N32G452 系列MCU。

实验室搭建模拟实际应用场景：实验室空间为8.3 m×7.3 m×3.7 m。货架质地为铁质，尺寸为6 m×0.5 m×2 m，分为三层，每层高度为0.85 m，间距为0.82 m。货架上的物品为金属制仪器设备，模拟真实应用环境。实验环境和所用设备如图5-6 所示。

图5 实验环境模拟图Fig.5 Simulation diagram of experimental environment

图6 实验场景和设备Fig.6 Experimental scenarios and equipment

锚节点位置（单位为m）分别为：BS1(0,0,0)、BS2(1.200,3.577,-1.340)、BS3(5.796,3.677,-0.460)、BS4(7.556,0,-1.700)、BS5(5.796,-3.430,-0.460)、BS6(1.200,-3.460,-1.340)。采用激光测距仪测量标签真实位置，测距精度可达±5 mm。定位模块与激光测距仪性能如表1 所示。

表1 实验设备性能Tab.1 Experimental equipment performance

实验共采集了14 个标签位置数据，图7 展示了在复杂实验条件下具有代表性的4 个标签位置。每0.2～0.3 s 标签与锚节点之间会发送和接收信号一次，对每个标签位置进行 300 次数据采集，并利用MATLAB R2018b 仿真软件进行数据处理。

图7 标签位置Fig.7 Label position

3.2 实验结果与性能分析

1) 标签垂直方向误差对定位精度的影响。

在室内环境下，标签定位受到锚节点布设限制和铁质货架等障碍物的干扰，导致定位精度受到一定程度的影响，垂直方向上的干扰和误差通常会比水平方向上大。

为验证锚节点布设限制和铁质货架等障碍物对标签定位精度的影响，在货架中间层随机选取一个定位点进行实验，采集150 组TDOA 数据，通过Chan 算法解算出标签的估计位置。X、Y、Z 三个方向上的点位误差如图8 所示，标签水平方向点位误差多数在0.2～0.4 m 范围内波动，垂直方向点位误差多数在0.2～1 m 范围内波动。Chan 算法解算出的标签估计位置的定位误差通常垂直方向比水平方向大，因此在受限环境下，提升垂直方向的定位精度是影响整体定位准确性的关键。

图8 Chan 算法在不同方向的点位误差绝对值Fig.8 Absolute value of point position errors of Chan algorithm in different directions

本文提出的基于SGDK 聚类的室内定位垂直精度优化算法可以有效减小垂直方向定位误差，表2 给出了将原始标签数据集划分两个区域确定标签优化位置时的实验数据，垂直方向最大点位误差0.246 m，最小点位误差0.006 m，平均点位误差为0.134 m。垂直方向定位精度可以达到毫米级。

表2 实验数据Tab.2 Experimental data

2) 聚类个数k值对定位精度的影响。

在实验中，将聚类个数k设置为2～6。聚类过程如图9 所示，SGDK 聚类算法将原始标签数据集划分为两个区域，区域中心即为该区域的参考位置（图中六角星标记的位置）。对参考位置赋予不同权重因子，通过加权质心法确定标签最终优化位置（图中红色菱形标记的位置）。

图9 聚类过程Fig.9 Clustering process

为验证不同k值对定位精度的影响，计算了14 个标签位置垂直方向点位误差，结果如图10 所示。当k为2～6 时，垂直方向平均点位误差分别为0.134 m、0.142 m、0.140 m、0.152 m 和0.158 m。通过实验数据可以发现，在大多数情况下将数据集划分为两个区域确定标签最优位置时，垂直方向的定位精度最高。

图10 不同k 值下垂直方向点位误差绝对值Fig.10 Absolute value of point position errors in the vertical direction at different k values

图11 显示了使用SGDK 聚类算法将数据集划分两个区域以确定标签最优位置时三个方向上的点位误差。从图中可知，水平方向点位误差小于0.4 m，垂直方向点位误差小于0.3 m。其中，X 方向平均点位误差为0.157 m；Y 方向平均点位误差为0.164 m；Z 方向平均点位误差为0.134 m，验证了本文算法不仅可以提升标签垂直方向的定位精度，对系统整体的定位精度也有所提升。

图11 三个方向点位误差绝对值Fig.11 Absolute value of point position errors in three directions

3.3 方法对比

图12 显示了随机选取一个标签定位点进行实验，采集 150 组 TDOA 数据，通过 Chan 算法[14]、Chan-Taylor 算法[15]、Kalman-Chan 算法[16]得到标签估计位置在垂直方向上的点位误差，Chan 算法和Chan-Taylor 算法误差可达到1.3 m，Kalman-Chan 算法误差可达到0.7 m。结果表明，传统定位算法很难降低标签在垂直方向上的定位误差。

图12 垂直方向点位误差绝对值Fig.12 Absolute value of point position errors in vertical direction

为了验证本文提出SGDK 聚类的垂直精度优化算法的定位效果，对14 个标签位置采用了Chan 算法、Chan-Taylor 算法、Kalman-Chan 算法、Chan-Kmeans算法以及本文提出的算法进行了比较，结果如图13所示。从图中可以看出，相比于传统的定位算法，本文提出的算法可以显著降低垂直方向的定位误差。传统的K-means 聚类随机选取初始聚类中心，定位结果易受离群值影响，并且每次聚类得到的定位结果都有所不同。本文算法在此基础上进行了改进，相比于随机初始聚类中心的Chan-Kmeans 算法，本文算法具有更优的定位精度，垂直方向的定位误差可以达到毫米级。

图13 垂直方向平均点位误差绝对值Fig.13 Absolute value of average point position errors in vertical direction

表3 显示了五种算法在垂直方向上的平均绝对误差（Mean Absolute Error,MAE）和总体均方根误差（Root Mean Square Error,RMSE）。MAE 和RMSE定义如式(30)(31)所示：

表3 定位算法精度对比Tab.3 Precision comparison of positioning algorithms

相比较于 Chan 算法、Chan-Taylor 算法、Kalman-Chan 算法和Chan-Kmeans 算法，本文算法在垂直方向定位精度分别提升了62.88%、70.81%、41.74%、27.96%，总体定位精度分别提升了54.46%、55.82%、18.68%、7.79%。

4 结论

在室内定位中，由于锚节点高度布设限制，导致标签在垂直方向定位精度往往比水平方向的定位精度更低，提升标签垂直方向定位精度一直是亟待解决的难点。本文提出了基于SGDK 聚类的室内定位垂直精度优化方法，将K-means 聚类算法和网格聚类算法结合起来，对所获得的原始标签数据集进行分类，进而确定标签最终优化位置，不仅提高了室内定位垂直方向的定位精度，还减少了离群点对K-means 聚类结果的影响。实验结果表明，本文算法与传统定位算法相比在垂直方向具有更高的定位精度。

未来将采用多传感器融合定位或利用深度学习算法对信号进行预处理和优化等方式，进一步提升室内定位精度。