软件学报  2014, Vol. 25 Issue (8): 1713-1728   PDF    
基于有限状态机的RFID流数据过滤与清理技术
罗元剑1,2,4, 姜建国1,2, 王思叶1,3,4, 景翔1,2,4, 丁昶1,2,4, 张珠君1,2,4, 张艳芳1,2,4    
1. 中国科学院 信息工程研究所, 北京 100093;
2. 中国科学院大学, 北京 100049;
3. 北京交通大学 计算机与信息技术学院, 北京 100044;
4. 物联网信息安全技术北京市重点实验室(中国科学院 信息工程研究所), 北京 100093
摘要:为了实现从大量不可靠、冗余的RFID(radio frequency identification)流数据中提取有效信息,提高RFID系统中数据的质量,提出了一种基于有限状态机的RFID 流数据过滤与清理方法.实验结果表明:该方法能够有效过滤系统外标签数据,清理系统内部冗余标签数据,筛选有效标签数据,并能够降低漏读、误读带来的风险.最后,利用地理信息系统的可视化技术,将过滤与清理结果展示在地图上.
关键词RFID(radio frequency identification)     有限状态机     流数据过滤与清理     地理信息系统    
Filtering and Cleaning for RFID Streaming Data Technology Based on Finite State Machine
LUO Yuan-Jian1,2,4, JIANG Jian-Guo1,2, WANG Si-Ye1,3,4, JING Xiang1,2,4, DING Chang1,2,4, ZHANG Zhu-Jun1,2,4, ZHANG Yan-Fang1,2,4    
1. Institute of Information Engineering, The Chinese Academy of Sciences, Beijing 100093, China;
2. University of Chinese Academy of Sciences, Beijing 100049, China;
3. School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China;
4. Beijing Key Laboratory of IOT Information Security (Institute of Information Engineering, The Chinese Academy of Sciences), Beijing 100093, China
Corresponding author: WANG Si-Ye, E-mail: wangsiye@iie.ac.cn, http://www.iie.cas.cn/
Abstract: In order to extract useful information from a large number of redundant and unreliable RFID (radio frequency identification) streaming data and improve the data quality of the RFID system, a filtering and cleaning method based on finite state machine for RFID streaming data is proposed. According to the experiment, suppressing interference tag data, filtering redundant tag data and extracting effective tag data can be realized in this method with reduced risk of system omission and false positives. Finally, using GIS technologies the monitoring and tracking results are displayed on the world map.
Key words: RFID (radio frequency identification)     finite state machine     filtering and cleaning streaming data     GIS (geographic information system)    

RFID(radio frequency identification)无线射频技术具有自动识别、快速检测、降低人力资源成本等优点,已经成熟地应用到很多的行业中,例如物流行业、制药和保健行业、图书馆、非接触式ID卡和门票、资产管理、制造业、服装业、汽车工业、动物标识、交通管理、航空航天、军队等[1,2].多行业的广泛应用也带来了对RFID数据的更高要求.

由于RFID信号穿透水或金属能力弱、功耗低、无线信号多途径效应等原因,造成了数据的不可靠性.此外,大量RFID标签数据被系统读取也会造成RFID原始数据的冗余.不可靠性主要指系统外标签数据的读入、系统内标签数据漏读、误读.冗余性主要指大量标签数据重复、无效[3].如果将RFID原始数据直接在实际环境中应用,得到的结果往往没有价值,因此,系统要对RFID 原始数据进行过滤与清理,以提高RFID数据的质量.

本文针对基于RFID技术的监控和跟踪定位应用场景,提出了一种基于有限状态机的RFID流数据过滤与清理方法.实验结果表明:该方法能够有效排除系统外标签数据、清理系统内部冗余标签数据,筛选有效标签数据,同时降低系统漏读、误读带来的风险.

本文第1节介绍本文的研究背景和目前RFID数据过滤与清理方面的相关研究工作.第2节介绍基于监控和跟踪定位应用场景定义的RFID三元组数据模型和流数据处理架构.第3节针对RFID原始数据不可靠、冗余的问题,提出数据过滤与清理模型及算法.第4节对本文提出的方法的正确性、有效性进行实验证明.第5节对全文进行总结.

1 研究背景和相关研究工作 1.1 本文研究背景

本文所进行的研究主要针对基于RFID技术的监控和跟踪定位的应用场景.我们根据应用需求对实验场景进行了部署,如图 1所示,把实验室划分为4个监控区域,分别标记为area0,area1,area2,area3;在每个监控区域及边界部署多个检测天线和读写器,用于获取粘贴在被监控对象上的RFID标签信息.

