一种改进的后退式二进制搜索RFID多标签防碰撞算法

张文欣， 昂志敏， 尹夕振

（合肥工业大学计算机与信息学院，安徽合肥 230009）

射频识别（Radio Frequency Identification，简称RFID）技术［1］是一种非接触的自动识别技术，它一般通过无线射频技术对目标进行自动识别并获取相关的数据［2］。当读写器的作用范围内存在多个标签，并且有2个或者2个以上的标签同时发送数据至读写器时就会产生信息之间的相互干扰，导致读写器无法正常识别出每个标签的数据，这就是标签碰撞问题。为了解决这个问题，必须采用有效的防碰撞算法［3］。

RFID系统中标签防碰撞算法一般有频分多路（FDMA）、空分多路（SDMA）、码分多路（CDMA）和时分多路（TDMA）。考虑到RFID系统中通信形式、功耗、系统的复杂性及成本等因素，目前广泛采用基于TDMA的防碰撞算法，主要有ALOHA算法［4］和二进制搜索算法［5］。ALOHA算法的所有电子标签的数据都是随机发送的，操作简单，便于实际应用，但是当系统中标签数量大量增加时，性能会急剧恶化。二进制搜索算法电路实现比ALOHA算法复杂，但算法识别率和系统吞吐率都比较高。本文在二进制搜索防碰撞算法的基础上，提出一种改进的防碰撞算法。

1 算法的几点约定

1.1 Manchester编码

采用Manchester编码来辨认出读写器中数据碰撞的比特位的准确位置，该编码通过电平的改变来表示数值位，用逻辑“0”表示上升沿跳变，用逻辑“1”表示下降沿跳变。如果没有状态跳变，就被视为非法数据，作为错误被识别。当2个或多个标签同时返回的数位有不同值时，将会出现上升沿与下降沿互相抵消，以至于无状态跳变，读写器便知道该位出现碰撞，产生错误，因而会进一步搜索［6］。假设有2个RFID标签，其ID为8位，利用Manchester编码能按位识别出碰撞位，如图1所示。

图1 采用Manchester编码按位识别碰撞位

读写器检测出D1、D4位出现碰撞，可知区域内存在多个RFID标签。

1.2 引入4种命令描述算法

（1）Request。请求命令，请求发送一序列号作为参数给区域里的标签。标签将自己的序列号与接收到的序列号相比较，如果小于或者等于，则回送此标签的序列号给读写器。

（2）Select。选择命令，用某个事先确定的序列号作为参数发送给标签，具有相同序列号的标签被激活，并以此作为执行其他命令（例如读出和写入）的切入开关，即选择了这个标签。

（3）Read－data。读出数据，选中的标签将存储的数据发送给读写器。

（4）Unselect。去选择，取消事先选中的标签，使该标签进入“无声”状态。在此状态下，标签不会对Request命令做出应答。只有将标签远离读写器的作用范围即没有能量供应后复位，才能重新激活标签。

2 算法原理

2.1 后退式二进制搜索算法

算法特点是发生碰撞时，根据碰撞的最高位，跳跃式向前搜索；无碰撞时，采取后退策略，实现标签的有序读取。当读写器识别出一个标签后不是从根节点开始重新查询，而是退到它的上一层节点，也就是父亲节点［7］。此算法实现过程如下。

（1）读写器发出Request（11111111），读写器作用区域内所有标签都应答。

（2）检查是否有碰撞发生，如果无碰撞则直接识别标签；如果有碰撞，找到碰撞的最高位。

（3）有碰撞时，将发生碰撞的最高位置“0”，低于该位的所有位全部置“1”，高于该位的不变，获得下次Request命令的寻呼参数。

（4）无碰撞时则直接识别出一个单独的标签，然后采用后退策略，从上一次的参数的父亲节点处获取下一次Request命令的寻呼参数。

（5）重复进行上述步骤，直到把所有的标签全部识别出来。

