基于统计平滑处理的单标签RFID数据清洗改进算法

饶晶晶

摘要：在RFID应用过程中，基于统计平滑处理（SMURF）的窗口自适应算法相比静态窗口算法可以大大改善清洗数据的效果，但是当阅读器在其与标签的动态移动环境下发生漏读现象时，该算法中的跃迁检测机制不能合理使清洗窗口大小自适应调整，从而导致消极读错误的大量产生；针对以上问题，本文在原算法的基础上提出改进，把清洗窗口平均分成子窗口1和子窗口2，将个阅读周期内在窗口中观测到标签的概率差值以及在子窗口2中标签被观测到的值作为判断标签是否发生跃迁的条件，使得原算法中的跃迁检测准确度提高，实现对移动单标签数据更有效的清洗。经实验验证：在移动环境中，该算法相比SMURF原算法能获得更好清洗效果。

关键词：RFID数据清洗；SMURF；自适应窗口；跃迁检测；

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）15-0237-04

Abstract：In the process of RFID application， the adaptive window algorithm based on SMURF can greatly improve the effect of data cleaning compared to static window algorithm， but the algorithm does not consider the dynamic mobile environment between tags and reader， if the reader missing the tags， the transition detection mechanism of this method will cause the cleaning window size can not reasonably and adaptively regulate， also will produce lots of false negative； In view of the above problems， this paper put forward the improvement based on the original algorithm， the average divideinto sub-windows of number one and sub-window of number two， use the observed valuein the number two of tagand the observed probabilitiesin the windowas the tag transition conditions， improved the tags transition detection accuracy of the original algorithm， and more effective to realize mobile single tag data cleaning. By experimental verification： In the mobile environment， the improved algorithm have better cleaning effect than SMURF.

Key words：RFID data cleaning； SMURF； adaptive window； transition detection

1 引言

射频识别 （Radio Frequency Identification，RFID）技术是利用射频通信原理实现非接触式的自动识别技术。在实际应用过程中，阅读器在其阅读范围内一旦识别到带有标签的物品经过时，就会自动且无接触的从标签中获取相应信息，识别物品或者实现自动收集物品信息的功能。目前阻碍RFID技术广泛应用的主要原因之一，就是原始数据获取的不准确，有时准确率仅为60%～70%，即阅读器漏读了30%～40%的数据[1]。 为了有效地支持RFID上层业务的逻辑处理，目前普遍采用的方法就是清洗原始数据。

在RFID应用过程的数据清洗技术中，有三种有效的方法可以提高RFID数据可靠性：硬件解决方案、中间件解决方案以及存储器解决方案。硬件解决方案着重提升包括阅读器和标签设备在内的硬件性能，如使用多个标签和阅读器来准确获取同一个物品的物理信息[2-4]。中间件解决方案主要在RFID原始数据未进入到数据库[5-7]之前，使用各种清洗算法对RFID原始数据进行清洗，从而到达数据可靠。而存储器解决方案是在数据存储过程中采用智能化控制技术对RFID不可靠数据进行修正[8-9]。基于中间件解决方案的简单与实用性，这一种解决方案已经成为保证RFID数据可靠性的主要研究热点，比较典型的方法有基于静态滑动窗口清洗方法和基于管道RFID数据清洗模型ESP。

对于静态窗口清洗方法[10]，这种清洗方式简单易行，但是错误率较高，在标签移动过程中固定的滑动窗口不会在系统的整个生命周期保持有效；管道RFID数据清洗模型[11]其在绝大多数的RFID应用系统中，都能有效处理冗余数据和大部分的错误数据，但不能理想的动态性追踪标签；而Jeffery等人为了解决管道RFID数据清洗模型中所选时间粒度（即清洗窗口大小）的不恰当，造成更多的积极读错误（阅读器认为已经离开阅读范围的标签仍然在其阅读范围之内）或消极读错误（标签没有离开阅读范围，但是被误解为已经出了阅读器的阅读范围）的问题，提出统计平滑处理方法SMURF[12]，该方法的窗口大小随着系统生命周期中RFID观测数据的改变，从而自适应调整；但是该方法忽略了单标签的空间粒度多变环境，当阅读器在动态移动中发生漏读，方法中的跃迁检测机制不能合理调整清洗窗口的自适应大小，并且使消极读错误大量产生。

