一种RFID标签定位改进算法

羊红光，邢亚斌，张 湃

（1.河北省科学院应用数学研究所，河北石家庄 050081；2.河北省信息安全认证工程技术研究中心，河北石家庄 050081；3.石家庄开发区冀科双实科技有限公司，河北石家庄 050081；4.石家庄工商职业学院建筑工程系，河北石家庄 050091；5.石家庄市第二中学，河北石家庄 050000）

一种RFID标签定位改进算法

羊红光1，2，3，邢亚斌4，张 湃5

（1.河北省科学院应用数学研究所，河北石家庄 050081；2.河北省信息安全认证工程技术研究中心，河北石家庄 050081；3.石家庄开发区冀科双实科技有限公司，河北石家庄 050081；4.石家庄工商职业学院建筑工程系，河北石家庄 050091；5.石家庄市第二中学，河北石家庄 050000）

通过分析用于室内定位的传统Monte Carlo算法存在的问题，对Monte Carlo定位算法更新模型进行了改进。改进算法具有更有效的采样、更强的稳定性、更少的计算量等优势。通过试验发现改进算法比传统算法具有更高的定位精度。

RFID定位；Monte Carlo算法；更新改进模型

典型的RFID室内定位系统主要由多个主动式应答器和阅读器组成。应答器在该系统中有两种功能：一种作为定位参考点，相当于信标的作用，一般称为参考点应答器；另一种是贴在被定位物体或人身上，称为被定位应答器。

RFID定位系统利用标签对物体的唯一标识特性，主要根据阅读器与安装在物体上的标签之间射频通信的信号强度（RSS）、信号到达时间差（TDOA）或信号到达时间延迟（TOA）来估计标签与阅读器之间的距离。基于RSS的距离估计需要大量的参考标签和阅读器以及较长的积累阶段，系统成本较高；基于TDOA的距离估计需要各阅读器之间保持同步，但在室内定位系统中，各阅读器之间的同步难以保证［1］；通过测量信号的到达时间延迟TOA来估计标签与阅读器之间的距离具有定位准确率较高、成本较低等优点。

国内外学者提出了多种TOA测量值定位算法，主要有泰勒展开、最小二乘、chan算法、多项式拟合、残差加权等［2－6］。这些算法中采用尽量接近有LOS路径时的测量值或增加算法对于含非视距（NLOS）误差测量值的鲁棒性进行处理，以达到克服NLOS误差的目的。

Monte Carlo定位方法利用随机数进行数值模拟，是由Metropolis在二次世界大战期间提出的，用于Manhattan计划研究与原子弹有关的中子输运过程。但传统的Monte Carlo定位算法存在两点缺陷：需要较多的采样点，占用计算资源多，不能进行实时定位；且难以定位运动中有停顿的物体［7－9］。因此，本文对传统Monte Carlo定位算法的更新模型进行了改进，使之更适合室内RFID标签定位需要的优越性能。

1 Monte Carlo定位算法原理

1.1 预测模型

在第k－1时刻，通过预测模型预测k时刻标签可能会出现的位置，即计算采样点的位置。假设室内噪声为高斯噪声，采用高斯分布的预测模型为：

在式（1）中，N（0，σ2）表示高斯分布；x（k），y（k）分别为横纵坐标；θ（k）为运动角度，方差为σθ；V（k）为标签的运动速度，方差为σV；dk为时间步长。

1.2 测量模型

假设RFID室内定位系统中阅读器的位置已知固定，标签移动。阅读器通过测距，即估计电磁波从标签到达自身的时间（TOA）来计算阅读器本身的位置及运动轨迹。

在第k时刻，测得标签与阅读器之间的距离，并计算出各采样点与阅读器的距离，通过测量模型计算出标签的位置。测量模型为：

其中，D K为k时刻采样点Sk所在位置到阅读器的计算距离值；Zk为k时刻测得的标签到阅读器的距离；δ为分布模型的标准差，其取决于距离测量的不确定度。

1.3 静止模型

当标签在运动的过程中停顿时，由k－1时刻和k时刻分别测得的标签到阅读器的距离，通过静止模型来判断标签是否停顿。静止模型为：

其中，Zk－1为k－1时刻测量到的标签到阅读器的距离；Zk为k时刻测量到的标签到阅读器的距离；δ为分布模型的标准差，取决于距离测量的不确定度。通过比较p（Zk｜Zk－1）与门限，大于门限时标签静止，否则标签运动。

2 传统的Monte Carlo定位算法

