基于特征匹配和距离加权的蓝牙定位算法

陆明炽，王守华，李云柯，纪元法，孙希延，邓桂辉

(卫星导航与位置感知重点实验室(桂林电子科技大学)，广西 桂林 541004)(*通信作者电子邮箱hwafly@guet.edu.cn)

0 引言

以全球导航卫星系统(Global Navigation Satelite System, GNSS)为主的室外定位技术日益成熟，在多个领域中有着广泛的应用前景，然而在大型商场、室内停车场和机场等复杂的室内环境中，因信号遮蔽等原因，而无法实现定位[1]。为实现室内定位，学者们提出了多种室内定位技术，如地磁场定位、惯性导航定位、计算机视觉定位、WiFi定位、超宽带(Ultra Wideband, UWB)定位[2]、低功耗蓝牙(Bluetooth of Low Energy, BLE)定位等。这些定位技术各有优点，但是或因定位精度不高，或因需要特殊接收设备，或因维护成本高等原因而没有得到大规模的应用[3]。如UWB的到达时间差(Time Difference Of Arrival, TDOA)室内定位技术可实现高达厘米级的室内定位精度，但是因为需要特殊接收设备而无法在智能手机等常用的电子设备上应用，且要求空旷的室内环境，因此没有得到大范围的商业应用。近年来，BLE室内定位技术因为覆盖范围广、低功耗、传输快等优点而引起了研究者的广泛关注[4]，特别是在iBeacon推出后，低功耗蓝牙定位技术得到了快速发展。一般的智能手机都配备了蓝牙数据接收模块，因此在室内环境中只需额外地増加一些低成本的iBeacon信标就可以在智能手机上实现米级的室内行人定位。文献[5]提出了一种基于接收信号强度值(Received Signal Strength Indication, RSSI)测距的室内定位算法，该算法在室内环境中对iBeacon的RSSI的衰减模型进行了较为精确的建模分析，但实现的定位精度并不理想。RSSI指纹定位和邻近发现是iBeacon室内定位技术的主要方式[6],而RSSI指纹定位可分为离线采集及在线定位两个阶段。文献[7] 提出了一种基于贝叶斯理论的RSSI概率分布蓝牙室内定位算法，该算法利用最大后验概率来确定移动目标的位置，算法复杂，存在较大的跳变误差；文献[8]提出了一种增强型高斯混合模型iBeacon室内定位算法，该算法实现了较高的定位精度，但是算法复杂，难以在智能手机等移动终端上实现。

在面对一个数据庞大的RSSI指纹库时，为减少指纹匹配的计算量，可先对指纹位置点进行聚类分析，找到一个最可能的RSSI向量簇，然后基于该向量簇使用某种定位算法匹配出定位位置点。文献[9]提出了K-mean法以实现指纹库的聚类，该算法有着简单易实现的特点，但须提前确定聚类数量，不适于指纹采样数量不确定、位置不规则的定位环境；文献[10]提出了AP法，该算法误差小，聚类效果好，且无须提前确定聚类个数，但计算量大，在对指纹点较多的指纹库进行聚类时耗时太久，不利于在移动终端上实现。

为了降低指纹库的聚类复杂度，提高iBeacon的定位精度，本文提出一种基于特征匹配和距离加权RSSI的指纹定位算法。在离线阶段，该算法先根据RSSI的大小生成排序特征向量和排序特征码，然后利用RSSI向量、排序特征向量、特征码、位置坐标组成一个指纹信息，并保存在指纹库中；在在线定位阶段，根据排序特征向量完全匹配算法、排序特征向量最相似匹配算法与基于距离的最优加权K最近邻(Weighted K Nearest Neighbours， WKNN)定位算法实现定位。

1 基于距离最优加权KNN定位算法

在在线RSSI指纹定位阶段，最常用的iBeacon室内定位方法是最邻近法(Nearest Neighborhood in Signal Space， NNSS)、K最近邻(K-Nearest Neighbors, KNN)定位法及加权K最近邻(WKNN)算法。NNSS核心思想是：在离线阶段，采集待定位场所的RSSI向量并制作指纹库；在在线定位阶段，分析实时接收的RSSI向量与指纹库的RSSI向量的相关性以实现当前位置的估计[11]。可以用两种RSSI向量的距离来描述该相关性，即当实时接收的RSSI向量与指纹库中某个RSSI指纹向量的距离最小时，该指纹向量对应的坐标即为当前目标的坐标。但实时接收的RSSI可能因某个蓝牙信标的RSSI存在突变现象而造成解算距离的误差增大，从而使定位精度降低。因此，为了提高NNSS算法的定位精度，可先求解前k个距离最小的指纹，计算其对应坐标点定位的平均值作为当前时刻t目标的坐标值，这也是KNN定位法的基本思想。而WKNN算法是对前k个距离最小坐标点进行加权处理而取代KNN定位法中的平均值，可以实现更高精度的定位[12]。在此基础上，本文提出了一种基于特征匹配和距离加权RSSI的指纹定位算法。算法可描述为：

