无线射频识别标签防碰撞算法比较分析

王佩玮

摘 要：在无线射频识别系统中，读写器通过广播方式向标签传输指令。而标签通过多路存取的方式返回自身标识数据给读写器。具体防碰撞算法有很多，为了合理选择最优的防碰撞算法，文中将对基本二进制树防碰撞算法以及后退二进制树防碰撞算法进行比较分析。得出了后退二进制树防碰撞算法优于基本二进制树防碰撞算法的结论。

关键词：无线射频识别；读写器；基本二进制树防碰撞算法；后退二进制树防碰撞算法

中图分类号：TP391 文献标识码：A 文章编号：2095-1302（2017）04-00-04

0 引 言

当无线射频识别系统工作时，若有多个电子标签进入读写器的广播范围，并同时发送信号给读写器，数据碰撞就无法避免。碰撞会导致数据发送失败，因此必须采取合适的方法以防止碰撞产生。标签防碰撞问题的实质是将电子标签依次放入读写器，区分出不同的电子标签，确保通信没有遗漏。

1 基本二进制树防碰撞算法

基于树的标签防碰撞算法在执行过程中，读写器不断更新广播请求码，通过返回结果将电子标签分成两个分支，直至确定每个电子标签。在判断寻找过程中，对应的请求命令参数会以节点的形式进行储存，最后将得到一个类似二叉树的数据结构，而且由于这些请求命令参数都用二进制形式表示，该算法又被称为“二进制树”算法。在介绍算法时，由于在不同协议下序列号的数据位数、数据格式以及编码方式都有所不同，本文预先设定一个长度为8的二进制数。

基本二进制树防碰撞算法识别标签时，读写器需要多次发送电子标签的标签序列号。这时定义数据传送的顺序为由低位到高位依次发送。在读写器或电子标签内部比较数据时也遵循这一原则。按照标签序列号由低位再到高位的顺序比较，约定0<1。根据该顺序，判断数据的大小时从最低位开始。即两个数A，B相比，从最右边的低位开始，直到遇到不相等数位。当两个数的所有数位都相同时，这两个数就是相等的。

基本二进制树防碰撞算法的步骤如图1所示。

因为每个电子标签的序列号都不相同，所以当多于两个的电子标签同时给读写器发送数据时，就不可避免地发生碰撞。当碰撞发生后，请求码中相应碰撞最高位的数值将被设定为0，低于碰撞位的数值保持不变，高于碰撞位的数值设定为1，生成新请求码。读写器将更新后的请求码传递给电子标签，电子标签会继续用自己的序列号与新请求码进行比较。如果序列号不大于请求码，则会返回自身的序列号给读写器。

反复执行上述步骤，直到选出序列号最小的电子标签，读写器将给该标签发送指令使其进入休眠状态。换言之，下次读写器发送最大序列号请求码时，该电子标签不会做出回应。

循环全部步骤，最终将所有电子标签按序列号由小到大的顺序识别出来。但需注意的是，循环全部步骤应从算法的最开始重复，即读写器确定一个电子标签后，将重新发送最大序列号的请求码。

以四个标签同时进入读写器的广播范围为例。标签1的序列号为（11011001），标签2的序列号为（11101101），标签3的序列号为（10111001），标签4的序列号为（10001001）。基本二进制树防碰撞算法识别标签过程如图2所示。

（1）读写器首先会发送一个为最大序列号的请求码（11111111），所有在其广播范围内的标签都会回应此请求码。由曼彻斯特编码可知，上述四个标签序列号的第3位、第5位、第6位、第7位不同，意味着标签识别过程中在上述位置会发生碰撞，由此可得其解码为1XXX1X01。由上述分析可知，标签识别过程中碰撞的最高位为第7位，因此读写器使高于第7位的数值保持不变，第7位的数值设为0，低于第7位的数值全部设置为1，由此可获得新的请求码——10111111。

（2）读写器发送请求码（10111111），电子标签收到请求码后会将自身序列号与请求码（10111111）进行比较，序列号不大于请求码的标签会应答，由此可知标签3和标签4会应答。由曼彻斯特编码可知，这两个标签的序列号会在第3位、第5位、第6位发生碰撞，由此读写器会将碰撞最高位第6位的数值设为0，高于第6位的数值保持不变，而低于第6位的数值则全部设置为1，由此可获得新的请求码——10011111。

（3）读写器发送请求码（10011111），电子标签收到请求码后会将自身序列号与请求码（10011111）进行比较，序列号不大于請求码的标签会进行应答，此次只有标签4应答。读写器将给标签4发送指令使其进入休眠状态，不再响应。然后算法需返回根节点，新的请求码为最大序列号，即11111111。

（4）读写器发送请求码（11111111），所有在其广播范围内的标签都会回应此请求码。收到请求码的标签1、标签2和标签3都会应答。由曼彻斯特编码可知，上述三个标签的序列号会在第3位、第5位、第6位、第7位发生碰撞，由此读写器会将碰撞最高位第7位的数值设为0，高于第7位的数值保持不变，而低于第7位的数值都设为1，由此可获得新的请求码，即10111111。

