RFID数据清洗算法概述❋

张　燕，汤一彬，李旭斐

（河海大学物联网工程学院，常州213022）

RFID数据清洗算法概述❋

张燕，汤一彬，李旭斐

（河海大学物联网工程学院，常州213022）

RFID技术作为当前与物联网领域相关的一个热门技术，具有广阔的应用前景，但因其获取数据过程中产生的不可靠数据极大地限制了RFID技术的发展，因此对于RFID数据进行清洗是非常必要的。对RFID数据清洗方法进行综合叙述，主要介绍了国内外针对RFID中单个阅读器数据获取中产生不可靠的数据清洗解决算法，分析了各种方法的基本原理，讨论了目前企业对于数据不可靠提出的数据清洗应用解决方案。分析表明当前的数据清洗算法主要针对单一问题设计，计算效率不高，尚不适合各种RFID应用场景，未来RFID技术的发展趋势应该向普适性、高效性发展。

RFID技术；物联网；不可靠；数据清洗；解决方案；普适性

1　引　言

无线射频识别（RFID）系统使用无线射频技术在开放系统环境中进行对象识别，并且能够快速、准确、实时地采集和处理数据信息。这种识别的优点之一是无需物理接触或其它任何可见的接触。RFID技术在生活中应用非常广泛，例如，它可以用于生产和销售管理场合以简化供应链管理并实现对存货成本的有效控制；可以代替传统的二维条形码用于数字图书馆管理；可用于动物研究和饲养中的动物识别；可用于防伪造的电子护照系统；甚至可以用于构建智能无线传感器网络环境等等。

然而，由于受到各种环境和射频技术本身一些特点的影响，RFID阅读器识别标签时会出现各种错误识别现象包括：积极读、消极读、数据冗余等，这些因素都会制约RFID技术的进一步发展。为有效支持RFID高层业务逻辑处理，提供高质量的RFID数据，对RFID数据进行清洗是非常必要的。

国外大学和研究机构对RFID阅读器识别标签出现错误数据的现象已经进行了多年的探索并取得了一些成果。加州大学洛杉矶分校（UCLA）提出了通过使用时间滑动窗口技术清洗RFID原始标签数据流的方法［1］。加州大学伯克力（UC Berkeley）针对时间平滑处理窗口大小设置困难的问题，提出了一种基于概率论知识动态改变窗口大小的方法——自适应改变滑动窗口大小的数据清洗算法（SMURF）［2］。日本九州大学（Kyushu University）提出了一种基于现实世界的约束关系来提高RFID数据的可靠性［3］。伊利诺伊大学厄巴纳－尚佩恩分校提出了使用动态贝叶斯网络（DBN）清洗原始标签流的方法［4］。格里菲斯大学采用集合理论提出一种清洗策略［5］等等。

尽管用于数据清洗的技术已相对比较成熟，但是由于RFID阅读器受多方面因素的影响，阅读器对标签数据识别的正确率仍只有60%－70%左右。如何使RFID数据传输更加高效可靠也是一个挑战。下面将详细介绍这些数据清洗算法，并分析这些算法的优缺点。

2　RFID数据清洗需要解决的问题

在RFID系统中，RFID数据管理是RFID应用的重要部分。由于各类物理的和信号传输方面的原因，比如电源失效、电磁干扰、网络传输中断以及RFID电子标签低功耗和低成本的限制等，收集到的RFID数据往往不可靠［6－7］，这严重影响了RFID技术在各领域的应用（比如精确的库存跟踪，严格的病人监护等）。数据作为分析和应用的基础，在实际应用中起到了至关重要的作用，一旦RFID获取数据出现问题，会对相关企业和公司造成严重影响。例如：在基于RFID的物流系统中，RFID获取的不可靠数据使得数据定位不准确；基于RFID的监控系统也部分失去了其价值；而在基于RFID的停车场收费系统中，对象的漏读直接损失了停车场的经济收益。同时，不可靠数据的存在也限制了基于RFID数据的分析、决策支持、知识发现等复杂应用。

在RFID阅读器获取数据的过程中，主要存在以下三种典型的数据读取错误：

（1）消极读

研究表明，在RFID项目系统中部署的阅读器的读取率（即阅读器射频范围内电子标签被实际读取到的百分比）经常处于60%～70%的范围，即超过30%的标签被漏读了［8－9］。造成这种情况的原因包括：当多个标签被同时检测到时，射频碰撞发生以及信号互相干扰，阻止了阅读器对标签的识别；由于水或者金属屏蔽和干扰射频信号影响了标签被检测到。

