基于ALOHA算法的防碰撞算法分析射频识别论文

《基于ALOHA算法的防碰撞算法分析射频识别论文》由会员分享，可在线阅读，更多相关《基于ALOHA算法的防碰撞算法分析射频识别论文（33页珍藏版）》请在装配图网上搜索。

1、【摘要】RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数据通信，从而达到自动识别的目的。随着RFID技术的发展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。在各种已出现的算法当中，主要分为基于ALOHA的防碰撞算法和基于二进制防碰撞的算法，本文分为三个方面，首先是基于ALOHA的防碰撞算法的理论研究比较，其次着重将现有的二进制树算法进行了归纳，汇总为基本算法、动态算法、退避式算法三类，阐述了各个算法的思路，并对其进行了性

2、能评价；最后，在现有的三类防碰撞算法的基础上，提出了一种新的改进型二进制树算法，该算法识别速度快，执行效率高，极大的改进了识别效果。【关键词】：射频识别；防碰撞算法比较；新型二进制树算法正文：1. 基于ALOHA算法的防碰撞算法分析 对于RFID系统来说TDMA法在防碰撞中应用量最大。TDMA法又分为标签驱动法和阅读器驱动法，标签驱动法中主要有代表性的算法是基于ALOHA的防碰撞算法。主要有ALOHA算法、时隙ALOHA算法、动态时隙ALOHA算法、优化的帧时隙(AFSA)算法和EDFSA算法。下面对这几种算法进行分析比较。11纯ALOHA算法 首先纯ALOHA算法是一种非常简单的时分复用算法

3、，用于实时性不高的场合，只能用于只读标签中，这类标签只存储一些标签的序列号等数据。这种算法多采取“标签先发言”的方式，即标签一进入阅读器的阅读区域就自动向阅读器发送其自身的ID信息。并且在一个周期性的循环中将这些数据不断地发送给阅读器，数据的传输时间只是重复时间的一小部分，以致在传输之间产生相当长的间歇。各个标签的重复时间之间的差别很小，两个标签以一定的概率在不同的时间段上设置它们的数据，使数据包传送时不发生碰撞。对同一个标签来说它的发送数据帧的时间也是随机的。ALOHA算法的基本思想是在标签发送数据的过程中，若有其他标签也在发送数据，那么发生信号重叠从而导致完全碰撞或部分碰撞。图1-1给出了

4、ALOHA算法标签发送数据部分碰撞和完全碰撞情况的示意图。标签1B标签标签1比哦啊标签2标签3 接收 部分碰撞 完全碰撞 图1-1纯ALOHA算法示意图阅读器检测接收到的信号来判断有无碰撞。一旦发生碰撞，阅读器就发送命令让标签停止发送，随机等待一段时间后再重新发送以减少碰撞，如果没有碰撞，阅读器发送一个应答信号给标签，标签从此转入休眠状态。而对于无接收功能的标签，标签收不到阅读器发送的碰撞信息或者应答信息，在检测期间一直重复地发送自己的信息，直到识别过程结束。纯ALOHA存在的一个严重问题是存在错误判决的问题，即对同一个标签，如果连续多次发生碰撞，这将导致阅读器出现错误判断，认为这个标签不在自

5、己的作用范围。纯ALOHA存在的另一个问题是数据帧的发送过程中发生碰撞的概率很大。纯ALOHA算法的标签读取过程可以总结如下：(1)各个标签随机地在某时间点上发送信息。(2)阅读器检测收到的信息，判断是成功接收还是发生碰撞。(3)标签在发送完信息后等待随机长时间再重新发送信息。(4)若假设一帧信息的长度为To，起始时间为。则当另一帧的起始时间满足关系式(3-1)时碰撞发生，即： （1-1）为了了解纯ALOHA算法的标签读取过程，下面分析它的标签读取性能。为了分析方便首先定义如下两个参数：(1)吞吐率S：代表有效传输的实际总数据率，即单位时间内标签成功完成通信的平均次数。(2)输入负载G：表示发

6、送的总数据率，即时间内标签平均到达次数。因此，吞吐率S可 以表示为输入负载G与传送成功率的乘积，即 （1-2）其中是到达的标签能成功完成通信的概率。由概率论知识可知，每秒钟发送的信息帧的数目服从泊松分布，因此t秒钟发送行个数据帧的概率为： （1-3）其中为每秒钟平均发送的总的信息帧数，此时输入负载为： （1-4）则在时间内没有发送信息的概率为: （1-5）这样，就可以得到纯ALOHA算法的吞吐率为： （1-6）当G=05时，吞吐率S达到最大值0184。当G0.5时性能急剧恶化，系统进入不稳定状态。因为必须尽量使G不要太大，这样只能改小,同时也要注意由于标签自身的问题不能检测碰撞，因此只能重发，

7、重发次数不一定越多越好，因为重发次数多了，会使得输入负载过大，碰撞率增加，因此要选适当的退避区间。 由上分析可知ALOHA算法的主要特点是各个标签发射时间不需要同步，是完全随机的，当标签的数量不多时它可以很好地工作。缺点是数据帧发送过程中碰撞发生的概率很大，碰撞周期是，而且由于受标签的费用及其大小的限制，它不能自己检测碰撞，只能通过接收阅读器的命令判断有无碰撞。当数据业务繁忙，发生碰撞的概率增多时，性能急剧下降，信道最佳利用率只有184。但是ALOHA法由于它实现起来比较简单，能够作为防碰撞的方法，适用于只读标签系统。12时隙ALOHA算法使纯ALOHA算法对比较小的吞吐率最佳化的途径就是时隙

