基于分步的位置指纹定位算法研究

2018-12-03杨勇明

电子科技 2018年11期

杨勇明

(上海理工大学公共实验中心，上海 200093)

当今，高层建筑越来越多，在这些人口密集的场所，由于受到障碍物的阻挡，GPS信号强度大大减弱，其定位精度远不及室外；而缺少室内地图，也导致了城市 “盲区”的出现。在人口密集的场所，诸如儿童看护、应急救援、商场导购等领域，对基于定位的服务[1](Location Based Services，LBS)需求量越来越大。此外，物联网与智慧城市[2]概念的提出推动了室内定位技术及其应用市场的迅速发展。射频识别技术(Radio Frequency Identification，RFID)以非视距、非接触、多目标读写、可重复使用等优点[3]成为目前室内定位的首选技术。

常用的室内定位算法主要包括基于测距的三边定位算法和基于非测距的位置指纹定位算法。由于受环境因素影响较小[4]，位置指纹定位算法成为诸多学者研究的焦点。LANDMARC定位算法由文献[5]提出，是基于非测距的经典算法。

1 传统LANDMARC定位算法

1.1 LANDMARC定位算法

LANDMARC定位算法原理图[6]如图1所示，假设定位系统中有m个阅读器、n个参考点标签、p个未知点：第一步，令θr,j表示第r个参考点标签在第j个阅读器上测得的信号强度值，其中r=1,2,3,4,…,n,j=1,2,3,4,…,m；第二步，令si,j表示第i个未知点在第j个阅读器上测得的信号强度值，其中i=1,2,3,4,…,p；第三步，对未知点测得的信号强度与数据库中对应参考点标签的RSSI((Received Signal Strength Indicator))值进行关联程度计算，即进行si,j和θr,j相似度计算，以式(1)所示的信号强度均方差表示

(1)

图1 LANDMARC算法原理图

Ei,r表示欧几里得距离[7]，根据式(1)，当未知点RSSI值与数据库中对应参考点标签的RSSI值接近时，表示未知点与参考标签的位置十分接近。由于数据库中有n个参考点标签，故将未知点与参考点标签一一进行相似度计算，并按照欧式距离的大小进行排序。为减小定位误差，通常选取距离最相近的k个参考点标签进行计算[8]，如式(2)所示，每个参考点标签坐标都要添加权值，权值的取值和欧式距离的大小有关。当未知点离参考点标签的实际位置较近时，权值较大；未知点与参考点距离较远时权值较小。

(2)

结合已知参考点标签的坐标，根据公式(3)进行未知坐标计算

(3)

式中(x,y)表示未知点的坐标，(xi,yi)表示已知参考点标签的位置坐标。

1.2 LANDMARC定位算法冗余性分析

LANDMARC定位算法中，选定的k个参考点标签坐标决定了LANDMARC得定位精度。其余参考点坐标也参与定位过程，不仅增加系统的复杂度，也增加了错误的产生率，进而产生数据冗余现象[9]，导致系统效率和实时性下降，影响用户体验。针对此问题，本文提出基于分步的位置指纹定位算法。在离线训练阶段，进行粗粒度的定位(粗略定位)，确定未知点所在的区域，排除不可能的区域点；在在线定位阶段，进行细粒度的定位(精确定位)。

2 基于分步的位置指纹定位算法

使用基于分步的位置指纹定位算法进行距离估算时，不依赖精确的室内传播模型，可以减小环境因素对定位精度的影响；此外使用粗粒度与细粒度的概念，有利于实现粗定位和精定位。基于分步的位置指纹定位算法流程图如图2所示。

图2 位置指纹算法流程图

2.1 离线训练阶段

环境分析[11]是基于分步的位置指纹定位算法的第一步，也是关键一步。良好的环境分析有助于定位区域的合理规划、参考节点位置和数量的确定，能够减少阅读器和标签的使用数量、节省系统成本，还可以减少部分数据的计算量。

参考点包括粗粒度参考点和细粒度参考点。粗粒度点主要负责大致确定未知点所在的区域，描述待定位区域的大致轮廓。粗粒度点设置合理可快速的确定未知点所在的区域，避开一些不必要参考点的计算。通常将粗粒度点设置在几何图形的中心位置，如正方形或者三角形的中心。粗粒度点确定后就需要确定细粒度点位置，细粒度点数量较多，通常围绕着粗粒度点呈放射状或者矩形状。基于分步的位置指纹定位算法原理图如图3所示。

图3 基于分步的位置指纹算法原理图

建立位置-信号强度指纹库[12]，在各个参考点处测得每一个标签的信号强度值，建立位置-信号强度指纹数据库。各个参考点接收到的信息按照标签1、标签2、标签3、…、标签n的规律建立数据库，例如共有m个参考点，n个标签，参考点的坐标为(xi,yi)，第i个参考点处接收到第t个标签的信号强度表示为RSSi,t,则任意一个参考点在指纹库中表示为(xi,yi,RSSi,1,RSSi,2,RSSi,3……RSSi,n)。

2.2 在线定位阶段

分步定位主要应用于在线定位阶段，在未知点处实时测得各个标签信号强度值，进行多次测量求取平均值，完成第一步粗定位。在缩小未知点所在区域时，将求得的平均值与粗粒度点进行矢量匹配性分析，计算出未知点与粗粒度点之间的相似度。如图3所示，将待定位区域划分为A、B、C、D、E、F、G、H、I9个区域，每个区域对应一个粗粒度点，用红色五角星表示。计算完欧氏距离后，选取欧式距离最小的粗粒度点所包含的区域作为定位区域的粗定位区间，与图3中9个参考粗粒度点进行对比后确定未知点所在的区域为E，则下一步在区域E进行精确定位。

