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

何涛+刘畅+徐鹤+姜彦男

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

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

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

1概述

射频識别（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算法的基础上，设计新的标签状态检测方法和窗口大小调整机制，对标签的状态变化可能通过概率来表现，并将改变概率和窗口大小调整结合，使清洗过程更加高效。

3.2 MC-SMURF算法描述

由于马尔科夫链是该算法的理论基础，并且新算法是基于SMURF算法的改进，我们将此算法命名为MC-SMURF。在此首先要了解什么是马尔科夫链。

定义1（马尔科夫过程）过程（或系统）在时刻t₀所处的状态为已知的条件下，过程在时刻t>t₀所处状态的条件分布与过程在时刻b之前所处的状态无关，即是在已知过程“现在”的条件下，其“将来”不依赖于“过去”，则称此过程为马尔科夫过程。

得出状态转移概率矩阵，我们就可以通过标签从阅读器读取范围离开或是留在读取范围的概率和标签在阅读器读取范围外进入读取范围的概率或是仍在读取范围外的概率做进一步讨论。

在完整性檢测方面，继续沿用SUMRF算法的方法，即式（8）。原算法中，当计算出的窗口较原窗口大时，通过增大窗口来保证完整性。但是在窗口增大的过程中，窗口内的平均读取率会降低，此时，原算法默认是由于窗口增大造成而不进行标签状态的检测，这样是不符合实际情况的，因为在窗口增大的过程中，随着标签的状态改变，窗口内的平均读取率也在下降。改进算法通过概率转移矩阵判断标签是否发生状态改变，巧妙的弥补了平均读取率下降时不进行状态改变检测的不足。

在计算过程中，如果得出的结果是标签的状态发生了改变，原算法通过将窗口减半来减少消极读，这是缺乏合理性的。改进算法通过引人状态改变和未改变的概率差值τ来对窗口大小进行调整。当标签处于状态1（状态2情况相同）时，具体情况如下：

在用概率来检测标签状态改变的改进算法中，在某些情况下是存在很大不确定性的，即：当通过状态转移概率矩阵计算出的状态改变和未改变数值相近时，此时在判定标签是否发生迁跃时不确定性较大。对于标签的状态改变检测，任何系统都没有办法做到百分百确定的检测正确，因此，改进算法通过在对窗口大小的幅度调整中加入τ来将误差减少至最低。

如果检测结果表明标签发生状态改变，但差值很小，那么是有一定可能标签并未发生状态转变的。此时，将差值τ引人新窗口的计算公式，差值小时窗口的改变幅度也随之很小，这就避免了由于误判导致的消极读。

同时，当未满足完整性需求时，原算法通过每次增加2来增大窗口，但这有可能导致窗口大小不足而使清洗后的数据与真实数据产生较大偏差。改进算法通过将计算出的新窗口大小加入窗口的线性增大过程，新窗口较原窗口很大时，窗口增大的速度会更快，更好的弥补读取时完整性的不足。具体方法是设置窗口大小为新窗口和原窗口和的二分之一。

3.3 MC-SMURF算法流程

MC-SMURF算法步骤如下：

1）将窗口初始大小设置为1，且在窗口内没有任何阅读时，均将大小调整为1。

2）改进算法以时间片为单位滑动窗口。如果当前窗口大小满足完整性需求，则转至步骤3）执行，否则转至步骤5）执行。

3）根据式91计算状态转移概率矩阵，然后计算状态转移概率，通过状态转移概率判断标签状态是否发生改变，改变则转至步骤4）执行，否则转至步骤6）执行。

4）通过式10）计算新窗口的大小并将滑动窗口调整为此大小，转至步骤6）执行。

5）计算满足完整性需求的窗口大小，并将新窗口大小和原窗口大小相加除以2作为当前窗口大小，调整窗口，转至步骤6）执行。

6）以当前滑动窗口中心为滑动点输出，滑动时间片做下一次处理。

新算法的流程图如图2所示。

3.4 MC-SMURF优化策略

如果每获取一次读取数据都需要进行标签状态改变概率计算的话，即使标签的运动状态变化不频繁，其代价也比较大。在实际运用中，诸如超市货架或是图书馆书架等RFID运用场景，标签物品的位置变化并不频繁，因此，我们在使用MC-SMURF算法时可加入以下策略：

如果计算出的标签位置在连续的N个窗口内都未发生变化，则认为标签在下一个窗口时位置仍不发生变化。

该策略的使用大大减少了对于概率的计算量，且是有理可循的。如果标签连续N个窗口检测结果位置都没有发生改变，则可以跳过下一个窗口直接计算再下一个窗口的概率值。

如图3所示，假设上述改进策略中的N取3，则在窗口滑动的过程中，如果计算出的W₁、W₂、W₃窗口中标签的状态均未发生改变，则跳过W₄直接计算眠中的标签状态变化概率，如果计算结果仍是标签状态没有发生改变，则继续跳过计算W₇窗口中的概率值。该策略大大提高了该算法的运行效率。

4实验与分析

4.1数据生成器设计

为了验证改进算法在数据清洗方面的性能，本节运用文献[8]里的方法，通过数据生成器生成RFID系统的模拟数据，再通过仿真实验模拟其他几种清洗算法，然后进行交叉对比，凸显本文提出的改进算法的清洗效果。

首先设计两个标签运动的模型：“托盘运动模型”和“随机运动模型”。

“托盘”运动模型：此模型模拟了托盘上被标记的物品，所有标签的运动速度均相同。

“随机”运动模型：此模型中，每个标签有一个1 feet/epoch至3 feet/epoch的初始速度。每隔一百个

epoch改变一次标签的状态或运动速度。（这里的lepoch代表阅读器的一个读取周期）。

阅读器的读取模型根据实际应用进行设计，如图4所示。

在主读取区里，读取率较高，一般约为80%至95%，意味着标签在主读取区基本都能读到。随着标签与阅读器的距离增加，标签进入阅读器次读取区，读取率呈线性衰减趋势。直至降为0，代表标签离开了阅读器的读取范围。

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算法相比，改进算法对于数据漏读的填补效果更优。