8、ALOHA(SlottedALOHA)算法。如图33所示，这种算法在ALOHA算法的基础上把时间分成多个离散的时隙(slot)，并且每个时隙的长度要大于标签回复的数据长度，每个时隙长度由系统时钟控制，各控制单元必须与此时钟同步。对于RFID系统，标签只在规定的同步时隙内才能传输数据包，对所有的标签所必须的同步由阅读器控制，标签只能在每个时隙内发送数据。标签1 标签2标签3 接收 正确接收 完全碰撞 图1-2时隙ALOHA算法示意图从上图可以看出，每个时隙存在以下三种情况：(1)无标签响应：在此时隙内没有标签发送。(2)一个标签响应：在此时隙内只有一个标签发送，标签能够被正确识别；(3)多个标签

9、响应：在此时隙内有多个标签发送，产生碰撞。与纯ALOHA算法的分析方法相同，可以得到在一个时隙起点处没有其他标签发送信号的概率为： (1-7)因此，可以得到时隙ALOHA算法的吞吐率为： (1-8)当G=1时，系统的吞吐率可以达到最大值0368，由此可见时隙ALOHA算法的系统吞吐率比纯ALOHA算法提高了1倍。缺点是需要同步时钟，且标签能够计算时隙。13帧时隙ALOHA算法 ALOHA算法的另一种扩展算法是帧时隙(Framed Slotted)ALOHA算法，简称FSA算法。它是在时隙ALOHA算法的基础上把个时隙组成一帧，标签在每个帧内随机选择一个时隙发送数据，如图1-3所示。这种算法适于

10、传输信息量较大的场合，与时隙ALOHA算法相同，FSA算法也需要一个同步开销。一个帧包含多个时隙，每个时隙的长度要足够让一个标签回答完，具体时间由阅读器定义。在阅读器发送读取命令后，要等待一定时间等待标签的回答。当在一个时隙中只有一个标签回答时，阅读器可以分辨出标签；当在一个时隙中没有标签回答时，跳过此时隙：当在一个时隙中有多个标签时，发生碰撞，需要重新开始读取过程。帧2帧1 Slot1Slot4Slot1Slot4FSA算法存在的缺点是，当标签数量远远大于时隙个数时，读取标签的时间将会大大增加，而当标签个数远远小于时隙个数时，会造成时隙的浪费。总的来说，FSA算法的主要特点如下：(1)把个时

11、隙打包成一帧；(2)标签在每个时隙中随机选择一个时隙发送一次信息；(3)该方法需要阅读器和标签之间的同步操作，每个时隙需要与阅读器进行同步，每一帧的最大时隙数为某默认值，需要预先设定。14动态帧时隙ALOHA算法 时隙ALOHA算法的吞吐率在输入负载G为1时达到最大。如果输入负载小于l，则会造成空时隙的数目增加，浪费宝贵的标签读取时间；如果输入负载大于l，则会造成碰撞的时隙数增加，造成处于一个单独时隙发送成功的标签概率比较小，因此同样需要准备更多的时隙，这样同样会降低系统的实时性。弥补的方法就是使用动态的时隙数，这是一种改进的FSA算法。该算法中，阅读器能动态改变(增加或减少)下一次阅读循环中

12、每帧的时隙个数，这种算法称为动态帧时隙(DynamicFramed Slotted ALOHA)算法，简称DFSA算法。一帧内的时隙数目能根据阅读区域中的标签数目而动态改变，或者通过增加时隙数以减少帧中的碰撞数目，或者在空时隙很多时减少以节省时间。该算法的具体步骤如下：(1) 标签进入阅读器的读取范围后，接收到阅读器的开始识别命令后进入识别状态，并且在开始识别命令中包含了初始的时隙数。(2)进入识别状态的标签随机选择一个时隙(内部伪随机数发生器产生)，同时将自己的时隙计数器复位为1；(3)当标签随机选择的时隙数等于时隙计数器时，标签向阅读器发送数据，当标签的时隙数不等于时隙计数器时，它将保留自

13、己的时隙数并等待下一个命令。此时，可能出现下列情况：情况l：当阅读器没有检测到标签的响应时，将发送结束时隙命令。处于识别状态而没有响应的标签接收到命令后把自己的时隙计数器加1，然后重复步骤(3)。情况2：当阅读器检测到多个标签的响应碰撞时，将发送结束时隙命令。处于识别状态的标签接收到命令后把自己的时隙计数器加l，然后重复步骤(3)。情况3：当阅读器接收到一个标签的正确回复时，阅读器将发送下一时隙命令，处于识别状态的所有标签的时隙计数器都加l，刚响应过的标签收到正确的休眠命令后将进入休眠状态，否则标签将继续停留在识别状态，跳到步骤(3)继续循环下去。(4)当阅读器检测到时隙数量等于命令中规定的循

14、环长度时，本次循环结束。阅读器发送开始识别命令进入步骤(2)开始新的循环，新的循环长度是阅读器根据前一次循环中碰撞数量动态优化调整后产生的。关于动态调整循环长度的方法也有很多不同的算法，一种是根据个时隙中发生碰撞的时隙数、没有响应的时隙数等来判断的。如当发生碰撞的时隙数大于某一上限值时，将每帧的总时隙数增加，当发生碰撞的时隙数小于某一个下限值时将每帧的总时隙数减少。另外一种算法是，阅读器用初始一帧内时隙数N(N较小)开始发送读取命令，如果在这次循环中没有一个标签回答，阅读器就增加一帧内时隙数，直到至少一个标签被识别，然后阅读器再从初始时隙数N开始新一轮循环。在DFSA算法中，每帧中的时隙个数都

