一种新颖的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。