一种分布式全类型RFID阅读器碰撞解决方案

王　宇，甘健侯

(1.云南经济管理学院，云南 昆明 650106；2.云南师范大学，云南 昆明 650092)

一种分布式全类型RFID阅读器碰撞解决方案

王宇1，甘健侯2

(1.云南经济管理学院，云南 昆明 650106；2.云南师范大学，云南 昆明 650092)

已有的RFID阅读器防碰撞算法一般仅可解决部分类型的阅读器碰撞，或者由于采用中心控制设备导致延迟较高，对此提出一种分布式的全类型RIFD阅读器碰撞解决方案。设计了一种分布式多信道通知协议，主要包括询问与接收两部分，从而合理地分布阅读器间的网络资源，在考虑全部阅读器碰撞类型的前提下，降低所有标签的平均询问延迟。仿真实验结果表明，本算法可解决全部类型的RFID碰撞，同时具有较低的延迟。

防碰撞；RFID系统；物联网；网络安全；分布式协议；通知协议

0　引言

在RFID系统中，如果阅读器的射频场作用范围内存在多个标签，并有两个或者两个以上的标签同时响应阅读器时将会产生碰撞［1］。而阅读器与标签的不同位置可能导致 3种碰撞类型［2］：(1)标签之间的碰撞；(2)阅读器接口之间的碰撞(RRI)；(3)阅读器与标签接口间的碰撞(RTI)。

目前主流的防碰撞算法主要分为两大类，一种是基于时隙分配的ALOHA方法［3］，该方法实现简单，但可能出现标签饿死现象；另一种方法是搜索树方法，该方法一般延迟较长［4］。近期一些研究对传统防碰撞方法进行了改进，提高了ALOHA与搜索树方法的性能，但是对于密集RFID网络，即碰撞发生概率极大的情况，其性能并不理想［5-6］。

针对上述问题，本文提出一种分布式多信道防碰撞算法，其中引入了一个多信道通知协议来使得阅读器感知网络采用的资源，本方法可解决所有3种类型的碰撞。与其他防碰撞协议比较，本方法减少了标签认证所需的平均时间，并增加了标签询问的成功率。

1　分布式多信道防碰撞算法

1.1背景知识与系统模型

本方法在阅读器之间建立一个通知机制，使阅读器知道网络中的资源、信道与时隙的分配情况，如图1所示，本方法在阅读器之间设置了两个控制信道CC1与CC2。在CC1与CC2中分别使用不同频率(频分)与时隙(时分)防止阅读器之间的干扰。阅读器与标签之间的通信则使用多数据信道。

图1　本文RFID系统的架构

首先定义以下变量：假设Ri表示一个阅读器 i，对于每个 Ri，ri设为 Ri的阅读范围，Ii是 Ri的干扰范围，di，j是Ri与Rj之间的距离。假设所有的阅读器阅读范围相等，则对于两个阅读器Ri与Rj，RTI的发生条件为：

该情况下，两个阅读器必须在不同的时隙运行，RRI与RTI同时发生的条件为；

该情况下，两个阅读器必须在不同的频带运行。本文方法中将控制信道CC1与CC2的传输范围分别设为r+I与2r。

每个阅读器R维护两个队列Q1与Q2，分别用于阅读器是否可以开始识别标签以及所使用的数据通道。Q1保存一些信息，例如对R干扰的阅读器ID；Q2保存当前正在干扰标签的阅读器信息。

1.2本文算法的步骤

每个阅读器R在标签询问过程中使用数据通道时也可接收控制通道的控制包，将从 CC1、CC2接收的控制信息分别保存于 Q1、Q2中。图2所示是控制数据包的格式，主要包括3个域：(1)type：“START”或“END”；(2)阅读器 ID，阅读器的身份ID；(3)选择的信道，标签询问的发送器所用信道。在CC2的传输中，所选通道域是空的，因为邻居节点距离发送器 2r，不需要所选通道的信息，此类邻居节点仅需要在同一时隙认证阅读器。END包中所选信道域也是空的，因为从队列中删除部分START数据包，阅读器ID足以识别一个阅读器。

图2　数据包格式

本文算法包括两个部分：询问程序与接收程序，分别如图3与图4所示。