Fig. 1 Illustration of application scenario图 1 应用场景示意图

· 应用需求1:监控被监控对象是否在监控区域,例如被监控对象在监控区域(area1),那么,监控系统需要每隔某个时间段(例如1小时)或者在某几个时间点(例如,9:00am,18:00pm,23:00pm)提示管理员,被监控对象还在监控区域.

· 应用需求2:跟踪定位被监控对象的位置信息,例如被监控对象最初在监控区域(area0),当被移动到其他监控区域(area1或者其他监控区域)时,监控系统应该立刻通知管理员,被监控对象从area0区域被带出,并被带入监控区域area1,并根据报警信息画出被监控对象的移动轨迹路线.

根据应用需求可知,监控系统具有实时性的特点,监控数据具有有序性的特点.怎样从大量不可靠、冗余的RFID流数据中提取有效信息,提高监控系统中的数据质量,对提高基于RFID技术的监控系统的监控效果起到关键作用.

1.2 相关研究工作

根据对相关文献的调研和研究,目前,提高RFID标签数据质量的解决方案主要有3种:第1种为物理层解决方案,提高RFID系统硬件来提高读写器的读取效率,以减少系统漏读;第2种为中间件层解决方案,把RFID数据存入数据库之前,利用一些数据清理的算法来提高数据质量;第3种为应用层解决方案,在数据库中,使用智能合并处理技术以达到数据清理的效果[4].

在物理层解决方案中,尽管采用C1G2协议[5]能够提高标签的识别率,较少数据的缺失率,但是标签与读写器的配置、多路径问题以及不可预测的干扰,会造成大量无效与冗余的数据[6].文献[6]中提出了一种结合数据分析(data analysis)和非单调推理的方法(non-monotonic)对漏读的数据进行恢复,但是该方法主要针对主动式RFID标签,在被动式RFID标签中并不能很好地应用;同时,在处理多个读写器接受到的RFID标签信息时,具有非时序的特性,对非单调性推理影响很大.

文献[7,8]针对在清理一定区域静态(非移动)RFID标签数据时,无法准确还原RFID标签数据的位置问题,分别采用了集合论和贝叶斯推导的方法.但是在实时性要求高、监控移动RFID标签的监控系统中,并不能得到很好的应用.

文献[9]提出了一种流水线数据清理的框架.该框架称为可扩展的传感器数据流处理(ESP).它根据阅读器所获得的数据在时间和空间上具有相关性对数据进行处理.数据清理过程是由点处理、平滑处理、合并处理、判决处理和虚化处理5个阶段组成的数据清理流水线,但是该框架处理流程比较固定,交换其中任意两个阶段的顺序,都会影响数据处理的效果.在平滑处理阶段,确定某个对象O在时刻t是否在某个位置上,不仅取决于阅读时刻t,而且依赖于预先设定的时间窗口W,但是阅读时刻t随机性比较大,时间窗口W难以设定.在合并处理阶段,将监控同一个逻辑区域的多个阅读器的阅读数据组合起来,以判断对象O在某个逻辑区域中的位置,这样一来,读写器的增加必定会产生大量冗余的数据.

文献[3]在时间窗口的基础上提出了两种RFID冗余数据的融合算法:一种为基本融合算法(BaselineMerge),另一种为哈希融合算法(HashtabelMerge).两种算法都假设所处理的RFID数据来源自于同一个读写器,即该算法只能在时间维度上对RFID冗余数据进行融合和过滤,提取有效数据,而不能提取多监控区域(多读写器)产生的有效RFID数据.同时,该方法只能设定1个时间窗口,不能满足监控系统中,任意时间段与某几个时间点上,监控系统对被监控对象是否在监控区域的提示.

针对文献[3,9]中难以设定适合的时间窗口的问题,文献[10]基于数理统计的方法提出了一种自适应的不可靠RFID数据统计平滑方法(statistical smoothing for unreliable RFID data,简称SMURF).基于数据的统计特性,连续采用平滑策略的统计方式,提出了二项分布标签数据清理模型和基于参量的多标签清理模型.但该方法主要针对单读写器情况下的数据清洗,对于多读写器的清洗工作,即多监控区域,只给出了一个初步设想,目前没有进一步的相关研究.

文献[11]在读写器识别标签时进行冗余数据处理,提出了一种RRE的解决方法.该方法可以使每一个RFID标签只能被唯一的读写器识别,从而解决了多个阅读器同时识别同一个RFID标签数据的问题.但是该方法在执行过程中,RFID标签将不断重写由读写器发送过来的读写器覆盖的标签数量以及读写器的标识符信息,不仅使传输时间变长,而且标签的重写操作需要更多的时间,对不能进行重写的RFID标签,该方法不能得到应用;同时,该方法并没意识到一段时间内读写器读取的静态标签数据中包含了很多冗余数据的问题.

