RFID 防碰撞技术中的算法分析

摘要：通过对RFID中的碰撞问题和防碰撞算法进行分析，结合动态帧时隙ALOHA算法和动态二进制搜索算法的优点，提出一种基于标签估计和标签识别的混合算法。

关键词：无线射频辐射；防碰撞算法；ALOHA算法；二进制搜索

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2013）15-3514-02

在RFID系统中，常用的标签防碰撞算法有基于时分多路法（TDMA）的ALOHA系列的算法和二进制防碰撞系列算法，而两种算法需根据标签的数量才能发挥其优点。但当标签数量无法估计的情况，单纯运用一种算法效率会较低。如能同时运用该两种算法，结合动态帧时隙ALOHA算法和动态二进制搜索算法的优点，能根据非固定标签数量，较快速解决碰撞问题。

1 RFID防碰撞算法概述

无线射频辐射技术（Radio Frequency Identification，RFID），是20世纪90年代兴起的一项非接触式的自动识别技术。它是通过射频方式进行非接触式双向通信，以达到对目标对象自动识别的目的。目前已广泛应用于身份识别、工厂制造、物流管理等领域，也是正在发展的物联网的核心技术。

在RFID系统中，防碰撞技术是信号识别的关键技术之一。当只有一个标签位于一个阅读器的可读范围内，则可直接进行阅读。但实际情况，通常会有多个标签同时位于一个阅读器的可读范围。在信道共用、频率相同的情况下，多个标签同时将信号送入一个阅读器的读通道会产生信道争用，各信号之间互相干扰，产生数据碰撞，从而造成阅读器和标签之间的通信失败。

在解决碰撞问题中已研究出许多解决方法，目前防碰撞技术的解决方法为通信技术常用的多路存取法，基本上有四种。空分多路法（SDMA）、频分多路法（FDMA）、码分多路法（CDMA）和时分多路法（TDMA）。前三者基于硬件的技术，通过改善硬件的条件来解决碰撞问题，但因利用率低、实现成本比较高，所以较少实用。一般采用的是易于更新的软件方法，即基于时分多路法（TDMA）的ALOHA系列算法和二进制防碰撞系列算法。

2 ALOHA系列算法

2.1 ALOHA算法

ALOHA算法的是一种为交互计算机传输设计的时分多路法的多路存取方法，是一种随机接入方式。基本原理是：当用户要发送数据帧时，就可以在任何时候发送，当发生冲突时，冲突的帧被破坏，发送方就得不到响应。当标签被识别或不被识别时，都会随机退避一段时间。退避时间是标签在某个时间内随机产生的随机数，因为随机数不同，便达到了避开碰撞的目的。

假设S为吞吐率，T0为传输的一个数据包所用的时间，G为交换的数据量，Pe为成功完成的概率，x为每秒发送的帧数，

则t秒发送n个数据帧的概率为： P（n）=（xt）ne-xt/n！

则在T0内发送信息的概率是： Pe=e-G

所以在2T0没发送的概率是： Pe=e-2G

可算得吞吐量为： S=Ge-2G

当G=0.5时，吞吐率达到最大值18.4%。

ALOHA算法最大的优点是：算法原理简单，实现成本较低，当标签不多时效率高。 缺点是：1）适应于实时性不高的场合，只能用于只读标签。2）当标签数量越大碰撞的概率越大。

2.2时隙ALOHA算法和动态时隙ALOHA算法

时隙ALOHA算法采用的是时分随机多址的方式，在数据的传送总是在同步的时隙内才开始，避免了ALOHA算法的部分碰撞，发生碰撞的时间缩短到T=t。

所以该算法的吞吐量为： S=Ge-G

当G=1时，吞吐率达到最大值36.8%。

但当G=1时，标签数量继续增大时，因所有的时隙段的持续时间与可能存在的标签有关，且可能只有一个标签处于读写器的作用范围的时候，便出现“死读”现象，无法读取。如果标签数量过小，则会浪费信道。解决方法可采用非固定的时隙。

动态时隙ALOHA算法原理是通过阅读器发送两个时隙大小不同的时隙，如碰撞标签数量多，则用下一个请求命令增加时隙数量，直到发现一个的标签为止，以此方法找到调整时隙大小。

2.3帧时隙ALOHA算法、动态帧时隙ALOHA算法和增强的动态帧时隙ALOHA算法

帧时隙ALOHA算法把N个时隙作为一个通信单位，帧。标签在每个帧时隙中随机发送一次信息，因此传输数量增大，适合传输数量较大的情况。

但由于所有帧具有相同且固定的时隙长度，如时隙ALOHA算法相似的，固定的时间段必直接影响了识别的效率。所以需动态调整发送的时间段。

动态帧时隙ALOHA算法能根据每个帧中空闲和碰撞情况动态的调整帧长度，在每一个循环中都利用一个标签估计函数来修改帧的大小。标签估计函数是根据阅读器反馈的空时隙数、成功时隙数和碰撞时隙数计算下一个识别循环需要的时隙数。

