1.二进制树搜索算法
     二进制树搜索算法（其模型如图7-11所示）的基本思想是将处于冲突的标签分成左右两个子集0和1，先查询子集0，若没有冲突，则正确识别标签，若仍有冲突则再分裂，把子集0分成00和01两个子集，以此类推，直到识别出子集0中的所有标签为止，然后再按此步骤查询子集。
      二进制树搜索算法是以一个独特的序列号识别标签为基础的。其基本原理如下：阅读器每次查询发送的一个比特前缀p0p1…pi，只有与这个查询前缀相符的标签才响应阅读器的命令。当只有一个标签响应，阅读器成功识别标签；当有多个标签响应的就发生冲突。在下一次循环中，阅读器给查询前缀增加一个比特0或1，并在阅读器中设一个队列Q来补充前缀，这个队列Q用0和1来初始化，阅读器从Q中查询前缀并在每次循环中发送此前缀，当前缀p0p1…pi是一个冲突前缀时，阅读器就把查询前缀设为p0p1…pi，并把前缀p0p1…pi放入队列Q中，然后阅读器继续这个操作直到队列Q为空为止。通过不断增加和减少查询前缀，阅读器能识别其阅读区域内的所有标签。
2.二进制树搜索算法的实现步骤
（1）阅读器广播发送最大序列号（11111111），查询前缀Q让其作用范围内的标签响应，同时传输它们的序列号至阅读器。
（2）阅读器对比标签响应的序列号的相同位数上的数，如果出现不一致的现象（即有的序列号的该位为0，而有的序列号的该位为1），则可判断出有碰撞。
（3）确定有碰撞后，把有不一致位的数的最高位置0再输出查询前缀Q，依次排除序列号大于Q的标签。
（4）识别出序列号最小的标签后，对其进行数据操作，然后使其进入“无声”状态，则对阅读器发送的查询命令不进行响应。
（5）重复步骤（1），选出序列号为倒数第二的标签。
（6）多次循环完后完成所有标签的识别。
     针对标签发送数据所需的时间和所消耗的功率，有人提出了改进的二进制树搜索算法，其改进思路是把数据分成两部分，阅读器和标签双方各自传送其中的一部分数据，由此可把传输的数据量减小一半，达到缩短传送时间的目的。根据二进制树搜索算法的思路再进行改良，即当标签ID与查询前缀相符时，标签只发送其余的比特位，这样也可以减少每次传送的位数，进而缩短传送的时间，最终缩短防碰撞执行时间。

3.二进制搜索算法
二进制搜索算法类似于天平中采用的逐次比较方法。它通过多次比较，不断筛选出不同的序列号，时分复用地进行阅读器和标签之间的信号交换，并以一个独特的序列号识别标签为基础。为了从一组标签中选择一个，阅读器发出一个请求命令，有意识地将标签序列号传输时的数据碰撞引导到阅读器上，即通过阅读器判断是否有碰撞发生，如果有碰撞，则缩小范围进行进一步的搜索。
二进制搜索算法由一个阅读器和多个标签之间规定的一组命令和应答规则构成，目的在于从多卡中选出任一个来实现数据的通信。
该算法有3个关键要素：选用适当的基带编码（易于识别碰撞）；利用标签卡序列号唯一的特性；设计一组有效的指令规则，高效、迅速地实现选卡。
1）曼彻斯特编码（Mancherster）

    在二进制搜索算法的实现中，起决定作用的是阅读器所使用的信号编码必须能够确定碰撞的准确比特位置。曼彻斯特编码可在多卡同时响应时，译出错误码字，可以按位识别出碰撞，这样可以根据碰撞的位置，按一定法则重新搜索标签。曼彻斯特编码与防冲撞该编码采用以下规则：逻辑“1”表示下降沿跳变；逻辑“0”表示上升沿跳变；若无状态跳变，作为错误被识别。
