基于二进制的RFID防碰撞算法研究与改进

摘要：标签防碰撞技术是射频识别（ RFID） 系统中提高标签识别效率的关键技术。在对基本二进制搜索算法（BS）的基础上，提出一种结合动态二进制搜索算法（DBS）和后退式二进制搜索算法（BBS）优点的改进算法，并对改进算法进一步优化。仿真结果表明，该算法能减少阅读器问询标签的数据量，有效地提高了标签识别的速度。

关键词：RFID；防碰撞；二进制搜索

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）09-2209-02

无线射频识别RFID是一种非接触式自动识别技术。因其具有识别速度快、距离远，抗干扰能力强等优点，被广泛应用于物品管理、物流等领域。

RFID系统主要由标签、阅读器及计算机系统三部分组成。每个标签拥有唯一的序列号ID。RFID 系统中多个标签可能会处于同一阅读器识别范围内，当多个标签同时响应阅读器时会产生信号干扰，致使阅读器无法正确识别标签，也即发生了标签碰撞。碰撞导致了标签被漏读，因此必须采用防碰撞策略来避免碰撞发生，识别全部标签。

1 基于二进制RFID防碰撞算法

二进制防碰撞算法是将碰撞的标签分成左右两个子集，先查询左子集0，若没有碰撞，则正确识别标签，如若仍有碰撞就再继续进行分裂，分成00和01两个子集，依次类推，直到识别出左子集0中的全部标签，再按此步骤查询右子集1。

1.1 二进制树搜索（BS）算法

在BS算法中，阅读器查询的不是一个比特，而是一个比特前缀，只有标签与这个查询前缀相符的标签才能响应阅读器的命令。当只有一个标签响应的时候，阅读器可以成功识别标签，但有多个标签响应的时，发生碰撞。 为了最简捷地实现二进制搜索算法，数据编码选用Machenster编码，依据其编码特点可以检测出碰撞位。

要从大量的标签中识别出唯一的标签，需要重复搜索操作。其识别的平均操作次数由阅读器范围内的标签总数n决定[1]：

利用BS算法可以较简单地解决碰撞问题，但随着标签数量的增多，重复操作的平均值很快增加。完成n个标签识别需要的总问询次数如下公式所示：

所有标签都需要发送完整的序列号来响应阅读器的问询。识别n个序列号为k位的标签，阅读器需要传输的总比特数为标签序列号长度与算法总搜索次数的乘积

1.2 动态二进制搜索（DBS）算法

上述BS算法虽然简单，但其不仅搜索范围较大，而且在阅读器问询和标签回应时序列号要全部传输。标签序列号可能长达12个字节，为了选择一个标签，所以数据传输量较大。因而DBS 算法被提出。

如果研究阅读器和单个标签之间传输的数据，就可以得出以下结果。假设H为最高碰撞位，标签序列号长度为K。

⑴ 请求命令（H-1）～0位中不包含任何给标签的补充信息，因为各位总是被置为“1”。

⑵ 标签应答的序列号的K～H位不包含任何给阅读器的补充信息，因为这些位是阅读器已经给定的。

由于DBS与BS使用相似的搜索过程，故可以得出的DBS算法总搜索次数。

DBS算法识别标签时，首先要求作用范围内的所有标签都上传各自的序列号，n个标签的序列号总长度就是第一次上传的数据长度，即整个序列号长度作为传输比特数。阅读器识别搜索一次传输平均数据量为[2]

当阅读器使用DBS算法时，识别n个标签所需要传输的序列号总长度为

1.3 基于后退索引的二进制搜索（BBS）算法

BBS算法中，阅读器完成一个标签的识别后，返回上一次发生碰撞的节点[3]，识别该节点的另外一个分枝，不断重复操作，直到把上一节点碰撞的标签识别完。其识别n个标签，阅读器共需问询2*n-1次。假设标签序列号长度为kbit，则在阅读器的发送的数据量为（2*n-1）*kbit。BBS的优点是减少了问询次数，而DBS的优点是减少了问询中参数长度，如果能将两者的优势结合，必能提高性能。该文提出了以下改进算法。

1.4 返回式动态二进制算法BDBS

下面以4个标签为例（10110011、10100011、10110010、11100011），首先引一条命令REQUEST命令，即REQUEST（ID（K～X），X），X为碰撞的最高位，其作用是让阅读器发送一个参数（标签的第K-H位）给区域内标签，序列号K～H位与之一致标签传输剩余的（H-1）～0位信息作为应答。阅读器完成一个标签的识别后，返回上一次发生碰撞的节点，识别该节点的另外一个分枝，不断重复操作，直到把上一节点碰撞的标签识别完。算法的执行过程如下：

第①步，阅读器发送REQUEST（NUL，8），处于阅读器作用范围的所有标签都返回其ID给阅读器，解码数据为1X1X001X，碰撞最高位是D6，将D6置“0”，高位不变，得到ID（K～H）取10，H取6作为下一次命令所需的两个参数。

第②步，阅读器发送REQUEST（10，6），序列号前缀为10的标签响应，即标签10110010、10100011和10110011响应。各自返回后6位的信息110010、100011、110011。阅读器得到解码数据为1X001X，将碰撞最高位D4置为“0”。

第③步，阅读器发送REQUEST（1010，4），序列号前缀为1010的标签响应，只有标签10100011响应，无碰撞发生，读写器处理完该标签后对它进行屏蔽。

第④步：从该节点的父节点获得下一次REQUEST指令参数，阅读器发送REQUEST（1011，4）。标签1和标签3应答，阅读器解码数据为001X。

第⑤步：阅读器发送REQUEST（10110010，0）指令，标签3应答。阅读器对标签3进行处理后使其进入“无声”状态。

第⑥步：阅读器发送REQUEST（10110011，0）指令，只有标签1应答。阅读器对标签1进行处理后使其进入“无声”状态。采用返回策略，返回到最上一个父节点11。

第⑦步：阅读器发送REQUEST（11，6）指令，标签4应答，阅读器读取标签4的数据，识别过程结束。

在BDBS算法中，阅读器的搜索次数为2n-1，阅读器传输每次搜索平均传输的数据量为（k+1）/2，所以阅读器识别所有标签所需要发送的数据量为

对于BDBS搜索算法，当标签数量较多时，比BBS通信量减少近50%，比DBS减少约67%，比BS减少达到80%。如仿真图1所示。

1.5 改进的BDBS

在标签碰撞位只有一位时，说明只有两个标签发生碰撞，则认为没有发生碰撞。一个标签的碰撞位为“0”。另一个标签的碰撞位为“1”，直接识别标签。则阅读器的搜索次数减少为（2n-1）-[n/2]（[]为向上取整），则完成n个标签问询，阅读器所需发送的数据量为

对阅读器的问询通信数据量进行比较。如图2所示，数据量较BDBS减少了约25%，性能得到了提高。

2 结论

本文提出了一种改进的二进制搜索算法，通过分析仿真和比较，得出该算法优于二进制搜索算法BS，随着标签数量的增加优势更加明显。极大地减小了阅读器问询识别范围内标签的通信量，提高了标签的识别速度。

参考文献：

[1] 鞠伟成，俞承芳.一种基于动态二进制的RFID抗冲突算法[J].复旦学报自然科学版，2005.

[2] 周晓光，王晓华.射频识别（RFID）技术原理与应用实例[M].北京：人民邮电出版社，2006.

[3] 鞠伟成，俞承芳.一种基于动态二进制二进制的RFID 抗冲突算法[J].复旦学报，2005：46-50.