2.2 改进算法

（1）只标识发生碰撞的比特位，且只在被标识的比特位上进行防碰撞处理。未发生碰撞的比特位对于读写器来说是已知的，故当读写器与标签通信时，不需要再传输已知的比特位，只需在未知的比特位上进行防碰撞处理，这样能减少发送的指令长度及能量消耗。

（2）当有碰撞发生时，先通过碰撞位中“1”的个数来识别标签，直接识别出碰撞位全为“1”和全为“0”的标签。

（3）由于电子标签的ID是采用曼彻斯特编码的，每个比特位的取值不是0就是1，是互斥的，因此当读写器检测到只有1个比特位发生碰撞时，读写器就不需要发送请求命令，而能够直接识别出这2个标签。

（4）本算法引入命令Request（UID，1）。UID表示的是读写器第1次发送Request指令后，根据其译码结果得到下一次Request指令所需的参数。UID取值有如下约定：当标签数据传输发生碰撞时，读写器先判断出在哪几位发生了碰撞，然后将碰撞位置“1”，未碰撞位置“0”，组成新的Request指令。当电子标签接到读写器发出的Request指令后，标签将自己的ID与此指令内容进行比较，其中与UID中的值为“1”所对应的比特位将被标识出来。这样在之后的防碰撞处理中，只有被标识的比特位参与数据发送和比较。所有标签中被标识的比特位中最高位为“1”的标签，将自己的ID返回给读写器。

2.3 算法实现

假设标签的ID为8位，在读写器作用区域内有8个标签，分别为：标签1，00010111；标签2，00110101；标签3，00011111；标签4，00111001；标签5，00111111；标签6，00010101；标签7，00011011；标签8，00110111。具体实现过程如下。

（1）读写器发送Request（11111111），读写器作用区域内所有标签都应答，读写器译码得到数据为00？1？？？1，可得到下一次寻呼指令为Request（00101110，1），第D5、D3、D2和D1位数据发生碰撞，根据算法直接识别碰撞位“1”的个数为0和4的标签，即标签5：00111111。

识别标签后，对已识别的标签5进行Select激活，再通过Read指令读取被激活的标签，最后用Quiet指令对标签进行去选择操作，使其进入“无声”状态，屏蔽标签5。

（2）读写器发送Request（00101110，1），所有标签ID的D5、D3、D2和D1位被标识，其新的ID为0011、1010、0111、1100、0010、0101、1011，标签5已被识别并屏蔽，此时最高位为1的标签2、4、8回送自己新的ID给读写器，读写器译码结果为1？？？，得到下一次寻呼指令为Request（0111，1）。

（3）读写器发送Request（0111，1），标签2、4、8应答，其ID的D2、D1和D0位被标识，得到新的ID：010、100、011。新ID中最高位为1的标签4回送其新的ID给读写器，读写器选中标签4并进行读取操作，最后对标签4进行去选择操作，使其进入“无声”状态，屏蔽标签4。此时算法采用后退策略，回到该节点的父亲节点，获得下一次寻呼指令Request（111）。

（4）读写器发送Request（111），标签2、8应答，译码结果为01？，此时只有一位发生了碰撞，因此可以直接识别出来，读写器直接选中标签2和8并进行读取操作，最后对标签2和8进行去选择操作，使其进入“无声”状态，屏蔽标签2和8。算法再次采用后退策略，回到该节点的父亲节点，获得下一次寻呼指令Request（1111）。

（5）读写器发送Request（1111），标签1、3、6和7应答，读写器译码结果为0？？？，根据算法直接识别碰撞位“1”的个数为0和3的标签，即标签3：0111。读写器选中标签3并进行读取操作，最后对标签3进行去选择操作，使其进入“无声”状态，屏蔽标签3。根据读写器译码结果得到下一次寻呼指令Request（0111，1）。