15、是动态产生的，因此解决了FSA算法中时隙的浪费问题。由此可以看出这种算法简单、易实现，且能充分适应标签数量的动态变化，非常适合在RFID技术中使用t241。15优化的帧时隙ALOHA算法 优化的帧时隙(AdvancedFramedSlotted)ALOHA简称为AFSA算法。这种算法使用可动态调整时隙的数量。AFSA算法通过估计标签的数量来确定合适的帧大小，以此来识别标签。所以它比FSA算法更有效。 在AFSA中，阅读器利用读循环的结果：空时隙的数量、有一个标签的时隙数量和发生碰撞的时隙数量的信息来预测标签的数量。AFSA算法预测标签数量的公式是切比雪夫不等式提出的随机变量X的随机试验结果在某

16、个特定环境非常接近于彳的期望值。预计标签数量时就是利用这个值。这样通过度量真实结果与预期结果之间的差异并使差异最小化来预测标签的数量。 在AFSA算法中，假设标签在其它读循环中己经响应。AFSA算法计算通过改变帧大小要读到99的标签需要多少时隙，然后它选择时隙数量最少的帧。因为AFSA算法需要估计标签数量并决定帧大小来最小化发生碰撞的概率，因此它比上述普通的ALOHA的算法更有效。然而，AFSA算法也存在与其它上述算法类似的问题，就是随着标签数量的增加，阅读器不能无限地增加帧大小。16 增强型动态帧时隙算法 上述的帧时隙ALOHA算法通过改变帧的大小来增加标签识别效率。然而随着标签数量的增加到

17、超过帧的大小，标签碰撞的概率依然会急剧增加。如果不限制响应标签的数量，使之达到与帧大小近似相等的数量，那么这种问题就不能得到很好的解决。因而出现了一种增强型动态帧时隙ALOHA(EnhancedDynamicFramed SlottedALOHA)算法。在EDFSA算法中，阅读器首先估计未读标签的数量。当标签太多时，阅读器把这些标签分簇，在一次识别过程中，只有_簇的标签可以应答阅读器，这样就能在标签太多时降低标签的碰撞率。首先阅读器进行广播，传输标签分簇的数量和一个随机号码给这些标签。接收到这个需求的标签从收到的随机号码和它的序列号中产生一个新号码，然后用这个新号码除以这个标签分簇的数量，只有

18、当余数是零时，这个标签才响应阅读器。当估计的未读标签数小于某个下限时，阅读器调整帧大小，而不是对未读标签进行分簇。这就意味着阅读器广播一个阅读器请求时有：帧的大小，一个随机数和标签分簇数量为l。经过几次读循环后，阅读器估计未读标签的数量并调整帧大小。如此反复直到读到每个标签。EDFSA算法读标签用的时隙数增长是线性的，无论有多少个未读标签，EDFSA都能把系统效率平均维持在346至368之间。当标签数量是1000时，EDFSA算法的效率是帧时隙的两倍，是动态时隙ALOHA算法的185倍。如果标签更多，这种优势就越明显。17各种基于ALOHA算法的比较(1) 纯ALOHA法算法应用于实时性不高的

19、场合，适用于只读标签，实现起来比较容易。但是它不能很好的防碰撞，防碰撞周期较长，当标签数量很多时性能急剧下降。信道利用率只有184，且能出现错误判决，当一个标签在很长时间没有被正确识别，可能被误判为不在阅读范围内。(2)时隙ALOHA算法是对纯ALOHA算法的改进，改进后信道利用率达到368，为ALOHA法的两倍。但是它需要精确的同步。(3)帧时隙ALOHA算法的是在时隙ALOHA算法的基础上把个时隙组成一帧，标签在每个帧内随机选择一个时隙发送数据。这种算法适于传输信息量较大的场合，但也需要一个同步开销。(4) 动态帧时隙ALOHA算法中，一个帧内的时隙的数目能根据阅读区域中的标签数目而动态改

20、变，从而节省时间。(5)EDFSA算法通过估计没有读到的标签的数量，从而确定合适的帧大小，以达到效率的最大化和降低发生碰撞的概率。2. 基于二进制算法的防碰撞算法分析211基本概念在RFID防碰撞算法中，二进制树算法是目前应用最广泛的一种，之所以称为“二进制树”，是因为在算法执行过程中，读写器要多次发送命令给应答器，每次命令都把应答器分成两组，多次分组后最终得到唯一的一个应答器，在这个分组过程中，将对应的命令参数以节点的形式存储起来，就可以得到一个数据的分叉树，而所有的这些数据节点又是以二进制的形式出现的，所以称为“二进制树”。 为了便于描述算法，声明一些基本概念如下：首先，在RFID系统当中

21、，每个应答器都是独一无二的，它们的独立性通过唯一的自身序列号来体现，该序列号在不同的标准中有不同的名称，如EPC标准中称其为电子产品代码EPC，即英文ElectronicProduct Code的缩写，IS014443标准中称其为唯一标识码UID，即英文Unique Identmer的缩写。事实上，这些都是对应答器序列号的名称描述，因为下文涉及到的防碰撞算法是普遍意义上的，既包括了EPC标准中的规定，也包括了ISO标准中的规定，因此在本文对普遍意义上的防碰撞算法的描述过程中，统一用序列号SN(SerialNumber)来描述上述概念，同时，序列号的长度，格式，以及编码方式也是各个标准各自差异的

