RFID防碰撞协议原理分析

1、RFID防碰撞协议原理分析姓名： _张强强_学号： 院系： _计算机学院_专业： _网络工程_指导教师：_范波_目录摘要3Abstract31.RFID系统中防碰撞协议41.1 二进制防碰撞协议51.2 查询树防碰撞协议52.RFID中防碰撞算法62.1基于Aloha的算法62.1.1纯Aloha62.1.2时隙Aloha72.1.3 FSA82.1.4 DFSA82.2基于二进制树的算法92.2.1 二进制搜索算法92.2.2 动态二进制搜索算法92.2.3后退式二进制搜索算法9结束语10参考文献11摘要RFID是一种非接触式的自动识别技术，碰撞问题是影响RFID系

2、统读取效率的关键问题。导致标签识别效率的降低和资源的浪费。本文介绍了两种防碰撞协议的性能。指出其优缺点和研究进展情况。关键词：RFID ; 防碰撞协议AbstractRFID is a non-contact automatic identification technology, which is the key problem of the RFID system. Reduce the efficiency of label identification and the waste of resources. In this paper, the performances of thre

3、e kinds of anti-collision protocols are compared. Points out their advantages and disadvantages and the research progress.Keyword: RFID ; Anti-collision protocol1. RFID系统中防碰撞算法为了解决碰撞问题，产生了很多的防碰撞算法，目的就是把众多的标签按照某种方式分隔开进行逐个读取，主要有频分多路法(FDMA)、空分多路法(SDMA)、时分多路法(TDMA)和码分多路法(CDMA)四种方法。防碰撞算法结构图如图所示防碰撞算法二进制树Q

4、算法查询树分裂法轮询法Aloha阅读器驱动标签驱动CDMAFDMA TDMASDMA空分多路法由于其复杂的天线系统的高费用使得应用不是很广泛，频分多路法由于其阅读器的费用比较高，应用也受到了限制。码分多路法的多路方式软件设计困难，读写器每一路都需要相应的硬件或软件支持，非常复杂，所以不适合RFID系统。因此，TDMA成为反碰撞算法最广泛的选择，该方法又分为标签驱动法和阅读器驱动法，标签驱动法中具有代表性的算法是Aloha算法。阅读器驱动法需要准确的同步进而无错误的检测出碰撞位，它再划分为“轮询法”和“分裂法”。由于Aloha算法不能有效地解决标签饿死的问题，所以本文的研究主要在分裂法的基础上进

5、行。1.1 二进制防碰撞协议二进制防碰撞协议中，阅读器应用二进制搜索算法能够成功地读取它范围内的所有标签。标签含有唯一的ID序列号(由一些二进制码构成)，阅读器在每次查询过程中只发送一位0或1，标签中与接收的位相同的才会发生应答，并发送自己的下一位直至所有ID序列号传完。标签中与接收到的位不相同的就会转到待机状态，直到某个标签被识别剩余的标签重置。在一个识别过程中，如果阅读器发现冲突就会发0，否则发送从标签接收的那一位作为下一个查询位。1.2 查询树防碰撞协议查询树算法是一种无记忆标签防碰撞算法。读写器发送一个前缀查询信息，与这个前缀相匹配的标签做出响应。读写器发出的前缀决定了碰撞的标签如何分

6、裂。标签除了其自身的ID号以外无需记忆其他额外的信息。一旦一个标签被成功识别，读写器就开始新一轮的读取操作。协议原理：读写器发送长度为k的前缀；ID中前k bit和前缀匹配的标签反馈第(k+1)bit至最后1 bit。如果阅读器收到的ID碰撞，再先后将前缀加“0”或 “1”，作为新的前缀发送出去。如果没有发生碰撞，就表明有一个标签被识别了。2.RFID中防碰撞算法本文主要研究基于时分多址技术的防碰撞协议，这些协议根据是由阅读器驱动还是标签驱动可以分为阅读器先发言(reader-talk-first，RTF)和标签先发言(tag-talk-first，TTF)，其中用得最广泛的是RTF，而基于R

7、TF有两种防碰撞算法，即Aloha算法和基于二进制树的算法。2.1基于Aloha的算法2.1.1纯AlohaAloha算法是一种随机接入方法，其基本思想是采取标签先发言的方式，当标签进入阅读器的识别区域时自动向读写器发送其自身的ID号，在标签数据的过程中，若有其他标签也在发送数据，那么发生信号重叠导致完全冲突或部分冲突，读写器检测接收到的信号是否发生冲突，一旦发生冲突，读写器就发送命令让标签停止发送，随机等待一段时间后再重新发送以减少冲突。在纯Aloha算法中，存在部分碰撞和完全碰撞的问题。它有如下3种工作状态关断。在协议中用Muting命令时，成功识别一个标签就会让在阅读器识别范围标签总数目

8、减，减少阅读器的负载。当两个标签同时发送数据时就会发生碰撞，随机等待一段时间再重新发送。当系统成功识别后，阅读器发送Muting命令让标签处于“沉默”状态。减慢标签信息发送速度。在这种工作模式下，主要降低数据的传输速率，这样能减少碰撞的几率。载波监听。当阅读器侦测到一个标签开始传送数据时，会发送一个“Silence”命令。目的是阻止其他标签传送数据，直到阅读器发送“ACK”或标签等待时间到时，标签重新传送数据。其他结合Fast Mode和Muting、PA with and Fast Mode和Slow Down各自的特性组成另外两种工作模式。由于纯Aloha算法存在着部分碰撞现象，因此其碰撞

