随着社会生活以及服务业的发展，人们对定位的范围提出了更加精确的要求.传统的GPS定位技术由于其局限性, 无法实现更小范围的室内定位.常见的室内定位技术包括蓝牙(Bluetooth)^[1]，红外线^[2]，射频识别技术^[3]等，由于设备的局限性，这些技术并没有被广泛应用.相较于上述设备，行动热点(WiFi)的优势很明显：①随着无线网络的发展，WiFi设备随处可见；②相较于红外线来说，WiFi信号是多路径传播，不会受到光照等环境因素的影响，对环境适应性更强；③与射频识别技术相比，WiFi具有网络服务功能，便于信息的即时解析，且传输效率高. WiFi室内定位技术有很多种实现方法，包括到达时间法(TOA，time of arrival)^[4]、到达时间差法(TDOA，time difference of arrival)^[5]、到达角度法(AOA，angle of arrival)^[6]等.这些算法的实现都需要附加额外的硬件设备.此外，Singh等^[7]还提出了基于接收信号强度指示(RSSI，received signal strength indication)的定位，该方法虽然摆脱了额外硬件设备的限制，但无线信号的传播受环境影响较为严重，导致定位精确度低.为了弥补以上不足，Wang等^[8]提出了一种指纹定位方法，该方法分为2个步骤：第1步需在离线环境下进行，主要目标是构建位置指纹库，需要在各个定位点采集数据样本，经过训练得到各个点的指纹；第2步为实时定位，即根据位置指纹库来判断当前用户的位置.

基于Shapelet算法的指纹定位方法, 其主要创新点有以下几个方面：

1) 在数据预处理阶段，使用了3-σ异常值处理以及卡尔曼滤波，减少了周围环境及人员走动带来的干扰；

2) 将Shapelet算法做适当改进，用于提取信道状态信息(CSI，channel state information)子序列，作为各位置的指纹，构建指纹库；

3) 通过与现有方法进行比较，证实该方法在使用小样本进行训练的情况下能实现精确的定位，且保证其鲁棒性.

1 基本原理 1.1 CSI

在无线通信领域，CSI就是通信链路的信道属性，它描述了信号在每条传输路径上的衰落因子，即信道增益矩阵H中每个元素的值，如信号散射(scattering)、环境衰弱(fading multipath fading or shadowing fading)、距离衰减(power decay of distance)等信息.这表明在不同路径下，距离不同，所接收到的WiFi信号的各个子载波信息(CSI)会各不相同.根据这一原理，很多算法将不同位置点的CSI样本作为该位置点的指纹用于实现定位.而数据表明，对于代表各位置点的CSI序列，其主要差别仅体现在某些子载波或子载波构成的子序列.基于Shapelet算法的指纹定位方法就是根据这一原理，采集每个定位点的CSI数据，提取其中的振幅信息，选取最能区别于其他位置点的子序列Shapelet作为该位置的指纹，从而创建指纹库来实现定位.

1.2 Shapelet算法

Shapelet^[9]是一种时序数据挖掘方法.该方法指出在对2种时序数据进行分类时，会有一个最能体现其差异的子序列能实现最好的分类效果，这个子序列被称为Shapelet，其基本流程如下：

1) 数据集D中包含M、N两个类别的时间序列，使用滑动窗口k(取所有可能值)在所有序列上截取子序列，所有子序列构成Shapelet候选项集S；

2) 依次取出候选项集的每一个候选项S_i求出其与数据集D中每一个时间序列D_i的距离并依据大小排序；

3) 取所有距离值d对数据集D进行分类，求出相应的信息增益，取信息增益最大的距离值作为最佳分割点b，此时的信息增益为2)中候选项S_i的信息增益；

4) 将各个候选项的信息增益值进行比较，最大的信息增益值所对应的候选项S_i为选定的Shapelet.

根据应用，对于此方法主要做出的改进有2点：①针对每一个位置，在生成候选项的距离数据集时，只取该位置数据所对应候选项，而非候选项集中的全部；②由于CSI的规律性，在求候选项与每个CSI序列距离的时候，不再需要截取每个等长的子序列来比较，只需选与候选项位置对应的子序列即可，这样在很大程度上降低了时间复杂度.

2 方法流程

基于CSI的指纹定位技术主要有2个难点：①如何从CSI中提取出代表各个位置的指纹？Basiouny等^[10]使用主成分分析方法对数据集进行降维，在定位点样本空间中找到了最大限度表示该样本的一组正交向量作为该样本的指纹. Shapelet算法在提取每个位置的特征时，将每个位置信道状态信息中与其他位置差别最大的特征子序列作为该位置的指纹，以达到最好的定位效果. ②如何对用户所在的位置进行识别？该阶段主要通过分类算法来实现，主要有决策树、K近邻算法、神经网络以及深度学习等.基于①中位置指纹所构建的指纹数据库，使用决策树分类法实现对用户位置的判定，具体流程如图 1所示.其主要包括数据采集与预处理、Shapelet特征提取以及决策树定位等流程.