（5）读写器发送请求码（10111111），电子标签收到请求码后会将自身序列号与请求码（10111111）进行比较，序列号不大于请求码的标签会进行应答，此次只有标签3应答。读写器将给标签3发送指令使其进入休眠状态，不再响应。同时算法需返回根节点，新的请求码为最大序列号，即11111111。

（6）读写器发送请求码（11111111），所有在其广播范围的标签都会回应此请求码。收到请求码的标签1、标签2会进行应答。由曼彻斯特编码可知，上述两个标签的序列号会在第3位、第5位、第6位发生碰撞，由此读写器会将碰撞最高位第6位的数值设为0，高于第6位的则保持不变，低于第6位的数值则全设为1，由此可得到新的请求码，即11011111。

（7）读写器发送请求码（11011111），电子标签收到请求码后会将自身序列号与请求码（11011111）进行比较，此次只有标签1会进行应答。读写器将给标签1发送指令使其进入休眠状态，不再响应。同时算法需返回根节点，新的请求码为最大序列号，即11111111。

（8）读写器发送请求码（11111111），所有在其广播范围内的标签都会回应此请求码。此次只有标签2进行应答。读写器将给标签2发送指令使其进入休眠状态，不再响应。至此所有标签识别完成。

由前文描述的二进制树搜索法的工作流程可知，在无线射频识别系统中发生标签碰撞的情况下，读写器会根据序号位数从高到低不断调整请求码来达到标签识别的目的，且每次标签响应阅读器的请求码时传输的序列号都是完整的。显然，识别所有电子标签所需的次数与无线射频识别系统中存在的电子标签数目成正比关系，同时标签识别所需的时间也与标签数目成正比关系。不妨假设无线射频识别系统中存在N个电子标签，根据算法的特点，需要循环遍历搜索。

2 后退二进制树防碰撞算法

在基本二进制树防碰撞算法中，每次比对查找标签的过程均需对完整的标签序列号进行传输。而现实中无线射频识别标签的ID号较长，且一个成功的搜索算法都须从头搜索，当标签数量增多，便会产生大量无效的检测步骤和冗余数据。因此针对这两个问题，又提出了后退二进制树防碰撞算法。

读写器发送最大序列号的请求码后，所有其广播范围内的标签都将响应请求。当发生碰撞后，序列号中只有碰撞位的信息不可知，需要查验。所以后退二进制防碰撞算法解决了过量无用信息的重复发送与过多侵占资源等问题。

在操作过程中，由于标签都位于二进制数的叶子节点，且基本二进制树防碰撞算法每次成功识别出一个标签后，算法就要返回根节点再开始下一轮查找，这样不仅浪费时间，而且算法的复杂度很高。不同于基本二进制树防碰撞算法，该后退二进制树防碰撞算法每成功识别出一个标签后，就先返回该节点的父节点以查找兄弟节点，以有效减少搜索时间。后退二进制树防碰撞算法步骤如下：

（1）当读写器检测到有电子标签进入其广播范围内时，就会发送一个最大序列号的请求码，命令所有电子标签都将自身完整的序列号返回给读写器。

（2）當多个标签同时给读写器发送序列号时，碰撞在所难免。碰撞发生后，碰撞最高位将被设定为0，高于碰撞位的数值设为1，低于碰撞位的数值不发送，并生成下次搜索序列号命令所需的新请求码。

（3）读写器将新请求码发送给电子标签，电子标签收到后会将自己对应请求码的最高几位序列号与请求码进行比较，序列号不大于请求码的标签会应答，并将自身剩余的序列号位返回读写器。

（4）循环上述过程，最终选出序列号最小的电子标签。发送指令使其进入休眠状态，不再响应。即下一次读写器发送最大序列号请求码时，该电子标签不会回应。返回其父节点重新获取发送序列号命令所需的搜索请求码。

（5）反复执行以上步骤，当发出最大序列号的请求码也无碰撞发生，成功识别出最后一个标签后结束。

继续使用上例所使用的四个标签，运用后退二进制树防碰撞算法识别标签的过程如图3所示。

（1）读写器发送最大序列号请求码（11111111），所有在其广播范围的标签都会回应此请求码。由曼彻斯特编码可知，上述四个标签序列号的第3位、第5位、第6位、第7位不同，意味着标签识别过程中在上述位置会发生碰撞，由此可得其解码为1XXX1X01。由上述分析可知，标签识别过程中碰撞的最高位为第7位，因此读写器会使高于第7位的数值保持不变，第7位的数值设为0，低于第7位的数值不发送，由此可得新的请求码，即10。

（2）读写器发送请求码（10），电子标签收到请求码后会将自身序列号对应请求码的最高两位与请求码（10）进行比较，序列号不大于请求码的标签会进行应答，由此可知标签3和标签4会应答，并返回各自剩余的后6位序列号。由曼彻斯特编码可知，这两个标签后6位序列号会在第3位、第5位、第6位发生碰撞，由此读写器将碰撞最高位第6位的数值设为0，高于第6位的数值保持不变，低于第6位的数值不发送，可获得新请求码，即100。

