重庆邮电大学 蔡云骐

基于蓝牙信标的k-means指纹定位算法研究

重庆邮电大学 蔡云骐

指纹定位技术是室内定位技术中的一个热点。相较与基于wifi的指纹定位方法，蓝牙信标设备体积较小，成本低，易于布置。传统的knn指纹定位方法有计算量大，定位精度不高等缺陷。本文提出了一种基于k-means的指纹定位算法，先对指纹库进行聚类并找到中心点，通过比较未知目标和中心点欧式距离确定未知目标属于的类，然后在该类中对未知目标定位。最后在Android平台上进行了实际测试，测试结果表明该算法能提高定位精度并缩短定位时间。

蓝牙信标；k-means；指纹定位；聚类

1 室内定位技术

自上世纪末以来，基于位置的服务[1-3]（Location Based Services,LBS）迅猛发展，成为了人们日常生活中必不可少的一部分。而伴随着小型智能移动终端的大规模普及，使得LBS有了更为广阔的发展空间。而LBS的核心是定位技术。GPS定位系统，北斗卫星定位系统等成熟的定位系统已实现了覆盖范围大、精度较高的室外定位。而在室内定位中，由于极为复杂的室内环境因素，GPS信号会受到极大干扰，基本无法利用GPS定位系统实现室内定位[4]。

目前常用的室内定位方法除了指纹定位算发还有时间到达法[5]（TOA），时间到达差法[6]（TDOA），信号强度测距法[6]（RSSI），到达角度差法[8]（AOA）等，这几种方法需要建立信号传播模型并对其中的参数进行估计，而复杂的室内环境使信号的多径传播产生反射和折射，很难对其中的参数进行准确的估计，从而使这些方法的定位精度不高。而基于信号强度的指纹算法作为临近关系定位技术的一种，在室内定位应用中由于其定位精度高而被广泛使用[9]。

图1 蓝牙信标指纹定位图原理

2 基于蓝牙信标的指纹定位技术

2.1 蓝牙信标指纹定位原理

基于无线信号指纹的定位技术是当前室内定位技术研究的重点。信号的多径传播对环境具有依赖性，呈现出非常强的特殊性,对于每个位置而言，该位置上信道的多径结构是惟一的,终端发射的无线电波经过反射和折射，产生与周围环境密切相关的特定模式的多径信号，这样的多径特征可以认为是该位置的“指纹”。

基于蓝牙信标的指纹定位就是在一个大区域布置n个蓝牙信标，在某一位置记录n个蓝牙信标的信号强度（rssi）作为其指纹数据，这样就可以在大区域得到m个指纹点作并建立指纹数据库，再通过指纹定位算法对未知目标进行定位（见图1）。

相较与基于wifi的指纹定位，采用低功耗蓝牙4.0标准的室内定位方法具有成本低、部署、方案简单、响应速度快等技术特点，加之手机设备厂商对蓝牙标准规范的大力推广，因而具有更好的发展前景[6]。

2.2 信号强度指纹定位算法

信号强度指纹算法指是目前最常用的指纹定位算法，它是基于室内环境复杂，信号反射折射所形成的在不同位置形成的不同的信号强度信息而提出的一套算法，利用已建立的指纹库信息，通过一定的推理运算得到位置目标的近似位置。主要算法有最邻近法法（NN）和K近邻法（KNN）。

2．2．1 最邻近法（NN，Nearest Neighborhood）

最邻近法是最简单的算法，首先确定参考节点个数并建立指纹数据库，设参考节点有n个，用Fi表示第i个指纹点收到n个参考节点的信号强度，那么某个指纹，这样就建立了指纹库。然后在某未知目标得到n个参考节点的信号强度，即，通过下式计算S与Fi的距离Di，找到与S距离最小的那个指纹Fm，将Fm的坐标作为未知目标的定位结果。