文献[12]提出了两种基于数据仓库冗余数据清理模型.第1种模型为(EPC,location,time_in,time_out),其中,EPC(electronic product code)表示RFID标签编号.该模型假设相同标签在某一时间段内产生的数据都是冗余数据.第2种模型为(EPC list,location,time_in,time_out).该模型假设RFID对象在某一时间段倾向于一起移动和停留,因此可根据它们的位置来分组,相同组的数据可抽取一条,其他的为冗余数据.但是该方法在清除冗余数据时粒度过大,一些有效信息可能被清理.在实时性要求高的监控系统中,这种基于数据仓库的方法并不适用.

2 数据模型与系统架构 2.1 RFID三元组数据模型

根据应用场景需求,定义RFID三元组数据模型:{EPC,Position,Timestamp},其中,EPC表示RFID标签编号,可以唯一标识一个RFID标签;Position表示标签被读取的位置,由读写器IP与端口组成;Timestamp表示标签数据被读写器读取的时间,如下所示:

2.2 流数据处理架构

在传统基于数据库或者数据仓库的数据处理技术中,系统响应用户提交的SQL查询语句,返回查询结果.当数据规模很大时,数据往往以磁盘或者磁带为存储介质,因此,执行查询操作需要大量的I/O交换,效率低下;同时,用户需要主动发起查询,查询到的数据已经成为历史数据,不能适应监控系统实时性高的要求[13].本文基于流数据处理技术设计了RFID流数据过滤与清理架构.系统架构如图 2所示.

Fig. 2 Architecture of filtering and cleaning for RFID streaming data system图 2RFID流数据过滤与清理系统架构

监控系统主要分为数据采集前端,数据过滤与清理中间件,数据存储、展示、报警系统这3个部分.使用RFID设备中间件在数据采集前端不间断收集RFID编号EPC,读取读写器IP地址、天线编号、时间等信息;收集到的RFID数据将被传输到数据过滤与清理中间件中,过滤和清洗模型可以动态添加到数据过滤与清理中间件中,中间件根据过滤与清理模型对RFID流数据进行处理;处理后的RFID数据将主动推送到数据库服务器、GIS服务器、报警系统服务器,分别进行存储、展示、报警.

3 数据过滤与清洗模型及算法 3.1 有限状态机模型

根据应用场景和实际需求,本文提出了基于有限状态机的RFID流数据过滤与清理方法.下面根据应用场景,阐述有限状态机模型.有限状态机模型由一个五元组构成,记作M=(S,S,f,S0,Z),其中,

· S={状态i},S是一个有限集,其中每一个元素称为一个状态.

在该实验场景中,有两种状态集:一种为位置(position)状态,例如场景中的(area0,area1,area2,area3);另一种为时间状态,例如监控时间段{time0(9,10],time1(10,11],time2(11,12],time3(13,14]}.为了规范,定义RFID标签的状态为(state0,state1,state2,state3,state4,…,state(n-1),state(n)).在该实验场景中,状态信息被保存在state.xml配置文件中,内容如下所示:

· ={输入字符i},S是一个有穷字母表,它的每一个元素称为一个输入字符.

在该实验室场景中,输入字符为新进入数据过滤与清理中间件的每一条标签信息,即(EPC,Position,TimeStamp).其中,每一条标签信息都包含RFID标签号、位置状态信息与时间状态信息.

· 是状态转换函数,表示某状态接受某个新输入字符后所转变的状态.

在该实验场景中,状态转移函数为:如果当前一状态与当前输入的标签数据的位置状态、时间状态不相同,那么该RFID标签的状态更改为当前状态;如果相同,则保存原有状态.

· S中的一个元素,是唯一的一个初态.

在该实验环境中,S0表示,系统给被监控RFID标签预设定的初始状态,该状态可以为任意值.

· ,且S的一个子集,是一个终态集,或者称为结束集.

在该实验环境中,Z表示,被监控RFID标签最后一次状态改变后的状态.

3.2 相关概念定义

根据应用场景,下面定义本文应用到的一些概念.

定义1(系统外标签数据). 当某个不在监控范围内的对象(RFID标签)也被监控系统中的读写器读取到时,该数据称为系统外标签数据.

定义2(标签数据漏读). 当被监控对象(RFID标签)停留在监控区域或者经过监控区域时,没有被监控区域中的读写器读取到,这种情况下称为标签数据漏读.