求解实时接收的RSSI向量与指纹库中所有RSSI指纹向量的距离Si(R)：

(1)

其中：R为实时接收的RSSI向量；Fi为RSSI指纹库中第i个指纹向量。当q=1时，Si(R)为R与Fi之间的曼哈顿距离；当q=2时，Si(R)为R与Fi之间的欧氏距离。

此时，若选取Si(R)中最小的值在指纹库对应的坐标作为t时刻目标的坐标，即为NNSS，如式(2):

(2)

式中:Smin为Si(R)中的最小值，Lmin为Smin在指纹库中对应的坐标值，Lreal为定位目标在时刻t的坐标值。

若选取Si(R)中前k个最小的值在指纹库中对应坐标点的平均值为t时刻定位目标的坐标，即为KNN定位法。设t时刻前k个S(R)最小值在指纹库中对应的坐标值的集合为Lt，如下式:

Lt={Ln};n=1,2,…,k

(3)

其中，Ln为第n个S(R)最小值在指纹库中对应的坐标，则定位结果为:

(4)

根据一定的权值计算模型解算前k个Si(R)最小值在指纹库中对应坐标的权值的KNN定位法即为加权KNN定位法，如式(5):

(5)

其中，λn为第n个S(R)最小值在指纹库中对应的坐标的权值。现利用最优加权模型，根据与t-m时刻确定的目标定位点坐标值的距离确定加权KNN中的权值。

设前t-m时刻确定的目标定位点坐标值的集合为:

Lb={Lt-j};j=1,2,…,m

(6)

其中:m表示与当前时刻t的时间间隔。m过小，则用来计算Lb权值的数据过少，结果会受影响；而m过大，则计算复杂度增加，且对应Lb的权重值较小，对定位结果几乎没有影响，故需取一个合适的值。实际应用时，可根据实际情况而定，一般4≤m≤6。第n个候选点到前t-m时刻确定的目标定位点坐标的距离d(n)为：

(7)

所有候选点的距离的总和Ysum为:

(8)

则第n个候选点所占权重值ρ(n)为:

(9)

基于距离的最优加权RSSI指纹定位算法在t时刻确定的目标定位点坐标为:

(10)

由上述推导可知，在t时刻的所有候选点中，与t-m时刻确定的目标定位点坐标值的距离越大，则其权重值越小，这避免了因距离过大而产生定位跳变的现象。

2 排序特征向量指纹匹配定位算法

2.1 排序特征向量完全匹配算法

由iBeacon信标室内布设模型的RSSI的分布及RSSI衰减模型可知，当接收到的RSSI越小时，对应的平均误差越大，定位精度越差[13]，因此可将各RSSI按从大到小的顺序进行编号，设计一种排序特征向量指纹匹配算法实现RSSI指纹精确而快速的匹配。为简化室内定位环境而对算法原理进行简明的描述，可将5个iBeacon信标均匀布设在室内平面中，形成一个正方形，如图1所示。iBeacon分别标识为iBeacon1、iBeacon2、iBeacon3、iBeacon4和iBeacon5，分别对应相应的位置坐标。在室内环境中采集四个指纹位置点，分别是A、B、C、D点，另有三个待定位点，分别是E、F、G。

图1 iBeacon及示例点的分布

分别在各位置点采集各iBeacon 到接收设备的RSSI，分别对应为rssi1、rssi2、rssi3、rssi4、rssi5，并组合成向量(rssi1,rssi2,rssi3,rssi4,rssi5)。用排序特征向量表示按由大到小的顺序进行编号的RSSI。将指纹位置点和待定位点的RSSI分别按由大到小的顺序进行标记，记为1、2、3、4和5，然后按原顺序进行排列而得到对应的排序特征向量和排序特征码。如A点的RSSI向量为：A(-79，-81，-63，-73，-69)，按RSSI由大到小的顺序进行编号，RSSI值最大值为-63，对应的编号为1，最小值为-81，对应的编号为5，待所有值都编号后，按原顺序进行排列得到排序(4，5，1，3，2)，所以A点对应的排序特征向量和排序特征码分别为(4，5，1，3，2)、45132。根据上述原理，以A、B和E点为例，提取各点对应的排序特征向量和排序特征码如表1所示。

