马尔科夫链的RFID数据清洗算法研究

摘要：在获取RFID（Radio Frequency Identification）数据过程中，大量的漏读导致用户无法直接使用原始数据，需通过一定方法对其清洗。在现有的清洗算法的基础上，分析已有算法的优缺点，并结合马尔科夫链提出改进算法。通过马尔科夫链对于状态转移概率的计算，改进SMURF算法检测标签状态改变机制，并将概率引入窗口大小调整策略中。实验中将匀速运动的标签和随机运动的标签产生的数据进行清洗。结果表明，所提出的算法对于数据漏读的填补效果更好。

关键词：RFID；数据清洗；填补；马尔科夫链

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）17-0168-05

1概述

射频R别（Radio Frequency Identification，RFID）技术是一种无需和目标对象进行接触的自动识别技术，它通过读写器识别出电子标签的信息来获取用户所需数据。

由于半导体技术的快速发展，目前已经能够生产较低成品的电子标签，这使得RFID技术迅速代替传统的条码技术而广泛应用到日常生活中，比如物流的定位跟踪、货架上物品的管理、机场行李输送等。RFID技术的使用大大提升了现代服务业、生产制造、商业流通、交通运输、医药卫生、军事、邮政、烟草等行业的管理效率和商业价值。可以说，RFID的应用前景十分广阔。但就目前来看，还有着制约其更大范围推广使用的因素亟待解决，那就是在获取RFID数据时用户面临的诸多问题，如数据数据的漏读和数据的多读等。

用户在采集RFID数据时，阅读器上报的原始数据，其准确性只有60%-70%，是无法直接上传给上层应用使用的。其中数据的多读情况较少而漏读情况较为严重，我们需要采取一定措施使数据尽可能还原其真实性。目前较为常用的三种措施为：硬件解决措施、中间件解决措施和存储器解决措施。硬件解决措施指的是提升采集设备和电子标签的属性；中间件解决措施是通过中间件对采集来的数据做相关处理；存储器解决措施是将数据在存储过程中通过智能化控制技术对其进行还原。中间件解决措施以其实用、高效、成本低的特性被广泛用。

2相关研究

目前的RFID中间件数据清洗技术，比较常用的有基于定长滑动窗口的处理方法、在线可扩展清洗框架、自适应滑动窗口的数据清洗、基于完整性约束的清洗方法和基于布隆滤波的清洗方法等。其中基于窗口的清洗方法适用场景广泛，机制简单，实际应用中被采用较多。但是，基于窗口的清洗方案仍有缺陷。

固定长度的滑动窗口在清洗时的优势是较为快速，当硬件设备和周围环境变化较小时清洗效果有明显优势。但是，窗口大小的取值完全取决于行业经验，如果窗口大小设定不当，清洗的效果将十分低下。通过观察图1中的“真实数据”可以推断出，标签一开始处于阅读器的读取范围内，在随后的一段时间里离开了阅读器的读取区域，之后再次回到读取区域内。而在实际采集时，由于漏读情况的存在，呈现的数据流是不连续的，如图中“接收到数据”除了真实离开时阅读器读取不到的一段空白，还有很多大大小小的空白区域。“小窗口平滑结果”显示了利用长度较短的窗口进行处理之后的结果，“大窗口平滑结果”所使用的窗口较长。可以看出，不论窗口大小如何，一定程度上都对数据的漏读现象做了填补，但过小的窗口无法对所有的漏读现象进行修复，而过大的窗口填补了所有遗漏，致使最后的结果对标签离开阅读器射频区域这一事实无法体现。

Jeffery等人基于以上问题，在固定窗口清洗方法的基础上提出可动态调整窗口大小的数据清洗方法――SMURF。该方法创造性地将概率引人清洗模型，将阅读器对标签的读取看作随机事件，从而根据观测值动态的改变窗口的大小。其具体实现过程如下：

如果标签状态发生改变，算法会依据式（8）动态的调整窗口大小。

SMURF算法首先将初始的窗口大小设置为1，然后根据读取的实际情况动态调整窗口长度。如果当前窗口内没有任何阅读，SMURF算法将窗口保持为1。然后窗口以时间片为单位进行滑动，如果当前窗口满足完整性需求，SMURF算法会根据式（8）对标签的状态进行检测。当检测结果表明标签状态改变时，SMURF会将当前窗口长度调整为原窗口的1/2，从而对标签的迁跃做出反应；若检测出标签并未发生迁跃，则算法以当前窗口中点为输出点进行输出，再继续滑动一个epoch来进行下一次处理。若计算得出的满足完整性约束的窗口大小大于当前窗口大小，则算法以2为步长线性增大当前窗口大小，并对当前窗口中点数据进行输出。