（6）读写器发送Request（0111，1），标签1、6、7应答，其序列号的D2、D1和D0位被标识，得到新的ID：011、010、101。标签7回送其新的ID给读写器，读写器选中标签7并进行读取操作，最后对标签7进行去选择操作，使其进入“无声”状态，屏蔽标签7。

此时算法采用后退策略，回到该节点的父亲节点，获得下一次寻呼指令Request（111）。

（7）读写器发送Request（111），标签1、6应答，译码结果为：01？。此时只有一位发生了碰撞，因此可以直接识别出来，读写器直接选中标签1和6，并进行读取操作，最后对标签1和6，进行去选择操作，使其进入“无声”状态，屏蔽标签1和6。

查询过程如图2所示。由图2可知，本算法识别出8个标签只需要发送7次指令，而后退式二进制搜索算法［7－8］需要2×8－1＝15次。可见本文的改进算法不仅在工作效率上而且在发送指令的长度上都有了很大改进，能较快地进行识别。

图2 算法搜索过程

3 算法性能分析

用后退式二进制搜索算法进行识别时，一个根节点下面有若干个子节点，父子节点之间可以双向搜索。因此对n个标签进行识别时，搜索次数为S（n）＝1＋（n－1）×2＝2n－1。由于本文算法是在基于后退式二进制搜索算法基础上进行的改进，故即使在最不理想的情况下，也可以保持搜索次数为2n－1。

当读写器作用区域内标签数量n较大时，发生多位碰撞的概率增大。本文算法中，先通过碰撞位中“1”的个数识别标签，而且只有碰撞位才被标识并参与以后的防碰撞处理，因此大大减少了搜索次数，有效地减少了发送和接收的信息量，缩短了传输时间，提高了识别的效率。

将本算法与后退式二进制搜索算法的搜索次数进行比较，假设标签ID为16位，通过Matlab［8］仿真得到结果，如图3所示。

图3 算法的性能比较

由图3可知，当标签数量不是很多时，本算法相比于后退式二进制搜索算法的优势并不明显，而当标签数量明显增多时，本算法优势逐渐明显，搜索次数明显减少，并且由于发送信息量减少，效率明显高于后退式二进制搜索算法。

4 结束语

防碰撞问题一直以来都是RFID技术的关键问题。本文在研究了后退式二进制搜索算法的基础上，提出了改进算法，本算法改变了发送指令的长度，减少了发送信息的信息量和读写器的搜索次数，提高了标签识别效率。通过仿真分析验证了本算法能更快地识别出碰撞的标签，相比于后退式二进制搜索算法具有更高的效率，因此具有良好的应用前景。

［1］ 康 东，石喜勤，李勇鹏，等.射频识别（RFID）核心技术与应用开发案例［M］.北京：人民邮电出版社，2008：165－178.

［2］ Yang C N，He J Y.An effective 16－bit random number aided query tree algorithm for RFID tag anti－collision［J］.Communications Letters，IEEE，2011，5（15）：539－541.

［3］ 单承赣，孙 明.基于后退策略的位传输二进制搜索算法［J］.合肥工业大学学报：自然科学版，2010，33（1）：68－71，80.

［4］ 赵晓霞，昂志敏，郭 治.一种新的时隙ALOHA算法［J］.合肥工业大学学报：自然科学版，2010，33（6）：855－858.

［5］ 冯东旭，夏哲雷，凌访华.一种改进的RFID防碰撞算法［J］.杭州电子科技大学学报，2010，30（5）：109－112.

［6］ 孙文胜，马建波.基于二进制搜索算法的RFID系统防碰撞算法［J］.计算机应用与软件，2010，27（12）：268－269，287.

［7］ 余松森，詹宜巨，彭卫东，等.基于后退式索引的二进制树形搜索反碰撞算法及其实现［J］.计算机工程与应用，2004，40（16）：26－28.

［8］ 赵 谦.通信系统中Matlab基础与仿真［M］.西安：西安电子科技大学出版社，2010：55－129.