2.3 基于指纹的定位技术

在室内环境中，路径损耗模型固有的不准确性，以及因障碍物造成信号的反射和衍射而导致的非视距传输与多径传输等因素，都会在测量距离时产生较大的误差，从而影响定位精度。指纹匹配，也称为场景分析，是一种日益流行的定位技术。通过在已知位置标记信号签名（指纹），并将这些信号签名与相关的位置信息一起存储在数据库中（数据库中的存储的数据也称为射频图），基于指纹的定位技术首先通过模式识别的方法来获取移动设备的指纹，然后通过指纹与射频图之间的最佳匹配来确定移动设备的位置^[14,16]。

2.3.1 基于指纹的定位技术概述

在移动设备中，既可以使用不同的内置传感器来标记指纹，也可以使用内置传感器来检测用户的活动模式。例如，用户可以使用相机进行拍照，并将图像与带有地理标记的图像进行匹配以识别位置；也可以通过麦克风检测不同地方的声信号；甚至还可以通过检测特定射频信号的接入点来判断用户是在办公室中还是在家中。环境中隐藏了复杂的线索，基于指纹的定位技术的目标是发现这些隐藏的线索，并有效地利用这些线索来估计移动设备的位置。

由于移动设备上的传感器越来越多，可以感知到越来越多的环境数据，这些环境数据为移动设备的定位提供给了新的机会。近年来，基于指纹的定位技术使用的指纹类型主要有三种，分别是视觉指纹、运动指纹和信号指纹。另外，通过融合不同的环境数据，还可以生产混合指纹。

1.视觉指纹

目前，大部分的移动设备（如智能手机或平板电脑）都配备了用于处理图像和视频部件，这使得视觉检索技术有了更大的用武之地，产生了许多基于内容的视觉检索技术，利用颜色、纹理、形状等视觉特征可以在图像数据库中检索相关图像和视频。随着视觉检索技术的发展，许多基于移动图像的检索应用得到了广泛应用，如Google公司的Goggles和PTC公司的Vuforia Object Scanner。Goggles是一款图像检索应用，可以识别移动图像中出现的产品、绘画、地标等，为用户提供有用的信息；Vuforia Object Scanner是一个Android应用程序，可利用计算机视觉技术实时识别和捕捉平面图像或简单的三维物体。

基于视觉指纹的定位技术示意图如图2-8所示，将捕获的图像作为查询输入，从带有地理标记的图像数据库中查询相关的图像，返回的是最佳匹配的图像，该图像可以用来确定移动设备的位置。

2.运动指纹

移动设备中的加速度计、陀螺仪等传感器，可以实时感知用户的运动数据。相关研究表明，运动数据不仅可以作为用户位置的签名，还可以提高定位的精度。

基于运动指纹的定位技术的思路是将加速度计和陀螺仪感知的运动数据结合起来，并将结合起来的运动数据与地图进行匹配，从而估计移动设备的位置。加速度计感知的运动数据可用于估计移动设备的移动距离，陀螺仪感知的运动数据可用于估计移动设备的移动方向。

3.信号指纹

移动设备和WSN的普及应用使人们对位置感知系统，以及基于位置的服务越来越感兴趣。在存在复杂无线电信号的环境中，与其他室内定位技术相比，基于信号指纹的定位技术受多径传输的影响较小，具有更高的定位精度。基于信号指纹的定位技术的思路是通过比较从多个锚节点（如WiFi的AP）接收到的信号模式和预先定义的信号模式数据库，从而估计移动设备的位置。

4.混合指纹

在大多数定位技术中，都存在定位精度和功耗之间的权衡。基于混合指纹的定位技术通过融合不同的环境数据（混合指纹），可以得到更高的定位精度，其鲁棒性更强。例如，将运动指纹与GPS模块结合起来，通过对运动数据进行分析，可识别用户当前的运动状态，如静止或运动。通过运动状态可以给出打开或关闭相关传感器或GPS模块的建议，从而可降低功耗。例如，当用户处于静止状态时，可关闭GPS模块，从而降低功耗、节省能量。

基于指纹的定位系统通常包括两个关键模块：指纹检测模块和指纹匹配模块。基于指纹的定位系统工作流程如图2-9所示。

2.3.2 常用基于指纹的定位技术

