预估计锁位RFID二进制防碰撞算法

王民　王磊

摘要：随着RFID（射频识别技术）逐渐从概念步入到商业应用阶段，标签碰撞问题影响着数据传输的完整性和正确性，为了解决标签冲突，现有的DBS算法在电子标签向阅读器发送识别码时都存在重复信息的发送，使得系统信道利用率低，同时识别效率降低。为了提高RFID 系统防冲撞算法的有效性，该文研究了一种改进的二进制冲撞比特搜索算法。首先检测冲撞比特的位置信息，通过只传输具体冲撞位信息的方法减少传输的总数据量。采用回退策略以降低阅读器发送请求命令的次数。经过实验验证，该算法有效的减少了搜索次数和时延，提高了系统识别效率。

关键词：RFID；二进制防碰撞；预估计

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）14-3414-04

Abstract： As RFID （radio frequency identification technology） from concept to enter the stage of commercial application，The tags collision problems of the RFID affect the completeness and correctness of data transmission. To solve the problem in a better way， DBS algorithm in electronic tag to the reader sends identification number when there are repeated to send information， makes the system channel utilization rate is low， at the same time identify efficiency reduced， an improved algorithm is proposed on the basis of binary anti-collision algorithm. First detect the location of collision bits， with only the collision position information method to reduce the total number of transmission according to the quantity. The fallback strategy is used to reduce the reader sends the request command. After experimental verification， the algorithm is effective to reduce the search times and delay， improve the efficiency of the system identification.

Key words： RFID； binary anti-collision algorithm； identification

1 概述

无线射频识别技术（RFID—Radio Frequency Identification）[1]是系统通过无线电讯号识别特定目标并读写相关数据。在无线射频识别技术中，读写器和标签都是在开放的环境下通过相同的无线讯号进行信息交互，当两者同时发出讯息交互请求时，必然在信道中发生碰撞。这将会产生两种类型的碰撞：一类即当多个标签通过同一信道向单个读写器发送信息时产生的碰撞，为标签碰撞。另一类是指当一个标签进入多个读写器的识别范围内时发生的碰撞，即读写器碰撞。该文主要研究是的：标签的防碰撞算法。

基于RFID防冲撞算法，世界各国的学者做了大量有意义的研究工作。由于考虑RFID标签，尤其是无源标签的功率限制和功能限制以及系统成本的问题。在RFID系统中，更多地采用了TDMA思想的防碰撞算法【2】。该文研究的是TDMA下二进制树防冲突算法。一般的二进制搜索算法通过识别标签内部信息来区分标签，这样导致整个系统的识别时间都比较长，系统的通信次数偏多。那么我们进一步需要研究的就是如何提高系统的识别效率。该文通过分析动态二进制防碰撞算法，再其基础上提出一种新的算法，进一步缩短了算法的传输时延和阅读次数。

2 二进制防冲突算法的基础

2.1 算法的冲突判断

Manchester 编码原理：利用信号比特中间的跳变来存储信息，当电平从高跳变为低时，我们这时用二进制数“0”表示。而当电平从低跳变到高时，我们用“1”来表示。因此，当一个阅读器收到标签的返回信号后，在数据传输过程中发生“没有变化”的状态，那么阅读器就能够判断这些位一定发生了相互之间的冲突。如图1。

2.2 DBS算法原理

动态二进制搜索算法（DBS）是针对二进制搜索算法传输时延的改进【3，4】。该算法的特点是判断出冲撞位以后，下一次只发送要搜索的序列号最高冲撞位之前的部分。这样就减少了碰撞概率和传输时延。

假设阅读器周围存在若干标签，标签的序列号为n位。下面是算法执行过程：

第一步：阅读器向识别范围内发送这样的请求Request（11111111，8），因为一开始还没检测到冲突位，所以发送完整的请求命令。类似于二进制搜索算法，因为所有的标签都小于请求ID，所以同时都向阅读器发送自身序列号。根据Manchester的编码规则识别到的序列号为1x1x001x，其中x就是没有检测到的比特位。由小到大数最高位的冲突位为第六位，因此阅读器将第六位的比特位拉低为“0”。这样就得到下回阅读器应该发出的请求命令Request（10，2）。endprint

