适用于RFID系统的多叉树防碰撞算法

1.一种适用于RFID系统的多叉树防碰撞方法，约定每个标签ID号为唯一，每个标签含有相应的响应计数器C、应答标志位TSC、睡眠程度计数器S，其特征在于，该方法步骤还包括：
步骤1）初始化前缀堆栈：阅读器初始化前缀堆栈为空，设定标签初始化参数命令，然后向所有标签发送请求命令Request(NULL)，标签做出响应；
步骤2）检测碰撞：标签做出响应后，阅读器检测碰撞情况，若检测到某三个数据位连续碰撞，则直接截断后续数据的传送再转至步骤3）；若检测到某两个相邻数据位连续碰撞，转至步骤3）；若检测到任意两个碰撞位皆不相邻，转至步骤3）；若检测到无碰撞或只有一个碰撞位，则识别标签后转至步骤4）；
步骤3）确定前缀：若碰撞位为相邻，发送Get命令，确定存在的前缀，再将前缀压入前缀栈，采用去空闲时隙的八叉树搜索或去空闲时隙四叉树搜索方式，发送Request命令处理后，返回步骤2）；若任意两个碰撞位皆不相邻，将最高碰撞位置“0”或置“1”，再将前缀压入前缀栈，采用二叉树搜索方式，发送Request命令处理后，返回步骤2）；
步骤4）判定前缀堆栈：判定前缀堆栈是否为空，若不为空，取出栈顶元素，形成新参数命令，发送请求命令Request，转至步骤2）；若前缀堆栈为空，算法结束。
2.根据权利要求1所述的适用于RFID系统的多叉树防碰撞方法，其特征在于，所述响应计数器C用于表示bit数目；所述睡眠程度计数器S用于记录标签睡眠程度，S=0时，标签处于等待状态；S>0时，标签处于休眠状态；S<0时，标签处于无声状态。
3.根据权利要求1~2任一所述的适用于RFID系统的多叉树防碰撞方法，所述标签初始化参数命令为：响应计数器C=0，应答标志位TSC=L，睡眠程度计数器S=0；所述TSC=L的L表示标签ID长度。
4.根据权利要求3所述的适用于RFID系统的多叉树防碰撞方法，其特征在于，所述步骤3）确定前缀的若碰撞位为相邻的情况为：当有某三个数据位连续碰撞，标签接收命令Get（11，DH）后，读写器采用去空闲时隙的八叉树搜索，发送Request（x,y,z,DH）命令处理后，返回步骤2）；当有某两个相邻数据位连续碰撞，标签接收命令Get(1,DH)后，读写器采用去空闲时隙四叉树搜索，发送Request（x,y,DH）命令处理后，返回步骤2）；所述Request（x,y,z,DH）命令、Request（x,y,DH）命令中的DH为相邻碰撞位中的最高位，其中x,y,z分别为DH，DH－1, DH－2位的标签应答。
5.根据权利要求4所述的适用于RFID系统的多叉树防碰撞方法，其特征在于，所述步骤3）确定前缀的若任意两个碰撞位皆不相邻的情况为：当任意两个碰撞位皆不相邻，将最高碰撞DH位置“0”或置“1”，再采用二叉树搜索，阅读器发送Request(x,DH)命令；所述Request(x,DH)命令中的DH为碰撞位中的最高位。

