基于自适应滑动窗口的RFID漏读数据清洗算法

褚　天,潘金满,杜　磊

(1.军事交通学院 研究生管理大队,天津　300161;2.军事交通学院 基础部,天津　300161)



基于自适应滑动窗口的RFID漏读数据清洗算法

褚天1,潘金满1,杜磊2

(1.军事交通学院 研究生管理大队,天津300161;2.军事交通学院 基础部,天津300161)

摘要RFID标签数据漏读问题普遍存在于RFID系统的应用中,为确保RFID数据的准确性,必须对原始数据进行清洗。针对当前最有效的滑动窗口清洗算法SMURF中存在的标签动态性检测的缺陷,文中在提出的改进算法中引入了标签概率运动模型进行判定,算法能准确检测到标签动态变化,并在窗口大小设置上更为合理。实验结果表明,文中所提出的算法比SMURF算法产生的平均错误数减少51%,性能更加优越。

关键词RFID;漏读;数据清洗;滑动窗口;标签运动

RFID(Radio Frequency Identification)是一种非接触式自动识别和数据获取技术。其将无线通信、数据管理和信号处理等技术融为一体,利用无线射频信号完成阅读器与电子标签之间的数据通信[1]。由于RFID技术采用无线射频信号进行数据通信,该信号易受环境影响,且相互间干扰较大,尤其当标签和阅读器数量增多时,信号之间的干扰加强,导致RFID数据更不可靠,严重影响了该技术的推广。RFID不可靠数据包括数据冗余(Duplication)、数据多读(False Positive)和数据漏读(False Negative)。在多数情况下,阅读器只能读取到其感应范围内60%～70%的标签数据,即至少有 30%的标签数据在读取时就被遗漏[2]。因此,为得到高质量的RFID数据,急需解决RFID数据漏读问题。

1RFID漏读数据清洗方法

针对RFID漏读数据的清洗方法有多种,但基于滑动窗口的数据填补算法是目前最实用、可行的方法。文献[3]中将静态时间窗口用于填补漏读的 RFID 数据。然而,使用静态时间窗口存在一些问题,如图1所示,若窗口设置过小,则有可能无法充分对漏读数据进行平滑处理,不能保证标签的完整性;窗口设置过大,又无法较好地监测标签的动态性。因此,理想窗口大小设置应综合考虑并合理设置,使得在保证不漏读数据情况下,准确地检测标签的状态转变。

图1　固定窗口平滑

(1)

(2)

为保证标签的动态性,滑动窗口的大小需要满足

(3)

SMURF算法在实现过程中将初始滑动窗口的大小置为 1,当窗口内发生阅读时,根据式(2)动态调整窗口大小以保证数据的完整性:如果调整后的窗口大小满足式(2)时,SMURF则会基于式(3)对标签的动态性进行监测。如果窗口大小不满足式(3),SMURF会将当前窗口缩小为原窗口大小的1/2,从而对标签状态的转变做出反应;否则,SMURF输出当前窗口,并滑动一个时间片的长度来进行下一次处理。若调整后的窗口大小不能满足式(2),则SMURF会将当前窗口以2为步长进行增大,以满足窗口设置的要求。SMURF算法实现的具体流程如图2所示。

图2　SMURF流程图

SMURF算法改进了定长滑动窗口大小难以确定的缺点,在静态标签下取得了较高的准确率,但当标签数目增大或者是标签频繁动态变化时,导致积极平滑或疲惫平滑现象较多,其重要原因是该算法对标签运动模式考虑欠缺[5],在标签的动态监测性方面只考虑到了标签在阅读器区域与不在区域两种情况。而实际上,这两种状态的转换也是要经历一个由量变到质变的过程,即标签的运动。本文在SMURF算法的基础上,提出一种改进的基于标签运动的RFID数据清洗算法DCATMS(Data Cleaning Algorithm of Tags in Motion Based on Sliding-window),DCATMS算法通过引入标签的概率运动模型来判断标签的动态跃迁性,进而动态调节滑动窗口大小,解决数据的完整性和动态性,更好地对RFID漏读数据进行填补。

2DCATMS算法设计

DCATMS算法采用的滑动窗口模型与SMURF类似,仍将RFID数据集当作统计学中的概率事件,即大量标签的随机样本。针对SMURF算法在标签动态性检测以及窗口大小设置方面的缺陷,该算法分别引入标签概率运动模型进行标签状态发生变化的判定,同时对窗口大小的设置进行改进。

