0 引言

近年来，随着移动互联网络的发展，智能终端的普及，公共场所无线局域网络热点的大规模部署，位置服务和位置感知计算等移动互联网增值业务受到关注，与基于射频识别或传感器网络的定位方法^[1-2]相比，基于Wi-Fi网络的定位技术以其网络接入便利、设备成本低的特点受到重视^[3]。该定位技术利用终端设备接收到的部署在Wi-Fi网络环境中的无线接入点(Access Point, AP)的信号强度，就可以对移动终端进行定位^[4-5]。

基于接收信号强度的定位方法可以分成基于测距的几何定位法、基于基站的近似定位法^[6-7]和基于指纹特征的场景分析法^[8-9]等。在室内环境中，由于建筑物布局、多径、墙面反射吸收、温湿度变化、人员出入等复杂因素对Wi-Fi信号传播衰减造成的影响，导致信号强度衰减量与收发设备之间距离并不满足路径损耗渐变模型^[10]，因此使用基于测距的三边或三角定位算法^[11-12]难以获得较理想的定位效果。基于AP的近似定位法^[6-7]主要利用设备的关联关系进行位置估计，但其定位精度较低，无法满足较高定位精度需求。基于指纹特征的场景分析技术则利用复杂环境引起的Wi-Fi信号的特异性来构建指纹信息。由于Wi-Fi信号的特异性与地形和传播时的障碍物具有依赖性，呈现出针对环境的特殊特征，能获得比其他定位方法更好的定位结果。

室内Wi-Fi网络的信号强度除了不满足路径损耗渐变模型之外，Wi-Fi信号本身还具有较大的时变性和随机性^[13-14]，信号接收终端在同一地点观测到的实时信号值也无法保证与该点的指纹样本所匹配^[15]，由此引起测试点的定位结果跳动从而影响总体定位效果。针对该问题一般的解决方式大多是在得出定位结果后再对其进行修正，如采用基于高斯滤波方法^[16]、卡尔曼滤波方法^[17]、粒子滤波方法^[18]等各种滤波方法，通过对定位结果进行滤波达到对定位的修正，然而该种方式只适用于连续定位过程修正，针对离散点修正效果不明显，且无法做到在定位过程中避免信号时变性引起的定位跳动。

考虑到在定位过程中避免定位跳动，本文提出了基于动态时间规整距离指纹匹配的Wi-Fi网络室内定位算法，它将采集到Wi-Fi网络的接收信号强度(Received Signal Strength, RSS)结合采样区域的路径特征转化为时间序列指纹，利用反映到序列指纹上的路径特征避免由于个别采样信号的时变性或人为干扰导致的定位跳动问题，并通过计算动态时间规整距离相似性解决由于变速运动造成的时间序列匹配不同步问题，进而在定位过程中抑制了结果跳变，提高了总体定位效果。

1 路径特征的时间序列指纹

基于指纹匹配的定位算法一般可以划分为指纹样本的采集处理和指纹数据的匹配定位两个步骤。在指纹采集处理过程中，通过Wi-Fi信号采集终端采集定位环境中AP的信号强度并记录采集点坐标位置，在指纹匹配定位阶段定位终端同样采集环境中的AP信号强度信息并与采集阶段的样本信息匹配，获得最相似的位置作为定位结果。然而，通常基于指纹匹配的定位算法采集的指纹数据只使用当前地点的AP信号强度，在定位过程中无法避免由于AP信号强度的时变性或人为干扰导致的定位结果的跳动。相比而言，本文采用路径特征的序列指纹可以充分结合采样路径的历史特征信息，对AP信号的抖动以及人为干扰有较强的抵抗能力。

时间序列是指按照时间先后顺序排列的各个观测记录的有序集合，广泛存在于商业、经济、科学工程和社会科学等领域。本文基于时间序列的指纹模型采样方式依照线路进行建模，在定位环境中规划出l条线路，而后沿着每条路径以大致匀速行走若干次，并沿途相隔均等时间记下当前时刻t的所采集到的M个AP的信号强度信息R_t={r₁^(t), r₂^(t), …, r_M^(t)}和所在点D维度坐标位置信息X_t={x₁^(t), x₂^(t), …x_D^(t)}建立t时刻基于时间序列模型的指纹s_t=(R_t, X_t)，而后针对采样线路i上各时刻点按照时间先后顺序建立基于时间序列方式线路样本p_i={s₁, s₂, …, s_n}，最后将各条采样线路样本合并成时间序列指纹样本库P={p₁, p₂, …, p_l}作为用于指纹匹配的样本数据库。对于请求定位指纹数据采用基于时间序列的指纹数据模型与上述构建的序列指纹样本库相适应，首先设置匹配的数据个数K，建立t(t≥K)时刻的信号强度匹配指纹数据Q_t={R_t-K+1, R_t-K+2, …, R_t}。因此用于进行指纹匹配的每条指纹记录包括M个AP在匹配个数K(图 1中K=3) 的全部指纹数据。与传统指纹匹配模型(如图 1中T₃)相比每条记录的指纹信息量相当于其K倍，且能够较好地反映信号强度随时间序列位置变化的规律。

