基于时隙ALOHA 的RFID 防冲突算法及其系统实现方案的分析研究

1 引言

　　无线射频识别(RFID，Radio Frequency Identification)技术是近年来应用发展迅速的一种利用射频通讯方式实现的无线非接触式身份识别技术。RFID 技术应用系统[1]主要是由RFID标签、标签阅读器及相应的计算机系统组成的，当系统要阅读现场贴有RFID 标签的对象时，系统由标签阅读器向RFID 标签发送特定频率的电磁波，RFID 标签经电磁波的触发将內部存储的身份识别码信息送出，这样系统通过标签阅读器识别货物并进行相应的信息处理。但是，如果有多个RFID 标签接收到电磁波并同时发送信息，则标签阅读器接收到的信号就会互相干扰，不可避免地出现标签阅读冲突问题[1]。

　　目前解决RFID 标签阅读冲突问题主要是基于两种防冲突算法即[1、2]：基于时隙ALOHA的防冲突算法和基于树结构的防冲突算法。其中，前者是采用随机选择发送时间的方式，系统识别的可靠性相对差一些，但易于设计兑现；后者则采用二叉树的搜索算法，系统识别的可靠性较高，但系统兑现时需要与RFID 标签的识别码信息相联系，硬件设计较为复杂。因此，低成本的RFID 标签一般是采用基于时隙ALOHA 的防冲突算法来设计的，如何提高该算法系统识别的可靠性是目前低成本RFID 标签应用系统研究重点。

　　本文将首先介绍基于时隙ALOHA 的RFID 防冲突算法的基本实现原理，分析说明该算法的关键模型参数，指出设计该算法系统兑现的关键在于现场RFID 标签数预测和时隙帧长确定问题，然后具体介绍几种不同的标签预测实现方案，并进行系统识别的性能仿真与分析，最后总结出各种情况下相对比较可行的系统实现方案。

2 基于时隙ALOHA 的RFID 防冲突算法

　　时隙ALOHA 算法（Framed Slotted ALOHA）简称FSA 是一种随机时分多址方式[3] 的用户信息通讯收发算法，它将信道用信息帧表示，把信息帧分成许多时隙 (slot)，每个标签随机选一个时隙来发送自己的识别码信息。在整个信息帧的时间内每个RFID 只响应一次，如图1 所示。

　　图1 中每个圆圈代表一个RFID 标签发出的识别码信息，这样阅读器在整个信息帧接收过程中遇到的标签回复有3 种情况，即：成功、空闲、冲突，它们可能分别代表在某个时隙内是一个标签、没有标签或两个以上标签的应答。

　　实际情况中，由于各标签距阅读器距离不同，近距离标签发送的信息可能覆盖了远距离标签发出的信息，即使是时隙冲突，阅读器也可能正确识别近距离标签的信息。同样，由于其他环境噪声的影响，即使在一个时隙内只有一个RFID 标签应答，阅读器也可能无法阅读成功。在不考虑这两种不理想条件即捕获效应和环境噪声的影响[4]，若整个信息帧的时隙数设定为F，则阅读N 个RFID 标签时每个信息帧内成功、空闲和冲突的时隙数分别为：

　　因此，RFID 系统的阅读吞吐率也称识别效率即阅读器在一个信息帧长的时间内能成功识别标签数所占的比例可以表示为：

　　图2 中给出利用Matlab 仿真的RFID 系统阅读100 次积累的识别结果，其中系统仿真设定的信息帧长即时隙数设定按2 的幂次方递增，即F 取值从16 到256 变化，横坐标为标签数N 从1 到1000 变化，纵坐标为阅读吞吐率。可以看出当标签个数接近信息帧长时，系统的吞吐率比较高，这与式（2）的结果是一致的，即最大阅读吞吐率可通过式（2）对F进行微分即（dS/dF）F=N =0 得到。

3 RFID 标签数预测与信息帧设定实现方案

　　在RFID 系统应用时，系统阅读器读取的RFID 标签数往往是未知的。根据上面RFID多标签阅读的防冲突算法分析结果上看，要实现具有解决RFID防冲突算法功能的系统方案，系统需要先进行现场的RFID 标签数预测[5]。通常可以通过以下几种预测方法来实现：

