1 RFID技术概述

RFID（Radio Frequency Identification，无线射频识别）是自动识别系统的一个重要分支。在RFID系统中应用了无线射频通信技术。应用广泛的条形码技术曾经引发了识别系统领域的革命，但是随着科技的发展，条形码技术暴露出越来越多的不足[1]。此时，RFID技术应运而生。与条形码相比，RFID系统有如下优点：

◆ 标签能够重复使用，而且标签中的信息也可以重复改写，而条形码却不能。

◆ 标签的容量远远大于条形码，其安全性也高于条形码。

◆ 当标签被障碍物遮挡时，仍能够被阅读器识别，而条形码不具备此功能。

◆ 标签被阅读器扫描的速度比条形码快得多，而且标签的寿命也比条形码长。

基于上述优点，RFID引起了人们的极大兴趣。近年来RFID系统发展迅速，并且在交通、物流、安全防伪、公共管理等许多领域得到广泛的应用。一个RFID系统通常由3部分组成，如图1所示。

图1 RFID系统结构

图1中，第一个部分是标签（应答机），它被固定在物体上，并由一个特殊的EPC（Electronic Production Code，电子产品代码）来标定其身份。标签由两个不同的部分组成：天线（标签由此获得来自阅读器的能量）和电子芯片（控制标签进行有效的工作）。第二个部分是阅读器（询问器）。阅读器通常包括两个部分：天线和阅读器。根据所使用的设计方案和技术标准，阅读器可以是只读的或同时具有读写功能的装置，但通常均称为阅读器。阅读器发送信号来“唤醒”标签，并向标签发送命令，然后接收存储在标签中的数据。通常由阅读器获得的数据能够被网络的数据管理系统使用。最后一部分是数据管理系统，它的功能是存储信息和管理数据。数据管理系统能够与固定在远处的阅读器进行通信，从而能够在任意时间获取标签中的信息。

RFID系统的工作过程如下：首先阅读器发送问询信号。如果一个标签在阅读器问询的范围内，它将会被激活，然后与阅读器进行通信，从而阅读器获得存储在标签中的信息。

由上述可知，如果有很多标签同时处在阅读器问询的范围之内，它们将同时与阅读器进行通信，所以阅读器不知道应该和哪一个标签进行“对话”，这就会产生所谓的“碰撞问题”。为了解决RFID系统中的碰撞问题，反碰撞算法是必不可少的，本文将对此进行讨论。

在通信系统中，信息的碰撞总是存在的。同时，也出现了解决这类问题的很多方法，常用的方法有：空分多址（SDMA），频分多址（FDMA）,码分多址（CDMA）和时分多址（TDMA）。但是由于这些方法较复杂，所以不能直接应用在RFID系统中。为了解决RFID系统中的标签碰撞问题，和通信系统相似，也有一些方法可以应用，如空域方法、频域方法和时域方法。在大多数RFID系统中，时域方法凭借其便于操作的优点而得到广泛应用。时域方法的机理是使标签在不同时刻与阅读器进行通信。时域方法又分为：确定性算法和不确定性算法。本文所讨论的算法属于第一类。

2 常用的反碰撞算法

在RFID系统中，解决碰撞问题是最基本也是最重要的问题。也就是说，只有在没有碰撞发生的情况下RFID系统才能正常工作。下面介绍一些常用的方法。

2.1 基于位仲裁的反碰撞算法[2]

在这个算法中，所有处在阅读器问询范围内而未被识别的标签，在开始时均处于激活状态。所有被激活的标签将参与仲裁过程。在仲裁的过程中，进入到阅读器问询范围内的标签将不参与仲裁的过程。这个算法的核心是：当阅读器发出问询命令时，被激活的标签将发出其EPC中一个指定的位上的信息。根据这一信息，标签被分成两组。阅读器将选择其中的一个组继续进行上述仲裁过程，直到识别出一个标签为止。基于此算法的识别时间与处于阅读器问询范围内的标签的数目无关，但与标签的EPC的长度有直接的关系。因此，假如有n个标签同时被识别，标签EPC的长度是m，则基于此算法阅读器需要搜索的总的次数m×n。

2.2 二进制搜索算法[3]

在二进制搜索算法的实现中，起决定作用的是阅读器所使用的信号编码。其编码必须能够确定碰撞的准确位置，可以采用曼彻斯特编码（Manchester）。

二进制搜索算法的方法类似于在天平中采用逐次比较方法。通过多次比较，不断筛选出不同的序列号，时分复用地进行阅读器和标签之间的信号交换，以一个独特的序列号来识别标签为基础。为了从一组标签中选择其中之一，阅读器发出一个请求命令，有意识地将标签序列号传输时的数据碰撞引导到阅读器上，即通过阅读器来判断是否有碰撞发生。如果有碰撞，则缩小范围进行进一步搜索。

二进制搜索算法由一个阅读器和多个标签之间规定的一组命令和应答规则构成，目的在于从多个标签中选出任一个从而实现数据通信。

该算法有3个关键要素： 选用适当的基带编码（易于识别碰撞）；利用标签EPC唯一的特性；设计一组有效的指令规则，高效、迅速地达到选择标签的目的。

2.3 跳跃式动态树形反碰撞算法[4]

此算法与二进制搜索算法主要有两点区别：

① 在一个标签的EPC被识别后，跳跃式反碰撞算法的过程不是二进制搜索算法的重复。阅读器发送的下一个代码不同于前一过程所发送的代码，而是第2个代码（计算后退）、第3个代码（计算后退）、第4个代码(计算后退)等，直到所有标签的所有代码被识别完为止。

