RFID技术中防碰撞算法的改进

郑晓彦 王玉庆

（郑州信息科技职业学院，河南 郑州 450046）

RFID技术中防碰撞算法的改进

郑晓彦 王玉庆

（郑州信息科技职业学院，河南 郑州 450046）

在射频识别系统中，如果多个电子标签同时出现在读写器的作用范围内，就会出现多个电子标签在数据上的碰撞问题，如果标签的碰撞位过多，用二进制搜索防碰撞算法处理起来就会显得繁琐，本文提出了一种基于二进制搜索算法的改进算法，原理是当碰撞位数过多时，就将碰撞位每两个来处理，通过设置它们的比特位来发送查询命令，理论和仿真软件证明了该算法比二进制搜索算法和动态算法更具优势。

射频识别；碰撞；二进制搜索算法

射频识别技术是一种非接触的自动识别技术，主要是由电子标签和读写器组成，通过无线传输技术对电子标签内部的数据进行读取或修改操作，当在读写器的作用范围内存在多个电子标签时，所有的电子标签就会同一时间将标签内部数据发送给读写器，在传输的过程中就会造成数据间的相互干扰，即碰撞。这样读写器就不能正常的读取出电子标签的内部数据，从而影响射频识别系统的正常工作。这也就是多路存取问题，因此，保证射频识别系统的正常运行的首要工作就是解决好电子标签的碰撞问题。而解决电子标签碰撞问题的方法就是设计出行之有效的防碰撞算法。

现有的射频识别系统的防碰撞算法都是基于TDMA[1]的，并且可以划分为基于二进制树搜索（Binary search，BS）算法和Aloha防碰撞算法。Aloha算法的特点是：算法比较简单，容易实现，成本低。但该算法的时隙是随机分配的，当有大量电子标签并存的时候，帧冲突严重，存在“tag starvation”问题[2-3]。而基于二进制搜索（BS）算法虽然识别率高，但是相应的算法复杂，识别需要较长的时间[4]，本文是基于二进制搜索算法提出了一种改进的防碰撞算法。

1 两种典型的二进制防碰撞算法

1.1 二进制搜索算法

能够在读写器中准确辨认出发生碰撞的比特位是实现二进制搜索算法的前提条件，因此必须选择适合的编码，曼彻斯特编码能够按位识别出碰撞位，这样就可以根据发生碰撞的位置，读写器就可以按一定的规则重新发出读取命令来搜索电子标签，因此曼彻斯特编码的使用是实现二进制搜索防碰撞算法的必要前提。它的工作流程如下：

1.1.1 电子标签进入到读写器的信号范围下，读写器便会向电子标签发送REQUEST（≤11111111）的命令，所有满足该条件的电子标签都会发生响应，并向读写器发送自己的EPC号。

1.1.2 读写器对比所有电子标签相同位置上的二进制数，如果发现有不一致的情况，就可以判定出该位置上发生碰撞。

1.1.3 当确定发生碰撞时，就将发生碰撞的最高比特位上的二进制数置为0，发生碰撞最高比特位之前的数保持不变，之后的数均置为1，并将此二进制数作为下次的REQUEST命令，从而逐步排除序列号较大的电子标签，直至发送的命令与电子标签所响应的序列号完全一致时，就说明了再无碰撞发生，使用选择命令（SELECT）选出这个唯一的标签。

1.1.4 选出唯一的标签以后，使用（UNSELECT）命令，使这个点子标签进入到“无声”状态，不再对读写器发出的命令进行相应，当该标签移出读写器的作用范围以外再进入时，可重新发生响应，进行复位操作可以重新激活该电子标签

1.1.5 重复上述的4个步骤，直至完成对所有电子标签数据的读取操作

1.2 动态二进制搜索算法

