登录
注册
一种新颖的RFID防冲突算法
作者：张明 张建华 徐国鑫 张平
来源：RFID世界网
日期：2007-06-11 15:47:20
摘要：提出一种应用于RFID系统上行链路的多标签冲突检测算法，并给出了参考安现电路。依算法，对电子标签进行随机分群，在群间做随机避让，在群内进行冲突检测和标签的仲裁。与现有的随机避让算法和二进制树算法相比，该算法不但有效降低了碰撞次数，实现电路也更简单。
无线射频识别(RFID)是一种非接触式的自动识别技术，其基本原理是刺用射频信号和空间耦合(电感或电磁耦合)的传输特性，实现对特定物体的自动识别。RFID技术可以追溯至第二次世界大战期间。后来发展应用到铁路、军队的货物跟踪甚至宠物识别上。在过去的半个多世纪里，RFID的发展经历了从技术探索、试验研究、商业应用和标准化建立等几个重要阶段。从现有发展趋势看，RHD将构建虚拟世界与物理世界的桥梁。可以预见在不久的将来，RFID技术不仅会在各行各业被广泛采用，最终RFID技术还将会与普适计算技术相融合，对人类社会产生深远影响。
RFID系统一般由电子标签和读写器两个部分组成，读写器具有同时读取多个电子标签的功能。在多标签对一个读写器的RFID系统中，标签经常会同时向读写器传输数据，这就要求RFID系统建立一种仲裁机制来避免数据发生碰撞。考虑到电子标签本身尺寸、能耗的限制，防碰撞机制在保障功能的同时还要求尽量简单易行，这正是RFID系统设计的挑战之一。
文献[1]和[2]提出了三种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 仲裁机制描述
本算法中，标签最大退让步数为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操作。
3 电路实现
算法实现的参考电路框图见图l，其中RGI是一个“0”“1”随机数产生器；Rel是一个8位寄存器。加法器ADDl和ADD2的加减功能根据读写器命令来设定：当执行加法操作时，低4位的ADD2需向高4位的ADDl进位；当执行减法操作时，两个器件ADDl和ADD2相互独立。加法器可以工作在同步状态或异步状态，工作在同步状态时可以使用电子标签的最大时钟。
4 仿真结果
仿真l：为了评估本算法的优劣，特设计以下仿真：标签使用8位寄存器，高4位为高位。定义0个、2个和2个以上的标签同时发送数据时为传输冲突；只有一个标签发送数据时为传输成功，平均冲突次数定义为传输冲突总次数和传输成功总次数的比；空传率定义O个标签发送数据的次数与传输成功总次数的比。观察标签数为20~10000时的平均冲突次数。
仿真结果如图2所示，本文提出的算法与二进制算法性能接近，平均每成功传输1次都要伴随2次传输冲突；而改进算法则在标签数为50~5000个时明显减少了碰撞次数。同时也注意到当标签个数少于50时，改进算法性能下降，这是因为此时标签数接近分群的群数导致空传率上升所致，解决的办法是减少分群的群数。针对该问题，特设计仿真2来分析。
仿真2：为了分析低标签密度时改进算法的性能，特设计以下仿真：采用改进算法，分别使用5~8位寄存器。高l~4位为高位，即分群群数分别为2、4、8和16。仿真结果如图3所示，可以看到当标签总数为20时，如果把高位寄存器的位数从4降到l，则平均碰撞次数从5 5回落到1．4。而当标签总数为200和2000时，高位寄存器位数的改变对平均碰撞次数的影响不大。因此如果在某次仲裁中出现多次空传，根据这个先验知识，读写器可以在下一次仲裁时指示标签改变寄存器高位个数，以此降低空传率，进而可以降低平均碰撞次数。
本文提出的防碰撞算法仅需在电子标签中配置1个8位寄存器、1个l位“O”、“l”随机数产生器和2个4位加减l 计数器以及少量选择电路就能实现最多达1048 576个标签的仲裁。仿真表明本算法产生的碰撞概率明显小于二进制数算法，同时通过寄存器高位的灵活设置，还能有效解决低标签密度时空传率高的问题，从而进一步降低了碰撞概率。本算法实现简单，复杂度低，非常适合在RFID系统中应用，因而具有广阔的应用前景。
RFID系统一般由电子标签和读写器两个部分组成，读写器具有同时读取多个电子标签的功能。在多标签对一个读写器的RFID系统中，标签经常会同时向读写器传输数据，这就要求RFID系统建立一种仲裁机制来避免数据发生碰撞。考虑到电子标签本身尺寸、能耗的限制，防碰撞机制在保障功能的同时还要求尽量简单易行，这正是RFID系统设计的挑战之一。
文献[1]和[2]提出了三种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 仲裁机制描述
本算法中，标签最大退让步数为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操作。
3 电路实现
算法实现的参考电路框图见图l，其中RGI是一个“0”“1”随机数产生器；Rel是一个8位寄存器。加法器ADDl和ADD2的加减功能根据读写器命令来设定：当执行加法操作时，低4位的ADD2需向高4位的ADDl进位；当执行减法操作时，两个器件ADDl和ADD2相互独立。加法器可以工作在同步状态或异步状态，工作在同步状态时可以使用电子标签的最大时钟。
4 仿真结果
仿真l：为了评估本算法的优劣，特设计以下仿真：标签使用8位寄存器，高4位为高位。定义0个、2个和2个以上的标签同时发送数据时为传输冲突；只有一个标签发送数据时为传输成功，平均冲突次数定义为传输冲突总次数和传输成功总次数的比；空传率定义O个标签发送数据的次数与传输成功总次数的比。观察标签数为20~10000时的平均冲突次数。
仿真结果如图2所示，本文提出的算法与二进制算法性能接近，平均每成功传输1次都要伴随2次传输冲突；而改进算法则在标签数为50~5000个时明显减少了碰撞次数。同时也注意到当标签个数少于50时，改进算法性能下降，这是因为此时标签数接近分群的群数导致空传率上升所致，解决的办法是减少分群的群数。针对该问题，特设计仿真2来分析。
仿真2：为了分析低标签密度时改进算法的性能，特设计以下仿真：采用改进算法，分别使用5~8位寄存器。高l~4位为高位，即分群群数分别为2、4、8和16。仿真结果如图3所示，可以看到当标签总数为20时，如果把高位寄存器的位数从4降到l，则平均碰撞次数从5 5回落到1．4。而当标签总数为200和2000时，高位寄存器位数的改变对平均碰撞次数的影响不大。因此如果在某次仲裁中出现多次空传，根据这个先验知识，读写器可以在下一次仲裁时指示标签改变寄存器高位个数，以此降低空传率，进而可以降低平均碰撞次数。
本文提出的防碰撞算法仅需在电子标签中配置1个8位寄存器、1个l位“O”、“l”随机数产生器和2个4位加减l 计数器以及少量选择电路就能实现最多达1048 576个标签的仲裁。仿真表明本算法产生的碰撞概率明显小于二进制数算法，同时通过寄存器高位的灵活设置，还能有效解决低标签密度时空传率高的问题，从而进一步降低了碰撞概率。本算法实现简单，复杂度低，非常适合在RFID系统中应用，因而具有广阔的应用前景。