鉴于本文所设计的数据采样模型主要应用于典型的公共场所定位环境，例如：商场、超市、楼宇等，本文对上述典型定位场景存在的区域路径采样方式进行规划，采样区域可分解为以下三类基本的动态路径采样方式：

1) 如图 2(a)所示，为两侧开放路径，路径数据采集方式为沿着①、② 两个方向各采集一次数据，而后将采集到的数据分别按照①② 和②① 的先后顺序相接，作为两条线路数据。

2) 如图 2(b)所示，为单侧开放路径，其路径数据采集方式同两侧开放路径采集方式，按照②① 的先后顺序相连作为一条线路。

3) 如图 2(c)所示，为开放区域，可考虑在不影响定位精度的情况下选取其中若干条路径作为数据采集路径，而后可以按照①②…⑥ 和⑥⑤…① 的顺序连接，作为两条线路。

利用上述基本的动态路径采样方式可以对区域路径进行规划，针对区域结构特征主要考虑以下两种情形：

1) 规则路径区域，可以按照路径划分成若干条纵向和横向路径；而后按照图 2(a)、(b)所示的两侧开放路径和单侧开放路径的基本路径采样方式进行采样生成采样数据。

2) 不规则路径区域，主要是针对一些弯曲的、闭合的、分叉的不规则的路径，首先将其转化为规则的若干条规则路径，而后按照1) 的规则路径区域方式进行处理。

针对其他类型的区域都可以划归到上述两种情形中的一种或几种进行处理。

2 基于动态时间规整的指纹数据匹配算法

动态时间规整(Dynamic Time Warping, DTW)算法是一种常用的度量时间序列相似性的方法^[19]，用于解决时间序列长度不一致的模板匹配问题，算法应用动态规划的思想，通过对时间序列数据进行逐次计算最终获得与模板数据的相似度。因其算法简单、无需进行复杂的数据训练过程，被广泛地应用于语音识别、手势识别、脱氧核糖核酸(DeoxyriboNucleic Acid, DNA)匹配等领域^[20-22]。

本文的指纹数据模型是基于时间序列的线路数据模型，在实际应用中人的行走速度是不确定的，故记录的时间序列指纹数据无法按照传统指纹匹配中的欧氏距离一一对应进行匹配，存在图 3所示的匹配不一致现象。鉴于此，本文设计了基于动态时间规整的线路指纹匹配算法，不同于传统的欧氏距离匹配，该算法可以将时间序列的线路数据进行弯折而后再进行对应，以此解决速度不确定导致的时间序列指纹数据无法对应的问题。

本文的匹配算法包括线路内匹配和线路间匹配两个步骤。在线路内匹配过程中，针对每条线路计算请求定位指纹数据Q_t与该线路的时间序列数据样本S的DTW距离，其中对于∀R∈Q_t，∃R′∈S，使得R与R′相似，即是Q_t中元素在样本S中都有与之对应的元素，同时对请求定位序列Q_t和样本序列S之间放宽起点和终点对齐限制，以使得Q_t可以遍历整条线路的样本S，设计DTW采用的连续性条件如图 4所示。

阶段最优判别式为：

$\min \left\{ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{g}}(i - 1,j)} & {\rm{①}}\\ {\mathit{\boldsymbol{g}}(i - 1,j - 1) + \mathit{\boldsymbol{d}}(i,j)} & {\rm{②}}\\ {\mathit{\boldsymbol{g}}(i,j - 1) + \mathit{\boldsymbol{d}}(i,j)} & {\rm{③}} \end{array}} \right.$

(1)

