ABSTRACT

In the RFID system, in order to avoid signal interference caused by that multiple tags simultaneously communicate with the reader, there must be some certain anti-collision algorithms. This paper describes several common anti-collision algorithms, then puts forward the Binary ALOHA Algorithm based on the Slotted ALOHA Algorithm and Improved Dynamic Binary Tree Search Algorithm. By analyzing the run results of the project, it shows that the new algorithm has a smaller size of the data transfer and a higher identify efficiency compared to the Improved Dynamic Binary Tree Search Algorithm. Meanwhile, the new algorithm can avoid the possibility of emerging the tag hungry in Slotted ALOHA Algorithm.

Keywords:RFID, Anti-Collision, ALOHA Algorithms, Binary Tree Search Algorithm, Binary ALOHA Algorithm

RFID系统中防碰撞算法的研究与改进

李  璐，王移芝

北京交通大学，计算机与信息技术学院，北京

Email: 996716105@qq.com

收稿日期：2014年10月24日；修回日期：2014年11月25日；录用日期：2014年12月4日

摘  要

在RFID系统中，为了避免多个标签同时与阅读器进行通信而造成的信号干扰，必须采用一定的防碰撞算法。本文详细介绍了目前几种常见的防碰撞算法之后，提出了基于时隙ALOHA算法和改进的动态二进制搜索算法的新型算法：二进制ALOHA算法。通过对运行结果的比较分析，可以证明新算法相比于改进的二进制搜索算法具有更小的数据传输量和更高的识读效率，同时又避免了时隙ALOHA算法出现标签饥渴的可能。

关键词

RFID，防碰撞，ALOHA算法，二进制搜索算法，二进制ALOHA算法

1. 引言

射频识别(RFID: Radio Frequency Identification)技术是近年来发展较快的一项技术。RFID技术通过射频信号，非接触式的在电子标签与阅读器之间双向的传递信息，以达到自动识别的目的。由于其具有识别速度快、识别准确率高、可以非接触识别等优点，目前被广泛应用于交通运输管理、物流管理、商业自动化等众多领域之中，被誉为二十一世纪最具发展潜力的十大战略性产业之一[1] 。

RFID系统区别于传统条形码系统的一个重要特点就是它一次可识读多个电子标签。RFID系统中的每个电子标签都有唯一标识的编码，阅读器的主要任务就是正确识读这些信息[2] 。而当一个RFID系统中阅读器工作范围内存在多个电子标签时，同一时刻就可能会有不止一个标签向阅读器发送信息。这样，多个标签的发送信号之间就可能会相互干扰，使得阅读器无法正确的接收标签发出的信息，这种情况即为标签碰撞。而解决标签碰撞问题的方法称为防碰撞算法。

本文将对目前几种常见ALOHA算法和二进制搜素算法进行介绍，并在此基础上提出一种全新的防碰撞算法，以提高RFID系统的标签识别效率。

2. 现有防碰撞算法

目前时分多路法中最常见的两类防碰撞算法是ALOHA算法和二进制搜索算法。ALOHA算法是一种随机性算法，有可能会出现某一标签在很长时间内不被阅读器识别的情况，即存在标签饥渴的问题，因此也称为不确定算法。二进制搜索算法是一种确定性算法，这类算法与ALOHA算法相比较为复杂，识别时间也相对较长，但是不存在标签饥渴的问题[3] 。

各种防碰撞算法之间没有绝对的优劣之分，不同的防碰撞算法适用于不同的环境。在高频频段，一般采用ALOHA算法，绝大多数的高频阅读器能够同时识读几十个标签。在超高频频段中，目前主要采用的是二进制搜索算法。

2.1. ALOHA算法