算法的思想是利用N个带有权重的离散采样C k＝｛，）｜i＝1，2，…，N｝表示后验概率密度分布p（X k｜Zk）。其中X k为标签在k时刻的状态，服从高斯分布Βel（X k）；Zk为阅读器从第1时刻到第k时刻的TOA测量值，Zk＝｛Zi，i＝1，2，…，k｝为标签k时刻的一个可能状态；≥0为权重参数，表示k时刻标签状态为的概率，且满足以下关系：

递归调用预测阶段和更新阶段，就能不断的更新带权重的样本集Ck，Ck中权重值最大的样本即为定位物体的当前位置。

在这个阶段，用带权重的采样点预测下一时间步长标签可能的位置，采样点越多预测会更准确，所以本算法需要大量的采样点。

3 算法更新模型改进

当阅读器获得测量数据Zk时，Monte Carlo定位算法将按下列方法对采样信息Sik（i＝1，…，N）操作：

这两项需要根据不同的情况来设计不同的区域。

如果一些采样被删除，算法会在区域B中自动增加新采样点。当采样点增加后，由于测量数据更新中采样分布会产生偶然偏差导致采样的不足以及估计的不稳定，所以区域B中的采样点可能会呈现发散状态。但样本密度与概率Bel（X）无关，因此应优先考虑计算速度，非严格的均匀分布。

4 改进算法分析

改进后的算法不需要很精确的概率模型，仅知道每个测量数据即可。如果不考虑权重计算，算法的迭代运算是固定的，更新改进模型只需判断测量数据更新后增删哪些采样点。改进后的Monte Carlo算法稳定性更强，对同一测量数据不会多次重复读取，避免处理和从前的信息相同的测量信息。

改进定位算法假设标签所在位置的概率服从均匀分布，减少了算法的计算量，降低了程序的复杂程度。

5 结论

本文介绍了Monte Carlo定位算法中用到的预测模型、测量模型、静止模型等三个模型，详细给出了传统Monte Carlo定位算法及其存在的问题。对Monte Carlo定位算法更新阶段进行了改进，改进算法具有更加有效的采样、更强的稳定性、更少的计算量等优势。通过试验发现改进算法比传统算法具有更高的定位精度。

［1］倪巍，王宗欣.一种室内无线网络多用户自适应定位及跟踪算法［J］.通信学报，2005，26（1）：66－73.

［2］W.H.Foy.Position location solutions by Taylor series estilnation［J］.IEEE Trans.Aerospace and Electronic Systems，1976，12（2）：187－194.

［3］M.K.Steven.Fundamentals of Statictical Signal Processing［M］.Estimation Theory，2003.

［4］邓平.蜂窝网络移动台定位技术研究［D］.西南交通大学博士学位论文，2002.

［5］M.P.Wylie，J.Holtzman.The non－line of sight problem in mobile location estimation［C］.Universal Personal Communications，1996，（2）：827－831.

［6］P.Chen.A non－line－of－sight error mitigation algorithm in location estimation［C］.Wireless Communications and Networking Conference，1999，（1）：316－320.

［7］D.Fox，W.Burgard，F.Dellaert.Monte carlo localization：Efficient position estimation for mobile robots［C］.In Proeeedings of the National Conference on Artificial intelligence，1999.

［8］张柱华，方华京.一种低计算量移动机器人自定位方法［J］.计算机与数字工程，2005，33（7）：53－57.

［9］林敏.RFID标签定位技术研究［D］.江苏大学，2007.

An modified RFID localization algorithm

YANG Hong－guang1，2，3，XING Ya－bin4，ZHANG Pai5

（1.InstituteofAppliedMathematics，HebeiAcademyofSciences，ShijiazhuangHebei050081，China；2.HebeiAuthenticationTechnologyEngineeringResearchCenter，ShijiazhuangHebei050081，China；3.SJZJKSSTechnologyCo.，Ltd，ShijiazhuangHebei050081，China；4.DepartmentofArchitecturalEngineering，ShijiazhuangVocationalCollegeofIndustryandCommerce，Shijiazhuang050091，China；5.TheSecondMiddleSchoolofShijiazhuangCity，ShijiazhuangHebei050000，China）

In this paper，problem existing in the Monte Carlo localization algorithm in the indoor is analyzed，the renewal model of Monte Carlo localization algorithm is improved.Compared to the Monte Carlo localization algorithm，modified algorithm has advantages in effective sampling，greater stability and less computational.From test and analysis，the modified algorithm has higher Positioning precision than the Monte Carlo localization algorithm.

RFID localization；Monte Carlo algorithm；Improved renewal model

TP311.52

：A

1001－9383（2011）04－0053－04

2011－06－30

羊红光（1979－），男，河北邯郸人，硕士，研究方向：物联网应用、信息安全技术.