RFID防碰撞算法研究与改进

1、河南省教育厅自然科学研究计划项目:射频识别技术在烟草仓储管理中应用研究;编号: 2008B120011;项目申请人:万红RFID 防碰撞算法研究与改进Research and Improvement on Anti-collision Algorithm for RFID System万 红,杨延昭Wan Hong ,Yang Yan-Zhao摘要 :多标签碰撞问题是 RFID 系统的关键问题之一。 当标签较少时, 基于 Aloha 的反碰撞算 法实现简单且性能良好,当标签增多时性能却急剧下降。本文提出一种改进的 Aloha 算法, 通过提前估计标签数量, 调整帧长度使系统效率最佳。 仿真结果

2、对比表明在标签数量大的情 况下该算法大大降低了识别时间。关键字 :射频识别; 反碰撞; Aloha 算法 吞吐量中图法分类号 :TN914.52 文献标识码 : AAbtract :In the RFID(Radio Frequency Identification systems,tag collision is one of significant issues. One of the popular anti-collision algorithms is ALOHA-based algorithms,which are simple and shows good performance

3、 when the number of tags to read is small. However, performance of them sharply descend as the number of tag increases.We propose an improved anti-collision algorithm by estimating the number of unread tags first and adjusts the the frame size to give the optimal system efficiency. Simulation result

4、s show that the proposed algorithm drastically reduces the identification time as the number of tag is huge.Keywords: radio frequency identification anti-collison aloha algorithm throughout 1 引言射频识别技术 (Radio Frequency Identification,RFID是上世纪 80年代逐渐走向成熟的自 动识别技术。 它通过射频信号进行非接触式双向通信交换数据, 以达到自动识别目标对象并 获取

5、相关数据。 RFID 可实现多目标的快速、动态、非接触性识别,广泛应用于物流、制造、 医疗、交通等领域。RFID 主要由阅读器 (Reader和标签 (Tag两部分组成。在阅读器和标签的通信过程中, 如有两个或多个标签处于 Reader 的可读范围内, 由于它们共用同一无线信道且频率相同, 因 此当它们同时给阅读器发送数据时将出现信道争用, 造成发送的数据干扰或冲突, 从而导致 阅读器不能正确读出数据。解决上述问题的方法称为反碰撞算法。反碰撞技术是 RFID 的关 键技术之一。反碰撞算法让 RFID 中 Reader 与 Tag 之间的数据快速、可靠地传输。反碰撞算法 设计的优劣很大程度上决定

6、了 RFID 系统性能。1纯 Aloha 算法在 P-ALOHA(Pure Aloha中, 任一标签进入阅读器的可读区域时, 立即以定长信息包形 式,将欲发送出去的数据送入信道。如果没有冲突出现,则认为是成功发射;若在发送过程 中其它标签也进入可读区域并发生碰撞,则随机独立地重新排定碰撞信息包,再一次重发, 直至发射成功。如图 1所示: 图 1ALOHA 算法示意图我们定义易碰撞期 T c 为当前信包发送时刻附近另一标签进入信道发生碰撞的一段时 间。 若标签信包长度为 T(时间表示 , 如图 2所示 , 在 P-Aloha 中 Tc=2T。 信道吞吐量是 Aloha 算法重要的性能指标,用 S

7、 p 表示。它是信包进入信道的速率 G 的函数,我们从图 2可以看 到 P-Aloha 的最大信道利用率为 18.4%,其性能不理想。2*G p S G e =(1 图 2 ALOHA算法的吞吐量2 时隙 Aloha 算法 S-Aloha(Slotted Aloha只是把 P-Aloha 算法的时间轴离散化成若干时隙。要求信包长度 小于或等于时隙长, 且标签只能在时隙开始时刻开始发送信包。 该算法的 Tc=T, 是 P-Aloha 的一半,故发生碰撞的概率减少一半。 图 3 时隙 ALOHA 算法示意图信道吞吐量 S s 可以表示成信包进入信道的速率 G 的函数。从图 4看出 S-Aloha

8、的最大 信道利用率为 36.8%,是 P-ALOHA 的两倍。但当阅读器范围内标签数目多时,要交换的信 包量增加而吞吐率却快速下降甚至为零。*G s S G e = 图 4 P-Aloha和 S-Aloha 算法信道利用率比较3 帧时隙 Aloha在 S-Aloha 基础上,把它的每个时隙进一步分割成若干时隙并打包成帧,就是 FSA(Framed Slot Aloha。 由于标签在帧内只随机发送一次信包, 因此就更一步降低了信包碰 撞的概率。 图 5帧时隙 ALOHA 算法示意图FSA 算法中帧时隙的长度是固定的,而实际应用中标签的数量未知,且是动态变化。 因此当标签数量远大于时隙个数时, 读

9、取标签的时间将会大大增加, 而在标签个数远小于时 隙个数时,会造成时隙的浪费。4 动态帧时隙 Aloha(DFSA算法由于 FSA 算法的局限性,我们提出根据标签的数目,改变帧内时隙的大小,使得识别效 率总是处于最优。设:帧时隙的长度为 m, 标签数为 n, 标签在帧内时隙的分布为二项式分布; 则一个时隙内有 k 个标签的概率为:( 1k n k nk p X k p p = (3由于帧内时隙地位一样,几率均等,故 p=1/m; 因此一个时隙内有一个标签的概率为 :1, 1111n m nA n m m = (4 在一个读周期内,一个时隙内只有一个标签的总时隙数(有效时隙数为:1111n S

10、mn m m = (5 定义系统的吞吐率(即有效时隙数占总时隙数的比率:1111n mn m m E m = (6 (6式说明效率E取决于时隙数m和标签数n。令0dE dn=,可以得到吞吐率最佳时,m,n 须满足的条件: 2l n 211n m e = (7当m,n满足(7时系统吞吐率最大, 因此我们可以根据标签数量n动态调整时隙数m。 下面 的关键问题就是怎样提前估计动态标签数量n。我们知道时隙只有三种状态:空闲状态(无标签进入该时隙、 发送状态(只有一个标签进 入该时隙和碰撞状态(多个标签进入该时隙。下面分别用 suc p , suc p , coll p 表示。1(1 n idle p

11、m =(8 111(1n sucp n m m = (9 又由 suc p +suc p +coll p =11coll idle suc p p p = (10为了估计标签数量,我们引入碰撞率 C r :碰撞的时隙数目与帧长度的比值。11111(1(1 1(1 (11n n n coll r mp n n C m m m m m m =+ (11 经过一个读周期后,可以知道当前帧长度和碰撞率 C r ,把 m 和 C r 代入(11 就可以得到标签数量 n。 5 动态帧时隙Aloha算法仿真及结论按照ISO/IEC 18000-6帧的结构,假定帧的长度为32bit,分别对帧长为128、256

12、的FSA及DFSA的识别时间用matlab进行仿真。并让标签数量从0到800变化。 从图7我们可以看到当标签数量较少时,该算法没有明显的优越性。但随着标签数目的 增多其识别时间与标签数量近似线形变化。因此该算法实现简单,尤其是大量标签的场合, 具有良好的动态特性,在大规模的商业配送中有一定的实用价值。6 结束语本文针对射频识别系统中存在的关键性问题防捧撞问题进行了研究, 提出一种改进的 动态 ALOHA 算法,有一定的创新性,并通过仿真,达到了较为满意的效果。由于缺乏大量 的实际检验数据,算法的实际效果还有待在实际应用中进一步的检验。本文作者创新点:通过对射频识别系统防碰撞算法的研究, 提出一

13、种改进的 Aloha 算法,通 过提前估计标签数量, 调整帧长度使系统效率最佳, 改善了 Aloha 算法不能适用于大规模标 签的场合。参考文献:1 崔 沂 峰 , 陈 平 等.RFID 电 子 标 签 防 碰 撞 算 法 的 研 究 J. 微 计 算 机 信 息 , 2007,8-2:233-2342吴春华,陈军.动态 ALOHA 法在解决 RFID 反碰撞中的应用J.电子器件, 2003, 26(2: 1731763Bin Zhen,Mamoru.Framed Aloha for Mutiple RFID Objects Identification.IEICE Trans.Commun.

14、, 2005,88(3:991-9994 Floerkemeier, C.,Wille, M.Comparison of Transmission Schemes for Framed ALOHA based RFID Protocols. Applications and the Internet Workshops, 2006. SAINT Workshops 2006.5H.Vogt,“Multiple Object Identification with Passive RIFD Tags”,2002 IEEE International Conf.on Systems,man and Cybernetics, 2002,3(12:6-9.作者简介:万红 (1964-,女,教授,博士,主要研究方向为雷达信号处理。杨延昭 (1979-, 男,河南许昌人,郑州大学模式识别与智能系统专业硕士研究生,研究方向 RFID 技术; Biography: Wan Hong(1964-, Female, P