邓一文，张红雨，张鹏程，向 舸

（电子科技大学 电子工程学院，四川 成都 611731）

RFID技术是一种非接触式的自动识别技术。在RFID系统工作时，当有多个标签同时向读写器发送数据时，由于传输信号的相互干扰，会造成数据无法读取。这就必须通过一定的方法，以使读写器能够正确的完成与所有标签的通信，这些方法就叫做防碰撞算法。随着物联网的应用领域越来越广泛，能适用于各种基于ISO/IEC 14443 A标准、低成本、小尺寸、高性能的非接触式高频通信的应用场合也越来越多，所使用到的标签数量也越来越大。因此提高高频读写器的防碰撞能力成为提高读卡器性能关键[1]。

文中便对符合ISO/IEC 14443 A规范的高频读写器运用的防碰撞方法所基于的二进制搜索算法进行了介绍。并对实际所运用到的比特防碰撞方法进行了详细的研究，对在防碰撞过程中读写器与标签的通信方法进行了分析，详细说明了比特帧防冲突的具体流程。

1 二进制搜索算法

1.1 二进制搜索算法简介

RFID冲突问题与计算机网络、无线电通信冲突问题都有相似之处。在无线电通信系统中，常用的多路存取方法一般有：空分多路法（SDMA）、频分多路法（FDMA）、码分多路法（CDMA）及时分多路法（TDMA），这些方法都可以被借鉴，但在RFID这个特殊系统中，空分多路法、频分多路法、码分多路法在技术实施上比较困难[2]，对读写器和标签的要求很高，需要支付的成本也相当高，只限制在少数的特殊应用场合。在诸多防冲突算法中，只有TDMA应用得非常广泛。

TDMA是把整个可供使用的通路容量按时问分配给多个标签的技术，读写器与各个标签分别在不同的时间里通信。尽管是在不同的时间通信，但由于整个时间很短，以致用户感觉不到时间浪费，从而可以被认为读写器对各个标签的读写是“同时”进行的。

在ISO/IEC 14443 A规范中，便采用了TMDA防冲突算法中的二进制搜索算法。

1.2 二进制搜索算法原理

二进制搜索算法是以标签的唯一序列号为基础来实现防冲突的。当多个标签同时向读写器发送序列号时，读写器能判断出数据冲突位的准确位置，由于冲突位只能是“1”和“0”，然后强迫是“1”或“0”的标签暂时退出，以此类推。 在判断完整个序列号之后，将得到唯一的序列号[3]。

能使得读写器能判断数据冲突位的准确位置的编码是二进制搜索算法的必要前提。Manchester编码就具有这种性质。图1是NRZ编码和Manchester编码发生冲突时的比较。

图1 NRZ和Manchester码发生冲突时的差异Fig.1 The difference between NRZ and Mancherster

由图1可知，对于NRZ码，混合信号不能反映出异常的状态。而当Manchester编码有不同的值时，接受到的整个位都是高电平，这种状态未作规定，导致一种错误，读写器可根据错误判断出冲突发生在第几位。因此，Manchester编码可以实现按位跟踪冲突[4]。

假设标签序列号为n位，并且标签在接到读写器的指令后能在同一时刻将序列号传送给读写器，以准确的检测到冲突位的位置。下面是算法执行过程：

1） 读写器发送“请求”指令，参数为 11…1（n个 1），这时所有标签将应答。读写器检测收到的信号，若没有标签，继续发送“请求”指令；若只有一个标签应答，选择该标签，并与其完成读写操作，操作后令其退出，接着继续发送“请求”指令。

2）若有不止一个标签，标签向读写器传送的序列号将发生冲突，这时读写器利用Manchester编码的特性识别出序列号发生冲突的位置，并将接收到的序列号的最高冲突位置“0”，高于该位的值不变，低于该位的值将全部设为“1”，得到下一步请求命令的参数。

3）在上一步的基础上发送请求命令，这是由于请求命令的参数限制了一部分标签的应答，有可能只有一个标签应答，若不止一个，则重复第2）步，这样不断地缩小待选择的标签，直到成功识别出一个标签。选择该标签，并与其完成读写操作，操作后令其退出。

