利用RFID数据时空冗余性提升数据清洗性能

李晶　张磊　王斌

摘要：无线射频识别（RFID）技术已经大规模应用于许多数据采集方面的应用。然而由于电磁干扰、元器件质量等因素，原始采集的RFID数据通常是低质量的，并且包含许多异常信息。目前已有的RFID数据清洗技术没有完全利用RFID数据的时空冗余性、环境先验知识及应用限制等特征。本文提出了一种基于贝叶斯推理的RFID数据清洗方法，充分利用了数据的冗余性。

关键词：时空冗余性；概率算法；贝叶斯推理；数据清洗

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）29-0232-03

1 引言

RFID是一种允许物体在一定范围内，被自动识别而无需直接观测到的电子标签技术，采用电磁和响应交换[1，2]。目前大量的零售商如沃尔玛、中国EMS、思科在仓库和分发中心的存货系统中安装RFID技术。然而RFID阅读器收集到的数据是不可靠的，中间件系统需要纠正阅读数据并提供清洗过的数据。目前大部分解决方案是清洗一组阅读器采集的数据[3]。然而，已有的方法主要存在三个方面的限制：

1）未利用RFID数据的时空冗余性提高数据的准确性。由大量拥有重复检测区域并且静止的阅读器可产生数据的空间冗余，移动的阅读器在一段时间内持续的数据采集可形成数据的时间冗余。

2）没有有效地利用标签物体和RFID阅读器的先验知识提高数据的准确性。

3）未有效的利用特定应用中的限制（比如一个房间或书架的容量）清洗数据。

本文提出一种考虑到这三种限制的新方法，充分利用数据的冗余性、先验知识和应用限制来提高准确性和数据清洗的有效性。

2 贝叶斯推理框架及n元检测模型

2.1贝叶斯推理框架

首先描述如何基于贝叶斯推理的方法来处理冗余数据和先验知识。贝叶斯推理是根据观察（y）得出假设（x）可能性的统计学方法。贝叶斯推理表明后验知识跟先验知识息息相关，可表示为[pxy∝pyxpx]。

假设在检测环境中有m个区域和n个物体，每个区域中间位置部署一个阅读器。oi表示拥有ID为i的物体。对于每个oi，它的位置表示为一个随机变量hi。因此，n个物体在m个区域可能的分布表示为一个向量[H=h1，h2，…，hn]。hi表示物体oi所在的位置。例如h1=2表示物体o1当前在区域2内。对于区域j中的阅读器，从物体oi标签接受到的未处理的数据（0或1）定义为zij。从m个阅读器每次完全的扫描得到的未处理数据矩阵可以表示为[n×m]阶矩阵[?]=|zij|。那么贝叶斯定理可以如公式（1）所示，其中[postH?]表示根据给定未处理数据[?]得到后验位置矢量[H]，假设满足以下约束：如果[H]无效，[postH?]=0；如果[H]有效，[postH?]>0；如果[H1]比[H2]可能性大，则[postH1?]>[postH2?]。如果在未处理数据矩阵中zij=1而实际中物体oi没在区域j中，那么zij就是误报。

为了计算[postH?]，假定每个阅读器检测不同的标签是独立的（阅读器成功检测到一个标签不影响它成功检测到另一个标签），可以得到公式（2）。假定不同的hi（物体位置）之间是独立的，并且假定对同一物体每个阅读器的检测是独立的，每个物体的先验分布不依赖于其他物体。由此可得到公式（3）。采用格式化常量[α]重写公式（3）可获得公式（4），对已给定的脏数据[?]和假设[H]（每个物体的位置），可以基于公式（4）得到假设的可能性。

我们的目标是创造一个大的有效假设样本集，而有效假设采样的一个先决条件是可以精确计算每个假设的后验概率。

2.2 RFID阅读器检测模型

計算公式（4）中每个样本的先验概率的关键是准确计算p（zij|hi）的可能性。为此引入n-状态检测模型来精确的计算其可能性。