ALOHA算法是一种数据信号随机接入的方法[4] 。当碰撞发生时，所有发生碰撞的标签发送的数据都会出现差错而导致发送失败，因此所有碰撞方都必须进行数据重传。但各方不能在碰撞之后立即开始重传，因为这样必定会导致再次碰撞。ALOHA算法采用的重传策略是发生碰撞的标签随机等待一段时间后再重新发送数据。由于每个标签数据的传输时间相对于重传等待时间来说非常短，因此标签两次数据发送之间有相对较长的时间间隔，这样就存在一定的概率，使得多个电子标签选择不同的时间发送数据，以避免碰撞的发生。

为了简化对ALOHA算法的分析，假设标签数据包的发送符合泊松分布。由吞吐量和网络负载的定义可知，与的关系为：

(1)

式(1)中的表示数据包发送成功的概率。由于我们假定了数据包的发送是一个泊松过程，即在T0时间内有个数据包发送的概率为：

而数据包发送成功的条件是在2T0的时间内没有其他数据包发送，因此数据包发送成功的概率为：(2)

由式(1)和式(2)有：

(3)

分析式(3)可知，当小于0.5时，随着的增加而增大，并在时达到最大值0.1839；当大于0.5后，随着的增大而逐渐减小。在ALOHA算法的实际应用中，为了保证系统的稳定性，值不应超过10%。

2.2. 时隙ALOHA算法

时隙ALOHA算法是一种随机时分多址方式的用户信息通讯收发算法[5] 。在这种算法中，将数据的传输时间划分成许多个等长的时隙，时隙的长度为一个数据包发送成功所需要的时间。时隙ALOHA算法规定标签只能在一个时隙开始的时候传输数据。这样，数据包只存在两种状态：发送成功或完全冲突[6] 。用于传输数据的时隙由阅读器控制，只有当阅读器分配完所有的时隙之后，标签才允许利用这些时隙来传输数据。

为了简化对时隙ALOHA算法的分析，我们假设标签数据包的发送符合泊松分布。设一个时隙为T0，即在T0时间内有个数据包发送的概率为：

(4)

由于时隙ALOHA算法规定标签只能在每个时隙开始时刻发送数据，因此数据包发送成功的条件为在同一时隙没有其他标签发送数据，因此其发送成功的概率为：

(5)

由式(1)和式(2)可得，吞吐量为：

(6)

分析式(6)可知，在时隙AccLOHA算法中，当网络负载时，其吞吐量达到最大36.79%，之后随着的增大，会迅速减小，使得重传次数迅速增大，成功发送一个数据包所需要的时间也不断增加，最终导致系统崩溃。相比于ALOHA算法，时隙ALOHA算法更加适合于标签数量较多的情况。

2.3. 二进制搜索算法

二进制搜索算法又名二叉树算法，它是基于树分叉搜索算法实现的。要求阅读器能够准确识别出数据碰撞的位置。之后根据一系列循环操作，识别所有标签。二进制搜索算法实现流程如图1所示。

其识别步骤说明如下：1) 阅读器设置初始筛选条件为全1，向其工作范围内的标签发出请求信号。2) 所有标签均符合筛选条件所以全部响应，并向阅读器返回自身序列号。3) 阅读器分析各标签返回的信息，若发生碰撞，阅读器检测出所有碰撞位置，重新修改筛选条件，将最高碰撞位置0，其余低位置1，重新发送请求信号。4) 编码小于等于阅读器请求信号的标签响应阅读器请求，并返回自身序列号。5) 重复上述识别过程，阅读器重复发送请求指令，直至有唯一标签响应，即无碰撞产生时，阅读器读取该标签信息，并令该标签进入“去活”状态。6) 若阅读器工作范围内仍有待识别标签，阅读器重置筛选条件为全1，重新发送请求信号，重复上述识别过程。直至所有标签识别完毕，此次识别过程结束。

分析可知，阅读器采用二进制搜索算法来识别个标签所需的搜索次数与标签之间碰撞位的位置和编码值均相关。最好状况下搜索次数为，最坏情况下的搜索次数为，即：

(7)

阅读器每次向标签发出请求指令的长度与标签的编码长度相同，即有：

(8)

由式(7)和式(8)可知，二进制搜索算法完成对个编码长度为的标签全部识别需要发送请求指令的数据长度总和为：

