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

2018 年第 31 卷第 11 期Electronic Sci. ＆ Tech. /Nov. 15，2018doi:10. 16180/j. cnki. issn1007 －7820. 2018. 11. 015 dianzikeji. org收稿日期:2017-11-28基金项目:上海市自然科学基金(13ZＲ1458500);上海市高校青年教师培养资助计划(1014204803)作者简介:杨勇明(1986 － )，男，硕士，实验师。研究方向:机器人技术、机电一体化。基于分步的位置指纹定位算法研究杨勇明(上海理工大学 公共实验中心，上海 200093)摘 要 针对 LANDMAＲC 室内定位算法产生数据冗余的问题，文中提出一种基于分步的位置指纹定位算法。离线训练阶段，通过合理布置粗粒度点与细粒度点建立位置与信号强度之间的指纹图，定位阶段，将实时测得的信号强度通过与指纹图对比进行粗定位和精定位。实验表明，分步的位置指纹定位算法在保证定位精度的同时，有效减少了数据计算量和传输量，满足定位的实时性要求，适用于室内定位等领域。关键词 分步;室内定位;信号强度;位置指纹;粗粒度;细粒度中图分类号 TP301. 6 文献标识码 A 文章编号 1007 －7820(2018)11 －060 －05Study on Positioning Algorithm Based on Step by Step Fingerprint LocationYANG Yongming(Pubilc Experiment Center，University of Shanghai for Science ＆ Technology，Shanghai 200093，China)Abstract Aiming at the data redundancy of LANDMAＲC indoor positioning algorithm，a positioning algorithmbased on step by step fingerprint location was proposed in the study． At the off － line training stage，fingerprint dia-gram between the location and the signal strength was established through reasonable arrangement of the coarse － grainpoint and the fine － grain point． At online positioning stage，the coarse positioning and fine positioning were meas-ured through the comparison between real － time signal strength and fingerprint diagram． Experiments showed thatstep by step location fingerprinting algorithm not only kept the positioning accuracy，but also reduced the amount ofcomputation and transmission of data． The algorithm met the real － time requirements of positioning and was suitablefor indoor positioning and other fields．Keywords step by step;indoor positioning;signal strength;fingerprint location;coarse － grain;fine － grain当今，高层建筑越来越多，在这些人口密集的场所，由于受到障碍物的阻挡，GPS 信号强度大大减弱，其定位精度远不及室外;而缺少室内地图，也导致了城市“盲区”的出现。

在人口密集的场所，诸如儿童看护、应急救援、商场导购等领域，对基于定位的服务［1］(Location Based Services，LBS)需求量越来越大。此外，物联网与智慧城市［2］ 概念的提出推动了室内定位技术及其应用市场的迅速发展。射频识别技术(ＲadioFrequency Identification，ＲFID)以非视距、非接触、多目标读写、可重复使用等优点［3］ 成为目前室内定位的首选技术。常用的室内定位算法主要包括基于测距的三边定位算法和基于非测距的位置指纹定位算法。由于受环境因素影响较小［4］ ，位置指纹定位算法成为诸多学者研究的焦点。LANDMAＲC 定位算法由文献［5］提出，是基于非测距的经典算法。1 传统 LANDMARC定位算法1. 1 LANDMARC定位算法LANDMAＲC 定位算法原理图［6］ 如图 1 所示，假设定位系统中有 m 个阅读器、n 个参考点标签、p 个未知点:第一步，令 θ r，j 表示第 r 个参考点标签在第 j 个阅读器上测得的信号强度值，其中 r =1，2，3，4，…，n，j =1，2，3，4，…，m;第二步，令 s i，j 表示第 i 个未知点在第 j 个阅读器上测得的信号强度值，其中 i =1，2，3，4，…，p;第三步，对未知点测得的信号强度与中对应参考点标签的 ＲSSI ((Ｒeceived Signal Strength Indica-tor))值进行关联程度计算，即进行 s i，j 和 θ r，j 相似度计算，以式(1)所示的信号强度均方差表示E i，r =∑mj =1(S i，j－ θr，j )槡2(1)0 6杨勇明:基于分步的位置指纹定位算法研究Electronic Science and Technology dianzikeji. org图 1LANDMAＲC 算法原理图E i，r 表示欧几里得距离 ［7］ ，根据式(1)，当未知点ＲSSI 值与中对应参考点标签的 ＲSSI 值接近时，表示未知点与参考标签的位置十分接近。

