(四川托普信息技术职业学院 通信系，成都 611743)

1 引 言

射频识别(RFID)系统主要由阅读器和电子标签两部分组成。阅读器和标签之间通过无线方式相互通信和交换数据，所有电子标签都工作在同一频率，共享同一通信信道，如果多个标签进入阅读器作用范围内，当标签收到阅读器发出的命令后，所有标签同时向阅读器发出返回数据，信号就会相互干扰，发生冲突，这就是RFID系统中的碰撞问题。防止这些冲突发生的方法就叫防碰撞算法。

解决冲突的方法主要有4种：时分多址(TDMA)、频分多址(FDMA)、码分多址(CDMA)和空分多址(SDMA)。由于RFID系统的一些特点和限制要求，传统的一些防碰撞技术很难在RFID系统中应用。目前，大多采用时分多址的方法。

RFID技术要得到普及和广泛应用，标签的成本必须足够低，应当尽可能使用无源标签，标签内部没有电源，标签的工作能量由阅读器产生的电磁场提供。阅读器可有自己的电源，但阅读器的成本也不能太高。由于这些特点，对标签有以下限制要求：

(1)由于标签内部没有电源，所以不允许标签消耗过大的功率和能量;

(2)标签之间不能相互通信，没有载波检测能力，也不能检测位冲突;

(3)标签不能处理过于复杂的计算，存储空间也比较小。

在标签的防碰撞算法中，可以分为概率性算法和确定性算法两大类，概率性算法主要有ALOHA时隙防碰撞算法[1-2]，确定性算法主要有二进制搜索防碰撞算法[3]。ALOHA算法在标签数量较大时，整个系统的可靠性难以保证，信道利用率也不高。二进制搜索防碰撞算法有较高的信道利用率，系统的可靠性高，但识别延时较长。本文主要研究确定性算法中的二进制搜索防碰撞算法及其改进算法。

现有的二进制搜索算法及其改进算法主要有二进制搜索基本算法、返回式二进制树搜索算法[3]、返回式动态二进制树搜索算法[4]、修剪枝二进制搜索树算法[5]、引入预处理的改进多状态二进制搜索算法[6-7]等，这些算法可参考相应文献，在此不再赘述。这些算法经过不断的改进，减小了标签搜索次数，阅读器和标签之间相互通信的数据量也在不断减小，但是，这些算法或多或少都存在一个问题：阅读器和标签之间重复发送已知信息，影响了标签识别的速率。为此，本文提出了一种计数型位屏蔽射频识别防碰撞算法，该算法充分利用已知信息，不发送和反馈重复信息，同时，尽量减小阅读器和标签之间信息交换的比特数，提高了标签识别的速率。

2 防碰撞算法原理

2.1 冲突位的检测

要通过搜索树的方法实现防碰撞操作，阅读器必须要对标签返回的数据进行准确的冲突位检测，这就需要对返回数据进行适当的编码。曼彻斯特编码(Manchester)可以方便地实现冲突位检测，该编码用“01”表示二进制的‘0’码，用“10”表示二进制的‘1’码，如：二进制编码“0101”用Manchester编码表示为“01100110”。若两个或多个标签同时发送Manchester编码，当某位发生了冲突，即该位有不同的值，既有“01”，又有“10”，则阅读器检测到的数据为“11”，由于Manchester编码没有“11”码元，阅读器就判断该位发生了冲突[8]。

在RFID系统中，每个标签都有唯一的编码(ID)。设有两个标签，ID分别为01100101和01010111，利用Manchester编码，阅读器可以正确检测出冲突位，如图1所示。

图1 Manchester编码冲突位检测

由图1可以看出，阅读器检测出D1、D4、D5位为“11”，共有3位冲突位，用X表示，阅读器检测出的数据可表示为01XX01X1。

2.2 算法设计

计数型位屏蔽防碰撞算法的设计思想是：尽量利用已知信息，减少重复发送的信息，以提高标签识别速率。

首先，由阅读器发送请求命令，所有标签都返回ID数据，阅读器检测出所有冲突位，冲突位记为‘1’，非冲突位记为‘0’，并把冲突位信息发送给标签，由于非冲突位是已识别位，是阅读器已知的数据信息，不需要标签再发送。所以，标签把这些非冲突位进行屏蔽，这些屏蔽位不再返回给阅读器，避免重复发送，标签仅返回必要的冲突位数据信息给阅读器，阅读器检测出冲突位，并发送冲突位信息给标签，标签再对非冲突位进行屏蔽。这样，在不发送非冲突位信息的前提下，可识别出所有标签。

在以下的论述中，假设标签的长度为N，按位表示为(1，2，3，…，N)。

2.2.1屏蔽位和计数器

(1)屏蔽位

在标签中设置一个屏蔽寄存器R，R的长度同标签ID的长度N，R的初值为全‘1’。

屏蔽位的概念由本文作者首先提出，在此，先给出屏蔽位的定义。