定义3(标签数据误读). 当被监控对象(RFID标签)停留在某监控区域或者经过某监控区域时,在被该监控区域的读写器读取到,同时也被其他监控区域的读写器读取到该标签数据,这种情况下称为标签数据误读.

定义4(标签数据有效性). 在监控与跟踪定位系统中,只有在被监控对象(RFID标签)从某个监控区域移动到另一个监控区域时,监控时间从某个时间段跳转到下一时间段时,即有限状态机模型中的状态改变时,读写器获取的RFID标签数据才是有效的,如图 3中的实心部分所示.设经过系统过滤与清理后的有效数据的数目为EO,理论有效数据的数目为ER,ER等于系统内标签状态改变的次数之和.

Fig. 3 Distinction between valid data and redundant data图 3 有效数据与冗余数据区分图

理论有效数据ER的计算公式如下:

其中,TotalTimes表示状态转移的总数,TotalCounts表示被监控的标签总数.

定义5(标签数据冗余). 在监控与跟踪定位系统中,读写器在同一状态下读取的RFID标签数据为冗余数据,即图 3中的空心部分.在该实验场景中,主要有两种数据的冗余:物理空间位置冗余与时间冗余.物理空间位置冗余为同一监控区域中获取的被监控标签的数据,时间冗余为同一监控时间段内获取的被监控标签的数据.

定义6(数据检测率). 在1次或者多次被监控对象(RFID标签)经过监控区域时,RFID标签数据经过系统处理过后,获取的有效标签数据数目EO与理论有效标签数据数目ER的比,称为数据检测率,公式如下:

定义7(数据压缩率). 在1次或者多次被监控对象(RFID标签)经过监控区域时,系统采集到的所有RFID原始数据T与有效数据EO的比,称为数据压缩率,公式如下:

3.3 数据过滤与清洗算法

为了消除系统外标签数据,在系统配置文件中,配置被监控对象(RFID标签)的标签号EPC与对应的初始状态,即有限状态机中的初态S0.在监控的过程中,如果读取的RFID标签号EPC不在配置文件中,则认为该RFID标签数据为监控系统外标签数据,只需把该数据丢弃.

为了减少标签数据漏读的情况,在每个监控区域逐渐增加天线个数,以提高数据检测率(detection ratio),直到检测率到达预设值为止,例如100%.

为了消除标签数据误读的情况,首先设定一个标签数据阈值valueThreshold与时间阈值timeThreshold,如果某两个监控区域或者某几个监控区域在该时间阈值内监控到同一RFID标签原始数据T大于valueThreshold,则这两个监控区域或者该几个监控区域的物理空间位置是邻近的,即为同一个物理空间位置状态,应合并为一个监控区域;如果监控区域监控到的同一RFID标签原始数据T小于valueThreshold,则该RFID标签监控区域的物理空间位置不邻近,即,不在同一个物理空间位置状态.如图 4所示.

Fig. 4 Illustration of combining the adjacent monitoring areas图 4 合并相邻物理空间位置示意图

图 4中有3个监控区域,分别为监控区域1、监控区域2、监控区域3.每一区域内都部署有相同数目和型号的RFID天线以及读写器,在监控区域1中有一个RFID标签,时间阈值timeThreshold假定为1s,标签数据阈值valueThreshold假定为3,监控区域1与监控区域2检测到的该RFID标签原始数据T超过了3,则监控区域1和监控区域2在物理空间位置上是邻近的,应该把它们合并为同一物理空间位置,即,同一物理空间位置状态;在监控区域3中,监控到的RFID标签原始标签数据T低于阈值3,则物理空间位置不是邻近的,是不同的物理空间位置状态.

算法描述如下:

Initialize:

从配置文件state.xml中读取物理空间位置状态信息,并保存在Vector中(stateVector).Vector中的元素为物理空间位置状态信息和是否被测试(checked)

设置一个待测RFID标签testRFID

设置时间阈值timeThreshold与标签数量阈值valueThreshold

Begin

//设置状态迭代器

stateIterator=stateVector.iterator(×)

//判断迭代器是否还有下一个元素

While (stateIterator.hasnext(×))

//获取下一个未测试物理空间位置状态信息

If (stateVector.next(×).checked==true)

continue;

End If

testStatePosition=stateVector.next(×)

//标记该位置已经被测试

testStatePosition.checked=true

//获取待测RFID标签在区域testStatePosition下,timeThreshold时间内

//被其他checked为假的检测区域检测到的数量,并记录到一个hash表中

//hash表的key值为物理空间位置状态,value为该物理空间位置内检测到的RFID标签数量

