多标签快速识别算法研究与改进

射频识别RFID(Radio Frequency Identification)是一种非接触自动识别技术。RFID系统主要由阅读器和标签构成，阅读器通过天线信道按照一定的协议读写标签。由于在一个阅读器的识别范围内可能存在多个标签，为了正确识别这些标签，RFID系统的防碰撞算法主要包括两类，一类是基于时隙的Aloha算法;另一类是基于二进制树形搜索的确定性算法。

本文中所研究的多标签快速识别算法，是以RFID空中接口协议ISO/IEC18000-6C的防碰撞要求为基础，利用随机时隙算法解决多标签识别的碰撞问题。本文在研究多标签快速识别算法的同时，结合理论研究，提出了一种改进的基于分组的多标签快速识别算法。仿真结果显示，改进后的算法提高了标签的识别效率，并缩短了识别过程中程序的运行时间。

1 多标签快速识别算法研究

1.1 ISO/IEC18000-6C识别标签过程

ISO/IEC18000-6C规定，阅读器通过Query命令将其产生的随机数Q发给每个标签，标签选择一个0~2Q-1范围内的随机数装入其时隙计数器。选到零值的标签应转移到应答(reply)状态，并立即应答。选到非零数的标签应转移到仲裁(arbitrate)状态，并等待阅读器命令来对它们的时隙计数器中的值进行减1操作，当标签的时隙计数值减为0时应答。ISO/IEC18000-6C的附录D描述了选择Q值的算法，如图1所示。

由图1看出，阅读器根据相应的标签数为0、1还是大于1去调整Q值，大于1时为发生碰撞的情况。在碰撞的情况下，根据Qfp=min(15，Qfp+C)和Q=round(Qfp)调整下一轮的Q值。Q值的调整参数C往往根据经验选择，其中x为标签数。

1.2 多标签快速识别算法数学模型

在一个轮询周期中，每个时隙内的标签响应有三种情况：没有标签响应(空时隙);有一个标签响应(没有碰撞的时隙);有一个以上的标签响应(碰撞时隙)。设标签数量为x，阅读器通过Query命令来产生随机数Q所给出的时隙数为A=2Q。对于每个时隙而言，某个标签在其中响应的概率为A-1，该标签不在其中响应的概率为(1-A-1)。共有x个标签，可以看成对每个时隙进行x次试验，上述情况符合二项分布B(x,A-1)。在多标签识别过程中，标签数比较多。因此，x很大而A-1很小，此时，二项分布近似为泊松分布。泊松分布参数：

根据最大时隙利用率，总结出多标签识别算法的流程图如图2所示。

从图2可以看到，当时隙利用率P1近似于0.367 9时，在后续的循环中只需要调整时隙数A即可，否则比较空时隙率P0与0.367 9大小，并对Q值作出调整，Q的调整参数C的取值应根据实际情况而定，往往靠经验选取，本文取值为0.8。

2 基于分组的多标签快速识别改进算法设计与分析

首先介绍一下此算法涉及到的标签的几个工作状态。准备态(READY)：处于阅读器的询问区域中的标签，而且标签接收到足够支持标签工作的能量。

待命态(STANDBY)：阅读器对所有处于其询问区域中的准备态的标签进行初始化后，选出一组标签来进行组内识别算法。

静默态(QUIET)：标签被阅读器正确读取后，不参与随后的识别过程的状态。

2.1 基于分组的多标签快速识别算法分析

2.1.1 标签的分组

在这个改进算法中，为了对标签执行分组操作，阅读器在发送命令中设定分组参数Q，作用域内的标签一旦接收到询问命令，就会随机产生一个介于0~2Q-1的随机数(包括0与2Q-1)，这样将所有处于“准备”状态的标签分成2Q组。例如，假设Q=2，第一组标签的组号为00，第二组标签组号为01，依次类推。阅读器选定所有属于第一组的标签，使它们处于“待命”态，阅读器再根据组内识别算法对处于“待命”状态的标签进行识别。

在实际应用中，设定Q的值最大值为15(即可以分为32 768组，完全满足实际需求)，阅读器根据特殊序列发生碰撞的情况来适当调整分组Q值，当空闲时隙数过多时Q-1，当碰撞时隙数过多时Q-1。

2.1.2 组内识别算法改进

根据1.1节的数学原理分析，当标签数目与时隙数目大约相等时，时隙利用率最大，那么在分组比特时隙算法中,在每次分组之后对分组标签数目进行统计，并分配与之相等的比特时隙,算法就可以达到最好的性能。

2.2 基于分组多标签快速识别算法流程

根据以上分析本文提出的算法步骤如下：

(1)阅读器发送询问命令，开始一个读取周期。

(2)阅读器作用域内的标签随机选择一个介于[0, 2Q-1]随机数，只有产生随机数为0的标签应答。统计产生随机数为0的标签的个数，并分配与之相等的时隙数目，标签随机选择不同的时隙数，生成特殊比特序列并发送给阅读器。

(3)阅读器检测接收到特殊序列，计算时隙利用率P1，空时隙率P0。

(4)根据表1调节Q值，进而调整标签的分组数。

(5)重复以上过程，直到所有标签都被读取完毕。

基于分组的多标签快速识别算法流程图如图3所示。

3 算法仿真与结果分析

衡量算法，要看同样数量标签的识别时间，它与所需的时隙总数、时隙利用率、阅读器的软硬件设备、标签与阅读器的实际距离、实际工作的电磁环境等众多因素有关，但理论识别时间可以通过时隙总数、时隙利用率加以衡量。除此以外，算法程序本身运行时间在一定程度上也能反映理论识别时间。在给出改进算法的仿真结果之前，先介绍3个衡量算法性能的参数。

(1)时隙数：阅读器识别其询问区域内所有标签所花费的总时隙数。时隙数的值越小，反应的识别速度越快。

(2)吞吐率(Througput)：定义为识别时隙数目与总时隙数目之比，即时隙利用率。

从图6中可以清楚地看到，从程序的运行时间来看改进后的算法具有绝对的优势，当标签数目相同时，改进算法所需的运行时间更短，而且标签数量越大优势越明显，也就是说在相同的时间里改进的算法识别的标签数量更多。

由此看来，改进后的算法在时隙数量、吞吐率、运行时间三个方面都比原算法具有更好的防碰撞性能的表现。这为实际生活中标签识别的防碰撞问题的研究提供了更加优越的方法。

本文对基于ISO/IEC18000-6C协议的多标签快速识别防碰撞算法进行了分析和仿真，并提出了一种改进的基于分组的多标签快速识别算法。在改进的算法中，将待识别的标签首先分成若干组，再根据组内的时隙数依次识别。用Matlab软件对这两种算法进行了仿真对比分析。实验结果表明，在相同的标签总数的情况下，改进之后的算法所需的总时隙数比原算法的少，并且提高了标签的识别效率。除此之外改进的算法还缩短了标签识别的时间。这对于RFID系统中标签的防碰撞问题研究具有一定的参考价值。