一种指纹定位中的预测式指纹图搜索方法

摘要

本发明属于无线电导航定位技术领域，提供一种指纹定位中的预测式指纹图搜索方法。本发明首先将采用滤波算法预测出的位置信息作为先验信息，以先验信息为中心，通过向周边辐射的方式进行搜索。搜索过程中不断更新信号空间欧氏距离上距信号特征TP最近的K个参考点RP。当连续搜索L次且K个RP没有变化时，则认定此K个RP为最终选定的，用于位置估计的参考点，并带入KNN算法中进行解算，本发明能够取代传统的对指纹图进行顺序搜索方法。本发明的有益效果为与分簇后定位的传统方法相比，能够提高定位精度，与不分簇的传统方法相比，搜索速度更快。

权利要求

1.一种指纹定位中的预测式指纹图搜索方法，其特征在于以下步骤：步骤1：预设搜索上限L；首次定位时，采用传统指纹定位方式对用户进行定位，得到第一个定位结果；非首次定位时，通过滤波算法对之前得到的定位结果进行计算，得到预测值(X′i，Y′i)；

步骤2：计算与步骤1得到的结果最近的参考点RP(a，b)，a和b表示步骤1中定位结果最近的相邻参考点的编号；

步骤3：计算RP(a，b)与TP之间的信号空间欧氏距离；所述的TP为用户在定位过程中自身测量的信号特征；

步骤4：以RP(a，b)为中心，搜索与RP(a，b)相邻的参考点RP，分别算出每一个参考点RP与TP之间的信号空间欧氏距离；

步骤5：记录步骤4信号空间欧氏距离中最小的K个参考点，令搜索计数器Nc＝0；

步骤6：向外扩展一圈搜索范围，并计算该搜索范围内的参考点RP，并分别算出每一个参考点RP与TP之间的信号空间欧氏距离；所述的搜索范围为以之前搜索过的所有参考点RP为中心，搜索与该中心相邻的参考点RP；

步骤7：记录步骤6中信号空间欧氏距离中最小的K个参考点；

步骤8：观察步骤7前后的两组K个选定的参考点RP是否有变化：若有变化，则返回步骤

6，Nc＝0；若没有变化，则Nc＝Nc+1，并判断Nc与预设搜索上限L的大小关系，若Nc不小于L，则进入步骤9，若Nc小于L，则返回步骤6；

步骤9：将步骤7中的K个参考点的位置带入KNN算法中进行定位，得到本次定位结果(Xi，Yi)；重复所有步骤，进行下一次定位。

说明书

一种指纹定位中的预测式指纹图搜索方法

技术领域

[0001] 本发明属于无线电导航定位技术领域，涉及到指纹定位技术，特别涉及到一种指纹定位中的预测式指纹图搜索方法。

背景技术

[0002] 指纹定位技术广泛应用在室内定位领域，该技术分为两个阶段：

[0003] 第一阶段为离线阶段，既在给定区域内，通过逐点测量等手段，将物理空间位置与信号空间特征之间建立映射关系，用户可以通过对比该映射关系估计自身位置。具体为：空间建立映射关系，通过数据库的方式存储，而存储的数据库被称为指纹图；指纹图由若干参考点(RP)构成，每个RP存储其物理地址和信号特征向量信息。

[0004] 第二阶段为在线定位阶段，系统将采集侧脸的信号特征(TP)与指纹图中的RP进行空间欧氏距离的计算，得出其相似度，从而记录下与TP间欧式距离最近的K个RP。通过KNN算法，将所得K个RP值进行估计，得到的位置即为定位位置。为减轻解算时间对定位系统造成的定位结果延迟，系统中往往还会引入滤波算法，根据前几次定位的结果对用户当前位置进行预测，从而提高定位精度。

[0005] 指纹定位常见指纹图过大问题，既每次搜索时过大的指纹图导致搜索量庞大，使得定位速度达不到标准。常规解决办法为分簇：将具有类似信号特征的向量归为一簇，定位时先通过计算出与簇头的欧氏距离，找出自身所在的簇，再在该簇的指纹图上进行遍历搜索以定位，以达到搜索分级，降低工作量。

[0006] 但常见分簇方法存在局限性：分簇过多导致分簇失去意义，分簇过少则达不到降低搜索量的作用，同时带来的簇边缘模糊问题，使得分簇定位易造成误差。即便分簇时预先画出交叠区也不能完全避免此情况。此外，如果发生簇头识别错误的话会导致较大的定位误差。目前的分簇手段包括依据设计者的主观认知进行人工分簇，以及根据数学算法进行自动分簇。前者可能出现簇内信号特征域上的不统一，而后者可能造成位置空间域上的不统一。因此二者都有可能在簇头识别时引入误差，从而降低定位精度。

发明内容

[0007] 针对现有指纹定位技术中存在的由于分簇带来精度下降问题，本发明提供一种更加高效的指纹图搜索的方法。

[0008] 本发明的技术方案为：

[0009] 一种指纹定位中的预测式指纹图搜索方法，所述的预测式指纹图搜索方法首先将采用滤波算法预测出的位置信息作为先验信息，以先验信息为中心，通过向周边辐射的方式进行搜索。搜索过程中不断更新信号空间欧氏距离上距信号特征TP最近的K个参考点RP。当连续搜索L次且K个RP没有变化时，则认定此K个RP为最终选定的，用于位置估计的参考点，并带入KNN算法中进行解算，取代传统的对指纹图进行顺序搜索方法。

[0010] 本发明具体包括以下步骤：

