密集环境下RFID系统滤波方法研究

郭凤鸣，李兵，何怡刚

1.湖南机电职业技术学院，长沙410151

2.湖南大学电气与信息工程学院，长沙410082

1 引言

物联网利用射频识别（RFID）、无线传感网等信息传感设备，将目标物与互联网相连接，实现对目标物的智能化识别、定位、监控及管理等功能。RFID系统、数据库及网络数据处理能力的限制，使得从大量标签识别码（ID）数据中过滤出有用信息成为亟需解决的问题[1-2]。

文献[3]介绍了典型的网络数据包分类方法；文献[4]讨论了RFID滤波及网络数据包分类方法的相似性；文献[5]给出了RFID阅读器读滤波算法；文献[6-7]提出了基于读滤波的RFID滤波方法，重点解决了实际应用中去除噪声及重复数据以准确获取目标ID数据的问题，但所提出方法实时性较差，不符合快速滤波的应用需求。本文结合读滤波算法及RFID空中接口通信协议规定的Select指令，提出了一种新的基于几何算法的RFID滤波方法，并对该方法进行了仿真实验。

2 RFID空中接口几何滤波算法

密集环境RFID系统是设备部署环境中存在多个阅读器及大量标签，且支持较大数量的终端用户及应用，如图1所示。图1中，空中接口层执行预滤波，中间件对预滤波做出响应；阅读器层及中间件层执行后滤波；后滤波由读滤波开始，且读滤波受终端用户及应用控制；中间件将部分后滤波任务分配给阅读器，以减少中间件计算量及阅读器与中间件网络载荷。

图1 密集环境RFID系统示意图

2.1 RFID标签数据结构及读滤波

根据ISO/IEC 18000-6C标准，标签数据一般包括版本号、域名管理者、对象分类及序列号4部分。编码长度分为64位、96位及256位3种，以GID-96为例，标签数据结构中4部分分别为8位、28位、24位及36位。阅读器接收标签数据后，基于按位模式对标签数据进行读滤波处理[5]。例如，可口可乐公司产品的GID-96编码为35.00009F1.*.*，其中355m l罐装可乐的对象分类代码为000200，则可利用35.00009F1.000200.*从标签数据中滤出355m l罐装可乐产品[8]，从而实现读滤波。

2.2 RFID空中接口标签群管理

根据ISO/IEC 18000-6C[9]标准，阅读器利用Select、Inventory及Access等3个指令管理标签群。阅读器通过一个或多个Select指令选择特定标签群执行Inventory指令。执行Select指令后，只有匹配标签设置标记，其他标签不执行Inventory过程。当匹配标签群接收到Query指令时，Inventory循环开始，如图2所示。Access过程是阅读器对Inventory过程中指定的标签进行读写操作。

图2 单标签响应过程示意图

2.3 几何滤波算法

读滤波方法滤波器数据输入端标签数据数量较大，影响系统滤波效率。本文结合读滤波算法及Select指令，利用矩形框几何形式，给出空中接口滤波算法，所提出算法分三步完成。

步骤1 获取包括所有矩形框的边界盒，如图3所示。图3（a）中，利用边界盒滤除数据源中冗余部分；但当标签群范围边界存在读滤波时，步骤1不能提高滤波效率，如图3（b）所示。

图3 步骤1示意图

步骤2利用水平及垂直扫描线找出交叉点，以隔离矩形框组的重叠部分，如图4所示。找到矩形框组重叠部分后，选择单独的隔离边界盒。步骤2在利用多个Select指令滤除冗余区域的同时增加了系统时间消耗，且由于新的复制区域的出现，使得步骤2相较于步骤1增加了少量的冗余区域。

图4 步骤2示意图

步骤3 利用更多Select指令获取更小冗余区域，如图5所示。图5（a）利用4个Select指令产生6个冗余区域；图5（b）利用4个Select指令产生3个冗余区域。图5中冗余区域远小于整体区域。

图5 步骤3示意图

3 Inventory概率模型及滤波时间测试方法

空中接口滤波算法利用Select指令在数据源头对标签数据进行滤波，从而提高系统数据处理能力。为评估所提出空中接口滤波算法效率，本文提出Inventory概率模型及循环次数模型。

3.1 Inventory概率模型

定义ALOHA防冲突算法[10]中帧长度为Sf，标签群大小为St。式（1）、（2）为文献[10]给出的Sf概率模型。假设n个标签的时隙数量为TSf，Stn，则系统效率Eff为：

为使系统效率最大，对式（1）求导，可得帧长度为Sf时最优响应标签数Sto为：

3.1.1 单标签响应、无响应及冲突响应概率模型

假设变量N服从关于η、p的二项分布，即有N～B(St，η)，其中，则根据概率质量函数可得n为：

一个Inventory周期内，单个标签响应及空闲概率Pr及Pnr分别为：

定义冲突响应概率Pcr包括除Pr及Pnr外的情况，则结合式（3）、（4）可得Pcr为：

由式（3）～（5）可得，当Sf及Sto较大时有：

3.1.2 读周期内Inventory循环次数模型

假设第c个标签进入新Inventory循环的概率为Stc，则

由式（7）可知，当阅读器在某段时间内未接收到标签响应时，阅读器完成读周期。由式（7）可得：

则读周期内Inventory循环次数Nir为：

3.2 滤波时间测试方法

假设Select、Inventory及读滤波时间分别为ts、ti及tf，则RFID系统标签识别时间t为：

3.2.1 Select时间近似计算

