射频识别（RFID）技术是一种非接触式的自动识别技术，通常由读写器、电子标签和计算机数据管理系统三部分组成[1],通过DSRC短程通信技术进行数据传输和交换。RFID系统工作时，如果遇到两个以上电子标签都在读写器信号的覆盖范围内，则各个电子标签会同时对读写器发出信号，从而造成各电子标签间数据的碰撞，使读写器不能正常读取各个电子标签内的有关数据，这就是RFID系统中的多路存取问题。因此只有解决好电子标签的碰撞问题，才能使RFID系统正常工作，而解决电子标签防碰撞问题的关键是优化的防碰撞算法。

    现有的RFID防碰撞算法都是基于TDMA算法,可划分为Aloha防碰撞算法和基于二进制搜索BS（Binary search）算法两大类[2-3]。Aloha是一种随机接入算法，这种算法多采取“标签先发言”的方式，即标签一旦进入阅读器的阅读区域就自动向阅读器发送其自身的ID,随即标签和阅读器间开始通信。在标签发送数据的过程中，若有其他标签也在发送数据，将发生信号重叠从而导致完全冲突或部分冲突，阅读器检测接收到的信号来判断有无冲突。如果发生冲突，阅读器将发送命令让标签停止发送，随机等待一段时间后再重新发起查询。该算法特点是：算法简单、便于实现，适用于低成本RFID系统。但是由于该算法的时隙是随机分配的，当大量标签并存时，帧冲突严重[4]。而基于BS算法是通过多次比较，不断筛选出不同的标签号，时分复用地进行读写器和射频卡之间的信号交换，以一个独特的序列号识别射频卡为基础。为了从一组射频卡中选出其中的一个，读写器需要发出一个请求命令，有意识地将射频卡序列号传输时的数据碰撞引导到读写器上，即让读写器来判断是否发生碰撞。如发生碰撞，则缩小范围进行进一步搜索。这类算法虽然识别效率高， 但是算法比较复杂， 识别时间较长[5-6]。本文在二进制防碰撞算法的基础上提出一种改进的防碰撞算法。
1 两种典型的二进制防碰撞算法的分析
1.1 二进制搜索算法
    实现BS算法系统的必要前提是能够辨认出在读写器中数据冲突位的准确位置，因此必须选用合适的编码。曼彻斯特编码能够按位识别出碰撞位，这样可以根据碰撞的位置，按一定的规则重新搜索标签。因此，使用曼彻斯特编码是实现二进制搜索防碰撞算法的必要前提[7-8]。BS算法的工作流程如下：
    （1）电子标签进入读写器的作用范围时，读写器发送命令REQUEST（≤11111111），所有满足此条件的电子标签响应此命令，并将自己的EPC号传给读写器。
   （2）读写器对比电子标签响应的EPC码相同位数上的数，根据Manchester编码规则，若出现不一致现象，即可判断出该比特位有碰撞。
   （3）当确定有碰撞后，将此次发生碰撞的最高位置“0”，最高碰撞位之前的比特位不变，最高碰撞位后的所有比特位都置“1”，并产生新的请求命令REQUEST，依次排除序列号大的标签，直到读写器对比电子标签响应的序列号中相同位数上的数完全一致时，则说明无碰撞。此时，使用选择命令(SELECT)选出一个唯一的标签。
    （4）选出唯一的标签后，使用READ-DATA命令完成读写器与该电子标签的数据交换。并使用选择命令(UNSELECT)进入“无声”状态，此时在读写器范围内不再响应(重新进入读写器范围可再次响应)。为了重新激活电子标签，必须进行复位操作。
    （5）重复前4个步骤，并选择剩余的电子标签数据交换。多次循环后即可完成所有电子标签的读取。
1.2 动态二进制搜索算法(DBS)
    在BS搜索算法中，从读写器和单个电子标签的数据流可以看出，读写器发出的请求命令中，最高碰撞位后的所有比特位都被置“1”，对标签的识别不能提供任何的信息。而标签返回的数据中，最高碰撞位以前的比特位及最高碰撞位不包含给读写器的补充信息，因为这些位是已知且给定的，属于多余的重复信息。基于此人们提出了动态二进制搜索算法(DBS)[9]，当读写器检测到碰撞后，下一次读写器在请求命令中只发送搜索序列号中的最高位和最高碰撞位之间的部分作为搜索依据，然后中断传输，所有在与最高位和最高碰撞位之间的部分相同的电子标签响应并送回它们序列号的剩余各位，即最高碰撞位之后的比特位作为应答。因此，DBS算法避免了序列号中多余部分的传输，数据传输时间明显缩短。DBS算法较BS算法在传输数据量和所需时间上可减少50%[10]。