表1 各个位置点的排序特征向量和特征码

在指纹定位阶段，利用待定位点特征码对指纹库中的各个指纹点特征码进行匹配。在匹配过程中，设在指纹库中为找到排序码完全相同的点的个数为mf，则有：

(11)

当mf=1，即有且只有一个特征码完全相同的点时，则该指纹点对应的位置坐标为当前定位点的坐标；当mf=gf且gf≥2，即找到多个排序码完全相同的点时，则利用基于距离最优加权RSSI指纹定位算法求得当前定位点的坐标。

2.2 排序特征向量最相似匹配算法

当没有在指纹库中找到排序特征码完全相同的点，即mf=0时，可设计排序特征向量最相似匹配算法求解待定位置的坐标。待定位点RSSI向量的排序特征向量R为：

R=(r1,r2,…,rw)

(12)

其中,下标w表示排序特征向量的维数。

指纹库中的排序特征向量Q集合为:

Q={Qi}=(q1,i,q2,i,…,qw,i)

(13)

其中，下标i表示指纹库中第i个指纹，i=1,2,…,M，M为指纹库中待筛选的指纹排序特征向量的总数。

可设排序特征向量下标位置变量为ω(ω=1,2,…,w),偏移值变量为β,待筛选的指纹排序特征向量集合为X,相似指纹排序特征向量集合为Y，其内部包含相似指纹排序特征向量的个数为g。

排序特征向量最相似匹配算法的基本原理可分为以下步骤：

步骤1 初始化， 排序特征向量下标位置变量ω=1；偏移值变量β=0，待筛选的指纹排序特征向量集合X=Q；相似指纹排序特征向量集合Y=∅，Y排序特征向量的个数g=0。

步骤2 若rω=qω,i，则Qi添加到集合Y中，其中i=1,2,…,M。

步骤3 判断集合Y是否空，若是，则执行步骤4，若不是则执行步骤5。

步骤4Y=∅，g=0，β=β+1，且rβ与rω-β互换，执行步骤2。

步骤5 判断g的大小，当g≥2时，ω=ω+1，Y=X，执行步骤2；当且仅当g=1时，Lreal=LQi，其中，Lreal为定位目标在时刻t的坐标值，LQi为指纹排序特征向量Qi对应的位置坐标。

3 本文算法

3.1 RSSI加权滑动窗处理

蓝牙接收设备在扫描得到iBeacon的信息时，易受环境或硬件的影响导致RSSI产生较大波动。为了克服这个问题，可利用正常情况下前后时刻扫描得到的RSSI不会出现较大跳变的原理[14]，设计加权滑动窗对在线定位阶段扫描到的RSSI进行加权处理。由于加权滑动窗窗口过长会降低定位解算实时性，故其窗口宽度设计为3，可描述为:

(λj,kλj,k-1λj,k-2)(rj,krj,k-1rj,k-2)T

(14)

3.2 指纹定位算法实现

本文提出的基于特征匹配和距离加权RSSI的指纹定位算法分为两个阶段：基于排序向量法的指纹库离线采集阶段；基于排序特征向量匹配的RSSI指纹定位算法和基于距离最优加权KNN定位算法的在线定位阶段。图2为离线阶段指纹库采集流程。

如图2所示，在离线指纹采集阶段进行RSSI指纹库制作时，因为特征向量的维数kR过大会增加算法的运算复杂度，所以可先确定排序特征向量的维数kR，一般kR≤6。采集各个指纹点的RSSI后，取前kR个最大的值按大到小顺序进行编号，并生成对应的排序特征向量和排序特征码。利用RSSI向量、排序特征向量、位置坐标组成指纹信息，并保存在指纹库。在室内定位环境中按固定的距离不断采集指纹点的指纹信息，完成整个指纹库的制作。

在线实时定位阶段可分为以下步骤：

步骤1 下载室内地图和对应的指纹库；

