RFID防碰撞技术PPT学习课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章,RFID,防碰撞技术,快速、准确、有效的防碰撞问题解决方案对,RFID,技术的发展有着至关重要的作用。标签防碰撞算法就是要解决在读写器的有效通信范围内，多个标签如何同时与读写器进行通信的问题。在高频（,HF,）频段，标签的防碰撞算法一般采用,ALOHA,。在超高频（,UHF,）频段，主要采用二进制树型搜索算法。本章将重点介绍这两类算法及其扩展算法。,1,8.1 RFID,系统中的碰撞与防碰撞,RFID,系统中的碰撞,RFID,系统经常会出现多个读写器以及多个标签的应用场合，从而,导致标签之间或读写器之间的相互干扰，这种干扰称为,碰撞,，也称,为冲突。,RFID,系统存在两类碰撞问题：,（,1,）一类称为,多标签碰撞问题,，即多个标签与同一个读写器同,时通信时产生的碰撞；,（,2,）另一类称为,多读写器碰撞问题,，即相邻的读写器在其信号,交叠区域内产生干扰，导致读写器的阅读范围减小，甚至无法读取,标签。,2,8.1 RFID,系统中的碰撞与防碰撞,1.,多读写器碰撞,当相邻的读写器作用范围有重叠时，多个读写器同时读取同一,个标签时可能会引起多读写器与标签之间的干扰。如图标签同时收,到,3,个读写器的信号，标签无法正确解析读写器发来的查询信号。,读写器自身有能量供应，能进行较高复杂度的计算，所以读写,器能检测到碰撞产生，并通过与其他读写器之间的交流互通来解决,读写器的碰撞问题，如读写器调度算法和功率控制算法。,3,8.1 RFID,系统中的碰撞与防碰撞,2.,多标签碰撞,多标签碰撞,是指读写器同时收到多个标签信号而导致无法正确,读取标签信息的问题。如图读写器发出识别命令后，在标签应答过,程中可能会两个或者多个标签同一时刻应答，或一个标签还没有完,成应答时其他标签就做出应答。它会使得标签之间的信号互相干,扰，从而造成标签无法被正常读取。本章后续讨论的防碰撞都是针,对多标签防碰撞。,4,8.1 RFID,系统中的碰撞与防碰撞,RFID,系统中防碰撞算法分类,电子标签的低功耗、低存储能力和有限的计算能力等限制，导,致许多成熟的防碰撞算法（如空分多路法）不能直接在,RFID,系统中,应用。这些限制可以归纳为：,（,1,）无源标签没有内置电源，标签的能量来自于读写器，因此算,法在执行的过程中，标签功耗要求尽量低；,（,2,）,RFID,系统的通信带宽有限，因此防碰撞算法应尽量减少读写,器和标签之间传输信息的比特数目；,（,3,）标签不具备检测冲突的功能而且标签间不能相互通信，因此,冲突判决需要读写器来实现；,（,4,）标签的存储和计算能力有限，这就要求防碰撞协议尽可能简,单，标签端的设计不能太复杂。,5,8.1 RFID,系统中的碰撞与防碰撞,1.,无线通信中的防碰撞方法,解决防碰撞的方法主要包括空分多路（,SDMA,）、频分多路法,（,FDMA,）、码分多路法（,CDMA,）和时分多路法（,TDMA,）。,1,）空分多路法,空分多路法,（,SDMA,）是在分离的空间范围内实现多个目标识别。一种实现方法是将读写器和天线之间的作用距离按空间区域进行划分，把读写器和天线安置在一个天线阵列中。当标签进入这个天线阵列的覆盖范围后，与其距离最近的读写器对该标签进行识别。由于每个天线的覆盖范围较小，相邻的读写器识别范围内的标签同样可以进行识别而不受相邻读写器的干扰，如果多个标签根据在天线阵列中的空间位置的不同，可以同时被识别。,另一种实现方法是读写器利用相控阵天线，让天线的方向性图对准单独的标签，标签根据其在读写器作用范围内的角度位置不同而区别开来。,空分多路法的,缺点,是天线系统复杂，会大幅度提高成本。,6,8.1 RFID,系统中的碰撞与防碰撞,2,）频分多路法,频分多路法,（,FDMA,）是把若干个使用不同载波频率的调制信号,在同时供通信用户使用的信道上进行传输的技术。通常情况下，,RFID,系统的前向链路（从读写器到标签）频率是固定的，用于能量,的供应和数据的传输。对于反向链路，不同标签采用不同频率的载,波进行数据调制，信号之间不会产生干扰，读写器对接收到的不同,频率的信号进行分离，从而实现对不同标签的识别。,频分多路法的缺点是导致读写器和标签成本要求较高。因此在,RFID,应用中，频分多路法很少使用。,7,8.1 RFID,系统中的碰撞与防碰撞,3,）码分多路法,码分多路法（,CDMA,）是基于扩频通信技术发展起来的。,扩频技术,包含扩频与多址两个基本概念。,扩频,目的是扩展信息,带宽，即把需发送的具有一定信号带宽的信息数据，用一个带宽远,大于其信号带宽的伪随机码进行调制，使原来的信息数据的带宽被,扩展，最后通过载波调制发送出去。解扩是指在接收端采用一致的,伪随机码，与接收到的宽带信号作相关处理，把宽带信号转换成原,来的信息。,多址,是给每个用户分配一个地址码，码型互不重叠。,码分多路法具有抗干扰性好，保密安全性高，信道利用率高等,优点。但是该技术也存在诸多缺点，如频带利用率低、信道容量,小，伪随机码的产生和选择较难，接收时地址码捕获时间长等，所,以该方法很难应用于实际的,RFID,系统中。,8,8.1 RFID,系统中的碰撞与防碰撞,4,）时分多路法,时分多路法（,TDMA,）是把整个可供使用的通路容量按时间分配,给多个用户的技术。,时分多路复用,是按传输信号的时间进行分割的，它使不同的信,号在不同的时间内传输，将整个传输时间分为许多时间间隔，每个,时间片被一路信号占用。,TDMA,就是通过在时间上交叉发送每一路信号的一部分来实现一,条电路传输多路信号的。电路上每一短暂时刻只有一路信号存在。,因为数字信号是有限个离散值，所以时分多路复用技术广泛应用于,包括计算机网络在内的数字通信系统。,9,8.1 RFID,系统中的碰撞与防碰撞,2.RFID,中防碰撞算法分类,10,8.1 RFID,系统中的碰撞与防碰撞,标签防碰撞算法,RFID,系统的标签防碰撞算法大多采用时分多路法，该方法可分,为非确定性算法和确定性算法。,非确定性算法,也称标签控制法，在该方法中，读写器没有对数,据传输进行控制，标签的工作是非同步的，标签获得处理的时间不,确定，因此标签存在,“,饥饿,”,问题。,ALOHA,算法,是一种典型的非确定性,算法，实现简单，广泛用于解决标签的碰撞问题。,确定性算法,也称读写器控制法，由读写器观察控制所有标签。,按照规定算法，在读写器作用范围内，首先选中一个标签，在同一,时间内读写器与一个标签建立通信关系。,二进制树型搜索算法,是典,型确定性算法，该类算法比较复杂，识别时间较长，但无标签饥饿,问题。,11,8.2 ALOHA,算法,ALOHA,算法,是一种随机接入方法，其基本思想是采取标签先发言,的方式，当标签进入读写器的识别区域内时就自动向读写器发送其,自身的,ID,号，在标签发送数据的过程中，若有其他标签也在发送数,据，将会发生信号重叠，从而导致冲突。读写器检测接收到的信号,有无冲突，一旦发生冲突，读写器就发送命令让标签停止发送，随,机等待一段时间后再重新发送以减少冲突。,12,8.2 ALOHA,算法,纯,ALOHA,算法,在纯,ALOHA,算法中，若读写器检测出信号存在相互干扰，读写器,就会以向电子标签发出命令，令其停止向读写器传输信号；电子标,签在接收到命令信号之后，就会停止发送信息，并会在接下来的一,个随机时间段内进入到待命状态，只有当该时间段过去后，才会重,新向读写器发送信息。各个电子标签待命时间片段长度是随机的，,再次向读写器发送信号的时间也不相同，这样减少碰撞的可能性。,当读写器成功识别某一个标签后，就会立即对该标签下达命令,使之进入到休眠的状态。而其他标签则会一直对读写器所发出命令,进行响应，并重复发送信息给读写器，当标签被识别后，就会一一,进入到休眠状态，直到读写器识别出所有在其工作区内的标签后，,算法过程才结束。,13,8.2 ALOHA,算法,纯,ALOHA,算法,纯,ALOHA,算法中的信号碰撞分两种情况：,（,1,）一种是信号部分碰撞，即信号的一部分发生了冲突；,（,2,）一种则是信号的完全碰撞，是指数据完全发生了冲突。,如图所示，,发生冲突的数据都无法被读写器所识别。,14,8.2 ALOHA,算法,纯,ALOHA,算法,纯,ALOHA,算法的信道吞吐率,S,与帧产生率,G,之间的关系为,当,G,=0.5,时，最大吞吐率,S,=1/(2e)18.4%,。发送帧不会产生碰撞,（即发送成功）的概率,P,为,电子标签数量越多，帧时越长，则,G,越大，发送成功的概率越低。,纯,ALOHA,算法虽然算法简单，易于实现。但对于同一个标签，,如果连续多次发生碰撞，这将导致读写器出现错误判断认为这个标,签不在自己的作用范围内。同时其冲突概率很大。,假设其数据帧长,度为,F,，则冲突周期为,2,F,。,15,8.2 ALOHA,算法,时隙,ALOHA,算法,时隙,ALOHA,算法把时间分成多个离散的时隙，每个时隙长度等于,或稍大于一个帧，标签只能在每个时隙的开始处发送数据。这样标,签要么成功发送，要么完全碰撞，避免了纯,ALOHA,算法中的部分碰撞,冲突，碰撞周期减半，提高了信道利用率。时隙,ALOHA,算法需要读写,器对其识别区域内的标签校准时间。时隙,ALOHA,算法是随机询问驱动,的,TDMA,防冲撞算法，工作过程如图所示。,16,8.2 ALOHA,算法,时隙,ALOHA,算法,时隙,ALOHA,算法的信道吞吐率,S,和帧产生率,G,的关系为,当,G,=1,时，吞吐量,S,为最大值,1/e,，约为,0.368,，是纯,ALOHA,算法的,两倍。,因为标签仅仅在确定的时隙中传输数据，所以该算法的冲撞发,生频率仅仅是纯,ALOHA,算法的一半，但其系统的数据吞吐性能却会增,加一倍。,17,8.2 ALOHA,算法,帧时隙,ALOHA,算法,帧时隙算法中，时间被分成多个离散时隙，电子标签必须在时,隙开始处才可以开始传输信息。读写器以一个帧为周期发送查询命,令。当电子标签接收到读写器的请求命令时，每个标签通过随机挑,选一个时隙发送信息给读写器。如果一个时隙只被唯一标签选中，,则此时隙中标签传输的信息被读写器成功接收，标签被正确识别。,如果有两个或两个以上的标签选择了同一时隙发送，则就会产生冲,突，这些同时发送信息的标签就不能被读写器成功识别。整个算法,的识别过程都会如此循环，一直到所有标签都被识别完成。,18,8.2 ALOHA,算法,帧时隙,ALOHA,算法,帧时隙,ALOHA,算法工作过程如图所示。,该算法的缺点是当标签数量远大于时隙个数时，读取标签的时,间会大大增加；当标签个数远小于时隙个数时，会造成时隙浪费。,19,8.2 ALOHA,算法,帧时隙,ALOHA,算法,一个典型的帧时隙,ALOHA,算法过程如图所示。,在每一帧初始时刻，读写器发出请求指令，向标签提供帧长等,信息。每个标签根据信息随机选择一个时隙向读写器发送信息。假,设标签的序列号为,4,比特，在第一帧中，标签,1,和标签,3,选择了时隙,1,与读写器通信，标签,2,和标签,4,选择了时隙,2,。时隙,1,和时隙,2,都发生了,碰撞，而标签,5,在时隙,3,中被读写器成功识别。第二帧中标签,3,和标签,2,被成功识别。如此循环直到所有标签被成功识别为止。,20,8.2 ALOHA,算法,动态帧时隙,ALOHA,算法,动态帧时隙,ALOHA,算法中一个帧内的时隙数目随着区域内标签,数目动态改变，或增加时隙数以减少帧中的碰撞数目。步骤如下：,（,1,）进入识别状态，开始识别命令中包含了初始的时隙数,N,。,（,2,）由电子标签随机选择一个时隙，同时将自己的时隙计数器,复位为,1,。,（,3,）当电子标签随机选择的时隙数与时隙计数器对应时，标签,向读写器发送数据；若不相等，标签将保留自己的时隙数并等待下,一个命令。,（,4,）当读写器检测到的时隙数量等于命令中规定的循环长度,N,时，本次循环结束，读写器转入步骤（,2,），开始新的循环。,该算法每帧的时隙个数,N,都是动态产生的，解决了帧时隙,ALOHA,算法中的时隙浪费的问题，适应标签数量动态变化的情形。,21,8.2 ALOHA,算法,动态帧时隙,ALOHA,算法,动态帧时隙,ALOHA,算法允许根据系统的需要动态地调整帧长度，,由于读写器作用范围内的标签数量是未知的，而且在识别的过程中,未被识别的标签数目是改变的，因此，如何估算标签数量以及合理,地调整帧长度成为动态帧时隙,ALOHA,算法的关键。由理论推导可知，,在标签数目和帧长度接近的情况下，系统的识别效率最高，也就是,说标签的值就是帧长度的最佳选择。,在实际应用中，动态帧时隙算法是在每帧结束后，根据上一帧,的反馈情况检测标签发生碰撞的次数（碰撞时隙数），电子标签被,成功识别的次数（成功时隙数）和电子标签在某个时隙没有返回数,据信息的次数（空闲时隙数）来估计当前未被正确识别的电子标签,数目，然后选择最佳的下一帧的长度，把它的帧长度作为下一轮识,别的帧长，直到读写器工作范围内的电子标签全部识别完毕。,22,8.3,二进制树型搜索算法,二进制树型搜索算法,由读写器控制,，基本思想是不断的将导致,碰撞的电子标签进行划分，缩小下一步搜索的标签数量，直到只有,一个电子标签进行回应。,1,冲突位检测,实现该算法系统的必要前提是能够辨认出在读写器中数据冲突,位的准确位置。为此，必须有合适的位编码法。如图对,NRZ,编码和曼,彻斯特编码的冲突状况作一比较。,23,8.3,二进制树型搜索算法,1,）,NRZ,编码,某位之值是在一个位窗（,t,BIT,）内由传输通路的静态电平表,示，这种逻辑,“,1,”,为,“,高,”,电平，逻辑,“,0,”,为,“,低,”,电平。如果两个,电子标签之一发送了副载波信号，那么，这个信号由读写器译码为,“,高,”,电平，就被认定为逻辑,“,1,”,。但读写器不能确定读入的某位究竟,是若干个电子标签发送的数据相互重叠的结果，还是某个电子标签,单独发送的信号，见下页中图（,a,）。,2,）曼彻斯特编码,某位之值是在一个位窗（,tBIT,）内由电平的改变（上升,/,下降沿）,表示。逻辑,“,0,”,编码为上升沿，逻辑,“,”,编码为下降沿。如果两个或,多个电子标签同时发送的数位有不同值，则接收的上升沿和下降沿,互相抵消，,“,没有变化,”,的状态是不允许的，将作为错误被识别。用,这种方法可以按位追溯跟踪冲突的出现，见下页中图（,b,）。,24,8.3,二进制树型搜索算法,采用,NRZ,编码和曼彻斯特编码的冲突状况（曼彻斯特编码能够按,位识别出冲突）示意图。因此，选用曼彻斯特编码可实现,“,二进制树,型搜索,”,算法。,25,8.3,二进制树型搜索算法,2.,二进制树型搜索算法过程,二进制树型搜索算法的模型如图所示，其基本思想是将处于冲,突的标签分成左右两个子集,0,和,1,，先查询子集,0,，若没有冲突，则正,确识别标签，若仍有冲突则再分裂，把子集,0,分成,00,和,01,两个子集，,依次类推，直到识别出子集,0,中所有标签，再按此步骤查询子集,1,。,可见，标签的序列号是处理碰撞的基础。,26,8.3,二进制树型搜索算法,二进制树型搜索算法的实现步骤如下：,（,1,）读写器广播发送最大序列号查询条件,Q,，其作用范围内的标,签在同一时刻传输它们的序列号至读写器。,（,2,）读写器对收到的标签进行响应，如果出现不一致的现象（即,有的序列号该位为,0,，而有的序列号该位为,1,），则可判断有碰撞。,（,3,）确定有碰撞后，把有不一致位的数最高位置,0,再输出查询条,件,Q,，依次排除序列号大于,Q,的标签。,（,4,）识别出序列号最小的标签后，对其进行数据操作，然后使其,进入,“,无声,”,状态，则对读写器发送的查询命令不进行响应。,（,5,）重复步骤,1,，选出序列号倒数第二的标签。,（,6,）多次循环完后完成所有标签的识别。,27,8.3,二进制树型搜索算法,为了实现这种算法需要一组命令。这组命令可由电子标签进,行处理（见下表），每个电子标签拥有一个唯一的序列号（,SNR,）。,REQUEST,（,SNR,）,请求（序列号）,此命令发送一序列号作为参数给电子标签。电子标签把自己的序列号与接收的序列号,进行,比较,，,如果小于或相等，则此电子标签回送其序列号给读写器。这样就可以缩小预选的电子标签的范围,SELECT,（,SNR,）,选择（序列号）,用某个（事先确定的）序列号作为参数发送给电子标签,，,具有相同序列号的电子标签将以此作为执行其他命令（如读出和写入数据）的切入开关，即选择这个电子标签,，,具有其他序列号的电子标签只对,REQUEST,命令应答,READ-DATA,读出数据,选中的电子标签将存储的数据发送给读写器（在实际的系统中，还有鉴别或写入等命令,等,）,UNSELECT,退出选择,取消一个事先选中的电子标签，电子标签进入,“,无声,”,状态。在这种状态,下，,电子标签完全是非激活的，对收到的,REQUEST,命令不作应答。为了重新激活电子标签，必须暂时离开读写器的作用范围（等于没有供应电压），以执行复位,28,8.3,二进制树型搜索算法,3,二进制树型搜索算法实例,下面以一个实例来说明二进制树型搜索算法。现以读写器作用,范围内的四个电子标签为例说明搜索的过程。这四个电子标签的序,列号（这里用,8,位的序列号举例）分别为：,电子标签,1:10110010,电子标签,2:10100011,电子标签,3:10110011,电子标签,4:11100011,二进制树型搜索算法算法在重复操作的第一次中由读写器发送,REQUEST,（,11111111,）命令。序列号,11111111,，是本例中系统最大,可能的,8,位序列号。读写器作用范围内的所有电子标签的序列号都应,小于或等于,11111111,，因此，处于读写器作用范围内的所有电子标,签都应对该命令作出应答。,29,8.3,二进制树型搜索算法,3,二进制树型搜索算法实例,二进制树型搜索算法选择电子标签的迭代过程如图。,30,8.3,二进制树型搜索算法,如上表所示,对于所接收的序列号的,0,位、,4,位和,6,位，由于重,叠着响应的电子标签对这些位的不同内容而造成了冲突（,x,）。因,此，可以推断在读写器作用范围内存在两个或多个电子标签。仔细,观察表明：由于接收的位顺序为,1x1x001x,，从而可以得出所接收的,序列号的八种可能性。,第,6,位是最高的,x,位，此位在第一次迭代中上出现了冲突。这意,味着：不仅在序列号（,SNR,）,11000000b,的范围内，而且在序列号,（,SNR,）,1,0,111111b,的范围内，至少各有一个电子标签存在。为了,能选择到一个单独的电子标签，必须根据已有的信息来限制下一次,迭代的搜索范围。例如，用,1,0,111111b,的范围内进一步搜索。为,此，将第,6,位置,“,0,”,（有冲突的最高值位），将所有低位置,“,1,”,，从而,暂时对所有的低值位置不予处理。,31,8.3,二进制树型搜索算法,二进制树型搜索树通过地址参数限制搜索范围的一般规则：,读写器发命令,REQUEST,（,10111111,）后，所有满足此条件的,电子标签都要做出应答，并将它们自己的序列号传输给读写器。本,例中，做出应答的是电子标签,1,、,2,和,3,（见第二次迭代）。,现在接收的序列号的第,0,位和第,4,位上出现了碰撞（,x,）。由此得出,结论：在第二次迭代的搜索范围内，至少还存在有两个电子标签。,需要进一步确定的序列号有四种可能性。,检 索 命 令,第一次迭代：范围,=,第,n,次迭代：范围,=,请求（,REQUEST,）范围,0,位（,x,）,=1,，位（,0,x1,）,=0,请求（,REQUEST,）范围,序列号（,SNR,）,Max,位（,x,）,=0,，位（,0,x1,）,=1,32,8.3,二进制树型搜索算法,如果第二次迭代仍然出现冲突，则要求第三次迭代进一步限制,搜索范围。使用表格形成的规则，其搜索范围,10101111,。读写器,将命令,REQUEST,（,10101111,）发送给电子标签。只有电子标签,2,（,“,10100011,”,）能满足此条件，该电子标签即单独对命令作出应答,（见第三次迭代）。,然后，读写器用,SELECT,命令选中电子标签,2,，对该选中的电子标,签进行,READ-DATA,操作。此时其他电子标签则处于静止状态。在完成,READ-DATA,操作后，读写器用,UNSELECT,命令使电子标签,2,进入,“,无声,”,状态，这样电子标签,2,对后继的请求命令将不再做出应答。,33,8.3,二进制树型搜索算法,如图形象地描述了上述例子的搜索过程，三次迭代需要不断地,搜索空间，直到第三次搜索定位到唯一的一个电子标签。,二进制树型搜索树：随着搜索范围的依次变小，最终可以选择一个唯一的电子标签,34,8.3,二进制树型搜索算法,为了从较大量的电子标签中搜索出某个唯一的电子标签，需要,多次迭代。其平均次数,L,取决于读写器作用范围内的电子标签总数,N,，即,可以看出，利用二进制树型搜索算法可以快速简单地解决碰撞,问题。如果只有一个电子标签在读写器作用范围内，在这种情况下,不会出现冲突，只需要一次迭代就可发现电子标签的序列号。如果,有一个以上的电子标签处在读写器作用范围内，那么迭代的平均数,增加很快。,35,8.3,二进制树型搜索算法,动态二进制树型搜索,二进制树型搜索算法为了选择一个电子标签传输大量多余的数据。,如图用,X,表示最高冲突位的位置，在前述的迭代的最高冲突位上出现了位冲突，即可得出：,命令中（,X,1,）,0,各位不包含给电子标签的补充信息，因为（,X,1,）,0,各位总是被置为“,1”,的。,电子标签序列号的,N,X,各位不包含给读写器的补充信息，因为,N,X,这些位是已知且给定的。,在搜索一个,4,字节序列号时，读写器的命令（第,n,次迭代）和电子标签的应答,36,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,），多次重复后可完成电子标签交换数据工作。,37,8.3,二进制树型搜索算法,如图为动态的二进制树型搜索算法过程。,NVB,表明请求命令的有效位数。电子标签返回的序列号只是除了这些有效位之后的部分，避免序列号中多余部分的传输，要传输的数据数量和所需时间的减少可达,50%,。,38,8.3,二进制树型搜索算法,基于随机数和时隙的二进制树搜索,该算法采用递归的工作方式，遇到碰撞就进行分支，成为两个,子集。这些分支越来越小，直到最后分支下面只有一个信息包或者,为空。分支的方法就如同抛一枚硬币一样，将这些信息包随机地分,为两个分支，在第一个分支里，是,“,抛正面,”,（取值为,0,）的信息包。,在接下来的时隙内，主要解决这些信息包所发生的碰撞。如果再次,发生碰撞，则继续再随机地分为两个分支。该过程不断重复，直到,某个时隙为空或者成功完成一次数据传输，然后返回上一个分支。,这个过程遵循,“,先入后出,”,的原则，等到所有第一个分支的信息包都,成功传输后，再来传输第二个分支，也就是,“,抛反面,”,（取值为,1,）的,信息包。此算法不要求电子标签需准确同步。,这种算法称为,树型搜索算法,，每次分割使搜索树增加一层分支。,39,8.3,二进制树型搜索算法,如图所示为四层（,m,=4,）树算法的原理示意图。每个顶点表示一,个时隙，每个顶点为后面接着的过程产生子集。如果该顶点包含的,信息包个数大于或等于,2,，那么就产生碰撞，于是就产生了两个新的,分支。算法从树的根部开始，在解决这些碰撞的过程中，假设没有,新的信息包达到。,40,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,为空闲。,41,8.3,二进制树型搜索算法,二进制树型算法是在碰撞发生后解决碰撞问题的一种算法。,需要指出的是，当碰撞正在进行时，新加入这个系统的信息包禁止,传输信息，直到该系统的碰撞问题得以解决，并且所有信息包成功,发送完后，才能进行新信息包的传输。例如，在上例中，在时隙,1,到,时隙,11,之间，新加入系统的信息包，只有在时隙,12,才开始传输。,二进制树型算法也可按照堆栈的理论进行描述。在每个时隙，,信息包堆栈不断地弹出与压栈，在栈顶的信息包最先传输。当碰撞,发生时，先把抛,1,的信息包压栈，再把抛,0,的信息包压栈，这样抛,0,的,信息包就处在栈顶，在下个时隙弹出即能进行传输。当完成一次成,功传输或者出现一次空闲时隙的时候，栈顶的信息包被继续弹出，,依次进行发送。显然，当堆栈为空时，即碰撞问题得以解决，所有,信息包成功传输。接下来，把新到达这个系统的信息包压栈，操作,过程同前面的一样。,42,8.4,本章小结,本章介绍了,RFID,中的关键技术,防碰撞技术。多个标签同时,向读写器发送数据时,将会产生碰撞而导致读写器无法正确识读这些,标签。,无线通信领域中防碰撞算法主要包括,TDMA,、,CDMA,、,FDMA,和,SDMA,。,RFID,系统的防碰撞算法基本都属于,TDMA,，主要包括,ALOHA,算法和二进,制树型搜索算法。其中，,ALOHA,算法,是一种非确定方法，由电子标签,控制发送时间，一般用于高频,RFID,系统。,二进制树型搜索算法,一般,是由读写器控制的确定性方法，主要用于超高频,RFID,系统。,43,