一种简单高效的RFID-防冲突算法

防冲突算法柳本金，丁海健北京邮电大学计算机科学与技术学院，北京(100876)E-mail：[e-mail]摘要：本文在分析研究以往两类RFID防冲突算法的基础上，结合两者的优点提出了一种基于时隙的改进算法。通过仿真与其它防冲突算法相比在识别数量稳定的情况下，本文提出的算法具有更好的效果。关键词：RFID，防冲突算法，射频卡识别中图分类号：TN9111.引言射频识别技术RFID(RadioFrequencyIdentification)是目前国内外发展很快的一项新技术。该技术是采用先进的射频技术，实现对各类物体或设备标号的自动识别，从而对其进行管理。射频识别技术能无源，并快速地识别多个物体或设备，能应用于许多场合。随着RFID卡片端成本的不断降低以及体积的不断变小，其应用必将越来越多。在射频卡的识别中，需要解决的一个问题是冲突问题。当多个射频卡同时发送数据时就会产生信道冲突，使得读写头不能读出射频卡的信息。故防冲突算法一直是RFID中重要研究内容之一。2.目前进展目前的防冲突算法分两大类，一是基于曼切斯特编码的二进制搜索算法及其改进算法，二是基于随机数产生器的时隙算法及其改进算法，下面分别介绍。2.1二进制搜索算法及其改进算法在二进制搜索算法中，射频卡的ID号必须采用曼切斯特编码。曼切斯特码（Mancherster）可在多个射频卡同时响应时，译出错误位置，可以按位定出发生冲突的位置。根据冲突的位置，搜索射频卡[1]。二进制搜索算法只能识别ID号唯一的情况。图1基于动态二进制搜索的二叉树搜索结构树改进的算法有动态二进制搜索算法，算法改进的地方是对没有发生冲突的ID位只传送一次。这样就减少了重传的数据，提高了效率[1]。文献[2]中所提的基于动态二进制的二叉树搜索结构RFID反碰撞算法是对二进制搜索算法的改进。它的思想是对每次识别的冲突位进行分类，分成0、1两部分，从而形成一颗二叉树[2]，如图1。2.2时隙算法及其改进算法时隙算法规定射频卡传送其ID号所用的时间为一个时隙，如果每个射频卡在不同的时隙段发送其ID号，就能避免冲突。算法的关键是怎样为不同的射频卡确定其所在的时隙，一般是采用随机数的策略。算法过程如图2。图2时隙算法流程图ISO18000-6A[3]和18000-6B[4]规定了这种时隙的标准算法。目前国内比较好的算法是文献[5]提出的一种新颖的RFID防冲突算法，算法基于随机数产生时隙，并分群快速识别多个射频卡[5]。国外比较好的算法是文献[6]中一种改进的算法，已在欧美得到实用。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个时隙后读写卡没有接到任何数据，则此时读写头判断总时隙是否满，是则结束，否则转66.读写头发送减1控制命令，每个射频卡接到此命令后，将其寄存器的值减1，如寄存器的值为零则发送这个射频卡的ID号，如小于零则此射频卡不再激活，转3。从步骤中可以看出射频卡需要实现的几个操作命令是：将卡的ID号读入寄存器、产生随机数压入寄存器、对寄存器进行加减操作、判断是否为零，这些都是一些比较简单的命令可以快速的实现，且消耗小。信道利用率是衡量一个防冲突算法效率的标准，其值是传输数据时总的时间除以整个识别过程所用的时间。如在本算法中产生的冲突次数为c，因冲突而增加的周期数为T，则期信道利用率Y的计算公式为：Ybn2TnnN−++=……………………………3.1在式3.1中，需要权衡的是N的值。怎样对N取值才能更大的发挥算法的优点？下面对其进行仿真并分析。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。表1仿真的结果数据N的取值234567总冲突次数C4660635902227721275966103297增加的总周期数T17314414128678184477082618813188平均信道利用率Y0.65250.69230.74350.72330.61510.4499算法中N的取值是关键，直接影响到算法的效率。从图3中我们可以看出N的值取得使之2N于识别的个数附近。当然N的值可以变换以适应不同的场合，但是一般读写头读取射频卡的时间固定，故N的值一般也是固定，这样也简化了射频卡的逻辑处理，从而降低了功耗。的关系从上面的模拟仿真中可以看出信道利用率还是挺高的，达到了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标准:Informationtechnologyautomaticidentificationanddatacapturetechniques-Radiofrequencyidentificationforitemmanagementairinterface-Part6:Parametersforairinterfacecommunicationsat860-960MHz［S］[4]ISO18000-6B标准:Informationtechnologyautomaticidentificationanddatacapturetechniques-Radiofrequencyidentificationforitemmanagementairinterface-Part6:Parametersforairinterfacecommunicationsat860-960MHz［S］[5]张明，张建华,徐国鑫,张平.一种新颖的RFID防冲突算法［J］.《电子技术应用》2006年第6期[6]ISO18000-6C标准:Informationtechnology-Radio-frequencyidentificationforitemmanagement-Part6C:Parametersforairinterfacecommunicationsat860MHzto960MHz.［S］[7]徐松森，詹宜巨，彭卫东，赵振宇.基于后退式索引的二进制树形搜索反碰撞算法及其实现［J］.计算机工程与应用，2004年16期(100876)AbstractInthispaper,twopreviousanticollisionalgorithmsforRFIDarestudied,andanewbetteralgorithmbasedontimeslotandcombinedwiththeadvantagesofthetwoalgorithmsisproposed.Throughsimulation,thismethodisbetterthanothermethodsinthesituationthatthenumbersofRadioFrequencyCardsarestable.Keywords:RFID,Anticollisionalgorithm,RadioFrequencyIdentification