设计新的标签状态检测方法和窗口大小调整机制，对标签的状态变化可能通过概率来表现，并将改变概率和窗口大小调整结合，使清洗过程更加高效。
3.2 MC-SMURF算法描述
由于马尔科夫链是该算法的理论基础，并且新算法是基于SMURF算法的改进，我们将此算法命名为MC-SMURF。在此首先要了解什么是马尔科夫链。
定义1（马尔科夫过程）过程（或系统）在时刻t0所处的状态为已知的条件下，过程在时刻t>t0所处状态的条件分布与过程在时刻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，则在窗口滑动的过程中，如果计算出的W1、W2、W3窗口中标签的状态均未发生改变，则跳过W4直接计算眠中的标签状态变化概率，如果计算结果仍是标签状态没有发生改变，则继续跳过计算W7窗口中的概率值。该策略大大提高了该算法的运行效率。
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算法相比，改进算法对于数据漏读的填补效果更优。