4）回到上一个结点处继续发送“请求”指令。不断地循环，直到识别出所有的标签[5]。

下面通过实际例子来说明二进制搜索算法的原理：

设有4个标签，它们的序列号分别为l100 1100、1000 0100、1000 0110和1000 1100。当读写器发送请求指令（参数1111 1111）时，4个标签将同时向读写器发送序列号，这时在第l位、第3位、第6位产生冲突，读写器接收到的序列号为1X00 X1X0，X为发生冲突的未知位，从而判断有冲突产生。下一次请求指令的参数将最高冲突位置“0”，高于该位的值不变，低于该位的值将全部设为“1”，得到“101l 1111”，以此为参数继续发送“请求”指令，以此类推，

直到识别出一个标签。具体过程见表1（X表示冲突位）

完成一个标签之后，会继续请求下一个标签。这时读写器不是从最开始搜索，而是根据已有的信息，从上一级的冲突位开始搜索即读写器发送的请求指令参数不是“1111 1111”而是“1000 0111”。表2是搜索第二个标签的执行过程。

在读写器轮询过程中，返回的序列号并非全部的序列号，而是序列号中未知的其他bit值，这样就可以减少二进制搜索法在防冲突运算中所要传输的数据量和所需的时间。在RFID系统中，当射频场内出现冲突时，根据智能卡内标签芯片UID序列号从高到低一次次筛选出某一射频卡，进行后续的操作。二进制搜索法的特点在于稳定性好，准确度高，但是硬件实现比较麻烦。随着冲突标签的越多、标签序列号越长，总的防碰撞执行时问也越长。二进制搜索算法为了从N个标签中找出唯一一个标签，需要进行多次请求。其平均次数为：L=1og2N+1由公式可知，找出一个标签的请求次数将会随着N的增加而迅速增加[6]。

表1 二进制搜索算法执行过程Tab.1 The process of binary search algorithm

表2 二进制搜索算法执行过程（第二步）Tab.2 The process of binary search algorithm（Step 2）

2 比特帧防冲突

ISO/IEC 14443A中提出的比特帧防冲突便是基于二进制搜索算法所提出的一种有效实用的防冲突方法。

在ISO/IEC 14443 A中指定了以下几个指令来管理PICC（标签）与 PCD（读写器）的通信：REQA请求命令，ATQA应答，ANTICOLLISION，SELECT，SAK 应答。

PCD设备（读写器）发送REQA请求命令，REQA命令数据组成如表3所示。

表3 REQA数据Tab.3 Data of REQA

REQA帧包括以下内容：

1）通信起始位S

3）通信结束位E

PICC接收到REQA命令后，在PCD能量场内所有PICC同时发出ATQA应答，ATQA应答数据组成如表4所示。

表4 ATQA数据Tab.4 Data of ATQA

ATQA帧包括以下内容：

1）b8、b7表示UID比特帧的大小，如表5所示。

表5 b8 b7数据Tab.5 Data of b8 b7

2）b1～b5示采用的是比特帧防冲突方式，如表6所示。

表6 b1～b5 数据Tab.6 Data of b1～b5

3）RFU为保留位，均置为0。

应立足绿色生产，提倡增施有机肥，坚持配方施肥，推行节氮减排，做到适氮增磷钾，实现化肥减量增效。“苏麦188”全生育期纯氮总用量为16 kg/亩左右，其中N：P2O5：K2O为1：0.6：0.6，其中氮肥运筹为基苗肥：平衡肥：拔节孕穗肥为5：1.0-1.5：3.5-4.0，磷钾肥分基肥和拔节肥施用。

PCD接受到ATQA应答后，PICC和PCD进入防冲突循环，PCD的ANTICOLLISION和SELECT命令用于防冲突循环。命令数据组成如表7所示。

表7 ANTICOLLISION和SELECT命令数据Tab.7Data of ANTICOLLISION and SELECT

命令帧包括以下内容：

1）SEL表示选择的串联级别，定义如表8所示。

