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

第 31 卷第 9 期 中国惯性技术学报 Vol.31 No.9 2023年09月 Journal of Chinese Inertial Technology Sep.2023 收稿日期：收稿日期：2023-04-14；修回日期：修回日期：2023-08-15 基金项目：基金项目：国家自然科学基金（62071167）作者简介：作者简介：李冰（1984），男，讲师，从事物联网、机器人技术等研究。通讯作者：通讯作者：刘春刚（1970），男，教授，硕士生导师，从事数据通信、无线电技术和物联网等研究。文章编号：文章编号：1005-6734(2023)09-0900-09 doi.10.13695/ki.12-1222/o3.2023.09.007 基于空间划分的基于空间划分的 K-means 聚类室内定位垂直精度优化方法 聚类室内定位垂直精度优化方法 李 冰1,2，杨珊珊1,2，刘春刚1,2，赵 华1,2，王 翔1,2（1.河北师范大学 中燃工学院，石家庄 050024；2.河北省信息融合与智能控制重点实验室，石家庄 050024）摘要：摘要：由于超宽带室内定位锚节点布设的高度限制导致垂直精度因子较大，进而影响标签垂直方向上的定位精度。针对这一问题，提出了一种基于空间划分的 K-means 聚类室内定位垂直精度优化方法。首先，采集标签的 TDOA 数据并利用拉依达准则剔除数据中的异常值，使用 Chan 算法解算标签估计位置以确定原始标签数据集。其次，对原始标签数据集进行空间网格单元划分，根据网格单元密度和距离确定 K-means 算法的初始聚类中心并将数据集划分为 k 个子区域，确定可信度高的 k 个参考位置。最后，将参考位置与中心位置之间距离的倒数作为权重因子，使用加权质心法确定标签的最终优化位置。实验结果表明，与 Chan 算法、Chan-Taylor 算法、Kalman-Chan 算法和 Chan-Kmeans 算法相比，所提算法在垂直方向定位精度分别提升了 62.88%、70.81%、41.74%和 27.96%，并且所提算法采用非监督的方式无需获取先验数据，具有较高的实际应用价值。关 键 词：关 键 词：超宽带室内定位；Chan 算法；K-means 聚类算法；垂直方向精度；拉依达准则 中图分类号：中图分类号：TN925 文献标志码：文献标志码：A Vertical accuracy optimization method of K-means clustering indoor positioning based on spatial division LI Bing1,2,YANG Shanshan1,2,LIU Chungang1,2,ZHAO Hua1,2,WANG Xiang1,2(1.College of Combustion Engineering,Hebei Normal University,Shijiazhuang 050024,China;2.Hebei Provincial Key Laboratory of Information Fusion and Intelligent Control,Shijiazhuang 050024,China)Abstract:Due to the height limitation of the deployment of ultra-wideband(UWB)indoor positioning anchor nodes,the vertical dilution of precision(VDOP)is large,which in turn affects the positioning accuracy of the label in the vertical direction.To solve this problem,a vertical accuracy optimization method of K-means clustering indoor positioning based on spatial division is proposed.Firstly,the time difference of arrival(TDOA)data of the label is collected and the outlier in the data is eliminated by Pauta criterion,and the Chan algorithm is used to calculate the estimated location of the label to determine the original label data set.Secondly,the original label dataset is divided into spatial grid cells,and the initial clustering center of the K-means algorithm is determined based on the grid cell density and distance.The dataset is divided into k subregions to determine k reference positions with high reliability.Finally,the reciprocal of the distance between the reference position and the center position is used as a weight factor,and the weighted centroid method is used to determine the final optimized position of the label.The experimental results show that compared with Chan algorithm,Chan-Taylor algorithm,Kalman-Chan algorithm and Chan-Kmeans algorithm,the vertical positioning accuracy of the proposed algorithm is improved by 62.88%,70.81%,41.74%and 27.96%,respectively.And the proposed algorithm adopts unsupervised approach without obtaining prior data,which has high practical application value.第 9 期 李冰等：基于空间划分的 K-means 聚类室内定位垂直精度优化方法 901 Key words:ultra-wideband indoor positioning;Chan algorithm;K-means clustering algorithm;vertical accuracy;Pauta criterion 随着物联网的快速发展，高精度室内定位技术的需求愈发强烈，目前室内定位技术有很多，其中超宽带（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.1 TDOA 定位原理 TDOA 定位算法9通过测量待测标签与锚节点间距离差来实现标签位置的解算，其几何原理是基于双曲线或双曲面相交解析定位，原理如图 1 所示。图 1 TDOA 定位原理图 Fig.1 TDOA positioning schematic diagram 图 1 中，主锚节点为 BS1，从锚节点为 BS2、BS3、BS4。以 BS1 为基准建立三条双曲线，交点为待测标902 中国惯性技术学报 第 31 卷 签 MS 的位置，其中锚节点坐标为(,)xy z，1 4；MS坐标为(,)x y z。由上述分析可得：222()()()Rxxyyzz(1),1,11RcRR(2)其中，1R为主锚节点到MS的距离；R为从锚节点到MS的距离；,1R为MS到从锚节点和主锚节点间的距离差；,1为MS发送信号到达从锚节点和主锚节点的时间差；c为信号传播速度。1.2 Chan算法 Chan算法是一种基于TDOA算法的定位方法，通过求解非线性双曲线方程组来确定标签位置，并采用多次加权最小二乘（Weighted Least Square,WLS）对定位误差进行修正。当测距误差符合高斯分布时，该算法能够实现较高的定位精度。然而，复杂室内环境中，非视距误差（Non-line-of-sight,NLOS）的存在将影响到测距误差的分布特性，使其不服从高斯分布10，所以Chan算法的定位精度还有待提高。假设在三维实验环境中存在N个锚节点，位置为(,)iiix y z，1,2iN。标签位置为(,)x y z，标签与锚节点之间的距离为iR，有：2222iiiiRxxyyzz(3)2222,11,1,1112iiiiRRRRR RR(4)联立式(3)(4)可得：2,1,111,1,1,12222iiiiiiRR RKKxxyyzz(5)其中，,11iiRRR；,11iixxx；,11iiyyy；,11iizzz；222iiiiKxyz。整理式(5)可得：2,11,1,1,1,1112iiiiiixyRKKxyzRzR (6)令T1zzapR为未知数向量，待定位标签坐标向量为Tpxyzz。由式(6)可建立以az为变量的线性方程：hGza(7)其中，22,12123,1312,1112hNNRKKRKKRKK；2,12,12,12,13,13,13,13,1,1,1,1,1NNNNxyzRxyzRxyzRG。由于观测噪声的存在，导致hGza，误差向量表示为：20.5hGzBnnnacc(8)其中，00023diag,NRRRB，0iR为标签与第i个锚节点间的真实距离；T2,13,1,1Nnnnn，,1in为时延误差；为Hadamard乘积。实际情况下可忽略式(8)中等式最右边第二项。假设za中各个元素相互独立，对式(8)进行WLS得到标签的第一次估计位置：T11T1T1argminaaazhGzhGzG GG h(9)其 中，为 误 差 向 量的 协 方 差 矩 阵，T2EBQBc，Q为TDOA的协方差矩阵，TEQnn。za中的元素可以表示为：0,110,220,330,414zzzzaaaaxeyezeRe(10)其中，1e、2e、3e和4e为za的估计误差；0 x、0y和0z为标签x、y和z三个方向的真实值；01R为标签与主锚节点间的距离真实值。实际上za中各个元素并不相互独立，为了得到更加精确的标签位置，需要对上述结果进一步优化，建立第二次估计的线性方程：hG za (11)其中，2,112,212,312,4()()()haaaazxzyzzz；100010001111G；212121()()()zaxxyyzz。的协方差矩阵为：TE4Cova BzB(12)其中，00001111diag,=xx yy zz RB；TT11CovEzzzGGaaa；za为za的估计误差。对式(11)进行WLS得到标签的第二次估计位置：111zGGGha(13)最终得到标签位置为：第 9 期 李冰等：基于空间划分的 K-means 聚类室内定位垂直精度优化方法 903 TT111(1)(2)(3)zzzzpaaaxyz (14)2 基于 SGDK 聚类的垂直精度优化方法 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倍标准偏差，就会被当作粗大误差，含有此误差的数据称为异常值，需要从数据集中剔除。计算公式为：11iitt(15)211()iitt(16)其中，it为第i个TDOA数据；t为TDOA数据均值；为数据标准偏差。若TDOA数据满足3itt，则被认为是异常值。剔除TDOA异常值后，通过Chan算法求解出标签 估 计 位 置，得 到 原 始 标 签 数 据 集，记 为(1,2300)data。在UWB室内定位锚节点布设时，对水平方向的限制比较小，可以布置在比较合理的范围，而对垂直方向的限制比较大，导致标签估计位置在垂直方向波动范围比水平方向更大，如图3所示。为了进一步提高垂直方向定位精度，需要对标签估计位置进行处理，采用聚类算法的目的就是对标签数据集分层划分，从中确定标签的最优位置。图 3 估计位置分布情况 Fig.3 Estimated location distribution 2.2 SGDK聚类算法 在传统K-means聚类算法中，随机初始聚类中心导致每次聚类结果不同，严重影响标签数据集聚类的准确性，使得标签最终定位精度也受到影响。因此本文提出SGDK聚类算法，通过网格聚类方法对原始标签数据集进行空间网格划分，并结合密度原则和K-means+聚类中心选取方法，从中确定初始聚类中心。2.2.1 数据空间网格划分 SGDK聚类算法通过网格聚类方法，进行数据集空间网格划分，将原始标签数据集中的样本点映射到各空间网格单元中。但是如果空间网格划分过于细化，不仅会导致计算效率降低，甚至还会出现某些网格中的样本点数量过少的情况。因此，本文结合原始标签数据集分布特点，通过确定聚类个数k值来划分原始标签数据集。定义定义 1 原始标签数据集空间为L WH，空间网格单元记为,i j rS，标签估计位置分布在每一空间网格单元内。定义定义 2 网格边长 设 原 始 标 签 数 据 集data三 个 维 度 范 围 为minmax,xx、minmax,yy、minmax,zz。将数据集按各维度划分3k个均等不相交网格。数据空间为：maxminmaxminmaxminSxxyyzz(17)网格边长为：maxminmaxminmaxmin()/()/()/ijrlxxklyyklzzk(18)904 中国惯性技术学报 第 31 卷 其中，为足够小的阈值。定义定义 3 标签估计位置与空间网格单元存在如式(19)所示的关系：minminmin1,1,2.1,1,2.1,1,2.ijrxxiiklyyjjklzzrrkl(19)其中，表示向下取整；i、j、r为标签估计位置映射到网格单元三个维度上的值，通过i、j、r的值确定标签估计位置所属的网格单元。定义定义 4 网格密度 空间网格划分后，网格单元样本点个数记为网格密度3(1,2)ggk。定义定义 5 近邻网格 存在公共边的空间网格单元，记为近邻空间网格单元。定义定义 6 网格质心 若落入网格m个样本点，网格质心为网格单元中所有样本点的均值，记为g。11mgiiCem(20)其中，iCe为网格单元中第i个样本点。2.2.2 K-means初始聚类中心的确定 数据空间网格划分后，需要在空间网格单元中选取候选初始聚类中心网格，从中确定初始聚类中心。然而，在候选初始聚类中心网格集中，同一簇可能存在多个候选网格。为了避免初始聚类中心出现在同一簇中，本文根据文献13的网格距离设置方法，设定距离阈值。如果任意近邻空间网格质心之间的距离小于，则合并两个空间网格单元。1max(,)ijrl l lk(21)密度原则：各空间网格单元密度按照从高到低顺序排序，选取前2k个密度最高的空间网格单元作为候选初始聚类中心网格单元2(1,2)PDCPk。K-means初始聚类中心选取步骤如下：步骤1：设定聚类个数k，划分3k个空间网格单元，根据定义4和定义6计算网格密度g和网格质心g。步骤2：若任意近邻空间网格质心之间的距离小于距离阈值，则合并两个空间网格单元。步骤3：再次计算空间网格单元密度，并根据密度原则确定候选初始聚类中心网格PDC，其中最高密度空间网格质心被选为第一个初始聚类中心1center。步骤4：根据K-means+初始聚类中心选取方法，在候选初始聚类中心网格中选择与第一个初始聚类中心距离最远的空间网格质心作为新的聚类中心，直到选定k个聚类中心。初始聚类中心空间网格选取如图4所示，深色虚线部分空间网格中样本数最多并且它们的距离较远。1kttttdatacenter(22)其中，tdata为第t个初始聚类中心空间网格内坐标样本点；t为空间网格密度。图 4 初始聚类中心空间网格选取 Fig.4 Initial cluster center spatial grid selection 2.3 算法步骤 综合上述过程，基于SGDK聚类的室内定位垂直精度优化方法具体实现步骤为：步骤1：采集标签TDOA数据，利用3准则剔除异常值，使用Chan算法解算标签估计位置，确定原始标签数据集data。步骤2：标签数据集聚类划分为k个子区域，确定各子区域参考位置。设定聚类中心个数k，根据K-means初始聚类中心选取规则确定初始聚类中心。12,kCcenter centercenter(23)其中，(,),1,2qqqqcenterxyzqk。计算标签数据集中样本点data到各聚类中心的距离d，将样本点划分到距离最近的簇中。2qddatacenter(24)取每个簇数据的均值，获得新的聚类中心。11kjjjjcenterdataP(25)第 9 期 李冰等：基于空间划分的 K-means 聚类室内定位垂直精度优化方法 905 其中，jP为聚类后第j个簇样本点总个数；jdata为第j个簇中样本点数据之和。若聚类中心不再变化或者达到最大迭代次数，则停止迭代，得到最终聚类中心。聚类中心即为每个簇的代表点，也被称为标签数据集k子区域参考位置。步骤3：加权质心定位算法确定标签优化位置。计算各子区域参考位置到数据集中心位置的离散程度，中心位置为标签估计位置的均值。二者距离越近，相关性越高，离散程度越小，越具有参考价值。各参考位置与中心位置距离的倒数定义为权重因子j。3003003001111,300uuuuuuxyz(26)21jjcenter(27)其中，(,)uuuxyz为原始标签数据集中估计坐标。将参考位置作为质心定位算法中的多边形顶点，分别为k个参考位置赋予权重因子j，加权质心法确定标签最终优化位置。11(,)kjjjkjjcenterx y z(28)2.4 算法复杂度分析 SGDK聚类算法的时间复杂度主要包括数据空间网格化过程和K-means聚类过程。假设原始标签数据集在空间大小为L WH的区域内共有n个样本点，划分N个空间网格单元，每个空间网格单元中有m个样本点。算法在数据空间网格化的时间复杂度为()O Nm，统计空间网格单元密度的时间复杂度为()O n，计算各空间网格单元与其近邻网格单元距离的时间复杂度为2()O n，K-means聚类过程时间复杂度为()O knT，k是聚类个数，T是迭代次数。算法总时间复杂度为：2()()()()TO NmO nO nO knT(29)由式(29)可以看出，算法的计算量主要与空间网格单元数量N、聚类个数k和迭代次数T相关。算法总空间复杂度为()O Nmm，其中数据空间网格化过程为()O Nm，K-means聚类过程为()O m。3 实验分析与验证 3 实验分析与验证 3.1 实验环境 本实验采用的UWB定位芯片为易百德微电子有限公司研发的EB1003，测距误差小于0.1 m，主控芯片为国民技术的N32G452系列MCU。实验室搭建模拟实际应用场景：实验室空间为8.3 m7.3 m3.7 m。货 架 质 地 为 铁 质，尺 寸 为6 m0.5 m2 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 实验设备 测距精度/m UWB 定位模块 0.1 激光测距仪 0.005 实验共采集了14个标签位置数据，图7展示了在复杂实验条件下具有代表性的4个标签位置。每0.20.3 s标签与锚节点之间会发送和接收信号一次，对每个标签位置进行300次数据采集，并利用MATLAB R2018b仿真软件进行数据处理。906 中国惯性技术学报 第 31 卷 图 7 标签位置 Fig.7 Label position 3.2 实验结果与性能分析 1)标签垂直方向误差对定位精度的影响。在室内环境下，标签定位受到锚节点布设限制和铁质货架等障碍物的干扰，导致定位精度受到一定程度的影响，垂直方向上的干扰和误差通常会比水平方向上大。为验证锚节点布设限制和铁质货架等障碍物对标签定位精度的影响，在货架中间层随机选取一个定位点进行实验，采集150组TDOA数据，通过Chan算法解算出标签的估计位置。X、Y、Z三个方向上的点位误差如图8所示，标签水平方向点位误差多数在0.20.4 m范围内波动，垂直方向点位误差多数在0.21 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 序号真实位置/m 优化位置/m 垂直方向误差/m 1(2.350,2.600,-0.600)(2.361,2.203,-0.796)0.196 2(5.200,1.300,-0.600)(4.954,1.034,-0.738)0.138 3(5.240,-1.200,-0.600)(5.160,-1.349,-0.645)0.045 4(2.410,-2.510,-0.600)(2.361,-2.203,-0.801)0.201 5(5.200,-1.200,-1.450)(5.086,-1.109,-1.594)0.144 6(2.500,1.500,-1.450)(2.668,1.445,-1.662)0.212 7(2.800,2.850,-1.450)(2.506,2.706,-1.246)-0.204 8(6.100,1.550,-1.450)(5.767,1.379,-1.204)-0.246 9(2.260,1.450,-1.450)(2.317,1.466,-1.568)0.118 10(4.300,0,-2.050)(4.083,-0.011,-2.209)0.159 11(3.270,-2.100,-1.950)(3.166,-1.724,-1.839)-0.111 12(3.400,2.440,-1.930)(3.127,2.510,-2.022)0.092 13(5.860,-2.550,-2.300)(5.894,-2.583,-2.289)-0.011 14(6.140,2.690,-2.300)(5.915,2.473,-2.306)0.006 2)聚类个数k值对定位精度的影响。在实验中，将聚类个数k设置为26。聚类过程如图9所示，SGDK聚类算法将原始标签数据集划分为两个区域，区域中心即为该区域的参考位置（图中六角星标记的位置）。对参考位置赋予不同权重因子，通过加权质心法确定标签最终优化位置（图中红色菱形标记的位置）。图 9 聚类过程 Fig.9 Clustering process 第 9 期 李冰等：基于空间划分的 K-means 聚类室内定位垂直精度优化方法 907 为验证不同k值对定位精度的影响，计算了14个标签位置垂直方向点位误差，结果如图10所示。当k为26时，垂直方向平均点位误差分别为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和RMSE908 中国惯性技术学报 第 31 卷 定义如式(30)(31)所示：222RMSE11()()()prrrrExxyyzzp(30)MAE11prrrEUUp(31)其中，p表示实验位置的个数；rU和rU分别为测量值和优化值；(,)rrrxyz和(,)x y z分别为优化坐标和真实坐标。表 3 定位算法精度对比 Tab.3 Precision comparison of positioning algorithms 算法 Z 方向MAEE/m RMSEE/mChan 0.361 0.650 Chan-Taylor 0.459 0.670 Kalman-Chan 0.230 0.364 Chan-Kmeans 0.186 0.321 本文算法 0.134 0.296 相 比 较 于Chan算 法、Chan-Taylor算 法、Kalman-Chan算法和Chan-Kmeans算法，本文算法在垂直方向定位精度分别提升了62.88%、70.81%、41.74%、27.96%，总体定位精度分别提升了54.46%、55.82%、18.68%、7.79%。4 结 论 4 结 论 在室内定位中，由于锚节点高度布设限制，导致标签在垂直方向定位精度往往比水平方向的定位精度更低，提升标签垂直方向定位精度一直是亟待解决的难点。本文提出了基于SGDK聚类的室内定位垂直精度优化方法，将K-means聚类算法和网格聚类算法结合起来，对所获得的原始标签数据集进行分类，进而确定标签最终优化位置，不仅提高了室内定位垂直方向的定位精度，还减少了离群点对K-means聚类结果的影响。实验结果表明，本文算法与传统定位算法相比在垂直方向具有更高的定位精度。未来将采用多传感器融合定位或利用深度学习算法对信号进行预处理和优化等方式，进一步提升室内定位精度。参考文献（参考文献（References）：）：1 Coppens D,Shahid A,Lemey S,et al.An overview of UWB standards and organizations(IEEE 802.15.4,FiRa,Apple):Interoperability aspects and future research directionsJ.IEEE Access,2022,10:70219-70241.2 Poulose A,Han D S.UWB indoor localization using deep learning LSTM networksJ.Applied Sciences,2020,10(18):6290.3 Fu J,Fu Y,Xu D.Application of an adaptive UKF in UWB indoor positioningC/2019 Chinese Automation Congress(CAC).China,November 22-24,2019:544-549.4 Guo H,Li M,Zhang X,et al.UWB indoor positioning optimization algorithm based on genetic annealing and clustering analysisJ.Frontiers in Neurorobotics,2022,16:715440.5 Wang M,Chen Z,Zhou Z,et al.Analysis of the applic