(9)

图1. 二进制搜索算法流程

2.4. 改进型动态二进制搜索算法

二进制搜索算法在识别的过程中，标签信息直接出现在阅读器的请求信号和标签的应答信号中，这有可能会引起RFID系统被远距离窃听等安全方面的问题[7] 。为了保证标签与阅读器通信过程中的数据安全性和数据传输的高效性，改进的动态二进制搜索算法被提出。改进的动态二进制搜索算法识别流程如图2所示[8] 。

其识别步骤说明如下1) 置全体标签休眠程度为0。阅读器向其工作范围内的标签发送REQUEST(NULL，X)请求指令。X为标签编码位数，该指令为全体响应指令。2) 阅读器工作范围内全体标签响应该指令，并向阅读器发送自身序列号。3) 阅读器分析标签返回的信息，找出最高碰撞位K，向标签发出REQUEST(0，K)指令；4) 满足条件的标签响应并返回自身序列号，其余未响应标签令其休眠程度加1。5) 重复上述识别过程，直至有唯一标签响应，即无碰撞产生时，阅读器读取该标签信息，之后将该标签去活。6) 阅读器成功识别一个标签之后，向休眠标签发出激活指令，令其休眠程度减1。休眠程度归0的标签进入待命态，算法进入上行搜索策略。7) 阅读器分析待命态标签的序列号信息，找出最低碰撞位K，发出REQUEST(1，K)指令。8) 重复上行搜索过程，直至最高碰撞位置1后，算法重新进入下行搜索策略。9) 重复以上搜索过程，直至所有标签识别完毕，此次识别过程结束。

图2. 改进的动态二进制搜索算法实现流程

分析可知，改进的动态二进制搜索算法识别个标签所需要的搜索次数为：

(10)

阅读器每次发出的请求指令长度为：

(11)

由式(10)和式(11)可知，改进的二进制搜索算法完成对个编码长度为的标签全部识别需要发送请求指令的数据长度总和为：

(12)

3. 新型防碰撞算法

通过第二章对四种防碰撞算法的分析描述，我们可知，在随机性防碰撞算法中，时隙ALOHA算法的算法性能好于纯ALOHA算法，而在确定性防碰撞算法中，改进的动态二进制搜索算法不仅实现较为简单，而且数据传输量小，数据安全性高。时隙ALOHA算法和改进的动态二进制搜索算法在标签数量不是很大的条件下都有较好的识别效率，

下面我们通过控制变量法对时隙ALOHA算法和改进的动态二进制搜索算法的识读时间进行计算。令标签数量为5，编码为8位，时隙ALOHA算法中数据重发最大时隙为5，标签随机选择发送时隙。多次运行时隙ALOHA算法和改进的动态二进制搜索算法程序，其识读时间统计结果如表1所示。

由表1可以看出，采用时隙ALOHA算法的RFID系统阅读器识读同等数量标签所用时间要小于改进的动态二进制搜索算法。在这里必须指出上表中所列出的时间只是程序执行算法的时间，没有包括数据传输的时间。由于改进的动态二进制搜索算法需要传输的数据多于时隙ALOHA算法的数据，因此在实际情况中，时隙ALOHA算法的识读速率会远高于改进的动态二进制搜索算法。但是，时隙ALOHA算法是一种随机搜索算法，即不确定算法，存在一定的几率使得两个或两个以上的标签长时间处于相互碰撞的状态下。为了保证RFID系统较高的工作效率，并尽可能的减少数据传输量，同时保证不会出现电子标签信息漏读的情况，本文提出一种基于时隙ALOHA算法和改进的动态二进制搜索算法结合的混合算法，为了方便后文表述，将其命名为二进制ALOHA算法。该算法工作流程如图3所示。