RFID的物理特性决定其数据采集和传输是不可靠的。阅读器的检测范围可以分为主要检测区域和次要检测区域，其中主要检测区域在距离阅读器较近的范围内，其阅读率可以维持在95%，而次要检测区域的阅读率呈直线下降趋势，超出阅读器的检测范围时，阅读器的阅读率恶化为0。

为了解决这个问题并利用重复的数据，本文提出了一个n-状态检测模型，将阅读器的所有检测区域分成成许多子区域，每一个区域都对应唯一的读取率。不同状态的读取率构成一个等差数列。

为了捕获这种相关性，选择n=3（生成3-状态检测模型）具有更好的可行性。当系统有更多可靠的阅读器就有更少的不确定性，3-状态模型比2-状态在目标定位上提供更多的信息。根据读取率和信息熵之间的关系可以证明，信息熵随着读取率的增大而减小，但是n的取值也不是越大越好，实践应用中3-状态检测是比较理想的模型。

3 具有约束的采样算法

由于公式（4）容易计算但难于采样，本文提出一种对采样进行约束管理的Metropolis- Hastings采样算法（简记为MH-C），算法产生的每个样本可以自动的满足所有的约束，可有效地从先验分布中抽采样本。

马尔可夫链蒙特卡尔理论（MCMC）是通过模拟一个马尔可夫链来从状态空间采样。当样本的数目足够大时，所有的样本都能随机获得后验知识。因此，可直接构建马尔可夫链来近似逼近后验概率。选择MCMC而不是其他采样技术是因为MCMC维持了样本之间的相关性。在MCMC中，下一个样本的选择取决于当前的样本[8，9]。下面首先阐述如何利用采样样本的相关性来提高效率，定义如下术语：

定义1 候选样本. 称从采集器获得的任何样本为候选样本，一个合格的样本是满足所有约束的候选样本。

通常采用的完全随机采样方法中，由于相邻样本相关性的丢失，产生独立样本的效率将受到影响。可以利用样本之间的相关性来改善采样效率，合格的采样空间是完全采样空间的一个子集。

尽管MCMC提高了采样效率，MCMC所产生的样本不一定是一个合格的样本。虽然原始的Metropolis- Hastings算法可以通过构造马尔可夫链来评估后验分布，但它没有把约束条件考虑进来。如果利用约束采样，将会拒绝许多样本，这是由于它们是不合格的样本。

为了在采样中利用约束条件，提出了MH-C方法。MH-C的每个区域都与资源描述符的变量相关，当前的资源描述符表示有多少相关资源仍然是可用的。假设使用一个变量DescriptorZonei跟踪区域i能可用的空白资源，初始的DescriptorZonei值是区域i内能容纳的最大容量。那么，占用空间值为Volumeobjectj的j物体能否存储在i区域可以表示为：

DescriptorZonei= DescriptorZonei -Volumeobjectj （5）

只有在DescriptorZonei不为0时资源分配才是可行的，否则必须重新采样直到找到一个满足所有约束新的分配。因此，资源分配是否可行的问题可以简化为检测描述符的值。

MH-C算法基于Dobject的空间矢量通过空间迭代获得每个样本，如果任何分配的资源符小于0，那么目前的样本不可能成为合格样本，应该丢弃当前的值并重新选择维度进行采样。构造一个随机游走链，选择关于步长的一致方案分布。MH-C算法的描述如下，表1给出了相关符号的含义。

Algorithm 1 支持约束的Metropolis-Hastings 采样算法

1） 初始化[S] = ?，获得原始数据矩阵[?]

2） 载入n-状态检测模型

3） 将资源描述符初始化为最大容量.

4） 初始化[C]，在Post（[H]|[?]）中随机选择合格的样本作为开始点.

5） for Cycle = 2 to E+B do

6） for j = 1 to Dobject do

7） repeat

8） Pj = Cj+ Random（-S，S） {根据当前值和建议步长生成新整数}

9） if Pj < 1 then

