基于DTW的室内指纹定位方法

徐莉莉， 范 洪， 胡军国

(浙江农林大学 信息工程学院，浙江 临安 311300)

0 引 言

在大型室内场景中定位需求日益显著，如在物流仓库为搬运机器人提供路径导航等[1～3]。然而目前的室内定位方法(如全球定位系统(global positioning system,GPS)、北斗、无线局域网(WiFi)定位、蓝牙定位、ZigBee定位、超宽带定位[4]等)存在诸多问题，很难应用于实际，因此研究一种可靠、低成本的定位方法意义重大。

目前室内定位方法可分为2种趋势：基于信号强度的测距定位方法；基于特征匹配的指纹定位方法。其中测距定位主要是利用信号强度随着传播距离衰减的特征进行测距，计算未知节点的位置。如文献[5,6]通过优化接收信号强度指示(recieved signal strength indication,RSSI)测距模型从而使得定位结果更加准确。文献[7]研究了一种新的信号强度观测模型并利用多锚节点协作定位。而基于特征匹配的指纹定位方法主要通过建立定位区域的特征指纹，然后利用匹配算法获得定位结果。如文献[8,9]采用WiFi构建定位指纹，通过控制指纹的匹配范围从而获得较高的定位精度。文献[10]利用Kriging插值方法构建定位区域指纹并通过K-means算法优化定位结果。文献[11]通过在室内普通电源线上注入宽带高频信号来构造定位指纹从而实现高精度定位。综合考虑实用性和定位精度，利用地磁特征进行室内定位是较好的选择[12～14]。

本文提出一种基于动态时间规整(dynamic time warping,DTW)的室内定位方法。该方法通过采集室内的地磁数据建立定位区域指纹，然后采用DTW算法进行特征匹配，同时为了提高定位精度，引入匹配范围和K-means误差排除等方法。

1 系统框架

定位方法总体框架如图1，定位过程主要可分为2部分：定位区域地磁指纹构建；地磁与气压融合进行定位。

图1 系统框架图

2 指纹构建

2.1 特征数据采集

在地磁指纹构建和定位两个过程中都需要智能设备采集数据，为了保证定位的实时性，采集数据的频率为60 Hz，采集的数据包括地磁的x,y,z三轴数据和气压数据。由于地磁的三轴数据与传感器的方向相关，但是x,y,z三轴地磁数据的模与地磁传感器方向无关，因此采用地磁的向量模进行后续计算，地磁的向量模(geomagnetic-vector module,GM)为

(1)

2.2 地磁波形配准和物理坐标标定

为了构建可靠的地磁指纹数据库，需要对定位区域进行多次数据采集，而每次采集数据时由于采集者的行走速度等原因的不同，会导致波形之间有错位。如果直接将多条地磁波形融合构建地磁指纹数据库会造成指纹数据库的不准确，从而影响定位结果。本文通过平移法对地磁波形进行配准，每次平移10个地磁数据然后记录每次平移后两个波形的余弦相似度，最后选择余弦相似度最高的位置作为波形配准后的位置。假设待配准的地磁波形用集合D={d1,d2,d3，…，dm}表示，样本地磁波形用集合Dy={dy1,dy2,dy3，…，dys}表示，配准前后如图2所示，配准后的地磁波形能够较好吻合。地磁波形配准方法为：

输入:样本地磁波形Dy；待配准的地磁波形D。

输出:待配准的地磁波形需要平移的位数。

1)扩展集合D，扩展后的集合为D′={0,0,0，…，d1,d2,d3，…，dm}，共m+s个元素。

2)扩展集合Dy，扩展后的集合为D′y={dy1,dy2,dy3，…，dys,0,0，…，0}，共m+s个元素。

3)计算D′和D′y的余弦相似度并保存到数组S中。

4)删除集合D′最前面10个元素，删除集合D′y最后面10个元素。

5)判断集合D′的元素数量是否小于m/2，如果是，则退出循环并根据数组S中的最大值输出配准需要平移的位数；否，则执行步骤(3)。

图2 波形配准

为了构建地磁指纹数据库，还需要为采集的地磁波形映射物理坐标。在采集数据的过程中记录下行走的路径，然后将该路径对应的物理坐标均匀映射到地磁波上，从而构建了地磁波形和物理坐标一一对应的指纹数据库。

3 定位过程

3.1 DTW地磁匹配

由于在定位过程中不同使用者的行走速度并不相同，这会导致在经过同一段路程时采集的地磁波形不完全相同，因此用传统的方法(如余弦相似度)计算波形相似度很难达满足需求。 本文采用DTW算法进行波形相似度匹配，能够动态规划两条波形的匹配点，即使地磁指纹数据库波形和待匹配的地磁波形在时间序列上的地磁数据数量不同也能较好地进行波形匹配。