本文对RFID数据清洗技术进行了深入研究，针对基于统计平滑处理（SMURF）的RFID数据清洗算法没有充分考虑到阅读器在其与标签的动态移动环境下发生漏读现象时，该算法中的跃迁检测机制不能合理使清洗窗口大小自适应调整，从而导致消极读错误大量产生的问题，提出把清洗窗口平均分成子窗口1和子窗口2，将个阅读周期内在窗口中观测到标签的概率差值以及在子窗口2中标签被观测到的值作为判断标签是否发生跃迁的条件，使原算法中的跃迁检测准确度提高。

2 基于统计样本的RFID数据流建模

本文提到的标签跃迁是指标签从阅读器阅读范围之内移动到阅读器范围之外后，RFID实际理想数据中的空白部分（见图1）。

在典型的RFID中间件解决方案中通常采用平滑窗口来清洗RFID数据流，但是窗口大小的调整需满足以下两种对立的应用要求：标签阅读的完整性和获取标签的动态变化。如图1所示。

（1）完整性（Completeness）：由于小窗口的清洗容易产生消极读，丢失某些标签信息。因此必须保证有足够大的清洗窗口，能够在阅读器阅读范围内有效的读取到所有标签的信息，避免数据丢失。当然，周围环境、标签的种类以及阅读器的种类和阅读率都会影响窗口的大小，从而影响阅读器读取数据的完整性。

（2）标签动态性（Tag Dynamics）：大窗口清洗虽然可以避免产生消极读错误，但同样不可避免的会出现阅读器错误的认为已经远离其阅读范围的标签仍存在于读取范围内，导致积极读错误产生。最糟糕的是，某些标签在离开阅读范围后又被放回阅读区间，但是由于窗口过大，阅读器无法正确判断标签的真实移动，从而在标签移动状态检测上出现问题。为了保证标签的动态性，我们需要了解标签的移动特点和应用领域。

在RFID应用过程中，当被附着标签的对象进入阅读器的阅读范围内时，就会产生一个RFID信息，但是标签与阅读器之间的动态移动环境下，阅读器读取的标签信息并不能保证连续；同时，标签与阅读器之间的距离也影响到标签被读取的概率，由于距离限制了阅读器发射的射频信号，所以标签想要被读取就要离阅读器近，反之离阅读器的阅读范围越远的标签就难以被成功读取到。因此基于统计平滑处理（SMURF）的RFID数据清洗算法对抽象的统计样本（阅读器读取的RFID数据信息）进行建模，利用样本理论，根据RFID数据的观测值驱动滑动窗口在系统的整个生命周期内，都能够连续地自适应调整自己的大小。

查询周期是单标签情况下，RFID阅读器与标签通信的基本时间单位，它包括两部分： 阅读器将射频信号发送给标签、标签接受到信号后发送应答给阅读器。为了增加RFID数据的可靠性，通常一个阅读周期由多个查询周期组成。用表示单位阅读周期，。

一个阅读周期内阅读器能读到的标签总数用表示，而一个阅读周期内被成功读取的标签数用表示，则一个阅读周期内标签的读取概率即为：

但是当标签信息漏读现象，发生在阅读器阅读范围之内的标签相对阅读器动态移动时（图3蓝线区间），也会使窗口条件满足情况1条件。这样就会使原算法错误地认为标签信号在当前窗口内发生了跃迁，而过大的窗口调整会产生更多的消极读。

针对情况1，本文提出规则1对当前清洗窗口大小进行适度调整，以满足清洗要求。

规则1：当且满足式（4）时，调整当前清洗窗口为；

情况2：改进算法为了更加准确的实现标签信号跃迁检测，提出规则2，引入窗口内个阅读周期观测到标签的概率差值和作为标签是否处于阅读器阅读范围之内的判断条件。

规则2：当在窗口内且，调整当前清洗窗口调整为原窗口的，也就是。

3.2 算法实现

为了减少RFID数据出现的积极读错误，同时平衡清洗窗口的平滑性，设置一个阅读周期为滑动窗口每次向前滑动的距离，为最小的清洗窗口值。将清洗窗口的中间时间节点作为标准，若滑动窗口内的数据在一个阅读周期内满足输出条件，即可输出数据。单个标签的改进算法如表1所示。

4 实验验证

测试环境如图4所示：

测试环境平台和软件：

测试平台：Microsoft Visual Studio 2010

数据库工具：Microsoft SQL Server 2008

数据生成的语言：C#

串口参数：

波特率：9600

数据位：8位

停止位：1位

校验位：无

现有的RFID数据清洗技术广泛采用模拟数据进行实验分析，为了验证本文所提出的改进算法，现数据模拟场景如下：固定一个阅读半径4.6m，最大阅读率为95%的阅读器，让单标签在阅读器阅读范围内外的任意位置以随机速度（）变化移动。根据模拟场景，当有符合条件的数据（图6中RFID原数据）PC1就会自动生成并且储存在自己的数据库表格中。

