第八章RFID防碰撞技术课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 RFID防碰撞技术,快速、准确、有效的防碰撞问题解决方案对,RFID,技术的发展有着至关重要的作用。标签防碰撞算法就是要解决在读写器的有效通信范围内，多个标签如何同时与读写器进行通信的问题。在高频（,HF,）频段，标签的防碰撞算法一般采用,ALOHA,。在超高频（,UHF,）频段，主要采用二进制树型搜索算法。本章将重点介绍这两类算法及其扩展算法。,第八章 RFID防碰撞技术 快速、准确、有效的防碰撞问,1,8.1 RFID,系统中的碰撞与防碰撞,在,RFID,系统应用中，因为多个读写器或多个标签，造成的读写器之间或标签之间的相互干扰，统称为,碰撞,。,1,什么是碰撞,1,、多标签碰撞,2,、多读写器碰撞,2,碰撞的类型,8.1 RFID系统中的碰撞与防碰撞 在RFID系统,2,电子标签,1,电子标签,2,电子标签,4,电子标签,3,电子标签,5,（,1,）多读写器碰撞,电子标签1电子标签2电子标签4电子标签3电子标签5（1）多读,3,8.1 RFID,系统中的碰撞与防碰撞,多读写器碰撞,当相邻的读写器作用范围有重叠时，多个读写器同时读取同一个标签时可能会引起多读写器与标签之间的干扰。如图标签同时收到,3,个读写器的信号，标签无法正确解析读写器发来的查询信号。,读写器自身有能量供应，能进行较高复杂度的计算，所以读写器能检测到碰撞产生，并通过与其他读写器之间的交流互通来解决读写器的碰撞问题，如读写器调度算法和功率控制算法。,8.1 RFID系统中的碰撞与防碰撞多读写器碰撞,4,电子标签,1,电子标签,2,电子标签,4,电子标签,3,电子标签,5,（,2,）多标签碰撞,电子标签1电子标签2电子标签4电子标签3电子标签5（2）多标,5,8.1 RFID,系统中的碰撞与防碰撞,多标签碰撞,多标签碰撞,是指读写器同时收到多个标签信号而导致无法正确读取标签信息的问题。如图读写器发出识别命令后，在标签应答过程中可能会两个或者多个标签同一时刻应答，或一个标签还没有完成应答时其他标签就做出应答。它会使得标签之间的信号互相干扰，从而造成标签无法被正常读取。,本章后续讨论的防碰撞都是针对多标签防碰撞。,8.1 RFID系统中的碰撞与防碰撞多标签碰撞,6,如何解决碰撞的问题呢？,如何解决碰撞的问题呢？,7,无线通信技术中，通信碰撞的四种解决防碰撞方法：,空分多址,(SDMA),频分多址,(FDMA),码分多址,(CDMA),时分多址,(TDMA),8.1 RFID系统中的碰撞与防碰撞,无线通信技术中，通信碰撞的四种解决防碰撞方法：8.1 RF,8,（,1,）空分多址,SDMA,法,Reader,Tag,Tag,Tag,1,、自适应,SDMA,，电子控制定向天线，天线的方向直接对准某个标签,2,、减少单个读写器的作用范围,3,、,缺点,是天线系统复杂，会大幅度提高成本。,（1）空分多址SDMA法ReaderTagTagTag1、自,9,读,写,器,Tag1,Tag3,Tag5,Tag4,Tag2,阅读器广播命令,阅读器读写区域,f,1,f,2,f,3,f,4,f,5,（,2,）频分多址,FDMA,法,1,、,RFID,系统把不同载波频率的传输通道分别提供给电子标签用户,2,、缺点是导致读写器和标签成本要求较高。因此在,RFID,应用中，频分多路法很少使用。,读Tag1Tag3Tag5Tag4Tag2阅读器广播命令阅读,10,不同用户传输信息所用的信号不是靠频率不同或时隙不同来区分，而是,用各自不同的编码序列来区分,，或者说，靠信号的不同波形来区分。如果从频域或时域来观察，多个,CDMA,信号是互相重叠的。,CDMA,是利用不同的码序列分割成不同信道的多址技术 。,CDMA,的频带利用率低，信道容量较小，地址码选择较难、接收时地址码捕获时间较长，其通信频带和技术复杂性在,RFID,系统中难以应用。,（,3,）,码分多址,(CDMA),（3）码分多址(CDMA),11,（,4,）时间分割,TDMA,a,b,c,a,b,c,Reader,Tag,1,Tag,2,Tag,3,a,a,b,b,c,c,TDMA,是把整个可供使用的信道容量按时间分配给多个同户的技术。,（4）时间分割TDMAabcabcReaderTag1,12,8.1 RFID,系统中的碰撞与防碰撞,RFID,系统中防碰撞算法分类,电子标签的低功耗、低存储能力和有限的计算能力等限制，导,致许多成熟的防碰撞算法（如空分多路法）不能直接在,RFID,系统中,应用。这些限制可以归纳为：,（,1,）无源标签没有内置电源，标签的能量来自于读写器，因此算,法在执行的过程中，标签功耗要求尽量低；,（,2,）,RFID,系统的通信带宽有限，因此防碰撞算法应尽量减少读写,器和标签之间传输信息的比特数目；,（,3,）标签不具备检测冲突的功能而且标签间不能相互通信，因此,冲突判决需要读写器来实现；,（,4,）标签的存储和计算能力有限，这就要求防碰撞协议尽可能简,单，标签端的设计不能太复杂。,8.1 RFID系统中的碰撞与防碰撞RFID系统中防碰撞算,13,8.1 RFID,系统中的碰撞与防碰撞,2.RFID,中防碰撞算法分类,8.1 RFID系统中的碰撞与防碰撞2.RFID中防碰撞算,14,8.1 RFID,系统中的碰撞与防碰撞,标签防碰撞算法,RFID,系统的标签防碰撞算法大多采用时分多路法，该方法可分,为非确定性算法和确定性算法。,非确定性算法,也称标签控制法，在该方法中，读写器没有对数,据传输进行控制，标签的工作是非同步的，标签获得处理的时间不,确定，因此标签存在“饥饿”问题。,ALOHA,算法,是一种典型的非确定性,算法，实现简单，广泛用于解决标签的碰撞问题。,确定性算法,也称读写器控制法，由读写器观察控制所有标签。,按照规定算法，在读写器作用范围内，首先选中一个标签，在同一,时间内读写器与一个标签建立通信关系。,二进制树型搜索算法,是典,型确定性算法，该类算法比较复杂，识别时间较长，但无标签饥饿,问题。,8.1 RFID系统中的碰撞与防碰撞标签防碰撞算法,15,8.2 ALOHA算法,ALOHA,算法,是一种随机接入方法，其基本思想是采取标签先发言的方式，当标签进入读写器的识别区域内时就自动向读写器发送其自身的,ID,号，在标签发送数据的过程中，若有其他标签也在发送数据，将会发生信号重叠，从而导致冲突。读写器检测接收到的信号有无冲突，一旦发生冲突，读写器就发送命令让标签停止发送，随机等待一段时间后再重新发送以减少冲突。,各种,ALOHA,算法：,纯,ALOHA,算法、时隙,ALOHA,算法、帧时隙,ALOHA,算法、动态帧时隙,ALOHA,算法,。,8.2 ALOHA算法 ALOHA算法是一种随机接入,16,ALOHA,算法的模型图,ALOHA算法的模型,17,纯,ALOHA,算法,思想：只要用户有数据要发送，就尽管让他们发送,纯,ALOHA,算法的标签读取过程：,（,1,）各个标签随机的在某时间点上发送信息。,（,2,）阅读器检测收到的信息，判断是成功接收或者碰撞。,（,3,）若判断发生碰撞，则标签随机等待一段时间再重新发送信息。,纯,ALOHA,存在的问题：,（,1,）错误判决。即对同一个标签，如果连续多次发生碰撞，则将导致阅读器出现错误判断，认为标签不在阅读器作用范围内。,（,2,）数据帧的发送过程中发生碰撞的概率很大。过多的碰撞导致吞吐量下降系统性能降低。,解决方向：,减小碰撞发生次数,缩短重发延时,存在的问题？,存在的问题？,18,吞吐率,S-,代表有效传输的实际总数据率，即在观察时间,T0,内标签成功通信的平均次数,输入负载,G-,发送的总数据率，即观察时间,T0,内标签的平均到达次数,S=G*P,e,其中,P,e,是到达的标签能成功完成通信的概率,性能分析,由概率论知识：,P,e,=e,-2G,所以：纯,ALOHA,算法的吞吐率为：,S=G*e,-2G,吞吐率S-代表有效传输的实际总数据率，即在观察时间T0内,19,当输入负载,G=0.5,时，系统的吞吐率达到最大值,0.184,。由于纯,ALOHA,算法中存在碰撞概率较大，在实际中，该算法仅适于只读型的标签，即阅读器只负责接收标签发射的信号，标签只负责向阅读器发射信号的情况。,当输入负载G=0.5时，系统的吞吐率达到最大值0.,20,时隙,ALOHA,算法,在,ALOHA,算法的基础上把时间分成多个离散时隙,(slot),，并且每个时隙长度要大于标签回复的数据长度，标签只能在每个时隙内发送数据。每个时隙存在：,a,空闲时隙：此时隙内没有标签发送,b,成功识别时隙：仅一个标签发送且被正确识别,c,碰撞时隙：多个标签发送，产生碰撞,时隙ALOHA算法,21,时隙,ALOHA,算法的吞吐率为：,S=G*e,-G,当输入负载,G=1,时，系统的吞吐量达到最大值,0.368,，避免了纯,ALOHA,算法中的部分碰撞，提高了信道的利用率。,需要一个同步时钟以使阅读器阅读区域内的所有标签的时隙同步。,时隙,ALOHA,算法示意图,时隙ALOHA算法的吞吐率为：S=G*e-G时隙ALOHA算,22,Frame Slotted Aloha(FSA),将,N,个时隙组成一帧，一帧中包含的时隙数固定，标签随机选择,N,个时隙中的一个与阅读器通信，一旦碰撞则等待下一帧，重新选择时隙重发信息。,优点：简化了时隙,Aloha,的随机退避机制。,缺点：当标签数远大于,N,时，出现“,饿死现象,”；,当标签数远小于,N,时，较多,时隙空闲,，产生浪费。,固定帧时隙,Aloha,运用于,RFID,系统示意图,帧时隙,ALOHA,算法,Frame Slotted Aloha(FSA) 将N个时隙,23,动态帧时隙,ALOHA,算法（,DFSA,）,动态帧时隙ALOHA算法（DFSA）,24,Downlink,(,Reader-Tag),Request,Frame 1,Request,Frame 2,Request,Frame 3,Request,Frame 4,Uplink,(Tag-Reader),Tag 1,1,Tag 2,2,Tag 3,3,Tag 4,4,Tag 5,5,Tag 6,6,Tag 7,7,Tag 8,8,Tag 9,9,Tag 10,10,Tag 11,11,Tag 12,12,Tag13,13,动态帧时隙,Aloha,运用于,RFID,系统示意图,当系统待识别标签数较多时，动态增加帧长，可以降低时隙碰撞率，提高系统性能；,当系统待识别标签数较少时，动态减少帧长，可以降低空闲时隙比率，提高时隙利用率，提高系统性能；,DownlinkRequestFrame 1RequestF,25,8.3 二进制树型搜索算法,二进制树型搜索算法,由读写器控制,，基本思想是不断的将导致,碰撞的电子标签进行划分，缩小下一步搜索的标签数量，直到只有,一个电子标签进行回应。,1,冲突位检测,实现该算法系统的必要前提是能够辨认出在读写器中数据冲突,位的准确位置。为此，必须有合适的位编码法。如图对,NRZ,编码和曼,彻斯特编码的冲突状况作一比较。,8.3 二进制树型搜索算法 二进制树型搜索算法由读,26,8.3 二进制树型搜索算法,1,）,NRZ,编码,某位之值是在一个位窗（,t,BIT,）内由传输通路的静态电平表,示，这种逻辑“,1”,为 “高”电平，逻辑“,0”,为 “低”电平。如果两个,电子标签之一发送了副载波信号，那么，这个信号由读写器译码为,“高”电平，就被认定为逻辑“,1”,。但读写器不能确定读入的某位究竟,是若干个电子标签发送的数据相互重叠的结果，还是某个电子标签,单独发送的信号，见下页中图（,a,）。,2,）曼彻斯特编码,某位之值是在一个位窗（,tBIT,）内由电平的改变（上升,/,下降沿）,表示。逻辑“,0”,编码为上升沿，逻辑“”编码为下降沿。如果两个或,多个电子标签同时发送的数位有不同值，则接收的上升沿和下降沿,互相抵消，“没有变化”的状态是不允许的，将作为错误被识别。用,这种方法可以按位追溯跟踪冲突的出现，见下页中图（,b,）。,8.3 二进制树型搜索算法1）NRZ编码,27,8.3 二进制树型搜索算法,采用,NRZ,编码和曼彻斯特编码的冲突状况（曼彻斯特编码能够按,位识别出冲突）示意图。因此，选用曼彻斯特编码可实现“二进制树,型搜索”算法。,8.3 二进制树型搜索算法 采用NRZ编码和曼彻斯特,28,8.3 二进制树型搜索算法,2.,二进制树型搜索算法过程,二进制树型搜索算法的模型如图所示，其基本思想是将处于冲,突的标签分成左右两个子集,0,和,1,，先查询子集,0,，若没有冲突，则正,确识别标签，若仍有冲突则再分裂，把子集,0,分成,00,和,01,两个子集，,依次类推，直到识别出子集,0,中所有标签，再按此步骤查询子集,1,。,可见，标签的序列号是处理碰撞的基础。,8.3 二进制树型搜索算法2.二进制树型搜索算法过程,29,8.3 二进制树型搜索算法,二进制树型搜索算法的实现步骤如下：,（,1,）读写器广播发送最大序列号查询条件,Q,，其作用范围内的标,签在同一时刻传输它们的序列号至读写器。,（,2,）读写器对收到的标签进行响应，如果出现不一致的现象（即,有的序列号该位为,0,，而有的序列号该位为,1,），则可判断有碰撞。,（,3,）确定有碰撞后，把有不一致位的数最高位置,0,再输出查询条,件,Q,，依次排除序列号大于,Q,的标签。,（,4,）识别出序列号最小的标签后，对其进行数据操作，然后使其,进入“无声”状态，则对读写器发送的查询命令不进行响应。,（,5,）重复步骤,1,，选出序列号倒数第二的标签。,（,6,）多次循环完后完成所有标签的识别。,8.3 二进制树型搜索算法二进制树型搜索算法的实现步骤如下,30,8.3 二进制树型搜索算法,为了实现这种算法需要一组命令。这组命令可由电子标签进,行处理（见下表），每个电子标签拥有一个唯一的序列号（,SNR,）。,REQUEST,（,SNR,）,请求（序列号）,此命令发送一序列号作为参数给电子标签。电子标签把自己的序列号与接收的序列号,进行,比较,，,如果小于或相等，则此电子标签回送其序列号给读写器。这样就可以缩小预选的电子标签的范围,SELECT,（,SNR,）,选择（序列号）,用某个（事先确定的）序列号作为参数发送给电子标签,，,具有相同序列号的电子标签将以此作为执行其他命令（如读出和写入数据）的切入开关，即选择这个电子标签,，,具有其他序列号的电子标签只对,REQUEST,命令应答,READ-DATA,读出数据,选中的电子标签将存储的数据发送给读写器（在实际的系统中，还有鉴别或写入等命令,等,）,UNSELECT,退出选择,取消一个事先选中的电子标签，电子标签进入,“,无声,”,状态。在这种状态,下，,电子标签完全是非激活的，对收到的,REQUEST,命令不作应答。为了重新激活电子标签，必须暂时离开读写器的作用范围（等于没有供应电压），以执行复位,8.3 二进制树型搜索算法 为了实现这种算法需要一组,31,范例,A:,101,00111,B:,101,10101,C,:,101,01111,D,:,101,11101,R,:,R,:,送,REQUEST,（）命令，要求区域内所有标签应答，根据曼彻斯特编码，解码数据为,101?1?1,发生碰撞，算法做下如下，,将碰撞的最高置,0,，其它碰撞位置,1,。得下次的,REQUEST(10101111),?,?,R,表示阅读器,范例A:10100111B:10110101C:101011,32,Improved Anti-collision Algorithm,搜寻过程,第一次搜寻,第二次搜寻,第三次搜寻,第四次搜寻,第五次搜寻,发送序号,接收序号,TagA,Tag,B,Tag,C,Tag,D,101?1?1,1010?111,识别,TagA,101?1?1,识别,TagB,Improved Anti-collision Algori,33,Improved Anti-collision Algorithm,搜寻过程,第六次搜寻,第七次搜寻,第八次搜寻,第九次搜寻,第十次搜寻,发送序号,接收序号,TagA,Tag,B,Tag,C,Tag,D,1011?101,识别,TagC,识别,TagD,Improved Anti-collision Algori,34,8.3 二进制树型搜索算法,为了从较大量的电子标签中搜索出某个唯一的电子标签，需要,多次迭代。其平均次数,L,取决于读写器作用范围内的电子标签总数,N,，即,可以看出，利用二进制树型搜索算法可以快速简单地解决碰撞,问题。如果只有一个电子标签在读写器作用范围内，在这种情况下,不会出现冲突，只需要一次迭代就可发现电子标签的序列号。如果,有一个以上的电子标签处在读写器作用范围内，那么迭代的平均数,增加很快。,8.3 二进制树型搜索算法 为了从较大量的电子标签中,35,练习,P132 8-5,练习,36,8.3 二进制树型搜索算法,动态二进制树型搜索,二进制树型搜索算法为了选择一个电子标签传输大量多余的数据。如图用,X,表示最高冲突位的位置，在前述的迭代的最高冲突位上出现了位冲突，即可得出：, 命令中（,X1,）,0,各位不包含给电子标签的补充信息，因为（,X1,）,0,各位总是被置为“,1”,的。, 电子标签序列号的,N,X,各位不包含给读写器的补充信息，因为,N,X,这些位是已知且给定的。,在搜索一个,4,字节序列号时，读写器的命令（第,n,次迭代）和电子标签的应答,8.3 二进制树型搜索算法动态二进制树型搜索 在搜索一个4,37,8.3 二进制树型搜索算法,动态二进制树型搜索算法的工作步骤如下：,（,1,）读写器第一次发出一个完整的查询条件,Q,，长度为,N,，每个位,上的码全为,1,，让所有标签都返回各自的序列号。,（,2,）读写器判断有碰撞的最高位,X,，将该位置,0,。然后传输,N,X,位,的数据。标签接到这个查询信号后检查自己的序列号是否匹配，如,果匹配则回传自己序列号的,X,1,0,位。,（,3,）读写器检测第二次返回的最高碰撞位数,X,是否小于前一次检,测回传的次高碰撞位数，若不是，则直接把该位置“,0”,；若是，则要,把前一次检测的次高位也置为“,0”,。然后广播新的查询信息。发出查,询条件的位数为,N,X,，满足查询条件的电子标签回传的信号只是序,列号中最高碰撞位后的数，即,X,1,0,位。若标签返回信号没有发生,碰撞，则对该序列号标签进行读,/,写，然后使其进入“无声”状态。,（,4,）重复步骤（,3,），多次重复后可完成电子标签交换数据工作。,8.3 二进制树型搜索算法动态二进制树型搜索算法的工作步骤,38,8.3 二进制树型搜索算法,如图为动态的二进制树型搜索算法过程。,NVB,表明请求命令的有效位数。电子标签返回的序列号只是除了这些有效位之后的部分，避免序列号中多余部分的传输，要传输的数据数量和所需时间的减少可达,50%,。,8.3 二进制树型搜索算法 如图为动态的二进制树型搜索算法,39,8.3 二进制树型搜索算法,基于随机数和时隙的二进制树搜索,该算法采用递归的工作方式，遇到碰撞就进行分支，成为两个,子集。这些分支越来越小，直到最后分支下面只有一个信息包或者,为空。分支的方法就如同抛一枚硬币一样，将这些信息包随机地分,为两个分支，在第一个分支里，是“抛正面”（取值为,0,）的信息包。,在接下来的时隙内，主要解决这些信息包所发生的碰撞。如果再次,发生碰撞，则继续再随机地分为两个分支。该过程不断重复，直到,某个时隙为空或者成功完成一次数据传输，然后返回上一个分支。,这个过程遵循“先入后出” 的原则，等到所有第一个分支的信息包都,成功传输后，再来传输第二个分支，也就是“抛反面”（取值为,1,）的,信息包。,此算法不要求电子标签需准确同步,。,这种算法称为,树型搜索算法,，每次分割使搜索树增加一层分支。,8.3 二进制树型搜索算法基于随机数和时隙的二进制树搜索,40,8.3 二进制树型搜索算法,如图所示为四层（,m,=4,）树算法的原理示意图。每个顶点表示一,个时隙，每个顶点为后面接着的过程产生子集。如果该顶点包含的,信息包个数大于或等于,2,，那么就产生碰撞，于是就产生了两个新的,分支。算法从树的根部开始，在解决这些碰撞的过程中，假设没有,新的信息包达到。,8.3 二进制树型搜索算法 如图所示为四层（m=4）,41,8.3 二进制树型搜索算法,如上图所示，第一次碰撞在时隙,1,发生，开始并不知道一共有多,少个信息包产生碰撞，每个信息包好像抛硬币一样，抛,0,的在时隙,2,内传输。第二次发生碰撞是在时隙,2,内，在本例中，两个信息包都是,抛,1,，以致时隙,3,为空。在时隙,4,内，时隙,2,中抛,1,的两个信息包又一次,发生碰撞和分支，抛,0,的信息包在时隙,5,内成功传输，抛,1,的信息包在,时隙,6,内成功传输，这样所有在时隙,1,内抛,0,的信息包之间的碰撞得以,解决。在树根时抛,1,的信息包在时隙,7,内开始发送信息，新的碰撞发,生。这里假设在树根时抛,1,的信息包有两个，而且由于两个都是抛,0,，所以在时隙,8,内再次发生碰撞并再一次进行分割，抛,0,的在时隙,9,内传输，抛,1,的在时隙,10,内传输。在时隙,7,内抛,1,的实际上没有信息,包，所以时隙,11,为空闲。,8.3 二进制树型搜索算法 如上图所示，第一次碰撞在,42,8.3 二进制树型搜索算法,二进制树型算法是在碰撞发生后解决碰撞问题的一种算法。,需要指出的是，当碰撞正在进行时，新加入这个系统的信息包禁止,传输信息，直到该系统的碰撞问题得以解决，并且所有信息包成功,发送完后，才能进行新信息包的传输。例如，在上例中，在时隙,1,到,时隙,11,之间，新加入系统的信息包，只有在时隙,12,才开始传输。,二进制树型算法也可按照堆栈的理论进行描述。在每个时隙，,信息包堆栈不断地弹出与压栈，在栈顶的信息包最先传输。当碰撞,发生时，先把抛,1,的信息包压栈，再把抛,0,的信息包压栈，这样抛,0,的,信息包就处在栈顶，在下个时隙弹出即能进行传输。当完成一次成,功传输或者出现一次空闲时隙的时候，栈顶的信息包被继续弹出，,依次进行发送。显然，当堆栈为空时，即碰撞问题得以解决，所有,信息包成功传输。接下来，把新到达这个系统的信息包压栈，操作,过程同前面的一样。,8.3 二进制树型搜索算法 二进制树型算法是在碰撞发,43,第八章RFID防碰撞技术课件,44,8.4 本章小结,本章介绍了,RFID,中的关键技术,防碰撞技术。多个标签同时,向读写器发送数据时,将会产生碰撞而导致读写器无法正确识读这些,标签。,无线通信领域中防碰撞算法主要包括,TDMA,、,CDMA,、,FDMA,和,SDMA,。,RFID,系统的防碰撞算法基本都属于,TDMA,，主要包括,ALOHA,算法和二进,制树型搜索算法。其中，,ALOHA,算法,是一种非确定方法，由电子标签,控制发送时间，一般用于高频,RFID,系统。,二进制树型搜索算法,一般,是由读写器控制的确定性方法，主要用于超高频,RFID,系统。,8.4 本章小结 本章介绍了RFID中的关键技术,45,作业：,1,、,P132 1,、,2,、,3,、,4,、,5,2,、下载,ISO 14443,协议，并阅读其第,3,部分,作业：,46,