2018, Vol. 48
2. 新南威尔士大学 计算机科学与工程学院，澳大利亚 悉尼 2052
2. School of Computer Science and Engineering, University of New South Wales, Sydney 2052, Australia
伴随着物联网技术与各种各样基于室内位置应用的快速发展[1-2], 对高精度以及实时性的室内定位服务需求变得越来越强烈。在过去的十年之中, 基于WiFi[3]、RFID[4-6]、声音信号[7]、磁场信号[8]以及惯性传感器[9-11]等众多室内定位技术发展了起来。在所有以上的技术之中, 由于WiFi设施的实用性以及已经在各种室内场景中被广泛地布置，使得基于WiFi的室内定位技术在所有技术之中最具有吸引力。许多大公司包括苹果、思科、华为以及百度等都研发了基于WiFi室内定位相关的产品。
基于WiFi的室内定位技术主要有两种不同的方向:基于测距的定位技术与基于指纹的定位技术。基于测距的定位技术利用信号在空间传播的过程，这也是信号能量衰减的一个过程, 并且传播距离越远信号衰减得也越强烈, 从而这种衰减暗含了距离信息。基于测距的定位技术根据当前位置接收到的信号强度来推算出与接入点之间的距离，从而进行定位。基于指纹的定位技术利用当前位置多个接受信号强度直接进行位置估计，而不利用信号强度进行测距, 通常将特定位置上的多个信号的信号强度排列在一起构造成为一个高维的向量, 这个向量称为该位置的无线指纹, 通过计算采集指纹与数据库各个指纹之间的相似度可以定位未知节点。
然而, 在复杂的真实环境之中, 信号传播的动态特性以及环境的不稳定性通常会对信号传播距离的计算产生很大的误差, 从而使得基于测距的定位技术很难达到较高的精度。在目前的实际运用中, 基于指纹的定位技术最广泛。为了带领读者更深入地了解这一项正在蓬勃发展的技术, 本文通过理清基于指纹的室内定位技术的发展脉络, 展示不同定位方法的优势与不足, 同时展望未来指纹定位的发展方向。
1 早期指纹定位早期指纹定位系统体现了指纹定位的基本方法, 到目前为止, 这些方法也依然在室内定位领域有着旺盛的生命力。在此, 我们介绍两种经典的室内定位系统:RADAR[12]与Horus[3], 借此两个系统来展示指纹定位的核心方法。
1.1 开山之作——RADARRADAR[12]是使用无线指纹进行室内定位的开山之作, RADAR的出发点在于对于同一个信号接入点(Access point, AP)产生的WiFi信号, 不同位置的接收信号强度(Received signal strength, RSS)会有一定的区分度, 同一位置的RSS会保持相对的稳定。基于此两项RSS分布的特点, 我们将特定位置上的多个AP的RSS值排列在一起构成的高维向量称为该位置的WiFi信号指纹, 通过计算不同指纹之间的相似度来定位未知节点。RADAR等一系列基于指纹定位的系统主要包含两个阶段:线下阶段与线上阶段。
在线下阶段, RADAR通过收集所有AP的RSS空间分布信息, 完成信号强度位置(RSS-location)数据库的构建。具体而言, 可以得到空间之中所有采样点的位置空间L={l1, l2, …, ln}, 其中n是空间之中采样点的个数, li表示的RSS指纹采样点坐标为(xi, yi)。
对于每一个采样点, 我们可以得到该点采集到的指纹fi={fi(j)}, 1≤j≤m, 其中m是空间中所有能采集到的AP的数量, fi(j)代表在位置li收集到的第j个AP的RSS值, 从而还可以得到一个指纹空间F={f1, f2, …, fn}。结合位置空间, 可以得到反映空间信号特征的指纹位置数据库, 这个数据库的构建可以使用实地采样或者众包的方法。
在线上阶段, 定位系统根据构建好的指纹位置数据库提供定位服务。一个未知位置的节点测量其当前所处位置的所有AP的RSS值，并形成一条查询RSS指纹，然后将该查询指纹上传到定位服务器。定位服务器将该查询指纹依次与数据库之中的指纹计算相似度, 并利用最近邻(nearest neighbor)或者K-近邻(K-Nearest Neighbor, KNN)算法返回定位结果。在评估指纹的相似性方面, 最常用的方法是计算两个指纹向量之间的p-范数距离。具体来说, 如果有一条查询指纹fQ, 目前与之匹配的数据库中候选指纹为fC, 那么两条指纹之间的距离d(fQ, fC)可以表示为
| $ \begin{array}{l} d\left( {{f_Q},{f_C}} \right) = {\left\| {{f_Q} - {f_C}} \right\|_p} = \\ {\left( {\sum\limits_{j = 1}^m {{{\left( {f_Q^{\left( j \right)} - f_C^{\left( j \right)}} \right)}^p}} } \right)^{1/p}}。\end{array} $ | (1) |
其中，m是所有AP的个数, 在通常情况之中p取2, p-范数距离退化为欧式距离。在最近邻算法下, 定位结果可以表示为
| $ l_Q^ * = \arg {\min _{{l_C} \in L}}d\left( {{f_Q},{f_C}} \right)。$ | (2) |
Horus[3]是基于无线指纹定位中比较经典、用途很广的系统之一。Horus改进了采用确定性指纹匹配策略的RADAR系统。在实际环境之中, 如图 1所示, RSS具有一定的波动性, 并且这种波动性近似一个正态分布。Horus提出了基于统计的方法, 将所有位置上采集到的指纹中每一个的RSS值建模为一个高斯分布, 同时, 对指纹匹配的算法由计算欧氏距离改为最大似然估计的方法。
|
图 1 RSS波动性示意图 Fig. 1 RSS bias over time |
Horus系统同样分为训练阶段与定位阶段。在训练阶段的数据采集过程中, Horus在目标区域中的采样密度为每1.5m设置一个采样点, 采集该位置的无线信号指纹。Horus利用概率性的方法来建模特定位置上每一个AP的信号强度特征, 包括参数化的分布模型, 如高斯分布以及非参数化分布。在服务阶段, 假设有m个AP, 用户在其位置上采集到来自每一个AP的信号强度, 形成一条m维向量s=(s1, s2, …, sm), 则定位问题转化为:给定信号指纹s=(s1, s2, …, sm), 查找位置x∈X使得概率P(x|s)最大, 其中X为二维的目标位置空间。根据Bayes理论, arg maxx[P(x|s)]=arg maxx[P(s|x)]。其中, 假设不同AP的信号强度彼此独立, P(s|x)可以计算如下:
利用无处不在的WiFi信号进行室内定位是定位技术上的一项重大的突破, 尽管RADAR与Horus系统提出了室内定位技术的核心方法与技术, 但这两种传统的技术也面临着极大的挑战, 包括:指纹的空间歧义性、指纹的时间不稳定性以及硬件多样性[13]。之后不断发展与完善的指纹定位新方法可以说都是在从不同的角度来解决这些问题。
2.1 指纹空间歧义性由于室内环境的复杂性以及多径效应, 两个距离比较远的位置处的WiFi信号RSS指纹可能会十分相似, 导致定位算法会出现指纹的错误匹配从而产生较大的误差。如图 2所示, 将数据库之中(6, 2)位置的指纹与数据库之中的每一个位置的指纹计算欧拉距离, 图中颜色越红代表距离越小, 可以看出(6, 2)与(2, 3)这两个点虽然空间距离比较远, 但是他们的指纹却长得十分相似, 这也就是指纹的空间歧义性。指纹的空间歧义性是最影响指纹定位效果的原因之一, 在实际场景之中, 定位系统即使出现了一些小的误差也不会影响用户的体验, 比如在一个商场之中, 一个店面的宽度可能就为3m左右, 这时如果我们的定位系统仅存在1m左右的误差并不会影响用户的使用, 但指纹的空间歧义性却会使距离很远的两个点错误地匹配上, 可能某个位置会达到8m以上的误差, 这会严重影响用户的体验。在近几年的WiFi定位系统的研究工作中, 提升WiFi定位精度的重要工作就是努力解决指纹的空间歧义性。
|
图 2 空间歧义性示意图 Fig. 2 Fingerprint spatial ambiguty |
在实际环境之中, 在同一个位置收集到的同一个AP的信号强度是会不断变化的, 这主要出于两个原因:第一个原因是在信号传播的过程中可能存在着一个正态分布的误差干扰, 如图 3所示, 在同一个位置连续采集相同AP的RSS值本身就很类似正态分布; 第二个原因是由于室内无线环境不同, 一些商业AP在不同信道状态不同的情况下会自动调整信道增益, 这为保证通讯质量做出了贡献，但是却给定位带来极大的不便利性。
|
图 3 RSS波动性示意图 Fig. 3 RSS bias over time |
图 4与图 5清楚地展示了指纹时间不稳定性, 图 4是数据库所有位置的指纹互相计算指纹的欧式距离的距离矩阵, 很显然, 越靠近对角线的两个指纹越相似。过了一段时间我们再次收集所有位置的指纹并与数据库之中各点原先的指纹计算指纹距离, 结果如图 5所示, 可以看出图 4和图 5已经完全不相同, 相似指纹出现的位置已经毫无规律可言, 这充分体现了指纹的时间波动性。在实际系统的应用过程之中, 由于指纹时间波动性的存在, 线下阶段采集的指纹数据库一段时间之后就会失效, 这会导致指纹定位的错误匹配, 同时, 为了重新获得有效的指纹数据库，又需要消耗大量的人力, 这些都限制了指纹定位系统的实用性。
|
图 4 指纹相似度矩阵 Fig. 4 The matrix for fingerprint similarity |
|
图 5 新指纹与老指纹相似度矩阵 Fig. 5 The similarity matrix for new and origin fingerprints |
除了指纹的时间不稳定性以及空间歧义性之外, 硬件上的多样性也是限制指纹定位系统没能够广泛应用的一个重要原因。硬件多样性是指即使在相同的位置、时间、环境甚至相同的采集方式的前提下, 不同硬件采集到的相同AP的RSS值都会存在一定的差异, 这是由于不同的硬件在天线等设计上的差异造成的必然结果。如图 6所示，选取了两个Nexus 6p，一个Nexus 7进行实验, 计算出的两组相同位置RSS测量值偏差的CDF图, 可以看出即使是相同型号的手机也会出现测量值的偏差, 不同型号的手机偏差值会更加显著。在实际的情况中, 这给我们构造的指纹数据库的普适性带来了很大的挑战。
|
图 6 硬件多样性示意图 Fig. 6 RSS bias over different devices |
以上介绍的指纹空间歧义性、时间波动性以及硬件多样性是目前指纹定位系统没能广泛运用于实际生活之中的瓶颈所在, 掌握了这些问题, 我们可以更全面地认识近几年提出的先进的指纹定位系统的创新之处。
3 发展中的指纹定位为了解决上文提到的指纹定位系统的3种挑战, 众多的定位系统都从各自的角度来进行优化与创新, 这些角度可以分为3个方面:更鲁棒的匹配算法、更鲁棒的指纹、更普适的指纹。接下来将从这3个分类来介绍一些目前已有的最先进的算法。
3.1 更鲁棒的匹配算法当我们在未知位置采集到了一条指纹之后，需要遍历指纹数据库之中的每一条指纹, 将他们依次与未知位置的指纹进行匹配, 最后将指纹距离最小的指纹对应的位置作为定位结果。在这个过程之中，可以看出计算两条指纹相似的匹配算法是一个非常重要的环节, 传统的定位系统(如RADAR)之中通常使用两个向量之间的欧式距离对其进行匹配, 但由于指纹的波动性，通常简单地计算欧式距离会存在较大的定位偏差; 改进策略的Horus将信号强度的波动抽象成为一个正态分布的概率模型, 从而将出现该条指纹概率最大的位置作为定位结果, 但由于正态分布只是理论上的结果, 在实际之中也会有很大的偏差。在本节中, 我们介绍两种室内定位算法, 了解它们在鲁棒性匹配的创新之处。
3.1.1 分布匹配:KL-散度KL-散度(KL-Divergence)[14]核心出发点与Horus类似, 都是利用概率的办法找出一个出现该条指纹概率最大的位置, 但与Horus不同, KL-散度没有将AP的RSS分布抽象成为一个正态分布, 而是计算未知位置的RSS分布与采样RSS分布之间的KL-散度。KL-散度是一个统计学上常用的比较两个分布相似程度的标准, 具体来说, 如果两个概率分布的密度函数为p与q, 在密度函数离散的情况下定义式(3)，
| $ {\rm{KL}}\left( {p\left\| q \right.} \right) = \sum\limits_s {p\left( {S = s} \right)\log \left( {\frac{{p\left( {S = s} \right)}}{{q\left( {S = s} \right)}}} \right)} 。$ | (3) |
在数学意义上KL(p‖q)可以理解为如果我们用q来代替p所带来的信息损耗。p与q的KL-散度D进而被定义为
| $ D\left( {p,q} \right) = {\rm{KL}}\left( {p\left\| q \right.} \right) + {\rm{KL}}\left( {q\left\| p \right.} \right)。$ | (4) |
下面将KL-散度运用到我们的指纹定位系统之中。定义S={S1, S2，…, SJ}为某一位置采集到的所有APi(i=1, 2, …, J)下的RSS采样集合。当我们在未知位置(x, y)采集到的所有AP下的RSS分布为p=p(S|{x, y}), 遍历指纹数据库之中的每一个点, 得到的数据库准确位置(xl, yl)，所有AP下的RSS分布为q=q(S|{xl, yl})，将KL-散度作为两组分布之间的匹配标准, 具体定义为
| $ D\left( {p,{q_l}} \right) = \sum\limits_{j = 1}^J {D\left( {p\left( {{S_j}\left| {\left\{ {x,y} \right\}} \right.} \right),q\left( {{S_j}\left| {\left\{ {{x_l},{y_l}} \right\}} \right.} \right)} \right)} 。$ | (5) |
相比于Horus, KL-散度没有将信号强度的分布抽象成为一个具体的概率模型, 而是通过单纯地匹配两个分布从而增强了匹配的鲁棒性。KL-散度系统相比于Hours效果提升了30%以上。
3.1.2 考虑AP权重DorFin相比于Horus与KL-散度将AP的分布抽象为一个概率模型, DorFin[15]直接通过两条指纹之间的鲁棒匹配来增强系统的准确性。具体来说，在实际环境中，信号强度随距离变化的理想数学模型可以被刻画为对数距离路径损失模型(Log-distance path loss model, LDPL)，
| $ {P_r}\left( d \right) = {P_0}\left( {{d_0}} \right) - 10\eta \lg \left( {\frac{d}{{{d_0}}}} \right) + {\mathit{\boldsymbol{X}}_\sigma }。$ | (6) |
其中, P0(d0)表示接收者在距离信号源为d0处接收到的信号强度, η代表路径损耗参数(通常在实际情况之中的取值范围为2~4), Xσ是服从对数正态分布的随机变量, 用来表征信号的反射、散射与遮蔽现象对接收者接收到的信号强度造成的影响。从式(6)可以推导出
| $ \rho _i^u = \left\{ \begin{array}{l} {10^{\frac{{{f_{u,i}} - {P_{{d_0}}}}}{{10\eta }}}},{\rm{if}}\;{f_{u,i}} \le {f_0}\\ \frac{1}{\alpha }\left( {1 + {{\rm{e}}^{ - 2\left( {\frac{{{f_{u,i}} + 100}}{{10}} - c} \right.}}} \right),\;\;{\rm{otherwise}} \end{array} \right. $ | (7) |
其中, f0是一个固定的RSS强度(在DorFin的实验中取值为-55dB), η是LDPL公式中的路径损耗参数, α与c是根据η来确定的常数。通过式(7)可以看出, 当接收到某个AP的信号强度比较强的时候, 我们通过LDPL模型估算距离计算出一个比较大的权重; 当信号强度比较弱的时候, 我们通过模型来赋予一个比较小的权重, 这样使得指纹的匹配更加鲁棒。
3.2 更鲁棒的指纹除了更加鲁棒的指纹匹配算法之外, 目前在室内定位系统上创新最多的地方是寻找更加鲁棒的指纹, 正如前文所说, 在定位的过程中，最直观能用的信息就是AP的RSS强度, 但计算RSS的理论公式并不一定是完全准确的, 所以直接使用RSS作为指纹可能会在本质上造成难以避免的误差。更鲁棒的指纹将相邻位置RSS之间的梯度关系或者连续采样得到的RSS之间的变化趋势作为更鲁棒的结构进行匹配, 从而取得了更好的定位结果。在本节中, 我们将介绍几种经典的鲁棒性指纹定位系统。
3.2.1 WiFi“地标”:Walkie-MarkieWalkie-Markie[16]是一个典型的利用用户在行走的过程中连续测量的WiFi信号进行定位的系统, 之后基于连续测量的室内定位方法都或多或少受Walkie-Markie的影响。Walkie-Markie系统不使用RSS的绝对读数, 而是使用用户在行走过程中RSS的变化趋势。如图 7所示, 虽然我们并不知道RSS衰减的准确公式, 但是可以肯定的是，距离越远, 接收到的RSS越小, 所以当用户从靠近到远离AP的时候, 接收到的RSS强度会先增大后减小。反过来, 如果RSS的变化出现这个趋势, 那么可以认为在这周围出现了一个WiFi“地标”, 如果我们用三元组来记录这个WiFi地标, 可以表示为WM={BSSID, (D1, D2), N}, 其中BSSID是该AP的MAC层地址, 用来区分空间之中的AP, D1与D2代表靠近地标和远离地标的方向, 该方向可以通过采集的地磁数据得出, N代表该位置收集到的其他AP, 这是为了区分开两条平行的轨迹。在线下阶段, 通过用户不断行走过程中采集到的连续RSS构造空间的Wifi地标-RSS变化趋势数据库; 在线上阶段, 通过比较用户在运动过程中采集到的所有AP的RSS变化趋势在数据库中找到相应的地标位置从而进行定位。由于Walkie-Markie在整个过程中没有用到RSS的绝对读数，而只是使用了用户在行走过程之中的RSS变化趋势, 使得系统的鲁棒性取得了大幅度的提升。
|
图 7 WiFi地标示意图 Fig. 7 Illustration of using WiFi landmarks |
GIFT[17]是基于Walkie-Markie方法的改进与变式, GIFT更加细粒度的刻画了在行走过程之中的RSS变化趋势，而不是像Walkie-Markie使用简单的RSS先增大后减小的这种变化趋势。如图 8所示, 具体来说, 当用户采集到了一条轨迹上的指纹之后, GIFT根据采集到的两个相邻位置的RSS值大小关系将RSS绝对读数离散化处理, 从而对于这条轨迹上连续采集的同一个AP的RSS绝对读数就变成了一个仅由0, 1, 2组成的序列, 由于没有用到RSS的绝对数值进行匹配，而是提取了在行走的过程不同位置采集到的RSS关系这一更加稳定的结构, 所以GIFT系统的鲁棒性得到了进一步的提升。在GIFT的线下阶段中，采集所有空间位置的指纹, 利用正态整体参数随机性检验的方法将RSS的读数离散化处理生成Gmap; 在线上阶段中, 离散化用户连续行走获得的RSS连续读数形成一条离散序列, 将离散序列在Gmap中进行匹配从而对用户进行定位。值得一提的是, 这种利用正态整体分布随机性检验的方法离散化RSS的绝对读数在之后的定位系统之中也有广泛的应用, 如果当前位置为li, 它的临近位置为lj, 在采样的过程之中会对每一个位置连续采集多条指纹, 取所有采样指纹的平均值作为当前位置的指纹。假设两个位置接收到的第k个AP的RSS读数采样为{fik1, fik2, …, fikn}与{fjk1, fjk2, …, fjkn}(n为采样个数, 一般多于50), 利用所有的采样, GIFT可以计算所有采样的均值与方差分别为(μik, σik)与(μjk, σjk)。当得到了均值与方差之后就可以进行参数随机性检验了, 在这里, GIFT的原假设H0与备择假设H1分别为
| $ \left\{ \begin{array}{l} {H_0}:{\mu _{ik}} = {\mu _{ik}},\\ {H_1}:{\mu _{ik}} \ne {\mu _{ik}}。\end{array} \right. $ | (8) |
|
图 8 GIFT示意图 Fig. 8 Illustration of GIFT |
由于实际采样次数(>50次)已经不算是一个小样本, 所以这里GIFT采用t-统计检测方法，这里的t值可以为
| $ {t^k} = \frac{{{\mu _{ik}} - {\mu _{jk}}}}{{\sqrt {\frac{{\sigma _{ik}^2}}{n} + \frac{{\sigma _{jk}^2}}{n}} }}。$ | (9) |
通过查找t-分布表可以查到tk对应的概率, 如果这个概率大于置信区间1-α, 那么就有理由拒绝原假设H0而接受备择假设H1, 也就是代表着实际结果显示μik≠μjk, 反之亦然, 需要说明的是在这里置信区间0.85≤1-α≤0.95, 在实际运用之中GIFT取1-α=0.92。
3.2.3 考虑指纹空间关系:ViVi为了解决时间不稳定性以及硬件多样性, ViVi[13]基于传统的RSS指纹充分挖掘指纹相似度中的空间关系限制，并提出了指纹空间梯度(Fingerprint spatial gradient, FSG)这一种新的匹配结构。ViVi的核心出发点是尽管单个地点接收到的某个AP的RSS值会发生变化, 但是他与相邻位置接收到的相同AP的RSS值之差会保持相对的稳定。具体来说, 如果位置li与位置lj相邻, 在t1时刻两个位置收集到的APk(1≤k≤m)的RSS值分别为fik1与fjk1, 在t2时刻收集到的APk的RSS值为fik2与fjk2, 尽管在同一位置不同时间收集到的信号强度之差|fik1-fik2|会发生不小的变化, 但是相邻位置在不同时刻收集到的RSS之差会保持相对的稳定, 即|fik1-fjk1 |≈|fik2-fjk2 |, 这是因为即使AP信号的强度会发生改变, 但这个改变带来的影响在十分接近的两个位置上会比较小, 这样ViVi就找到了在变化的过程之中一个稳定的量, 利用其进行鲁棒性的匹配。
如图 9所示, 对于每一个位置的指纹来说, ViVi结合周围临近位置的指纹构造一条FSG曲线, FSG曲线刻画了当前的指纹和一些周围位置指纹之间的相似度变化趋势, 位置li位置的FSG曲线gi为
| $ {g_i} = \left\{ {\left\langle {d\left( {{l_i},{l_j}} \right),\varphi \left( {{f_i},{f_j}} \right)} \right\rangle ,i - r \le j \le i + r} \right\}。$ | (10) |
|
图 9 FSG曲线示意图 Fig. 9 Illustration of FSG profile |
其中, φ(fi, fj)是位置li的指纹fi与位置lj的指纹fj之间的指纹相似度, 通常刻画为欧氏距离; d(li, lj)是位置li与位置lj之间的物理距离, 位置li-1到位置li-r和位置li+1到位置li+r是围绕在当前位置li两侧的周围位置子集。在匹配时，有两条FSG曲线gQ={〈dQ, φQ〉}与gC={〈dC, φC〉}, 由于在构造FSG曲线的时候都选取了2r+1个点并且排列方式相同, 所以匹配gQ与gC实际上就是在匹配φQ与φC, 在ViVi之中使用了效果不错的余弦相似度来对相似度进行刻画，
| $ \mathit{\Gamma }\left( {{g_Q},{g_C}} \right) = \frac{{{\varphi _Q} \cdot {\varphi _C}}}{{\left\| {{\varphi _Q}} \right\| \cdot \left\| {{\varphi _C}} \right\|}}。$ | (11) |
除了提出了FSG这种鲁棒性的匹配结构, ViVi在其基础上还设计了精妙的选取周围点的办法以及FSG匹配算法, 相比于目前已有的定位系统的精度提升了20%以上。
3.3 更普适的指纹以上的一些方法都是从指纹本身的基础之上提取出更稳定的结构，并构造更加鲁棒的匹配算法, 取得了不错的效果。同时, 伴随着高速发展的智能手机产业, 智能手机上通常配备多种传感器(磁力计、陀螺仪、加速度计、扬声器、麦克风等), 这些传感器为手机的智能化奠定了基础，同时也为我们的定位技术提供了一种新的思路:利用传感器采集到的信号来纠正WiFi指纹定位的误差，实现更加细粒度的定位。本小节通过介绍几种融合额外传感器数据的定位方法来了解这种室内定位领域发展的新趋势。
3.3.1 WiFi+地磁由于在空间之中无处不在并且比WiFi有更强的抗动态性，使得地磁信号逐步走入了室内定位领域[8, 18-19]。如图 10所示, 可以发现在定位效果上, WiFi在大范围上的区分效果比较好, 不同的屋子或者相距很远的两个位置的指纹会很不相似; 而地磁信号在细粒度上的区分效果更加良好, 即使两个位置比较接近, 但是采集到的地磁信号强度也会有一定的差异, 所以，基于以上的观察，结合WiFi与地磁进行定位能够融合两种信号之间的优势, 是一种理想的定位方法。
|
图 10 不同信号定位效果示意图 Fig. 10 Illustration of localization results of different signals |
结合WiFi与地磁信号的核心方法是:用户在行走一条轨迹的过程之中会采集到了一系列指纹与地磁信号强度序列, 一方面可以根据Wi-Fi指纹定位算法算出用户行走的轨迹, 另一方面, 可以通过动态时间规整(Dynamic time wrapping, DTW)算法，通过地磁信号强度序列匹配出数据库中相似度最高的一段轨迹, 这样就通过不同的定位方法算出了两种轨迹, 通过Wi-Fi计算出的轨迹全局性高, 能大体知道用户在空间中的位置; 用地磁信号算出的轨迹形状精确, 能够知道用户行走的方向与距离, 因此, 将两种结果结合就实现了对用户的轨迹追踪。当然, 地磁信号强度序列计算出的轨迹也能纠正WiFi指纹定位存在的空间歧义问题。
3.3.2 WiFi+惯导利用惯性测量单元(Inertial measurement unit, IMU)协助WiFi进行室内定位或者轨迹追踪的思路与WiFi+地磁类似[11, 20], 都是利用WiFi算出一个大体的位置, 再由IMU数据解算出用户行走的一个精确的轨迹, 结合二者从而实现高精度的室内定位或追踪。
图 11展示了利用IMU协助定位的一般示意图, 加速度计会不断检测用户是否发生了运动, 如果检测到用户行走, 利用对陀螺仪数据的积分可以算出用户行走的方向与距离, 利用这个精确的方向与距离结合WiFi定位的结果就可以实现对用户精确的定位。至于结合两种定位方法的算法, 目前用途最广泛的是卡尔曼滤波器(Kalman-Filter, KF)与粒子滤波器(Particle-Filter, PF)。卡尔曼滤波器的工作方式是对IMU算出的用户下一时刻位置与用WiFi估算出的位置进行加权平均; 粒子滤波器工作流程如图 12所示, 在用户的当前位置周围随机撒下很多粒子, 所有的粒子按照IMU数据计算出的轨迹信息进行相同的转移, 在根据与采集到的WiFi指纹进行相似度匹配，给每一个粒子计算一个权重, 之后取权重最高的前10%的粒子的加权平均作为用户下一时刻的位置。
|
图 11 IMU协助定位示意图 Fig. 11 Illustration of IMU-assisted system |
|
图 12 粒子滤波器流程示意图 Fig. 12 Illustration of Particle-Filter |
区别于上述的WiFi+传感器需要引入一条轨迹的方式, WiFi+声音[7, 21]采用了多用户协同定位的方法。如图 13所示, 当多个用户进行协同定位时, 利用声音信号测量两两用户之间距离, 利用用户之间的这个准确的位置多边形对WiFi指纹定位的结果进行限制, 有效减轻指纹定位的空间歧义性与时间不稳定性。在通过声音测距的过程之中, 为了不影响用户的体验，通常是麦克风发送一段超声波, 利用Beep算法进行测距。
|
图 13 WiFi+声音多用户协同定位示意图 Fig. 13 Illustration of indoor peer-assisted localization |
WiFi+图像与WiFi+声音的定位方法核心思想类似, WiFi+图像[22]的定位算法利用多个图像计算出用户的实际位置空间多边形来限制指纹定位的结果, 从而实现高精度的室内定位。如图 14所示, 用户在4个位置分别拍摄了一些图片并且采集到了所在位置的WiFi指纹, 利用SfM算法在图像数据库之中匹配拍摄的图片, 形成一个图像定位四边形, 这个四边形相对而言比较精确。再在指纹数据库之中匹配指纹, 得到一个WiFi定位多边形, 这个多边形只能知道用户大体上的空间位置。最后, 结合这两个多边形就能够对用户实现高精度的室内定位。相比于基于声音测距的方法, 计算机视觉领域上的图片匹配算法更加精准, 同时利用图像的方法还不需要多个用户进行协作, 提高了系统的易用性。除此之外, 从一张图片之中可以发掘出大量的语义信息, 这些语义信息也会为我们提供进一步的服务。
|
图 14 WiFi+图像协助定位示意图 Fig. 14 Illustration of computer vision-based localization |
从开山之作RADAR诞生开始的近20年之中, 基于WiFi指纹的室内定位技术层出不穷, 也伴随着技术的发展融入新的定位手段，从而给这个传统的领域带来了新的生机。本文所列出的一些定位系统只是这个领域中比较有代表性的很小的一部分。尽管定位手段多种多样, 但在实际中能有效运行的却并不是很多, 这主要有两部分原因:第一个重要的原因是我们无法准确刻画信号传播模型以及实际空间中的环境复杂性，导致“鲁棒”的匹配算法与“鲁棒”的指纹并没有那么“鲁棒”, 一些鲁棒性的前提假设在实际环境面前面临着挑战; 第二个重要的原因是基于WiFi指纹的定位方式都需要前期进行指纹数据库的构建以及指纹数据库的维护, 这导致指纹定位系统需要大量的人力开销, 在大规模场景下难以部署。基于以上指纹定位存在的问题，指纹定位技术未来的发展有以下几个方面。
4.1 更实用的室内定位技术指纹定位技术的实用性包括指纹的鲁棒性以及系统的可维护性。如何从传统的指纹基础之上提取出鲁棒的结构是重中之重, 比如RSS读数可能是不鲁棒的, 但距离AP越近RSS越大, 距离AP越远RSS越小，这个关系是鲁棒的, 如何发掘这些特征是实现鲁棒性的重要问题。而系统的可维护性主要体现在众包技术以及指纹数据库更新技术中, 减轻系统的人力开销也是需要解决的一个重要问题。
4.2 更智能的室内定位技术正如3.3.3节WiFi+图像中提到的, 从一张图片中可以发掘出大量的语义信息, 如何利用这些语义信息也会给定位系统带来智能化的突破, 在之后可能用户想知道的不仅仅是一个空间中的二维坐标, 而更想知道的是:我想去KFC应该怎么走?我应该怎么找到他/她?他/她和谁在一起做什么?所以在未来的发展中，WiFi+计算机视觉的技术会在定位领域有所发展与突破。
禅宗提到过悟道三境界:第一重是在悟道初期，“看山是山, 看水是水”; 第二重是小有所成，“看山不是山, 看水不是水”; 第三重是真正领悟大道, 返归“看山还是山, 看水还是水”的境界。其实室内定位发展的脚步也是这样的一个过程, 早期的室内定位系统用单纯的WiFi指纹进行定位, 虽小有所成但难以突破自身的局限性。在技术发展的过程中引入大量传感数据协同定位, 取得大量的突破，但由于对用户的使用与系统的维护进行过多的限制导致仍然没能实用, 但这一阶段的发展开阔了我们的研究思路, 使得我们对信息的使用提升了一个档次。到了如今, 发现返璞归真从单纯的WiFi信号之中提取出鲁棒性的结构才是能够帮助室内定位技术使用化的重要途径。“我是谁”、“我在哪”永远是人们追求的两大问题，希望室内定位技术能够帮助到更多的人——不要让空间上的迷失带来心灵上的迷失。
| [1] |
刘云浩. 从互联到新工业革命[M]. 北京: 清华大学出版社, 2016: 23-26.
|
| [2] |
杨铮, 吴陈沭, 刘云浩. 位置计算:无线网络定位与可定位性[M]. 北京: 清华大学出版社, 2014: 7-9, 28-29.
|
| [3] |
YOUSSEF M, AGRAWALA A. The Horus location determination system[J]. Wireless Networks, 2008, 14(3): 357-374. DOI:10.1007/s11276-006-0725-7 |
| [4] |
NI L M, LIU Y, LAU Y C, et al. LANDMARC:Indoor location sensing using active RFID[J]. Wireless Networks, 2004, 10(6): 701-710. DOI:10.1023/B:WINE.0000044029.06344.dd |
| [5] |
WANG J, KATABI D. Dude, where′s my card?: RFID positioning that works with multipath and non-line of sight[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 51-62. |
| [6] |
SHANGGUAN L, YANG Z, LIU A X, et al. STPP: Spatial-temporal phase profiling-based method for relative RFID tag localization[J]. IEEE/ACM Transactions on Networking (ToN), 2017, 25(1): 596-609. DOI:10.1109/TNET.2016.2590996 |
| [7] |
LIU K K, LIU X X, LI X L. Guoguo: Enabling fine-grained indoor localization via smartphone[C]//Proceeding of the 11th Annual International Conference on Mobile Systems, Applications, and Services. ACM, 2013: 235-248.
|
| [8] |
SHU Y, SHIN K G, HE T, et al. Last-mile navigation using smartphones[C]//Proceedings of the 21st Annual International Conference on Mobile Computing and Networking. ACM, 2015: 512-524.
|
| [9] |
YANG Z, WU C S, LIU Y H. Locating in fingerprint space: Wireless indoor localization with little human intervention[C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking. ACM, 2012: 269-280.
|
| [10] |
WU C S, YANG Z, LIU Y H. Smartphones based crowdsourcing for indoor localization[J]. IEEE Transactions on Mobile Computing, 2015, 14(2): 444-457. DOI:10.1109/TMC.2014.2320254 |
| [11] |
YANG Z, WU C S, ZHOU Z M, et al. Mobility increases localizability: A survey on wireless indoor localization using inertial sensors[J]. ACM Computing Surveys (Csur), 2015, 47(3): 54. |
| [12] |
BAHL P, PADMANABHAN V N. RADAR: An in-building RF-based user location and tracking system[C]//INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2000, 2: 775-784.
|
| [13] |
WU C S, XU J A, YANG Z, et al. Gain without pain: Accurate WiFi-based localization using fingerprint spatial gradient[J]. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 2017, 1(2): 29. |
| [14] |
MIROWSKI P, WHITING P, STECK H, et al. Probability kernel regression for WiFi localisation[J]. Journal of Location Based Services, 2012, 6(2): 81-100. DOI:10.1080/17489725.2012.694723 |
| [15] |
WU C S, YANG Z, ZHOU Z M, et al. Mitigating large errors in WiFi-based indoor localization for smartphones[J]. IEEE Transactions on Vehicular Technology, 2017, 66(7): 6246-6257. DOI:10.1109/TVT.2016.2630713 |
| [16] |
SHEN G B, CHEN Z, ZHANG P C, et al. Walkie-Markie: Indoor pathway mapping made easy[C]//Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation. USENIX Association, 2013: 85-98.
|
| [17] |
SHU Y C, HUANG Y H, ZHANG J Q, et al. Gradient-based fingerprinting for indoor localization and tracking[J]. IEEE Transactions on Industrial Electronics, 2016, 63(4): 2424-2433. DOI:10.1109/TIE.2015.2509917 |
| [18] |
SHU Y C, BO C, SHEN G B, et al. Magicol: Indoor localization using pervasive magnetic field and opportunistic WiFi sensing[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(7): 1443-1457. DOI:10.1109/JSAC.2015.2430274 |
| [19] |
XIAO Z L, WEN H K, MARKHAM A, et al. Lightweight map matching for indoor localisation using conditional random fields[C]//Proceedings of the 13th International Symposium on Information Processing in Sensor Networks. IEEE Press, 2014: 131-142.
|
| [20] |
MADGWICK S O H, HARRISON A J L, VAIDYANATHAN R. Estimation of IMU and MARG orientation using a gradient descent algorithm[C]//Rehabilitation Robotics (ICORR), 2011 IEEE International Conference on. IEEE, 2011: 1-7.
|
| [21] |
LIU H B, GAN Y, YANG J, et al. Push the limit of WiFi based localization for smartphones[C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking. ACM, 2012: 305-316.
|
| [22] |
XU H, YANG Z, ZHOU Z M, et al. Enhancing wifi-based localization with visual clues[C]//Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing. ACM, 2015: 963-974.
|