（2）积极读

这种错误又被称为噪声，在该情况下，除了读取到原有的电子标签，也可能读取到一些额外的、并不期望的标签数据。这归因于以下几个方面：在阅读器正常射频范围之外的标签被该阅读器读取到了，例如阅读器被设置为从某一场景中读取对象，它同时也可能从邻近场景中读取对象；阅读器和环境的未知原因，例如某一个阅读器周期性的发送错误ID。

（3）数据冗余

这种情况主要由以下几个原因造成：标签长期处于阅读器射频范围之内在重复读取模式下被阅读器多次读到；安装了多个阅读器覆盖了大范围的区域，处于重叠区域内的标签被多个阅读器读取到；为了增强读取的精确性，多个拥有相同EPC编码的标签被贴在同一物体上，产生了多个相同的读取结果。

RFID数据与传统关系数据库和数据仓库数据库的数据相比，作为一种流数据，使得数据清洗［10］变得更加困难。①因为内存的限制，很多在静态数据上有效的清洗算法对RFID数据不适用；②流的特质使得记录表的范围只限于局部，无法观其全貌，这使得清洗结果的准确性更低；③因为应用的特点，必须在短时间内完成RFID数据的清洗工作，因此算法的时间要求更高。特别是当某个RFID应用布置规模极大时，如涉及到数千个阅读器、数万个标签时，数据清洗的难度更大。

因此，系统中必须增加对RFID数据的预处理环节，使阅读器读取来的数据，无论从时间序列还是从数值上都尽可能的接近真实数据。数据清洗的目的是检测数据中存在的错误和不一致，剔除或者改正它们，提高数据质量［8］。数据清洗的过程必须满足如下几个条件：不论是单数据源还是多数据源，都要检测并且除去数据中所有明显的错误和不一致；尽可能地减小人工干预和用户的编程工作量，而且要容易扩展到其他数据源；应该和数据转化相结合；要有相应的描述语言来指定数据转化和数据清洗操作；所有这些操作应该在一个统一的框架下完成［11］。

3　RFID数据清洗算法

目前，针对RFID数据的不可靠性提出了许多数据清洗算法，算法主要在两个方面展开：第一个方面是寻找高效的清洗模型和算法来解决单个阅读器识别标签的不可靠问题，该方面的研究对大多数RFID应用系统都具有一定的适用性；另一个方面是通过系统自身的独特规则和阅读器架构，从系统逻辑的角度来对数据进行清洗。采用第二种方法往往清洗效率很高，但清洗策略和具体应用相关，不具有普遍适用性。通过上述分析得出，进行数据清洗主要有三类数据清洗算法：一种是基于滑动窗口的数据清洗算法，一种是根据现实约束进行数据清洗，还有一种是优化方法获得最小代价的值。

3.1基于定义滑动窗口的RFID数据清洗算法

滑动窗口是一种比较典型、常用的数据流清洗技术。加州大学洛杉矶分校（UCLA）的Bai等人提出一种基于滑动窗口的方法清洗RFID数据流。使用滑动窗口解决清洗输出结果的顺序问题，RFID的定长滑动窗口数据清洗技术示意图如图1所示。

图1　定长滑动窗口数据清洗示意图

定长滑动窗口清洗技术是指在对RFID数据流进行清洗时，窗口的长度始终都保持不动。定长滑动窗口方法的清洗原理：在原始数据流上使用大小固定的滑动窗口，在某一时刻，如果窗口捕获到了某个数据，则这个数据会被认为一直存在于这个窗口中，并将这个数据输出。随着新数据的到来，窗口向前滑动，在窗口内存在的漏读错误会被填补。

通过图2可以看出，真实数据反映了这样一种情况，标签离开阅读器的覆盖区域之后经过一段时间又重新回到了阅读器射频范围之内。由于环境变化和RFID本身非接触式识别的技术特点，我们通过阅读器收集上来的数据用原始数据来表示，数据流出现了很多中断的地方，这就造成了数据漏读的现象。

图2　定长窗口引发的问题