　　1）最小预测（lowbound）[6、14]：即系统阅读有冲突出现的话，至少有2 个以上的标签存在，可以预测发生冲突的标签个数至少为2*ak。

　　2）Schout 预测[4、6、12、13]：若在每个信息帧中每个标签选择时隙符合λ=1 的泊松分布，则信息帧中各冲突时隙平均响应的标签个数约为2.39，这样可以预测未识别的标签数为2.39*ak。

　　3) Vogt 预测 [2、11]：它是通过比较实际的成功、空闲、冲突时隙数与理论的成功、空闲、冲突时隙数得出误差最小的结果来预测未知标签数，即：

　　其中，c1、ck、c0 为实际测得的成功、空闲、冲突时隙数值。在标签数N 取值范围[C1+2*CK，……，2*（C1+2*CK）]内找到最小的ε值，所对应的N 值就是预测的标签数。图3 分别给出采用Lowbound、Schout、Vogt 三种不同的标签数预测实现方案的系统仿真结果，它们均先预测确定现场可能的标签数后再来设定最佳信息帧长度，并重复阅读100次。与FSA（即信息帧长度固定为256）相比，可以看出基于标签数预测的系统，系统阅读吞吐率有明显改善。

　　但是总的来说，对于现场有大数量标签（特别是标签数大于500）时，采用式（2）由预测标签数来设置最佳信息帧长度的实现方案显然是不合适的。因此，有人提出了采用分组应答响应的方法[7]来实现，即当标签数超过354 个时，将标签进行分组，选择1 组的先应答，识别完1 组之后再识别2 组……，分组数和标签数目的关系如表一。

　　图4 是对现场有大数量标签（大于500）时采用分组算法和Lowbound、Schout、Vogt的预测方案比较仿真结果。可以看出采用分组算法的系统吞吐率在标签数大于500 的时候可以达到很高，而其它几种则降得很快。因此如果用在大规模的标签识别时使用分组算法可以有效的提高系统的识别效率。

4 自适应信息帧时隙设置

　　从前面分析与仿真结果上看，要获得最高的吞吐率或最佳识别效率，先得预测获得可能的标签数，并设置最佳的信息帧长度[5]。但是，任何RFID 系统在不同场合要识别的标签数的变化范围很大，要直接预测标签数并设置好最佳信息帧长度在实际电路实现系统设计是比较复杂，且带来额外功耗[8]。事实上，RFID 系统中常用2 的n 次幂作为信息帧长度，其中 n取1 到8（即最大的帧长为256，最小为2，但更多最小取16)，如Vogt 预测[11]提出的帧长和标签数的关系如表二，当标签个数在1—9 之间时，帧长采用16。

　　为了简化实际电路的兑现设计，通常采用基于标签数预测的幂指数信息帧长度设置方法， 如在最新的EPC Gen2 标准[15]中采用了Q-Algorithm 的自适应信息帧时隙设置方案，当一个帧中出现过多的冲突时隙时，阅读器提前结束该帧发送一个新的更大的帧；当一个帧中出现过多的空闲时隙时，此帧也不是最佳的帧，阅读器提前结束该帧发送一个新的小的帧。具体实现方案如图5 所示：

　　图5 中参数Q、Qfp 和c 均为正整数，信息帧长度为F=2^Q-1，Q 是动态变化的，初值取round(Qfp)。一个时隙之后，若该时隙是冲突时隙，则将Qfp 加上参数c；若是空闲时隙，则将Qfp 减去参数c；若是成功时隙，则Qfp 保持不变。阅读器根据新的Q=round(Qfp)来决定是继续发送下一个时隙还是重新开启一个新的帧。

　　EPC Gen2 采用Q-Algorithm 在标签数变化很大的范围内要实现高吞吐率主要取决于参数c 的取值。c 太大会造成帧长变化过于频繁，太小又不能迅速的实现最佳帧的选择。在EPC标准中c 的取值并未规定，因此必须找到合适的c 取值。文献[8]中帧长小于64 的全部取c最大值0.5，帧长64 到512 之间c 值取线性减小变化，帧长大于1024 的全部取c 最小值0.1。该取值方法比较简单且符合实际，实现结果也较理想，如图6。图6 中x 轴是标签从1 到1000变化，y 轴左边图形显示识别一个标签所需的平均时隙数为3，右边图形显示在标签数大范围的变化内都保持较高的吞吐率。文献[9]中提出了另外一种方案，时隙冲突和空闲时所取的c 值不等，但成一定比例，这种方案相对复杂。