具体实现方法如下：1) 当两个及以上的标签同时进入阅读器识别范围后，向阅读器发送信息，阅读器检测到碰撞，并确定当前标签数量n。2) 阅读器分配n个时隙，时隙的长度为标签发送完成全部数据所需时间。每个电子标签随机选择一个时隙作为其数据发送时间。3) 阅读器依次检查每个时隙，若该时隙内只有唯一标签发送数据，则选中该标签并与之进行通信，读取完成后令其进入“去活”状态；若有多个标签同时发送数据，则阅读器检测到碰撞，不对这些标签进行任何处理。4) 所有时隙检查完成后，所有未被“去活”的标签进入第二轮筛选。5) 同改进的动态二进制搜索算法，阅读器首先发送全体请求信号，未被去活的所有标签响应，之后阅读器根据标签的响应信号判断其碰撞位，并通过循环不断发出请求信号，最终完成对所有标签的识别。

特别需要指出的是，在阅读器对n个电子标签进行识读的过程中，当有其他标签进入时，若其在时隙ALOHA算法阶段入站，则该标签参与二进制搜索算法识别过程；若其是在二进制搜索算法阶段入站的，则其等待阅读器下一轮的识别。

在二进制ALOHA算法中，由于标签随机选择阅读器初始分配的个时隙，因此我们可知，标签成功发送的概率为：

(13)

图3. 改进的动态二进制搜索算法实现流程

时，的值如表2所示。

由于在二进制ALOHA算法第一阶段中，10个标签均会向阅读器发送自身数据，因此第一阶段的数据传输量为。由表2可知，时，平均有3.8个标签被阅读器成功识读。即在二进制ALOHA算法的第二阶段，平均只需传输6.2个数据包。因此，电子标签向阅读器的数据传输量为，而阅读器向电子标签的数据传输量为。综上所述，在二进制ALOHA算法中，总的数据传输量为。

在改进的动态二进制搜索算法中，阅读器在识读电子标签时，电子标签至少要响应三次阅读器请求。第一次是响应阅读器的全部请求信号，第二次响应阅读器检测到碰撞后的条件请求信号，第三次是响应阅读器读取请求。因此x的值一定大于等于3，由此可知，对于时隙ALOHA算法、改进的动态二进制搜索算法、二进制ALOHA算法，识别10个标签的数据传输量分别为：272、76 + 80x、126.4 + 50.4x，而由于x大于等于三，因此二进制ALOHA算法相比改进的动态二进制搜索算法具有更小的数据传输量。

三种算法程序运行结果如表3所示。

由表3数据可知，利用二进制ALOHA算法的程序运行时间要长于时隙ALOHA算法，但小于改进的动态二进制搜索算法。且采用二进制ALOHA算法避免了由于时隙ALOHA算法随机性而造成的数据无法准确识读的情况[9] ，保证了RFID系统采集数据的可靠性。同时相比于改进的二进制搜索算法，不仅缩短了标签的识读时间，而且减少了数据的传输量，提高了算法的综合性能。

4. 结束语

本文在对现有的几种防碰撞算法进行简要介绍后，提出了一种新型防碰撞算法：二进制ALOHA算法，通过对比在不同标签数量下与时隙ALOHA算法和改进的动态二进制搜索算法程序运行时间，识读相同数量标签的数据传输量，证明该算法不仅能够有效避免时隙ALOHA算法可能出现漏读的问题，同时相比于二进制搜索算法有较小的数据传输量和较高的识读效率。

在下一步的工作中，将对如何进一步提升阅读器的标签识别效率和降低系统建设成本进行研究，同时将对如何减少在标签识别过程中的数据传输量进行深入研究，以期进一步优化标签识别过程。

致  谢

感谢在本文撰写过程中对我提供无私帮助的王移芝教授，正是她的悉心指导为我指明了前进的方向，是她每一次的鼓励让我一直坚持不放弃。她严谨的治学态度，坦荡的胸襟，高尚的人格，都将是我今后研究学习生活中的宝贵财富。

感谢在百忙之中审阅此稿的专家和老师，感谢你们提出的宝贵意见和建议。

感谢所有在我成长中给予我关怀和帮助的人们！

参考文献 (References)