（3）读写器发送请求码（100），电子标签收到请求码后将自身序列号对应请求码的最高三位与请求码（100）进行比较，序列号不大于请求码的标签会进行应答，此次只有标签4应答。读写器将给标签4发送指令使其进入休眠状态，不再响应。同时算法返回父节点，由此可获得新的请求码，即10。

（4）读写器发送请求码（10），电子标签收到请求码后会将自身序列号对应请求码的最高两位与请求码（10）进行比较，序列号不大于请求码的标签会应答，此次只有标签3应答。读写器给标签3发送指令使其进入休眠状态，不再响应。同时算法返回根节点，新的请求码为最大序列号，即11111111。

（5）读写器发送请求码（11111111），所有在其广播范围内的标签都会回应此请求码。收到请求码的标签1和标签2应答。由曼彻斯特编码可知，上述两个标签的序列号会在第3位、第5位、第6位发生碰撞。由此读写器会将碰撞最高位，即第6位的数值设为0，高于第6位的数值保持不变，低于第6位的数值不发送，由此得到新的请求码，即110。

（6）读写器发送请求码（110），电子标签收到请求码后将自身序列号对应请求码的最高三位与请求码（110）进行比较，序列号不大于请求码的标签会应答，此次只有标签1应答。读写器给标签1发送指令使其进入休眠状态，不再响应。同时算法返回根节点，新的请求码为最大序列号，即11111111。

（7）读写器发送请求码（11111111），所有在其广播范围内的标签都会回应此请求码。此次只有标签2会应答。读写器将给标签2发送指令使其进入休眠状态，不再响应。由此所有标签识别完成。

3 算法分析与实验比较

通常评估无线射频识别标签防碰撞算法的性能，主要从读写器向标签发送请求码的次数和读写器向标签发送请求码的总位数这两方面入手。

本次实验主要针对读写器发送的二进制请求码数据的总数位，对后退二进制树防碰撞算法与基本二进制树防碰撞算法进行比较。由于实际应用中难以存在标准的数据，因此只能选择随机生成的方式来产生防碰撞算法所需的数据。

当同时有20个标签时，基本二进制树防碰撞算法需发送的请求码为2 944位，而后退二进制树防碰撞算法需发送的请求码为1 664位，少于基本二进制树防碰撞算法所发请求码位数的一半。当标签个数持续增多时，两种算法的性能都有所下降。但当标签个数为最大值100时，基本二进制树防碰撞算法需发送的请求码为51 200位，后退二进制树防碰撞算法只需发送请求码30 720位。充分证明后退二进制树防碰撞算法在识别标签时发送的请求码位数更少。发送二进制请求码总位数比较如图4所示。

与基本二进制树防碰撞算法相比，后退二进制树防碰撞算法能够更快地识别出全部标签。但为了保证所有标签都能被准确识别，后退二进制树防碰撞算法也会存在一定数量的冗余请求码，发送的二进制请求码位数明显少于基本二进制树防碰撞算法。且后退二进制树防碰撞算法减少了发送的请求码位数，降低了碰撞位数量的概率，将在一定程度上减少标签的识别时间。

4 结 语

本文主要介绍了两种无线射频识别标签防碰撞算法。首先对产生标签碰撞的原因进行了详细分析，介绍了现在主要使用的标签防碰撞算法，详细描述了基本二进制树防碰撞算法和后退二进制树防碰撞算法的思路和步骤。通过对算法实验的结果进行分析、比较，发现后退二进制树防碰撞算法可以有效避免大量重复的检测步骤，解决无效数据等问题。

参考文献

[1]吴可，张萌，冯菁.无线射频识别防碰撞算法的研究[J].硅谷，2011（10）：102-103.

[2]田晶.基于二进制树的无线射频识别系统开发防碰撞算法研究[J].信息通信，2014（2）：50-51.

[3]杨威.基于无线射频识别系统二进制树防碰撞算法的研究[D]. 武汉：武汉理工大学， 2011.

[4]向垂益.无线射频识别二进制树防碰撞算法的研究与实现[D].长沙：湖南大学， 2009.

[5]游战清，李苏剑，张益强，等.无线射频识别技术（RFID理论与应用）[M].北京：电子工业出版社，2006：3-18.

[6] S Ahuja，P Potti.An introduction to RFID technology（Radio Frequency Identification）[J].Pervasive Computing IEEE，2006，5 （l）：25-35.

[7]梁彪，胡爱群，秦中元.一种新的RFID防碰撞算法设计[J].电子与信息学报，2007，29（9）：21 58-2160.

[8]王晓东，戎蒙恬.基于Q一选择的RFID防碰撞算法的研究[J].计算机仿真，2008，25（6）：124-126.

[9]夏冬雪，杨斌，阳树洪.一种基于射频识別系统的二进制防碰撞算法[J].科协论坛，2008 （6）：53-54.