22、，为了说明的便利，统一定义为8位长度的二进制码。如图21所示。图21 应答器序列号数据格式读写器与应答器之间进行数据交换时，往往要传输序列号的部分或者全部位，此时的传输顺序定义为：先发送低位，再发送高位。在读写器或者应答器内部，对数据进行比较时，遵循这样的原则，即按位依次比较，先比较低位，再比较高位，约定01，根据这个比较顺序，在判断大小时，低位数据优先，即两数A，B相比较，从低位开始的第一个不相等位的大小决定了两数的大小，只有当两个数的全部位均相等时，两数才相等。212性能指标定义碰撞解决时期CRI，即Collision Resolution Interval，即解决一个读写器工作范围内碰撞

23、所需要的时隙数，对二进制树算法的评价，一些常用的性能指标如下所示：首先是算法执行效率，定义如下：在算法执行过程，一共个时隙，识别了n个应答器，则=n/表示算法的执行效率。分析如下：n=l，显而易见，在第一个时隙内不发生碰撞，可以成功识别该应答器，=1。n2，由于应答器序列号的唯一性，将有碰撞发生，在一个时隙内发生碰撞的概率p是一个随机事件，在n个应答器信息包中i个发生碰撞的概率为： （2.1）给出i个碰撞，则CRI的长度为：（2.2）其中1是n个信息包最初的一个时隙，是i个碰撞的顺利传输的时隙，是n-i个无碰撞传输的时隙。由上式可知，是逐渐递归的，通过递归可得：根据式(2.3)，上式可化为：由

24、此可见，是关于p的函数，则=n/也是关于p的函数，一般情况下，可以参考二项分布，将p取为12。算法的第二个重要的性能指标是稳定性，显然，基于TDMA的二进制树防碰撞算法是沿着时间轴线来执行协议的，有一系列的碰撞解决时期CRI，定义一个随机变量，表示第k个CRI的长度，这些形成一个马尔可夫链(Markovchain)，因为第个CRI的长度由它开始的第一个时隙传输的信息，也就是在k个CRI区间内到达的信息包决定的，所以，如果马尔可夫链满足遍历性分布，那么这个系统就可以说是稳定的。马尔可夫链遍历性分布要满足下列两个条件：这里有： 也就是n个信息包从发生碰撞开始传输的CRI区间长度的数学期望，是在一个

25、时隙内到达这个系统信息包的期望值，该过程属于泊松过程。一般来说，在二进制树防碰撞算法中，系统都能够满足马尔可夫链的两个遍历性分布条件，即作为一种确定型的算法，二进制树防碰撞算法是稳定的。算法的第三个重要性能是系统通信复杂度，显而易见，系统的通信双方是读写器与应答器，则通信复杂度也应该从这两方面着手考虑，即读写器与应答器各自发送的数据位的位数。该指标的评价标准是基于能量消耗的角度的，即发送的数据信息量越少，则整个系统消耗的能量也越少，这显然是一个理想的效果。213算法分类在基本的二进制树搜索算法的基础上，有多种形式的二进制树搜索算法，它们之间主要的区别在于命令的数据形式，主要有两点。(1)命令参

26、数是1bit数据，还是多bit数据。(2)命令参数长度是固定的，还是变化的。图22是一个二进制树搜索算法的分类图，在基本二进制树的基础上，按照命令参数分为1bit和多bit，根据传输的命令参数的长度分为定长二进制树和动态二进制树两种，根据二进制树遍历时是一轮前进到底的还是退避返回的分为前进二进制树和退避二进制树两种。需要说明的是，这只是一个大略的分类法，主要目的在于说明二进制树分类的基本原则。事实上，分类所得的这些算法中也有互相重合的，如动态二进制树算法既可以采用前进思路，也可以采用退避思路。另外，在具体应用时，可能还存在多种不同的说法，如lbit长二进制树中还有修正二进制树MBBT，加强二进

27、制树EBBT等区别。图22二进制树算法分类22基本二进制树防碰撞算法221算法思路定义两个具有普遍意义的命令来描述算法：(1)请求命令Request(SN)：该命令携带一个参数SN，应答器接收到该命令，将自身的SN与接收到的SN比较，若小于或者等于，则该应答器回送其SN给读写器。注：Request(SN)初始值设为Request(11111111)。(2)休眠命令Sleep(SN)：该命令携带一个参数SN，应答器接收到该命令，将自身的SN与接收到的SN比较，若等于，则该应答器被选中，进入休眠状态，也即是不再响应Request命令，除非该应答器通过先离开读写器工作范围再进入的方式重新上电，才可以

28、再次响应Request命令。基本二进制树算法的流程图如图23所示：图23基本二进制树算法流程基本二进制树算法的步骤如下：(1) 应答器进入读写器工作范围，读写器发出一个最大序列号，所有应答器的序列号均小于该最大序列号，所以在同一时刻将自身序列号返回给读写器。 (2) 由于应答器序列号的唯一性，当应答器数目不小于两个时，必然发生碰撞发生碰撞时，将最大序列号中对应的碰撞起始位设置为O，低于该位者不变，高于该位者设置为l。(3) 读写器将处理后的序列号发送给应答器，应答器序列号与该值比较，小于或等于该值者，将自身序列号返回给读写器。(4) 循环这个过程，就可以选出一个最小序列号的应答器，与该应答器进

