改进的RFID室内定位算法

段本亮，李建雄，陈明省，毛陆虹

（1.天津工业大学 电子与信息工程学院，天津 300387；2.天津大学 电子信息工程学院，天津 300072）

近年来，随着移动通信技术、无线技术的飞速发展，更多的应用需要确定物体的位置信息，定位技术越来越受到人们的关注.根据环境的不同，定位可以分为室外定位和室内定位.目前最常用的室外定位误差主要有卫星定位和蜂窝网定位技术2种，其定位方法都在米数量级，在室外环境中可以较好地满足用户需求，然而建筑物的屏蔽作用令其室内定位精度大打折扣，而且高昂的成本使其直接应用于室内环境也存在困难.为了更好的实现室内定位，必须采用新的方法与技术.目前较常用的室内定位技术主要有超声波、红外线、蓝牙、超宽带（UWB）和射频识别（RFID）[1].红外线和超宽带定位技术造价昂贵、系统复杂；蓝牙定位技术定位精度较差；而RFID技术以其非接触、非视距、成本低且定位精度高等优点，逐渐成为了室内定位领域的优选技术，被业界公认为是本世纪最有价值的应用技术之一[2-4].RFID定位系统一般由阅读器、标签和应用软件系统3部分组成，通过检测到的标签反射回来的信号强度来表征阅读器与标签之间的几何距离，是一种基于接收信号强度指示（received signal strength indicator，RSSI）的定位技术[5].本文首先介绍现有的2种基于RFID的室内定位算法即RSSI线性定位算法和LANDMARC算法，分析其优缺点，结合2种算法给出了改进的RFID室内定位算法，并进行了仿真分析和总结.

1 RSSI线性定位算法

1.1 传播路径信号损耗模型

基于理论和测试的传播路径模型指出，经过多径信道接收到的信号强度一般服从对数正态分布.常用的对数距离路径损耗模型遵从公式[6]:

式中:P（d）表示经过距离 d 后的路径损耗值；P（d0）表示经过距离d0后的路径损耗值，d0为参考距离，一般取值为1 m；n表示路径损耗指数，表示路径损耗随距离增长的速率，它主要受周围环境和建筑物的影响，取值范围一般为2～4；Xσ是均值为0、标准差为δ的高斯分布随机数，δ的范围一般为4～10.

路径损耗P（d）与阅读器接收到的信号强度Pr（d）及系统发射功率Pt之间存在以下关系:

为了得到阅读器接收到的信号强度与距离之间的关系，将式（1）代入式（2），整理可得对数距离路径损耗模型的另一表达式:

式中:Pr（d）表示阅读器在距离标签d时接收到的信号强度，即RSSI，单位为dBm；Pr（d0）表示阅读器在参考点d0时接收到的信号强度.本文采用式（3）对阅读器接收到的RSSI进行处理得到距离关系.

1.2 RSSI线性定位算法

通过硬件设施完成信号的接收及信号强度的测量，根据上述建立的传播路径信号损耗模型计算出各个阅读器与待定位标签之间的距离，然后根据距离方程组使用最小二乘法便可计算出待定位标签的坐标.假设共有n个阅读器，坐标分别为（xi，yi），（i=1，2，…，n），各个阅读器与待定位标签之间计算出的距离为di，待定位标签的坐标为（x，y），所列出的距离方程组如下:

将方程组的前（n－1）个方程分别减去第n个方程，从而达到把二次方程线性化的目的，得到下列方程组:

则（5）式可写为:

用最小二乘法（LS）求解可得:

向量θ里的元素即为计算出来的待定位标签的坐标值（x，y）.

RSSI线性定位算法[7]是目前最常用的室内定位算法之一，其原理简单，数据处理量小，系统实时性好.当然RSSI线性算法也存在着一些不足，最大的缺点就是定位精度不是很高，要想进一步提高定位精度，就需要增加阅读器的数目，从而导致成本的提高.根据文献[8]所述，阅读器与标签距离越远，测距误差就越大.由此可知，当定位边缘区域的标签距离个别阅读器较远时，测距误差较大，从而定位误差变大，甚至有时无法实现定位.所以非常有必要对此算法进行改进，解决边缘区域定位差的问题，从而使该算法更具有适用性.