图3　本文方法的询问程序

图4　本文方法的接收程序

询问程序：将可用数据信道AV的数量设为n，初始化时，AV=｛c1，…，cn｝的所有数据信道均是可用的。当一个阅读器开始一次询问，首先等待一个伪随机时间，然后检查该阅读器的Q1与Q2两个队列，如果Q1集合的大小不等于n，Q2是空的，则选择一个可用的数据通道，在CC1与CC2上发送一个START数据包，并开始标签询问过程。如果两个条件没有同时满足，则阅读器需等待一个伪随机时间，重新开始上述过程。

接收程序：如果阅读器收到一个START控制包，则提取关于阅读器与数据通道的信息，依赖该包的控制信道将其排列在对应的队列中，如图4所示。将CC1通道上阅读器R的传输范围设为r+I，由此通知邻居阅读器引发RRI或者RTI型的碰撞。因此，如果有其他可用的通道，则可选择其他通道，如图3所示。另外，将CC2的传输范围设为2r，通知引起R阅读器RTI碰撞的邻居阅读器，使这两个阅读器不同时操作。上述设置可防止终端隐藏与暴露问题，互相干扰的阅读器之间可使用控制信道通信。当一个阅读器结束标签询问过程，则在CC1与CC2通道中发送END包通知其结束状态，收到该消息的阅读器从其队列中删除对应的START数据包。

1.3干扰范围的计算

使用路径衰减模型计算干扰范围，如式(3)所示：

其中d是检验与阅读器的距离，分母1为无线通信参考距离。假设阅读器与标签的位置如图5所示，此外，因为阅读器的覆盖范围依赖阅读器的输出能力，考虑阅读器操作的输出功率为2W［7］，因此对应阅读器的传输范围是10 m。然后，使用式(3)计算从阅读器A到标签的路径衰减，假设阅读器与标签的距离为10 m，有：

图5　B对A产生的干扰

根据文献［8］，需要 13 dB的输入功率来激活一个被动标签，因此总衰减为：58+58+13=129 dB。为了在A中成功接收标签的反向散射信号，从阅读器B到A干扰信号的路径衰减必须大于129 dB。因此为了防止阅读器碰撞，A与B的距离应该为：

由此证明本文对阅读器干扰范围的选择是合理的，即当阅读范围是10 m时，干扰范围是1 000 m。

2　仿真实验与结果分析

