基于最小值的多映射数据结构指纹库定位算法

郭昕刚， 胡 朗

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

0 引 言

近年来，随着移动互联时代的到来，人们对定位导航服务的需求越来越多。基于GPS的室外定位已经为人们提供了很大的便利，如汽车的定位跟踪、高德地图、滴滴打车应用等。对于室内环境，由于室内建筑物的遮挡、信号的多径传播等影响，GPS定位不能满足室内对精度要求较高的定位需求。

针对室内WiFi的大量部署，WiFi室内定位技术已经成为当今室内定位的研究热点。基于WiFi的室内定位主流方向通常分为：基于测距(range-based)和测距无关(range-free)两种。基于测距的定位方法一般为通过待定位点与AP节点的距离或者角度来计算定位目标的位置，常见的有：接收信号强度指示(RSSI)、信号到达角度(AOA)、信号到达时间(TOA)以及信号到达时间差(TDOA)等[2]。而与测距无关的定位方法主要是依据对定位环境的场景特征分析，在定位时将待定位点的场景信息与参考点的场景信息进行对比实现定位，典型的应用算法是位置指纹法。该方法的主要优点是无需对AP节点位置和距离进行测量计算、无需添加额外的硬件设备。

在研究WiFi室内定位的过程中，基于位置指纹的定位方法是比较可行而且精度较高的定位方法，成为室内定位研究的热门方向。位置指纹定位方法主要分为离线阶段(off-line)和在线阶段(on-line)两个过程[3]。在离线阶段，主要通过智能终端的WLAN无线接入点，采集室内各个AP的特征信息，把这些信息如MAC地址、RSSI信号强度值以及采集点的位置坐标作为指纹存入指纹库中，遍历室内所有的采集点便构成了完整的位置指纹库。在线阶段通过智能终端实时接收到各个AP的RSSI信号值，通过与离线数据库的匹配找到与之相似的指纹参考点，进而估算出当前待定位点的位置坐标。

离线指纹库的合理构建和在线匹配算法的选择是影响WiFi室内定位精度和实时性的两个主要因素。通过规划和测量，按一定间距选取合适的参考点，在每个参考节点上测得各个AP的MAC地址和信号强度值。WiFi信号的时变性以及信号传播的复杂性，使得测量的信号强度值并不能直接存储，而是需要滤波之后再使用，避免各种奇异信号值和小概率信号值存储到指纹库中影响定位的稳定性[4]。实时在线阶段，需要使用合适的匹配算法去寻找相关的指纹参考点，与待定位点的欧式距离越小，权值就越大，对目标位置的定位贡献程度就越高。

对于上述问题，文中采用了多映射的数据结构来构建离线阶段的位置指纹库，使得每个参考点位置对应同一AP的一个或多个RSSI值，这样在线匹配阶段通过计算欧式距离最小值，找到与待定位点最匹配的K个参考点，用WKNN算法实现位置的估算。这种方法有利于提高指纹库的准确性，减小定位误差。

1 多映射数据结构的数据库滤波算法

影响室内信号传播的因素很多， 导致在采集信号的过程中同一位置对同一AP信号的不同时间RSSI值具有差异性[5]，因此需要对每个AP节点进行单独的数据采集与分析。移动终端在同一参考点处多次采集所获取的同一AP的RSSI信息,如图1所示。

对同一AP距离下的RSSI值采样分析发现，RSSI信号值并不是固定在某个值下不变的，而是随着采样时间的变化，RSSI值会发生波动[6]。由于室内环境存在多径效应等影响，这种波动是随机发生的，所以在构建指纹库前，通常需要对信号进行滤波处理。

将采集到的同一AP样本值{RSSI1,RSSI2,RSSI3,…,RSSIn}进行平均滤波：

(1)

依次遍历所有参考点的各个AP，并将所得的结果存入数据库，得到整个定位区间的离线指纹数据库[7]：

(2)