2.1标签概率运动模型引入

RFID技术在实际应用中,通常会有标签进、出阅读区,反应到物理世界中就是标签位置的变化,即标签的运动过程。显然,标签的运动过程必然符合牛顿运动学定律。RFID 阅读器的识别半径通常为几m,最远不超过十几m。

RFID标签在阅读器识别区域内的运动速度通常较为平稳,而阅读器本身处于识别区域的中心,如图3所示。所以在一个较小的时间段Δt内标签的运动可被近似看作是过识别区域中心(圆心)的匀速直线运动或者是多个连续的匀速直线运动的组合。如果记d0为标签与阅读器的初始距离,根据匀速直线运动的性质显然可得

d=d0±vΔt

(4)

其中,v表示物体的运动速率。

为推断出d的值,将式(4)变为

d=a+bΔt

(5)

图3　阅读器识别区

其中,a=d0,b=±v。

首先估计未知参数a和b的值,且a和b值的准确度直接会影响到数据清洗的准确度。由式(5)可知,d与Δt成线性关系,所以可采用最小二乘法对参数a和b进行线性回归[6]。详细计算过程此处不再赘述,利用最小二乘法估算出参数a和b的值为

(6)

(7)

2.2DCATMS算法

DCATMS算法基本思路:在完整性方面,继续沿用SMURF算法保证完整性的条件。然而在对SMURF算法的实验中发现,将窗口大小每次线性增加2,则有可能导致窗口大小的不足而使得数据的平滑结果与实际情况相差较远。为此,本文采用一种对计算出新窗口大小与原窗口大小进行折中的方法来对窗口大小进行控制,即当计算出新窗口的大小大于原窗口大小时,将原窗口大小设置为新窗口大小与原窗口大小之和的一半。在标签动态性检测方面,通过上文标签运动模型进行准确判定。DCATMS算法基本流程如图4所示。

图4　DCATMS流程图

3实验结果与分析

为验证DCATMS算法的有效性,本文采用JT900R四通道射频阅读器,使用符合EPC CLASSI G2标准的标签50个,让标签以一定的速度通过阅读器,图5和图6所示为实验室环境下对算法进行测试。同时,为了验证算法的可扩展性,本文进行了大量的仿真实验,采用文献[7]中的方法生成仿真数据。如图7所示,横轴代表标签与阅读器之间的距离,纵轴表示标签被阅读器读取到的概率即阅读率。

图5　实验硬件

图6　实验硬件与软件测试

图7　仿真数据生成模型

实验中对标签进行了两种运动模式的研究:模式1是标签以不同速度匀速运动;模式2是标签随机运动[8-9]。实验参数设置如表1所示。

表1　实验参数设置

实验中,通过变化阅读器主识别区在整个阅读器阅读区中比例大小对数据进行实验,算法性能用每个epoch的错误阅读数来表示。错误阅读数是指当标签存在于阅读器范围内时,经算法处理过后并无阅读数据产生,或当标签在阅读器范围外时,经算法处理过后产生了阅读数据。通过大量实验数据,本文比较了固定大小的静态滑动窗口方法Static-x、SMURF算法和DCATMS的算法性能,并重点对比分析了DCATMS和SMURF算法的清洗效果。

3.1标签匀速运动算法清洗效果分析

实验分析了标签在匀速运动时,算法在不同速度下的平均错误数,标签匀速进出探测区域,速度在0～90 cm/epoch之间,实验记录了不同速度下每种方案产生的平均错误数。图8显示了实验结果。

图8　不同算法平滑结果

如图8所示,为标签速度不同时的RAW原始数据、固定窗口Static-5、Static-10、Static-20、SMURF算法和DCATMS的性能比较。结果显示随着标签运动速度加快,对固定窗口而言,小窗口更能捕获标签的运动状态的改变,性能相对较好。SMURF和DCATMS算法则由于能够根据阅读率和约束条件进行动态调节,能更准确地应对标签运动引发的状态变化,从而准确率相对较高且较为平稳,此外DCATMS算法对标签状态改变更加敏感,准确率更好。由图7显示的算法比较可知,DCATMS比SMURF平均错误数总体减少量约为50%,对漏读数据的填补效果更佳。

3.2标签随机运动算法清洗效果分析