第二步：阅读器向识别范围内发送这样的请求Request（10，2），这时候标签ID中8位比特位的最高两位为“10”的标签应答阅读器的请求命令，因为有三个标签的最高两位都为“10”，他们分别是Tag A，Tag B以及Tag C。这几个标签向阅读器发送他们的低六位信息，因为阅读器已经知道高两位信息。而Tag D因为高两位不符合要求，所以不予响应。对于响应的三个标签他们后六位的读出的ID序列为1x001x，将最高冲突位拉低，与之前的高两位结合组成阅读器新的请求命令即Request（1010，4）。

第三步：阅读器向识别范围内发送这样的请求Request（1010，4），高四位为“1010”比特位的标签做出应答，发现只有Tag B向阅读器发送自身的信息，因为只要一个标签，这样阅读器成功读出Tag B的信息。向Tag B发送去选择命令，以后Tag B不在响应阅读器。

第四步：阅读器再次向识别范围内发送这样的请求Request（11111111，8），依次按照工作原理执行一，二，三四步。直到所有标签都进入去选择状态，即所有标签的信息都被阅读器读取。

2.3 DBS算法实现

假设有以下四张电子标签，其识别ID 为8 位，Tag A：10110010，Tag B：10100011，Tag C：10110011，Tag D：11100011。应用DBS算法举例说明具体的识别过程。步骤如下：

1）阅读器发送参数为11111111的请求命令。应答结果为1x1x001x。

2） 阅读器发送参数为10的请求命令。应答结果为101x001x；阅读器继续发送参数为1010的命令，应答结果为10100011。成功识别标签2，标签2进入休眠。

3） 重复第一步，应答结果为1011001x。继续发送参数为10110010的请求命令，应答结果为10110010。成功识别标签1，标签1进入休眠。

4） 重复第一步，应答结果为10110011。标签3被识别，成功识别所有标签3，标签3进入休眠。

5） 阅读器发送参数为11的请求命令。应答结果为11100011。成功识别标签4，标签4进入休眠。

由DBS算法可以看出：

1）阅读器每次发送请求命令都包含已知位信息，这样反复传送增加了传送时延。

2） 采用遍寻树的方法发送请求指令，这样寻呼次数不是最优。

针对以上DBS算法的缺点，提出了一下改进型的二进制搜索算法。

3 改进的二进制搜索算法

3.1 算法的原理及指令

新的改进型二进制算搜索算法，在阅读器判断出数据发生碰撞的准确比特位后，对碰撞位进行锁位，以后的寻呼命令发送对应碰撞位，这样有效地缩短了传输比特位。为了更快的识别标签，对碰撞位的所有可能情况进行预估计，阅读器根据碰撞位预估值发送请求序列号可以减少阅读器与标签的识别次数。对于新的算法我们规定一下指令：

LCID （锁定的冲突位序列号）：阅读器利用同样利用曼彻斯特编码方式识别出序列号发生碰撞的位置，并将几个碰撞的比特拉高位置 “1”，未发生碰撞的位置拉低并去除未发生碰撞的比特位，将碰撞位置组成新序列号作为参数。

REQUEST（LCID）—请求（序列号）：阅读器发送比特位全部拉高的ID作为参数向标签发送请求命令。磁场范围内的标签将接受ID与本身被赋予的ID相比较，若小于等于自身则向阅读器发出响应，不然则继续等待阅读器命令。

SELECT（LCID）—选择（序列号）：用提前预估计出来的碰撞位可能的序列号作为新的阅读器请求序列发送给电子标签。

READ-DATA（ID）—识别标签信息：该电子标签响应阅读器，将自身信息发送给阅读器，从而成功识别该标签。

