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