根据图2中第三部分和第四部分可以看出小窗口能够弥补一些漏读错误。但是由于窗口选择过小，有些真正的漏读情况并没有被弥补掉，依然存在消极读取的错误。而大窗口确实对漏读进行了完全弥补，通过大窗口平滑之后所有的漏读错误都解决了，但是，却不能检测到标签离开阅读器这个事件所引发的积极读取错误。这样由于窗口大小固定，导致窗口过大产生积极读取错误，窗口过小产生消极读取错误。由于窗口大小固定造成RFID不能根据数据特点进行精确填补漏读的数据，最好的改进方法是通过自适应的改变窗口大小，这样可以适应多变的环境。

3.2自适应窗口大小的RFID数据清洗算法

为避免定长滑动窗口带来的问题，加州大学伯克力分校的Jeffery R等人针对RFID数据流所固有的不可靠性，针对定长滑动窗口的窗口大小不容易确定问题，提出了一种自适应改变滑动窗口大小的RFID数据清洗方法——SMURF。

SMURF方法的主要思想是采用统计采样理论来自适应进行过滤。将RFID阅读器捕获的标签数据当成是对探测器范围内存在的标签的一次抽样，然后对RFID阅读器捕获的数据进行数学建模，根据建立起的数学模型，并结合探测到标签的情况对窗口大小进行实时更新。SMURF策略采用两个不同的概率模型来对探测范围内不同的情况进行清洗：

（1）单个标签数据清洗

利用标签阅读率决定滑动窗口的大小，若标签的阅读率较低则会赋予其大窗口以减少消极读；反之，如果标签的阅读率较高，则赋予一个小窗口以减少积极读。该方法通过定义窗口大小为wi，每个标签被阅读发生的概率为pi。将若干查询周期组合成一个纪元，每个纪元内标签的阅读率pi与窗口大小wi符合二项式分布B（wi，pi），根据伯努利概率模型得到窗口的大小如下：

通过（1）式能够以很高的概率保证其完整性，但同时可能导致丢失标签的动态变化过程，方法用下式来保证探测标签的动态变化。

（2）式表示在平滑窗口内检测到标签的次数，即数学期望与实际检测数值之差的绝对值大于二倍标准差，此时适当减小其窗口。由此根据标签的当前检测信息，适应性的调整窗口大小，可以保证较完整的填充数据。

（2）多标签集合清洗

多标签数据清洗技术：与单标签方法不同的是，其利用的概率模型是π－estimator，判断标签移动的条件是，其他的操作和单标签数据清洗技术操作一样。

SMURF方法与定长的滑动窗口方法相比，可以自适应改变窗口的长度，既能保证数据完整性又能保证及时捕获标签的状态改变，可以很好的弥补由于窗口长度一定而不能够同时满足这两要求不足。但是利用数学模型进行调整时，采用了平均概率，若数据速率波动大就不能反映某一时刻的数据特征，造成窗口调整错误，致使阅读率陡然下降。SMURF方法反而增大窗口进行平滑，此时将产生更多积极读取错误。

3.3基于约束的清洗算法

Kyushu University提出了一种基于现实世界的约束关系来提高RFID数据的可靠性［5］。它指出现实世界的约束主要有两种，一种是Accompany Constraint（伴随约束）另外一种是Route Constraint（路径约束）。所谓伴随约束是指系统明确知道一组物体同时运动，阅读器只要检测到部分物体就可以推知整个物体被检测到。另外一种路径约束是指系统已知物体会沿着特定的路径运动。通过这两种约束可以解决标签漏读问题。

本文提出的综合清洗系统主要由两个部分组成：冗余去除引擎和约束引擎，如图3所示。冗余去除引擎主要是删除原始RFID数据中的大量冗余数据，减少待清洗的RFID数据量。约束引擎主要是对去冗余之后还存在错误的RFID数据再次进行清洗，以保证最后输出干净的RFID数据流以供用户后续的查询工作。

图3　综合清洗系统框架图

将原始的带有冗余的RFID数据输入冗余删除引擎；经冗余删除引擎处理后，得到去冗余后的RFID数据以进行下一步处理；将用户指定约束及自学约束输入约束引擎，维护约束引擎；用约束引擎清洗去冗余后的RFID数据；得到经约束清洗后干净的RFID数据，并输出给用户以供上层应用。

冗余去除算法可将原来采集到的RFID数据量减少40%－50%，这将极大降低系统开销，为后续的数据清洗工作提供便利。约束算法是在自学约束及用户指定约束的指导下进行清洗的，考虑进了对象之间的联系以及约束对数据对象的影响，其性能要优于在线清洗的五层管道框架系统算法。

3.4基于动态贝叶斯网络（DBN）的清洗算法