29、行正常通信后，发出命令使该应答器进入休眠状态，即除非重新上电，否则不再响应读写器请求命令。也就是说，下一次读写器再发最大序列号时，该应答器不再响应。(5)重复上述过程，即可按序列号从小到大依次识别出各个应答器。注：第五步时，从步骤1开始重复，也就是说，读写器识别完一个应答器后，将重新发送原始的最大序列号。222实例演示根据上述分析，下面给出一个基本二进制树搜索算法的实例演示，如图24所示。假设RFID系统中有一个读写器R，四个应答器Tl(10100101)，T2(10l01101)，T3(11010101)，T4(11101101)，在某一时刻，四个应答器同时进入读写器的工作范围之内，读写器发

30、出命令，四个应答器同时响应，由于其序列号SN的唯一性，将发生应答器碰撞，从而启动防碰撞循环，分析如下：图2.4 基本二进制树算法实例注：图中共有四轮循环，依次识别出四个应答器，分别以不同格式的线条表示，并加有循环轮次的数字标识。(1)启动第一轮循环，读写器发送Request(1lll1111)命令，所有应答器响应该命令，将自身序列号与该SN(1l1l1111)比较，均小于该值，于是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为lXXXXl0l，其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0，低于该位者

31、不变，高于该位者置l，得到11ll0l01，作为下一次Request命令携带的参数值，即Request(11110l01)。(2)读写器发送Request(11110101)命令，所有应答器响应该命令，将自身序列号与该SN(11110l01)比较，其中T1(10l00101)，T3(1l010101)的序列号小于该值，则Tl，T3返回自身序列号给读写器，在读写器接收端发生碰撞，读写器检测到返回数据为1XXX0l01，读写器做如下处理：将碰撞起始位D5位置0，低于该位者不变，高于该位者置l，得到11l00l01，作为下一次Request命令携带的参数值，即Request(11100101)。(3

32、)读写器发送Request(11100101)命令，所有应答器响应该命令，将自身序列号与该SN(111 00l01)比较，其中Tl(10100l01)的序列号小于该值，则Tl返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为10100101，读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即Sleep(10100101)。(4)读写器发送Sleep(10100101)命令，所有应答器响应该命令，将自身序列号与该SN(10l00111)比较，其中T1(10l00101)的序列号等于该值，则T1执行该命令，进入休眠状态，即除非重新上电，否则不再响应Reques

33、t命令。(5)启动第二轮循环，读写器发送Request(111l1111)命令，除T1外所有应答器响应该命令，将自身序列号与该SN(11111l11)比较，均小于该值，于是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1XXXXl01，其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0，低于该位者不变，高于该位者置1，得到11110101，作为下一次Request命令携带的参数值，即Request(11110101)。(6)读写器发送Request(11110101)命令，除Tl外所有应答器响应该命令，将

34、自身序列号与该SN(11l10101)比较，其中T3(1l010l01)的序列号小于该值，则T3返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为110l0101，读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即Sleep(11010101)。(7)读写器发送Sleep(1l010101)命令，所有应答器响应该命令，将自身序列号与该SN(110l0101)比较，其中T3(11010101)的序列号等于该值，则T3执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。(8)启动第三轮循环，读写器发送Request(11111111)命令

35、，除T1，T3外所有应答器响应该命令，将自身序列号与该SN(1111ll11)比较，均小于该值，于是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1X101101，其中x表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D7位置0，低于该位者不变，高于该位者置1，得到10101101，作为下一次Request命令携带的参数值，即Request(10101101)。(9)读写器发送Request(10101101)命令，除Tl，T3外所有应答器响应该命令，将自身序列号与该SN(10101101)比较，其中T2(101011

36、01)的序列号等于该值，则T2返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为l0101101，读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即Sleep(10101101)。(10)读写器发送Sleep(10101101)命令，所有应答器响应，将自身序列号与该SN(10101101)比较，其中T2(10101101)的序列号等于该值，则T2执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。(11)启动第四轮循环，读写器发送Request(1l111111)命令，除Tl，T3，T2外所有应答器响应该命令，将自身序列号与该SN(1

37、1l1l111)比较，均小于该值，则所有应答器均返回自身序列号给读写器，因为只有应答器T4返回数据，所以在读写器接收端不发生碰撞，读写器检测到返回数据为11101101，读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即Sleep(1l1 01101)。(12)读写器发送Sleep(1ll 01101)命令，所有应答器响应，将自身序列号与该SN(11101l01)比较，其中T4(1l1 01101)的序列号等于该值，则T4执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。223性能评价假设工作范围内有N个应答器存在，通过基本二进制树搜索算法进行防碰撞操作

38、，依次识别出所有应答器。循环次数定义为在整个防碰撞循环过程中的循环轮次，也即是二进制树的遍历次数。根据前面的分析可知，做为一种确定性的算法，基本二进制树一轮循环总能识别出一个应答器，所以在n个应答器的前提下，经过n次循环可以识别出N个应答器，所以整个过程中的循环次数为n搜索次数定义为算法执行命令的次数。也即是二进制树的节点数目。该值可以用式子来表示，其中Integ表示取整。通信时间t定义为数据交换的时间，也即是命令执行的时间。假设有n个应答器，从读写器到应答器的传输时间为tl，反之为t2总时间为t，则传输的总时间t可以用式2.8来表示：数学归纳法证明如下：假设只有一个应答器，则读写器发送命令，

39、应答器响应，无碰撞，识别出应答器。假设有两个应答器，则读写器发送命令，两个应答器响应，发生碰撞，为第一次过程，该时间为：读写器修改命令参数，发出命令，仅一个应答器响应，则识别出该应答器，这一次过程时间与前一次一致，读写器再发送命令，最后一个应答器响应，得到识别，时间也是一样的，则总时间为：当有n个应答器时，假设识别总时间为：则当n+1个应答器时，读写器首先发送命令，应答器全体响应，发生碰撞，这个过程时间为：读写器修改命令参数，发出命令，k个应答器响应，余下p个不响应，k+p=n+l，则识别出该k个应答器需要时间为：再识别余下p个需要时间为：则这两者时间之和为：加上前一次的t1+t2，总时间为：