在二进制搜索算法中，从读写器和单个电子标签进行数据转换的过程中可以看出：读写器发出请求命令中，把最高碰撞位之后的比特位都置为1，这对于标签的识别不能提供任何信息，而标签返回过来的数据，最高碰撞位和最高碰撞位之前的比特位也不包含任何补充的信息，属于重复多余的信息，正因为如此，人们提出了动态二进制算法[5]，当读写器检测到有碰撞发生的时候，下一次读写器在请求命令中只发送搜索序列号中的最高位与最高碰撞位之间的二进制数位搜索的依据，然后中断传输，所有与最高位和最高碰撞位之间二进制数相同的电子标签发生响应，并将剩余的序列号传输给读写器。这样就避免了序列号中多余二进制数的传输，这样就能缩短识别的时间，动态二进制数相对于二进制搜索算法来说，在传输数据量和传输时间上可以减少达50%。时间上可以减少达50%。

2 改进的二进制算法

2.1 算法的原理

通过分析二进制搜索算法的缺点，本文提出了一种改进的二进制算法，算法约定如下：其一，电子标签序列号上的比特值不是“0”就是“1”，因此如果读写器检测出电子标签的碰撞为只有一位的情况下，不用发出读写命令就直接可以将2个电子标签识别出来。其二，当读写器检测出电子标签中有N个碰撞位的话，说明除了这N个碰撞为是未知的，在其余比特位上的二进制数都是已知的，所以只需要针对这N个碰撞为发送适当的请求命令就可以将电子标签识别出来，这样就极大地减少了二进制搜索算法中的重复检测过程，从而减少识别所用消耗的时间。

为了便于描述该改进算法，给出以下的防碰撞命令。

2.1.1 该算法主要是对碰撞位进行0，1的二进制数赋值，与碰撞位上的二进制数具有相同序列号的电子标签将被识别出来，如果碰撞位数过多，赋值的过程也比较麻烦，因此采用每两位碰撞位进行赋值的方法，查询命令REQUEST（Dx1，Mx；Dx2，Mx1），REQUEST（Dx3，Mx3；Dx4，Mx4），参数Dx1为检测到的最高碰撞位，Dx2为碰撞次高位，Dx3为碰撞位的第三高位，Dx4为碰撞为的第四高位，例如检测1？？1？？0？，那么读写器首先发送request（D6，0；D5，0），符合条件的电子标签进行相应，然后响应的标签进入到待命的状态，然后在发送request（D4，0；D3，0）命令，从待命状态下的电子标签选出符合条件的电子标签，完成数据读取后，将读取过的电子标签进入“无声”状态，即非激活状态。同理读写器依次发送（D4，0；D3，1）（D4，1；D3，0），（D4，1；D3，1）命令将处于相应待命状态的电子标签全部识别出来，并将其进入非激活状态，然后再发送request（D6，0；D5，1）命令，重复上述过程直至将电子标签全部识别出来。

2.1.2 退出选择命令unselect：取消事先选中的电子标签，使标签进入到“无声”的状态，即非激活状态，对于读写器所下达的任何命令都不予以响应。如果想要重新激活标签，需要先移除读写器的范围，并再次进入到读写器的范围。下面以8个具体的电子标签为例，电子标签的编码为8位，它们的编码分别如下：标签1：00001000，标签2：01010100，标签3：10011010，标签4：11000000，标 签 5：01000010，标 签 6：01010000，标 签 7：01001010，标签8：01011000.

具体过程如下：

第一，发送request≤11111111命令，处在读写器范围内的所有电子标签均发生相应，并向读写器发送各自的序列号，读写器检测出的结果为：？？0？？？？0碰撞位为D7，D6，D4，D3，D2，D1。最高碰撞位是D7，次高碰撞位为D6，第三高碰撞位为D4，第四高碰撞位为D3。因此下次发送的查询命令为（D7，0；D6，0）。

第二，读写器发送查询命令（D7，0；D6，0），标签通过比较自己相应位上的二进制数，与之相同的电子标签将内部的信息发送给读写器，通过比较得发生相应的只有标签1，这样标签1就被顺利识别出。

第三，读写器发送unselect命令使标签1进入到“无声”状态。

第四，读写器发送查询命令requset（D7，0；D6，1），发生响应的电子标签为：标签2，标签5，标签6，标签7，标签8，然后将这些响应的标签进入到待命状态。

第五，读写器发送命令request（D4，0；D3，0），碰撞位上二进制数与之相同的电子标签为标签5，因此读写器从这些待命的电子标签中识别出标签5。