步骤2 通过在待定位点进行扫描而实时获得各个iBeacon信标到该点的RSSI向量，采用加权滑动窗对RSSI进行处理，取RSSI前kR个最大的值生成该点对应的排序特征向量和排序特征码；

步骤3 用排序特征向量完全匹配算法在RSSI指纹库中寻找与该排序特征码完全匹配的点，并判断是否找到匹配点，若找到了，则执行步骤5，否则执行步骤4；

步骤4 用排序特征向量最相似匹配算法找到最相似匹配点；

步骤5 判断是否只有一个定位匹配点，若是则执行步骤7，否则执行步骤6；

步骤6 用基于距离的最优加权KNN定位算法求解出一个定位坐标；

步骤7 输出定位结果，实现定位。

图2 离线阶段指纹库采集流程

4 算法测试仿真

4.1 iBeacon布设方案及聚类效果测试分析

在室内环境中，iBeacon的布设方式直接影响基于特征匹配和距离加权RSSI的指纹定位算法的特征码分布，从而影响定位精度。为了提高定位精度，可先分析iBeacon布设方案及聚类效果。现进行以下两组实验，iBeacon布设方案分别如图3(a)、(b)所示：a组使用5个iBeacon信标，其中4个布设成一个边长为40 m的正方形，另外1个布设在正方形的中心点处；b组也使用5个iBeacon信标，选择1个边长为40 m的正方形，5个iBeacon信标均匀布设于正方形的对角线上。对a、b两组布设方案的排序特征码进行仿真分析，特征码分布图如图3(c)、(d)所示。

由图3的仿真结果可知，基于特征匹配和距离加权RSSI的指纹定位算法的排序特征码会按距离对形成的指纹库进行划区。划分的区域和iBeacon信标数量有关，iBeacon信标数量越多，划分的区域越多。用相同数量的iBeacon信标，b组比a组在指纹库中分割的区域更为详细，即iBeacon信标布设在非边角区域比布设在边角区域效果好。当应用于面向行人的实际室内中,因定位环境的不同, 如在走廊等窄长环境,可适当作出调整，如减少iBeacon的数量而将其布设在非边角区域。

图3 iBeacon布设方案和特征码区域划分

本文以室内空旷的大厅环境为例进行分析，选用b组iBeacon信标布设方案。基于特征匹配和距离加权RSSI的指纹定位算法会根据iBeacon的布设情况自动对指纹库进行区域聚类，为了分析其聚类的效果，与文献[10]中提出的AP聚类法进行对比。现对b组iBeacon布设方案进行聚类分析，在定位区域内随机产生100个位置点，分别利用AP聚类法和排序特征法得到的聚类效果如图4所示。

由图4可知，排序特征法聚类的种类更多，相应每类的个数更少。当在智能手机实现定位时，若每个类的总数量过大，则会增加运算的复杂度。在基于排序特征码的聚类过程中，每个指纹点采集指纹后生成特征码即可自动进行聚类归类，无须像AP聚类法一样在全部的指纹采集完成后才通过运算进行聚类。在基于RSSI指纹定位技术的应用中，排序特征向量匹配法只需对每个采样的前kR个最强RSSI进行排序，就可以在指纹采集阶段自动完成聚类，相比利用AP聚类法等定位耗时少，更适合在智能手机上应用。

图4 AP法和排序特征法的聚类效果对比

4.2 RSSI加权滑动窗处理测试仿真

本文使用的iBeacon信标选用智石科技有限公司的Max Beacon信标，其内含蓝牙芯片为nRF51822III，并以0 dBm为发射功率，辐射范围为80 m。以华为荣耀7i智能手机作为蓝牙接收终端，并研发App实现蓝牙数据接收。接收的数据通过USB传送到电脑，然后利用Matlab进行仿真分析。

在制作指纹库阶段，通常利用一段时间内RSSI的平均值来标识该点的位置，故在指纹匹配定位阶段，若实时得到的RSSI越接近于平均值，则定位误差越小。对RSSI加权滑动窗进行处理，可使RSSI更接近平均值。为了分析加权滑动窗对异常点的抑制效果，可静止在同一个位置上进行测试，测试结果如图5所示。由图5可知，在线定位阶段，对扫描得到的RSSI进行加权滑动加窗处理后， RSSI更接近这个指纹点的RSSI均值，更有利于定位匹配算法的实现。在本文实验坏境下，经过多次测试和校正后，可得到rj对应权值λj的经验值，即当λj=(0.59 0.29 0.22)时，各个时刻的RSSI与平均值较为相近，异常点得到了较好的抑制。