40、得证。因为基本二进制树算法中每次传输的序列号SN长度相同，所以有：基本二进制树搜索算法是所有二进制树算法的基础，分析基本二进制树搜索算法的性能可知，对于固定数目的应答器，二进制树算法的性能主要取决于二进制树的节点数目和单次传输命令参数的时间，事实上，二进制树的节点数目与应答器分组的思路是直接相关的，而单次传输命令参数的时间则取决于该命令包含的数据位数。所以，要改善二进制树算法的性能，就必须从这两点着手，现有的二进制树搜索算法有很多种，它们都是在基本二进制树搜索算法的基础上加以改进得来的，根据前述分析，主要的改进思路有两个：(1)减少每次通信过程中的数据传输位数。(2)减少应答器分组的询问次数。

41、本文中，定义根据第一个思路得来的算法为动态二进制树，它的一个典型应用为ISOl4443 TYPE-A二进制树搜索算法。定义根据第二个思路得来的算法为退避式二进制树，它的一个典型应用为EPC二进制树搜索算法。23动态二进制树防碰撞算法231算法思路定义两个具有普遍意义的命令来描述算法：(1)请求命令Request()，该命令携带一个参数SN，长度为，应答器接收到该命令，将自身的SN中的前1x位与接收到的比较，若两者相等，则该答器返回其SN的剩余位给读写器。注：Request()初始值设为Request(1l111111)，约定当参数值为全1时，应答器返回完整序列号。(2)休眠命令Sleep(SN

42、)，该命令携带一个参数SN，应答器接收到该命令，将自身的SN与接收到的SN比较，若等于，则该应答器被选中，进入休眠状态，也即是不再响应Request命令，除非该应答器通过先离开读写器工作范围再进入的方式重新上电，才可以再次响应Request命令。动态二进制树算法的流程与基本二进制树算法是一致的，它们的区别在于：基本二进制树算法中，应答器返回完整序列号，而动态二进制树算法中，应答器只返回序列号的有效部分；同样，基本二进制树算法中，读写器生成新Request命令时，其命令参数长度是固定为8位的，而动态二进制树算法中，该命令参数长度是根据应答器返回的序列号来动态变化的。动态二进制树算法的流程如图25

43、所示：图25动态二进制树算法流程事实上，动态二进制树对基本二进制树的改进是基于如下考虑的，在基本二进制树的分析过程中可见，算法的核心部分即新命令参数的生成，是根据是否发生碰撞，以及碰撞位来决定的，特别是新Request命令参数的生成是由碰撞的起始位来确定的，而碰撞的起始位的得到只需要应答器序列号中包括碰撞起始位在内的部分位即可，把这些位称为序列号的有效位，同样，新Request命令参数也为包括碰撞起始位(设为0)在内的部分位，综合如下：若选择高位加碰撞起始位(设为0)，则算法为应答器序列号对应位小于这些位的数值者，返回剩余低位，若选择碰撞起始位(设为0)加低位，则算法为应答器序列号对应位等于这

44、些位的数值者，返回剩余高位，从而读写器的新Request命令参数与应答器返回的序列号有效部分组合起来，可以得到一个完整的应答器序列号。这两种选择方式并没有本质区别，在本文中，采取其中的一种，即：读写器检测到碰撞后，将碰撞起始位置0，低位不变，从而将碰撞起始位(置为O)加低位作为新Request命令参数，应答器响应，从低位开始比较，若对应位等于该参数，则返回剩余位给读写器，如果只有_个应答器响应，读写器检测到无碰撞发生，则将上一次发出的Request命令参数与应答器返回的剩余位组合起来，作为新的Sleep命令参，该参数也即是刚刚做出响应的这个应答器的序列号。注：如果上一次发出的Request为全

45、l，则表明读写器工作范围内只有一个应答器，此时应答器返回数据为完整序列号，以该序列号作为Sleep命令参数。动态二进制树算法的步骤如下：(1) 应答器进入读写器工作范围，读写器发出一个最大序列号，约定此时所有应答器均返回完整序列号，则同一时刻应答器将自身序列号发回给读写器。(2) 由于应答器序列号的唯一性，当应答器数目不小于两个时，必然发生碰撞。发生碰撞时，将最大序列号中对应的碰撞起始位置为0。低于该位者不变。(3) 读写器将处理后的碰撞起始位与低位发送给应答器，应答器序列号与该值比较，等于该值者，将自身序列号中剩余位发回(4) 循环这个过程，就可以选出一个最小序列号的应答器，与该应答器进行正

46、常通信后，发出命令使该应答器进入休眠状态，即除非重新上电，否则不对读写器请求命令起响应。(5) 重复上述过程，即可按序列号从小到大依次识别出各个应答器232实例演示动态二进制树算法的实例演示如图26所示，基本设置同基本二进制树算法：图26动态二进制树算法实例(1)启动第一轮循环，读写器发送Request(11111111)命令，所有应答器响应该命令，按照约定，命令参数为全1时，所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1XXXXl01，其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0，低于该位者不变

