改进K均值聚类BP神经网络超宽带室内定位方法

连宗凯,袁飞，祁伟

（广东技术师范学院自动化学院，广州510000）

改进K均值聚类BP神经网络超宽带室内定位方法

连宗凯,袁飞，祁伟

（广东技术师范学院自动化学院，广州510000）

室内定位技术随着生产生活对室内定位的需求不断提高而成为热点问题之一，超宽带定位技术以其独特的优势而快速发展，针对超宽带定位系统定位数据存在稳定性差、精度低的问题，提出改进K均值聚类BP神经网络超宽带室内定位方法。该方法对超宽带定位系统中原始数据进行改进K均值聚类算法的预处理，过滤位置偏差大的数据。再对测定区域内多点进行基于真实坐标和聚类过滤坐标的BP神经网络建模。定位过程则将过滤后的待定位坐标输入建好的BP神经网络定位模型，进行识别定位。通过实验测定，该室内定位方法精度可达26cm，且稳定性好。

2016广东省科技厅（No.2016A040403122）

0 引言

室内定位应用广泛，在商场、机场等大型建筑物内，家居环境中的服务机器人领域都是关键技术。研究室内定位意义重大。根据定位所采用的测量标度可以分为基于视觉的室内定位、基于超声波的定位、基于激光测距定位、基于惯性加速度传感器定位和基于无线网络的定位方法。视觉定位存在计算复杂度高的问题。基于超声波的定位存在受定位环境影响大的问题。基于激光测距受室内障碍物等外部因素影响大的问题。因此在实际应用中，基于无线网络的室内定位方法研究得最多。

目前，基于无线网络的室内定位所采用的网络类型主要包括蓝牙、无线局域网（WLAN）、射频识别（RFID）、ZigBee、超宽技术[1]。这些网络中，定位精度最高的为超宽带技术。其他无线网络在使用中受到环境影响较大，定位精度相对较低。

UWB具有功耗低、频带极宽、短距离传输速率高、隐蔽抗干扰、时间分辨率高、穿透能力强等优势。这些优势提供了厘米级定位基础[2]，并且超宽带定位系统装配简单、算法时间复杂度和空间复杂度低。

由于室内环境复杂，干扰源多，超宽带定位系统存在非视距传播和多径传播现象，导致返回的原始位置数据存在漂移现象，严重影响定位精度[3]。为此本文提出改进K均值聚类BP神经网络超宽带室内定位方法。该方法先采用改进K均值聚类算法对原始坐标信息进行过滤优化，接着使用优化过的数据训练BP神经网络构建定位模型，最后利用该模型识别经过改进K均值聚类处理过的待识别位置坐标，从而得到最终定位结果。

1 超宽带室内定位系统

本文采用超宽带定位系统包括四个定位锚节点（A1，A2，A3，A4）和一个移动目标节点（Tag）。当Tag位于某个位置时，Tag向四个锚节点发送数据，锚节点收到数据后，向Tag返回数据。Tag根据发送数据和接收到数据之间的时间差，得到Tag与锚节点A1，A2，A3，A4间距离分别为d1、d2、d3和d4。再利用锚节点和Tag节点间空间几何关系，得到Tag的坐标数据，该坐标数据为超宽带系统采集到的原始坐标数据。

2 改进K均值聚类算法的数据预处理

对于某个已知位置，超宽带定位系统受环境影响，存在采集到的原始坐标数据漂移的问题，若采用传统均值过滤方法，也存在过滤后坐标受漂移点影响大的问题。因此，本文通过改进k均值聚类算法对原始坐标数据进行聚类预处理，将漂移坐标数据与可靠坐标数据进行区分，用可靠坐标数据的中心作为该已知位置的坐标数据。改进K均值聚类算法也克服了k均值聚类算法需要事先指定聚类数K和易陷入局部最优的问题。

改进K均值聚类算法的数据预处理分为三步：Canopy算法确定聚类数K和初始聚类中心；K均值聚类算法确定各簇内数据；根据各簇内坐标数据个数确定可靠坐标数据。

2.1 Canopyy算法确定聚类数 k和初始聚类中心

本文采用Canopy的算法是以欧氏距离作为相似度标准，在聚类速度有很大优势，可应用与K均值聚类之前做粗聚类预处理得到K值与K均值聚类算法的初始聚类中心[4]。