② 在阅读器开始发送问询命令时，只发送代码“1”而不是发送与标签EPC等长的全1代码。在下一个问询命令中，阅读器只发送若干位，而不像二进制搜索算法那样发送全部位。如同二进制搜索算法那样，跳跃式动态树形反碰撞算法的搜索过程也是从最高位到最低位依次进行的。假如标签高几位的EPC同阅读器发送的代码一致，这些相应的标签就会发送它们的EPC给阅读器。

3 改进的反碰撞算法

与二进制搜索算法和跳跃式动态树形算法相比，本文所提出的是一种改进的算法。它的目标是当碰撞连续发生时提高标签的识别速度。如同二进制算法，本算法也有一些约定：

① 必须使用曼彻斯特编码。只有使用曼彻斯特编码阅读器才能准确发现碰撞的位置，一一识别出在问询范围内的所有标签。

② 需要引入以下4个命令：第一个是请求命令。此命令发送一序列号作为参数给标签。标签把自己的序列号同接收到的序列号比较，如果小于或等于，则此标签回送其序列号给阅读器。这样可以缩小预选的标签的范围。第二个是选择命令。假如阅读器收到标签的EPC，并且无碰撞发生，阅读器就会选择这个标签，然后执行其他命令（如读写命令）。第三个是读写命令。根据读写命令来处理存储在标签内部的数据。第四个是去选择命令。取消一个事先选中的标签，使标签进入“无声”状态。在这种状态下标签完全是非激活的，对请求命令不作应答。

③ 本算法的关键是要求所有标签能够在同一时刻响应阅读器的问询，以便标签能够同步发送它们的EPC给阅读器。只有在这种情况下本算法才能更好地工作。

以上3点与二进制搜索算法和跳跃式动态树形反碰撞算法是相同的，但本文所提出的反碰撞算法主要有两点不同：

① 由于二进制位上的取值具有相互排斥特性（非1即0），所以假如只有一位二进制位发生碰撞，则阅读器不需要发送请求命令而能够自动识别出这两个标签。

② 假如碰撞连续发生，在阅读器检测出连续的碰撞后，发生碰撞的最低位被置1，其他碰撞位置0。只有最后一位发生碰撞的两个标签将会被阅读器同步识别。与上述3种算法相比，本算法的下一个请求命令是把原有的请求命令的最低两位加10。在把原有的请求命令加10后继续发送请求命令，直到所在阅读器问询范围内的标签被一一识别。

可以从下面的例子中清楚地了解这一过程。假设有8个标签，它们的识别码分别是：10000010（标签1），10001010（标签2），10010010（标签3），10011010（标签4），10100010（标签5），10101010（标签6），10110010（标签7）和10111010（标签8）。这8个标签同时在阅读器的问询范围内，算法的处理过程如下：

第1次，阅读器发送请求命令（1），所有处在阅读器问询范围内的标签都响应此命令。根据曼彻斯特编码规则，阅读器收到的代码是10XXX010，因此阅读器就会知道D5、D4和D3发生了碰撞。根据本文所提出的算法，把发生碰撞的位D5、D4置0，D3置1，即10001，作为下一次阅读器的问询命令。

第2次，阅读器发送请求命令（10001）。阅读器收到的代码为1000X010，因为只有一位发生了碰撞，因此阅读器就没有必要再次发出请求命令。阅读器收到了标签1和标签2的EPC；然后，运行读写命令对这两个标签进行处理。最后阅读器运行“去选择命令”，使得标签1和标签2进入“无声”状态。把此次请求命令加10即为下一次阅读器的问询命令。

第3次，阅读器发出请求命令（10011）。阅读器收到的代码为1001X010。此时只有D3位发生碰撞。类似地，阅读器获得标签3和标签4的EPC，然后对这两个标签进行处理，最后使它们进入“无声”状态。把此次请求命令加10即为下一次阅读器的问询命令。

第4次，阅读器发出请求命令（10101）。阅读器收到的代码为1010X010。D3为唯一的碰撞位。因此阅读器收到标签5标签6的EPC，然后对这两个标签进行处理，最后使它们进入“无声”状态。把此次请求命令加10即为下一次阅读器的问询命令。

第5次，阅读器发出请求命令（10111）。阅读器收到的代码是1011X010。D3是唯一的碰撞位。因此阅读器获得标签7和标签8的EPC。现在阅读器识别出所有的标签。整个过程如表1所列。

表1 改进算法的搜索过程

从表1可以看出，该改进算法中重复搜索的次数是5。假如使用跳跃式动态反碰撞算法，则重复搜索的次数为15；使用二进制搜索算法，重复搜索的次数会更多。所以与二进制搜索算法和跳跃式动态树形反碰撞算法相比，该算法大大减少了重复搜索的次数。由此可得出结论，假如有n个连续的位发生碰撞，则识别2n个标签所需阅读器发送问询命令的次数仅为2n-1＋1，大大提高了RFID系统的工作效率。

4结论

RFID系统的应用领域已经非常广泛，而且越来越重要。由于标签和阅读器的工作环境极为复杂，阅读器识别标签的速度和正确率往往不能令人满意。因此迫切需要有新的反碰撞算法出现，以便更好地解决这个问题。本文提出了一种改进的反碰撞算法。与其他算法相比，尤其在有大量标签存在的环境中，它的优势更加明显。随着标签数目的增加，发生碰撞的概率的增大，用此改进算法将会收到令人满意的效果。这对RFID系统的发展和应用是非常重要的。