rfidHashTable=getRFIDData(testStatePosition.Position,timeThreshold)

//如果rfidHashTablesize大于0,则说明,其他监控区域也检测到了该标签

If (rfidHashTable.size(×)>0)

//遍历整个物理空间位置状态

For (i=0; i<stateVector.size(×); i++)

//判断rfidHashTable是否包括了物理空间位置状态i

If (rfidHashTable.containsKey(stateVector.get(i).Position))

//判断该监控区域内获取的标签数据的数目是否大于valueThreshold

//如果大于valueThreshold,合并物理空间位置状态

If (rfidHashTable.get(stateVector.get(i).Position).Value>valueThreshold)

//合并物理空间位置状态

mergePosition(testStatePosition,stateVector.get(i))

//同时标记该位置已经被测试

stateVector.get(i).checked=true

End If

End If

END For

End If

End While

//把合并后的物理空间位置状态写回state.xml中

writeBackXML(stateVector)

End

· 空间复杂度

该算法需要保存物理空间位置状态,因此空间代价为.用HashTable存储检测区域检测到的被检测标签的数量,空间代价为,则该算法空间复杂度为.

· 时间复杂度

假设每次某一检测区间获取被检测标签的数量花费的时间为a,每次合并物理空间位置状态花费的时间b.

Ø 最坏情况下:物理空间位置两两相互独立(检测到的数量都小于阈值),那么花费时间代价为

Ø 最佳情况下:物理空间位置两两相邻,即第1次检测时,物理空间位置合并为一个检测区域,那么时间复杂度为

则该算法的平均时间复杂度为.

为了清理监控系统内的标签数据冗余,获取有效数据,根据有限状态机理论,只需要记录被监控对象(RFID标签)的上一状态的信息.当读写器读取新的RFID标签数据(EPC,Position,Timestamp)后,与该RFID标签的上一状态进行比较:如果状态一致,即标签数据是冗余的,就丢弃该信息;如果状态不一致,即数据是有效的,就更新该RFID标签的状态信息,并把该RFID标签数据分发到数据库服务器、GIS服务器、报警系统服务器,分别进行存储、展示、报警,如图 5所示.

Fig. 5 Illustration of filtering the redundant data图 5 冗余数据过滤示意图

算法描述如下:

Input: newRFIDInfo(EPC,Position,Timestamp).

Initialize:从配置文件state.xml中读取状态信息,保存在hash表中(stateHashTable),初始化另一个hash表(rfidHashTable),存放被检测的RFID标签的的标签号与初始状态,key值为被检测的RFID标签号,value为初始状态,可以为任意状态值.

Begin

//在stateHashTable中,根据newRFIDInfo中的PositionTimestamp信息,查找该标签对应的状态,并

//把该状态保存到一个临时变量中,newState

newState=findNewState(stateHashTable,newRFIDInfo)

//如果该标签数据,它的物理空间位置状态与时间状态都与state.xml中所规定的状态信息不符合,

//即不再规定范围内,此时,newState的值为空

If (newState==NULL)

//非监控内标签(非法数据),丢弃,并跳过后面的检查操作,执行下一条新到来的数据

continue

End if

//在rfidHashTable中,根据newRFIDInfo中的EPC,查找该标签对应的上一状态信息,如果查找失败

//返回NULL,查找成功返回状态信息,并保持在oldState

oldState=findOldState(rfidHashTable,newRFIDInfo)

If (oldState!=NULL)

//oldStatenewState进行匹配,如果相等,则丢弃该信息,

//如果不相等,则更新rfidHashTable中该标签对应的状态

If ((oldState.Position==newState.Position) && (oldState.Position==newState.Position))

//丢弃该信息

Else

//在rfidHashTable中,更新该标签对应的状态

updateRFIDState(rfidHashTable,newState)

//并把该信息保存到数据库中、传输到报警系统中、显示在地图上

dispatchRFIDInfo(newRFIDInfo)

End if

Else

//系统外标签,不做处理

End if

End

· 空间复杂度

存储状态信息需要,存储被检测标签的数量,则该算法空间复杂度为.

· 时间复杂度

查找状态信息需要O(1),更新被检测标签的时间复杂度需要O(1),所以该算法的时间复杂度为.

4 实 验

在每个监控区域内分别部署1台UHF频段无源读写器,每台读写器连接4支检测天线,分别放在监控区域的4个角.每个读写器的功率衰减为60DBM,监控区域之间的距离可调,监控区域0,1与监控区域2,3之间用非金属挡板隔离.用于实验的读写器是Alien 9800,配套天线是圆极化天线Alien 9600BC,实验标签是Alien H3标签.Alien 9800与服务器之间用网线连接,每个读写器都有自己的固定IP地址,每个读写器的4支天线接口分别用port0,port1,port2,port3标识.计算机实验环境见表 1.