由于SMURF方法只是根据观测值改变滑动窗口的大小，同一窗口中数据具有相同权重的问题。伊利诺伊大学厄巴纳－尚佩恩分校（University of Illinois at Urbana-Champaign）的Gonzalez H等人提出一种考虑代价的大量RFID数据集的清洗方法。该方法引入一个全新的清洗规则即最小化代价，提出一个清洗框架，来产生一个全局的最优清洗方案。提出了一种动态调节信任状态的清洗新方法——基于动态贝叶斯网络（DBN）的方法。

动态贝叶斯网络主要思想是通过利用网络结构以及条件概率表，获得所要求事件的概率，并利用先验知识和样本数据获得对未知样本的估计。在RFID数据清洗方法中利用动态贝叶斯网络是通过假设一个隐模式标签来决定实际标签位置，实际读取可以观察该隐模式加噪声的情况，算法是通过历史观测数据对标签进行预测并获得一个概率值，以此概率值判断标签是否存在。

动态贝叶斯网络中的模型具体实现是定义一个隐变量Xt，若标签在时间t出现在阅读器范围内改制为真；另定义一个观测变量et作为关于Xt的噪声观测量。通过e1：t＋1得出Xt＋1的可能状态：

式（3）中P（et＋1｜Xt＋1）已知为真时，通过观测可得概率P（Xt＋1｜xt）为一个真状态转换为另一个真状态的概率，而P（Xt｜et＋1）为之前的信任状态，观测模型和转换模型可从历史数据得到，具体方法框图如图4所示。

图4　DBN清洗方法框图

与滑动窗口、SMURF等方法比较，贝叶斯网络的优点在于结合观察值和预测值的关系赋予新数据更高的权重，且不需要记载最新的标签数据。然而从历史数据集中得到预测值与观察值的关系，不能动态更新，所以不能理想地清洗动态标签，对于动态标签的清洗效果不是十分理想。

4　RFID数据清洗应用解决方案

随着对RFID项目的实施研究，发现通过RFID中间件可以将RFID数据正确导入相应的信息管理系统。国际上，比较知名的RFID中间件厂商提供了对于RFID数据清洗的应用方案，主要有IBM、SUN、Oracle等大型企业。

IBM基于Java语言并依照J2EE企业构架开发的RFID中间件产品可以简化企业实施RFID项目的步骤，同时实现企业能够处理海量货物数据的目的。IBM的RFID中间件产品是开放式的，其RFID中间件架构［12］中的Edge Domain模块的功能是管理RFID底层设备以及过滤、聚合和分发原始标签数据。在整个RFID中间件系统中Filter Agent与数据处理相关，但只能实现冗余过滤和位过滤，不能针对漏读、脏读、冗余读以及复杂时间清洗。

SUN的RFID中间件架构包括两个部分，分别是Execution Agent和Control Station，但只有Execution Agent中的Filter组件和数据处理有关。最早提出用smooth、delta和bandpass等简单过滤规则组件来过滤冗余读、消极读的是SUN公司，但增加过滤功能仍然需要特定组件，而且不存在完整的数据清理解决方案和灵活的复杂事件读取引擎。

基于BEA的Web Logic Enterprise Server 9.2架构是Oracle／BEA联合研发的RFID中间件架构［13］，其中的事件引擎位于事件服务架构中，是目前功能最完善的事件引擎。它使用Esper流事件处理引擎和EPL语言来监控实时标签数据并生成具有逻辑业务含义的复杂事件。但建于关系代数模式之上的引擎不能顺序读取时序，同时RFID事件读取中的时序读取又非常关键，在这一点上它是不适用的，并且BEA的事件处理模块对RFID数据中存在的问题也没有提供合适的清洗方案。

5　结束语

RFID技术已被大多数人所熟知，其广泛的应用场景，低廉的成本，部署实施的简单性，已经越来越多地吸引着更多的用户、研究人员和IT厂商。RFID技术作为无线射频技术，技术特点决定了其数据流具有不可靠性的缺点，该缺点是限制RFID技术被广泛应用的关键因素，该缺点造成了RFID技术在高水平的精确应用中应用价值不高的问题。为解决该问题，需要对原始数据进行清洗，以得到干净的、可实际应用的数据流。通过详细讨论已有的RFID数据清洗算法，分析了这些算法中存在的缺陷。根据算法比较结果表明：目前尚不存在一个高效、实用、干净的低成本RFID清洗算法。设计高效、实用、低成本的实用RFID清洗算法以及清洗策略依旧是一个值得挑战的领域，尤其是对中间件研发使其具有高效的数据处理模式是一个值得开发的领域。