Canopy算法的原理是对一个给定的包含n个d维数据点的数据集合X={x1,x2,…,xn}，其中xi=｛xi1,xi2,…,xid｝，以欧氏距离作为相似度评判标准，通过给出两个距离（T1,T2且T1

该算法步骤如图1 Canopy算法流程图所示。

上述过程之后，将k值与k个中心坐标赋值给K均值聚类算法作为k值与初始聚类中心

2.2 K均值聚类算法确定各簇内数据

K均值聚类算法的原理是对一个给定的包含n个d维数据点的数据集合X={x1,x2,…,xn}，其中xi={xi1,xi2，…，xid}，以欧氏距离作为相似度评判标准，将X划分为K个数据子集C={Ci,i=1,2,…,K}[5]。

图1 Canopy算法流程图

K均值算法是反复迭代直到收敛的过程，收敛条件为聚类各聚类中心点移动幅度小于设定的阈值ε，算法流程包括四个步骤如图2 K均值聚类算法流程图所示。

图2 K均值聚类算法流程图

从上不难看出，K均值聚类算法存在两个缺陷：

①k值的确定没有自动化

②初始聚类中心选取没有自动化

在不同的问题应用里，K值往往是是难以估计的，而初始聚类中心的选取则对聚类结果有较大影响，因此结合Canopy聚类算法改进K均值聚类算法以克服以上两个缺陷是有必要的。

2.3 确定可靠坐标数据

K均值聚类算法得K个数据子集C={Ci,i=1,2,…,K}，计算每个Ci中数据的数量，取数量最大的Ci作为可靠数据，输出该可靠数据集的均值中心作为可靠坐标数据Cicenter。

3 BP神经网络定位模型构建

超宽带定位系统对多个已知位置的原始坐标数据进行改进k均值聚类算法的数据预处理后，将这多个（已知位置、可靠数据中心）数据对通过BP神经网络[6]构建定位模型，以便对待识别位置的坐标数据进行识别。

BP神经网络定位模型构建如图3 BP神经网络模型构建流程图所示：

图3 BP神经网络模型构建流程图

4 待定位位置的定位确定

图4模型建立与定位识别框图给出了改进K均值聚类算法与BP神经网络整合的定位算法过程：

首先将超宽带定位系统返回的原始数据送入Canopy预处理，获取k值后再将k值与原始数据送入K均值聚类处理，最后将K均值聚类算法中数据量最大的类的均值中心送入BP神经网络的输入层，通过BP神经网络定位模型输出定位位置。

图4 模型建立与定位识别框图

基于改进K-means聚类算法与BP神经网络整合的定位算法方案有优势如下：

①保留单独使用算法的优势，即运算时时间复杂度和空间复杂度低，无需求取复杂参数；

②消除两者单独作用于该定位系统时的缺点，K均值聚类算法为BP神经网络提高的样本与待识别位置的准确性，BP神经网络算法则对K均值聚类算法的结果做进一步精细拟合。

5 定位精确度检验

5.1 定位精确度指标

定位精确度是评价定位技术的重要指标。本文针对定位精确度采用均方根误差作为评价定位方法的性能指标：式中Pi表示第i个坐标信息，表示与i个坐标信息对应的实际坐标。

5.2 实验数据采集

实验时，在广东技术师范学院自动化学院机器人实验室内，部署了超宽带定位系统。设备部署如图5实验环境与设备部署所示。

超宽带定位系统包括四个定位锚节点A1，A2，A3，A4和一个移动目标节点Tag，在实验室采用吸顶方式水平按照位置固定四个锚节点，形成一个400× 600的矩形，天线朝下与地面垂直；移动目标通过超宽带定位系统相配套的配置软件，以A1为原点建立空间直角坐标系，根据实际距离设置各个定位锚节点的坐标：A1（0，0，285）、A2（400，600，285）、A3（0，600，285）、A4（400，600，285），启动超宽带定位系统即可通过串口接收该系统返回的融合定位数据。四个锚节点围成平面所投影地面按照相邻100cm取参考位置。

图5 实验环境与设备部署

实验环境为实验室一个10×10的矩形区域，定位区域内为视距环境，定位区域外摆放有大量金属设备，具体图6定位环境所示：

图6 定位环境

下面说明采集数据和使用数据：

