RFID防碰撞算法概述

RFID防碰撞算法概述学院：学号：姓名：年级：目录1RFID系统的介绍..............................................................................................-3-1.1RFID系统的结构和构成.....................................................................-3-1.1.1阅读器的结构...............................................................................-3-1.1.2电子标签的结构...........................................................................-4-2防碰撞算法.........................................................................................................-6-2.1防碰撞算法的产生..................................................................................-6-2.2防碰撞算法分类......................................................................................-6-2.2.1空分多路法（SDMA）...............................................................-6-2.2.2频分多路法（FDMA）...............................................................-7-2.2.3时分多路法（TDMA）...............................................................-8-3时分多路防碰撞算法.......................................................................................-10-3.1非确定性防碰撞算法分析....................................................................-10-3.1.1纯ALOHA算法（算法）...................................................--3.1.2时隙ALOHA法（SA算法）..................................................-12-3.1.3帧时隙ALOHA算法（FSA算法）.......................................-13-3.1.4动态帧时隙ALOHA算法（DFSA算法）.............................-13-3.1.5随机推迟算法（P-ALOHA算法）..........................................-14-3.1.6非确定性防碰撞算法的比较.....................................................-15-3.2确定性算法的分析................................................................................-15-3.2.1树形分裂算法（TS算法）.......................................................-15-3.2.2询问树算法（算法）..........................................................-16-3.2.3改进的混合查询多叉树防碰撞算法.........................................-16-3.2.4二进制树搜索算法（BS算法）...............................................-17-3.2.5DynamicBinarySearch（DBS）算法......................................-19-3.2.6基于状态仲裁的锁位防碰撞算法.............................................-20-3.2.7自适应分裂树算法（AST算法）...........................................-20-3.2.8非确定性防碰撞算法的比较.....................................................-22-4总结及展望.......................................................................................................-23-参考文献.................................................................................................................-24--2-1RFID系统的介绍RFID是射频识别技术的英文缩写（RadioFrequencyIdentification的信息达到识别目的的技术。它是上世纪90年代兴起的自动识别技术，首先在欧洲市场上得以使用，随后在世界范围内普及。RFID较其它技术明显的优点是电子标签和阅读器无需接触便可完成识别。1.1RFID系统的结构和构成1.1阅读器终端的工作；后台网络是整个RFID系统的信息管理中心。图1.1射频识别系统的构成1.1.1阅读器的结构RFID签内部信息，或者将要写入标签的信息编码、调制后经天线发射出去[1][3]。1.2射频通道模块、控制处理模块和I/O接口模块[3][4]。-3-信号送到控制处理模块。现，I/O控制也由控制处理模块完成。图1.2阅读器的工作模型I/O的输入与输出通信。常用的接口有：RS-232串行接口、RS-422-485串行接口、标准并行打印接口、以太网接口、红外IR接口以及USB接口。1.1.2电子标签的结构电子标签（）由耦合元件及芯片组成，标签含有内置天线，用于和射频天线间进行通信。每个标签具有唯一的电子编码，附着在物体上标识目标对象。每个标签都有一个全球唯一的ID号码—UIDUID是在制作芯片时放在中的，只能读取，无法修改。用户数据区（）是供用户存放数据的，可以进行读写、覆盖、增加的操作。典型的电子标签结构如图1.3所示。识别和读取[3][3]。本身带有电源，工作能量可以从电源直接获得。-4-图1.3典型的电子标签结构FDXHDXSEQ并解调来自电子标签的高频信号。图1.4系统工作原理图-5-2防碰撞算法2.1防碰撞算法的产生RFID系统主要包括标签（）和读写器（Reader）两部分。标签适用于对象身份识别，它的主要模块集成在一个芯片中，芯片内存用来存储ID或其他RF信号与标签通信，标签将自身ID号发送给读写器，达到身份识别的目的。阅读将产生冲突，称为标签冲突。这个冲突被称为碰撞（collision致一次传输的失败。为了解决上述问题而产生了防碰撞算法。2.2防碰撞算法分类SDMATDMAFDMA（CDMA数据相互碰撞而不能读出等问题的出现。RFIDCodeDomainMultipleAccessCDMAFrequencyDomainMultipleAccessFDMADomainMultipleAccessTDMASpaceDomainMultipleAccessSDMA）4大类。2.2.1空分多路法（）SDMA技术，图2.1就是一种使用定向天线的自适应的空分多路法的示意图。-6-别开来。的参赛运动员。图2.1使用定向天线的自适应的空分多路法2.2.2频分多路法（）频分多路法（FMDA）[41]是把若干个使用不同载波频率的传输通路同时供通信用户使用的技术，图2.2就是这种频分复用的示意图。签区别开来。FDMA的缺点是阅读器的成本比较高，因为每个接收通路都必须-7-也应用在极少数的特殊场合上。2.2.3时分多路法（）时分多路法[42]就是把整个可供使用的通路容量按照时间分配给多个用户的技术。在射频识别系统中，TDMA法构成了防碰撞算法的最大的一族。这种2.3所示。图2.3频分多路示意图否通过阅读器的信号而断开，又可区分为“开关断开”法和“非开关”法。为定时双工法。-8-图2.4时分防碰撞算法分类-9-3时分多路防碰撞算法目前在RFID系统中应用最多、种类最广的算法是基于TDMA的防碰撞算法。RFID防碰撞算法又可以分为确定性算法和非确定性算法两大类【2】。如图3.1。图3.1表3.1优缺点。表3.1非确定性防碰撞算法与确定性防碰撞算法比较算法类型硬件设计识别率吞吐量识别速度非确定性防碰撞算法简单不能保证100%识别低快确定性防碰撞算法复杂保证100%高慢3.1非确定性防碰撞算法分析非确定性防碰撞算法主要是在Aloha是不同标签在不同的时隙发送识别编码，达到防碰撞的目的。其中包括纯ALOHA算法（PureAloha，ALOHA算法（SlottedAloha,SA-10-帧时隙ALOHA算法（FrameSlottedAloha，FSA）及动态帧时隙ALOHA算法（DynamicFrameSlottedAloha，DFSA3.1.1纯ALOHA算法（算法）ALOHA算法的基本思想是：采取标签先发言的方式，即标签一进入阅读器的作用区域，就主动发送自己的信息。如果采用的是接收功能的芯片，那么0，T）随机产生的随机数，因为随机数的不同，避开了碰撞。这里假设标签的退避时间服从（0，T）之间的均匀分布。算法是所有多路存取中最简单的一种方法，在阅读器作用范围内的标签随机产生应答时间。Aloha标签进入读写器的识别区域内就自动向读写器发送其自身的ID号，在标签发送数据的过程中,若有其他标签也在发送数据,那么发生信号重叠导致完全冲突或部Aloha算法模型图如图3.2所示。标签标签标签信道完全冲突