第六，读写器发送unselect命令，标签5进入到“无声”状态。

第七，读写器发送命令request（D4，0；D3，1），碰撞位上二进制数与之相同的电子标签是标签7，因此读写器从这些待命的电子标签中识别出标签7。

第8，读写器发送unselect命令，标签7进入到“无声”状态。

其9，读写器发送命令request（D4，1；D3，0），碰撞位上二进制数与之相同的电子标签为标签2和标签6。处于待命中的标签2和标签6发生响应，读写器检测出这两个电子标签只有一个碰撞位，因此可以直接识别出待命状态的标签2和标签6。

第10，读写器发送unselect命令，标签2和标签6进入到“无声”状态。

第十一，读写器发送命令request（D4，1；D3，1），碰撞位上二进制数与之相同的电子标签为标签8，因此读写器识别出待命状态中的标签8。

第十二，读写器发送unselect命令，标签8进入到“无声”状态。

第十三，此时读写器已经处于待命状态的电子标签全部识别完。读写器再次发送命令request（D7，1；D6，0），碰撞位上二进制数与之相同的电子标签为标签3，因此读写器识别出标签3。

第十四，读写器发送unselect命令，标签3竟如到“无声”状态。

第十五，读写器发送命令request（D7，1；D6，1），碰撞位上二进制数与之相同的电子标签是标签4，因此读写器识别出标签4。至此，处于读写器范围内的电子标签全部被正确识别出来。

2.2 算法性能的比较

设在读写器作用范围内的电子标签数有N个，防碰撞算法完成所有电子标签识别所需要的搜寻命令次数为S（N），那么基于二进制搜索防碰撞算法的搜寻次数：

动态二进制搜索算法的搜寻次数：

而对于改进后的防碰撞算法来说，当有N电子标签在读写器的作用范围下，而发生碰撞的次数为n（N=2n），则当有两个电子标签探测到发生碰撞的位数只有1位的碰撞的时候，查询次数：

当有4个电子标签，发生的碰撞有2位的时候，查询次数为：

根据数学归纳法可知当有N电子标签在读写器的作用范围下，而发生碰撞的次数为n（N=2n），总的查询次数为：

根据MATLAB仿真结果如图1：可以看出改进后的防碰撞算法比之传统的算法具有两个明显的优势：一是搜寻的次数大大减少，从而减少读写器识别标签的时间。二是传输的数据量减少，相应的识别时间也大大减小，从而提高识别的效率。

图1 查询次数的比较

3 结语

本文主要是对传统的二进制算法进行了分析和研究，并在此基础上提出了一种基于二进制算法的改进算法。该算法能够大大减少搜寻次数和传输的数据量，也体现出了该算法的优越性。

[1]夏志国，何怡刚，侯周国.一种二进制树位检测的标签防碰撞算法[J].计算机工程与应用，2010，46（20）：245-248.

Xia ZG，He Y G，Hou Z G.A binary tree tag anti-collision algorithm for detecting [J]. Computer Engineering and Applications，2010，46（20）：245-248.

[2]Harald Vogt．Efficient object identification with Passive RFID tags，in：Proceedings International Conference on Pervasive Computing，April，2002：98-113.

[3]Harald Vogt.Multiple object identification with Passive RFID tags，in：Proceedings of IEEE International Conference on Systems，Manand Cybernetics，vol.3，Hammamet，Tunisia，October，2002：114-124.

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

Ju W C，Yu C F.A dynamic binary anti-collision algorithm based on RFID [J]，Journal of Fudan University（Natural Science），2005，44（1）：46-50.

[5]余松森，詹宜巨.基于修剪枝的二进制树形搜索反碰撞算法与实现[J].计算机工程，200，31（16）：217-218.

Yu S S，Zhan Y J.Pruning branches based on a binary search tree anti-collision algorithm and implementation[J]. Computer Engineering，200，31（16）：217-218.

TP301

A

1671-0037（2014）08-81-2.5

郑晓彦（1986-），女，硕士研究生，助教，研究方向：电子电器技术。