RFID装备管理系统的防碰撞算法

2013-07-03杨成龙

兵器装备工程学报 2013年6期

杨成龙

(重庆大学，重庆 400044)

RFID 技术在装备管理信息系统中的应用，必然会有多目标的识别，多目标的识别在此系统的延伸问题就是多标签的识别，这是很重要的一个问题。在该管理信息系统中，当工作范围内同时出现了多个读写器和射频标签时，读写器和标签两种设备的任意组合产生的干扰，就是冲突，也称碰撞。称之为RFID 系统有了碰撞(collision)［1］。如何有效的解决RFID系统的碰撞这一关键问题?根据现有的研究成果，防碰撞算法是一个不错的选择。据通信原理可知，直接提高数据传输效率的方法是增大频率带宽，可是这个是非常有限的，所以我们只有从降低碰撞的概率入手，来提高对目标的识别。

1 碰撞算法相关理论

1.1 防碰撞

RFID 系统可以采用不同的算法来减少冲突。在RFID技术越来越普及的当代，很多应用场合都遭遇到碰撞问题，防碰撞技术已经成为RFID 系统应用必须面临和解决的关键问题。碰撞的预防就是选择合适的射频标签，特别是在众多的标签之中准确的、快速的进行通信，不断的选出，直至数据交流结束。

防碰撞问题主要解决的是如何快速和准确地从多个标签中选出一个与读写器进行数据交流，而其他的标签同样可以从接下来的防碰撞循环中选出与读写器进行通信。

1.2 射频识别系统中常见的碰撞

在射频识别系统中，常见3 种碰撞形式，如图1 所示。其中，标签干扰和读写器干扰归类于读写器碰撞范畴，是读写器相互的沟通问题。本文主要针对标签之间的碰撞问题进行讨论。

如前所述，该装备管理系统中的数据碰撞问题以通信的角度理解为多路存取问题。常利用FDMA、SDMA、CDMA 以及TDMA 这4 种方法应对。建设成本的昂贵和使用环境的复杂不得不使我们更多的选择TDMA 的方法。信道资源的高效合理利用，具体讲就是通道容量和时间以及用户间的分配问题。这也是实现RFID 系统的防碰撞的常用机制，是应用最多的一种。将TDMA 法解决标签碰撞问题根据提供能量的不同可分为以下几种情况(如图2)。

图1 RFID 系统中的3 种碰撞问题

图2 时分多路标签防碰撞算法分类

针对该平台，选择灵活的较为成熟的二进制搜索算法(BS)，因为标签基本都是确定性的［2］。

2 二进制树形搜索算法(BS)

在RFID 系统的ISO/IEC 标准中，在ISO 14443 标准中，TYPEA 和ISO 18000-6 标准中，TYPEB 中都可使用的是二进制树搜索算法［3-4］。二进制树形搜索算法(Binary Search)，以逐级的办法将每一次冲突产生隔离，生2 个支脉，这属于时间域多重访问中的一种算法。这些支脉会越来越具体和细致，直到最后的支脉下面仅有一个单位的信息量或是没有。这个流程是按照“First-in，Last-out”的原则［5］。算法的实现，必然需要相应的请求、选择、读数命令，在实际系统中，还有鉴别或写入、取消预定等命令。

BS 算法会将碰撞标签的每一位逐步识别出来，在这之前需要让读写器使用曼彻斯特编码判断到冲突的准确位置，见图3。

图4 中，阅读器识别范围内有标签1 和标签2，标签接受到命令后将自己的识别码传输给阅读器。图3 中的虚线线框就是标签冲突的位置。

下面3 个式子分别表示上述BS 算法的识别出一个目标的迭代次数为f(n)

目标全部被识别的总迭代次数为

若定义r 为非零自然数，定会有2r-1 ＜n≤2，通过式(1)、式(2)便可得出想要的总的次数

图3 二进制树型搜索算法示意图

图4 Manchester 编码发现碰撞原理