虽然基于指纹的定位系统都遵循如图2-9所示的工作流程，但根据指纹类型的不同，每种定位技术在实现细节、定位精度、能效和延时方面都有所不同。基于指纹的定位技术分类如图2-10所示。

1.基于视觉指纹的定位技术

基于视觉指纹的定位技术的关键是通过分析图像的内容，提取出图像的视觉特征，从而在地理标记图像数据库中检索相似图像的指纹。这种图像检索技术被称为基于内容的图像检索（Content-Based Image Retrieval, CBIR）技术，该技术是计算机视觉的一个研究重点。

CBIR技术的主要挑战是在大型数据库中检索数字图像的准确率和速度。采用k-Means算法后，可以使用词袋（Bag-of-Words, BoW）模型表示图像，将每个图像看成一个文档，将视觉特征（用于训练图像）聚类成不同的视觉词，用视觉词出现频率的直方图来表示图像。

基于视觉指纹的定位技术示意图如图2-11所示。

1）视觉指纹的生成

通过提取图形的视觉特征，可生成视觉指纹。视觉特征一般可分为全局特征和局部特征。全局特征是指图像的整体属性，如颜色、边缘和纹理；局部特征是指图像的内容，用于从图像的显著区域或斑块中提取的兴趣点。将全局特征与局部特征结合起来可以提高图形的识别性能。

兴趣点（Points of Interest, PoI）是使用特征描述符来捕获的，是图像的重要特征，对图像的理解和分析有着重要的作用。特征描述符是图像中每个区域的高维特征向量，具有唯一的兴趣点特征。在光照条件、尺度变化、仿射变换下，可通过尺度不变特征变换（Scale-Invariant Feature Transform, SIFT）算法来检测兴趣点。

通过k-Means算法可以将特征描述符转换成视觉词，用视觉词出现频率的直方图来表示图像，视觉词可作为大规模图像检索的指纹。图像被转换成文本文档（也称为反向文件）后，可采用文本检索方式来对图像进行检索。

2）视觉指纹的匹配

通过k-Means算法可以将图像检索问题转化为文本检索问题，使用反向文件可以有效地查询图像与数据库中的参考图像之间的相似性。反向文件的大小与参考图像的数量成线性关系，随着反向文件的增大，视觉指纹的匹配存在功耗高、延时长等问题，这是因为CBIR技术必须将待查询的图像与整个地理标记图像数据库进行匹配。

在基于视觉指纹的定位技术中，需要将检索区域限制在锚节点邻近区域中具有地理标记的图像。锚节点可以通过移动设备来粗略定位，确定锚节点后可以采用多种方法来检索锚节点的邻近区域。

在缩小检索区域后，可利用视觉指纹的匹配技术从地理标记图像数据库中找到最匹配的图像。大多数采用CBIR技术的匹配技术都使用最近邻检索（Nearest Neighbor Search, NNS）算法来计算两幅图像之间的距离，即两幅图像的相似度。首先获取图像兴趣点和特征描述符，然后通过NNS算法在检索区域中选择候选图像并将它们分组到不同的特征集合中（一个候选图像可以出现在多个特征集合中），最后将候选图像合并在一起，并根据每个候选图像在特征集合中出现的次数进行排序。例如，如果某个候选图像具有与特征描述符非常相似的颜色和边缘特征，则该候选图像可能会被分组到两个特征集合（颜色集合和边缘集合）中，在最后的合并过程中，该候选图像是根据它在两个特征集合中出现的次数来排序的。

3）视觉指纹的填充

地理标记技术是近年来数码相机中的一种流行功能。通过地理标记技术和GPS模块，可以为拍摄的图像添加地理坐标数据。目前，在互联网中，可以搜索到很多带有地理标记的地标性建筑图像。使用移动设备拍摄周围环境后，通过对比拍摄的图像和带有地理标记的图像，可确定移动设备的位置。

通过移动设备中的应用程序，如Flickr、Pinterest、Instagram、Photobucket和Picasa等，可以从互联网搜索带有地理标记的图像，通过这些图像可构建视觉指纹数据库。

2.基于运动指纹的定位技术

