基于RFID的边界虚拟参考标签定位算法.doc

2011 年 3 月march 2011计算机工程computer engineering第 37 卷第 6 期vol.37no.6开发研究与设计技术文章编号：10003428(2011)06027403文献标识码：a中图分类号：tp391基于rfid的边界虚拟参考标签定位算法俱 莹，刘开华，史伟光，闫 格(天津大学电子信息工程学院，天津 300072)摘 要：介绍 vire 室内定位算法的原理，针对 vire 算法对边界标签定位准确度低的问题，提出边界虚拟参考标签定位算法 bvire。该算法通过建立线性回归方程，在边界处加入边界虚拟参考标签。仿真结果表明，在不额外增加参考标签且不增大射频干扰的前提下，bvire算法较原算法使靠近边界处待定位标签的定位准确度得到较大提高。 关键词：bvire 算法；线性回归方程；射频识别；室内定位boundary virtual reference tags location algorithmbased on rfidju ying, liu kai-hua, shi wei-guang, yan ge(school of electronic information engineering, tianjin university, tianjin 300072, china)【abstract】this paper introduces the principle of vire algorithm for indoor location. for the positioning accuracy of boundary tags in virepositioning algorithm is low, bvire algorithm is proposed by using boundary virtual reference tags. bvire algorithm inserts some virtual reference tags on the boundary of the indoor environment by establishing a linear regression equation. simulation results show that, bvire algorithm improves the positioning accuracy of boundary tags significantly without adding extra reference tags and radio frequency interference compared with vire algorithm.【key words】bvire algorithm; linear regression equation; rfid; indoor locationdoi: 10.3969/j.issn.1000-3428.2011.06.095边界，16 个参考标签按照网型排列布设于待定位区域。vire方法的核心思想是将每 4 个参考标签看做一个单元网格，再 将其进一步等分为 nn 个小网格，在小网格处加入网格虚拟 参考标签，见图 2，虚拟参考标签均匀等间隔分布于单元网 格中。由于实际参考标签的位置坐标已知，因此网格虚拟参 考标签的坐标亦能方便算得，相当于增加了大量参考标签。1 概述近年来，随着无线技术、移动计算以及射频识别(rfid)技术的飞速发展，室内定位技术越来越受到人们的关注1-3。 基于有源射频识别校验的动态定位技术(landmarc)4 以 其方法简单、准确度较高的特点被广泛应用，作为室内定位 算法的理论基础发展出了很多更为准确的定位算法。文献5在 landmarc 算法的基础上，加入网格虚拟参考标签，通过比较去除冗余位置信息，实现更准确的定位。但是 vire 算法存在边界附近标签定位准确度低的不足，若在边界处加 入实际参考标签，会大大增加系统成本。为提高边界标签的 定位准确度且不增加系统成本，本文提出 bvire 算法，即在 边界处加入虚拟参考标签的算法。2 vire 算法简介vire 系统阅读器和标签分布如图 1 所示。图 2 网格虚拟参考标签分布另外，为提高定位准确度，在对 landmarc 权重改进 的基础上，引入 2 个权重因子 w1i 和 w2i 。w1i 用来表征选出的 邻近参考标签与待定位标签的信号强度(rssi)差值，差值越基金项目：国家自然科学基金资助项目“情境感知服务位置信息获取机理与算法”(60872001)作者简介：俱 莹(1986)，女，硕士研究生，主研方向：无线定 位算法，无线传感器网络；刘开华，教授、博士生导师；史伟光、 闫 格，博士研究生图 1 vire 系统阅读器和标签分布在图 1 所示的环境布局中，4 个阅读器置于待定位区域收稿日期：2010-08-21e-mail：第 37 卷 第 6 期俱 莹，刘开华，史伟光，等：基于 rfid 的边界虚拟参考标签定位算法275小， w1i 越大。 w2i 用来表征优选出的邻近参考标签的密度，密度越大， w2i 越大。考标签的 rssi 值，则边界虚拟标签就和实际参考标签具有了一样的参考价值。当实际参考标签的位置和 rssi 值变化 时，边界虚拟参考标签位置和 rssi 值可实时更新，具备良 好的环境适应性。具体做法如下：kw = 1(1)1ik =1 k sk (ti )s = + xnci(6)0 1w =(2)2ina其中， ncii=1其中， nci 表示与邻近参考标签 i 连接在一起的区域的个数，na 表示整个室内待定位区域内选出的邻近参考标签的数量。综合考虑 w1i 和 w2i ，得到权重为：n n xi si nxs ( xi x )(si s )= i=1= i=1(7)1n n x 2 nx 2 ( x x )2iii=1i=1= s x(8)wi = w1i w2i则待定位标签的坐标值可通过下式计算得到：01(3)以图 4 中第 1 行标签 t1 、t2 、t3 、 t4 为例，假设这 4 个标签在阅读器 r1 上的 rssi 值分别为 s11 , s12 , s13 , s14 ，将它们( x, y ) = i=1 wi ( xi , yi )na(4)的坐标值和 rssi 值 ( x1 , s11 ), ( x2 , s12 ), (x3 , s13 ), ( x4 , s14 ) 代入式(7)、定义理论得到的待定位标签坐标与实际坐标之间的估计误差为：式(8)求出一组 0 、1 值，根据式(6)和 tb1 标签的横坐标 xb1 可求得它在阅读器 r1 上的 rssi 值 s1b1 。22e = ( x x0 ) + ( y y0 )(5)s1b1 = 0 + 1 xb1其中， ( x0 , y0 ) 表示待定位标签的实际坐标。vire 方法与 landmarc 方法的定位误差比较见图 3。(9)同理可得其在另外 3 个阅读器上的 rssi 值。左边和右边的 8 个边界虚拟参考标签的 rssi 值均可由以上几个式子求 得。上边和下边的 8 个边界虚拟参考标签则可通过纵坐标 y 建立线性回归方程，方法同上。(2)网格虚拟参考标签的加入 将边界虚拟参考标签布设计算完毕之后，开始计算 nn的网格处的虚拟参考标签的坐标值和 rssi 值，如图 2 所示，在每 4 个参考标签或边界虚拟参考标签组成的单元网格中均匀等间距加入网格虚拟参考标签，则每个单元网格中将会被 加入 ( n + 1)2 4 个网格虚拟参考标签。相当于增设了许多实 际参考标签，细化了单元网格中的传播环境，可以有效减弱landmarc 定位系统中由多径效应而引起的估计误差6。基于简化复杂度考虑，采用线性插值算法计算它们的坐标和rssi 值。 (3)邻近参考标签的选取 经过以上步骤已得到所有参考标签(包括实际参考标签、边界虚拟参考标签、网格虚拟参考标签)的位置坐标和 rssi图 3 vire 方法与 landmarc 方法的定位误差比较可以看出，vire 方法的误差得到了有效改善。但是，观 察可知，靠近边界处的待定位标签相较于其他待定位标签， 定位误差较大，下面主要针对这一问题提出了改进方法。3边界虚拟参考标签定位算法 bvire本文提出边界虚拟参考标签定位算法 bvire，具体步骤如下：(1)边界虚拟参考标签的引入。边界虚拟参考标签位置分 布如图 4 所示。值。另外，各阅读器中均已获得所有待定位标签的 rssi 值。将参考标签和待定位标签在每个阅读器上的 rssi 值进行比较求绝对差值，差值越小说明和待定位标签的位置越近。 建立模糊地图5，以参考标签为中心将整个区域划分为一定数量大小相等的区域。选取一定的阈值，将绝对差值小于该阈值的位置置 1，大于该阈值的位置置 0。对于每个待定 位标签来说，k 个阅读器上可形成 k 个模糊地图，将各模糊 地图取交集得到最终优选出的邻近参考标签，即 k 个模糊地 图上都置 1 的位置，去除冗余位置信息。4 仿真与分析在路径损耗指数 n=2.2 的环境下7，按照图 1 所示位置在 4 m4 m 的空间布设 16 个参考标签，参考标签间距为 1 m，4 个阅读器位于空间边界，并放置 9 个待定位标签。如图 4所示加入边界虚拟参考标签，并等间隔加入网格虚拟参考标 签。使用 matlab 软件对算法进行仿真。图 5 为 bvire 算法 与原 vire 算法定位误差的对比，其中，间隔数 n=30；阈值 th=1。由图 5 可知，相对于 vire 算法，采用 bvire 算法后， 边界待定位标签 tag6、tag7、tag8、tag9 的估计误差得到了图 4 边界虚拟参考标签位置分布本文引入 16 个边界虚拟参考标签，由原参考标签的坐标 值易求得边界虚拟参考标签的坐标值。另外，根据原参考标 签的信号强度(rssi)值建立线性回归方程，得到边界虚拟参sk (ti ) - sk (r)276计 算机 工 程2011 年 3 月 20 日显著下降，准确度得到有效提高。4 个边界待定位标签的估计误差相较 vire 算法降低 42.5%61.9%，边界标签平均估 计误差降低 49.8%。9 个待定位标签中，最大的估计误差为0.206 7 m，平均估计误差较 vire 算法提高 39.4%。n=30 较 n=20 时定位准确度有较大提高，但当 n=40 时准确度并没有显著提高。基于运算复杂度的考虑，选取 n=30。5 结束语针对 vire 定位算法对边界标签的定位准确度不高的问题，本文提出了边界虚拟参考标签算法 bvire，该算法通过 建立线性回归方程，在边界处插入边界虚拟参考标签，采用 线性插值法加入网格虚拟参考标签，去除冗余位置信息，求 出待定位标签的位置坐标。仿真结果表明，与 vire 算法相 比，本文算法的准确度较高。下一步将研究如何将 bvire 算 法应用到三维定位中，以解决三维室内环境下的边界标签定 位问题。参考文献1hightower j, borriello g. location systems for ubiquitous com-putingj. computer, 2001, 34(8): 57-66.liu hui, darabi h, banerjee p, et al. survey of wireless indoor positioning techniques and systemsj. ieee trans. on systems, man, and cybernetics iii, 2007, 37(6): 1067-1080.vossiek m, wiebking m, gulden l. wireless local positioning concepts, solutions, applicationsc/proc. of ieee wireless communication and networking confenrence. new orleans, usa: s. n., 2003.lionel m n, liu yunhao, lau y c, et al. landmarc: indoorlocation sensing using active rfidj. wireless networks,2004, 10(6): 70l-7l0.zhao yiyang, liu yunhao. vire: active rfid-based localization using virtual reference eliminationc/proc. of international conference on parallel processing. xian, china: s. n., 2007.stallings w. wireless communications and networksm. 北京:电子工业出版社, 2006.杨大成. 移动传播环境理论基础、分析方法和建模技术m.北京: 机械工业出版社, 2003.张 佳, 罗军勇, 王 艳, 等. 改进的无线传感器网络定位算 法j. 计算机工程, 2009, 35(6): 133-135.编辑 顾姣健2图 5 bvire 算法与 vire 算法的定位误差比较图 6 为不同的间隔数 n(即网格虚拟参考标签的密度)对bvire 算法定位误差的影响8。34567图 6 网格虚拟标签密度对定位误差的影响由于加入的是虚拟标签，密度增大不会带来额外的开销。 理论上虚拟参考标签的密度越大，定位越准确。但当 n 的值 高于一定数量时，准确度将不会进一步改善。观察图形可得，8(上接第 273 页)(3) 验证了文献2 提出的无向双环网络 g(n; r, s) 的直2bermond j c, comellast f, hsu d f. distributed loop computernetworks: a surveyj. parallel and distributed computing, 1995,24(2): 2-9.wong c k, coppersmith d. a combinatoria