2.1 数据采集与预处理

在实验区域内布署WiFi路由器，并设定好定位点，将WiFi接收器分别采集各点的信道状态信息，并为这些样本添加位置标签.每个位置点采集的样本要足够多，每个样本h包含30个子载波(h₁, h₂, …, h₃₀)，以从中提取振幅信息.由于数据采集环境中，其他的WiFi信号、物体反射以及人员站位和走动都会对信号产生影响和干扰，导致出现数据发生偏差或缺失等情况.为此，采用了3-σ异常值处理法以及卡尔曼平滑滤波对该原始数据进行预处理.

在使用3-σ法对异常值进行处理时，要将每个位置点所有样本的第j(1≤j≤30)个子载波构建成一个矩阵H_1j, H_2j，…, H_nj，求其均值$ \mu = \frac{1}{n}\sum\limits_{i = 1}^n {{\boldsymbol{H}_{ij}}} $，标准差$ \sigma = \sqrt {\frac{1}{n}\sum\limits_{i = 1}^n {{{\left( {{\boldsymbol{H}_{ij}} - \mu } \right)}^2}} } $；对其中的每个数据值进行判断，将所有H_ij(H_ij＞μ+3σ‖H_ij＜μ-3σ)作为异常值；然后用均值来代替每个异常值.经过这样的处理，将原始数据中干扰引发的异常值进行修正.之后采用了卡尔曼滤波对数据进行平滑处理.

2.2 Shapelet特征提取及构造指纹库

经过异常值处理和卡尔曼滤波等预处理后的CSI数据趋于平稳，接下来将对每一个位置点的数据进行特征提取，构建最终的指纹库.

1) 构建Shapelet候选项集

选取每个定位点的10个数据样本作为训练集D，将每个数据样本作为一个序列D_ij，设置候选项序列的最小长度和最大长度.从第i个定位点的训练集D_i(i=1, 2, …, 16)中依次取序列D_ij(j=1, 2, …, 10)作为原始序列，在D_ij上截取所有可能长度的子序列s_k，长度l介于最小长度与最大长度之间.所有的子序列s_k构成第i个定位点的Shapelet候选项集S_i.

2) 构造距离数据集

从第i个定位点的候选项集S_i中取所有子序列s，依次构造其距离数据集.

取第k个子序列s_k，计算s_k与D中所有序列D_ij的距离d_ij.在D_ij上截取与s_k相同位置的子载波序列X，则

$ {d_{ij}} = \sum {{{\left[ {{s_k}\left( a \right) - X\left( a \right)} \right]}^2}} $

(1)

将d_ij按大小顺序存入数据集P.

3) 求最佳分割点

依据2)中的数据集P，选取相邻数据的均值作为分割点$ f = \frac{{{P_i} + {P_{i + 1}}}}{2}\left( {i = 1, 2, \cdots , 160} \right) $，将满足d_ij≤f的样本序列D_ij划分至数据集D₁中；反之，划分至D₂中，并求该分割方式下的信息增益，如

$ G = E\left( D \right) - \frac{{{l_1}}}{l}E\left( {{D_1}} \right) - \frac{{{l_2}}}{d}E\left( {{D_2}} \right) $

(2)

其中：l、l₁、l₂分别为数据集D、D₁、D₂的大小；E(D)为D的熵，其表达式为

$ E\left( D \right) = - \frac{a}{d}\log \left( {\frac{a}{d}} \right) - \frac{q}{d}\log \left( {\frac{q}{d}} \right) $

(3)

其中：a为数据集D中第i个定位点样本的个数，q为数据集D中不属于第i个定位点的样本个数.

根据式(3)，依次求得所有分割点的信息增益G，取信息增益最大值为第k个Shaplet候选项的最大信息增益g_k，取相应的分割点f为第k个Shapelet候选项的最佳分割点b_k.

4) 构造Shapelet位置指纹库

依次求得各个候选项的最大信息增益g_k及最佳分割点b_k后，取g_k最大的候选项子序列为第i个定位点的特征子序列S_i，并标记其对应的最佳分割点最佳分割点b_i.依次求得每个定位点的Shapelet，并存入位置指纹库F.至此，完成了位置指纹库的构造，训练阶段结束.

5) 构造Shapelet决策树