9、概率很大，适用于阅读器只负责接收标签发射的信号，而标签只负责向阅读器发射信号的情况。2.1.2时隙Aloha在时隙Aloha算法中，标签数据传输只在每个时隙的起始，因此它只会发生，不会发生部分碰撞。时隙Aloha算法有如下几种工作状态。Muting/Slow Down。作用相似于在纯Aloha算法中的作用，只是运行在单个时隙中.Early End。当在这个时隙没有检测到有数据传送时，阅读器马上关闭该时。在这个工作模式中，有两个命令应用：第一，Start-of-Frame(SOF)开始一个阅读循环；第二，End of-Frame(EOF)关闭一个空闲的时隙。Early End and Mutin

10、g。成功识别标签后，阅读器发送Mute命令减少需要识反之，在一个短暂时间内侦测到没有数据传输，阅读器就发出EOF命令终止这个。Slow Down and Early End。提前结束状态时间。总的来说，Fast Mode仅用于与纯Aloha结合，Early End用在时隙算法中，目的是减少对已经终止的时隙的检测，Muting和Slow Down能有效地减少阅读器的负载。在时隙算法中，完全Aloha算法中的部分碰撞，提高了信道的利用率。但是这种算法需要一个时钟使阅读器阅读区域内的所有标签时隙同步，这相应地提高了设备的成本，并且标签数目远远大于时隙时，标签碰撞机率就会大大增加，造成标签识别时延。2

11、.1.3 FSA帧时隙 Aloha (framed slotted Aloha，FSA)算法是在时隙Aloha算法的基础上，把N个时隙组成一帧，标签在每个帧内随机选择一个时隙发送数据，适用于传输信息量较大的场合，与时隙Aloha算法相同，其也需要一个同步开销，但只需要每个帧同步就可以了，相对于时隙Aloha算法，其同步开销更少。基于RFID的PA和SA有很快的响应速度，随之带来的也是很高的碰撞几率，因为在一个时隙中，多个标签都可以在每个时隙开始的时候传输数据。在FSA算法中，只在每个帧开始时传送一次数据，这会大大降低标签碰撞的几率.2.1.4 DFSADFSA动态帧时隙Aloha(DFSA)算

12、法是FSA算法的一种改进算法，也是在RFID应用中防碰撞算法应用得最多的算法之一。在DFSA算法中，每帧中的时隙数都是动态的，因此解决了FSA算法的时隙浪费和不足问题，与FSA算法的不同之处在于其每次循环都会利用一个标签估计函数来修改帧的大小。动态帧时隙Aloha算法中的标签估计函数是基于阅读器反馈的空时隙数(c0)、成功时隙数(c1)和碰撞时隙数(ck)计算下个识别循环需要的时隙数。理论上，当估计的时隙数等于标签的数目时，标签识别的效率最高。2.2基于二进制树的算法2.2.1 二进制搜索算法基本思想是将处于碰撞的标签分成左右两个子集0和1，先查询子集0，若没有碰撞，则正确识别标签，若还碰撞则

13、再次分裂，直到识别完所有标签；同理，查询子集1。在RFID系统中，要实现这种防碰撞算法，需要一系列的命令Request ； Select ； Read Data ； Unselect；2.2.2 动态二进制搜索算法在实践中标签的序列号不像上例中那样仅由1byte组成，而是按系统的规模可能长达10byte，以致不得不传输大量的数据，而仅仅是选择一个单独的标签。传输的序列号的各自互补的部分是多余的，也是不必传输的。由此得出一种最佳的算法：代替序列号在两个方向上完整地传输，序列号或搜索的范围标准的传输现在简单地改变为部分位（X）。阅读器在Request（请求）命令中只发送要搜索的序列号的已知部分NX

14、作为搜索的依据，然后中断传输。所有在NX位中的序列号与搜索依据相符的标签，则传输的序列号的剩余各位即x-1位为应答。在Request命令中的附加参数（有效位的编号）将余下各位的数量通知标签。2.2.3后退式二进制搜索算法这个算法的策略是不断缩小搜索的范围来识别标签。相对于前面两种算法减少了时间的复杂度，即识别N个标签，阅读器共需要问询2N-1次，平均问询次数为2次。实现方法：碰撞发生时，根据碰撞的最高位，跳跃式向前搜索；无碰撞时，采取后退策略，能够快速地识别所有标签22,23，减少标签识别的循环次数，但标签ID传输时间和二进制传输时间是一样的。从上面几种算法可以看出，二进制算法及基于二进制改进的算法都可以减少标签数据和搜索循环次数，以此来减少识别时延。结束语从上面的分析可知，当标签数目不是很多且对实时性要求不是很高时，可以采用Aloha算法和由它改进的算法，因为这种算法实现简单，成本较低；当标签数量很多时，Aloha算法的信道利用率迅速降低，这时就可以采用二进制算法及由它改进的一些算法。从上面的比较可知，这几种算法暴露信息很多，安全性很差，因此未来的防碰撞算法应该在不增加成本的基础上，提高标签识别的效率和数据信息的安全性。参考文献1.Rfidinfo.中国RFID市场首次突破120亿规模.2 谭民，刘禹，曾隽芳,等.RFID技术系统工程及应用指南M.北京:机械工业出版社，