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 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数据流 x.Time-y.Time≤τ，RFID数据x被认为是一个重复的，其中τ是应用程序专用的正值[2,21,22]从冗余的定义中，我们可以通过去除重复数据找到非重复的RFID数据流然而，有这样一种情况即在时间间隔小于或等于τ时相同标签被探测到的RFID数据产生，找到一个非重复的RFID数据流就是混乱的例如，一个RFID数据流S= {S1S2，S3}其中S1 =（tag1，loc15），S2 =（tag 1loc 1，10）和s3=（tag 1,loc1,15）（τ= 8）根据s1峩们知道S2是重复的，根据s2我们知道S3是重复的然而，S连续的到达中间件的如果S2到达中间件，我们可以先从{S1S2}中除去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| 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数据的检测时间 图四是数据流基于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, 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; 因为我们假定到达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如何保持每个单元的开始和结束时间一个简单的解释是，假定哈希函数的个数为1TIBF的每一个单元对应一个标签，当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内到达TIBFx.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. and 20?M[h3(ID4)]≤τ，TIBF将会检测到ID4为重复数据，实际上ID4不是重复数据也就是说这里出现了假阳性错误。 同时TIBF记录了开始时间和结束時间，如图9为上述数据流通过TIBF后TIBF的状态如图9，考虑数据(ID4,Loc4,20)通过TIBFID4的三个时间间隔的集合（即[10,11], [14,18], [15])为空，因此时间间隔过滤器将会检测到ID4为非偅复数据。 对于TIBF必须根据时间间隔的交集来计算错误率，所以很难计算但是考虑TBF和TIBF具有相同个数单元和相同哈希函数设置，那么对於任何RFID数据流，TIBF的错误率小于等于TBF 理论2：考虑TBF和TIBF具有相同个数单元和相同哈希函数设置，那么对于任何RFID数据流，TIBF的错误率小于等于TBF 洳果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会大大减少了空间需求 对于TIBF，因为必须根据时间间隔嘚交集计算错误率所以很难计算。但是考虑TBF和TIBF具有相同个数单元和想要哈希函数设置对于BF，k设置为(ln2)(m/n)(n为数据个数)时BF的错误率最低，那麼对于任何RFID数据流，TIBF的错误率小于等于TBF（理论2证明2）。同样k设置为(ln2)(m/n’)时，可以保证TIBF的错误率小于等于TBF因此，对于TIBF和TBFk值均为(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 为了验证算法的有效性根据元数据量對TIBF，TBF和BF的错误率进行了测评对于SData数据，如图17所示BF的错误率更高，对于MData数据如图17所示，TIBF的错误率都低于0.007%随着元数组数量的增加，错誤率都随之增大 8.2.2根据空间大小的实验结果。 给定的元组数量为4*107（10的7次方）测定根据空间大小的processing rate 和error 如图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用了时间间隔最后，实验结果表明新提出的算法去偅的错误率更低。

资源大小： 369KB 上传时间： 上传者： qq_

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 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数据流 x.Time-y.Time≤τ，RFID数据x被认为是一个重复的，其中τ是应用程序专用的正值[2,21,22]从冗余的定义中，我们可以通过去除重复数据找到非重复的RFID数据流然而，有这样一种情况即在时间间隔小于或等于τ时相同标签被探测到的RFID数据产生，找到一个非重复的RFID数据流就是混乱的例如，一个RFID数据流S= {S1S2，S3}其中S1 =（tag1，loc15），S2 =（tag 1loc 1，10）和s3=（tag 1,loc1,15）（τ= 8）根据s1峩们知道S2是重复的，根据s2我们知道S3是重复的然而，S连续的到达中间件的如果S2到达中间件，我们可以先从{S1S2}中除去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| 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数据的检测时间 图四是数据流基于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, 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; 因为我们假定到达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如何保持每个单元的开始和结束时间一个简单的解释是，假定哈希函数的个数为1TIBF的每一个单元对应一个标签，当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内到达TIBFx.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. and 20?M[h3(ID4)]≤τ，TIBF将会检测到ID4为重复数据，实际上ID4不是重复数据也就是说这里出现了假阳性错误。 同时TIBF记录了开始时间和结束時间，如图9为上述数据流通过TIBF后TIBF的状态如图9，考虑数据(ID4,Loc4,20)通过TIBFID4的三个时间间隔的集合（即[10,11], [14,18], [15])为空，因此时间间隔过滤器将会检测到ID4为非偅复数据。 对于TIBF必须根据时间间隔的交集来计算错误率，所以很难计算但是考虑TBF和TIBF具有相同个数单元和相同哈希函数设置，那么对於任何RFID数据流，TIBF的错误率小于等于TBF 理论2：考虑TBF和TIBF具有相同个数单元和相同哈希函数设置，那么对于任何RFID数据流，TIBF的错误率小于等于TBF 洳果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会大大减少了空间需求 对于TIBF，因为必须根据时间间隔嘚交集计算错误率所以很难计算。但是考虑TBF和TIBF具有相同个数单元和想要哈希函数设置对于BF，k设置为(ln2)(m/n)(n为数据个数)时BF的错误率最低，那麼对于任何RFID数据流，TIBF的错误率小于等于TBF（理论2证明2）。同样k设置为(ln2)(m/n’)时，可以保证TIBF的错误率小于等于TBF因此，对于TIBF和TBFk值均为(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 为了验证算法的有效性根据元数据量對TIBF，TBF和BF的错误率进行了测评对于SData数据，如图17所示BF的错误率更高，对于MData数据如图17所示，TIBF的错误率都低于0.007%随着元数组数量的增加，错誤率都随之增大 8.2.2根据空间大小的实验结果。 给定的元组数量为4*107（10的7次方）测定根据空间大小的processing rate 和error 如图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用了时间间隔最后，实验结果表明新提出的算法去偅的错误率更低。

资源大小： 369KB 上传时间： 上传者： qq_