3改进算法MC-SMURF

3.1新算法的提出

SMURF算法通过将标签的读取看作是随机事件，通过概率知识判断标签的状态改变，从而减少了固定窗口清洗由于窗口长度设置不当导致的较多积极读或消极读现象。但是，当标签进行频繁的迁跃，或者标签运动速度较快时，SMURF算法不能及时对窗口大小做出合适的调整。算法性能缺陷分析如下：

1）在标签的动态性检测方面，只通过对窗口内标签平均读取率的改变来判定标签是否发生了迁跃，这在某些情况下是不准确的。我们知道，标签的状态改变除非肉眼所见，否则是无法寻找一个百分之百准确及时的判定标签状态改变的策略。

2）对于窗口大小的调整。无论是以2为步长增大窗口，还是将窗口大小设置为原来的一半，窗口的大小调整幅度和标签的状态变化并无关系，这使得在某些场景下积极读和消极读的现象较多。并且，当检测到标签状态变化时，将窗口大小减半是武断的，这可能造成消极读的概率很高；而当窗口以2为步长增大时，可能会因为不能够及时满足完整性需求导致平滑结果和实际数据差异较大。

基于以上两点考虑，在SMURF算法的基础上，设计新的标签状态检测方法和窗口大小调整机制，对标签的状态变化可能通过概率来表现，并将改变概率和窗口大小调整结合，使清洗过程更加高效。

4.2实验结果与分析

该节将本课题的改进算法与SMURF算法和其他固定窗口清洗算法比较来验证改进算法性能，每个固定窗口清洗算法用Static-X表示。

实验通过数据生成器模拟一个6*6m的区域，阅读器的最大读取范围为4.6m，标签个数为30个，每个实验使用数据生成器生成的500个时间片的数据进行处理。

实验过程中，每个算法通过处理数据生成器产生的数据，将结果与真实数据对比，用每个epoch里的错误阅读数来表示各个算法的清洗效果，其中的错误阅读数是指标签在阅读器读取范围但是结果中没有显示的（a false negative），或是标签不在阅读器读取范围但在结果中显示有读数的（a false positive），公式如下：

首先选取“托盘”模型的运动方式来进行仿真实验。设置阅读器的主读取区百分比为70%，通过改变标签匀速运动速度比较各种清洗算法的性能。实验所得数据如图5所示。图中可以看出，随着标签速度增大，小窗口的清洗效果逐步提高，那是因为较小的窗口有更好的填补作用。对于SMURF算法和MC-SMURF算法，它们的清洗效果稳定且高效。而MC-SMURF由于改进了标签状态转变检测条件和窗口大小调整策略，对标签状态变化更为敏感，清洗效果更佳。

第二实验中，使用“随机运动模型”进行验证，通过改变阅读器的主读取区百分比验证随机运动状态下各种清洗算法的性能，并让标签在每100个epoch时改变其状态。实验结果对比如图6所示：

由图6可以看出，小窗口在主读取区百分比较小的时候清洗效果不佳，因为主读取区很小的时候，次读取区的读取率很低，即对标签的漏读率很高，而过小的窗口无法有效地对漏读数据进行清洗，导致错误读数较高。而对于大窗口，其过滤效果随着主读取区百分比的增加几乎没有变化，原因是过长的窗口在清洗的过程中虽然可以将漏读数据清洗完整，但无法对标签的状态变化导致的真实空白数据做出判断，从而将标签离开阅读器读取范围而形成的0数据错误清洗为1。本文的改进算法较SMURF算法和另外两种定长窗口算法有着更好的清洗效果，是因为改进算法对于标签的状态改变判定更为及时准确，同时在窗口大小的调整方面更为合理，使清洗后的数据错误数最低。

5结束语

为了让提供给用户的RFID数据更加真实可靠，提出一种基于SMURF的改进算法。算法结合马尔科夫链对检测标签状态转变条件做出改变，并结合计算出的转变概率动态设置窗口大小。实验结果表明，与定长滑动窗口算法和SMURF算法相比，改进算法对于数据漏读的填补效果更优。