2 LANDMARC算法

LANDMARC （location identification based on dynamic active rfid calibrarion）定位算法[9]是一种经典的基于有源RFID系统的室内定位算法，设计思想是采用固定参考标签辅助定位，通过待定位标签的信号强度值与参考标签的信号强度值之间的比较，采用“最近邻居”权重思想，计算出定位标签的坐标.LANDMARC算法具有较高的定位精度，可扩展性好，能处理比较复杂的环境，是一种非常实用的定位算法.

假设有n个阅读器、m个参考标签和u个待定位标签.待定位标签的坐标为（xi，yi），（i=1，2，…，u）.阅读器分别读出所有参考标签和待定位标签的场强值.待定位标签坐标求解过程如下:

（1）定义待定位标签的信号强度矩阵S:

式中:Sij（i=1，2，…，u；j=1，2，…，n）表示第j个阅读器读取到第i个待定位标签的信号强度.定义参考标签的信号强度矩阵θ:

式中:θpj（p=1，2…，m；j=1，2…，n）表示第j个阅读器读取到第p个参考标签的信号强度.

定义待定位标签与参考标签的欧几里德距离矩阵E:

Eip越小说明它们之间的距离越近.

（2）为了计算出待定位标签的坐标，人为地选择k个参考标签，其坐标记为（x'r，y'r）（r=1，2，…，k），这些参考标签与待定位标签i的欧几里德距离是（Ei1，Ei2，…，Eim）中最小的k个值，记为E'ir（r=1，2，…，k）.待定位标签i的坐标可以通过这k个参考标签的坐标及其权重得到

式中:ωir为待定位标签i的第r个邻居参考标签的权重（r=1，2，…，k），距离越近的标签所占的权重越大.ωir可根据经验公式得到:

（3）定义估计误差:通过比较待定位标签的估算坐标与实际坐标，可以计算出他们之间的误差值:

式中:（xi，yi）为估算的待定位标签坐标位置；（xi0，yi0）为待定位标签的实际坐标位置.

LANDMARC算法具有以下3个方面的优势:

（1）采用多个廉价的参考标签代替了昂贵的阅读器，降低了整个定位系统的成本；

（2）待定位标签和参考标签处于同样的环境中，环境因素的影响可以很大程度地抵消；

（3）定位精度较高.

但是，它也有一些不足之处:

（1）定位精度与参考标签密度有关，要想获得更高的定位精度，必须布置更多的参考标签，一方面增加了系统成本和标签布局难度，另一方面太多的参考标签还会造成标签之间的信号干扰；

（2）该算法在确定邻近参考标签时，需要计算所有的参考标签与待定位标签之间的欧几里德距离，从而会导致大量的不必要的计算而影响定位实时性.

3 定位算法的改进

3.1 改进方法

RSSI线性定位算法的定位误差虽然比LANDMARC算法要大一些，但其不需要布置大量的参考标签，既可以节省一部分成本，又避免了特殊空间难以布置参考标签的问题，所以在精度要求不太高的场合仍有着较大的应用价值.由前文分析可知RSSI线性定位算法边缘区域定位误差较大，所以本文借鉴LANDMARC算法定位精度较高的优势，在定位边缘区域布置少量参考标签，并在布置参考标签的区域采用LANDMARC算法，而其他区域仍采用RSSI线性定位算法.这样不仅解决了RSSI线性定位算法边缘区域定位误差大的问题，而且相比整个区域全部使用LANDMARC算法降低了一些成本，减少了算法运行时间.该算法流程图如图1所示.

图1 改进算法流程图Fig.1 Improved algorithm flow chart

3.2 仿真与分析

在路径损耗指数n=2.2、标准差δ=5的环境下，按照图2（a）所示位置在20 m×20 m的空间边缘区域放置68个参考标签，参考标签间距为2 m，4个阅读器位于空间边界的角上，并在定位区域设置10个待定位标签.图2（b）除了没有放置参考标签以外，其它条件与图2（a）相同.图2（c）是在所有的区域都放置上参考标签，总数为117个，其它条件与图2（a）和图2（b）完全相同.