基于运动指纹的定位技术是通过用户的运动数据来确定其位置的，可通过加速度计和陀螺仪等传感器来感知运动数据。基于运动指纹的定位技术的关键部分是运动跟踪和地图匹配。运动跟踪主要采用航迹推算（Dead Reckoning, DR）算法来跟踪用户的运动速度和运动方向，该算法可利用移动设备中加速度计和陀螺仪等传感器来周期性地生成运动指纹。地图匹配是指通过对比地图和最新的运动指纹来估计用户当前的位置。

基于运动指纹的定位技术示意图如图2-12所示。

由于加速度计和陀螺仪等传感器可能存在噪声，因此基于运动指纹的定位技术的定位精度往往比较低。在地图匹配过程中，可以通过在数字地图中调整估计位置来细化用户的位置。另外，和其他定位技术结合起来使用，基于运动指纹的定位技术可进一步提高定位精度。例如，图2-12中的同步信号被经常当成锚节点，当地图匹配过程出现偏差时，允许移动设备（如智能手机）重新校准其位置。同步信号通常是通过其他定位技术生产的，如GPS定位技术和基于蜂窝网络的定位技术。

1）运动指纹的生成

DR算法通过定期记录来自加速度计和陀螺仪感知的运动数据，来估计用户的运动距离和运动方向，从而可生成运动指纹。DR算法需要进行两个估计距离估计和方向估计。

（1）距离估计。通过对加速度进行二重积分可得到距离，但移动设备中的加速度计的噪声较大，因此在通过加速度计的加速度来估计距离时，需要进行修正，特别是在进行行人跟踪时。利用行人的步长和步行模式来进行距离估计是可行的，常用的方法有基于步长的距离估计和基于步行模式的距离估计。

① 基于步长的距离估计。通过计算步行步数，然后乘以步长即可得到距离。

d=n_s×l_s

式中，d为距离；n_s为步行步数；l_s为步长。采用基于步长的距离估计方法时，关键在于如何根据加速度计的读数来检测步长。通过步长检测技术可解决该问题，步长检测技术是使用运动数据来检测步长的。

当用户在行走时，步长检测技术持续检测并分析从加速度计感知到的运动数据。假设感知到的加速度为a₁，a₂，…，a_n，可通过式（2-19）将加速度映射到位置，即：

式中，μ_n是加速度的平均值；σ_n是相应的标准差；∧是一个未定义的状态；阈值μ_n+σ_n和μ_n-σ_n分别表示水平向上和水平向下。通过式（2-19）可以产生一个包含“1”“0”“∧”的位置序列，将连续的“1”合并成1个“1”，将连续的“0”合并成1个“0”，将连续的“∧”合并成1个“∧”，从而形成一个包含“10”或“1∧0”的步长。当检测到一个步长时，将该步长报告给地图匹配过程，可提高定位精度。

② 基于步行模式的距离估计。移动设备（如智能手机）的不同位置会影响计步的准确性，但无论如何放置移动设备，加速度数据总是存在一些重复模式。为了方便起见，这里将模式称为周期。使用下面的公式可估计距离，即：

d=n_p×l_p

式中，d为距离；n_p为周期数；l_p为一个周期内的行进距离。在步长检测技术中，一个周期内的行进距离称为一个步长。

（2）方向估计。通过移动设备中集成的陀螺仪可以进行方向估计。陀螺仪产生的数据是相对于移动设备本身的笛卡儿坐标系而言的。笛卡儿坐标系是由正交的x、y、z轴表示的，x轴指向移动设备的右侧，y轴指向移动设备的顶部，z轴指向离开移动设备屏幕方向。虽然角速度在随时间变化，但每个轴上的角速度都遵循一个周期，因此对这三个轴上的角速度进行时间积分可以减小波动。此外，当用户按照直线匀速行走时，任何轴的平均加速度数据均波动不大。

陀螺仪通过检测三个轴上的角位移，可以估计运动的方向。在一个时间窗口内，如果三个角位移都未超过预先设定的阈值，则认为用户是在沿直线行走的。在用户沿直线行走的过程中，计算每个方向上的加速度平均值即可。行人在拐弯时的角位移调整量为：

式中，α、β、γ分别为第一步时的角位移；μ_x、μ_y、μ_z分别在每个方向加速度的平均读数。

2）地图匹配