当多个标签同时返回的数位有不同值时，上升和下降沿互相抵消，以至无状态跳变，则阅读器知道该位出现碰撞，产生了错误。
利用曼彻斯特编码来识别碰撞位：如图7-12所示，假如有两个标签，其ID为10011111和10111011，则利用曼彻斯特可识别出D5和D2位的碰撞。
2）防碰撞指令规则
典型的防碰撞指令规则有以下几个。
（1）REQUEST—请求（序列号）。此命令发送一序列号作为参数给标签。其应答规则是：标签把自己的序列号与接收到的序列号进行比较，如果其自身的序列号小于或等于REQUEST指令的序列号，则此标签回送其序列号给阅读器，这样可以缩小预选的标签的范围；如果其自身的序列号大于REQUEST指令的序列号，则不响应。
（2）SELECT—选择（序列号）。此命令将某个（事先确定的）序列号作为参数发送给标签，具有相同序列号的标签将以此作为执行其他命令（如读出和写入数据）的切入开关，即选择这个标签，具有其他序列号的标签只对REQUEST命令进行应答。
（3）READ-DATA—读出数据，即选中的标签将存储的数据发送给阅读器。
（4）UNSELECT—去选择。取消一个事先选中的标签，则标签将进入“无声”状态，在这种状态下标签完全是非激活的，对收到的REQUEST命令不作应答。为了重新激活标签，必须先将标签移出阅读器的作用范围再进入作用范围，以实行复位。
3）二进制搜索算法的改进分析
（1）二进制搜索算法的传输时间。由二进制搜索算法的工作流程可知，防碰撞处理是在确认有碰撞的情况下，根据高低位不断降值的序列号一次次筛选出某一标签的过程，由此可知标签的数量越多，防碰撞执行时间就将越长。搜索的次数N可用下式来计算：
式中，M是终端作用范围内的标签片数；Integ表示数值取整。
UID的位数越多（如ICODE达64位），每次传送的时间越长，数据传传送的时间也就会增大。例如，每次都传输完整的UID，每次时间为T，则用于传输UID的通信时间为也就是说，终端作用范围内的标签片数越多，UID位数越多，传送时间越长，总的防碰撞执行时间肯定也就越长。
（2）动态二进制搜索算法。动态二进制搜索算法考虑的是在UID位数不变的情况下，尽量减少传输的数据量，使传送时间缩短，提高RFID系统的效率。其改进思路是把数据分成两部分，收发双方各自传送其中的一部分数据，由此可把传输的数据量减小到一半，达到缩短传送时间的目的。
通常序列号的规模在8KB以上，为选择一个单独的标签，每次不得不传输大量的数据，效率非常低。根据二进制搜索算法的思路进行改良，可以减少每次传送的位数，也可缩短传送的时间，从而缩短防碰撞执行时间。
（3）动态二进制搜索算法的工作步骤。
① 阅读器第一次发出一个完整的UID位数码N，每个位上的码全为l，让所有标签都发回响应。
② 阅读器判断有碰撞的最高位数 X，把该位置 0，然后传输 N～X 位的数据后即中断传输。标签接到这些数据后马上响应，回传的信号位是 X-1～1，即阅读器和标签以最高碰撞位为界分别传送前后信号。传递的总数据量可减小一半。
③ 阅读器检测第二次返回的最高碰撞位数X′是否小于前一次检测回传的次高碰撞位数。若不是，则直接把该位置 0；若是，则要把前一次检测的次高位也置 0，然后向标签发出信号。发出信号的位数为 N～X，标签收到信号后，如果这一级信号出现小于或等于相应数据的情况则马上响应，回传的信号只是序列号中最高碰撞位后的数，即 X-l～l位。若标签返回信号表示无碰撞，则对该序列号的标签进行读/写处理，然后使其进入“不响应状态”。
④ 重复步骤①，多次重复后可完成标签的交换数据工作。
动态二进制搜索算法与工作步骤相对应的示例如下。在本例中使用的标签有3张，其序列号分别是：卡1，11010111；卡2，11010101；卡3，11111101。
① 例如，N=8，传送数据为11111111b。最高位为第8位，最低位为l位。根据响应可判断第6位、第4位、第2位有碰撞。
② X=6，即第6位有碰撞，则传送数据变为11011111b。传送时，只传送前面3位数110b，这时卡1和卡2响应，其序列号的前3位与标签相同，不回传，只回传各自的后5位数据，即卡1为10111b，卡2为10101b。由此可判断第2位有碰撞。
③ X′=2，根据要求第 4 位也要补零，则传送数据变为 11010101b，传送时只传送1101010b。这时只有卡 2响应，并返回 1b，表明无碰撞。阅读器选中卡 2进行数据交换，读/写完毕后卡2进入“不响应状态”。
④ 重复步骤①，依序可读/写卡1、卡3。
在动态二进制搜索算法的工作过程中，要注意通过附加参数把有效位的编号发送给标签，从而保证每次响应的位置是正确的。