式中Sj表示位置目标受到第j个参考节点的信号强度，fij表示第i个指纹点收到第j个参考节点的信号强度，n即为参考节点总个数，当q=1代表曼哈顿距离，q=2代表欧几里得距离。q的取值不是固定的，可以根据具体情况来取q的值。

2．2．2 K邻近法（KNN，K Nearest Neighborhood）

K邻近法是在最邻近法的基础上做出的改进。K邻近法不再是取与S距离最近的那个指纹点的坐标作为最终定位结果，而是取与S距离最近的K个指纹点，计算这K个指纹点的平均坐标(x,y)作为最终定位结果，并在计算取q=2即取欧氏距离，如下式：

找到K个最近指纹点后：

在计算中一般取K=3，即找到三个最近指纹点用它们的三角质心作为最终定位结果。

3 kNN指纹定位法

传统的k均值指纹定位方法可以分为以下两个阶段。

第一阶段为训练/离线阶段，在目标区域内采集n个指纹点建立指纹库，每个指纹点到5个蓝牙信标的信号并得到一个5维向量作为其指纹信息。

图2 kNN指纹定位法原理图

4 k-means指纹定位法

针对以上传统knn指纹定位法的不足，本文提出了一种基于k-means聚类算法的指纹定位方法。

4.1 k-means聚类算法

K-means聚类算法是基于划分的聚类方法，一般常见的做法是同时提取N种特征，将它们放在一起组成一个N维向量，从而得到一个从原始数据集合到N维向量空间的映射，通过不断的迭代来实现聚类，当算法收敛到结束条件或者达到最大迭代次数时终止迭代过程，得出聚类结果。

这里ui表示分类Si的平均值。

其算法步骤一般如下：

①从D中随机取k个元素，作为k个簇的各自的中心。

②分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。

③根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。

④将D中全部元素按照新的中心重新聚类。

⑤重复第4步，直到聚类结果不再变化。

⑥将结果输出。

4.2 k-means指纹定位法过程

k-means指纹定位法可以分为三个阶段。

第一阶段为建立指纹库，同于传统KNN指纹定位法。

第二阶段为指纹库聚类阶段，如图3所示，可以设k-means算法中的k为4，选取4个指纹点作为其初始类簇中心点。由于初始类簇中心点的选择对最终聚类结果的影响非常大，在指纹库中随机选用4个指纹点作为初始类簇中心点容易造成局部收敛，与是采取的办法是先首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出4个初始类簇中心点。这样将n个指纹点分为A,B,C,D这4类，每一个指纹点都会被归入一类，每一个类中计算出一个中心点。这时，求未知目标与4个中心点的欧式距离，找到与未知目标欧式距离最近的点并将位置目标归入该类。

第三阶段为位阶段，定位时，只需要求未知目标与该类中的每个指纹点的欧式距离，找到该类中与未知目标欧式距离最近的三个指纹点求质心即可，这样大大减小了运算量，缩短了定位时间。并且在一个类中的指纹点距离不会出现较大波动，在一定程度上减小了定位误差。

图3 k-means指纹定位法原理图

5 实验过程

实验场所选取在一个长10米，宽8米大展厅，如图3所示。三星GALAXY S5 G9008V手机作为蓝牙信号接收设备，手机位置即为未知目标位置。选用brightbeacon作为信号发射设备。5个beacon布置在展厅的天花板上，位置如图1所示。在展厅中取均匀分布的30个指纹点，并在每个指纹点取每个beacon的120次rssi均值作为其指纹数据，建立指纹数据库。将beacon的发射频率设置为100ms，理论上手机每秒可以收到每个beacon的10个rssi值，可以用10个rssi值的均值作为该位置的rssi位置信息与指纹库的指纹点数据进行相应的定位计算。但是实际测量中，并不能保证在同一时间收到到每个beacon的rssi值个数一致，于是采用的方法是将手机在1s内收到的n次rssi值作均值作为位置目标的的指纹信息。按以上步骤，分别用knn算法和kmeans指纹定位法进行定位，得到数据如表1所示。