由图 2 可知，待定位标签 Tag1、Tag2、Tag3、Tag4、Tag5、Tag6、Tag7位于边缘区域，待定位标签 Tag8、Tag9、Tag10位于非边缘区域.

采用MATLAB数学软件分别对RSSI线性定位算法、LANDMARC算法和本文改进算法仿真50次.定义计算出来的待定位标签的坐标为（xt，c，yt，c）（t=1，2，…，10；c=1，2，…，50），待定位标签的实际坐标为（xt，y）t（t=1，2，…，10），计算出来的坐标与实际坐标的欧式距离为et，c=（t=1，2，…，10；c=1，2，…，50）.利用每个待定位标签的平均误差=（t=1，2，…，10）和所有标签的平均误差=（t=1，2，…，10）评估本文提出的算法性能，结果如图3所示.

图2 不同算法情况下的阅读器与标签布局图Fig.2 Reader and Tag layout diagram on different algorithms

图3 标签定位误差对比图Fig.3 Tag positioning error comparison diagram

由图3可知，相对于RSSI线性定位算法，采用改进算法后，边界待定位标签 Tag1、Tag2、Tag3、Tag4、Tag5、Tag6、Tag7的定位误差得到了显著下降，精确度得到有效提高.7个边界待定位标签的估计误差与RSSI线性算法相比降低了35.8%～60.4%.使用RSSI线性定位算法、LANDMARC算法和本文改进算法时的所有标签平均定位误差分别为1.97、1.23、1.25，由此可见本文改进算法与LANDMARC算法的定位精度非常接近.3种算法相比较，RSSI线性定位算法用时0.004398 s，LANDMAR算法用时0.040603 s，改进算法用时0.029161 s.RSSI线性定位算法定位误差最大，但用时最少，LANDMARC算法比改进算法的定位精度稍高，但算法执行时间更长，并且需要更多的参考标签，所以改进的算法相比LANDMARC算法而言实时性更好，成本更低一些.

4 结束语

本文提出的改进算法在没有增加太多成本的基础上解决了RSSI线性定位算法在边缘区域定位精度差的问题，提高了整体系统的定位精度，扩大了该算法的适用范围.由于该算法只是在边缘区域布置参考标签，所以与LANDMARC算法相比，减少了参考标签的使用数目进而降低了系统成本和减小了系统布局的难度.由于该算法只是在边缘区域才使用LANDMARC算法，所以算法计算量比单纯使用LANDMARC算法减少了许多，从而提高了系统的实时性.在定位精度要求不太严格的场合，该改进算法有很大的使用价值.

[1]张文锦，李建雄，毛陆虹.基于多波束切换的便携式RFID阅读器设计 [J].天津工业大学学报，2013，31（1）:52-56.

[2]SHIRAISHI T，KOMURO N，UEDA H.Indoor location estimation technique using UHF band RFID[C]//Information Networking，2008 International Conference.Busan:[s.n]，2008:1-5.

[3]SHIH S，HSIEH K，CHEN P.An improvement approach of indoor location sensing using active RFID[C]//Innovative Computing，Information and Control，2006 First International Conference.Beijing:[s.n]，2006:453-456.

[4]DAI H，SU D.Indoor location system using RFID and ultrasonic sensors[C]//Personal，Indoor and Mobile Radio Communications，2006 IEEE 17th International Symposium.Kunming:[s.n]，2006:1179-1181.

[5]陈永光.基于信号强度的室内定位技术[J].电子学报，2004，32（9）:1456-1458.

[6]杨大成.移动传播环境理论基础、分析方法和建模技术[M].北京:机械工业出版社，2003.

[7]顾宗海.基于RSSI测距的室内定位算法研究[D].郑州:郑州大学，2011.

[8]黄涛.物联网短距离定位算法研究 [D].大连:大连理工大学，2011.

[9]NI L，LIU Y，LAU Y，et al.LANDMARC:Indoor location sensing using active RFID [C]//Proceedings of the First IEEE International Conference on Pervasive Computing and Communications（Per-Com2003）.Dallas:[s.n]，2003:407-415.