图5 RSSI加窗处理

4.3 定位结果分析

以下设计室内定位实验来验证本文算法的性能。本次测试实验场地选在长为20 m、宽为10 m的长方形室内空旷的大厅环境中，使用8个iBeacon信标，分别均匀布设在该实验场非边角地区，如图6所示。

图6 测试实验场地示意图

iBeacon信标的编号和坐标分别为A1(150,150)、A2(850,150)、A3(500,575)、A4(150,1 000)、A5(850,1 000)、A6(500,1 425)、A7(150,1 850)、A8(850,1 850)。在离线指纹采集阶段，为了制作指纹库，每隔0.5 m采集一个指纹点，进而把实验场地均匀划分成边长为0.5 m的若干个正方形区域。每个点的指纹信息包含了在该点对应的RSSI向量、排序特征向量、排序特征码和位置坐标，所有指纹点信息组成指纹库。在本实验中，iBeacon采用电池供电，正常供电时间可达2年，故指纹库有效期相对较长。同时，当指纹失效时，需对指纹库进行更新，可在蓝牙指纹采集时设立指纹添加和删除模块，实现指纹信息补充采集或更新。

按要求采集所有指纹信息完成iBeacon指纹库后，开始进行移动定位测试。测试时，移动轨迹如图6中实际行走轨迹所示，从B1点出发，沿东向行走4 m，然后沿南向行走16 m，最后再沿东行走4 m到达B2点。行走过程中，利用蓝牙接收终端接收各个iBeacon信标的信息，然后分别用本文提出的基于特征匹配和距离加权RSSI的指纹定位算法与文献[7]提出的朴素贝叶斯法进行定位解算，得到定位轨迹如图7所示。从图7可以看出，相比利用朴素贝叶斯法实现的定位，利用本文算法实现的定位更接近于实际行走的轨迹，点与点之间的波动范围较小，定位结果更稳定。为了进一步分析算法的定位精度，可计算它与实际行走轨迹的误差，结果如表2所示。

图7 定位轨迹

从表2中可以看出:基于朴素贝叶斯定位算法的定位误差在1.623 m内，平均定位误差为1.152 m，运行时间为0.795 ms；基于文献[8]提出的增强型高斯混合模型法误差在1.234 m内，平均定位误差为0.964 m，运行时间为0.632 ms；本文算法虽然也存在一定的定位误差，但是定位精度在0.952 m内，平均定位误差为0.692 m，运行时间为0.573 ms，性能相对更好。

表2 多种方法的性能比较

为了分析iBeacon信标节点数量及其布设方式对定位精度的影响，在相同的室内环境和指纹库采集方式下做以下三组实验：第一组，使用5个iBeacon信标节点并将它们布设在边角区域上；第二组，使用5个iBeacon信标节点并将它们布设在对角线非边角区域上；第三组，使用8个iBeacon信标节点，并将它们布设在对角线非边角区域上。

表3 定位误差对比

由表3可知，第一组实验和第二组实验只有iBeacon布设方式不一样，而第二组的平均定位误差较小，所以iBeacon信标布设在对角线非边角区域定位效果较好；第二组实验和第三组实验只有iBeacon信标节点的数量不一样，而第三组的平均定位误差较小，所以一定数量范围内iBeacon信标节点越多定位精度越高。在室内的行人定位中，可根据实际定位精度的需求调整蓝牙信标之间的距离，即在同一个场所内，可适当增加信标的数量从而提高定位精度。

5 结语

针对传统蓝牙指纹定位技术存在指纹库的聚类复杂度大、定位跳变性误差较大的问题，本文提出基于特征匹配和距离加权RSSI的指纹定位算法，该算法在离线阶段根据排序特征向量等信息组成指纹信息，形成指纹库。在在线定位阶段，根据排序特征向量完全匹配算法、排序特征向量最相似匹配算法和基于距离的最优加权KNN定位算法实现定位。该定位方法可自动根据特征码进行聚类，从而有效降低聚类的复杂度，能实现0.952 m内的定位精度，适合在智能手机上实现行人定位而应用于室内停车场等场所。实际应用时，可适当增加信标的数量以提高定位精度。但是该算法也存在实现更高定位精度时需要采集大量指纹点的缺点，因此当应用于在走廊等环境时，可适当减少指纹点的数量从而减少采集量，在定位精度和计算复杂度间寻求均衡。