为了从大量收发器中检测出单个收发器所需要的轮回平均数为L，取决于在读写器检测区中的收发器总数N，可以容易计算出

UID 有着越多的位数，显然传输的时间随即增大，是因为传输时间就会增长。如每次都传输完整的UID，每次时间为T，则用于传输UID 的时间为

这也就是说交互范围内的电子标签数和UID 位数是成正比的，传输时间的长短和防冲突运算时间也是成正比的，这也是BS 算法的传输时延。

3 动态二进制搜索算法(DBS)

在DBS 算法中，就像是按需分配原则。阅读器需要的识别码才被发送，这也是搜索的条件。而目标上的射频标签只呈现为被识别的SN。在该算法中读写器发生冲突后，将一样比特码的识别模块回馈其互补的序列号，而后只发送合适的NVB 和相应的SNR 比特编码。

从而，这种动态的算法极高的提高了管理的执行效率。最主要的原因是它减少了用在序列号在系统中的传送时间［7］。

4 改进的二进制算法

4.1 算法原理

首先从数学角度理解标签的识别。设标签UID 长度为L(标签UID 以二进制的形式表示)。标签j 的SN 为Ij，标签量为n(n2≥2L)，起始指令时间为T0，休眠指令时间为T1，信道传送周期的帧长度是T，扫描轮回的时隙数为(n2≥2L)。在时隙i 内会有Pi个标签能够与读写器产生数据量:标签j在扫描轮回内的收发时隙为Sj，发送位为Dj，标签UID 对M的商为Qj，标签j 在整个数据收发轮回中的发送顺序Tj，则

系统的性能S 为

算法主要步骤为:

1)以8 位二进制码标签为例，读写器收发REQUEST(null，8)命令，全部标签对此命令作出应答，这些响应了的标签将自身UID 码传输;

2)当读写器无信号，则表示工作范围无射频标签，继续对REQUEST(null，8)命令做出应答，否则对回应信号做出判断;

3)接着步骤2 中的阅读器有信号的情况，通过回应信号产生的译码来判断是否碰撞，并且经过曼彻斯特编码译码得到碰撞最高位。

4)读写器根据步骤3 中的判断结果分析出冲突在哪些比特位上，读写器把这些冲突的比特位置显示为“1”，无信号冲突的部分是“0”。

5)射频标签接受到读写器的REQUEST 指令，将另外几位作为回应传给读写器。若读写器发送SELECT 和READDATE 指令则表明没有冲突发生，之后按图示往下执行。否则在进行上面的循环识别，通过不断的译码，判断出准确的比特位置，显示高地位再次执行REQUEST(UID)命令。

6)全部的目标被识别，识别任务完成，见图5。

图5 改进的二进制搜索算法流程

4.2 分析

作为一个基本的参数了解，我们需要知道单个射频标签的被识别的平均搜索次数［8］，以及全部目标被识别的次数分别为

设识别n 个目标标签，读写器所需要的搜索次数便有S(n)，将冲突次数定为C(n)，这样会有以下2 种情况，通过数学归纳法易证明［9-10］。

5 结束语

本文在分析BS 算法、DBS 算法的基础上提出了一种改进的二进制搜索防碰撞算法，经仿真实验得知，如图6 所示，黄色线表示的改进算法对于相同的n 值来说显然比绿色线表示的BS 算法和DBS 算法需要的搜索次数少很对，这样体现在数据传输效率效率上面是非常可观的。如果进一步规定碰撞发生的比特位数的取值分别为log2n、log2n+k/2、k 三个值，能够更深入的得到它们的传输时延，以及跟随目标个数的关系变化［9］。综述可得下面的结论:在上述规定的条件下，从搜索识别目标的效率上来讲，改进的BS 算法和DBS算法以及BS 算法是逐步降低的过程。显而易见，搜索次数是一个很直观的判断，就我们想要了解的传输效率而言，它和传输时延表达改进的二进制算法、DBS 算法、BS 算法之间的关系是一致的。