UNSELECT（ID）—去选择：该命令是阅读器向识别范围内的所有标签发送一个参数ID，若标签有标签应答，并且标签返回的ID于阅读器发出的ID相等，则对该标签进行去选择，即不再应答阅读器响应，重新激活该标签只能通过掉电再加电或者移出阅读器识别范围再进入的方法。

3.2 算法的主要步骤

1） 读写器发送REQUEST命令，参数为 11…1（n个1），这时阅读器识别范围内的所有标签都将应答。若没有标签，继续发送REQUEST命令；若只有一个标签，则读出该标签后阅读器发出UNSELECT，继续发送REQUEST命令。

2） 若不止一个标签，那么标签在向阅读器传输序列号时会发生冲突，读写器利用冲突的判断方法识别出冲突发生的序列号位置。利用LCID组成新的寻呼序列。

3） 预估计新序列号，序列号不含0，第0位为0，第1位以为0，第2位为0。根据冲突位情况依次置位“0”；置位完后依次发送请求命令。

4）重复1）， 2）， 3）步骤。直到所有标签被识别。

5） 置新的寻呼序列的最高位为“0”，单独发送。锁位位中最高位为“0”的标签将自己锁定位中剩下的几位发送给阅读器，阅读器判读是否有碰撞。若无，成功识别标签；若有，则将碰撞位锁位，置新的锁定位最高位为“0”，新的锁位位中最高位为“0”的标签将自己锁定位中剩下的几位发送给阅读器，阅读器判断碰撞。依次类推，每次若有标签被识别，采取回退策略，返回上一次发生碰撞的节点，识别此节点为“1”的分枝，这样不断重复，直至所有标签被识别。

3.2算法的具体实现

假设如上面所说的4个标签存在于阅读器周围，算法的主要实现步骤：

1）REQUEST（11111111），所有标签对阅读器进行应答。阅读器得到1x1x001x。利用LCID组成新序列为111。endprint

2）预估计冲突位的序列号（111，110，101，011）依次发送。标签3，标签4被识别，进入休眠。

3）发送REQUEST（11111111）。所有标签对阅读器进行应答。阅读器得到101x001x，用LCID组成新序列为11。

4）预估计序列号冲突位（11，01，10），标签与自身相应位进行比较。依次发送，标签1，标签2.被识别。至此所有标签被识别。

以上的例子只用了前四步，但是若第一次预估计发送后并没有标签响应，那么算法将进入死循环。因此必须存在第5步，。例如存在以下5个标签：A（01010111），B（01101101），C（01011100），D（01110100），E（01010110）。检测这五个标签必须使用第五步。流程如图3所示。

4 两种算法的性能比较

对RFID 系统来说有两个很重要的因素用来评价系能性能的优略，一个是阅读器在识别所有标签时发送请求命令的次数，另一个是阅读器发送请求命令时的传输比特位数。这是决定阅读器识别效率的两个重要参数。

假设阅读器作用范围内的标签数量为n，标签编码长度为l，总的搜索次数满足公式（1），传输的数据长度总和满足公式（2）。

对于两种算法我们选择实物进行验证，然后采用数学建模进行matlab仿真：

实验选定Philips 公司的Mifare S50 射频卡，其UID 编号为96 位，其中前48 位是卡的序列号，中间32 位是卡的类型号最后16 位为结束符。每张卡的48位的序列号中只有后位是唯一有效的。为了方便分析和仿真，以下假32设射频卡的有效编码长度为8 位。以下是DBS算法与改进算法matlab仿真比较图。

随着标签数量N 的增加，两种算法的仿真结果如图4和图5所示。可以看出改进的算法的传输时延和搜索次数均比DBS他算法少。同时从时间复杂度的角度分析：当阅读器周围存在有限个数量的标签时，随着标签数量的增加，各算法的时间复杂度不同。改进的新的二进制算法的复杂度是比DBS算法的时间复杂度的高阶无穷小，表明该算法最优。

5 结束语

