基于RFID防碰撞算法综述

刘晓岗　宋高俊

摘要：无线射频识别（Radio Frequency Identification，RFID）技术作为当下最重要的科技之一，以其广泛的应用性将有越来越大的发展前景，RFID技术也由于其非接触的特性，遇到了多目标识别过程中的信息碰撞问题。现对Aloha类防碰撞算法、二进制树防碰撞算法以及改进算法进行分析。

关键词：RFID；防碰撞算法；Aloha；二进制树

RFID系统在识别过程中会有一个普遍的问题，那就是对象冲突，当在同一时间内有若干个电子标签同时请求识别是，阅读器不能正确区别出来，这样当多个电子标签同时发送数据的时候，就会出现数据的干扰导致数据传输失败，这就是文章要研究的防碰撞问题。为了解决这一问题，提高系统的性能，需要制定有效的防碰撞算法，所以防碰撞算法是RFID系统的研究核心。

现有的防碰撞算法包括：Aloha类防碰撞算法，又称为随机性算法；二进制树防碰撞算法，又称为确定性算法；改进算法，在原有的基础上设计出性能更优的算法。

1基于Aloha类防碰撞算法

ALOHA（Additive Link On line Hawaii）算法算是出现比较早的防碰撞算法，它是采取随机多址方式。作为无线通信协议，ALOHA算法研究取得成功后被广泛利用。在理想状态下，利用ALOHA类防碰撞算法，系统最高吞吐率是36.8%。但是在实际应用中，由于各种因素的干扰，系统的识别效率很难达到理想的状态。

1.1纯Aloha算法

纯ALOHA算法也叫基本ALOHA算法，是一种比较容易的时分多址算法。当标签进入阅读器的工作范围内，标签获取能量被激活，向阅读器发送储存在标签内部的数据信息。在这个过程中，假如有两个标签一同向阅读器发送信息，就会产生信息冲突，造成完全碰撞；而当一个标签正在向阅读器发送过程中，另一个标签开始信息传送，这种情况下就会出现标签部分碰撞。只有标签单独在一个时间内进行信息传输时才能让阅读器正常识别，不会出现碰撞情况。使用纯ALOHA算法，系统最大吞吐率只有18.4%，标签发生碰撞概率比能够正确识别概率要大得多。

1.2时隙Aloha算法与帧时隙Aloha算法

由于ALOHA算法中，标签发送数据时间是随机性的，导致完全碰撞或者部分碰撞。于是将纯ALOHA算法进行优化，得到了时隙ALOHA算法。这种算法是把时间划分成若干等长时隙（每个时隙长度满足一个标签成功发送完数据），标签通过不同时隙向阅读器发送数据，如此一来，就能避免部分碰撞的产生，从而总体上缩减了产生碰撞的次数。时隙Aloha算法采用分割时隙思想，避免了标签的部分碰撞，只有成功识别和完全碰撞情况，成倍地提高了信道利用率。但要划分时隙就要解决一个同步问题，在系统中要有同步时钟，使阅读器作用范围内的所有标签达到时隙同步。该算法的系统吞吐率可达到36.8%，比纯Aloha算法效果提高了一倍。

尽管时隙ALOHA算法在信道利用率上比纯ALOHA算法得到一定改进，可是标签发生碰撞的概率依然很大，发生碰撞后的标签会随机接着发送数据，进而影响其他标签的读取，为了避免这种情况，于是研究出了帧时隙ALOHA算法。这种方法是把多个时隙组成一个帧，在每一个帧内，标签任意选择其中一个时隙发送数据，但只可以发送一次。在某一个时隙内，当标签发生了完全碰撞，将会处于休眠状态，等到下一帧进行读取，这样不会影响本帧内其他标签的正常读取。算法中每一帧的时隙数都是固定的，并且时隙长会大于一个标签成功发送完信息的时间。这样，阅读器发送读取指令后，假如一个时隙内仅有一个标签响应，则成功读取标签数据；如果时隙内没有一个标签，就会掠过此时隙；如果存在许多标签的话，产生了碰撞后自动等到下一帧的到来，再选择其他时隙。

2基于二进制树防碰撞算法

二进制树防碰撞算法通过电子标签具有唯一的二进制编码来查询区别。此算法工作原理是将产生了碰撞的电子标签分为0、1两个子集，首先从子集0开始搜寻，要是没有碰撞产生，说明成功识别。如果产生了碰撞，就将碰撞的标签再分成00与01两个子集，再从00子集开始搜寻，重复执行操作。0子集的标签完全成功识别后，转向1子集搜寻，直至把全部标签都识别完，任务结束。

2.1二进制搜索算法与动态二进制搜索算法

与ALOHA类算法不同的是，使用二进制搜索算法需要用到标签自身的序列号和阅读器的查询指令号。当标签序列号与阅读器查询指令相同时，标签产生响应。要是仅有一个标签做出响应，那么成功识别。如果存在若干个标签一同做出响应，阅读器会根据碰撞位情况修正查询指令，经过不断修正查询命令来识别出所有标签。

动态二进制搜索（DBS，Dynamic Binary Search）算法是对二进制搜索算法进行优化的。使用二进制搜索算法，整个标签序列号需要多次被传输，并且阅读器发送的REQUEST指令数据位也多，从而会造成查询时间增加，出错频率也跟着提高。动态二进制搜索算法能很好减少数据位冗余，但是它的运行流程与二进制搜索算法基本相同，只是修改了REQUEST指令。

2.2锁位后退二进制搜索算法与跳跃式动态二进制搜算算法

锁位后退二进制搜索算法也是在二进制搜索算法基础上得到优化的，虽然动态二进制搜索算法能减少数据传输量，但是并不能减少搜索次数。锁位后退二进制搜索算法的工作原理是当阅读器成功识别出一个标签后，阅读器不需要重新发送REQUEST指令，而是直接根据上一层的锁位分组退回到上一层，也就是返回根节点，这样显然会减少搜索次数。

跳跃式动态二进制搜索算法在动态二进制搜索算法和锁位后退算法的基础上结合而成的，涵盖了两种算法的优点，既减少了数据冗余位的发送，也减少了搜索次数，同时缩短了查询时间，也提高了标签识别效率。

跳跃式搜索算法比二进制搜索以及锁位后退搜索需要的查询次数少，比动态搜索算法数据传输量又少，整体性能相对来说是最好。

3改进算法

为了使识别效率更好，不少学者在原有的基础上，提出了新的改进算法，有学者提出了优化帧内时隙长度的策略，并通过马尔科夫建模实现对标签的读取周期数达到减少的目的。同时，基于二进制树的防碰撞算法也有很多学者在研究，并且在其基础上提出了不少改进算法，如改进的返回式动态二进制算法、NTA算法、EMBT算法和二叉树搜算算法等，相比之前的动态二进制搜算算法，在平均比特数上，实现了大大的减少，提高了识别效率。最近，有学者提出GDRA（geometric distribution reader anticollision）拓扑方案，利用筛选几何概率分布函数来实现阅读器碰撞问题最小化，它能提供更高的吞吐量，符合EPC国际标准，在不需要额外的硬件条件就可在真实的RFID系统中实现功能。

4结语

相比之下，Aloha类算法操作简单，识别时间短，但稳定性不足，系统利用率最高也只能达到36.8%，并且当标签数量增加时，系统的识别效率将下降的很快。二进制算法虽然识别效率高，稳定性也较好，但是操作复杂，识别时间较长。改进算法在原有的基础上，实现新的突破，在准确度、信道利用率、稳定性等方面寻求改善，是未来的研究方向之一。