利用两个Select指令计算ts，如图6所示。标签被初始标记（Flag）的概率为0.5，故第一个Select指令改变被选择标签群数量，第二个Select指令设置对话标记(A⇄B)。假设一个Select指令耗时为τ，则一个空中接口滤波耗时为2τ。假设空中接口滤波次数为k，则ts为：

图6 两次Select操作示意图

3.2.2 Inventory时间近似计算

假设图2中，第一个Inventory循环内发送Query指令，RN16，连续波及协议控制时间分别为ωQ-r、ωQ-nr及ωQ-cr，则第一个Inventory循环时间ti1为：

第二个Inventory循环发送Query Rep指令，则ti2为：

由式（12）、（13）可得，第n个Inventory循环时间为：

故ti为：

3.2.3 读滤波时间近似计算

假设RFID系统中存在m个阅读器，n个标签，阅读器及中间件滤波次数为γ，则当滤波过程采用线性查询，即按位进行逻辑“与”操作时，tf-l为：

当滤波过程采用预构树算法时，tf-p为：

4 仿真实验

测试读滤波线性查询（LS）及所提出空中接口滤波算法条件下，RFID系统标签识别时间t，并比较二者滤波效率。为简化分析过程，根据文献[10]，假设St=2Q，则由式（2）可得Sf=2Q+1，其中0≤Q≤15。所提出空中接口滤波算法三个步骤分别记为步骤1、步骤2、步骤3。

4.1 单阅读器测试

实验测试阅读器进行5次读滤波，且Q=4，5，6，7，即St分别为24、25、26及27时，ts、ti及tf的比例关系。相较于ts及ti，tf受系统部署方式及应用环境影响较大。根据文献[4]，假设式（16）、（17）中γ=0.1为单次读滤波最小计算消耗。利用Select及Inventory链路时间参数，获取100次仿真的平均值。测试结果如图7、8所示。图7为ts、ti及tf比例关系；图8为图7中每个读循环Inventory操作次数。

图7 单阅读器环境ts、ti及tf比例关系

图8 读循环Inventory操作次数

由图7可见，空中接口滤波算法滤除了非目标标签群；ts为固定值且远小于ti，故虽然空中接口滤波算法增大了ts时间消耗，但其滤波效率仍优于线性查询。ti为t主要影响因素；tf远小于ts及ti，LS、步骤1、步骤2及步骤3的tf值分别为0.064、0.042、0.035及0.029，其对t影响最小。由图8可见，读循环Inventory次数随St增大而增大；空中接口滤波中Select指令次数越多，滤除的非目标标签群越多，故每个读循环Inventory操作次数越少。

4.2 密集环境测试

实验测试系统存在32个阅读器，随机产生1 024次读滤波，Q=11，12，13，14，即St分别为211、212、213及214时，ts、ti及tf比例关系如图9。

图9 阅读器密集环境ts、ti及tf比例关系

由图9可见，阅读器密集环境下，空中接口滤波算法滤波效率高于线性查询方法。对于步骤1，由于边界盒几乎覆盖整个标签域空间，故步骤1滤波效率与LS相差较小；采用步骤2及步骤3，系统滤波效率得到较大提高，相较LS方法，系统标签识别时间分别减少40%及50%。对于阅读器密集环境，中间件接收32个滤波器数据，读滤波发生在中间件，故相较于单阅读器环境，此时ti及tf成为影响t的重要因素；ts大小固定，且远小于ti及tf。

5 结束语

提出一种新的结合空中接口滤波及读滤波的RFID滤波方法。测试结果表明，本文方法滤波效率优于线性查询方法。对于单阅读器环境，ti为t主要影响因素。对于密集环境，ti及tf为t主要影响因素；相较于线性查询方法，本文方法滤波效率最大提高了50%。本文测试过程基于阅读器接收标签ID为随机量假设前提，实际应用中，阅读器接收到的标签ID可能符合某种统计分布，其分布特性将对系统滤波效率产生影响。下一步，将针对实际应用中标签ID分布特性，研究提出自适应的RFID系统滤波方法。

[1]Schreiber F A，Camplani R，Fortunato M，et al.PerLa：a language and middle ware architecture for data management and integration in pervasive information system[J].IEEE Transactions on Software Engineering，2012，38（2）：478-496.

[2]Lee C H，Chung C W.RFID data processing in supply chain management using a path encoding scheme[J].IEEE Transactions on Know ledge and Data Engineering，2011，23（5）：742-758.

[3]Gupta P，Mckeown N.A lgorithms for packet classification[J].IEEE Network，2001，15（2）：24-32.

[4]Park H S，Kim J D.Design and Implementation of a highs peed RFID data filtering engine[C]//Proc of EUC Workshops，2006，4097：423-434.

[5]Cglobal E P.Reader Protocol，Version1.1.2006.

[6]Bai Y，Wang F，Liu P.Efficiently filtering RFID data streams[C]//Proc Int VLDB Workshop on Clean Databases，2006：50-57.

[7]Wang F，Liu P.Temporal management of RFID data[C]//Pro of International Conference on Very Large Data Bases，2005：1128-1139.

[8]蒋韶钢，谭杰.RFID中间件数据处理与过滤方法的研究[J].计算机应用，2008，28（10）：2613-2615.

[9]ISO/IEC Information Technology-Radio Frequency Identification for Item Management-Part 6：Parameters for Air Interface Communications at 860 MHz to 960 MHz[S].USA：ISO/IEC，2007.

[10]Lee S R，Joo S D，Lee CW.An enhanced dynam ic framed slotted ALOHA algorithm for RFID tag identification[C]//Proceedings of International Conference on Mobile and Ubiquitous System s，MobiQuitous，2005：166-174.