射频识别技术（RFID）是近年来兴起并逐渐走向成熟的一项自动识别技术。它利用射频的方式进行非接触的双向通信，交换数据从而达到识别的目的。

基本的RFID系统主要包括3部分： 标签，阅读器和天线。在RFID系统中有两种基本的通信方式。第一种通信方式是阅读器到标签的数据传输，称为“广播”；第二种通信方式是多个标签到阅读器的数据传输，称为“多路存取”。在第二种情况中，当多个标签同时向阅读器发送数据时，就会发生数据位的冲突，因此需要一种防冲突的技术以解决上述问题，即多标签防冲突算法。目前的防冲突算法主要是基于ALOHA的算法和基于二进制搜索的算法。本文主要是针对二进制搜索算法进行研究。

1 二进制搜索算法

实现二进制搜索算法的前提是为标签到阅读器的数据传输选择一种合适的编码方法，以识别冲突的准确位置。Manchester（曼彻斯特）编码满足这样的条件。Manchester编码是用在一个位窗内的电平的改变（上升/下降沿）来表示某一位的。因此，在数据传输的过程中“没有变化”的状态是不允许的，并且作为冲突被识别。若多个标签同时发送的数据位有不同的值，则接收的上升沿和下降沿相互抵消，以致在某一个位窗之内“没有变化”。因此通过这种方式可以识别冲突的准确位置。

为了实现这种算法，还需要一组命令。这组命令由阅读器发出，由标签进行处理。

① REQUEST（EPC）： 请求（序列号）。该命令发送一个序列号作为参数给标签。标签将自己的EPC码与序列号相比较，如果小于或等于，则该标签返回其EPC码给阅读器。

② SELECT（EPC）： 选择（序列号）。用某个事先已经确定的序列号作为参数发送给标签。具有该序列号的标签将以此作为执行其他命令（写入和读出命令）的切入开关。

③ READDATA： 读出数据。被选中的标签将存储的数据发送给阅读器。

④ UNSELECT：去选择。取消一个已选中的标签，标签进入“无声状态”。在该状态下标签对收到的REQUEST命令不再应答，如果要重新活化标签，必须暂时离开阅读器的作用范围以实现复位。

2 动态二进制搜索算法

上述二进制搜索算法中，标签总是以完整的序列号作为应答；然而在实践中标签的序列号按系统的规模可以达到10个字节，以致不得不传输大量的数据，识别时间过长。从二进制搜索算法可知： ① 在最高冲突位后的所有位都被置“1”，这部分没有包含任何给标签的信息；② 标签返回的包括最高冲突位在内的之前的各位也是阅读器已知的。由此可见：传输序列号各自的互补部分是多余的，本来是不必传输的。

在动态二进制搜索算法中，阅读器检测到冲突后，下一次只发送当前已确定位数NVB及其对应的比特位编码SNR’，而具有相同确定比特位编码的标签则回送其序列号的互补部分。从而，动态二进制搜索算法大大缩减了算法系统消耗在序列号上的传送时间，即提高了系统的执行效率。此时的请求命令格式可表示为REQUEST(NVB, SNR’)。

3 改进的二进制搜索算法

3.1 算法描述

假设阅读器的作用范围内有5个标签，其EPC码分别为：

TAG1，10110100；TAG2，10100010；TAG3，10111100；TAG4，11100100；TAG5，11111000。

①阅读器发送REQUEST（NVB=0）命令，所有的标签都响应该命令并返回其EPC码，那么阅读器收到的EPC码为1X1XXXX0。

② 阅读器发送REQUEST（NVB=2，10）命令，TAG1、TAG2、TAG3三个标签的前缀与命令参数的10相同，均返回其剩余部分。阅读器收到的EPC码为1X0XXX。

③ 阅读器发送REQUEST（NVB=4，1010）命令，同理只有TAG2响应命令并返回其EPC码剩余部分0011。此时未发生碰撞，随后阅读器发送SELECT命令选中该标签进行其他操作。最后UNSELECT该标签，使其不再响应REQUEST命令。

④ 阅读器返回上一层的REQUEST命令，即REQUEST（NVB=2，10），此时因为TAG2已被屏蔽，只有TAG1和TAG3响应命令，阅读器接收到的EPC码为11X100。

⑤ 阅读器发送REQUEST（NVB=5，10110），同理只有TAG1响应并返回其剩余部分100。无碰撞，阅读器选择该标签并进行其他操作。

⑥ 阅读器返回上一层的REQUEST命令，即REQUEST（NVB=2，10）。此时只有TAG1响应，并返回110100。无冲突，选择该标签并进行其他操作。

⑦ 阅读器再返回更上一层的REQUEST命令，即REQUEST（NVB=0）命令。此时TAG4和TAG5响应，并返回111XXX00。

⑧ 阅读器发送REQUEST（NVB=4，1110）命令，同理只有TAG4返回0100。阅读器选择它并进行其他操作。

⑨ 阅读器返回上一层即REQUEST（NVB=0），由于其他标签已经被屏蔽，此时只有TAG5响应。选择TAG5并进行其他操作。

至此，阅读器范围内的所有标签都已经被正确识别完毕。由上述实例可知该方法在每次正确识别一个标签后，下一次的REQUEST命令都应利用该步骤上一层的REQUEST命令。

假设阅读器的作用范围内有M个标签，阅读器每发送一个REQUEST命令就作为识别一次。由上述方法容易得出，总的所需的识别次数为:SUM=2M-1。

然而若利用二进制搜索算法，从所有的标签中识别一个单独的标签的平均次数为log(M)/log(2)+1，则用二进制搜索算法所需的总的识别次数为:SUM′=log(M)/log(2)+1+log(M-1)/log(2)+1+…+1

当M≥3时，SUM<SUM′。在M≥3(即在阅读器范围内的标签多于3个）时与二进制搜索算法相比，改进后的方法减少了识别次数。同时，由于采用了动态二进制的方法，既减少了系统传输的信息量，又提高了识别速度。

3.2 实现方法

该算法可以利用程序设计中的堆栈（FILO）方法来实现，即将每次发生冲突的REQUEST命令压入栈顶，然后根据动态二进制搜索算法产生一个新的REQUEST命令；在每次正确识别一个标签的REQUEST命令后，从栈顶弹出上一层的REQUEST命令。上例识别过程中堆栈的内容变更如图1所示。

图1 堆栈的内容变更

4 总结

改进的二进制搜索算法与原有的二进制搜索算法相比，减少了防冲突识别的次数；同时结合了动态二进制搜索算法的优点，减少了系统传输的信息量，提高了多标签识别的速度，体现了其优越性。