Table 1 Experimental envionment 表 1 实验环境

实验中,令穿过监控区域的测试人员的步行速度保持在4m/s左右;采用两个Alien H3类型的标签作为系统内被监控对象,采用一个Alien H3类型的标签作为系统外标签;并规定area0®area1®area2®area3为一次路过,area3®area2®area1®area 0也为一次路过,每次路过,物理空间位置状态发生3次改变,即有效标签数据为3条.

实验1. 针对标签数据漏读的情况,在每一个监控区域,逐渐增加天线个数来提高数据检测率,以降低标签数据漏读的情况.实验为3组,分别部署1对天线、2对天线、4对天线.测试人员携带2个被监控标签,路过监控区域30次,理论有效数据应为182条数据,实验结果如图 6所示.

Fig. 6 Result of processing negative data图 6 处理漏报数据结果

实验1表明:在同一个区域增加RFID检测天线的数量,可以减少RFID标签数据的漏报,当增加的天线数目达到一定量时,检测率可以达到100%;同时,随着天线数量的增加,获取的RFID标签总数也在增加,即冗余数在增加,压缩率也在增加.

实验2. 针对标签数据误读的问题,设定时间阈值为2s,标签数量阈值为0,最后通过标签数据误读消除算法,合并相邻的物理空间位置状态,确定了当监控区域之间的距离为2m时,系统误报率为0.实验2通过合并相邻的物理空间位置状态可以消除标签数据误读的情况.

为了验证本文提出的算法(FiniteStateMerge)对过滤与清理冗余数据和提取有效数据的有效性,在实验1和实验2结果的基础上,确定在每个监控区域分别部署2对天线,监控区域之间的距离为2m,做了关于物理空间位置状态冗余数据过滤与清理和有效数据提取的实验3和关于时间状态冗余数据过滤与清理和有效数据提取的实验4.

实验3. 物理空间位置状态冗余数据的过滤与清理和有效数据的提取.设监控时间段为[00:00:00,23:59:59],以保障有限状态机模型中的时间状态为同一状态,在前3组实验中,逐渐增加物理空间位置状态的个数,同时设定在每一个物理空间位置状态内停留的时间为3s,测试人员携带2个被监控标签,路过监控区域10次.第1组的物理空间位置为[area0,area1],理论有效数据位ER=11 x2=22(条);第2组的物理空间位置为[area0,area1,area2],理论有效数据为ER=21x2=42(条);第3组的物理空间位置为[area0,area1,area2,area3],理论有效数据为ER=31x2=62(条);在第4组实验中,物理空间位置为[area0,area1,area2,area3],但停留时间变为5s,理论有效数据ER=31x2=62(条).实验结果如图 7~图 10所示.

Fig. 7 Two monitoring areas图 7 Two monitoring areas

Fig. 8 Three monitoring areas图 8 3个监控区域

Fig. 9 Four monitoring areas for 3s 图 9 4个监控区域停留3s

Fig. 10 Four monitoring areas for 5s图 10 4个监控区域停留5s

实验3在确保系统漏读数与误读数为0与时间状态相同的前提下,系统过滤出的有效数据EO和理论有效数据ER一致,即,检测率为100%.这表明本文提出的算法能有效过滤与清理相同物理空间位置状态下的冗余数据,提取有效数据.前3组实验表明:随着物理空间位置状态的个数的增加,系统的压缩率基本保持不变,即监控区域的个数与压缩率无关.第3组与第4组实验表明:压缩率和标签在物理空间位置中停留的时间相关,停留时间越长,压缩率越大.

实验4. 时间状态冗余数据的过滤与清理和有效数据的提取.放置2个被监控标签在area1中,以保障有限状态机模型中的物理空间位置状态为同一状态,

在前3组实验中,每组的时间区间为timei[beginTime+timeLengthxi,beginTime+timeLength(i+1)],时间间隔(timeLength)相同,都设为5s,第1组i的取值[0,5],理论有效数据为ER=5x2=10条;第2组i的取值为[0,10],理论有效数据为ER=10x2=20条;第3组i的取值为[0,20],理论有效数据为ER = 20x2=40次;第4组i的取值为[0,5],但时间间隔timeLength=10s,理论有效数据ER=5x2=10条.实验结果如图 11~图 14所示.

Fig. 11 5 counts of time interval图 11 5个时间区间