其中:g(i, j)为到请求序列Q_t中第i个元素与样本S第j个元素阶段所匹配DTW距离; d(i, j)为请求序列Q_t中第i个元素与样本S第j个元素之间的相似性距离; 本文选取指纹信号之间的欧氏距离作为元素之间距离度量。而后选择其中的DTW距离最小的样本记录s_j参与线路间匹配。式(1) 中:式① 相当于S中当前元素与上个元素对应Q_t中同一个元素，因为Q_t中对应元素未变，因此未增加d(i, j); 而式② 中相当于S中元素和Q_t中元素在窗口中均增加一个，因此增加d(i, j)，同时，式② 为时间序列对应完全一致条件下的匹配计算式; 式③ 为Q_t中元素在窗口中加1而S中元素未变的情况。本文动态时间规整算法即是通过式①、③ 对时间序列对应的调整来弥补式② 在时间序列对应不一致时的计算误差。

本文基于动态时间规整的线路内匹配算法如下：

输入 请求定位序列Q_t，样本序列S;

输出 DTW距离和对应样本序列的位置组X。

1) 分别计算序列Q_t和S中元素的个数n和m;

2)  构造Q_t与S之间欧氏距离矩阵d(i, j)_n×m;

3)  构造Q_t与S之间的DTW距离矩阵D_n×m;

4)  赋值D的第1列D(:, 1) =d(:, 1);

5)  计算D的第1行D(1, j)=D(1, j-1) +d(1, j);

6)  for i=2:n

7) for j=2:m

8)  D(i, j)=$\min \left\{ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{D}}(i - 1,j)}\\ {\mathit{\boldsymbol{D}}(i - 1,j - 1) + \mathit{\boldsymbol{d}}(i,j)}\\ {\mathit{\boldsymbol{D}}(i,j - 1) + \mathit{\boldsymbol{d}}(i,j)} \end{array}} \right.;$

9)   end;

10)  end;

11)  DTW距离=min(D(:, m));

12)  X=X_{find(DTW距离==D(:, m))}

本文的线路内匹配算法由于利用动态时间规整距离进行相似性匹配，可自行计算获得样本序列与请求序列的匹配关系，而无需请求序列的起止点与线路数据的起止点一一对应，因此可以获得各条线路内与请求序列Q_t最相似的样本子序列位置组X(Q_t中等于DTW距离的一组X按线路采样时间顺序排列)，而后进行线路间匹配，以获得最终匹配定位结果，算法如下：

输入 每条线路的DTW距离和对应样本序列位置组X以及选取样本个数K和对应的一组权重W={w₁, w₂, …, w_K}；

输出 匹配定位位置X_final。

1)  按照DTW距离由小到大排序对应位置组X，组成位置组序列{X₁, X₂, …, X_l};

2) 选择位置组序列{X₁, X₂, …, X_l}中前K个位置;

3)  计算其平均加权位置: X_aver=$\sum\limits_{i = 1}^K {\left\{ {{w_i}{\mathit{\boldsymbol{X}}_i}} \right\}} $;

4)  匹配定位位置X_final=X_aver

通过线路内匹配和线路间匹配获取最终的定位位置X_final作为最终的定位结果。

对本文定位算法的线路内匹配和线路间匹配进行分析，线路内匹配的计算复杂度为O(n×m)，而线路间匹配的计算复杂度为O(l²)，均可在平方时间复杂度内完成计算，可以满足实际定位时间需求；而在线路内匹配计算过程中所需最大的空间开销为距离矩阵D_n×m，线路间匹配计算过程中, 所需最大的空间开销为位置组序列{X₁, X₂, …, X_l}，也均可以满足实际定位的空间需求。

3 实验结果与分析

本文的定位算法主要是基于时间序列数据模型进行指纹匹配，算法的定位效果会受到时间序列窗口的大小、采样的速度以及采样的路径所影响，鉴于上述分析，本文实验部分主要包括窗口大小的选取、变速运动定位测试和开放区域定位实验。

3.1 窗口大小的影响

本实验测试环境如图 5所示，实验环境面积大小为25 m×15 m，其中的四处“*”为无线AP所在位置，矩形为环境中不可抵达点(如：办公桌、机柜、墙体等)，在实验环境中以大致匀速沿虚线所示路径按照规则路径区域采样方式进行采样，采样的时间间隔是0.5 s，包括纵向7条采样线路和横向1条采样线路，并将采样数据分别分为采样样本和测试数据两部分。

通过对DTW相似性匹配算法的分析，由于定位过程中每次匹配的数据特征为一个滑动窗口中的内容，故滑动窗口的大小将影响定位的效果，同时随着滑动窗口增大，定位所需时间增加，本文此处对比滑动窗口大小与定位误差的变化，累积错误率为误差范围内的定位测试数据量占总定位测试数据量的比例, 得到窗口大小与定位结果如图 6所示。