但在匹配的过程中，平均滤波对定位精度的优化效果并不理想，原因主要是平均滤波对所有测得的RSSI值进行计算，这将引入一些对定位无关的RSSI值，这些值通常出现的概率很小,甚至不会出现[7]。而在线过程中，采样时间很短，各种匹配算法都很难消除这些误差，导致匹配的结果会偏离实际位置很多。

图1 同一参考点所获取的同一AP的RSSI变化图

由于室内各个AP的独立性，所以需要对各个AP进行单独分析，对两组不同AP进行采集所得的RSSI值概率分布，如图2所示。

从图中可以看出，RSSI值的波动呈现一种线性回归状态，即RSSI在一定范围内波动，且具有上下限。若设置概率阈值为0.1，则图2(a)中RSSI值集中在-49～-46 dBm之间，图2(b)中RSSI值集中在-57～-55 dBm之间。

(a) 同一参考点接收到的AP1信号强度概率分布

(b) 同一参考点接收到的AP2信号强度概率分布

在室内环境复杂变化以及多径效应影响的情况下，大多数值都在上下限范围之内，极少情况会出现在范围之外，这说明各AP的RSSI值满足正态分布规律[8]。针对上述分析情况，文中提出了一种多映射的数据库滤波算法，合理构建离线指纹数据库，以提高在线匹配的精度。

针对各AP信号呈现的规律特征，在构建指纹库之前，采用高斯滤波滤除RSSI信号值中的非常规数值，保留出现可能性较大的RSSI数值。对每组AP的RSSI值处理则有：

(3)

(4)

(5)

式中：μ——样本信号强度RSSI的平均值；

σ——样本信号强度RSSI的标准差。

将概率范围在0.1≤f(x)≤1的RSSI信号值取出，滤除小概率的异常信号，经过高斯滤波之后的每组RSSI样本值的集合为：

(6)

针对采样信号RSSI值出现的频数大小从左到右进行降序排序，得到排序后的信号RSSI值的集合：

(7)

式中：nk——每个RSSI信号值出现的频数。

为了选取对定位有效的RSSI值存入到指纹库，下面将通过对频数排序后的RSSI信号值的集合进行筛选。首先选取出现次数最多的RSSI值的频数与集合中的总频数进行比较，所得的值如果大于概率阈值，则此次筛选结束，保留当前的RSSI值作为该点测得的RSSI信号值存入到指纹库。否则，将下一出现次数多的RSSI值的频数加到当前的RSSI值频数中，累加到一起与集合总频数比较，直到该占比大于概率阈值,并将这些累加的频数对应的RSSI值存入到指纹库。具体筛选的准则为：

(8)

式中：nk——对应RSSI值出现的频数；

pthreshold——筛选的概率阈值。

该算法这样筛选的目的是能最大限度地保留对定位有作用的RSSI值，在传统的指纹库中，同一位置点对应的同一AP仅仅只有一个值，而在该算法中往往可以得到同一位置对应的同一AP两个或者多个RSSI值。这样在定位匹配的过程中，可以找到与该位置最相近的RSSI值做比较。对应的指纹库见表1。

表1 多映射指纹库下参考点对应的RSSI分布表

室内定位范围内终端搜索到的AP节点有3个，分别为AP1、AP2和AP3。参考点RP1位置处AP1值为-48、-46 dBm，AP2值为-62、-59、-58 dBm,AP3值为-50、-47 dBm，这样RP1参考点存得的RSSI向量组合形式就有12种，在线匹配阶段，可以找到欧式距离最小的向量组合去参与匹配，降低最后的定位误差。

2 最小值的多映射数据结构在线匹配算法

