无线射频识别(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)重复操作。
(7)如果当前没有标签回传ID，读写器等待一定时间后发送确认命令，附加命令参数“低位减1”。所有在仲裁态且高4为全零的标签Rel低4位减1，回到步骤(4)重复操作。
(8)低4位减1操作重复L次(L是一个系统参数，由系统设定，经验值为4)后，读写器认为所有在仲裁态且寄存器高4位为零的标签都已经被正确读取，则发送确认命令，附加命令参数“高4位减l”，回到步骤(4)。
(9)标签接收到附加“高位减l”参数的确认命令后，所有Rel高4位不为零的标签高4位减l，回到步骤4重复操作；在被要求高位减1前已为零的标签则回到等待态。
(10)重复15次高位减1操作后．读写器认为所有在仲裁态的标签都已经被读取，则仲裁过程停止，所有还处于仲裁态的标签返回等待态。
算法步骤中所述等待态是指电子标签上电后的初始状态；仲裁态是指未被读写器鉴别的电子标签开始响应读写器鉴别命令时进入的状态；确认态是指已被读写器鉴别的电子标签进入的状态。电子标签状态转移规则如下：上电后电子标签进入等待态；处于等待态的电子标签可以进入仲裁态；处于仲裁态的电子标签可以返回等待态；处于仲裁态的电子标签可以进入确认态；处于确认态的电子标签不能返回仲裁态；确认态与等待态之间不能直接转移。
针对上述算法步骤，在以下几个地方加以改进，形成本算法的改进算法。
A、步骤(1)中，随机数产生器产生两组随机数，分别加载到寄存器高位和低4位。其中高位加载的位数M可以动态设为1、2、3或4。
B、步骤(10)中的重复操作次数为2M次。因为改进算法在寄存器低4位也加载了随机数，使得标签在群间转移的概率(即低4位向高位进位的概率)大大增加，特别如果最后一个群中标签的寄存器低4位在退让步骤中进位，则会产生一个新群，因此需要额外增加一次高位减l操作。