实验分析了标签随机运动时算法在不同主识别区百分比的平均错误数和自适应清洗结果。标签在阅读器阅读范围内及范围外以0～90 m/epoch 的速度随机运动,主识别区的比率从0～1之间以步长为0.1选取11个值。较低的主识别区百分比模拟不可靠的环境,较高的主识别区百分比模拟可靠环境。图9显示了这项实验的结果。

图9　不同算法平滑结果

图9显示了固定窗口Static-5、Static-10、Static-20、SMURF算法和DCATMS算法在不同主识别区百分比的错误数比较。结果显示主识别区百分比较低时,标签阅读率较低,大的固定窗口平滑效果相对较好且较稳定,随着阅读率的提高,所有算法的准确度都随之上升,针对固定窗口而言,小窗口的平滑效果较好。SMURF和DCATMS算法相对固定滑动窗口整体效果较好,自适应性较高,且DCATMS算法平均错误数比SMURF总体减少量约为52%。

4结束语

本文分析了经典的RFID漏读数据清洗算法SMURF,针对该算法存在标签动态性检测以及滑动窗口大小设置方面的缺陷,提出了一种改进的RFID漏读数据清洗算法DCATMS。DCATMS算法中引入标签概率运动模型对标签的动态性进行准确判断,防止在填补漏读数据时造成积极平滑或疲惫平滑现象较多。同时,该算法选择了一种更为合理的方法来设置窗口大小。实验结果显示,标签在两种运动模式下,DCATMS算法的清洗效果比SMURF算法有显著提高,前者产生的平均错误数量比后者降低了51%,基本可以达到对RFID漏读数据的清洗要求。但DCATMS算法依然存在一定的缺陷。该算法中提出的标签运动模型仅考虑标签与阅读器之间的位置关系,由于RFID阅读过程的复杂性,其不仅能反映标签的位置信息,同时也能反映出标签读取的时刻。在标签动态检测机制中,若能将标签位置信息与时间相结合,可能会更加准确地判断标签的动态变化。此外,该算法有待在大量RFID标签的实际应用环境下进一步检验。

参考文献

[1]Want R.An introduction to RFID technology[J].Pervasive Computing,2006,5(1):25-33.

[2]Popovski P,Fyhn K,Jacobsen R M,et al.Robust statistical methods for detection of missing RFID tags[J].IEEE Wireless Communications,2011,18(4):74-80.

[3]Rizvi S,Jeffery S R,Krishnamurthy S,et al.Events on the edge[C].Boston:Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data,2005.

[4]Jeffery S R,Garofalakis M,Franklin M J.Adaptive cleaning for RFID data streams[C].Korea:VLDB,2006.

[5]樊华.面向物联网的RFID不确定数据清洗与存储技术研究[D].长沙:国防科学技术大学,2013.

[6]欧俊豪,王家生,徐漪萍,等.应用概率统计[M].2版.天津:天津大学出版社,2004.

[7]Jeffery S R,Garofalakis M,Franklin M J.Adaptive cleaning for RFID data streams[C].Porland:Proceedings of the 32nd International Conference on Very Large Data Bases,2006.

[8]陈翅刚.制造物联网海量RFID感知数据智能清洗处理技术研究[D].广州:广东工业大学,2014.

[9]封慧英,周良.基于滑动窗口的RFID自适应数据清洗算法[J].计算机与现代化,2015(1):31-36.

RFID Missing Data Cleaning Algorithm Based on Adaptive Sliding-window

CHU Tian1,PAN Jinman1,DU Lei2

(1.Postgraduate Training Brigade,Military Transportation University,Tianjin 300161,China;2.General Courses Department,Military Transportation University,Tianjin 300161,China)

AbstractThe original RFID data must be cleaned to ensure the accuracy of data due to the problem of RFID missing data in reading.In view of problems that exist in the SMURF,which is the most effective cleaning algorithm based on sliding-window in the current,this paper proposes an improved algorithm for accurately detecting the tag’s dynamic changing with a more reasonable mechanism to set sliding-window.The experimental results show that the proposed algorithm enjoys fewer errors and better performance than the SMURF algorithm during the cleaning.

KeywordsRFID;missing data in reading;data cleaning;sliding-window;tag motion

中图分类号TP391

文献标识码A

文章编号1007-7820(2016)04-024-05

doi:10.16180/j.cnki.issn1007-7820.2016.04.007

作者简介:褚天(1989—),男,硕士研究生。研究方向:交通信息工程及控制。潘金满(1984—),男,硕士研究生。研究方向:交通信息工程及控制。

收稿日期:2015- 09- 06