将本方法与文献［9］的DSAC和文献［10］的AAC进行比较，DSAC与AAC均是近期性能较好的防碰撞算法。基于网络仿真器NS3进行实验，使用RangePropagationLoss-Model与NS3的802.11 Wife模型(http://www.nsnam.org)。实验中使用MAC层的CSMA处理控制包的碰撞，本算法检测阅读器碰撞，假设每个阅读器必须验证100个标签，阅读100个标签所需的时间为0.46 s，阅读器可能同时阅读不同的标签。

本实验设计了稀疏与密集的两种阅读器分布场景。稀疏场景：在 3 km3的三维空间中手动地放置5、10、15、20、25个阅读器，因此会频繁地发生不同类型的碰撞；密集场景：在 2 km2的三维空间(高 20 m)中随机地分布25、70、150、250、350、1 000与 2 000个阅读器。假设阅读器的传输范围是10 m，干扰范围是1 000 m。阅读器天线类型为全向天线，数据速度为 1 Mb/s，CC1传输范围r+I=1 010 m，CC2传输范围2r=20 m；每组实验重复运行次数是10，稀疏场景数据通道数量是6，密集场景数据通道数量是10。

2.1阅读器询问操作失败的次数

如果网络中不同阅读器的队列之间发生碰撞，则认为是询问失败。图6所示是稀疏、密集两种场景的询问失败次数，稀疏场景下，DSAC失败询问次数随着阅读器数量增加而增加，主要原因是DSAC仅解决了RTI，而本文方法的阅读器没有出现失败情况，本方法与AAC可解决RTI与RRI。在密集场景下，本方法与AAC仍然没有出现失败的情况，可解决RRI与RTI两种碰撞。

图6　阅读器询问操作失败的次数

2.2阅读器询问总延迟

不同数量阅读器的总识别延迟定义为所有阅读器结束标签询问过程所需的时间，图7所示是实验结果的统计。稀疏场景下，DSAC比AAC的总延迟低，原因是DSAC并未解决所有的碰撞，所以用时较少。而本方法的延迟最低，受益于本方法的分布式处理方案，因此在阅读器数量增加之后，本方法的总询问延迟上升幅度减小。而对于密集场景，因为本方法是分布式检测方法，所以本方法的延迟依然最低。

图7　阅读器询问总延迟

3　结论

本文针对已有RFID阅读器防碰撞算法一般仅可解决部分类型的阅读器碰撞或者由于采用中心控制设备导致延迟较高的问题，提出一种分布式的全类型RIFD阅读器碰撞解决方案。本方法可解决所有3种类型的碰撞。与其他防碰撞协议比较，本方法减少了标签认证所需的平均时间，并增加了标签询问的成功率。

［1］余松森，詹宜巨，蔡庆玲，等.融合安全与反碰撞的RFID处理机制［J］.计算机工程，2011，37(10)：26-28.

［2］KLAIR D K，CHIN K W，RAAD R.A survey and tutorial of RFID anti-collision protocols［J］.IEEE Communications Surveys&Tutorials，2010，12(3)：400-421.

［3］单剑锋，谢建兵，庄琴清.基于分组的动态帧时隙ALOHA防碰撞算法研究［J］.计算机技术与发展，2012，21(11)：39-41.

［4］黄琼，凌江涛，张敏，等.LRST：低冗余搜索树防碰撞算法［J］.通信学报，2014(6)：110-116.

［5］刘国柱，王腾，王华东.基于帧分组与二进制搜索树识别的 RFID防碰撞算法的研究［J］.海南大学学报：自然科学版，2015，32(4)：320-326.

［6］LAI Y C，HSIAO L Y，LIN B S.An RFID anti-collision algorithm with dynamic condensation and ordering binary tree［J］.Computer Communications，2013，36(s17-18)：1754-1767.

［7］BUENO-DELGADO M V，VALES-ALONSO J，ANGERER C，et al.A comparative study of RFID schedulers in dense reader environments［C］.IEEE International Conference on Industrial Technology，2010：1373-1378.

［8］LEHPAMER H.RFID design principles，second edition［M］.Automatic Vehicle Identification，2012.

［9］SAADI H，TOUHAMI R，YAGOUB M C E.Design and simulation of anti-collision RFID system based on SDMAOFDM［C］.Multimedia Computing and Systems(ICMCS)，2014 International Conference on.IEEE，2014：1510-1515.

［10］徐海峰，姜晖，刘振.一种改进的 RFID自适应防碰撞算法［J］.计算机工程，2012，38(17)：290-292.

A distributed anti algorithm for all types of RFID reader collision

Wang Yu1，Gan Jianhou2
(1.Yunnan College of Business Management，Kunming 650106，China；2.Yunnan Normal University，Kunming 650092，China)

The existing anti-collision algorithms for RFID reader can only resolve some types of reader collisions,or it has high delay due to adopting centralized control hardware,a distributed anti method for all types of RFID reader collision is proposed for that problem.A distributed multi-channel notification protocol is designed,which includes two parts of interrogation and receive, and the network resource for the readers is distributed reasonably.All types of collisions are considered by the proposal and the average tag interrogation delay of all tags are reduced.Simulation experiments results show that the proposal can handle all types of collisions and realize a lower delay.

anti-collision；RFID system；Internet of Things；network security；distributed protocol；notification protocol

TN911

A

10.16157/j.issn.0258-7998.2016.04.026

2015-12-21)

王宇（1982-），男，硕士，讲师，主要研究方向：数据库技术、面向对象技术、移动互联网。

甘健侯(1976-)，男，教授，主要研究方向：数据挖掘、民族教育信息化。

中文引用格式：王宇，甘健侯.一种分布式全类型RFID阅读器碰撞解决方案［J］.电子技术应用，2016，42(4)：92-94，98.

英文引用格式：Wang Yu，Gan Jianhou.A distributed anti algorithm for all types of RFID reader collision［J］.Application of Electronic Technique，2016，42(4)：92-94，98.