下载文档原格式
基于后退式搜索的自适应多叉树防碰撞算法孙文胜;胡玲敏【摘要】Concerning the common problem of tag collision in Radio Frequency Identification (RFID) system, an improved anti-collision algorithm for multi-branch tree was proposed based on the regressive-style search algorithm.According to the characteristics of the tags collision, the presented algorithm adopted the dormancy count, and took quad tree structure when continuous collision appeared, which had the ability to choose the number of forks dynamically during the searching process, reduced the search range and improved the identification efficiency.The performance analysis results show that the system efficiency of the proposed algorithm is about 76.5％; moreover, with the number of tags increased, the superiority of the performance is more obvious.%针对无线射频识别(RFID)系统中常见的标签防碰撞问题,在后退式搜索算法的基础上提出了一种改进的多叉树防碰撞算法.根据标签碰撞的特点,采用休眠计数的方法,以及遇到连续碰撞位时进行四叉树分裂的策略,使得在搜索过程中能够动态选择分叉数量,缩短了标签识别时间,有效地提高了算法的搜索效率.性能分析表明,该算法的系统识别效率达76.5%,且随着标签数目的增多,优越性更加明显.【期刊名称】《计算机应用》【年(卷),期】2011(031)008【总页数】4页(P2052-2055)【关键词】无线射频识别;标签碰撞;后退式搜索;标签识别【作者】孙文胜;胡玲敏【作者单位】杭州电子科技大学,通信工程学院,杭州,310018;杭州电子科技大学,通信工程学院,杭州,310018【正文语种】中文【中图分类】TP391.450 引言无线射频识别(Radio Frequency Identification，RFID)技术是一种利用射频通信实现的非接触式自动识别技术，其应用开始于20世纪60年代。
一种自适应的RFID防碰撞算法REN Bo-han;ZHANG Sheng-jie;SHI Hao-sen;GONG Jing【摘要】在射频识别的(radio frequency identification,RFID)的应用中,当多个标签同时出现在读写器范围内进行信息传输时,会出现“碰撞”现象,使阅读器无法正常工作.为解决射频识别应用过程中多个标签同时存在引发的碰撞问题,在自适应二四叉树防碰撞算法的基础上,将八叉树引入,提出了一种改进的自适应的二四八叉树算法.该算法通过计算标签的碰撞因子,自适应地选择最优树的叉树,然后进行搜索,从而大大减少了空闲时隙.对改进后的算法进行复杂度分析后,针对不同标签数量的搜索过程,在总时隙数和吞吐率两个方面对算法进行仿真.仿真结果表明,在一定条件下,与自适应的二四叉树相比,改进后的算法可以在减少空闲时隙数的同时提高算法的吞吐率.【期刊名称】《计算机技术与发展》【年(卷),期】2018(028)012【总页数】4页(P67-70)【关键词】防碰撞算法;射频识别;自适应;多叉树搜索;八叉树【作者】REN Bo-han;ZHANG Sheng-jie;SHI Hao-sen;GONG Jing【作者单位】;;;【正文语种】中文【中图分类】TN920 引言射频识别(radio frequency identification，RFID)技术可以通过无线电讯号实现无接触式自动识别，由于其具有阅读速度快，可适应于各种恶劣环境，读写能力快等优点，现已广泛应用于交通物流、食品管理、图书馆书刊借阅、门禁等各个领域[1]。
但当多个标签同时与读写器进行信息传输时，会出现“碰撞”现象，使阅读器无法正常工作，严重影响系统正常运行。
为解决这一问题，现已提出了多种RFID防碰撞的算法[2]。
1 当前防碰撞算法常用的防碰撞算法一般可以分为两类：确定算法和非确定算法[3]。
非确定算法主要是基于ALOHA算法，包括时隙ALHOA算法、分群时隙ALOHA算法等。
一种基于二叉树形搜索的RFID防碰撞算法作者：辜大光袁仁坤范振粤杨晓东来源：《软件导刊》2012年第03期摘要：在RFID防碰撞算法中，平均时延是影响识别性能的关键因素。
平均时延主要取决于识别每个标签所需的平均比特数。
在二进制搜索防碰撞算法的基础上，提出了一种新的二叉树形搜索算法,该算法显著减少了识别标签的平均比特数，且当阅读器检索到树的底层时,可向二叉树的上层回溯，最终连续识别出所有的标签。
对算法进行了仿真分析，证明该算法在性能上有明显提高。
关键词：平均时延；平均比特数；防碰撞算法；二叉树形搜索；射频识别中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2012）003-0062-作者简介：辜大光（1985-)，男，湖南娄底人，硕士，南星电子有限公司产品经理，研究方向为通信与信息系统；袁仁坤(1967-)，男，湖南绥宁人，硕士，南星电子有限公司副总经理、工程师，研究方向为电路与系统；范振粤(1983-)，男，广东汕尾人，硕士，南星电子有限公司产品经理，研究方向为通信与信息系统；杨晓东（1984-），男，广东揭阳人，硕士，南星电子有限公司产品经理，研究方向为通信与信息系统。
0 引言射频识别 (Radio Frequency Identification, RFID)的主要思想是通过射频信号自动识别目标对象并获取相关数据。
RFID系统一般由电子标签( Tag)和阅读器(Reader)组成。
阅读器负责发送广播并接收标签的标识信息;标签收到广播命令后将自身标识信息发送给阅读器。
在数据传输的过程中从阅读器到标签的数据传输称作下传,从标签到阅读器的数据传输称作上传。
随着RFID的发展，其应用也越来越广泛，当阅读器识别区域内存在两个或者两个以上的标签在同一时刻向阅读器发送标识信息时,将产生碰撞问题。
解决碰撞问题的方法主要有空分多址（SDMA）、时分多址（TDMA）、码分多址（CDMA）、频分多址（FDMA）四大类。
《RFID标签防碰撞算法研究》篇一一、引言随着无线通信技术的快速发展，射频识别（RFID）技术已成为现代物流、零售、医疗、交通等众多领域的重要应用之一。
然而，在RFID系统中，多个标签同时响应阅读器时，会引发所谓的“碰撞”问题。
这导致阅读器无法准确读取标签信息，从而影响了RFID系统的性能。
因此，研究有效的防碰撞算法，解决RFID 标签碰撞问题具有重要意义。
本文旨在深入探讨RFID标签防碰撞算法的原理及其应用，分析其优势和挑战。
二、RFID系统概述RFID系统主要由阅读器、标签和后端处理系统三部分组成。
阅读器负责发送信号给标签，接收来自标签的信号并进行解析；标签是一种射频电子标签，用于存储信息并响应阅读器的询问；后端处理系统负责管理标签信息，并进行数据处理和存储。
在RFID系统中，防碰撞算法是解决多个标签同时响应阅读器时发生碰撞的关键技术。
三、RFID标签碰撞类型及影响RFID标签碰撞主要分为两类：一类是标签间碰撞，即多个标签同时发送数据导致接收信号相互干扰；另一类是帧内碰撞，即一个标签在发送数据过程中由于信号传输时间过长导致数据分片在帧内发生碰撞。
这两种碰撞都会导致阅读器无法准确读取标签信息，降低RFID系统的性能。
四、RFID标签防碰撞算法研究为了解决RFID标签碰撞问题，研究者们提出了多种防碰撞算法。
下面将介绍几种常见的防碰撞算法及其原理。
1.ALOHA算法ALOHA算法是最早的防碰撞算法之一，它是一种随机性算法。
其主要思想是当检测到碰撞时，标签需要随机延迟一段时间后再次发送数据。
通过不断尝试和调整延迟时间，最终使所有标签的数据都能被阅读器正确接收。
ALOHA算法实现简单，但效率较低。
2.二进制树搜索算法二进制树搜索算法是一种基于二叉树原理的防碰撞算法。
它通过将标签组织成二叉树结构，并按照树形结构逐级进行查询和应答。
该算法可以有效地降低碰撞概率，提高系统的吞吐量。
然而，在标签数量较多时，算法的复杂度较高。
基于完全二叉树BVH的自碰撞检测算法陆睿;刘卉【摘要】Dynamic real-time simulation of deformable objects is the main task of applications of computer graphics and virtual reality. Such simulation tasks require fast calculated models and dynamics simulation algorithms, in particular, the efficient detection algorithms for collision and self-collision. Although the collision detection for rigid object has been well-investigated by the researchers, the collision detection for deformable objects brings more challenge. In this paper, a bounding volume hierarchy structure based on complete binary tree is presented , and by using the construction and the update algorithm based on this structure, a couple of processes in simulation system are optimised. We also implement the self-collision detection of cloth deformable object and its physical simulation in complicated scene.%计算机图形学与虚拟现实应用的一个主要任务是对柔性物体的动态实时模拟.这类仿真任务需要能够快速计算的模型与动力学仿真算法,特别是高效的碰撞、自碰撞检测算法.尽管研究者们针对刚体的碰撞检测已经做了大量工作,但柔性物体对碰撞检测提出了更高的挑战.给出一种基于完全二叉树的包围盒层次结构,并运用基于此结构的构建、更新算法,优化仿真系统中数个环节,实现复杂场景中布料类柔性物体的自碰撞检测与物理模拟.【期刊名称】《计算机应用与软件》【年(卷),期】2012(029)012【总页数】5页(P282-285,294)【关键词】层次包围盒;完全二叉树;碰撞检测【作者】陆睿;刘卉【作者单位】复旦大学计算机科学技术学院上海201203;复旦大学计算机科学技术学院上海201203【正文语种】中文【中图分类】TP3010 引言三维场景中物体的真实感模拟是计算机图形学的主要任务之一。
基于二进制树的RFID系统自适应多分支防碰撞算法崔英花【摘要】To improve the identification efficiency of radio frequency identification (RFID) systems, the anti-collision problem of the systems was studied.Considering that dividing tags into multiple branches can efficiently improve the tags identification efficiency in RFID systems, while the conventional anti-collision algorithms based on multiple branch usually choose the optimal branches based on the tag number estimation, and the estimation delay and error can affect the identification efficiency, an adaptive multiple branche (AMB) algorithm for anti-collision based on binary tree was proposed.The alglorithm uses the number of the identified tags to estimate the tags in the right node of a binary tree in the same level according to the characters of binary tree and chooses the optimal branches, then executes this repeatedly, the system identification efficiency can be improved by avoiding the estimation error caused by only once tag number estimation.The simulation result shows that the AMB algorithm can improve the system identification efficiency, which reaches 43% when in large tag number quantity.Meanwhile, the algorithm is compatible with the existing protocols by only adding several counters in the reader and without changing any air interface protocol.%为提高射频识别(RFID)系统的识别效率,研究了系统的标签防碰撞问题.考虑到对标签进行多分支处理能够有效地提高RFID系统标签识别效率,而传统的多分支防碰撞算法都是在标签估计的基础上对标签进行最优分组,标签估计产生的时延和误差都会影响整体的识别效率,提出了一种基于二进制树的自适应多分支(AMB)防碰撞算法.该算法根据二进制树结构特点,利用识别的标签数目对树结构中右节点标签进行估计并进行分组识别,经过多次调整的自适应多分支防碰撞算法,可以规避一次标签估计所引入的估计误差,从而提高系统的识别效率.仿真结果表明自适应多分支算法可以大大提高标签识别效率,在标签数量较大时系统效率可达43%左右.同时该算法实现简单,只需在阅读器中增加若干计数器,不需要改变任何空中接口,很容易与现有协议兼容.【期刊名称】《高技术通讯》【年(卷),期】2017(027)005【总页数】6页(P398-403)【关键词】射频识别(RFID);防碰撞算法;二进制树;多分支算法;标签估计【作者】崔英花【作者单位】北京信息科技大学信息与通信工程学院北京 100101【正文语种】中文在射频识别(radio frequency identification, RFID)通信系统中，有大量的标签与读写器进行通信，标签与标签之间、读写器与读写器之间都存在相互干扰，即所谓的碰撞问题。
基于多位碰撞检测的自适应树形RFID防碰撞算法梅佳伟;李晖【摘要】多叉树查询算法仅利用最高几位碰撞位形成新查询码,使得标签传送过程中存在大量无用信息,造成了大量的通信资源浪费,降低了通信效率.因此,提出了一种自适应多位碰撞检测树算法(MCDT).该算法在RFID二进制碰撞检测基础上,根据阅读器检测到的标签碰撞信息中最高2～3位碰撞位的分布情况,利用碰撞位之间间隔的位数来判决下一轮查询过程中标签需要传送给阅读器的ID的比特数,动态调整标签在碰撞密集区域向阅读器传输的有效ID信息.仿真结果表明,MCDT算法在维持较好的识别效率和识别时间的同时,标签碰撞位向阅读器的通信量明显低于其他同类算法,且有效降低了查询过程中的通信量.【期刊名称】《通信技术》【年(卷),期】2018(051)004【总页数】6页(P846-851)【关键词】RFID;防碰撞;碰撞位;通信量;标签查询码【作者】梅佳伟;李晖【作者单位】沈阳工业大学信息科学与工程学院,辽宁沈阳110870;沈阳工业大学信息科学与工程学院,辽宁沈阳110870【正文语种】中文【中图分类】TP391.440 引言射频识别（Radio Frequency Identifcation，RFID）技术起始于1973年。
作为自动识别和数据获取的一部分，RFID系统通过无线网与网络系统进行互交，能够单独识别追踪并捕获包装中货物、动物甚至人的标签状态或信息[1]。
因此，RFID 将会取代现在普遍使用的条形码广泛应用于物流、零售和存储管理等领域[2]。
由于标签的体积和造价等原因限制，一个阅读器读取范围内同时出现多个标签时，它们会同时响应阅读器的查询信息，而标签本身无法感知到周围标签的存在，此时就会出现标签信息的碰撞[3]，导致阅读器无法顺利获取标签信息。
因此，射频标签的防碰撞成为射频识别过程中的一个关键技术[4]。
受现有标签技术和成本制约，目前的标签防碰撞算法主要分为两类：一种是以ALOHA算法为主的非确定性算法[5-8]，一种是以二进制搜索算法为基础的确定性算法。
2010年6月Journal on Communications June 2010 第31卷第6期通信学报V ol.31No.6基于二叉树的RFID防碰撞算法的研究王雪，钱志鸿，胡正超，李奕男（吉林大学通信工程学院，吉林长春130025）摘要：在二叉树算法的基础上提出了锁位后退防碰撞（BLBO）算法，增加了锁位寻呼指令，阅读器根据译码结果判断发生碰撞的比特，发送锁位寻呼指令锁定发生碰撞的比特，寻呼过程采用后退策略，每次识别一个标签之后返回到上一个发生碰撞的节点。
算法充分考虑了阅读器寻呼次数、传输时延、标签能耗以及吞吐量4个重要性能指标，仿真结果表明，BLBO防碰撞算法较其他二叉树算法性能有明显提高，更适用于RFID防碰撞协议。
关键词：RFID；锁位；二叉树；防碰撞中图分类号：TN92 文献标识码：A 文章编号：1000-436X(2010)06-0049-09Research on RFID anti-collision algorithmsbased on binary treeWANG Xue, QIAN Zhi-hong, HU Zheng-chao, LI Yi-nan(College of Communication Engineering, Jilin University, Changchun 130025, China)Abstract: The bit-locking backoff (BLBO) anti-collision algorithm was proposed on the basis of binary algorithm, which puts forward the concept and orders of bit-locking. A reader recognizes the bits where there are collisions according to the results of decoding. Then the orders of bit-locking are transmitted to lock the bit collided, after which backoff strategy is adopted. When the reader recognizes one tag, it returns to the previous collided tag. The proposed algorithm fully takes the time of request into account, as well as transmission delay, power consumption and throughput of the system. The analysis on simulation result indicates that BLBO performs significantly better than the existing binary tree algorithms. It is suitable for the RFID anti-collision protocol in a greater deal.Key words: RFID; bit-locking; binary tree; anti-collision1引言RFID(radio frequency identification)利用射频信号通过空间耦合（交变磁场或电磁场）实现无接触信息传递并通过所传递的信息达到识别目的。
第31卷第6期电子与信息学报Vol.31No.6 2009年6月Journal of Electronics & Information Technology Jun. 2009基于二叉树分解的自适应防碰撞算法丁治国①②郭立②朱学永①汪赵华②①(解放军电子工程学院网络中心合肥 230037)②(中国科学技术大学电子科学与技术系合肥 230027)摘要：该文提出了一种基于二叉树分解的自适应防碰撞算法。
新算法利用标签EPC的唯一性，通过时隙分配估计标签的分布情况，对发生碰撞的时隙进行二叉树搜索，从而将一个庞大且复杂的二叉树分解成多个简单的小子二叉树，简化了搜索流程。
通过引入碰撞堆栈，并根据时隙状态自适应得调整搜索路径，从而进一步减少搜索的时隙数及提高了时隙的吞吐量。
理论和仿真实验证明了新算法的有效性，即在待识别的标签数量较多时，可有效的减少识别时间，提高搜索效率。
关键词：射频识别；防碰撞算法；二叉树分解；碰撞堆栈中图分类号：TN91 文献标识码：A 文章编号：1009-5896(2009)06-1395-05An Adaptive Anti-collision Algorithm Based on Binary-Tree Disassembly Ding Zhi-guo①②Guo Li②Zhu Xue-yong①Wang Zhao-hua②①(Center of Network, Electronic Engineering Institute PLA, Hefei, 230037, China)②(Department of Electronic Science and Technology, USTC, Hefei, 230027, China)Abstract: A new adaptive anti-collision algorithm based on binary-tree disassembly is proposed in this paper. In order to enhance the search efficiency, a big and complex binary-tree is disassembled to several small and simple binary-trees by estimating the distributing of tags. The introduction of the collision stack, as well as adjusting the search paths adaptively based on the state of slots, the performance of the new algorithm is improved further, including reducing the search timeslots and improving the throughput of timeslots. Theory and computer simulations show that the new anti-collision algorithm is practical, especially when the number of tags is large.Key words: Radio Frequency IDentification (RFID); Anti-collision algorithm；Binary-tree disassembly; Collision stack1引言射频识别(RFID)是20世纪90年代兴起并逐渐走向成熟的一种非接触式的自动识别技术，在物流、跟踪、定位等领域已得到广泛应用。
其中，用于解决读写器作用范围内多标签识别问题的防碰撞算法已成为该领域研究的热点之一。
标签防碰撞算法主要解决在读写器有效通信范围内，多个标签同时与读写器进行通信的问题。
常用的防碰撞算法一般可以分为两类，一种是基于时隙随机分配的ALOHA算法[1]，包括动态时隙ALOHA(DSA)算法[1]，分群时隙ALOHA 算法(GSA)[2]和标签估计算法(TEM)[3]等。
其特点是，算法简单，便于实现，适用于低成本RFID系统。
但由于该类算法的时隙是随机分配的，即存在一定的可能性，某一标签在相当长的一段时间内无法识别，即“tag starvation”问题，所以这类方法被称为可能性方法。
另一类是基于二进制树搜索(BS)算法[1]，包括动态二进制搜索(DBS)算法[1]，自适应二2008-07-02收到，2008-12-08改回高等学校博士学科点专项科研基金(20020358033)资助课题叉树搜索算法(ABS)[46]−，自适应查询树算法(AQS)[7]、返回式搜索算法(BackTrack)[8]和后退索引搜索算法[9]等。
该类算法比较复杂，识别时间较长，但不存在“tag starvation”问题，又被称为确定性方法。
本文提出了一种基于二叉树分解的自适应防碰撞算法。
新算法在二叉树搜索算法的基础上，利用标签EPC (Electronic Product Code，即电子产品代码)的唯一性，通过时隙分配估计标签的分布情况，对发生碰撞的时隙进行二叉树搜索，从而将一个庞大且复杂的二叉树分解成多个简单的小子二叉树，简化了搜索流程。
通过引入碰撞堆栈，并根据时隙状态自适应地调整搜索路径，从而进一步减少搜索的时隙数及提高了时隙的吞吐量。
理论和仿真实验证明了新算法的有效性，即在待识别的标签数量较多时，可有效的减少识别时间，提高搜索效率。
2防碰撞算法原理及相关的研究成果对于一个特定的RFID系统来说，任意一个RFID标签都有一个唯一确定的EPC。
读写器通过获取标签的EPC来确认标签的身份。
当读写器作用范围内有多个未识别的标签时，1396 电子与信息学报第31卷每个标签都会响应读写器的查询命令，发送自己的EPC，这样就不可避免会出现相互之间的干扰，即产生碰撞。
而防碰撞算法就是要提出相应策略，使读写器能依次对标签逐一进行识别。
目前，很多RFID系统都采用国际标准ISO/IEC1800026中的二进制树搜索(BS)算法，它采用曼彻斯特(Manchester)的编码方法，可以有效地识别碰撞比特出现的位置。
BS算法的实质就是通过多次比较，不断缩小响应标签的范围，直至对唯一的标签进行识别，并通过循环操作，依次识别所有标签。
但该算法是始终自上而下进行的，搜索的过程中会出现许多重复路径，搜索效率比较低。
自适应二叉树搜索(ABS)算法，自适应查询树(AQS)算法和返回式搜索(BackTrack)算法都是在BS算法的基础上，在搜索策略上进行的改进。
它们根据3种不同时隙状态(碰撞、空闲和可读)，自动地调整搜索路径，在不同程度上提高了搜索效率，减少读写器对标签的搜索时隙。
值得注意的是，上述防碰撞算法都是对一个庞大且复杂的二叉树进行操作的，在搜索的过程中难免会出现重复路、回头路或冤枉路。
在如图1所示的RFID系统中，读写器的作用范围内有6个待识别的标签，标签的EPC长度为4位。
以AQS算法为例，完成上述搜索需要12个时隙。
其中，由于标签Tag1和Tag2的EPC前3位都相同，所以需要深度为4的搜索，才能将两个标签区分开来。
如果能够根据标签EPC的分布情况，将一个庞大且复杂的二叉树分解成多个简单的小二叉树，逐一进行搜索，是否可以使用更少的时隙数来完成对所有标签的识别呢？根据下一节的描述，答案是肯定的。
图1 AQS算法的搜索流程3基于二叉树分解的自适应防碰撞算法如图2所示，可以通过初始分配4个时隙用来掌握所有标签的EPC的分布情况。
在这4个时隙里，读写器分别发送00、01、10和11的查询码，前两位EPC满足上述条件的标签在相应时隙内做出应答。
读写器根据应答可以判断，第1个和第3个时隙分别为空闲时隙和可读时隙，无需进行二叉树的搜索，读写器就可直接完成对标签的识别。
而在第2个和第4个时隙发生碰撞，需要以01和11为起点，继续二叉树的搜索。
这样就将原来一个庞大而复杂的二叉树问题分解为两个简单的小子二叉树进行解决。
在01的子二叉树中读写器直接发图2 初始分配4时隙的ABD算法的搜索流程送查询码010和011，需要4个时隙完成对Tag1，Tag2和Tag3的搜索，而在11的子二叉树中读写器直接发送查询码110和111，只需要2个时隙即完成标签Tag5和Tag6的搜索。
故新方法只需要4+4+2=10个时隙就完成了所有标签的搜索。
图3给出了初始分配8个时隙的解决方案，可以看到只有在读写器发送010这个时隙时标签出现碰撞，这样只需要在010的子二叉树下继续搜索。
所以该方案同样需要8+2=10个时隙完成所有标签的搜索。
当然也可以初始分配16个时隙进行搜索，由于所有时隙都是空闲和可读的，所以不存在子二叉树，但该方案需要16个时隙，显然不是最优方案。
图3 初始分配8时隙的ABD算法的搜索流程综上所述，下面对新算法进行一般性描述，由于新算法将一个复杂的二叉树分解成多个简单的小子二叉树依次进行搜索，所以新算法被称为基于二叉树分解的自适应防碰撞算法(Adaptive binary-tree disassembly anti-collision algorithm)简称ABD算法。
为了保证算法的高效率，在读写器中增加了碰撞堆栈，用以在子二叉树的返回搜索过程中，直接确定搜索的新起点，算法的流程如图4所示。
步骤 1 读写器初始分配2l(1l L≤≤其中L为标签EPC的长度)个时隙用来判断标签的分布。
l被称为区分度，其值越大表示估计的标签分布越细，分解后的子二叉树越多而且越小。
读写器在相应的时隙内发送长度为l的查询码，前l位符合查询码的标签做出响应。
步骤2 读写器根据时隙中发生碰撞的次数确定子二叉树的个数(02)ln n≤≤。
对于空闲时隙，由于没有标签存在，读写器不做处理。
对于可读时隙，读写器直接完成对标签的识别。
步骤3标签依次对子二叉树进行搜索，根据不同时隙状态，自适应地调整搜索路径：(1)碰撞时隙：判断将当前搜索是否为满叉的(1j=)，如果不是，将当前搜索深度值i保存到碰撞堆栈中S i=，表示该深度还有一个分支没有搜索，在进行返回搜索时，必第6期 丁治国等：基于二叉树分解的自适应防碰撞算法 1397图4 ABD 算法的流程框图须返回到该深度，继续另一个分支的搜索。
同时，由于该节点内有大于或等于2个标签存在，所以该节点需要进行二叉树分割，令1,0;i i j =+=读写器根据当前的,i j ，确定查询码继续搜索。