Fig. 12 10 counts of time interval图 12 10个时间区间

Fig. 13 20 counts of time interval 图 13 20个时间区间

Fig. 14 5 counts of time interval图 14 5个时间区间

实验4在确保系统漏读数与误读数为0与物理空间位置状态相同的前提下,系统过滤出的有效数据EO和理论有效数据ER一致,即检测率为100%.这表明该算法能够有效过滤与清理相同时间状态下的冗余数据,提取有效数据.前3组实验表明:随着时间区间的个数的增加,压缩率基本保持不变,即时间区间个数与压缩率无关.第1组实验和第4组实验表明 :压缩率和时间状态的时间间隔相关,时间间隔越长,压缩率越大.

实验5. 在实验1和实验2的基础上,用本文提出的冗余数据过滤与清理方法(FiniteStateMerge)和文献[3]中提到的BaselineMerge与HashtableMerge方法做了如下的对比实验:

实验用3个Alien H3标签,ID分别为tag1,tag2与tag3,tag1,tag2为系统内标签,tag3为系统外标签.实验模拟3 000次路过,每个标签在每一个监控位置产生5条标签信息,则系统产生的标签数据总数为

3000(路过次数)x3(1次路过经过的监控区域的个数)x3(标签总数)x

5(每次产生的标签数)+3x5(刚进入系统时标签数)=135015(条).

同时,设定从一个监控区域移动到另一个监控区域的时间间隔1s.文献[3]中提到的两种方法都是基于时间窗口的方式进行冗余数据的过滤与清理.为了与实验场景保持一致,设定时间窗口为3s,即一次路过的时间.理论有效数据为ER=(3001)x2=6002,其中,3 001为时间窗口总个数,2为系统内标签数据.为了与文献[3]中的方法进行比较,设定每隔3s 为一个时间状态,那么时间状态改变总数为3 001.同时,物理空间状态改变总数为3000x3+1=9001.因此,理论有效数据位ER=(3001+9001)x2=24004(条),实验结果如图 15所示.

Fig. 15 Three methods of duplicate elimination: FiniteStateMerge,BaselineMerge,HashtableMerge图 15 3种冗余消除算法:FiniteStateMerge,BaselineMerge,HashtableMerge

由实验结果可知:本文提出的过滤与清理冗余数据提取有效数据的方法(FiniteStateMerge)过滤出的有效数据EO与理论有效数据ER一致,即检测率为100%.这表明该算法能够有效过滤与清理相同状态下的冗余数据,提取有效数据.同时,文献[3]中的方法不能有效地识别系统外标签tag3,只能从时间维度上对冗余数据进行清洗,时间窗口一旦设置就不能变化,且大小不易设置.此外,一些有效的数据也被清理掉了,例如监控系统需要在某几个时刻通知管理员时产生的数据和被监控对象从一个监控位置移动到列一个监控位置时产生的数据.从时间性能上看,本文提出的方法(finiteStateMerge)需要一点额外的时间从配置文件中读取状态信息与系统内标签,总体上与HashtableMerge用时一致.

最后,结合地理信息系统技术,把测试人员携带两个被测标签路过一次实验场景的数据,不经过本文提出的方法处理与经过本文提出的方法处理后,分别显示在地图上,如图 16图 17所示.

Fig. 16 Display RFID datawithout processing method图 16显示未处理的RFID数据

Fig. 17 Display RFID datawith processing method图 17 显示处理后的RFID数据

实验总结:

在实验1中,不断增加天线数量,可以减少对被监控标签漏读的情况.当天线数量增加到一定量时,漏读标签数可以为0.与文献[6]相比,该方法通过增加冗余数来减少系统对被监控标签的漏读,再通过本文提出的过滤与清理冗余数据的方法提取有效数据,在硬件相对便宜的情况下,该解决方案有一定的实用价值,同时实用于主动式与被动式RFID标签、多读写器的应用场景.

在实验2中,不断合并相邻物理空间位置状态,可以减少被监控标签误读的情况.当物理空间位置相隔较远时,误报数可以为0.本文获取的被监控标签数据为三元组模型数据,即{EPC,Position,Timestamp},再通过合并相邻物理空间位置,排除误读情况,就能判断被监控标签在哪个监控区域.与文献[7,8]相比,该方法可操作性更强,效果也更佳.