在线定位阶段，比较常用的定位算法有最近邻算法(NN)、K近邻算法(KNN)和加权K近邻算法(WKNN)[9]。最近邻算法根据定位终端实时采集到AP的RSSI值与位置指纹库中的指纹信息进行匹配，找到相似度最大的位置指纹对应的参考点坐标作为待定位点坐标，而K近邻算法是找到位置指纹库中K个指纹点并求得对应参考点坐标的平均值。WKNN算法是在KNN算法上的改进，在找到K个指纹相似点之后，将每个相似点赋予不同的权重ωi，一般来说，离目标接近的指纹点对待定位点的贡献大，相应的权重值大；反之，离目标稍远的指纹点对带定位点的贡献小，相应的权重值小[10]。

为了找到对定位贡献最大的指纹参考点，在计算欧式距离过程中，文中引入了最小欧式距离的计算方法，舍弃了传统指纹库同一位置对应的同一AP下的单个RSSI值对定位造成的误差。具体步骤为：在线阶段我们测得各个AP的RSSI信息值，通过均值滤波得到每个AP的平均值，依次遍历所有AP就得到了该定位点的RSSI信息值。由于欧式距离的结果是两者所有对应AP节点相似度差值的累加，在参与欧式距离计算的过程中，找到接近于实时测得的相应AP的RSSI值参与计算，这样能够在指纹库中的多种向量组合中找到最接近定位的RSSI向量组合。

用RSSI={RSSI1,RSSI2,RSSI3,…，RSSIn}表示定位终端在待定位点测量到的n个AP的RSSI信号强度值，用rssij={rssi1,rssi2,rssi3，…,rssin}表示第j个指纹点存得的某一组合的信号强度，两点的RSSI信号强度的相似度用欧式距离表示为：

(9)

每个参考点的权重表示为：

(10)

式中：ε——一个无限接近于0的整数，目的是防止分母出现0的特殊情况。

最终待定位点的估计位置为：

(11)

3 实验与分析

文中提出的算法在长春工业大学计算机科学与工程学院实验室走廊区域进行实验验证，事先在定位区域部署3个AP发射点，以1.6 m的间隔规划一定的采样点，采用智能手机APP采集WiFi信号。在每个采样点处采集AP节点的RSSI信号值，并将每个AP采集样本首先进行高斯滤波滤除小概率的噪声值，然后对保留下来的每个RSSI依次排序并计算单个RSSI值的频数占总体频数的比值，设置概率阈值对其进行有效筛选，得到最终保留下来的单个AP的样本值，依次遍历所有AP就得到了该采样点的指纹信息，将其保存在数据库中。在线匹配的过程中，在线测得的待定位点的RSSI信息值与多映射数据结构的指纹库进行匹配，找到欧式距离最小的K个指纹点信息，最后通过WKNN求得带定位点的坐标。整个定位的过程具体流程如图4和图5所示。

图4 多映射数据结构指纹库构建流程 图5 基于最小值的多映射数据结构在线定位流程

实验结果采用误差累计分布函数(Cumulated Denstiy Function, CDF)来衡量本定位算法相对于传统指纹库以及匹配算法的精度和稳定性，结果如图6所示。

图6 传统指纹库对应匹配算法和文中算法累计误差图

文中提出的算法能够有效提高定位的精度，减小了WiFi信号的变化以及传统指纹库的局限性对定位造成的误差。从图中能够看出，文中算法的误差在3.5 m范围内，同等误差距离下，该算法累计误差概率提高了将近10%，验证了该算法的有效性和可行性。

4 结 语

针对传统指纹库单向量的构建形式造成的精度不高问题进行了深入分析，提出了一种多映射的数据结构指纹库以及最小值在线匹配算法，改变了传统指纹库的采样点对应每个AP的单个RSSI值的情况，以多个RSSI值映射同一个位置。在线匹配阶段，通过最小欧式距离的选择，能够找到拟合度最高的RSSI向量组合，得到对待定位点贡献大的参考点。实验结果表明，文中提出的定位算法在精度以及稳定性方面具有一定的提升，对基于位置指纹的室内定位研究提供了一定的参考作用。