登录
注册
一种简单高效的RFID 防冲突算法
作者：北京邮电大学计算机科学与技术学院 柳本金 丁海健
来源：RFID世界网
日期：2007-12-17 14:55:44
摘要：本文在分析研究以往两类RFID 防冲突算法的基础上，结合两者的优点提出了一种基于时隙的改进算法。通过仿真与其它防冲突算法相比在识别数量稳定的情况下，本文提出的算法具有更好的效果。
1. 引言
射频识别技术RFID (Radio Frequency Identification)是目前国内外发展很快的一项新技术。该技术是采用先进的射频技术，实现对各类物体或设备标号的自动识别，从而对其进行管理。射频识别技术能无源，并快速地识别多个物体或设备，能应用于许多场合。随着RFID卡片端成本的不断降低以及体积的不断变小，其应用必将越来越多。在射频卡的识别中，需要解决的一个问题是冲突问题。当多个射频卡同时发送数据时就会产生信道冲突，使得读写头不能读出射频卡的信息。故防冲突算法一直是RFID 中重要研究内容之一。
2. 目前进展
目前的防冲突算法分两大类，一是基于曼切斯特编码的二进制搜索算法及其改进算法，二是基于随机数产生器的时隙算法及其改进算法，下面分别介绍。
2.1 二进制搜索算法及其改进算法
在二进制搜索算法中，射频卡的ID 号必须采用曼切斯特编码。曼切斯特码（Mancherster）可在多个射频卡同时响应时，译出错误位置，可以按位定出发生冲突的位置。根据冲突的位置，搜索射频卡[1]。二进制搜索算法只能识别ID 号唯一的情况。
改进的算法有动态二进制搜索算法，算法改进的地方是对没有发生冲突的ID 位只传送一次。这样就减少了重传的数据，提高了效率[1]。文献[2]中所提的基于动态二进制的二叉树搜索结构RFID 反碰撞算法是对二进制搜索算法的改进。它的思想是对每次识别的冲突位进行分类，分成0、1 两部分，从而形成一颗二叉树[2]，如图1。
时隙算法规定射频卡传送其ID 号所用的时间为一个时隙，如果每个射频卡在不同的时隙段发送其ID 号，就能避免冲突。算法的关键是怎样为不同的射频卡确定其所在的时隙，一般是采用随机数的策略。算法过程如图2。
3. 改进算法
通过对以前RFID 防冲突算法两类方法的分析与研究，结合这两种方法的优点，本文提出了一种新的算法。
3.1 算法介绍与分析
本文提出的算法是在时隙的基础上利用各个ID 号尾数不同的特点，同时结合随机数来实现防冲突的目的。对于多个需要识别的射频卡，考虑它的低N 位ID 号，产生2N 个时隙。各个射频卡在它的低N 位的ID 值所在时隙发送其ID 号。在一个时隙段，如果有两个以上的射频卡（具有相同低N 位ID 值的射频卡）发送数据，则产生冲突，此时产生随机数来区分；如果只有一个射频卡发送其数据，则可读出其ID；如果没有射频卡发送数据，则等待一个较短的时间发现没有数据，则取消这个时隙。总之算法的思想就是要尽量减少等待和冲突的时间，从而提高防冲突的效率。
算法步骤如下：
1. n 个射频卡进入读写范围，感应读写头发出的射频，获得能量，处于激活状态。
2. 读写头发送第一个控制命令，这个命令使得各个射频卡将它的ID 号的低N 位放入寄存器，如这N 位组成的值为零则发送这个射频卡的ID 号。
3. 如果只有一个射频卡发送其ID 则读写头读出此ID。此时读写头判断总时隙是否满，是则结束，否则转6。
4. 如果有多个射频卡发送其ID 则发生冲突，则要增加a 个时隙，读写头发送冲突控制命令，各个射频卡如果寄存器值为零则产生N1 个随机数放入寄存器中（2N1＝a），否则寄存器的值加上a，如寄存器的值为零则发送这个射频卡的ID 号，转3。
5. 如果1/b 个时隙后读写卡没有接到任何数据，则此时读写头判断总时隙是否满，是则结束，否则转6
6. 读写头发送减1 控制命令，每个射频卡接到此命令后，将其寄存器的值减1，如寄存器的值为零则发送这个射频卡的ID 号，如小于零则此射频卡不再激活，转3。
从步骤中可以看出射频卡需要实现的几个操作命令是：将卡的ID 号读入寄存器、产生随机数压入寄存器、对寄存器进行加减操作、判断是否为零，这些都是一些比较简单的命令可以快速的实现，且消耗小。
信道利用率是衡量一个防冲突算法效率的标准，其值是传输数据时总的时间除以整个识别过程所用的时间。如在本算法中产生的冲突次数为c，因冲突而增加的周期数为T，则期信道利用率Y 的计算公式为：
3.2 仿真分析
对上面的算法我们来进行模拟，模拟的过程是先产生一些射频卡的卡号，卡号是随机产生的，我们的任务就是识别这些随机产生的卡号。
假设需要识别的射频卡个数n 为16 个，射频卡的ID 号为64 位，需要识别的卡号只有后面15 位不同，前面的49 位相同，故产生的随机数的范围为：0～216-1。a 的值取4（即N1＝2），识别的个数n＝15，b＝10，样本数m＝10000，N 的值我们取2，3、4、5、6、7来进行对比，对产生的随机数允许重复。完全模拟整个算法过程，并记录产生的冲突的次数C 和增加的总周期数T，根据式3.1 即可计算出信道利用率的期望值。结果如表1。
从上面的模拟仿真中可以看出信道利用率还是挺高的，达到了60％~74％。与文献[7]中的基于后退式索引的二进制树形搜索反碰撞算法的信道利用率在50％左右相比，本文的方法不仅信道利用率比其高，而且不需要曼切斯特编码故更易于实现，响应更快速[7]。与文献[5]中提出的新颖的RFID 防冲突算法相比，因为考虑了射频卡的ID 值和减少了等待的时间，在识别物品个数稳定的情况下具有比其更好的性能。
4. 结论
本文提出了一种尽量减少等待时隙的提高RFID 防冲突效率的方法。这种方法是对以前两种方法的折中，在识别数量稳定的一些场合（比如机场的物件识别）等情况下具有很好的信道利用率，且能识别重复的ID。使本方法适应更多的场合也是以后研究发展的方向。
参考文献
[1] 徐丽香, 蓝运维. RFID 二进制搜索法防碰撞的实现[J].Microcontrollers &EmbeddedSystems,2006年第5 期
[2] 李兴鹤，胡咏梅，王华莲. 基于动态二进制的二叉树搜索结构RFID 反碰撞算法［J］. 山东科技,第19 卷第二期
[3] ISO18000-6A 标准:Information technology automatic identification and data capture techniques-Radio frequency identification for item management air interface-Part6:Parameters for air interface communications at 860-960MHz［S］
[4] ISO18000-6B 标准:Information technology automatic identification and data capture techniques-Radio frequency identification for item management air interface-Part 6:Parameters for air interface
communications at 860-960MHz［S］
[5] 张明，张建华, 徐国鑫, 张 平. 一种新颖的 RFID 防冲突算法［J］. 《电子技术应用》2006年第6期
[6] ISO18000-6C 标准:Information technology-Radio-frequency identification for item management-Part 6C:Parameters for air interface communications at 860 MHz to 960MHz. ［S］
[7] 徐松森，詹宜巨，彭卫东，赵振宇. 基于后退式索引的二进制树形搜索反碰撞算法及其实现［J］. 计算机工程与应用，2004 年16 期
射频识别技术RFID (Radio Frequency Identification)是目前国内外发展很快的一项新技术。该技术是采用先进的射频技术，实现对各类物体或设备标号的自动识别，从而对其进行管理。射频识别技术能无源，并快速地识别多个物体或设备，能应用于许多场合。随着RFID卡片端成本的不断降低以及体积的不断变小，其应用必将越来越多。在射频卡的识别中，需要解决的一个问题是冲突问题。当多个射频卡同时发送数据时就会产生信道冲突，使得读写头不能读出射频卡的信息。故防冲突算法一直是RFID 中重要研究内容之一。
2. 目前进展
目前的防冲突算法分两大类，一是基于曼切斯特编码的二进制搜索算法及其改进算法，二是基于随机数产生器的时隙算法及其改进算法，下面分别介绍。
2.1 二进制搜索算法及其改进算法
在二进制搜索算法中，射频卡的ID 号必须采用曼切斯特编码。曼切斯特码（Mancherster）可在多个射频卡同时响应时，译出错误位置，可以按位定出发生冲突的位置。根据冲突的位置，搜索射频卡[1]。二进制搜索算法只能识别ID 号唯一的情况。
改进的算法有动态二进制搜索算法，算法改进的地方是对没有发生冲突的ID 位只传送一次。这样就减少了重传的数据，提高了效率[1]。文献[2]中所提的基于动态二进制的二叉树搜索结构RFID 反碰撞算法是对二进制搜索算法的改进。它的思想是对每次识别的冲突位进行分类，分成0、1 两部分，从而形成一颗二叉树[2]，如图1。
时隙算法规定射频卡传送其ID 号所用的时间为一个时隙，如果每个射频卡在不同的时隙段发送其ID 号，就能避免冲突。算法的关键是怎样为不同的射频卡确定其所在的时隙，一般是采用随机数的策略。算法过程如图2。
3. 改进算法
通过对以前RFID 防冲突算法两类方法的分析与研究，结合这两种方法的优点，本文提出了一种新的算法。
3.1 算法介绍与分析
本文提出的算法是在时隙的基础上利用各个ID 号尾数不同的特点，同时结合随机数来实现防冲突的目的。对于多个需要识别的射频卡，考虑它的低N 位ID 号，产生2N 个时隙。各个射频卡在它的低N 位的ID 值所在时隙发送其ID 号。在一个时隙段，如果有两个以上的射频卡（具有相同低N 位ID 值的射频卡）发送数据，则产生冲突，此时产生随机数来区分；如果只有一个射频卡发送其数据，则可读出其ID；如果没有射频卡发送数据，则等待一个较短的时间发现没有数据，则取消这个时隙。总之算法的思想就是要尽量减少等待和冲突的时间，从而提高防冲突的效率。
算法步骤如下：
1. n 个射频卡进入读写范围，感应读写头发出的射频，获得能量，处于激活状态。
2. 读写头发送第一个控制命令，这个命令使得各个射频卡将它的ID 号的低N 位放入寄存器，如这N 位组成的值为零则发送这个射频卡的ID 号。
3. 如果只有一个射频卡发送其ID 则读写头读出此ID。此时读写头判断总时隙是否满，是则结束，否则转6。
4. 如果有多个射频卡发送其ID 则发生冲突，则要增加a 个时隙，读写头发送冲突控制命令，各个射频卡如果寄存器值为零则产生N1 个随机数放入寄存器中（2N1＝a），否则寄存器的值加上a，如寄存器的值为零则发送这个射频卡的ID 号，转3。
5. 如果1/b 个时隙后读写卡没有接到任何数据，则此时读写头判断总时隙是否满，是则结束，否则转6
6. 读写头发送减1 控制命令，每个射频卡接到此命令后，将其寄存器的值减1，如寄存器的值为零则发送这个射频卡的ID 号，如小于零则此射频卡不再激活，转3。
从步骤中可以看出射频卡需要实现的几个操作命令是：将卡的ID 号读入寄存器、产生随机数压入寄存器、对寄存器进行加减操作、判断是否为零，这些都是一些比较简单的命令可以快速的实现，且消耗小。
信道利用率是衡量一个防冲突算法效率的标准，其值是传输数据时总的时间除以整个识别过程所用的时间。如在本算法中产生的冲突次数为c，因冲突而增加的周期数为T，则期信道利用率Y 的计算公式为：
3.2 仿真分析
对上面的算法我们来进行模拟，模拟的过程是先产生一些射频卡的卡号，卡号是随机产生的，我们的任务就是识别这些随机产生的卡号。
假设需要识别的射频卡个数n 为16 个，射频卡的ID 号为64 位，需要识别的卡号只有后面15 位不同，前面的49 位相同，故产生的随机数的范围为：0～216-1。a 的值取4（即N1＝2），识别的个数n＝15，b＝10，样本数m＝10000，N 的值我们取2，3、4、5、6、7来进行对比，对产生的随机数允许重复。完全模拟整个算法过程，并记录产生的冲突的次数C 和增加的总周期数T，根据式3.1 即可计算出信道利用率的期望值。结果如表1。
从上面的模拟仿真中可以看出信道利用率还是挺高的，达到了60％~74％。与文献[7]中的基于后退式索引的二进制树形搜索反碰撞算法的信道利用率在50％左右相比，本文的方法不仅信道利用率比其高，而且不需要曼切斯特编码故更易于实现，响应更快速[7]。与文献[5]中提出的新颖的RFID 防冲突算法相比，因为考虑了射频卡的ID 值和减少了等待的时间，在识别物品个数稳定的情况下具有比其更好的性能。
4. 结论
本文提出了一种尽量减少等待时隙的提高RFID 防冲突效率的方法。这种方法是对以前两种方法的折中，在识别数量稳定的一些场合（比如机场的物件识别）等情况下具有很好的信道利用率，且能识别重复的ID。使本方法适应更多的场合也是以后研究发展的方向。
参考文献
[1] 徐丽香, 蓝运维. RFID 二进制搜索法防碰撞的实现[J].Microcontrollers &EmbeddedSystems,2006年第5 期
[2] 李兴鹤，胡咏梅，王华莲. 基于动态二进制的二叉树搜索结构RFID 反碰撞算法［J］. 山东科技,第19 卷第二期
[3] ISO18000-6A 标准:Information technology automatic identification and data capture techniques-Radio frequency identification for item management air interface-Part6:Parameters for air interface communications at 860-960MHz［S］
[4] ISO18000-6B 标准:Information technology automatic identification and data capture techniques-Radio frequency identification for item management air interface-Part 6:Parameters for air interface
communications at 860-960MHz［S］
[5] 张明，张建华, 徐国鑫, 张 平. 一种新颖的 RFID 防冲突算法［J］. 《电子技术应用》2006年第6期
[6] ISO18000-6C 标准:Information technology-Radio-frequency identification for item management-Part 6C:Parameters for air interface communications at 860 MHz to 960MHz. ［S］
[7] 徐松森，詹宜巨，彭卫东，赵振宇. 基于后退式索引的二进制树形搜索反碰撞算法及其实现［J］. 计算机工程与应用，2004 年16 期
