一种新颖的RFID防冲突算法

　　无线射频识别(RFID)是一种非接触式的自动识别技术，其基本原理是刺用射频信号和空间耦合(电感或电磁耦合)的传输特性，实现对特定物体的自动识别。RFID技术可以追溯至第二次世界大战期间。后来发展应用到铁路、军队的货物跟踪甚至宠物识别上。在过去的半个多世纪里，RFID的发展经历了从技术探索、试验研究、商业应用和标准化建立等几个重要阶段。从现有发展趋势看，RHD将构建虚拟世界与物理世界的桥梁。可以预见在不久的将来，RFID技术不仅会在各行各业被广泛采用，最终RFID技术还将会与普适计算技术相融合，对人类社会产生深远影响。

　　RFID系统一般由电子标签和读写器两个部分组成，读写器具有同时读取多个电子标签的功能。在多标签对一个读写器的RFID系统中，标签经常会同时向读写器传输数据，这就要求RFID系统建立一种仲裁机制来避免数据发生碰撞。考虑到电子标签本身尺寸、能耗的限制，防碰撞机制在保障功能的同时还要求尽量简单易行，这正是RFID系统设计的挑战之一。

　　算法A基于随机避让、冲突检测的原理，使用1个8位寄存器和1个8位随机数产生器，最大可以仲裁标签的数量只有256个。算法B基于二进制数的原理，使用1个8位寄存器和1个l位随机数产生器，理论上最大可以实现2256个标签的仲裁。文献提出了对该算法的一个实现方案，文献对该算法做了很大改进。算法C类似于算法A，使用1个16位寄存器和16个l位随机数产生器，最大可以仲裁标签的数量是65536个。本文中，作者提出一种分群避让、群内冲突检测的算法和其改进算法，仅需要1个8位寄存器和1个1位随机数产生器就可以实现最大1048 576个标签的仲裁．而且碰撞次数相对干算法B要大大减少。

　　1 仲裁机制描述

　　本方法的核心思想是：首先把电子标签随机分群，并将群随机排序以实现群问的随机避让，然后在群内进行冲突检测和标签的仲裁。实现时标签仅需一个寄存器：利用其高位存储群号，低位存储冲突检测时退避的步数，实现极为简单。下面以8位寄存器为例具体说明本算法的仲裁机制。

　　当读写器初始化标签时，所有标签在0~15之间任选一个整数存人寄存器高4位(相当于随机选择一个群)并把寄存器低4位设为全O，同时产生一个O或l的随机数加到寄存器中。如果此时寄存器中的8比特数为全0则圆传该标签的ID(ID是指电子标签的惟一标识，在不同的编码系统中有不同的含义)。如果多个标签同时回传数据，则冲突发生。发生冲突后，其他寄存器高4位为O的标签寄存器中的数加l，而寄存器中的8比特数为全0的标签则再产生一个0或1的随机数加到寄存器中。如果寄存器作加法后仍为全零。则继续回传该标签的ID；如果回传时不发生碰撞，则其他寄存器高4位为O的标签仅把寄存器低4位减1后重复前面的回传操作。当寄存器高4位全为0的标签全部回传完ID，则所有其他标签把寄存器高4位减1后重复前面的操作。

　　此外依本算法．由于所有标签随机选择群，有可能会出现某个群中的标签数目过大，使该群中的标签在仲裁过程中始终发生碰撞，标签寄存器始终加1，导致寄存器低4位向高4位进位。进位意味着所有进位的标签的寄存器低4位清零而高4位加1，这使得这些标签不再属于原有的群而归人到下一个群中，从而优化了因随机选择而产生的分布不均匀的群标签数。

　　本算法中，标签最大退让步数为24=16步，因此每个群最大能仲裁的标签数目为216=65536，则本算法能仲裁的标签数理论上限是16×216=1048576。

　　2 算法步骤

　　给出算法步骤，假设使用一个8位寄存器，则本算法包括以下步骤：

　　(1)在所述RFID系统的被动方一标签中设计一个4+4位的寄存器(Rel)和1个"0"、"l"随机数产生器(RGI)，如图l所示。

　　(2)在所述RFID系统的主动方一读写器向所有处在等待态的标签发送初始化命令。标签因此进入仲裁态，用RGI产生4比特随机数，加载到Rel高4位R7~R4，低4位R3~R0全部清零。

　　(3)读写器等待一定时间后发送允许回传命令。

　　(4)Rel为全零的标签向读写器回传标签ID。

　　(5)如果当前只有一个标签回传ID，读写器正确读取该ID，则发送确认命令，附加命令参数"低位减l"。回传了ID的标签接收到该命令后，进入确认态，其他高4位为全零的标签Re1低4位减1，回到步骤(4)重复操作。

　　(6)如果当前有多个标签回传ID，读写器通过CRC校验或码长校验，检测到错误的ID号，则发送确认命令，附加命令参数"寄存器加1"。接收到读写器这个命令后，所有在仲裁态且Rel为全零的标签由RGI产生1比特随机数和寄存器上的数相加后重新载入到寄存器中；其他仲裁态且Rel高4位为零而低4位不为零的标签Rel加1，回到步骤(4)重复操作。