47、，得到0101，则下一次Request命令携带的参数值，即Request(0101)。(2)读写器发送Request(0l01)命令，所有应答器响应，将自身序列号与该SN(0101)比较，其中Tl(10l00101)，T3(110l0l01)的序列号低四位等于该值，则T1，T3返回剩余位给读写器，在读写器接收端发生碰撞，读写器检测到返回数据为lXXX，读写器做如下处理：将碰撞起始位D5位置0，低于该位者不变，得到0010l，作为下一次Request命令参数值，即Request(00l01)。(3)读写器发送Request(00l01)命令，所有应答器响应，将自身序列号与该SN(00101)比较

48、，其中Tl(10100101)的序列号对应位等于该值，则Tl返回剩余序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为l0l，读写器做如下处理：将上一次Request(00l01)命令参数00101与返回数据101组合起来，作为下一次Sleep命令携带的参数值，即Sleep(10100101)。(4)读写器发送Sleep(10100101)命令，所有应答器响应该命令，将自身序列号与该SN(10100101)比较，其中T1(10100101)的序列号等于该值，则Tl执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。(5)启动新一轮循环，重复上述步骤，总计12

49、步后，依次识别出T1，T3，T2，T4，参数变化过程见图26中标示，具体内容不再详述。233性能评价与332基本二进制树实例图比较可知，动态二进制树算法的识别过程中，节点数目，循环轮次都是一样的，但是每次循环过程中，读写器命令与应答器指令所携带的参数都是在动态改变长度的，所以动态算法的优势主要体现在两个方面，一是算法执行过程中数据传输时间；二是算法执行过程中数据信息量。根据分析，算法执行过程中，读写器与应答器传送的数据主体是应答器的序列号，为了便于分析，假定数据交换过程中，双方只传送序列号SN，则在基本算法中，读写器与应答器均传送了序列号全部长度，而在动态算法中，读写器传送序列号的部分位，应答

50、器再传送剩余位，两者组合起来才得到全部的序列号，显然，虽然每次传送时动态算法的数据长度不同，但是在整个算法执行过程中，基本算法传送了两倍序列号，动态算法则只传送了一倍数据量，从而可知，动态算法传送的信息量是基本算法的50，从而数据传输时间也是原基本算法的50在本例中，由于假定了应答器的序列号为8位长度二进制数，所以这个动态变化的优势并不明显，然而，事实上在实际应用中，应答器序列号长度往往是极大的，比如说常见的是96位，在这样的情况下，动态算法的优势就体现出来了。24退避式二进制树防碰撞算法241算法思路退避式二进制树搜索算法是对基本二进制树搜索算法的一种改进，根据23基本二进制树算法的分析可知

51、，每识别一个应答器后，读写器恢复Request命令参数的初始值，重新从二进制树的根部开始执行，对此可以采取退避的思想，即每次识别出一个应答器后，算法返回其上一个父节点，而不返回整棵树的根节点。定义两个具有普遍意义的命令来描述算法：(1)请求命令Request(SN)：该命令携带一个参数SN，应答器接收到该命令，将自身的SN与接收到的SN比较，若小于或者等于，则该应答器回送其SN给读写器。注：Request(SN)初始值设为Request(11ll1111)。(2)休眠命令Sleep(SN)：该命令携带一个参数SN，应答器接收到该命令，将自身的SN与接收到的SN比较，若等于，则该应答器被选中，进

52、入休眠状态，即除非重新上电，否则不再响应Request命令。退避式二进制树算法的流程见图27，基本设置可参考基本二进制树算法：图27退避式二进制树算法流程如图所示，退避式二进制树算法的流程与基本算法的区别在于：基本算法中，一个应答器被识别后，重新启动新循环时，读写器返回整棵树的根节点，获取原始Request命令参数，而退避式算法中，读写器返回上一次发生碰撞节点，获取Request命令参数。事实上，退避式算法的改进是基于如下考虑的，在基本二进制树的分析过程中可见，算法之所以称为二进制树，是因为每次碰撞后，均以碰撞起始位为界，将应答器分为两个部分，形象的看，如同一棵树在进行从根部到主干到树枝的一个

53、不断的分叉过程，所以，分叉也即是分组的理念是二进制树算法的本质所在，根据这一点，算法每次分叉到达末端之后，不再返回根部重新开始分叉，而是返回上一次分叉的节点即可重新开始新的树干，该节点也即是上一次发生碰撞的节点。采用该返回思路的二进制树算法，称为退避式二进制树算法。退避式二进制树算法的步骤如下：(1) 应答器进入读写器工作范围，读写器发出一个最大序列号，所有应答器的序列号均小于该最大序列号，所以在同一时刻将自身序列号发回给读写器。(2)由于应答器序列号的唯一性，若应答器数目不小于两个，必发生碰撞。此时将最大序列号中对应碰撞起始位置为O。低于该位者不变，高于该位者置1。(3)读写器将处理后的最大

54、序列号发送给应答器，应答器序列号与该值比较，小于或等于该值者，将自身序列号发回(4)循环这个过程，选出一个最小序列号的应答器，与之正常通信后，命令该应答器进入休眠状态，即除非重新上电，否则不再响应读写器请求命令。(5)返回上一个发生碰撞的节点，获取该节点对应的最大序列号，重复上述过程，即可按序列号从小到大依次识别出各个应答器242实例演示退避式二进制树算法实例演示如图28所示，其设置参考基本二进制树算法：图28退避式二进制树算法实例(1)启动第一轮循环，读写器发送Request(11111111)命令，所有应答器响应，将自身序列号与该SN(11111111)比较，均小于该值，则所有应答器均返回