增加的动态帧时隙ALOHA算法是基于对标签数量的限制或标识来改进算法。如分组动态帧时隙ALOHA算法，通过分组来限制每帧中的响应标签数。后也有提出通过对分组的函数的改善，提出很多改进的方法。如加入分数参数和标签分组序号的算法，Gen2协议的Q值选择方法。但由于算法复杂，实现起来困难，所以目前应用更多的是动态帧时隙ALOHA算法。

3 二进制防碰撞系列算法

3.1二进制树搜索算法

二进制防碰撞算法是由在一个读写器和多个标签之间规定的相互作用（命令和应答）规则构成的。

算法实现如下：

1）REQUEST（EPC）：请求序列号。读写器发送一序列号作为参数给标签，标签把参数与自己的序列号比较，如果小于或等于，则送回序列号给读写器。

2）SELECT（EPC）：选择标签。读写器发送某个序列号给标签，该序列号的标签将此作为切入开关。

3）READ-DATA：读写数据。选中的标签向读写器发送数据。

4）UNSELECT：取消选择。标签进入不作答状态。

在参数与标准序号比较中，运用了二进制树搜索算法。其思想是通过多次比较，不断缩小相应标签的范围，直至对唯一标签进行识别，再对以上操作循环运行，继续识别下一个唯一标签，直到全部标签识别完为止。在搜索策略上改善的有自适应二叉树搜索算法、自适应查询数算法和返回式搜索算法。

3.2动态二进制树搜索算法和改进的二进制树搜索算法

因标签中序列号中还包含了阅读器发送来的补充信息，为了避免了序列号中多余部分的传输，提高传输速度，提出了动态二进制树搜索算法，在读写器和标签相互作用时，标签序列号去除了补充信息。

对二进制树搜索算法的改进，有后退式索引算法、有跳跃式树形算法、二叉树索索算法、二进制查询树算法、二时隙树RFID标签防碰撞算法、二时隙树算法等，这些算法都在一定程度上提高了识别的效率。

4 基于ALOHA系列算法和二进制搜索算法的混合算法

在ALOHA系列算法中，由于算法简单，实现起来成本低，所以较常用，特别是动态帧时隙ALOHA算法。在标签数量较多，传输数据较大时，动态帧ALOHA算法能发挥出实时性强的优点。但是，ALOHA系列算法对标签的识别是随机的，所以碰撞机会不确定，当发生碰撞的标签过多，将直接导致算法识别效率下降。

而二进制搜索算法因基于树的搜索方法，对标签的选择是可预测的，所以能在标签数量比较少的情况下，对标签的识别的能力较强。但由于需要对每个标签进行请求和响应互动过程，所以当标签数量过多是，会大大降低算法的识别效率。

所以，如果在实际处理中，当标签数不确定时，可采用动态帧时隙ALOHA算法和动态二进制搜索算法结合的混合算法。把防碰撞问题分为标签估计和标签识别两个模块。在标签估计模块中，因标签数量可能比较大，所以先采用适合标签数量较大而比较简单的动态帧时隙ALOHA算法对标签数量进行估计。经过估计，进入识别模块的标签就比较少了，这时再采用动态帧时隙ALOHA算法对标签初步识别，当发生碰撞的时候，碰撞的标签数量又当前比识别模块中标签少，再通过二进制搜索算法对标签进行二次识别。继续进行下个标签估计、识别，如此循环，直至所有标签识别完为止。这样结合了两个系列算法对不同标签数量处理的优势，能大大提高识别效率。

5 结束语

由以上分析可见，在解决标签碰撞问题中，ALOHA系列算法和二进制搜索算法都各有优缺点，在实际处理问题中，可以运用基于ALOHA系列算法和二进制搜索算法的混合算法，发挥两者优点，较快速解决碰撞问题。

参考文献：

[1] Kleinberg J，Tardos E.算法设计[M].张立昂，屈婉玲，译.北京：清华大学出版社，2007.

[2] 黄玉兰.物联网：射频识别（RFID）核心技术详解[M].2版.北京：人民邮电出版社，2012.

[3] 董丽华.RFID技术与应用[M].北京：电子工业出版社，2008.

[4] 王雪.基于二叉树的RFID防碰撞算法的研究[J].通讯学报，2010（6）：49-57.

[5] 孙文胜，金陈敏.新型的RFID动态帧时隙ALOHA防碰撞算[J].信息与控制，2012（4）：233-238.

[6] 王晓东.算法设计与分析[M].2版.北京：清华大学出版社，2008.

[7] 丁治国.RFID关键技术研究与实现[D].合肥：中国科学技术大学，2009.

[9] 程文青，赵梦欣，徐晶.改进的RFID动态帧时隙A10ho算法[J].华中利技人学学报：自然利学版，2007，35（6）：14，16.