表8 SEL数据内容Tab.8 Data of SEL

2）NVB表示有效比特的数，定义如表9所示。

较高4位称为字节计数，指定所有有效数据位（包括被PCD发送的NVB和SEL）的数目被8除后所得的整数。这样，字节计数的最小值是2而最大值是7。

较低4位称为比特计数，指定所有有效数据位（包括被PCD发送的NVB和SEL）的数目被8除后所得的余数。

3）BCC在UID CLn为40 bit才有，是前5个字节的异或，此时为 SELECT 命令（NVB=‘70’），不足 40 个 bit时，则为ANTICOLISION命令。

表9 NVB数据内容Tab.9 Data of NVB

PCD发送SELECT命令之后，与40位UID CLn匹配的PICC，以SAK作为应答。SAK应答的数据组成如表10所示。

表10 SAK应答数据Tab.10 Data of SAK

1）b3表示UID是否完整，0表示完整，即PICC的UID已被PCD所确认。

2）b6表示当 UID完整时，PICC是否遵循 ISO/IEC 14443－4，1 表示遵循。

3 比特帧防冲突流程

PCD初始化和防冲突流程如图2所示。包括以下步骤：

1）PCD接收到ATQA，防冲突循环开始；

2）PCD指定 NVB的值为 ‘20’， 此值表示 PCD不发出UID CLn的任一部分，而迫使所有在场的PICC发回完整的UID CLn作为应答，发送防冲突指令ANTICOLLISION；

3）PCD接收到所有在场的PICC发回完整的UIDCLn应答；

4）如果发现有冲突则进入第5步，若无则进入第7步；

5）PCD记录第一个冲突的位置；

6）PCD指示NVB值说明UID CLn的有效位数目，这些有效位是接收到的UID CLn发生冲；

突之前的部分，后面再由PCD加一位‘1’。发送防冲突指令ANTICOLLISION；

7）只有这样的PICC，它们的UID CLn部分与PCD发送的有效数据位内容相等，才发送出UID CLn的其余位；

8）假如还有冲突发生，重复5－7。最大循环次数为32；

9）假如没有再发生冲突，PCD指定 NVB为‘70’，此值表示PCD将发送完整的UID CLn，接着发送40位UID CLn，后面是CRC校验码。发送选择指令SELLECT；

10）与40位UID CLn匹配的PICC，以SAK做为应答；

11）检验SAK中叠层位，若叠层位为‘0’，则UID是完整的，PICC从准备状态转换到活动状态，防冲突循环结束；如果层叠位为‘1’的SAK，将CL加1，并再次进入防冲突循环。

图2 比特帧防冲突流程Fig.2 The process of Bite frame anti-collision

4 结束语

基于二进制搜索算法的比特帧防冲突能高效率的解决当高频读写器读到多个标签时的冲突问题，通过对比特帧防冲突的研究，我们能设计出更高效，更低功耗的读卡器。对我国在RFID产业的发展有着积极的推广意义。

[1]纪震，李慧慧，姜来.电子标签与应用[M].西安：西安电子科技大学出版社，2006.

[2]Finkenzeller K. RFID Handbook：Fundamentals and applications in contactless smart card and identification[M].Second Edition，John Wiley&Sons，2002.

[3]（美）A.J.维特比，J.K小村.数字通信和编码原理[M].西安：西安交通大学出版社，1990.

[4]游战清，李苏剑，无线射频识别技术[M].北京：电子工业出版社，2004.

[5]徐丽香，蓝运维.RFID二进制搜索法方碰撞的研究[J].单片机与嵌入式系统应用，2006（5）：33-35.XU Li-xiang，LAN Yun-wei.Research of RFID binary search algorithm[J].Microcontrollers&Embedded Systems.2006（5）:33-35.

[6]陈香，薛小平，张思东.标签防冲突算法的研究[J].现代电子技术，2006（5）:13-15 CHEN Xiang， XUE Xiao-ping， ZHANG Si-dong.Research of anti-collision algorithm of tags[J].Modern Electronics Technique，2006（5）:13-15.