在定位过程中智能设备实时采集地磁数据，利用滑动窗口截取实时数据流中的一段地磁波形作为待匹配的地磁波形用于和地磁指纹数据库中的地磁波形进行匹配。系统每进行1次定位，DTW算法会匹配地磁指纹数据库中所有的地磁波形并计算相似度，然后选择波形匹配相似度最高的前n个匹配点作为匹配结果，根据匹配点对应的物理坐标得到n个定位坐标，最后根据误差排除方法，融合n个定位结果获得最终的一个定位结果。

3.2 定位误差排除

为了提高定位精度、防止匹配偶然性带来的定位误差，本文选择匹配度最高的前n个定位结果作为定位结果集群，然后对定位结果集群进行误差点排除，最终获得精度较高的定位结果，如图3所示，图中阴影区域表示误差较大的定位结果，椭圆形内的有色区域表示误差较小的定位结果。

本文采用K-means对n个定位结果进行聚类，共聚为K类，选择元素最多的1类作为有效定位结果集，然后以有效定位结果集的重心作为最终定位结果，而其他元素较少的误差类则能够有效排除，从而提高了定位精度。

图3 定位结果优化

3.3 楼层判断

楼层的判断可通过气压传感器实现，不同的楼层气压有明显的差异，当用户上楼时，气压减小，当用户下楼梯时，气压增大，如图4所示。图中记录了用户从四楼下到三楼(A～B)，在三楼稍作停留后又上到四楼(C～D)，稍作停留后又上到五楼(E～F)的气压变化情况。结果表明:每次上下楼梯，气压的变化值大约为40 Pa，而在同一楼层，气压值基本没有太大的变化。

图4 大气压强变化

本文利用气压变化值的大小判断用户在定位过程中是否发生了楼层的变化。如果当前传感器读取的气压值为P，则系统计算前T时间内采集的气压值与当前气压P的差值，寻找差值中绝对值最大的值，设前T时间内与气压P的差值绝对值最大的气压为PT，若P-PT<0且PT-P>Pth(本文设定阈值40 Pa)，则表明此时用户上了一层楼，若P-PT>0且P-PT>Pth，则表明此时用户下了一层楼。

4 系统实验

本文将定位算法部署到Nexus智能手机上，该手机配备地磁传感器和气压传感器。定位实验场景是三层教学楼内的走廊，三条走廊形状一致，走廊中定位的路程总长度为14.2 m，走廊宽度为1.3 m。

4.1 定位时间间隔对精度的影响测试

定位的精度和定位实时性是算法的重要指标，地磁波形子序列越长，则匹配过程中的依据越多，匹配准确率越高，定位精度也就越高，而地磁波形子序列越长，在匹配过程中则需要更大的运算量，定位消耗的时间也就越长。因此,本实验研究地磁波形子序列长度对定位精度和算法实时性的影响，图5所示。图5(a)表明，地磁波形序列越长，定位误差越小，因为地磁波形序列越长，在匹配时的特征点越多，匹配越准确。当地磁波形序列长度为3 s时，定位误差基本达到稳定，误差大约为1.6 m。图5(b)表明地磁波形序列越长，则每次定位需要消耗的时间越长，因为波形越长，在波形匹配时，运算量越大，因此消耗时间越多。本文将地磁波形序列长度设置为1.8 s，即在定位过程中，每隔1.8 s进行1次定位。

图5 算法性能

4.2 定位结果优化实验

对定位结果进行优化能够提高定位精度，本实验对比了没有进行误差排除和进行定位结果优化的结果，如图6所示，在进行误差排除前，共选择了10个最高相似度的位置作为有效定位结果集，排除误差后最终计算得到一个较可靠的定位结果。

图6 定位结果优化

实验结果表明:没有经过误差排除处理的定位结果误差较大，且存在跳动的情况，平均定位误差在2 m以上，而采用K-means方法进行误差排除，其定位结果比较稳定，平均定位误差约为1.4 m。

4.3 匹配范围

根据上次定位结果为下次定位限定地磁指纹数据库搜索范围，既可以提高定位精度，还可以减少系统运算量。本次实验对比限制地磁指纹数据库搜索范围前后对定位精度的影响，实验结果如图7所示。

图7 匹配范围影响

实验结果表明：限制了地磁指纹数据库的搜索范围能够较大幅度提高定位精度，其定位误差最小约为1.6 m，而不限制搜索范围的定位精度比较差，最小定位误差约为3.1 m 左右，因为本文根据上次匹配的定位结果和匹配相似度限制了地磁指纹数据库的搜索范围，使得DTW算法匹配准确率更高，从而提高了定位精度。

5 结 论

本文采用室内地磁场构建定位指纹，利用DTW算法进行指纹匹配，实现初步定位，并引入匹配范围减少系统运算量，最后采用K-means优化定位结果，实验结果表明，提出的定位方法具有较高的定位精度和适应性，能够满足室内定位的需求。