English
资源说明：RFID冗余数据近似消重
1.简介：
随着信息技术的发展,各种数据(如XML、RDF和RFID数据生成。RFID不需要接触即可检测射频识别标签的特性，因此被用于很多领域,如商业、军事和医学，导致了大量的RFID数据生成,沃尔玛采用RFID技术是一个典型的RFID在商业领域应用的例子。
然而，RFID技术也带来一系列的问题，由于RFID是非接触式探测，只要标签在阅读器的探测范围内，所有的标签信息都会被读到，因此，RFID标签在探测区移动缓慢或者停留都会产生冗余数据。另外，标签在探测区移动速度过快或者有多个标签同时移动，会造成阅读器漏读。为了避免漏读现象的产生，就会在一个区域放置多个阅读器，当同一个标签被几个阅读器读到时，冗余数据也就产生了。
一个智能的RFID阅读器能够去除自身产生的冗余数据，但是多个阅读器产生的冗余数据紧靠本身自包含的处理能力去除是不可能的，因此我们提出了一种基于中间件的处理冗余数据的技术。
上面这张图表示：有两个阅读器Reader1和Reader2，两个标签在探测区内，Reader1探测到标签用ID1,Reader2探测到标签用ID2表示，每个阅读器生成的信息表示形式为 :
.
Reader1探测到标签ID1产生RFID数据 : , , ，然而, RFID 数据是重复的除了.
.Reader1 也探测到了ID2的RFID 数据 , , 是重复数据.
同样的, Reader2 探测到的数据和产生的一些冗余数据在上图中都表示出来了。由于两个阅读器可能会探测到同一个RFID标签于是更多就会造成中间件中有更多的冗余数据。比如：Reader1， Reader2 就是冗余数据。中间件要进行去冗余处理，去冗余后结果为, .对于小数据的处理似乎是很简单的。
然而，RFID数据量是很庞大的，如果每个商品上都有一个标签，那么一个大型的零售商每天产生的数据将会超过1TB，并且，RFID数据是以流的形式产生的，也就意味着冗余数据在一个有限的内存中要立即进行去重处理，我们很难设计出一个精确的去冗余办法，因而，提出了一个近似去冗余方案去替代它。
有一种应用背景是这样的。我们要对大型百货商场中客户的移动进行实时分析，每个客户都有一个唯一的RFID标签，经理希望得到对客户的一些实时分析，比如：每个商店的顾客数量，哪个商店的顾客数量最多，百货商店的中间件就应该对这些数据进行去冗余处理。在这样的环境中，大量的重复数据同时进入中间件，特别是一个顾客长时间呆在同一个地方就会产生大量的重复数据，为了准确的去除冗余数据，我们需要在内存中长时间保存包括重复数据在内的所有RFID数据。当相对于RFID数据来说存储器的数量较少时，RFID数据实时去冗余也就很困难。在这个应用中，管理者是允许统计数据有误差，因而我们提出了在有限存储空间中的近似RFID去重技术。
Bloom filter是一种能够容忍误差的情况下被广泛应用的数据结构。要用少量的内存管理RFID数据流，我们设计了基于bloom filter的方法。然而，由于布鲁姆过滤器是针对静态数据，我们应该让bloom filter适应RFID数据流的环境。因此，我们提出了time bloom filter，由于要用少量的内存管理RFID数据流，我们设计了基于bloom filter的方法。然而，由于布鲁姆过滤器是针对静态数据，我们应该让bloom filter适应RFID数据流的环境。因此，我们提出了time bloom filter，由于time bloom filter是基于bloom filter的，它们不会产生假阴性错误，但是，它们可能产生假阳性错误。我们也计算出了time bloom filter的假阳性错误率，为了降低错误率，我们又提出了time interval bloom filter。
2.相关工作：
3.初期（基本bloom filter介绍）：
为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。
在判断a是否属于这个集合时，我们对a应用k次哈希函数，如果所有hi(a)的位置都是1（1≤i≤k），那么我们就认为a是集合中的元素，否则就认为a不是集合中的元素。A如果不是集合中的元素但却被误认为是集合中的元素。这就是一个false positive。
错误率：
当k=
时错误率最低。
4.问题说明：
系统结构如图 2所示，RFID数据流产生并进入中间件。中间件中有过滤模块和应用程序在。在原始RFID数据流进入应用程序之前，它通过过滤模块去除重复RFID数据，之后应用程序接收到非重复的RFID数据。即，在过滤模块中，重复的RFID数据被去除。
RFID数据是在许多RFID阅读器中连续地产生的。 RFID阅读器发送RFID数据到中间件。因此，中间件接收到一系列的RFID数据流。 其中RFID数据包括标签识别符（即，EPC），RFID阅读器的位置，检测标签的时间。
RFID数据流定义如下：
Definition1：数据流S（s1,s2,s3,……sn）,si=(TagID,Loc,Time),
在RFID数据流，，如果在RFID数据流中存在γ（≠x），使得x.TagID= y.TagID 和 x.Time-y.Time≤τ，RFID数据x被认为是一个重复的，其中τ是应用程序专用的正值[2,21,22]。从冗余的定义中，我们可以通过去除重复数据找到非重复的RFID数据流。然而，有这样一种情况，即在时间间隔小于或等于τ时相同标签被探测到的RFID数据产生，找到一个非重复的RFID数据流就是混乱的。例如，一个RFID数据流S= {S1，S2，S3}，其中S1 =（tag1，loc1，5），S2 =（tag 1，loc 1，10）和s3=（tag 1,loc1,15）（τ= 8）。根据s1我们知道S2是重复的，根据s2我们知道S3是重复的。然而，S连续的到达中间件的。如果S2到达中间件，我们可以先从{S1，S2}中除去s2。在这种情况下，如果S3到达中间件，因为不存在s2所以S3就判断为不是一个重复数据。（相同时间去定义重复）
根据不同的应用程序，非重复的数据流S的定义是不同的。
Definition 2：（不同时间定义重复数据）标签相同，出现时间间隔小于等于t即为重复。
Definition 3：集合S'（⊂S）为S的无重复数据集合，如果不存在x∈S'，则称x在S中属于重复数据。
Definition 4：集合S'（⊂S）为S中的最大无重复集合， x∈S-S’，则称x在S中属于重复数据。 Min=|Sˆ−S| / |S’| , Max=s’。
5.time bloom filter
为了去除冗余数据，我们提出了一个基于bloom filter 的简单的time bloom filter，从definition2 中可以知道，标签相同的RFID数据不一定就是冗余数据，因此，可以用时间信息来检测冗余。Bloom filter的位数组被设置成0或者1，TBF的数组设置成RFID标签的检测时间。也就是说，TBF用整数数组而不是一个bit数组。
TBF如图三所示。它使用k个相互独立的哈希函数（h1,h2,…..hk）,如BF一样映射到（0，….,m-1）.TBF第i个单元的值用M[i]表示。为了存储RFID数据x，找到h1(x.TagID),⋯,hk(x.TagID)对应的k个单元，TBF将K个单元的值设置为x的检测时间x.time。如果这个单元已经被设置成之前RFID数据的检测时间，TBF用当前RFID数据的检测时间。
为了检测RFID数据x是否是冗余数据，检测h1(x.TagID),….,hk(x.TagID)对应的k个单元，如果至少存在一个单元满足x.Time−M[hi(x.TagID)]>τ,那么x不是冗余数据（因为冗余数据产生在t时间内）。在TBF中，可以将x.Time−M[hi(x.TagID)]≤t看作BF中的1，x.Time−M[hi(x.TagID)]>τ看作BF中的0。
图四是数据流基于TBF的去冗余算法，这个算法能够在有限的存储空间中找到非重复的数据，TBF所有的单元初始值为0，当RFID数据到达中间件，通过TBF 的数据将被过滤，换句话说，数据x要么被过滤掉要么被发送给应用程序。首先，当数据x通过TBF的时候，检测x.Time-M[hi(x.TagID)]≤τ for all i∈{1, 2,⋯,k}是否全部满足来判断数据x是否是重复数据。因为所有单元的初始值都是0，如果当至少有一个单元的值为0时，数据x就不是重复数据。如果 x.Time−M[hi(x.TagID)]≤τ满足对于所有的 i∈{1, 2,⋯,k}没有满足 M[hi(x.TagID)]为0的，数据x可能就是重复数据，然后将x过滤掉，将非重复数据发送给应用程序，最后 x是否是重复数据都将单元的值更新为x.time。如果我们仅当数据不是重复数据的时候更新，那么当有相同标签的数据在小于t的时间间隔内连续出现时就不能进行被过滤掉。
例子1：如图五所示，图五表示数据流S={s1, s2, s3}在通过TBF过滤之后的TBF 的状态。s1=(ID1, Loc1, 10), s2=(ID2, Loc2, 120), and s3=(ID1, Loc1, 130).TBF的数组长度为8，哈希函数个数k为3，时间间隔t为100，为了很好的解释TBF，我们假定h2(ID1)=h1(ID2)。
考虑TBF如何处理数据流S={s1, s2, s3}，当s1到达TBF的时候，它将会检测s1是否是冗余数据，因为M[0],M[5],and M[2]的初始值都是0，s1不是重复数据，s1被发送给应用程序，然后TBF设置M[0],M[5],and M[2]的值为10。当s2通过TBF的时候因为没有重复数据，它被发送给应用程序，TBF设置M[5],M[7],and M[3]的值为120，对于M[5]单元，虽然之前的值10，但也被重新设置为120。s3通过TBF时，由于 130−M[0]>τ and 130−M[2]>τ，不是重复数据，s3发送到应用程序。TBF设置M[0],M[5],and M[2]的值为130.在这个例子中，因为没有数据是重复的，所以应用程序可以接受到所有的RFID数据。
TBF假阳性率（错误率）：
公式：
，其中k为哈希函数个数，n’ 为在t时间内非重复的元素个数，m为单元个数。
证明：为了得到错误率，我们假定到达TBF的数据流都是非重复的，然而，在真正的应用中，RFID数据流中有很多重复数据，这些数据流的标签相同，到达时间集中因而在TBF被哈希到相同的单元，单元设置的时间值相似。因而，重复数据到达TBF后被过滤和非重复数据到达TBF导致的TBF状态是一样的。因而，假定到达TBF的数据都是非重复数据是合理的。
思考，之前有RFID数据到达TBF，现在对于任意的元素x我们想计算其假阳性率。重复数据的定义是在时间t内到达的数据，也就是说在时间t内到达TBF的数据是无效的，因此，我们只考虑相对于x.time来说t时间内的数据。
P1为x.Time−M[hi(x.TagID)]≤τ for 1≤i≤k的概率，p2为x可能为重复数据的概率。
X的假阳性概率为：x=p1-p2;
为了得到p1，我们先得到对于u的x.Time−M[u]≤τ的 概率，我们假定哈希函数有统一的分布，对于在时间t内的RFID数据y来说概率为：hi(y.TagID)≠u for some i is （1−1/m），对于所有的i∈{1, 2,…,k}，hi(y.TagID)≠u的概率为 。
假定n’为在t时间内到达TBF的RFID数据的数量， 。
. 因为我们假定到达TBF的数据是非重复数据，因而，p2=0.
所有y的假阳性概率为： 。
6.time interval bloom filter
.
在前面的部分，我们介绍了TBF，TBF只是BF的一个简单扩展，我们提出了TIBF去优化TBF。
如图3即为TIBF的结构，M[i].StartTime和M[i].EndTime分别表示第i个单元的开始和结束时间，开始和结束时间的初始值分别为0和-1.考虑TIBF如何保持每个单元的开始和结束时间，一个简单的解释是，假定哈希函数的个数为1，TIBF的每一个单元对应一个标签，当RFID数据x（TagID=1）首先到达时，设置TagID=1对应单元的开始和结束时间为x.time，也就是初始时间间隔是一个时间点，当另一个数据y（TagID=1）到达时，仅仅改变TagID=1对应单元的结束时间为y.time。因此，TIBF保持了TagID=1对应的时间间隔，对RFID数据x，如果有x.Time-EndTime>t, x.Time-x.StartTime>t，时间间隔没有用，在这种情况下，初始化时间间隔，设置单元的开始和结束时间为x.Time.
因为一个单元可能被不同TagID的RFID数据设置，对于每个TagID的时间间隔可能被混合，但是，单元的间隔时间[StartTime,EndTime]涉及所有跟单元有关的RFID数据的检测时间。
为了确定RFID数据x是否是冗余数据，检查h1(x),h2(x),…hk(x)对应的所有时间间隔的交集是否为空。如果接收到的RFID数据TagID=x.TagID在时间t内到达TIBF，x.TagID对应的所有时间间隔应该包括了该数据的检测时间，并且其交集应不为空。因此，当交集为空，亏确定任何RFID数据TagID=x.TagID在时间t内没有到达TIBF..
图6说明了如何确认RFID数据x是否为冗余数据，图6中TIBF右侧坐标表示数据x对应的时间间隔，在图6（a）中，四个时间间隔的交集是[10,15]。因为交集非空，x是冗余数据。在图6（b）中，四个时间间隔的交集为空，x非冗余数据。
图7 为TIBF 去除冗余数据的算法，RFID数据x到达TIBF，首先检测x是否为冗余数据，为了检测x是否为冗余数据，首先要检查时间间隔对应的h1(x),h2(x),….,hk(x)的交集是不是空集，如果交集在x.time-t之前（即x.time-intersection.EndTime>t）,我们认为他是空集，因为重复数据定义在t之间之内的，当交集不是空集并且x. Time−intersectInterval.EndTime≤τ, 则认为数据x是重复数据并且将被过滤掉，否则将会被发送给应用程序。
例子2：考虑数据流{(ID1, Loc1, 10), (ID1, Loc1, 11), (ID2, Loc2, 14), (ID3, Loc3, 15), (ID2, Loc4, 17), (ID2,Loc2, 18)}.在解释TIBF的操作之前，我们先解释数据流通过TBF后的TBF的状态，哈希函数如图8,9所示，单元数组的长度为8，k为3，t为100，为了解释TIBF，假定h1(ID1)=h2(ID4), h1(ID2)=h1(ID4), and h3(ID3)=h3(ID4).如果(ID4, Loc4,20)通过TBF，因为20−M[h1(ID4)]≤τ, 20−M[h2(ID4)]≤τ and 20−M[h3(ID4)]≤τ，TIBF将会检测到ID4为重复数据，实际上ID4不是重复数据，也就是说这里出现了假阳性错误。
同时，TIBF记录了开始时间和结束时间，如图9为上述数据流通过TIBF后TIBF的状态，如图9，考虑数据(ID4,Loc4,20)通过TIBF，ID4的三个时间间隔的集合（即[10,11], [14,18], [15])为空，因此，时间间隔过滤器将会检测到ID4为非重复数据。
对于TIBF，必须根据时间间隔的交集来计算错误率，所以很难计算，但是考虑TBF和TIBF具有相同个数单元和相同哈希函数设置，那么，对于任何RFID数据流，TIBF的错误率小于等于TBF。
理论2：考虑TBF和TIBF具有相同个数单元和相同哈希函数设置，那么，对于任何RFID数据流，TIBF的错误率小于等于TBF。
证明：假定相同的数据流通过TBF和TIBF ，当数据被检测出来是重复时就会出现假阳性错误，证明，对于任何元素x，当被TIBF检测出为重复时，被TBF检测出也为重复。
假定TIBF检测x为重复数据。
Then
intersectInterval≠ϕ and x.Time−intersectInterval.EndTime ≤τ
ei ≥intersectInterval.EndTime for 1≤ i≤k
(also, si ≤intersectInterval:StartTime)
mi = ei ≥intersectInterval.EndTime [mi is M[hi(x.TagID)]
−mi≤−intersectInterval:EndTime
By adding x.Time in both sides,
x.Time−mi ≤ x:Time−intersectInterval:EndTime
Since x.Time−intersectInterval.EndTime≤τ by Eq. (1),
x.Time−mi ≤τ
所以对于任何元素x，当被TIBF检测出为重复时，被TBF检测出也为重复。
6.1空间优化：
如果TBF和TIBF的元素个数相同，那么TIBF需要的空间是TBF的两倍。但是，因为只有t以内的时间间隔有用，可以对TIBF的空间进行优化，如图10所示，时间间隔只需保存StartTime 和 EndTime−StartTime(DiffTime)代替了StartTime 和 EndTime，因为DiffTime所需空间小于EndTime。但是用如图7所示的算法运行的时候DiffTime的值可能会大于t，为了使DiffTime的值小于等于t，我们修改了算法如图11所示。StartTime和 EndTime需要保存数月，日，时，分，秒，但是t只是一个很小的值，因此保存DiffTime会大大减少了空间需求。
如图11所示，考虑空间优化后的TIBF算法，StartTime 和 DiffTime的初始值为0和-1，类似TIBF（）算法，TIBF_OPT()首先检查数据x是否为重复数据，EndTime可以通过DiffTime+StartTime计算出来。
为了保证t的值小于等于t，TIBF_OPT()更新单元值的方法与TIBF（）不同，当StartTime=0 或者x.Time−(StartTime+DiffTime)>τ时，设置StartTime = x.Time ， DiffTime = 0，当x.Time−StartTime>τ时StartTime = x.Time−τ ，DiffTime =τ，当x.Time−StartTime≤τ时，只设置DiffTime =x.Time−StartTime。
7.参数设置。
对于TIBF，因为必须根据时间间隔的交集计算错误率，所以很难计算。但是考虑TBF和TIBF具有相同个数单元和想要哈希函数设置。对于BF，k设置为(ln2)(m/n)(n为数据个数)时，BF的错误率最低，那么，对于任何RFID数据流，TIBF的错误率小于等于TBF（理论2，证明2）。同样，k设置为(ln2)(m/n’)时，可以保证TIBF的错误率小于等于TBF。因此，对于TIBF和TBF，k值均为(ln2)(m/n’)(n’为非重复数据的个数)。
8.实验
为了验证算法的有效性，我们设计了实验进行验证。比较了BF,TBF和TIBF处理数据额能力。实验环境：3GHz PC with 1 GB 主存。
8.1数据集
由于没有一个已知的数据集，我们生成了类似的合成数据，用检测模型去模拟RFID标签检测。
如果标签和阅读器的距离过远，标签将不能被检测到，随着标签靠近阅读器，标签被检测到的概率和距离成正比，这个区域被称作次检测区域，当标签和阅读器的距离较近时，标签被检测到的概率是恒定的，这个区域被称为主检测区域。
由于我们的目的是检测去重效率，所以假定标签是直线移动的，如图13所示。标签只在出发的时候产生，然后沿着直线移动，移动速度是标签生成时随机分配的，同一时间产生的标签分配的速度相同因为在现实的应用中，标签是一起移动的，标签到达目的地后就会消失，另外，为了提高检出率在检测区内存在多个标签和多个阅读器。我们分别在有一个阅读器和三个阅读器的检测区生成了107, 2×107, 3×107, 4×107, 5×107，和6×107（10的7次方）个元组。之前的数据称为SData 之后的数据称为MData。
8.2 实验结果
8.2.1显示的是根据元数据多少的实验结果，8.2.2显示的是根据空间大小的实验结果。
如图14.15所示为根据元数组大小的实验结果，对于数据SData和MData,BF的processing rate随着元数组的增加而增大,而TBF和TIBF的processing rate恒定。但是SData的processing rate小于MData，因为MData的k值较大（k值较小，在BF中访问的单元就比较小，因而，processing rate较大）。
为了验证算法的有效性，根据元数据量对TIBF，TBF和BF的错误率进行了测评，对于SData数据，如图17所示，BF的错误率更高，对于MData数据，如图17所示，TIBF的错误率都低于0.007%，随着元数组数量的增加，错误率都随之增大。
8.2.2根据空间大小的实验结果。
给定的元组数量为4*107（10的7次方），测定根据空间大小的processing rate 和error rate。如图18，,19所示随着空间的增大，BF,BTF,BITF的processing rate减少。
对于数据SDate,BF的processing rate比BTF和BITF高很多，对于数据MDate，BF的processing rate 比TBF和TBIF也高出一些，这是因为BF中MDate的k值比BTF和BITF中的K值增加的更多。
如图20和21为根据空间大小的错误率结果。随着空间增大BF的错误率保持恒定，而TBF和TIBF的错误率降低。而TIBF的错误率比起其他算法来是最低的，因为BF不能动态改变单元的值，并且元数组的数量越少错误率越高。
8.2.3优化k值
和BF类似，k值也影响TBF和TIBF的错误率，为了测试在第7部分提出来的K值是否有效，从1到10改变k的值去测试错误率，如图22和23所示，给定的空间大小为3*107（10的7次方），元数组数量为3*107（10的7次方），单个圆圈表示用第7部分公式测试的k值，双圆圈表示用BF的公式测试的k值。
实验结果表明虽然第7部分给定的K值不是最优解，但是计算出来的错误率最低。
9.结论
通常，RFID数据流中有大量的重复数据，由于数据是以流的形式产生的，所以要在很小的存储空间上去除重复数据是很困难的，因此，我们提出了近似去重方法，基于BF的TBF和TIBF。根据RFID数据中重复的定义是和检测时间有关的，我们用时间信息的整数代替了BF中的bit，为了降低错误率，TIBF用了时间间隔。最后，实验结果表明，新提出的算法去重的错误率更低。
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