研究比较动态二进制搜索算法与新改进的二进制搜索算法。系统的通信时间，新的改进算法只发送冲突位信息，从而减少了传输码元长度，降低了传输时间。而阅读器采用预估计冲突位则在标签冲突数量多的情况下显著减少了阅读器的寻呼次数，也是提高了阅读器的通信效率。当然对于寻呼次数的研究本算法在标签冲突少的时候并不是很突出，有待进一步学习和改进。相信随着RFID的广泛应用，未来会有更多更好的算法用来解决这一问题。

参考文献：

[1] K. Finkenzeller.RFID Handbook： Fundamentals and Applications in Contactless Smart Cards and Identification.3rd ed [M].John Wiley and Sons Ltd，2010：75-91.

[2] Jianguo Hu，Ke Lin，Deming Wang，Yanyu Ding and Hong Zhou Tan.A Novel Anti-Collision Algorithm for RFID System[C].Program for the IEEE International Conference on RFID Technology and Applications， Guangzhou，China：2010：17–19.

[3] 向垂益，何怡刚，李兵，等.动态二进制树搜索算法的改进[J].计算机工程，2010，36（2）：260–265.

[4] 王春鹏.RFID 标签防冲撞算法研究[D].成都：西南交通大学优秀硕士学位论文，2009.

[5] 单承贛.射频识别原理与应用[M].北京：电子工业出版社，2008：78-142.endprint

2）预估计冲突位的序列号（111，110，101，011）依次发送。标签3，标签4被识别，进入休眠。

3）发送REQUEST（11111111）。所有标签对阅读器进行应答。阅读器得到101x001x，用LCID组成新序列为11。

4）预估计序列号冲突位（11，01，10），标签与自身相应位进行比较。依次发送，标签1，标签2.被识别。至此所有标签被识别。

以上的例子只用了前四步，但是若第一次预估计发送后并没有标签响应，那么算法将进入死循环。因此必须存在第5步，。例如存在以下5个标签：A（01010111），B（01101101），C（01011100），D（01110100），E（01010110）。检测这五个标签必须使用第五步。流程如图3所示。

4 两种算法的性能比较

对RFID 系统来说有两个很重要的因素用来评价系能性能的优略，一个是阅读器在识别所有标签时发送请求命令的次数，另一个是阅读器发送请求命令时的传输比特位数。这是决定阅读器识别效率的两个重要参数。

假设阅读器作用范围内的标签数量为n，标签编码长度为l，总的搜索次数满足公式（1），传输的数据长度总和满足公式（2）。

对于两种算法我们选择实物进行验证，然后采用数学建模进行matlab仿真：

实验选定Philips 公司的Mifare S50 射频卡，其UID 编号为96 位，其中前48 位是卡的序列号，中间32 位是卡的类型号最后16 位为结束符。每张卡的48位的序列号中只有后位是唯一有效的。为了方便分析和仿真，以下假32设射频卡的有效编码长度为8 位。以下是DBS算法与改进算法matlab仿真比较图。

随着标签数量N 的增加，两种算法的仿真结果如图4和图5所示。可以看出改进的算法的传输时延和搜索次数均比DBS他算法少。同时从时间复杂度的角度分析：当阅读器周围存在有限个数量的标签时，随着标签数量的增加，各算法的时间复杂度不同。改进的新的二进制算法的复杂度是比DBS算法的时间复杂度的高阶无穷小，表明该算法最优。

5 结束语

研究比较动态二进制搜索算法与新改进的二进制搜索算法。系统的通信时间，新的改进算法只发送冲突位信息，从而减少了传输码元长度，降低了传输时间。而阅读器采用预估计冲突位则在标签冲突数量多的情况下显著减少了阅读器的寻呼次数，也是提高了阅读器的通信效率。当然对于寻呼次数的研究本算法在标签冲突少的时候并不是很突出，有待进一步学习和改进。相信随着RFID的广泛应用，未来会有更多更好的算法用来解决这一问题。

参考文献：

[1] K. Finkenzeller.RFID Handbook： Fundamentals and Applications in Contactless Smart Cards and Identification.3rd ed [M].John Wiley and Sons Ltd，2010：75-91.