屏蔽位指的是标签中和屏蔽寄存器R的‘0’位对应的ID数据位，反之，和R的‘1’位对应的ID数据位为非屏蔽位。

(2)休眠计数器

标签有激活态和去活态2种工作状态，未识别的标签处于激活态；已识别的标签由阅读器发出去活命令后处于去活态，不再响应任何命令。激活态又分待命态和休眠态，标签中设置一个休眠计数器，处于激活态的标签，计数值为0则为待命态，计数值等于或大于1则为休眠态。当标签收到命令后，首先更新休眠计数器，完成更新后，处于待命态的标签发送返回数据给阅读器。

2.2.2请求控制命令

为了方便描述，先对阅读器的请求控制命令REQ(SNR)进行说明：

(1)SNR=0：标签收到命令后，休眠计数值为0，处于待命态的标签返回ID数据；

(2)SNR=1：标签收到命令后，休眠计数值减1，处于待命态的标签更新R，R中最高位‘1’改为‘0’，R完成更新后，该标签非屏蔽位组成返回数据，发送给阅读器；

(3)SNR>1：标签收到命令后，处于待命态的标签先更新屏蔽寄存器R：SNR各位取代R的对应‘1’位，再更新休眠计数值：非屏蔽位首位为0的标签仍处于待命态，否则转入休眠态，休眠值为1。处于休眠态的标签计数值加1。完成休眠计数值更新后，处于待命态的标签，R的最高‘1’位改为‘0’，该标签发送返回数据给阅读器，返回数据由标签ID非屏蔽位组成。

2.2.3算法流程

计数型位屏蔽二进制搜索算法的具体算法处理流程如下：

(1)阅读器发送REQ(0)；

(2)标签收到命令后，休眠计数值为0，所有标签同时返回ID数据给阅读器；

(3)阅读器检测接收数据是否有冲突位，若没有冲突位，跳至步骤5；若有冲突位，则可得到下次请求命令的SNR(SNR>1)，SNR构成如下：接收数据的所有冲突位为‘1’，其余位为‘0’，阅读器发送REQ(SNR)；

(4)标签收到命令后，更新R，更新休眠计数器，处于待命态的标签发返回数据给阅读器；

(5)阅读器若检测出冲突位，则转至步骤3；阅读器若没有检测出冲突位，则识别出一个标签，阅读器读取该标签数据，对该标签进行去活化，该标签处于去活态；

(6)阅读器发送REQ(1)；

(7)标签收到命令后，更新休眠计数器，更新R，处于待命态的标签发返回数据给阅读器；

(8)跳至步骤3，依此循环，直到识别出所有标签。

步骤3还可以进一步改进：若阅读器检测到仅有一个冲突位，则可识别出两个标签：一个标签该冲突位为‘0’，另一个标签该冲突位为‘1’。

阅读器识别标签的算法如下：阅读器中设置一个ID存储区域来存放收到的数据，设阅读器作用范围内共有K个标签，由于计数型位屏蔽搜索算法总的搜索次数最多为2K-1次，所以存储区大小设置为2K-1就足够了。通过对收到的数据进行存储和处理，可以识别出所有的标签：

(1)若阅读器请求命令的SNR=0，则直接存储标签返回的ID数据；

(2)若阅读器请求命令的SNR≠0，则作如下处理；若SNR>1，则返回数据首位补0；若SNR=1，则返回数据首位补1，得到一个新数据。在ID存储区，搜索最新存储的冲突位个数和该新数据长度相等的ID存储值，用该新数据逐位取代该存储值的对应冲突位(前一个存储值还继续保留)，得到一个新的存储值；

(3)若阅读器收到的ID数据无冲突位，则可识别出一个标签；若阅读器检测到仅有一个冲突位，则可识别出两个标签。

3 算法比较和仿真

为评介计数型位屏蔽二进制搜索算法的性能，对位屏蔽二进制搜索算法和返回式动态二进制搜索算法进行了比较和仿真。

3.1 返回式动态二进制搜索算法

返回式动态二进制搜索算法是在基本二进制搜索算法基础上改进的一种算法。

当阅读器检测到最高冲突位(假设为第Q位)，则可得到下次请求命令序列号(长度为Q)：前Q-1位与接收到的ID号的前Q-1位相同，第Q位为0。各标签把自身ID号的前Q位与之比较，相同的标签返回后面的N-Q位给阅读器。当识别出一个标签后，阅读器的请求命令序列号为：上一次请求命令序列号的第Q位改为1，其余不变。通过这种返回动态式的搜索，可以识别出所有的标签。

假设阅读器作用范围内有K个标签，阅读器检测数据共有H次仅1个冲突位。返回式动态二进制搜索算法完成所有标签识别的搜索命令次数为L(K)=2K-1。计数型位屏蔽搜索算法完成所有标签识别的搜索命令次数为L(K)=2K-2H-1。

由于计数型位屏蔽搜索算法仅发送非屏蔽位信息，所以阅读器和标签之间的数据通信量更少，特别是在有大量相同ID比特位的情况下，更加明显。

3.2 算法仿真