如图4所示，精确定位时，舍弃与定位结果无关的A、B、C、D、F、G、H、I区域内的参考点，只将未知点的信号强度与定位区域E内4个细粒度参考点进行相似度匹配即可：首先根据粗粒度点确定细粒度点，并将其利用到第二步精确定位；然后通过与参考细粒度点运用加权K近邻算法进行未知点坐标值计算。该算法大大减少计算量，提高了定位效率。

图4 细定位原理图

3 实例验证

3.1 实验环境

实验环境选择上海理工大学机械创新实验楼的一楼大厅，测试范围为长3.6 m，宽3.6 m的区域，实验仪器选择2.4 GHz远距离RFID阅读器和有源RFID电子标签。基于RFID的应用主要分为标签的移动和阅读器的移动[13]，本次实验选择阅读器移动，该方法的优势是数量较多、价格较便宜的标签被放置在已知位置点，仅需使用一个阅读器即可完成，费用较低。实验开始前，检查笔记本与阅读器之间的通信连接状况，检查所有的有源标签的纽扣电子是否电量充足，定义实验中阅读器的位置代表未知点的位置。

图5 实际实验测试图

图5为实际实验的测试图，图6为实验布置图。图6中按照如图所示的方式选定坐标原点，建立坐标系，布置好标签，图中每个小正方形的边长为0.6 m，实验选择的有源标签数量共计4个，用五角星表示。离线训练阶段，需要建立的数据点用圆表示，并进行阿拉伯数字编号，有源标签点处需要进行数据点的测量，用于粗粒度点数据库的建立。

图6中，1～4为有源标签的位置，放置在地板砖的中心位置，并且标签要竖直放置以便阅读器的天线与标签处于同一高度，保证阅读器更有效的接收标签信号强度。阅读器的位置代表未知点位置，当阅读器在1～4有源标签位置时，测得各个标签的信号强度。该条件下建立的数据库点为粗粒度点，而粗粒度点也是部分细粒度点的中心。21～24为未知点，1～20为训练阶段建立位置信号强度数据库时所需要测量的数据点。在此过程中有源标签的摆放位置要精确，有源标签的方向也要保持一致。阅读器在每个位置测量有源标签的信号强度时，若天线朝向始终保持一致，则可有效减小其它因素对实验结果的影响。

图6 无障碍物实验布置图

3.2 实验步骤

(1)离线训练阶段。确定坐标原点后，依次把阅读器放在1～20号数据点处，阅读器的中心放置在地板砖的中心位置，在各点处阅读器的天线朝向保持一致。由于受其它环境因素的影响[14-15]，信号强度并不稳定，为了克服信号强度不稳定对定位的影响，减小实验误差，通常在每个参考点多次测量取平均值，每个数据点测量100次。获得数据后，首先建立粗粒度数据库，然后根据各点的归属，在粗粒度点下建立细粒度数据库，数据点存储格式为(xi,yi,RSSI1,RSSI2,RSSI3,RSSI4)，RSSIi表示接收到的第i个标签的信号强度值，例如标号为5的位置点存储格式为 (0.3,0.3,-65,-71,-60,-69)。

(2)在线定位阶段。阅读器的位置代表未知点的位置，在未知点处依次读取到标签1、标签2、标签3、标签4的信号强度，接下来进行算法的实现和对比分析。基于分步的位置指纹定位算法测得未知点处的各个标签信号强度之后，先和粗粒度点1、2、3、4进行匹配性分析。LANDMARC定位算法仅需要与第(1)阶段建立的所有指纹点即1～20进行匹配性分析。基于分步的位置指纹定位算法和LANDMARC定位算法选用加权K近邻算法，K取值为4。采用图7所示的基于分步的位置指纹定位GUI界面，完成分步的位置指纹定位算法和LANDMARC定位算法效率的对比与分析，其中根据定位所需的时间长短对效率对比进行评价[16]。

图7 基于分步的位置指纹定位GUI界面

3.3 实验结果及分析

表1是离线训练阶段建立的数据库，其中1、2、3、4号位置点为粗粒度中心，每个粗粒度中心包括多个细粒度的数据点，例如1号粗粒度中心包括5、6、9、10共4个细粒度数据点。同理，由实验布置图可知其余的粗粒度中心及其包括的细粒度点。

表1 训练阶段建立的数据库

实验中阅读器的位置代表未知点的位置，依次将阅读器放在实验布置图中的21、22、23、24位置，多次测量求出其平均值。表2汇总了实验测得的未知点各个标签的信号强度值。

表2 未知点处各标签的信号强度

基于分步的位置指纹定位算法通过计算欧式距离，确定最小距离所在的点为粗粒度点，LANDMARC定位算法中计算出所有的欧式距离，选取最小的4个点来参与未知点位置的计算。表3为基于分步的位置指纹算法和LANDMARC定位算法所确定的参考点情况。

表3 未知点处所确定的参考点

采用式(4)来计算定位误差[17]

(4)

式中，(x,y)为实验测得未知点坐标，(x1,y1)为未知点实际坐标。

表4为基于分步的位置指纹定位算法与LANDMARC定位算法的定位结果对比，包括定位所需的时间及其定位精度。

表4 实验定位结果

根据表4可知，基于分步的位置指纹定位算法在保证定位精度与LANDMARC定位算法的定位精度相当的基础上，提高了定位效率。这是由于先粗略定位后精确定位的思想减小了较大一部分的数据计算量，有效避免了数据的冗余。而LANDMARC定位算法在未知点处测得各个标签的信号强度值之后，还需要与第一步建立的指纹库中的全部点进行匹配分析，众多的数据影响了算法的复杂度，而且在一一匹配分析时较多次数的计算也增加了定位结果出错的可能性。