图 6中，本文分别对同一组测试数据按照1~5个大小的窗口应用本文的算法进行定位测试，并分别统计其1~10 m的定位误差。由图 6可以看出，随着窗口增加，定位误差减小，当窗口大小为5时，误差范围3 m的定位达到72%，误差范围5 m的定位达到91%。因此，该实验验证了将指纹数据按照时间序列方式转化为滑动窗口模型，增加了指纹匹配的信息量，提高了指纹匹配定位的精度，但窗口的设置在考虑定位精度的同时也要兼顾定位的时间，即是当窗口增大时首次定位时间会由于需要足够的窗口数据而延长，且当切换线路时会由于窗口数据的存在而导致定位延迟，因此，折中选择窗口的大小为3~6既可以提高总体定位精度又不会在感觉上造成较大的影响。

3.2 变速运动定位效果

本文的数据模型是基于时间序列的，因此，采样时间间隔的变化对指纹匹配的结果会有影响，反映在采样线路就是运动速度的变化，鉴于此本实验针对图 5的测试环境，分别进行变速、匀速指纹采集，而后将变速、匀速的测试数据代入匀速建立的指纹样本库进行测试，用以比较传统的指纹匹配算法和本文的基于时间序列模型的指纹算法的定位效果。如图 7所示，本文选择的窗口大小为5，从图中可以看到基于动态时间规整的指纹匹配定位算法因为能够较好地吻合时间序列特征获得线路的相似数据，匀速运动误差范围在3 m以内的定位达到72%，较传统的欧氏距离瞬时指纹匹配的定位方法的累积错误率提高了10%，本文算法的平均定位误差为2.06 m，较文献[18]中的3.18 m定位误差相比，定位精度提高了35%，且本文所提算法定位误差受速度变化的影响相对不大，变速运动误差范围在3 m以内的定位达到65%，与传统的欧氏距离瞬时指纹匹配的定位相比，累积错误率高于匀速运动3%，高于变速运动13%，因此，本文的基于时间序列模型的指纹定位算法以其特征数据量大的优势获得较好的定位效果。

3.3 开放区域定位效果

本文基于时间序列的指纹匹配算法，所建立的模型是基于路径的时间序列的指纹数据，因此定位效果会受到路径所影响，而对于开放区域路径规划较为困难，因此，本文针对该类型区域定位效果进行实验测试，如图 8所示，本文针对横向3条曲线以及与横向交叉的纵向12条曲线和一条S型曲线进行采样，并用横向曲线建模作为样本数据，对交叉的纵向曲线和S型曲线进行测试。

如图 9所示，针对交叉曲线本文的基于时间序列模型的DTW定位算法与传统指纹定位算法的在1~10 m误差范围内本文算法定位效果均好于传统指纹定位算法，误差范围在3 m以内的定位达到46%，较传统的欧氏距离瞬时指纹匹配的定位方法的累积错误率提高了9%，因其将整个开放区域作为一条路径可将一定范围内时间序列作为一个样本进行指纹匹配，即使无法达到与样本线路完全吻合也会略好于瞬时指纹数据，因此，定位效果较比传统指纹算法要好。

图 10所示的S型曲线的测试是为了验证本文算法在跨越线路的随机运动的定位效果，同样本文算法的定位效果优于传统的指纹定位算法。误差范围在3 m以内的定位达到48%，较传统的欧氏距离瞬时指纹匹配的定位方法的累积错误率提高了3%。本文算法的平均定位误差为3.05 m，较文献[18]中的3.77 m定位误差相比，定位精度提高了19%。

4 结语

本文针对基于指纹匹配室内定位算法面临的Wi-Fi信号时变特性引起的定位精度问题，提出了基于DTW距离指纹匹配定位算法，利用Wi-Fi采样信号在时间上先后顺序的相关性，建立了基于时间序列Wi-Fi信号指纹模型，并根据采样区域结构特征，将Wi-Fi信号指纹采集问题归纳为三类基本动态路径采样方式和两种区域路径规划情况，使指纹匹配准确性和定位精度得到提高，实验结果表明本文算法在匀速运动、变速运动以及开放区域等方面的定位效果均优于瞬时指纹定位算法。但是，在计算定位指纹匹配过程中，本文的DTW距离计算仍需平方时间复杂度，在一定程度影响了定位性能，这也是今后需要改进的方面。