10） Pj = 1+ （1-Pj ）{溢出并重设}

11） end if

12） if Pj > Dzone then

13） Pj = Dzone -（Pj -Dzone）

14） end if

15） until所有与引用区域相关的资源描述符值不小于0，在接受当前对象的建议分配之后

16） j ← j + 1

17） end for

18） Jitter←生成0，1之间的一个随机数

19） if Jitter ≤ min（1， [Post（P|?）Post（C|?）]） then

20）[C] = [P] //Metropolis-Hastings采样

21） end if

22） 将[C]添加到[S]作为下一个样本

23） 重置所有资源描述符

24） Cycle ← Cycle + 1

25） end for

算法1中用到的符号含义如下：[S]：样本集， [C]：马尔可夫链上当前的样本，[P]：马尔可夫链上建议的样本，Cj：[C]的第j维，Pj：[P]的第j维，E：有效样本个数，B：老化阶段的样本个数，S：统一建议分布步长，Dobject：监测对象的总数，Dzone：区域总数。

4 实验验证

为了验证算法性能，本文模拟大型仓库生成检测物品的RFID数据集，让物体对应盒子，区域对应货架。采用3-状态检测模型实现MH-C算法，并且作为对比，扩充基于SIS的方法[4]，增加利用重复读数功能，达到可对比程度。

4.1实验数据及测度

本文设计了模拟器生成大型仓库的随机产生分布矩阵（行表示物体，列表示货架（区域））和具有噪声的RFID原始数据，通过100次试验来验证MH-C方法在重建的效率和准确性方面相对于SIS的性能。

定义2 前k成功率. 真实位置匹配了重建分布中前k个预测位置的箱子个数在总共箱子个数中所占的百分比，k=1时表示最佳成功率。

4.2 實验描述及性能分析

本节模拟5000个箱子和200个货架的大型仓库环境，比较MH-C和SIS在重建效率和准确性方面的性能。在重建精度实验中，随机生成的真实分布矩阵和100个相应的RFID蕴含噪声的矩阵。在每个重建分布中，记录采样时间，计算平均K-L散度，5000例的最佳成功率（每个结果进行平均5000次位置查询）。

实验1：重建准确性

在本实验中，改变合格样本的数据、数据冗余度和每个阅读器管理货架的数目，研究这些因素对重建准确性的影响。

实验2：冗余度对算法性能的影响

接下来，通过改变数据的冗余度研究MH-C和SIS的重建准确度的性能。因为误报实际上是阅读器成功检测到了在次要检测区域的物体，使用在次要区域的读取率来定义数据冗余程度。越大的冗余程度表明一个阅读器越可能检测到邻近区域（货架）内的物体。

实验3：阅读器管理货架数目对算法性能的影响

为了使部署在仓库中的阅读器更加有效率，用户可能要为每个阅读器分配多个货架。目前实际应用场景中，一个普通的RFID阅读器的整体检测区域几乎没有超过5米的，因此设置每个阅读器管理货架数目从1到6变化。

5结论

实际应用中，RFID设备所接收的数据被是不可靠的。本研究提出采用贝叶斯推理方法清洗RFID原始数据，从而可以充分利用具有时空冗余的读数。为了估计位置信息和聚合查询结果，本方法采用先验知识来量化每个物体的不确定位置和每个区域的剩余容量，并且提出了n-状态检测模型捕获可能性，设计并实现了MH-C算法。实验证明本文提出的方法可有效的环境中从后验分布环境中符合约束采样，可以广泛地应用于物联网实际应用。

参考文献：

[1]L. Sullivan. RFID Implementation Challenges Persist， All This Time Later. InformationWeek， October 2005.

[2] M. J. Franklin， S. R. Jeffery， S. Krishnamurthy， F. Reiss， S. Rizvi， E. Wu， O. Cooper， A. Edakkunni， and W. Hong. Design Considerations for High Fan-In Systems： The HiFi Approach. In CIDR， pages 290-304， 2005.