部分冲突图3.2Aloha算法模型纯Aloha--数据帧为F2FAloha算法在RFID系统其可行性和识别率，H提出了一种改进的算法是SlottedAloha算法，该算法在Aloha算法的基础上把时间分成多个离散时隙，每个时隙长度T等于标签的数据帧长度，Aloha算法中时钟，对标签要求较高，标签应有计算时隙的能力。ALOHATDMA）方式，其算法要点如下：（1）进入到阅读器阅读区域的标签随即向阅读器发送消息。（2,阅读器发送命令让标签停止发送，随机等待一段时间再发送。若无，阅读器则开始与标签进行通信。3.1.2时隙ALOHA法（SA算法）SA算法是在算法的基础上，将信道分成若干时隙，标签只在规定的同步时隙内传输数据包，因此冲突只在时隙边界处才会发生。时隙ALOH大于一个帧，标签只能在每个时隙的开始处发送数据，这样标签或成功发送或者ALOHA用率。相对于纯ALOHA算法ALOHA算法需要阅读器对其识别区域内的标签校准时间。所以只有具有接收功能的芯片才能实现时隙ALOHA算法。时隙ALOH算法的基本思想是：标签进入阅读器范围内，随机选择发送信不止一个标签响应，当阅读器检测出碰撞后，通知标签，则标签将在退避区间T将睡眠T2个周期后，重新开始下一次发送。算法要点如下：（1）REQUEST子标签在下一个时隙里将它的序列号传输给读写器。-12-（2子标签。（3）READ—。此算法要求电子标签拥有一个唯一的序列号并且所有的标签必须由读写器，令之后把ID传给读写器，机地分给标签，直到读完所有的标签。算法特点：SA算法因为有读写器控制在同步时隙内传送数据，可能发生碰撞的时间区就缩短了一半，当G=I时，S增大为36.8％，但仍局限于只读型电子标签。3.1.3帧时隙ALOHA算法（FSA算法）帧时隙Aloha（framedslottedAlohaFSA）算法是在时隙Aloha算法的基础上，把Ⅳ个时隙组成一帧，标签在每个帧内随机选择一个时隙发送数据，适AlohaAlohaFSA算法是在SA个时隙发送自己的数据信息。基于RFID的和SA有很快的响应速度，随之始的时候传输数据。在FSA算法中，只在每个帧开始时传送一次数据，这会大大降低标签碰撞的几率。的浪费。3.1.4动态帧时隙ALOHA算法（DFSA算法）DFSA求在减少冲突标签和避免空闲时隙之间寻找平衡点。表二为非确定性防碰撞算-13-法吞吐率计算公式及最大吞吐率的比较。对FSAALOHA法。算法要点如下：（1）标签进入读卡器阅读范围后，接收到读卡器的开始识别命令后进人识别状态，并且在开始识别命令中包含了初始的时隙数；（2）进入识别状态的标签随机选择一个时隙（内部伪随机数发生器产生）同时将自己的时隙计数器复位为1；（3）当标签随机选择的时隙数等于时隙计数器计数时，标签向读卡器发送一个命令；（4N将结束。读卡器发送开始识别命令进入步骤（2）开始新的循环，新的循环长度N是读卡器根据前一次循环中的冲突数量动态优化调整后产生的。优点：由于帧中的时隙个数N是动态产生的，其时隙数可变，解决了FSA到有唯一标签的时隙为止，从而大大提高了吞吐率。3.1.5随机推迟算法（P-ALOHA算法）采用纯ALOHA算法经常会遇到多移动目标同时进入工作区域的情况，P-ALOHA决RFID系统的碰撞问题。重发模式要点如下：(1)阅读器向处在阅读范围内的标签发送“启动”信号。(2)标签在接收到阅读器“启动”信号后向阅读器发送信号，若发生碰撞，则发生冲突的标签在等待一段随机时间之后再进行重发。由于每个标签推迟的时间不一样，所以重发后再碰撞的可能性就降低了。此方法特点：重发模式和随机推迟增大了随机数变化的范围，减少了碰撞，延较长，导致读取速率较慢且发生错误的几率较大。-14-3.1.6非确定性防碰撞算法的比较表3.2非确定性防碰撞算法吞吐率计算公式及最大吞吐率的比较算法类型吞吐率计算公式最大吞吐率PASGe2G18.4%SASGeG36.8%FSA11)n136.8%SCNNnDPSA11)n136.8%SCNNn表3.2中SG范围内的标签数，N为时隙数。其中动态帧时隙ALOHA算法的N是根据读写器识别范围内的标签数n不同而变化的。3.2确定性算法的分析由于非确定性防碰撞算法无法保证在规定时间内完成阅读器作用范围里所100％应用，splittingQuery，（BinarysearchBSBitwisearbitration（AdaptiveSplittingAST法。3.2.1树形分裂算法（TS算法）TS算法基本思想是当碰撞发生时，采用随机方式将标签分成若干子组，分组数目会不断增加直到每组内仅包含一个标签。TS算法中的每个标签都要一个杂度。-15-3.2.2询问树算法（算法）算法则是将所有复杂运算交由阅读器处理，标签始终处于“无记忆”状态，但在标签位数较长时搜索范围很大，因此其应用受到一定限制。查询树协议（Query（QT）protocol）是一种确定性的防碰撞协议，roundsofqueries个包含特定前缀（prefixpID号拥有相同的前缀p时，前缀p的前面再附加上0或者1能唯一的识别每一个标签。但是当标签的ID号都非常相近时，应用方法，标签发生碰撞的几率将越来越大。每个标签都有自己的前缀匹配电路，阅读器发送长度为m的匹配前缀（prefixID号前mbit和prefixID号；如果有多个标签同时应答即发生碰撞，此时阅读器将prefix增加1位0或（即m+l位）作为新的prefix’进行查询，直到仅1个标签响应为止。QueryID信息上加上0或1继续寻呼[4][5][6]。3.2.3改进的混合查询多叉树防碰撞算法改进的混合查询多叉树防碰撞算法采用曼彻斯特（Manchester下优化：（1）采用八叉树查询即匹配前缀的后3位，提高算法的效率。（283位生成8位相应信息。当回答阅读器命令时不仅是标签的ID号，还包含了标签的解决碰撞的信息。该算法可以有效减少碰撞和询问次数。（3ID式为8bit匹配前缀的后3位形式+剩余ID号。-16-步骤1阅读器发送请求命令request（NULL）作用范围内的所有标签检索前3位ID号并记作AjBj。当序列计数器值与Bj相等时序列生成器将生成10构成8位连续序列Cj的碰撞信息。标签将以Cj+剩余ID号作为对阅读器的应答信息并返回，阅读器根据返回的标签信息其中的碰撞信息Cj，判断出标签信息并入栈，此时栈T生成相应Φ。步骤2阅读器取栈Q数据生成匹配前缀码prefix，prefix高位为栈T中数据，低位为栈Q中数据，发送询问命令request（prefix3位ID号将生成8位序列及剩余ID号构成应答信息。8位序列信息没有碰撞而后位仅有1位发生碰撞，则阅读器发送rea命令读取标签信息，并使其执行quite命令进入静默状态。8位序列生成标签信息压入栈相同的prefix压入栈T。步骤3阅读器取栈Q数据生成匹配前缀码prefixrequest（prefix’Active状态并且前缀匹配码匹配的标签进行应答。判断是否有碰撞发生，如果没有碰撞阅读器读取标签信息，并使其静默。如果有碰撞发送，则返回步骤2。步骤4判断栈是否为空，如果不为空，阅读器根据prefix及栈信息构成新的prefix3；栈为空则算法结束。3.2.4二进制树搜索算法（BS算法）在BS采用二叉树查找的方法，从作用范围内的标签中筛选唯一一个标签进行通信。二进制树形搜索又称读写器控制法，其前提是要辨认出阅读器中数据碰撞的准确位置，因此选用合适的位编码方法很重要。Manchester编码的位窗值由所以为二进制树搜索算法所采用。二进制树防冲突算法的基本思想是将处于冲突的标签分成左右两个子集0-17-和1，先查询子集0，若没有冲突，则正确识别标签，若仍有冲突则再分裂，把子集0分成00和010按此步骤查询子集1。图3.3二进制树算法模型如下：读写器每次查询发送的一个比特前缀p0p1^pi，只有与这个查询前缀相符0或1，读写器中设有一个队列Q来补充前缀，这个队列Q用0和1来初始化，读写器从Q中查询前缀并在每次循环中发送此前缀，当前缀p0p1^pi是一个冲突前缀,读写器就把查询前缀设为p0p1^pi，把前缀p0p1^pi放入队列，读写器继续这个操作直到队列Q为空，通过不断增加和减少查询前缀,读写器能识别其阅读区域内的所有标签。二进制树搜索算法类似于二分法：REQUEST+SELECT+READ_+uNSELECT。算法要点如下：（1）读写器发送作为查询标（REQUEST）的参考ID自己的ID与之相比较，小于或等于就回送自己的ID；（2ID的碰撞位置零。重复若干次之后就可以找到一个确定的ID；（3）将确定的ID用SELECT发送给所有的电子标签，只有选中的标签回应READ—DUNSELECT不再响来。-18-此算法的特点：具有较高的稳定性，属于TDMA方式，易于用软件实现，吞吐率最高可达36.4IDID超过一定限度时，这种算法将不再适用。3.2.5DynamicBinary（DBS）算法DynamicBinarySearchBinarysearch基础上提出的。国际标准ISO14443A所推荐的防碰撞算法就是动态二进制搜索防碰撞算法。率。实际上，经过对阅读器和单个电子标签之间数据流的分析（如图3.7X-10各位不包含给电子标签的补充"1""0"（本文举例中全置1这些信息可不必发送。电子标签响应的序列号的～X各位不包含给阅读器的中阴影部分）是多余的，除这部分冗余数据可以使系统的传输效率提高一倍。图3.4信息交换数据流图动态二进制搜索算法的具体操作流程为：1.如果是n位二进制ID代码，开始某个时隙k由阅读器发送REQUEST（）命令，所有ID代码都小于或等于（）阅读器工作区域内的所有标签应答。2.检测阅读器收到的信号，如果为空表示空闲，阅读器范围内没有标签；如果只有一个标签应答，执行SELECT和操作，读写完成后的标签执行UNSELECT命令，然后重新进行下一次REQUEST命令。3.如果标签个数大于或等于2，则发生碰撞，利用Manchester编码按位识-19-"0"在发生碰撞的这些标签中再次进行REQUEST命令。4.每次顺利读取某个标签之后，阅读器将回到起始寻呼命令，再次发送REQUEST命令（）k个时隙内发生碰撞的所有标签识别完以后，再识别后来到达阅读器工作区域内的标签。假设阅读器周围存在着四个电子标签、B、C、，并且它们的ID分别为简易操作流程如表3.2所示。3.2.6基于状态仲裁的锁位防碰撞算法分成3种状态，进行相应搜索，当只有2个准备态时直接识别出2个标签。基于状态仲裁的锁位防碰撞算法--EDBS（EnhanceDynamicBackBinarySearch2个方面对已有算法进行改进：（1）状态仲裁思想,3标记状态为去活态，对于每一次搜索时，符合请求号的标签标记状态为准备态，22完后再把休眠态的标签状态转为准备态，并继续进行搜索。（2）锁位处理由于实际应用中标签的卡号长度一般在8Byte~10Byte碰撞运算，这种改进算法在动态后退式的基础上，再一次减少数据的冗余位。3.2.7自适应分裂树算法（AST算法）自适应分裂树（AdaptiveSplitting，AST）算法，其基本思想在于：在-20-碰撞发生的时隙内，结合碰撞集规模估计的结果，阅读器反馈碰撞指令（COLLISION）时附带一个分裂规模（SplitBranchScale，SBC）参数，目的是将碰撞标签均匀地划分到SBC个子集之中，直至出现可识别标签。该算法在碰撞集规模较大时会选择大的SBC值碰撞集规模变小时，算法会选取较小的SBC值，以减少空闲时隙。通过自适应的调整方式，获取高的系统效率。表3.3动态二进制搜索算法的操作流程实例AST算法的具体实现流程可描述如下：在所有标签内实现一个计数器（counter）指令后，所有标签初始化counter值为0；阅读器发出问询（REQUEST）指令后，仅counter等于0的标签可以应答：若出现碰撞，阅读器通过碰撞集估计算法，得到当前碰撞标签规模为Ⅳ，采用线性模型SBC=SBC_factor*N计算出SBC（分裂规模参数）值，并发送反馈指令COLLISIONSBCcounter值为0上轮应答节点，碰撞集节点）激发一个随机数发生器并将返回值对SBC取余，然后将计数器counter值增加该取余结果，而其他节点的计数器值增加SBC-1。SUCCESSSUCCESSIDLE1默（SILENCE）态，在本次识别流程中不再响应阅读器。循环执行，即可以完-21-成所有节点的识别。3.2.8非确定性防碰撞算法的比较表3.4确定性防碰撞算法比较算法成功识别一个标签需要成功识别所用标签需要成功识别所用标签中传类型TS发送Request命令次数12mi发送Request命令次数inm2i输的中信息量inmk2i1n2nn!nnk22BS1n2nnnnk!22knknk-22-4总结及展望标签冲突是RFIDALOHA法和二进制树搜索算法以及在此基础上发展起来的其他一些比较重要的防碰撞算法的分析比较，可以看出：（1）ALOHA算法实现较简单，但是存在错误判决问题，其信道利用率最大为36％，在标签数目不大的场合，可以用到时隙ALOHA法和DFSA