由于一个阅读周期中还包含标签给阅读器的应答，因此每隔一个周期PC2会得到一条由PC1从数据库中通过串口发送的标签数据，PC2会执行完整性置信度的清洗算法，处理得到的标签数据，保存记录最终数据以作分析。简单构建标签信息数据格式如图5所示，以模拟阅读器有无读取到随机速度的标签：

B1位：标签未被读取即为0，标签被读取即为1；A1～A7：标签的移动速度，0～90随机数。

由图6可知，当标签在阅读器阅读范围内动态移动而发生阅读器漏读标签信息时，改进算法能够更加合理的使清洗窗口大小自适应调整，从而使得清洗的数据更加接近实际理想数据，并且能够更准确地动态判断标签信号跃迁检测。这种与实际数据相比，清洗效果明显优于SMURF原算法的改进算法在性能上整体实现了提升。

由图7可知，相较于SMURF原算法，改进算法在标签以随机速度变化移动过程中，减少了积极读错误的产生；但是却增加了消极读错误，因为改进算法中进行数据处理的清洗窗口会比原算法的小，因而标签跃迁检测机制检测不到清洗窗口。

5 结论

本文分析比较了几种经典的数据清洗技术，并且对基于统计平滑处理的RFID数据清洗技术进行了深入研究，针对阅读器在动态移动环境下发生标签信息漏读现象，该算法中的跃迁检测机制不能合理使清洗窗口大小自适应调整，导致消极读错误大量产生；为此，本文提出改进算法，利用个阅读周期内在窗口观测到标签的概率差值和子窗口2中标签被观测到的值作为判断标签发生跃迁的条件。经实验验证，改进算法使得动态标签跃迁检测的准确度提高，但是改进算法过小的清洗窗口，也将引入一定程度的消极读错误，这个问题有待进一步研究解决。

参考文献：

[1]谷峪，于戈，张天成.RFID复杂事件处理技术[J].计算机科学与探索，2007，I（2）：255-267.

[2] M. S. Trotter and G. D. Durgin.Survey of Range Improvement of Commercial RFID Tags with Power Optimized Waveforms[C].IEEE International Conference on RFID， April 2010：195-202.

[3] A. Rahmati， L. Zhong， M. Hiltunen， and R. Jana.Reliability Techniques for RFID-Based Object Tracking Applications[C]/.Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks （DSN 07）. IEEE Computer Society， 2007：113–118.

[4] H. Chen， W. Ku， H. Wang and M. Sun.Leveraging spatio-temporal redundancy for RFID data cleansing[C]/.Proceedings of the 2010 international conference on Management of data， SIGMOD '10， 2010.

[5] S.R. Jeffery， M. Garofalakis， and M.J.Franklin.Adaptive cleaning for RFID data streams[C]// Proceedings of the 32nd international conference on Very large data bases ， VLDB Endowment， 2006：163-174.

[6] H. Gonzalez， J. Han， and X. Shen.Cost-conscious cleaning of massive RFID data sets[C]/.Proc. 2007 Int. Conf. on Data Engineering （ICDE'06）， Istanbul， Turkey， April 2007.

[7] B. Song， P. Qin， H. Wang， W. Xuan， G. Yu，.bSpace： A data cleaning approach for RFID data streams based on virtual spatial granularity[J].Proceedings of HIS， 2009 （3）：252-256.

[8] P. Darcy， B.Stantic and A.Sattar.A Fusion of Data Analysis and Non-Monotonic Reasoning to Restore Missed RFID Readings[J].Proceedings of Intelligent Sensors， Sensor Networks and Information Processing （ISSNIP 2009）， 2009：313-318.

[9] J. Rao， S. Doraiswamy， H. Thakkar and L. S. Colby. A Deferred Cleansing Method for RFID Data Analytics[C].VLDB， 2006.

[10] E.Rahm and H.Do.Data cleaning：Problems and current approaches[J] .IEEE Data Eng.Bull， 200023（4）：3-13.

[11] S.R.Jeffery，G.Alonso，et al.A Pipelined Framework for Online Cleaning of Sensor Data Streams[C]. ICDE，2006.

[12] Jeffcry S R，Garofalakis M，Frakklin M J.Adaptive cleaning for RFID data stream.Proc of the 32nd Int Conf on Very large Databases[C]. NewYork：ACM，2006：163-17.