[0011] 步骤1：预设搜索上限L；首次定位时，采用传统指纹定位方式对用户进行定位，得到第一个定位结果；非首次定位时，通过滤波算法对之前得到的定位结果进行计算，得到预测值(X′i，Y′i)；所述的传统指纹定位方式为传统的分簇解算方法或不分簇解算方法。

[0012] 步骤2：计算与步骤1得到的结果(第一个定位结果或预测值(X′i，Y′i))最近的参考点RP(a，b)，a和b表示步骤1中定位结果最近的相邻参考点的编号。

[0013] 步骤3：计算RP(a，b)与TP之间的信号空间欧氏距离；所述的TP为用户在定位过程中自身测量的信号特征。

[0014] 步骤4：以RP(a，b)为中心，搜索与RP(a，b)相邻的参考点RP，分别算出每一个参考点RP与TP之间的信号空间欧氏距离。

[0015] 步骤5：记录步骤4信号空间欧氏距离中最小的K个参考点，令搜索计数器Nc＝0。

[0016] 步骤6：向外扩展一圈搜索范围，并计算该搜索范围内的参考点RP，并分别算出每一个参考点RP与TP之间的信号空间欧氏距离；所述的搜索范围为以之前搜索过的所有参考点RP为中心，搜索与该中心相邻的参考点RP。

[0017] 步骤7：记录步骤6中信号空间欧氏距离中最小的K个参考点。

[0018] 步骤8：观察步骤7前后的两组K个选定的参考点RP是否有变化：若有变化，则返回步骤6，Nc＝0；若没有变化，则Nc＝Nc+1，并判断Nc与预设搜索上限L的大小关系，若Nc不小于L，则进入步骤9，若Nc小于L，则返回步骤6。

[0019] 步骤9：将步骤7中的K个参考点的位置带入KNN算法中进行定位，得到本次定位结果(Xi，Yi)；重复所有步骤，进行下一次定位。

[0020] 本发明的效果和益处是相比分簇后进行定位的传统方法，提升了指纹定位系统的定位精度，并且比不分簇的传统算法搜索速度更快。

附图说明

[0021] 图1是本发明工作流程图。

[0022] 图2是仿真验证的定位精度仿真结果图。

具体实施方式

[0023] 以下结合技术方案(和附图)详细叙述本发明的具体实施方式。

[0024] 本发明输入输出变量分别为：

[0025] 输入：指纹图参考点信号特征数据库；指纹图参考点空间位置数据库；TP的信号特征；KNN算法的k值；前次定位结果的X坐标；前次定位结果的Y坐标；搜索上限L。

[0026] 输出：定位结果；搜索过的参考点数目。

[0027] 具体实施中本发明包括以下步骤：

[0028] 实施例1：

[0029] 步骤1：预设搜索上限L；首次定位时，采用传统指纹定位方式对用户进行定位，得到第一个定位结果；非首次定位时，通过滤波算法对之前得到的定位结果进行计算，得到预测值(X′i，Y′i)。

[0030] 步骤2：计算与步骤1得到的结果(第一个定位结果或预测值(X′i，Y′i))最近的参考点RP(a，b)，a和b表示步骤1中定位结果最近的相邻参考点的编号。

[0031] 步骤3：计算RP(a，b)与TP之间的信号空间欧氏距离；所述的TP为用户在定位过程中自身测量的信号特征。

[0032] 步骤4：以RP(a，b)为中心，搜索与RP(a，b)相邻的参考点RP，分别算出每一个参考点RP与TP之间的信号空间欧氏距离。

[0033] 步骤5：记录步骤4信号空间欧氏距离中最小的4个参考点，令搜索计数器Nc＝0。

[0034] 步骤6：向外扩展一圈搜索范围，并计算该搜索范围内的参考点RP，并分别算出每一个参考点RP与TP之间的信号空间欧氏距离；所述的搜索范围为以之前搜索过的所有参考点RP为中心，搜索与该中心相邻的参考点RP。

[0035] 步骤7：记录步骤6中信号空间欧氏距离中最小的4个参考点。

[0036] 步骤8：观察两组4个选定的参考点RP是否有变化：若有变化，则返回步骤6，Nc＝0；若没有变化，则Nc＝Nc+1，并判断Nc与预设搜索上限L的大小关系，若Nc不小于L，则进入步骤
9，若Nc小于L，则返回步骤6。

[0037] 步骤9：将步骤7中的4个参考点的位置带入KNN算法中进行定位，得到本次定位结果(Xi，Yi)；重复所有步骤，进行下一次定位。

[0038] 实施例2：

[0039] 本实施例中预设搜索上限L为5，K值为4，其它步骤与实施例1相同。

[0040] 实施例3：

[0041] 本实施例中预设搜索上限L为10，K值为4，其它步骤与实施例1相同。

[0042] 图2为传统指纹定位方法与采用本发明定位方法得到的定位精度仿真结果图，表1为仿真验证的定位速度仿真结果。从图2中可以看出，分簇后的定位精度最低，其方差最大；而本发明的定位精度则与不分簇的传统方法相当。单参数选择合理时(如图中的L＝5时)，本发明的定位精度甚至高于不分簇的传统指纹定位算法。由于指纹定位的速度主要由每次定位中需要搜索的参考点的数量来决定，从表1中可以看出，分簇方法的搜索参考点数量最少，但结合图2中的仿真结果可知，其定位精度最低。表1中同样可以看出，本发明的参考点搜索数量低于不分簇的传统指纹定位手段，即，定位速度更高，而且结合图2中的分析，本发明的定位精度更高。

[0043] 表1仿真验证的定位速度仿真结果

[0044]