由于中有 n 个参考点标签，故将未知点与参考点标签一一进行相似度计算，并按照欧式距离的大小进行排序。为减小定位误差，通常选取距离最相近的 k 个参考点标签进行计算 ［8］ ，如式(2)所示，每个参考点标签坐标都要添加权值，权值的取值和欧式距离的大小有关。当未知点离参考点标签的实际位置较近时，权值较大;未知点与参考点距离较远时权值较小。w i =1E 2i，r∑mj =11E 2i，r(2)结合已知参考点标签的坐标，根据公式(3)进行未知坐标计算(x，y)= ∑ki =1w i (x i ，y i ) (3)式中(x，y)表示未知点的坐标，(x i ，y i )表示已知参考点标签的位置坐标。1. 2 LANDMARC定位算法冗余性分析LANDMAＲC 定位算法中，选定的 k 个参考点标签坐标决定了 LANDMAＲC 得定位精度。其余参考点坐标也参与定位过程，不仅增加系统的复杂度，也增加了错误的产生率，进而产生数据冗余现象 ［9］ ，导致系统效率和实时性下降，影响用户体验。针对此问题，本文提出基于分步的位置指纹定位算法。在离线训练阶段，进行粗粒度的定位(粗略定位)，确定未知点所在的区域，排除不可能的区域点;在定位阶段，进行细粒度的定位(精确定位)。

2 基于分步的位置指纹定位算法使用基于分步的位置指纹定位算法进行距离估算时，不依赖精确的室内传播模型，可以减小环境因素对定位精度的影响;此绕着粗粒度点呈放射状或者矩形状。基于分步的位置指纹定位算法原理图如图 3 所示。建立位置 － 信号强度指纹库［12］ ，在各个参考点处测得每一个标签的信号强度值，建立位置 － 信号强度指纹。

各个参考点接收到的信息按照标签 1、标签 2、标签 3、…、标签 n 的规律建立，例如共1 6Electronic Science and Technology杨勇明:基于分步的位置指纹定位算法研究 dianzikeji. org图 3 基于分步的位置指纹算法原理图有 m 个参考点，n 个标签，参考点的坐标为(x i ，y i )，第i 个参考点处接收到第 t 个标签的信号强度表示为ＲSS i，t ，则任意一个参考点在指纹库中表示为(x i ，y i ，ＲSS i，1 ，ＲSS i，2 ，ＲSS i，3 ……ＲSS i，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 远距离 ＲFID 阅读器和有源 ＲFID电子标签。基于 ＲFID 的应用主要分为标签的移动和阅读器的移动［13］ ，本次实验选择阅读器移动，该方法的优势是数量较多、价格较便宜的标签被放置在已知位置点，仅需使用一个阅读器即可完成，费用较低。实验开始前，检查笔记本与阅读器之间的通信连接状况，检查所有的有源标签的纽扣电子是否电量充足，定义实验中阅读器的位置代表未知点的位置。图 5 实际实验测试图图 5 为实际实验的测试图，图 6 为实验布置图。图 6 中按照如图所示的方式选定坐标原点，建立坐标系，布置好标签，图中每个小正方形的边长为 0. 6 m，实验选择的有源标签数量共计 4 个，用五角星表示。

离线训练阶段，需要建立的数据点用圆表示，并进行阿拉伯数字编号，有源标签点处需要进行数据点的测量，用于粗粒度点的建立。图 6 中，1 ～ 4 为有源标签的位置，放置在地板砖的中心位置，并且标签要竖直放置以便阅读器的天线与标签处于同一高度，保证阅读器更有效的接收标签信号强度。阅读器的位置代表未知点位置，当阅读器在 1 ～4 有源标签位置时，测得各个标签的信号强度基于指纹的定位算法。该条件下建立的点为粗粒度点，而粗粒度点也是部分细粒度点的中心。21 ～ 24 为未知点，1 ～ 20 为训练阶段建立位置信号强度时所需要测量的数据点。在此过程中有源标签的摆放位置要精确，有源标签的方向也要保持一致。阅读器在每个位置测量有源标签的信号强度时，若天线朝向始终保持一致，则可有效减小其它因素对实验结果的影响。3. 2 实验步骤(1)离线训练阶段。确定坐标原点后，依次把阅读器放在 1 ～20 号数据点处，阅读器的中心放置在地板砖的中心位置，在各点处阅读器的天线朝向保持一2 6杨勇明:基于分步的位置指纹定位算法研究Electronic Science and Technology dianzikeji. org图 6 无障碍物实验布置图致。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-103039-1.html