当采用DR算法检测到一个新的步长或一个新的转弯时，可进行地图匹配，并通过检测到的新的信息来细化用户的位置。地图匹配有助于纠正由DR算法引起的误差，例如，如果将某辆正在行驶的汽车的位置估计到了某个建筑物内，则可通过地图匹配将这个估计的位置调整到最近的道路上。地图匹配的工作过程如图2-13所示。精确定位通常需要定位数据和数字地图，由于定位系统的误差，定位数据往往不在数字地图上，因此需要进行地图匹配，将定位数据放到数字地图上。

3）数字地图的构建

为了提高定位精度，在定位系统中经常使用数字地图作为用户位置的约束，可将DR算法返回的定位数据和数字地图关联在一起来估计用户的位置。数字地图是通过二维平面中的一个点子集，或者使用一组标记了纬度和经度的段标记来构建的，段标记或点子集表示实际地图中的道路。

3.基于信号指纹的定位技术

1）基于信号指纹的定位技术简介

基于信号指纹的定位技术通常使用接收信号强度（RSS）来构建信号指纹，即接收到的无线局域网（WLAN）接入点（AP）信号的功率。WLAN广泛部署在办公室、商业大厦、商场、机场、家庭等环境中，提供无所不在的区域覆盖，移动设备和无线接收器均包含了测量RSS的网卡，网卡通常每秒能够检测0.5个或1个信号的RSS，因此，基于信号指纹的定位技术得到了广泛的应用。

在WLAN覆盖的室内环境中，通常部署了大量的AP，每个AP发射的信号都会在特定位置留下了一个唯一的信号指纹，该信号指纹可用于定位。将RSS作为信号指纹的特征值，并与特定的空间位置关联起来，当获取某一特征值时，即可得到与该特征值相关联的位置信息，从而可实现定位。基于信号指纹的定位技术通常包括训练阶段和匹配阶段。训练阶段是指在特定位置测量特征值（如接收到AP信号的强度，即RSS），以建立射频图（RSS地图）的过程。匹配阶段是指通过对比实时测量到的RSS和RSS地图来进行定位的过程。

在基于信号指纹的定位技术中，训练阶段采集特定锚节点（如AP）的RSS，通常会在每个锚节点进行多次测量，取所有测量值的平均值作为最终的RSS，利用最终的RSS和锚节点的名字构建一个向量。这些与每个位置相关联的向量集合称为射频图。

在匹配阶段中，移动终端实时测量RSS，将实时测量的RSS与射频图进行比较，通过定位算法可得到位置信息。对定位算法的要求是尽可能简单，并具有足够的准确性。

由于WiFi网络在全球范围内得到了广泛的应用，因此大多数室内定位系统都采用基于WiFi信号指纹的定位技术，该技术具有成本低、定位精度高等优点，可用于任何已经覆盖WiFi网络的室内环境，无须安装额外的硬件设备。另外，在复杂的室内环境中，可能会出现到达时间、到达角度方面的误差，但WiFi信号强度相对比较稳定，使得基于WiFi信号指纹的定位技术比其他定位技术的定位精度高。

2）基于信号指纹的定位技术的工作流程

基于信号指纹的定位技术的工作流程可分为训练阶段和匹配阶段，如图2-14所示。

（1）训练阶段。当移动设备进入感兴趣的区域时，观测到的信号是无序的，必须将这些信号组织成信号指纹的形式。常用的信号指纹形式为：

式中，F_i（x，y）为移动设备在坐标为（x，y）处第i个位置生成的信号指纹；RSS_n为移动设备在第i个位置接收到的第n个锚节点（如AP）的信号强度；N为锚节点的数量。在信号指纹中，除了使用RSS，还可以使用锚节点（如AP）的MAC地址，形式如下：

式中，F_i（x，y）为移动设备在坐标为（x，y）处第i个位置生成的信号指纹；RSS_n为移动设备在第i个位置接收到的第n个锚节点（如AP）的信号强度；N为锚节点的数量；MAC_i为第i个锚节点（如AP）的MAC地址。

传统的定位技术使用移动设备接收到的信号来构建信号指纹，在基于信号子空间的定位技术中则使用阵列天线接收到的信号来生成信号指纹。阵列天线不仅会受到障碍物的干扰，还会接收来自直接路径和多条反射路径的信号。接收到的信号x（t）可表示为：