对计数型位屏蔽二进制搜索算法和动态二进制搜索算法进行了仿真，仿真环境为：标签ID长度为96 bit,其中30 bit是相同的，其余66 bit随机分配；比特率为128 kbit/s，标签数量为10～300。仿真结果如图2所示。

图2 不同标签数量的识别时间

根据计数型位屏蔽二进制搜索算法的原理不难看出，标签中的相同比特位越多，其识别速度越快，在上述仿真环境中，假设66 bit是相同的，其余30 bit随机分配，其余条件不变，仿真结果如图3所示。

图3 相同比特位较多情况下标签的识别时间

由仿真结果可以看出，计数型位屏蔽搜索算法识别时间远小于返回式动态二进制搜索算法。

在标签相同比特位个数增加的情况下，返回式动态二进制搜索算法识别时间并没有减少，但计数型位屏蔽搜索算法识别时间却大大减小了。

4 结束语

本文提出了计数型位屏蔽搜索算法，其核心思想是：充分利用已知信息，不发送和反馈重复信息，最大程度减少阅读器和标签之间的通信量。

现有的二进制搜索算法及其改进算法，或多或少都存在重复发送和反馈已知信息的问题。与已有的二进制搜索算法相比，计数型位屏蔽搜索算法彻底解决了阅读器和标签之间重复发送信息的问题，利用位屏蔽寄存器屏蔽所有的已知信息，标签仅发送阅读器未知的冲突位信息；休眠计数器把不需要返回数据的标签转入休眠态。

计数型位屏蔽搜索算法特别适合于有大量比特位相同的标签的识别，待识别标签相同比特位越多，越能体现其优势。需要提到的是，文献[6]中提到的预处理方法，对于全部待识别标签都有部分比特位相同的情况，也能在一定程度上提高标签的识别速率。但是，由于该方法只是进行简单的预处理，对于待识别标签中的部分标签有相同比特位的情况却无能为力，但在实际应用中，这却是经常出现的情况，而计数型位屏蔽搜索算法能很好地解决这一问题。计数型位屏蔽搜索算法不但有一定的理论价值，而且也有一定的实用价值。

参考文献：

[1] 万红,杨延昭.RFID防碰撞算法研究与改进[J].微计算机信息,2009,25(3-2):230-232.

WAN Hong,YANG Yan-zhao.Research and Improvement on Anti-collision Algorithm for RFID System[J].Microcomputer Information,2009,25(3-2):230-232.(in Chinese)

[2] 刘丹,魏鹏,谭杰,等.一种RFID多标签防碰撞检测方法[J].小型微型计算机系统,2009,30(9):1890-1894.

LIU Dan, WEI Peng, TAN Jie，et al.Method for Detecting the Collision of Multiple RFID Tags[J].Mini Microcomputer System, 2009, 30(9): 1890-1894. (in Chinese)

[3] 林挺钊,刘建成.RFID二进制搜索算法的研究与改进[J].福建工程学院学报,2008,6(6):732-736.

LIN Ting-zhao, LIU Jian-cheng. Improvements on radio frequency identification(RFID) binary search algorithm[J]. Journal of Fujian University of Technology, 2008, 6(6): 732-736. (in Chinese)

[4] 王忠勇,高向川.基于回溯的RFID防冲撞算法[J].微计算机信,2009,25(2):187-188,217.

WANG Zhong-yong,GAO Xiang-chuan.RFID Anti-collision Algorithm Based on the Recollection[J]. Microcomputer Information,2009,25(2):187-188,217.(in Chinese)

[5] 余松森,詹宜巨.基于修剪枝的二进制树形搜索反碰撞算法与实现[J].计算机工程,2005,31(16):217-218.

YU Song-shen, ZHAN Yi-ju. A Binary-tree Searching Anti-collision Algorithm Based on Pruning Away Branches and Its Practice[J]. Computer Engineering,2005,31(16):217-218.(in Chinese)

[6] 吴跃前,辜大光,范振粤.RFID系统防碰撞算法比较分析及其改进算法[J].计算机工程与应用,2009,45(3):210-213.

WU Yue-qian, GU Da-guang, FAN Zhen-yue. Comparison and analysis of anti-collision in RFID system and improved algorithm[J].Computer Engineering and Applications,2009,45(3):210-213.(in Chinese)

[7] 李兴鹤, 胡咏梅, 王华莲.基于动态二进制的二叉树搜索结构RFID 反碰撞算法[J].山东科学, 2006,19(2):51-55.

LI Xing-he, HU Yong-mei, WANG Hua-lian. An anti-collision RFID algorithm based on binary-tree search of the dynamic binary[J].Shandong Science, 2006, 19(2): 51-55. (in Chinese)

[8] 廉国斌.射频识别系统中的防碰撞算法研究[J].计算机技术与发展,2009,19(1):36-38.

LIAN Guo-bin. Research on Anti-Collision Algorithm for RFID Systems[J].Computer Technology and Development, 2009, 19(1): 36-38. (in Chinese)