将Tag放置在某一已知位置，按照超宽带定位系统串口通讯协议进行数据采集，每次读取i个坐标，构成集合Mi(i=1,2,…)。

将取得的坐标集合采用改进K均值聚类算法处理，将返回值作为已知位置可靠的训练样本点

在同一已知位置，重复步骤2）k次，取得可靠的样本训练点集合，k的取值根据BP神经网络训练效果决定。

重复步骤1）～3），取得个已知位置坐标及其可靠估计坐标构成训练样本集合，使用该训练样本集合训练BP神经网络，从而获得BP神经网络定位模型。

最后在定位阶段，将Tag放在某一待定位识别位置，按照步骤1）和步骤2）的做法，获得待定位识别位置的估计坐标Sx，将其输入到训练好的BP神经网络定位模型进行拟合定位，从而得到Tag所处位置坐标信息。

5.3 定位精确度验证

在定位区域内，每隔1m取一个已知位置，共35个位置，分别进行数据采样100次，每5个数据进行一次改进K均值聚类，每个位置得20个经过过滤优化的数据。对于BP神经网络，使用每个位置中的10个数据进行训练，最终建立层数为3、隐藏层神经元数为14的BP神经网络。建立定位识别模型后采用另外10个数据进行验证，得到的定位结果如图7仅聚类与有神经网络的RMSE比较与表1仅聚类与有神经网络定位数据比较所示。

图7 仅聚类与有神经网络的RMSE比较

表1 仅聚类与有神经网络定位数据比较

数据分析

上表与图可知，采用改进K均值BP神经网络方法的最大偏差、最小偏差、平均RMSE、平均偏差均有大幅度降低，平均RMSE降低了45%，定位精度相比仅聚类算法有大幅度改善。

6 结语

在超宽带定位系统的基础上，本文提出改进K均值聚类BP神经网络超宽带室内定位方法。从改进K均值聚类、BP神经网络模型构建两个方面入手，通过实验验证该方法在减小超宽带定位系统定位数据稳定性差、精度低等方面有明显效果，并且定位精度理想，具有良好的应用价值。

[1]石晓伟.基于BP神经网络和改进质心算法的室内无线定位技术的研究.北京工业大学，2012：11-13.

[2]肖竹等.超宽带定位研究与应用:回顾和展望.电子学报，2011（01）:1.

[3]冯晓莉.超宽带通信系统定位技术研究.南京理工大学，2009：35.

[4]赵庆.基于Hadoop平台下的Canopy-Kmeans高效算法.电子科技，2014（02）.

[5]王千等.K-means聚类算法研究综述.电子设计工程，2012（07）.

[6]刘彩红.BP神经网络学习算法的研究.重庆师范大学，2008.

Improved K-means Clustering BP Neural Network UWB Indoor Location Method

LIAN Zong-kai，YUAN Fei，QI Wei

（School of Automation，Guangdong Polytechnic Normal University，Guangzhou 51000）

Indoor positioning technology with the production and living on the indoor positioning of the demand has become one of the hot issues,ul⁃tra-wideband positioning technology with its unique advantages and rapid development,for ultra-wideband positioning system positioning data is poor stability,low accuracy,proposes the improved K-means clustering BP neural network UWB indoor location method.This meth⁃od improves the original data in the UWB positioning system and preprocesses the K-means clustering algorithm to filter the data with large deviation of the position.And then carries on the BP neural network modeling based on the real coordinates and the clustering filter coordinates in the multi-point in the measurement area.Positioning process is filtered after the positioning of the coordinates of the input BP neural network positioning model,identification and positioning.Through the experimental determination,the indoor positioning meth⁃od accuracy of up to 26cm,and good stability.

1007-1423（2017）21-0016-05

10.3969/j.issn.1007-1423.2017.21.003

连宗凯（1996-），男，广东汕头人，在读本科，专业方向为2015级电气工程及其自动化；袁飞(1984-)，男，湖南常德人，博士研究生，研究方向为无线传感器网络、数据融合；祁伟（1964-），女，山东陵县人，本科，研究方向为检测技术与自动化装置、智能机器人；；

2017-05-04

2017-07-16

超宽带；室内定位；聚类算法；BP神经网络

Ultra-Wide Band;Indoor Location;Clustering Algorithm;BP Neural Network