式中，M为直接路径和反射路径的总数；a（θ_i）为一个导向向量，表示在每个天线接收到的信号的相移；A为L×M的导向矩阵。可利用接收到的信号构造的信号子空间作为信号指纹来估计移动设备的位置。

（2）匹配阶段。在匹配阶段中，通常采用基于欧氏距离的匹配算法，先比较测量的信号指纹与信号指纹数据库中每个锚节点信号指纹的欧氏距离，然后通过最近邻（NN）算法来选择欧氏距离最小的信号指纹。两个信号指纹之间的欧氏距离定义为：

式中，N为锚节点（如AP）的数量；RSS_RL和RSS_ML分别为锚节点的RSS向量和测量位置RSS的向量。

随着训练阶段被测区域的增多，信号指纹数据库会迅速增大，使得匹配效率急剧下降。为了提高匹配效率，需要对信号指纹进行滤波，只保留可能影响定位结果的信号指纹。在进行信号指纹滤波时，最简单的方法是选择RSS最大的锚节点，并找到所有包含该锚节点的信号指纹。另外一种方法是，选择几个锚节点进行查询，找到包含这几个锚节点的所有信号指纹。

3）基于信号指纹的定位技术中的常用定位算法

在基于信号指纹的定位技术中，需要先在离线阶段收集RSS，然后在匹配阶段比较测量的RSS和信号指纹。匹配阶段常用的定位算法有以下几种。

（1）概率性算法。假设位置候选集L={L₁，L₂，L₃，…，L_m}，在检测到信号的RSS向量O后，如果移动设备在某个位置的概率高于其他位置的概率，即：

则可将移动设备定位在位置L_j。如果P（L_j）=P（L_k），j，k=1，2，3，…，m，则利用贝叶斯定理在不同位置计算P（O|L_i），i=1，2，3，…，m，可得到检测到的信号RSS向量O的位置似然概率。如果

则可将移动设备定位在位置L_j。对于独立的锚节点，可以利用所有锚节点的概率乘积来计算位置似然概率。

如上所述，基于信号指纹的定位技术是通过对比观测到的信号RSS与信号指纹来进行定位的，信号指纹可以看成离散网格上的点，因此使用该技术进行的定位是离散定位，而不是连续定位。从理论上讲，减小离散网格上的点之间的距离，即增加网格的密度，就可以实现连续定位。但是，相邻两个点对应的信号指纹RSS差将比实际RSS的变化小得多，这使得正确地进行点估计是不可能实现的。因此，需要在信号指纹的位置粒度与位置估计成功率之间进行权衡。

（2）确定性算法。常见的确定性算法有NN算法、kNN算法和WkNN算法。WkNN算法与kNN算法类似，但对不同的RSS向量赋予了不同的权值。

（3）支持向量机（SVM）。支持向量机是一种很有吸引力的数据分类和回归算法，主要用于机器学习（ML）和统计分析，也可以在基于信号指纹的定位技术的训练阶段和匹配阶段作为定位算法来使用。

（4）人工神经网络（ANN）。使用RSS向量和相应的坐标对人工神经网络进行训练后，就可以将人工神经网络用于定位。隐层节点的多层感知器（Multi-Layer Perceptron, MLP）网络可用于定位。在基于MLP的定位中，为不同的RSS向量赋予不同的权重后，将其添加到输入层偏差中，将得到的结果代入隐层的传递函数；将传递函数输出与经过训练的隐层权值的乘积添加到隐层偏差，可得到估计的位置。

（5）质心定位算法。如果已知锚节点的位置，则可以通过质心定位算法得到一个经过信号指纹校准的质心辐射图，并使用一个加权质心来计算锚节点在该辐射图中的位置。采用质心辐射图的定位精度不如射频图高，但比采用射频图的定位简单，适合对定位精度要求不高的场合。

4.基于混合指纹的定位技术

混合指纹中包含了多种类型的指纹，基于混合指纹的定位技术可以得到更高的定位精度。采用基于混合指纹的定位技术的定位系统，可以使用多种类型的指纹或不同的定位技术。另外，周围的环境信息对这种定位系统的影响也比较大，因此在实际应用中，往往会将环境信息和不同类型的指纹结合起来，以捕获更加丰富的环境特征来进行定位。