适用于RFID系统的多叉树防碰撞算法\n技术领域\n[0001] 本发明涉及无线射频识别中的标签防碰撞技术，具体地说是一种适用于RFID系统的多叉树防碰撞算法。\n背景技术\n[0002] 随着通信与计算机技术的发展，物联网技术与人们的生活、工作和娱乐变得越来越紧密。无线射频识别（RFID）技术作为物联网标识环节中的关键技术，近年来也成为诸多专家和学者关注的热点方向。RFID是一种通过射频信号进行非接触式识别的自动识别技术，其基本原理是利用阅读器与电子标签之间的控件耦合，包括电感耦合或电磁耦合，或反射的传输特性来实现数据通信，从而可对被识别物体的自动耦合。\n[0003] RFID系统中，标签周围可能同时存在多个读写器，这样，标签可能同时收到不同阅读器发送的命令，此时便产生读写器之间的碰撞。但是由于读写器具有很强的处理能力，而且这种碰撞的概率比较小，也容易解决，因此一般不把其作为关注热点。另外，一般情况下，同一个RFID系统中的所有标签工作在同一频道，当读写器的作用范围内存在多个标签，并在同一时刻可能有多个标签同时与阅读器进行通信，此时就会产生相互干扰，也就是标签发生了碰撞或冲突，使读写器不能正确识别任何一个标签的信息。\n[0004] 因此，迫切需要提出一种防碰撞技术，用于解决读写器作用范围内同时存在多个标签时的识别问题。标签防碰撞算法由此应运而生，其目标是快速地从多个标签中选择一个响应读写器的请求命令，并尽量在较短时间内识别其作用范围内的所有标签。因此，防碰撞算法已成为RFID系统研究领域的一个热点。\n[0005] 目前已有的防碰撞算法主要有两类：基于ALOHA的防碰撞算法和基于树的防碰撞算法。基于ALOHA的算法是一种随机算法，算法比较简单而且对标签的硬件要求也不高。基于ALOHA的算法中，读写器作用范围内的标签随机选择一个时隙，向读写器传送自身存储的信息。但是由于每个标签都是随机选择时隙，所以存在“标签饥饿”的问题,即某个标签所选择的时隙总是与其他时隙相同，长时间不能被识别。基于树的搜索算法是一种确定性算法，算法的实现比较复杂，标签的成本也相对较高。每个标签都有一个唯一标识的ID号，读写器根据这个唯一性选择标签进行通信。当采用二叉树的搜索算法时，每次碰撞，标签只分成0和1两个组，树分裂速度较慢，造成标签的识别时间较长，但是不存在“标签饥饿”的问题。因此人们提出了各种防碰撞算法以克服上述问题。\n[0006] 通过文献检索，我们检索到了以下相关文献，但其算法皆单一地基于二叉树防碰撞算法，并未综合应用多叉树算法，例如：\n[0007] 中国专利CN201210149625.5，一种基于时间可用度的飞机射频设备间电磁兼容性分析方法，专利权人：北京航天航空大学，该专利公开了一种基于时间可用度的飞机射频设备间电磁兼容性分析方法，该发明方法采用时间可用度数值与电磁兼容性要求进行对比，判断飞机的设计是否能符合各设备电磁兼容工作的要求。该发明方法首先采用基于二叉树防碰撞算法的工作时隙分配方法，计算出各个互扰射频设备的时间可用度；然后应用时间可用度来评价飞机一次完整模拟飞行分析过程中，各个互扰射频设备是否能满足正常使用要求。\n[0008] 中国专利CN201110188133.2，管桩制造养护工艺中的动态二进制查询树防碰撞方法，专利权人：广东三和管桩有限公司，该专利在读写过程中，将堆栈算法与动态二叉树防碰撞算法融合于一体，并利用动态减位对碰撞进行处理，有效解决了读写器对多标签进行读写时可能出现的碰撞问题。\n发明内容\n[0009] 本发明的目的是克服现有防碰撞算法中存在搜索速度慢、数据传输量大、碰撞标签识别时间长的缺点，提供一种适用于RFID系统的多叉树防碰撞算法。该方法是面向RFID系统的增强型自适应多叉树碰撞算法，通过判断相邻碰撞位的个数情况，综合采用自适应的无空闲时隙的八叉树或四叉树或二叉树搜索方式，减少了读写器与标签之间数据量的传输，从而提高了多标签的识别速度，加快了识别时间。\n[0010] 本发明的一种适用于RFID系统的多叉树防碰撞算法技术方案如下：一种适用于RFID系统的多叉树防碰撞算法，约定每个标签ID号为唯一，每个标签含有相应的响应计数器C、应答标志位TSC、睡眠程度计数器S，其特征在于，该算法步骤还包括：\n[0011] 步骤1）初始化前缀堆栈：阅读器初始化前缀堆栈为空，设定标签初始化参数命令，然后向所有标签发送请求命令Request(NULL)，标签做出响应。\n[0012] 步骤2）检测碰撞：标签做出响应后，阅读器检测碰撞情况，若检测到某三个数据位连续碰撞，则直接截断后续数据的传送再转至步骤3）；若检测到某两个相邻数据位连续碰撞，转至步骤3）；若检测到任意两个碰撞位皆不相邻，转至步骤3）；若检测到无碰撞或只有一个碰撞位，则识别标签后转至步骤4）。\n[0013] 步骤3）确定前缀：若碰撞位为相邻，发送Get命令，确定存在的前缀，再将前缀压入前缀栈，采用去空闲时隙的八叉树搜索或去空闲时隙四叉树搜索方式，发送Request命令处理后，返回步骤2）；若任意两个碰撞位皆不相邻，将最高碰撞位置“0”和置“1”，再将前缀压入前缀栈，采用二叉树搜索方式，发送Request命令处理后，返回步骤2）。\n[0014] 步骤4）判定前缀堆栈：判定前缀堆栈是否为空，若不为空，取出栈顶元素，形成新参数命令，发送请求命令Request，转至步骤2）；若前缀堆栈为空，算法结束。\n[0015] 作为本发明的进一步改进，所述响应计数器C用于表示比特数目；所述睡眠程度计数器S用于记录标签睡眠程度，S=0时，标签处于等待状态；S>0时，标签处于休眠状态；\nS<0时，标签处于无声状态。\n[0016] 作为本发明的进一步改进，所述标签初始化参数命令为：响应计数器C=0，应答标志位TSC=L，睡眠程度计数器S=0；所述TSC=L的L表示标签ID长度。\n[0017] 作为本发明的进一步改进，所述步骤3）确定前缀的若碰撞位为相邻的情况为：当有某三个数据位连续碰撞，标签接收命令Get（11，DH′）后，读写器采用去空闲时隙的八叉树搜索方式，发送Request（x,y,z,DH′）命令处理后，返回步骤2）；当有某两个相邻数据位连续碰撞，标签接收命令Get(1,DH′)后，读写器采用去空闲时隙四叉树搜索方式，发送Request（x,y,DH′）命令处理后，返回步骤2）；所述Request（x,y,z,DH′）命令和Request（x,y,DH′）命令中的DH′为相邻碰撞位中的最高位。\n[0018] 作为本发明的进一步改进，所述步骤3）确定前缀的若任意两个碰撞位皆不相邻的情况为：当任意两个碰撞位皆不相邻，将最高碰撞位DH置“0”和置“1”，再采用二叉树搜索方式，阅读器发送Request(x,DH)命令；所述Request(x,DH)命令中的DH为碰撞位中的最高位。\n[0019] 为了使本发明公开充分，步骤3）确定前缀其具体步骤如下三方面（以下四叉树或八叉树搜索中所述DH′为相邻碰撞位中的最高位，二叉树搜索中所述DH为碰撞位中的最高位）。\n[0020] ①当有3个相邻碰撞位，采用去空闲时隙的八叉树搜索方式，其步骤包括：\n[0021] a、标签接收命令Get（11，DH′），S=0的标签将自身的DH′和DH′－1位的数据与“11”相与，结果为00、01、10、11的标签分别将1、2、3、4载入其响应器C。\n[0022] b、标签等待响应计数器C－1个 比特的传输时间后向读写器返回其相邻碰撞位中的最低位即DH′－2位信息，应答后C=0。因为标签接收Get命令后反馈的只是一个比特位的信息，所以以一个比特的传输时间为时间计数单位。\n[0023] c、读写器根据四次接收DH′－2位数据的情况，确定标签中存在的前缀；如果4次均有碰撞，则说明存在八种前缀000、001、010、011、100、101、110、111，若第一次接收到数据“0”，则说明存在前缀000，否则存在001；若第二次接收到数据“0”，则说明存在前缀\n010，否则存在011前缀；若第三次接收到数据“0”，则说明存在前缀100，否则存在101；若第四次接收到数据“0”，则说明存在前缀110，否则存在111前缀。\n[0024] d、S=0的标签响应此命令后应答标志位TSC=DH′－3。由前缀堆栈获取栈顶元素，根据获知存在的前缀然后选择八叉树的搜索方式，发送Request(x,y,z,DH′)，要求标签应答标志位TSC为DH′－3，同时DH′，DH′－1, DH′－2位分别为x,y,z的标签应答，应答后S=0，其他的标签将自身的睡眠程度计数器S=S+1。然后返回步骤2）。\n[0025] ②当只有2个相邻碰撞位，采用去空闲时隙四叉树搜索方式，其步骤包括：\n[0026] a、标签接收命令Get(1,DH′)，S=0的标签将DH′位的数据与“1”相与，结果为0的标签便将1载入其响应计数器C，结果为1的标签将2载入响应计数器C。\n[0027] b、标签等待响应计数器C－1个 比特的传输时间后向读写器返回其相邻碰撞位中的最低位，即DH′－1位的信息，应答后C=0。\n[0028] c、读写器根据两次接收DH′－1位数据的情况，确定标签中存在的前缀。如果两次均有碰撞，则说明存在前缀00、11、01、10，若第一次接收到数据“0”，则说明存在前缀00，否则存在01，若第二次接收到数据“0”则说明存在前缀10，否则存在11前缀。\n[0029] d、S=0的标签响应此命令后应答标志位TSC=DH′－2。由前缀堆栈获取栈顶元素，根据获知存在的前缀然后选择四叉树的搜索方式，发送Request(x,y,DH′)，要求标签应答标志位TSC为DH′－2，同时与查询前缀的匹配的标签应答，应答后S=0，其他的标签将自身的睡眠程度计数器S=S+1。然后返回步骤2）。\n[0030] ③当任意两个碰撞位皆不相邻，将碰撞位置“0”和置“1”，再采用二叉树搜索方式，其步骤包括：阅读器发送Request(x,DH)命令；如果x=0, 则要求S=0且DH位为x的标签返回其自身的数据，其他标签均将S=S+1；如果x=1，则当前标签均将S=S－1，然后要求S=0且DH位为x的标签应答。然后返回步骤2）。\n[0031] 本发明实现的原理：根据相邻碰撞位的个数动态地选择无空隙时隙的八叉树或四叉树或二叉树的搜索方式，克服了二叉树分裂速度慢的缺点，加快了树的分裂速度。在一般的四叉树或八叉树搜索方式中，一方面加快了树的分裂速度，但是随着读写器作用范围内标签数量的减少，空闲时隙的数量也随之增多，造成了不必要的搜索。本发明利用标签中的计数器，在收到读写器的获取前缀命令后，等待响应计数器C－1个比特的传输时间后返回相邻碰撞位中最低一位的1比特数据，不仅确定了存在的时隙，而且获取前缀只需较短时间与很小的数据传输量。标签的应答计数器和睡眠程度计数器使得本发明无需发送额外的指令便可直接退回上一个碰撞节点，获知响应该碰撞节点命令且还未被识别的标签，减少了命令的开销，提升了系统的识别效率。\n[0032] 本发明一种适用于RFID系统的多叉树防碰撞算法产生了以下良好效果：\n[0033] （1）根据某碰撞位相邻的个数情况，动态选择无空闲时隙八叉树或四叉树或二叉树搜索方式，克服了二叉树分裂速度慢的缺点，加快了树的分裂速度，而且提高了碰撞标签识别的准确性。\n[0034] （2）通过引入响应计数器C决定标签的响应顺序，利用标签中的计数器，在收到读写器的获取前缀命令后，立即或等待C－1 个比特的传输的时间后返回相邻碰撞位中最低位的1比特数据，不仅确定了存在的时隙，避免了空闲命令的传送，而且获取前缀时标签响应的只是1比特的信息位，只需较短时间与很小的数据传输量。\n[0035] （3）通过引入应答标志位TSC和睡眠程度计数器S，读写器无需传送激活命令便能直接退回到上一个碰撞节点，得知响应上个节点命令但还未被识别的标签，减少了命令的传送，通过只接受三个相邻碰撞位以前的数据，减少了读写器与标签之间数据的传输量，从而提高了多标签的识别速度，加快了识别时间。\n附图说明\n[0036] 图1.本发明适用于RFID系统的多叉树防碰撞算法流程图。\n[0037] 图2.读写器发送Request(NULL)指令后标签应答示意图。\n[0038] 图3.读写器发送Get(11,7)指令后标签响应示意图。\n[0039] 图4.读写器发送Request(000,7)指令后标签响应示意图。\n[0040] 图5.读写器发送Get(1,3)指令后标签响应示意图。\n[0041] 图6.读写器发送Request(01,3)指令后标签响应示意图。\n[0042] 图7.读写器发送Request(10,3)指令后标签响应示意图。\n[0043] 图8.读写器发送Request(001,7)指令后标签响应示意图。\n[0044] 图9.读写器发送Request(010,7)指令后标签响应示意图。\n[0045] 图10.读写器发送Request(0,2)指令后标签响应示意图。\n[0046] 图11.读写器发送Request(1,2)指令后标签响应示意图。\n[0047] 图12.读写器发送Request(111,7)指令后标签响应示意图。\n具体实施方式\n[0048] 以下结合图1~12和实施例描述本发明适用于RFID系统的多叉树防碰撞算法。\n[0049] 在本发明中约定每个标签ID号为唯一，八叉树和四叉树搜索方式中所述DH′为检测到的相邻碰撞位中的最高位，二叉树搜索方式中所述DH为碰撞位中的最高位，每个标签含有相应响应计数器C、应答标志位TSC、睡眠程度计数器S，并引入以下几种命令：\n[0050] 1）获取命令Get，命令的形式Get(x,DH′)，其含义为参数DH′为检测到相邻冲突位中的最高位，用于获取四叉数或八叉树搜索方式时标签中存在的前缀。\n[0051] 2）请 求 命 令Request，命 令 形 式 为Request（NULL），Request(x,DH) 和Request(x,y,DH′)，Request(x,y,z,DH′)。\n[0052] Request（NULL）的含义为阅读器进行第一次查询时，要求其所有范围内的标签响应，返回其自身的标签信息。\n[0053] Request(x,DH)的含义是在进行二叉树搜索时，若 x=0, 读写器要求S=0且DH位为x的标签应答，其余标签S=S+1；若x=1，则当前标签将S=S－1，然后S=0且DH位为x的标签应答。\n[0054] Request(x,y,DH′)的含义是在进行四叉树搜索时，读写器要求发送Request(x,y,DH′)，要求标签状态TSC为DH′－2，同时DH′，DH′－1为分别为x,y的标签应答，应答后S=0，其他的标签将自身的S=S+1。\n[0055] Request(x,y,z,DH′)的含义是在进行八叉树搜索时，读写器要求发送Request(x,y,z,DH′)，要求标签状态TSC为DH′－3，同时DH′，DH′－1，DH′－2位分别为x,y,z的标签应答，应答后S=0，其他的标签将自身的S=S+1。\n[0056] 实施例1\n[0057] 下面举例说明本算法的一个具体实施过程，其过程如图1所示，假设读写器的作用范围内有7个标签，标签长度为8，tag1为0000 1000，tag2为0100 0100，tag3为0010 \n0100，tag4为0100 0001，tag5为1110 0001，tag6为0000 1001，tag7为0000 0101。在本组标签ID号中左边为高位，最高位为第七位，最低位为第0位。用Di表示第i位的数据，如D7表示第7位的数据，用“？”表示碰撞位。\n[0058] 步骤1）初始化前缀堆栈：阅读器初始化前缀堆栈，使之为空，初始时睡眠程度计数器S=0，响应计数器C=0，应答标志位TSC=8，睡眠程度计数器S=0，8表示标签ID的长度，然后发送请求命令Request(NULL)，要求所有标签响应，其过程如图2表示。\n[0059] 步骤2）检测碰撞：标签做出响应后，阅读器检测碰撞情况，阅读器检测碰撞情况结果为：情况①：三位数据连续碰撞，读写器则直接截断后续数据的传送，不再接收标签三个相邻碰撞位以后的数据，直接发送下一个命令，转至步骤3）；情况②：只有两位数据位连续碰撞则转入步骤4）；情况③：任意两个碰撞位都不相邻，则转入步骤5）；情况④：若无碰撞或只有一个碰撞位则识别标签后转至步骤6）。\n[0060] 步骤3）DH′，DH′－1，DH′－2这三位数据连续碰撞，采用去空闲时隙的八叉树搜索方式，其步骤包括：\n[0061] a、确定前缀：发送Get指令，确定存在的前缀，并将获知的前缀压入前缀栈。标签接收命令Get（11，DH′），S=0的标签将其第DH′位和DH′－1位的数据与“11”相与，结果为00、01、10、11的标签分别将1、2、3、4载入其响应器C。本组标签中，DH′=7,标签接收获取命令Get(11,7)。七个标签均将其D7和D6位的数据与“11”相与。其中tag1，tag3，tag6，tag7相与的结果都为00，其对应的C则为1，tag2和tag4相与的结果都为01，则C=2，tag5相与的结果为11，则对应的C为4。如图3所示。\n[0062] b、标签等待响应计数器C－1个 比特的传输时间后向读写器返回其相邻碰撞位中的最低位的信息，本组中标签返回D5位的数据，应答后C=0。\n[0063] c、读写器根据四次接收相邻碰撞最低位数据的情况，确定标签中存在的前缀；如果4次均有碰撞，则说明存在八种前缀000、001、010、011、100、101、110、111，若第一次接收到数据“0”，则说明存在前缀000，否则存在001；若第二次接收到数据“0”，则说明存在前缀\n010，否则存在011前缀；若第三次接收到数据“0”，则说明存在前缀100，否则存在101；若第四次接收到数据“0”，则说明存在前缀110，否则存在111前缀。在本组标签中，第一次发生碰撞，则说明存在标签中存在前缀000和001，第二次接收数据“0”，第四次接收数据“1”，均无碰撞，则说明分别存在前缀010、111。第三次无标签响应，则说明不存在D7和D6位是\n10的前缀。\n[0064] d、S=0的标签响应此命令后应答标志位TSC=DH′－3，如图3所示。由前缀堆栈获取栈顶元素，根据获知存在的前缀然后选择八叉树的搜索方式，发送Request（x,y,z,DH′）指令，要求TSC=DH′－3且前缀匹配的标签响应，应答后S=0，其他的标签将自身的睡眠程度计数器S=S+1，此时本例中发送Request(000,7)，TSC=4且前缀匹配的标签响应，此时只有tag1，tag6，tag7应答，其应答后均将其S=0，其他的标签将自身的睡眠程度计数器S=S+1，如图4所示。然后返回步骤2）。\n[0065] 步骤4）相邻碰撞位只有两个，采用去空闲时隙的四叉树搜索方式，其步骤包括：\n[0066] a、标签接收命令Get（1，DH′），S=0的标签将其第DH′位的数据与“1”相与，结果为0、1的标签分别将1、2载入其响应计数器C。本例中读写器发送 Request(000,7)后进入此步骤，发送此请求命令经标签应答后，读写器经过译码后接收到的数据为0000??0?（？代表该位发生碰撞）。D3、D2、D1位均发生碰撞，相邻位的个数为2。此时标签接收命令Get(1,3)，如图5所示。本组中S=0的标签tag1，tag6将自身的D3位与“1”相与后均为1，则将2载入C中，tag7的D3位与“1”相与后为0，则将1载入C中。\n[0067] b、标签等待响应计数器C－1个比特的传输时间后向读写器返回其相邻碰撞位中的最低位，本例中返回D2位的信息，应答后C=0。\n[0068] c、读写器根据两次接收2位数据的情况，确定标签中存在的前缀。如果两次均有碰撞，则说明存在前缀00、11、01、10，若第一次接收到数据“0”，则说明存在前缀00，否则存在01，若第二次接收到数据“0”则说明存在前缀10，否则存在11前缀。本组中第一次接收数据“1”，第二次接收数据“0”，两次均无碰撞，则说明存在前缀01和10。\n[0069] d、S=0的标签响应此命令后应答标志位TSC=DH′－2。由前缀堆栈获取栈顶元素，根据获知存在的前缀然后选择四叉树的搜索方式，发送Request（x,y，DH′）指令，要求TSC=DH′－2且前缀匹配的标签响应，应答后S=0，其他的标签将自身的睡眠程度计数器S=S+1，然后返回步骤2）。本例中先发送Request(01,3)，要求标签应答标志位TSC为1，同时与查询前缀的匹配的标签应答，应答后S=0，此时只有tag7应答，读写器识别tag7后将其转为无声状态，S=－1，其他标签都将S=S+1。如图6所示。\n[0070] e、识别标签后，读写器采取后退策略，从前缀堆栈中获取新的Request查询参数，发送Request指令后返回步骤2）。\n[0071] 本例中发送Request(01,3)请求命令后，只有标签7应答，识别tag7后转入此步骤的，如图7，图8，图9所示，具体识别过程如下：\n[0072] aa、读写器从前缀堆栈中获取新的Request参数，发送Request(10,3)指令，求标签应答标志位TSC为DH′－2，同时与查询前缀的匹配的标签应答，应答后S=0，其他的标签将自身的睡眠程度计数器S=S+1。此时只有tag1和tag6应答，读写器接收的数据为\n0000100？，只有一个碰撞位，直接识别tag1和tag6，然后将其转为无声状态，S= －1，其他标签都将S=S+1，如图7所示。\n[0073] bb、读写器识别tag1和tag6后采取后退策略，从前缀堆栈中获取命令参数，发送Request(001,7)指令，要求TSC=4且前缀匹配的标签响应，应答标签S=0，其余标签S+1，返回步骤2）。此时只有tag3响应，则直接识别tag3后将其进入无声状态。其余标签S=S+1。\n如图8所示。\n[0074] cc、读写器识别tag3后采取后退策略，从前缀堆栈中获取命令参数，发送Request(010,7)指令，TSC=4且前缀匹配的标签响应，应答标签S=0，此时tag2和tag4应答，其余标签S+1，返回步骤2）。如图9所示。\n[0075] dd、以上再次经步骤2）检测后，读写器接收到的数据为01000？0？，只有D2和D0发生碰撞，且不相邻，则采用二叉树的搜索方式。转入步骤5)。\n[0076] 步骤5）任意两个碰撞位都不相邻，则采用二叉树的搜索方式，具体包括以下步骤：\n[0077] a、阅读器发送Request(0,DH)命令，此时 x=0, 则要求S=0且第2位为0的标签返回其自身的数据，且其他标签均将S=S+1。本例中，读写器发送请求命令Request(010,7)后进入此步骤的。进入此步骤后，读写器发送命令Request(0,2)，此时DH=2；此时只有tag4响应，识别tag4后将其转为无声状态，其余标签都将S=S+1；如图10所示。\n[0078] b、读写器识别标签后，采取后退策略，发送Request(1,DH)指令，x=1，则当前标签S=S－1，然后S=0且DH位为1的标签应答，然后转到步骤2）。本例中此时DH=2，发送Request(1,2)指令，此时只有标签2应答，识别tag2后，tag2进入无声状态，如图11所示。\n读写器识别tag2后从前缀栈中获取新的查询参数，发送Request(111,7)指令，TSC=4且前缀匹配的标签响应，此时只有tag5响应，则直接识别tag5后将其进入无声状态。如图12所示。\n[0079] 步骤6）经过步骤2）检测后转入此步骤，判断前缀堆栈是否为空，若为空则转入步骤7)。若前缀堆栈不为空，则读取栈顶元素，获取Request新的请求命令参数，然后发送Request指令，再转入步骤2）。\n[0080] 步骤7）此时前缀堆栈为空，则算法结束。本例中识别tag5后前缀堆栈为空，则识别过程结束。\n[0081] 最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制。尽管参照实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，对本发明的技术方案进行修改或者等同替换，都不脱离本发明技术方案的精神和范围，其均应涵盖在本发明的权利要求内。本发明是经过多位标签防碰撞算法技术人员长期科学研究经验积累，并通过创造性劳动创作而出，根据某碰撞位相邻的个数情况，动态选择无空闲时隙八叉树或四叉树或二叉树搜索方式，克服了二叉树分裂速度慢的缺点，加快了树的分裂速度，提高了碰撞标签的识别准确性；而且减少了数据的传输，降低了能量消耗，消除了空闲时隙，缩短了识别时间。