[2] Jianguo Hu，Ke Lin，Deming Wang，Yanyu Ding and Hong Zhou Tan.A Novel Anti-Collision Algorithm for RFID System[C].Program for the IEEE International Conference on RFID Technology and Applications， Guangzhou，China：2010：17–19.

[3] 向垂益，何怡刚，李兵，等.动态二进制树搜索算法的改进[J].计算机工程，2010，36（2）：260–265.

[4] 王春鹏.RFID 标签防冲撞算法研究[D].成都：西南交通大学优秀硕士学位论文，2009.

[5] 单承贛.射频识别原理与应用[M].北京：电子工业出版社，2008：78-142.endprint

2）预估计冲突位的序列号（111，110，101，011）依次发送。标签3，标签4被识别，进入休眠。

3）发送REQUEST（11111111）。所有标签对阅读器进行应答。阅读器得到101x001x，用LCID组成新序列为11。

4）预估计序列号冲突位（11，01，10），标签与自身相应位进行比较。依次发送，标签1，标签2.被识别。至此所有标签被识别。

以上的例子只用了前四步，但是若第一次预估计发送后并没有标签响应，那么算法将进入死循环。因此必须存在第5步，。例如存在以下5个标签：A（01010111），B（01101101），C（01011100），D（01110100），E（01010110）。检测这五个标签必须使用第五步。流程如图3所示。

4 两种算法的性能比较

对RFID 系统来说有两个很重要的因素用来评价系能性能的优略，一个是阅读器在识别所有标签时发送请求命令的次数，另一个是阅读器发送请求命令时的传输比特位数。这是决定阅读器识别效率的两个重要参数。

假设阅读器作用范围内的标签数量为n，标签编码长度为l，总的搜索次数满足公式（1），传输的数据长度总和满足公式（2）。

对于两种算法我们选择实物进行验证，然后采用数学建模进行matlab仿真：

实验选定Philips 公司的Mifare S50 射频卡，其UID 编号为96 位，其中前48 位是卡的序列号，中间32 位是卡的类型号最后16 位为结束符。每张卡的48位的序列号中只有后位是唯一有效的。为了方便分析和仿真，以下假32设射频卡的有效编码长度为8 位。以下是DBS算法与改进算法matlab仿真比较图。

随着标签数量N 的增加，两种算法的仿真结果如图4和图5所示。可以看出改进的算法的传输时延和搜索次数均比DBS他算法少。同时从时间复杂度的角度分析：当阅读器周围存在有限个数量的标签时，随着标签数量的增加，各算法的时间复杂度不同。改进的新的二进制算法的复杂度是比DBS算法的时间复杂度的高阶无穷小，表明该算法最优。

5 结束语

研究比较动态二进制搜索算法与新改进的二进制搜索算法。系统的通信时间，新的改进算法只发送冲突位信息，从而减少了传输码元长度，降低了传输时间。而阅读器采用预估计冲突位则在标签冲突数量多的情况下显著减少了阅读器的寻呼次数，也是提高了阅读器的通信效率。当然对于寻呼次数的研究本算法在标签冲突少的时候并不是很突出，有待进一步学习和改进。相信随着RFID的广泛应用，未来会有更多更好的算法用来解决这一问题。

参考文献：

[1] K. Finkenzeller.RFID Handbook： Fundamentals and Applications in Contactless Smart Cards and Identification.3rd ed [M].John Wiley and Sons Ltd，2010：75-91.

[2] Jianguo Hu，Ke Lin，Deming Wang，Yanyu Ding and Hong Zhou Tan.A Novel Anti-Collision Algorithm for RFID System[C].Program for the IEEE International Conference on RFID Technology and Applications， Guangzhou，China：2010：17–19.

[3] 向垂益，何怡刚，李兵，等.动态二进制树搜索算法的改进[J].计算机工程，2010，36（2）：260–265.

[4] 王春鹏.RFID 标签防冲撞算法研究[D].成都：西南交通大学优秀硕士学位论文，2009.

[5] 单承贛.射频识别原理与应用[M].北京：电子工业出版社，2008：78-142.endprint