　　采用EPC Gen2 标准中的算法优势一是系统的总体识别时间较少，系统吞吐率高；二是阅读器中初始帧长值（即Q 值）的设置不受限制，如图7。图7 中横轴1 和2 分别代表标签数200 个和400 个，Q 初值分别取1-8 的变化，发现最终的识别时间几乎无差别，这主要就是算法自适应调整的优势。采用EPC Gen2 标准中的算法劣势是系统由于调整帧长过于频繁而造成功耗的增加[10]。

5 总结

　　防冲突算法是射频识别系统实现标签快速识别的关键。本文通过对现有几种代表性的防冲突算法的比较研究，对防冲突算法有更加深刻的理解。Vogt 提出的预测识别范围内所有标签的机制，预测准确度高；分组算法采用幂次变化帧长且系统的识别时间短，吞吐率高，非常适合实际的应用；EPC Gen2 标准提出的Q-Algorithm 算法使系统能自适应的调整，识别效率高，在超高频射频识别系统中得到广泛的应用。

参 考 文 献
[1] Klaus Finkenzeller 著.射频识别技术[M].第三版.BeiJing:电子工业出版社,2006.

[2] MaurizioA.Bonuccelli,Francesca Lonetti ,Francesca Martelli. Instant collision resolution for tag identification in RFID networks[A]. Ad Hoc Networks, Elsevier, Volume 5, Issue 8, November 2007

[3] L. Burdet. RFID multiple access methods[A]. Technical Report ETH Zurich, 2004.

[4] FRITS C. SCHOUTE. Dvnamic Frame Length ALOHA[A]. IEEE Transaction on Communications,1983

[5] Jae-RyongCha ,Jae-HyunKim. Novel Anti-collision Algorithms for Fast Object Identification in RFID System [A].in Proc. International Conference on Parallel and Distributed Systems, 2005

[6] Christian Floerkemeier. Transmission control scheme for fast RFID object identification[A].IEEE PerCom Workshop on Pervasive Wireless Networking, Italy, March 2006

[7] Su-RyunLee,Sung-DonJoo,Chae-WooLee. An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification[A]. Proceedings of the Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, San Diego, CA, USA, July 2005

[8] Inwhee Joe,Juno Lee. A Novel Anti-Collision Algorithm with Optimal Frame Size for RFID System[A]. 2007.SERA 2007. 5th ACIS International Conference,2007

[9]DonghwanLee,KyungkyuKim,WonjunLee. Q -Algorithm: An Enhanced RFID Tag Collision Arbitration
Algorithm[J].Computer Science, 2007, Volume 4611:23-32

[10] Jianwei Wang, Dong Wang, Yuping Zhao .A Novel Anti-Collision Algorithm with Dynamic Tag Number Estimation for RFID Systems[A]. Communication Technology, 2006. ICCT '06,Nov.2006

[11] Harald Vogt. Efficient Object Identification with Passive RFID Tags[A]. in Proceedings of the IEEE
International Conference on Systems, Man and Cybernetics (SMC '02), Hammamet, Tunisia, October 2002

[12] Qiaoling Tong, Xuecheng Zou, Dongsheng Liu,et al. Modeling the Anti-collision Process of RFID System byMarkov Chain[A].Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007

[13] Christian Floerkemeier , Matthias Wille. Comparison of Transmission Schemes for Framed ALOHA basedRFID[A]. Applications and the Internet Workshops, 2006. SAINT Workshops 2006

[14] Tae-Wook Hwang, Byong-Gyo Lee, Young Soo Kim, et al. Improved Anti-collision Scheme for High Speed Identification in RFID System[A]. Innovative Computing, Information and Control, 2006. ICICIC '06
[15] EPCTM Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for ommunications at 860 MHz – 960 MHz Version 1.1.0 Draft1, EPCglobal Inc,2005

作者简介：
吴伟贞（1983-），女，福建莆田人，硕士生，研究方向为无线射频识别；郭东辉（联系人），男，教授，博士生导师.