在实验1和实验2的前提下,实验3~实验5表明:本文提出的基于有限状态机的过滤与清理方法能够有效地过滤与清理同一状态下的RFID标签数据,提取有效监控数据.与传统的基于时间窗口的RFID流数据过滤方法(文献[3,9,10])相比,该方法不仅能够从时间维度上对数据进行过滤与清理,而且能够提取特定监控时间段内的数据,同时可以从物理空间位置维度上对数据进行过滤与清理,提取有效的监控数据,并过滤掉系统外标签数据,即干扰数据.文献[11]在读取标签数据时、文献[12]在标签数据存入数据仓库后对冗余标签数据进行过滤与清理,与之相比,本文提出的方法实时性更高,可操作性更强,代价相对较小.此外,该方法也能实用与快速移动的被监控对象,但前提是被监控对象能被监控系统所识别.

5 结束语

本文针对在基于RFID技术的监控和跟踪定位应用场景实现过程中要求实时性较强的特点,提出了一种流数据处理框架,被监控数据通过数据过滤与清理中间件处理后,实时的主动推送到数据库服务器、GIS服务器、报警系统服务器;然后,针对在实现过程中产生的大量不可靠、冗余的RFID数据的问题,提出了一种基于有限状态机的RFID流数据过滤与清理方法.该方法利用RFID标签数据的三元组模型(EPC,Position,Timestamp)与有限状态机理论,一方面根据信号读取位置建立等效的物理空间位置状态模型,对相邻物理空间位置状态进行合并,以降低系统对被监控对象(RFID标签)的误读;另一方面,通过对RFID流数据的分析,对同一物理空间位置状态与时间状态内的冗余数据进行过滤与清理.实验结果表明:该方法能够排除系统外标签数据、清理系统内部冗余标签数据,筛选有效标签数据,并降低漏报、误报带来的风险,在基于RFID技术的监控与跟踪定位系统上有一定的实用价值.

致谢   在此,谨向对本文的工作给予支持和建议的同行,尤其是中国科学院信息工程研究所的黄伟庆研究员、朱大立研究员及组内的其他老师表示感谢.

参考文献
[1] Derakhshan R, Orlowska ME, Li X. RFID data management: Challenges and opportunities. In: Proc. of the 2007 IEEE Int' Conf. on RFID. IEEE, 2007. 175-182
[2] Ahsan K, Shah H, Kingston P. RFID applications: An introductory and exploratory study. IJCSI Int' Jornal of Computer Science Issues, 2010,7(1):1-7.
[3] Bai YJ, Wang FS, Liu PY. Efficiently filtering RFID data streams. In: Proc. of the CleanDB. 2006.
[4] Darcy P, Stantic B, Sattar A. A fusion of data analysis and non-monotonic reasoning to restore missed RFID readings. In: Proc. of the 2009 Int' Conf. on Intell. Sensors, Sens. Networks Inf. Processing. IEEE, 2009. 313-318 .
[5] EPCglobal Inc. EPCTM Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz-960 MHz. Specification for RFID Air Interface, 2008.
[6] Massawe LV, Vermaak H, Kinyua JDM. An adaptive data cleaning scheme for reducing false negative reads in RFID data streams. In: Proc. of the 2012 IEEE Int' Conf. on RFID. IEEE, 2012. 157-164 .
[7] Pupunwiwat P, Stantic B. Location filtering and duplication elimination for RFID data streams. Int' Journal of Principles and Applications of Information Science and Technology, 2007,1(1):29-43.
[8] Chen HQ, Ku WS, Wang HX, Sun MT. Leveraging spatio-temporal redundancy for RFID data cleansing. In: Proc. of the 2010 Int' Conf. on Management of Data-SIGMOD. 2010. 51 .
[9] Jeffery SR, Alonso C, Franklin MJ, Hong W, Widom J. A pipelined framework for online cleaning of sensor data streams. Technical Report, UCB/CSD-5-1413, UC Berkeley, 2005.
[10] Jeffery SR, Franklin MJ, Garofalakis M. An adaptive RFID middleware for supporting metaphysical data independence. The VLDB Journal, 2008,17(2):265-289 .
[11] Bilenko M, Mooney R. Adaptive name matching in information integration. In: Proc. of the IEEE Intelligent Systems. 2003. 16-23 .
[12] Gonzalez H, Han JW, Li XL, Klabjan D. Warehousing and analyzing massive RFID data sets. In: Proc. of the 22nd Int' Conf. on Data Engineering. IEEE, 2006. 83-94 .
[13] Jin CQ, Qian WN, Zhou AY. Analysis and management of streaming data: A survey. Ruan Jian Xue Bao/Journal of Software, 2004, 15(8):1172-1181 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/15/1172.htm
[13] 金澈清,钱卫宁,周傲英.流数据分析与管理综述.软件学报,2004,15(8):1172−1181. http://www.jos.org.cn/1000-9825/15/1172.htm