根据决策树的定义，需要为决策树选定内部节点和叶子节点. 2.2节所构造的位置指纹库便是决策树构造的依据.叶子节点依次为每个定位点，内部节点依次为其对应的定位点特征子序列F_i与目标序列的距离d，如果该距离值满足(d≤b_i)，则有向边指向定位点；否则，有向边指向另一分支.最终构造Shapelet决策树，如图 2所示.

2.3 决策树定位

方法中使用了决策树分类来实现定位，其主要方法是将定位数据与构建的决策树内部节点，即每个位置点的指纹特征，进行匹配.若与某一特征匹配成功，则可认定其位置在该点.操作步骤如下：

1) 对定位样本进行预处理操作，去除干扰与噪音；

2) 根据图 2所示的决策树，将每一个定位样本依次与16个定位点匹配.具体依据式(1)求出与每个定位点指纹F_i, 的距离d；

3) 如果d≤b_i，则判定该样本是在i点采集到的，实现定位.

3 结果分析与比较 3.1 实验设计

本实验分别在2个实验场地进行，如图 3所示. ① 4.8 m×4.8 m的空旷环境，选位置点16个，相邻点间距均为1.2 m；② 4 m×6 m的休闲区，其中有4组桌椅以及走廊过道，共选位置点12个，相邻点间距同为1.2 m.在以上2个场地中每个位置点分别采集CSI数据，分3个时间段进行：第1天上午实验环境1采集的数据为A₁，实验环境2采集的数据为B₁；第1天下午实验环境1采集的数据为A₂，实验环境2采集的数据为B₂；第2天上午实验环境1采集的数据为A₃，实验环境2采集的数据为B₃.分别提取CSI数据中的振幅数据，并对这些数据样本进行标记.

离线建立指纹库阶段，在A₁、B₁中为每个定位点选取10个训练样本，对这些样本进行预处理，并根据上述方法提取位置指纹，分别构造决策树T₁、T₂.在实验中，分别测试了基于Shapelet算法的指纹定位与基于主成分分析(PCA，principal components analysis)算法及k近邻(KNN，k-nearest neighbor)算法的指纹定位结果，并分析比较了定位精确度和平均定位误差, 其中PCA与KNN算法的所使用的训练集为A₁、B₁.

3.2 实验结果分析

1) 实验环境1下的结果分析

在对数据A₁的测试中，在定位误差小于1 m时，基于Shapelet算法定位方法的精确度达到99.58%，基于PCA算法与KNN算法的定位方法高达100%，其中误差累计分布如图 4所示.

在对测试数据A₂的实验中，定位误差小于1 m时，基于Shapelet算法的定位的精确度为91.21%，基于PCA算法的方法进行定位精确度为92.24%，使用KNN算法进行定位精确度为97.74%.定位误差累计分布如图 5所示.

将数据A₃作为测试数据进行定位，定位误差小于1 m时，基于Shapelet算法的定位精确度依旧很高，为89.34%；而使用PCA算法和KNN算法的定位方法定位精度达89%时，定位误差分别为4 m和3 m.定位误差累计分布如图 6所示.

根据上述各定位结果计算出每次实验的平均定位误差，如表 1所示.对于同一天采集的数据A₂，3种定位方法的定位误差都比较小；对于第2天采集的数据A₃来说，基于Shapelet算法的定位方法平均误差达到了25.8 cm，而使用基于PCA和KNN的指纹定位方法平均误差分别为91.20 cm和65.48 cm.

2) 实验环境2下的结果分析

在环境2下，仅对数据B₂、B₃进行了定位测试，结果如图 7、图 8所示.在复杂环境下，不同时间段内基于Shapelet算法的指纹定位在1.2 m内的定位精度依旧保持稳定，分别为90.34%和87.34%；基于PCA算法的定位精度分别为93.20%和59.2%；基于KNN算法的定位精度分别为89.2%和73.3%.在该环境下的平均误差如表 2所示.

上述实验结果表明，基于Shapelet算法的指纹定位方法不同时间的定位精度较高，且能保持稳定.

4 结束语

提出了一种基于Shapelet算法的指纹定位方法，在相对理想的环境下搭建常用的数据采集平台，在WiFi信号中提取CSI数据，并对该数据进行处理修正；通过Shapelet特征提取方法提取各个定位点的指纹，构建指纹库；使用Shapelet决策树方法实现定位，使得不同时间段的平均定位精度达到90.23%，明显优于PCA算法以及KNN算法.实验结果表明，Shapelet特征提取算法对于不同时间段的数据，定位准确率较高；Shapelet算法所需要的训练集数据需求量小.针对这两点可以看出，使用Shapelet算法实现定位在生活中适用性更强.