［1］Yijian Bai，Fusheng Wang，Peiya Liu.Efficiently filtering RFID data streams［C］.The first international VLDB Workshop on Clean Database（CleanDB）Workshop，Seoul，Kerea，2006：50－57.

［2］Shawn R.Jeffery，Minos Garofalakis，Michael J.Franklin，et al.Adaptive cleaning for RFID data streams［J］.Proceedings of the 32nd international conference on Very Large Data Bases（VLDB），Seoul，Korea，2006：163－174.

［3］Sozo Inoue，Daisuke Hagiwara，Hiroto Yasuura.Systematic Error detection for RFID reliability［C］.proceedings of the Frist International Conferece on Availability，Reliability and Secuity.2006.

［4］Hector Gonzalez，Jiawei Han，Xuehua Shen.Cost－conscious cleaning of massive RFID data sets［C］.Conferenece on DataEngineering（ICDE 07），Istanbul，Turkey.April 2007：1268－1272.

［5］Jeffery S R，Alonso G，Franklin M J，et al.A pipelined framework for online cleaning of sensor data streams［C］.Proceedings of the 22nd International Conference on Data Engineering，2006：140－153.

［6］许嘉，于戈，谷峪，等.RFID不确定数据管理技术［J］.计算机科学与探索，2009，3（6）：561－576.Xu Jia，Yu Yi，Gu Yu，et al.RFID data management Technology［J］.Computer Science and exploration 2009，3（6）：561－576.

［7］陈旭辉，王馨，柯铭.一种改进的基于RFID中间件的冗余数据清洗算法［J］.微电子学与计算机，2013，30（7）：154－158.Chen Xu_hui，Wang Xin，Ke Xin.An improved Redundancy Data Cleaning Alogorithm based on RFID Midsoftware［J］.Microelectronics and Computer，2013，30（7）：154－158.

［8］Popovski P，Fyhn K，Jacobsen R M，et al.Robust statistical methods for detection of missing RFID tags［J］.IEEE Wireless Communicationns，2011，18（4）：74－80.

［9］Wang F，Liu P.Temporal Management of RFID Data［C］.In：Proceedings of the 31st International Conference on Very Large Data Dases.Trondheim，Norway，2005：1128－1139.

［10］Daniel J.Abadi，Don Carney，Ugur C.etintemel.Aurora：A new model and architecture for data stream management［J］.In：VLDB.Journal，2003.

［11］R Jeffery，M Graofalakis，M J Flanklin.Adaptive Cleaning for RFID Data Streams［C］.Proceedings of the 32nd International Conference on Very Llarge Data Bases.Seoul，Korea，2006：163－174.

［12］Rahm E，Do H H.Data cleaning problems and current approaches［J］.IEEE Data Engineering Bulletin，2000，23（4）；3－13.

［13］郭志懋，周傲英.数据质量和数据清洗研究综述［J］.软件学报，2002，13（11）：2076－2082.Guo zhimao，Zhou aoying.Survey of data quality and data cleaning［J］.Iournal of Sofrware，2002，13（11）：2076－2082.

Overview on RFID Data Cleaning

Zhang Yan，Tang Yibin，Li Xufei
（College of Internet of Things Engineering，HoHai University，Changzhou 213022，China）

RFID，as a popular technology related to Internet of Things field，has good application in the future.It is necessary for RFID data cleaning，because the unreliability of the data is produced，in the process of the data acquired，and the development of RFID technology is limited.RFID data cleaning methods are surveyed through introducing the RFID data cleaning technology research in domestic and overseas.The advantages and disadvantages of the various algorithms are compared and analyzed，and the application based on the middleware of data cleaning solutions is discussed.The result shows that the algorithm of data cleaning is mainly designed for a single issue with low calculation efficiency，and the new one，with good applicability and high efficiency，should be developed in the future.

RFID technology；Internet of Things；Unreliability；Data cleaning；Solutions；universal

10.3969／j.issn.1002－2279.2016.01.009

TN911.73

A

1002－2279（2016）01－0032－05

❋江苏省自然科技基金（BK20130238）

张燕（1992－），女，山东省潍坊市人，本科生，主研方向：数字图像处理。汤一彬（1982－），男，东南大学博士，河海大学讲师。

2015－05－20