无线射频识别作为一种实时数据采集技术, 被广泛应用于物流、资产追踪、设备监控等领域[1,2]。但由于RFID数据具有客观不可靠性, 容易产生冗余数据或时间戳乱序现象[3]。如果由上层应用系统来解析如此巨大的RFID数据, 不仅会造成系统处理业务逻辑的效率低下, 而且开发的系统也不利于扩展[4]。

国内外学者围绕RFID不确定性数据清洗问题展开了一系列研究。JEFFERY, GAROFALAKIS等人[5]针对标签数据清洗最早提出了一种自适应滑动窗口的数据清洗算法, 通过构建标签数据清洗模型对标签漏读、脏读等现象进行处理, 从而为上层应用提供可靠的数据[5];MASSAWE, KINYUA等人[6]在JEFFERY研究的基础上针对RFID数据的不可靠性提出一种自适应滑动窗口处理方法, 有效处理了动态环境和标签下的数据处理;为了解决冗余数据的处理效率问题, 贾红梅、李文杰[7]分析了仓储中标签冗余和阅读器冗余问题产生的原因, 并给出了解决这两种冗余的数据过滤模型。FAN, WU等人[8]设计并部署了一种基于标签行为的RFID数据清洗系统, 并使用了一种通用的RFID应用程序来验证该方案的有效性, LI, LIU等人[9]针对RFID系统中发生的数据流乱序现象提出了一种优化序列扫描和构建的方法。

本研究以仓储环境为对象, 针对冗余数据清洗问题, 提出队列缓存机制实现在线清洗数据。

由于现场环境和读写器设备本身性能的影响, 在每一个读写器采集位置都有可能产生冗余数据和乱序事件。如果能在实际环境中抽象出具有通用特征的场景, 则更加便于RFID仓储中数据的清洗。

数据冗余主要包括:单数据源冗余和多数据源冗余两方面[10]。

以RFID仓储为例其抽象场景如图1所示。

图1 冗余数据产生场景抽象  下载原图

单数据源冗余主要指当标签进入读写器R1~R4射频范围内, 由于RFID读周期为0.2 s左右, 假设时间窗口为w, 那么在[t, t+w]时间范围会产生大量的具有相同Tag_ID的三元组数据。多数据源冗余指不同位置的读写器覆盖范围重叠现象, 如图1右边所示, R6和R7的读写器覆盖范围重叠, 则会产生交叉冗余数据。假设在某一位置存在m个读写器, 有m×n个固定位置的标签和k个等待判定位置的标签, 为了方便后续对相关清洗算法地讨论现在对本文相关概念做如下定义:

定义1读写器元组。为了方便冗余数据过滤论文将标签原始数据扩展为五元组<Tag_ID, Reader_ID, Reader_Grp, Time_Start, Time_End>, Reader_Grp属性用于表示读写器所在的位置属性。

定义2确定位置标签信号强度。假设已知标签Tagi其属于读写器Readerj, 那么Tagi相对于Readerj的信号强度用Fj, i表示, 其中i∈ (1, ……n) , j∈ (1, ……m) 。

定义3待判定位置标签信号强度。假设待判定位置标签Tagi相对Readerj信号强度用Wl, j表示, 其中l∈ (1, ……k) , j∈ (1, ……m) 。

定义4标签位置相似度。通过欧式距离公式计算Wl, j和Fj, i之间的距离Dl, j, 如果该距离很小那说明该位置不确定的标签Tagl属于该读写器j, 去计算公式为:

定义5冗余数据产生条件。在某一确定时间范围内, 当读写器读到相同的标签时, 就有可能产生冗余数据, 其条件需同时满足:

在实际的RFID仓储应用环境中, 通常会分布式部署RFID读写器设备, 然后通过TCP/IP或者RS232等传输方式将各个位置所采集到的标签数据以事件流的形式聚集到后台处理引擎中。在理想状态下先发生的RFID简单事件先到达后台数据处理系统, 但是由于仓储现场可能存在通信故障、网络延迟等问题, 可能造成发生早的事件反而到达事件处理引擎的时间更晚[11,12], 其抽象场景如图2所示。

图2 乱序事件产生场景  下载原图

以入库流程为例, 在质检、入库和上架3个位置分别部署RFID读写器, 假设其触发的事件分别为A、B和C, 使用TA代表A事件从发生到达系统的时间, TA-B代表货物从A移动到B的时间, 其他事件时间以此类推。如果满足表达式:TA>TA-B+TB, 则说明先发生的A事件后到达, 则产生事件流乱序问题[13], 在时间戳上先发生的事件后到达则会产生乱序问题。

如果需要对RFID数据进一步挖掘, 那么必须对采集的数据进行处理才能上传至上层应用系统, 否则会造成后台系统的业务逻辑设计困难[14]。面向仓储的RFID数据清洗模型如图3所示。

图3 RFID仓储数据清洗模型  下载原图

该数据清洗模型结合冗余数据清洗算法和乱序事件流修正方法, 对RFID读写器网络所采集到的原始数据进行过滤, 最后将干净的数据上传至上层应用系统中进行处理。

本文以多数据源冗余问题为主要对象设计相关算法, 引入标签位置相似性的方法来判断标签所属读写器分组, 并采用互斥原理来消除不同读写器之间的交叉冗余数据。其核心伪代码为:

算法中输入的参数是读写器原始数据流, 输出的参数是清洗后的标签元组映射表, 具体步骤为:

(1) 读写器网络不断推送原始数据流至系统中, 算法首先对标签编码进行判断, 如果标签编码符合规则, 则进入 (2) , 否则丢弃该标签数据;

(2) 根据当前标签的Reader_Grp属性判断当前标签所对应的队列是否存在, 如果已经存在, 则进入对应的标签缓存队列中, 否则新建一个属于该读写器组的标签缓存队列CQi, 如果标签无法判断其位置信息, 则进入 (3) , 否则进入 (4) ;

(3) 根据定义4和公式 (1) , 通过Computer Sig-nal Intensity () 计算标签位置相似度, 根据欧式距离计算结果大小来判断该标签属于哪个读写器, 通过最小化相对位置相似度的方法来裁决该交叉冗余数据所属读写器, 判定位置后可以利用互斥原理消除交叉冗余数据;

(4) 与当前标签缓存队列中的最后一个标签数据的Tag_ID进行对比, 如果标签编号满足Tag_IDi=Tag_IDj并且时间约束满足 (Timei=Timej) ∨|TimeiTimej|<=Threshold, 则标签当前标签在短时间内出现了重复读取, 那么就剔除旧数据并更新当前数据的最新时间信息, 如果不满足约束条件, 那么判断当前对比的标签否为队列中的第一个, 如果不是就继续循环对比, 如果已经对比结束则进入 (5) ;

(5) 将新数据存入缓存队列并用Sort () 方法按到达时间进行排序, 如果当前还有数据流需要处理, 则继续 (2) , 否则进入 (6) ;

(6) 将所属同一读写器组的标签元组数据进行合并, 最后输出清洗后的数据。

目前提出的乱序事件流修正框架通常采用Hash加单链表结构进行数据存取[15], 采用双链表结构有利于提高数据的操作效率。

本文提出的乱序事件流修正模型如图4所示。

图4 RFID乱序事件流修正模型  下载原图

TID—Tag_ID;RID—Reader_ID;C—事件数量;Timer—计时器

Hash主表中的每一个位置指向一个主链结点, 每一个主链结点包含当前的事件类型、事件数量、计时器以及其第一个子链结点的地址。本研究用链地址法将具有相同事件类型的RFID事件构成一个双向链表, 通过主链结点的地址可以找到所有链表中的子节点, 其流程图如图5所示。

图5 RFID乱序事件修正方法流程  下载原图

实验采用C#语言在win764bit、内存为8 G的操作系统上实现, 标签数据通过多线程随机产生.

读写器检测模型如图6所示[16,17]。

图6 读写器检测模型  下载原图

随着标签与读写器距离的变化, 相关读写器读取参数也会随之改变, 其中横坐标表示标签与读写器之间的距离, 纵坐标表示读写器检测到标签的概率。该模型检测区域主要分为Major detection region和Minor detection region两部分。当标签与读写器之间的距离超出DetectionRange时, 读写器将检测不到标签信号, 检测概率随着距离的增大而线性递减。实验中设定如下指标验证算法的性能:

(1) 记录数。经过冗余数据清洗后的标签存储数量;

(2) 正确率。经过乱序修正后可以正确输出的事件流比例。

实验中冗余清洗和乱序修正实验的参数分别如表1、表2所示。

表1 冗余清洗实验参数  下载原图

表2 乱序修正实验参数  下载原图

为了验证本研究所提方法的有效性, 实验中采用记录数和准确率来分别对比冗余清洗和乱序修正之后的数据。实验结果如下:

(1) 记录数指标测试结果如图7所示。

图7 冗余清洗前后数据对比  下载原图

记录数量越小表明冗余清洗结果越好。为了对比算法改进后的效果, 本文与文献[18]中的SNM算法进行对比。标签数量在100~500之间, 图中真实数据表示理想状态下标签应该产生的记录数, 其一般等于实际的标签数量。

原始数据表示标签实际环境应该产生的数据量, 其一般大于真实数据。改进前清洗结果表示文献[18]中SNM算法清洗后的标签记录数量。改进后清洗结果表示经过本研究提出算法清洗后的标签记录数量, 其越接近真实数据代表算法的清洗效果越好。

通过实验可以发现, 在标签数量较少时文中所提算法和SNM算法清洗效果相差不大, 但是随着标签数量的增加, 本研究所提算法具有更好的数据清洗效果, 也验证了该算法的有效性。

(2) 正确率指标测试结果如图8所示。

图8 乱序事件处理前后对比  下载原图

正确率越高表明乱序事件修正的效果越好。实验中随机生成的乱序比例在0~60%之间, 本研究采用开源复杂事件处理引擎Esper来进行事件的匹配。图中, Esper代表的结果是没有经过乱序修正的输出结果, Hash+Esper (单链表) 和Hash+Esper (双链表) 分别表示方法改进前后的输出结果。

将未经处理的事件发送到复杂事件处理引擎后, 由于事件流的乱序现象会导致原本符合条件的事件不能被匹配到, 而通过Hash算法进行处理后, 可以对原有的乱序事件进行修正。从图中可以:看出采用双链表结构可以明显提高正确匹配的事件数量, 符合本研究所提方法的预期效果。

本研究结合RFID仓储环境中的数据问题设计了面向仓储的RFID数据清洗模型, 采用不同的实验参数进行了仿真实验。结果表明:当标签数量和乱序率增大时, 通过模型中的数据清洗方法不仅可以有效降低RFID仓储中的冗余数据, 还可以提高事件输出的正确率。