2 改进的二进制搜索算法
2.1算法约定
    鉴于BS算法的缺点，本文提出了一种改进的二进制搜索算法，算法约定如下：
    （1）采用曼彻斯特编码的电子标签序列号每个比特位上的取值不是“0”就是“1”。因此，如果当读写器探测到仅有一位碰撞位时，读写器不需要发送请求命令,可以直接识别出2个标签。
     （2）读写器如果检测到有N个碰撞位，则说明这N个碰撞位的比特位对读写器来说是未知的,而其他的比特位对读写器来说是已知的。因此读写器只需要对未知的碰撞位处理，而不需要传输那些已知的比特位，从而减少传输时延。
    为了便于描述以及实现该算法,给出如下防碰撞命令：
     ①查询命令request(DX,MX;DX1,MX1)。参数DX、DX1分别为检测到碰撞位的最高位和次高位，参数MX、MX1为0、1的二维排列组合，例如检测到1?1?00?1，那么读写器发送request（D6,0;D4,0）符合条件的标签响应并返回冲突位及相关信息。
     ②退出选择命令unselect。取消事先选中的电子标签，使标签进入“无声”状态。在这种状态下标签完全是非激活的，对收到的request命令不做应答。为了重新激活标签，必须暂时离开读写器的作用范围，然后再次进入该读写器范围。
2.2 算法原理
　 下面以读写器作用范围内的8个编码为8 bit的标签为例说明该算法，8个标签的编码如下：tag1:01001000，tag2:01010100，tag3：01011010，tag4:01000000，tag5:01000010，
tag6：01010000，tag7:01001010，tag8:01011000。
    （1）request≤11111111命令，读写器作用范围内的所有标签应答，读写器译码的结果为010????0碰撞位为D4,D3,D2,D1,最高碰撞位为D4，次高碰撞位为D3，因此下次查询命令为request（D4,0;D3,0）。
    （2）读写器发送查询命令request（D4,0;D3,0）,标签通过比较各自的D4、D3位，与之相同的标签则发送自己的相关信息给读写器。通过比较后标签4和标签5响应，编码后得到010000?0，读写器检测到仅只有一位碰撞，可以直接识别出标签4和标签5。读写器正确识别它们之后，执行unselect命令，使标签4和标签5处于“无声”状态。
    （3）读写器发送查询命令request（D4,0;D3,1）,标签1和标签7响应，编码后得到010010?0，读写器检测到仅只有一位碰撞，可以直接识别出标签1和标签7。读写器正确识别它们之后，执行unselect命令，使标签1和标签7处于“无声”状态。
    （4）读写器发送查询命令request（D4,1;D3,0）,标签2和标签6响应，编码后得到01010?00，读写器检测到仅只有一位碰撞，可以直接识别出标签2和标签6。读写器正确识别它们之后，执行unselect命令，使标签1和标签7处于“无声”状态。
    （5）读写器发送查询命令request（D4,1;D3,1）,标签3和标签8响应，编码后得到010110?0，读写器检测到仅只有一位碰撞，可以直接识别出标签3和标签8。读写器正确识别它们之后，执行unselect命令，使标签1和标签7处于“无声”状态。至此，读写器作用范围内的所有标签都别正确识别完毕。算法流程如图1所示。
3 算法性能比较
    假设读写器作用范围内有N个电子标签，则BS算法完成所有标签识别的搜索命令次数S(N)为:
    
    系统的吞吐率η1为:
    

    对三种算法采用Matlab软件进行仿真， 其结果如图2所示。

    通过理论和仿真比较可见，采用改进后的二进制搜索算法较其他两个算法有三个方面的优势：其一减少了查询标签次数，使计算时间减小；其二减少了系统数据传输量，提高了标签的识别速率；其三较大地提高了系统的吞吐率。
    本文对BS算法及DBS算法过程进行了分析，找出了其中的不足之处，在此基础上提出了一种改进的二进制搜索算法，并通过Matlab仿真得到该算法的查询次数和吞吐率方面的数据。通过实验数据表明，该改进算法可以减少系统的查询次数，提高系统的吞吐率。从而验证了该改进算法的优越性。
参考文献
[1] 李晓东．射频识别技术中的隐私安全问题及策略[J]．微电子学与计算机，2005，22(9)：137-140．
[2] FINKENZELLER K． RFID Handbook：Fundamentals and  applications in contactless smart cards and identification[M]．New York：John Wiley and Sons，2003．
[3] 廖传书，付泰．射频识别系统的防碰撞算法研究[J]．国外电子元器件，2008，16(9)：6-8．
[4] LEE S R，JOO S D，LEE C W．An enhanced dynamic  framed slotted ALOHA algorithm for RFID tag identification[C]. The Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems，2005．
[5] 莫磊．RFID位屏蔽二进制搜索防碰撞算法研究[J]．河北科技大学学报，2010，31(5)：458-462．
[6] TSAN P W．Enhanced binary search with cut through operation for anti-collision in RFID systems[J]．Communications Letter IEEE，2005,10(4):236-238．
[7] 余松森，詹宜巨,彭卫东，等．基于返回式索引的二进制树形搜索反碰撞算法及其实现[J]． 计算机工程与应用, 2004,40(16)：26-28．
[8] 姜丽芬，卢桂章，辛运帷，等．射频识别系统中防碰撞算法研究[J]．计算机工程与应用，2007，43(5)：29-32．
[9] 王忠勇，高向川．基于回溯的RFID防碰撞算法[J]．微计算机信息，2009，25(2)：187-188.
[10] FINKENZELLER K．射频识别技术—无线电感应的标签和非接触式IC卡的原理与应用[M]．陈大才,译.北京：电子工业出版社，2001．