55、自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为lXXXXl0l，其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0，低于该位者不变，高于该位者置1，得到1l110l01，作为下一次Request命令参数，即Request(1l1l 0l01)。(2)读写器发送Request(1l110101)命令，所有应答器响应，将自身序列号与该SN(111l0l01)比较，其中T1(10100101)，T3(110l0101)的序列号小于该值，则Tl，T3返回自身序列号给读写器，在读写器接收端发生碰撞，读RFID二进制树防碰掩算法的研

56、究与实现写器检测到返回数据为1XXX0101，读写器做如下处理：将碰撞起始位D5位置0，低于该位者不变，高于该位者置1，得到11l 00101，作为下一次Request命令携带的参数值，即Request(1l100101)。(3)读写器发送Request(11100101)命令，所有应答器响应，将自身序列号与SN(1ll 00101)比较，其中T1(10100101)序列号小于该值，则Tl返回序列号，在读写器接收端不发生碰撞，读写器检测到返回数据为10100l01，做如下处理：将该值作为下一次Sleep命令参数值，即Sleep(10100101)。(4)读写器发送Sleep(10l00l01)

57、命令，所有应答器响应，将自身序列号与该SN(10100ll1)比较，其中T1(10100l01)的序列号等于该值，则Tl执行该命令，进入休眠状态，即除非重新上电，否则不再对Request命令做出响应。(5)启动新一轮循环，重复上述步骤，总计12步后，依次识别出T1，T3，T2，T4，参数变化过程见图28中标示，具体内容不再详述。243性能评价与基本二进制树比较可知，退避式算法每次传送的数据信息量与基本算法是一样的，区别在于，退避式算法的传送次数，也即是所遍历的节点数目比之基本算法大大减少，假设读写器工作范围内有n个应答器，则所需节点数目为而，则可用式子219来表示：数学归纳法证明如下：当读写器

58、工作范围内只有一个应答器时，显然有：假设n个应答器时，有：则当系统中有n+1个应答器时，由于新增加的这个应答器与原来n个应答器的序列号均不相同，为了将其与某个匹配度最高的应答器区分开来，需要在原来二进制树中增加一个节点，由于节点之间仅存在父子关系，且仅通过两条边相连，所以有：得证。25本章小结本章归纳了现有的二进制树防碰撞算法，将其分为三个基本类别，分别讲述了其实现思路，进行了实例演示，并且对其做了性能分析，结果表明，动态算法和退避式算法是对基本算法的两个改进思路，具有各自的优势。3 改进型二进制树防碰撞算法311算法思路PCD的初始化，防碰撞，以及数据交换的流程如图31所示：图31ISOl4

59、443标准TYPE A类型PCD通信全过程如图所示，分为这么几个部分：1PCD与PICC进行符合lSOIECl44432的初始化通信。(1)PCD不断发送请求命令Req，检测工作范围内的PlCC。(2)PICC接收到请求命令Req，返回一个请求命令应答Atq。(3)PCD接收到来自PICC的请求命令应答Atq，表明有PICC存在。(4)PCD对该Atq进行检测，决定下一步动作。此时若Atq携带信息显示，PICC符合ISOl44433，则启动位帧防碰撞循环，否则启动专用的防碰撞循环。2PCD与PICC进行符合ISOIECl44433的位帧防碰撞循环。(1)PCD选择级联层l，发送防碰撞命令Ant

60、icollision。(2)PICC响应防碰撞命令Anticollision，返回其UID的部分或者全部。(3)PCD根据PICC的响应，检测到碰撞，修改Anticollision命令参数，发送防碰撞命令Anticollision。(4)PICC响应防碰撞命令Anticollision，返回其UID的部分或者全部。(5)循环3)4)步。(6)PCD根据PICC的响应，若检测不到碰撞，则发送Select选择命令。(7)PICC接收到Select选择命令，发送选择应答SAK作为响应。(8)PCD对该SAK进行检测，决定下一步动作。若SAK携带信息显示：PICC返回的UID不完整，且未清除级联层数，

61、则应增加级联层数，继续位帧防碰撞循环，即循环2)7)步。若SAK携带信息显示：PICC返回的UID完整，且清除级联层数，但是不符合IS0144434，则PCD发送停止命令Halt，令PICC进入停止状态Halt。若SAK携带信息显示：PICC返回的UID完整，且清除级联层数，并且符合IS0144434，则启动数据操作，即下一个环节3。3PCD与PICC进行符合ISOIECl44434的数据操作。(1)PCD发送请求选择应答RAts。(2)PICC接收到请求选择应答RAts，返回一个选择应答Ats。(3)PCD接收到来自PICC的选择应答Ats。(4)PCD对该Ats进行检测，决定下一步动作。若

62、Ats携带信息显示：PICC支持协议和参数选择PPS，则根据实际情况，判断是否需要进行参数修改。如果不需要进行参数修改，则执行步骤5)，如果需要进行参数修改，则执行下列操作。(1)PcD发送协议和参数选择请求PPSReq。(2)PICC接收该命令，修改相关参数。RFID_二进制树防碰掩算法的研究j实现(3)PICC返回协议和参数选择应答PPSResp。若Ats携带信息显示：PICC不支持协议和参数选择PPS，则直接进行数据交换，即步骤5)。(5)PCD与PICC进行数据交换。(6)PCD发送去选择请求命令DeselectReq，表示不再选择该PICC。(7)PICC接收该命令，去除选择，返回去选择应答命令DeselectResp，表示已经去除了选择，进入HALT状态，除非重新唤醒，否则将不再响应其它命令。(8)PCD接收去选择应答命令DeselectResp。总结：PCD与PICC