射频识别(Radio Frequency Identification, RFID)技术是一种自动识别方法,它通过射频电波对存储在射频标签芯片中的数据进行无线读取。RFID系统通常由阅读器、标签、应用系统构成。典型的RFID阅读器一般具有充足的存储容量和计算能力。RFID标签却存在很大的差异,从只能接收并响应阅读器命令的无源被动标签,到具有独立的片上微控系统、存储器、电源等的主动标签和智能标签。由于低成本、低能耗,无源被动标签越来越受到人们的青睐,并被广泛使用。许多RFID应用系统需要同时对多个射频标签进行识别和处理。当多个标签或阅读器同时在相同信道进行信息传输的时候,就会发生碰撞(collision),增加系统通信开销,延长数据交互时间,甚至导致RFID系统工作失效。因此,高效的防碰撞算法(anti-collision algorithm),对于RFID多标签识别系统,特别是大规模RFID应用系统,非常重要。RFID系统中碰撞可以分为标签碰撞(tag collision)和阅读器碰撞(reader collision)。本论文主要研究和解决标签碰撞和防碰撞问题。当多个标签同时响应阅读器的查询请求,它们发送的数据信号在信道中相互干扰,就会引发标签碰撞,致使阅读器无法完成对这些标签的识别和数据采集。目前解决标签碰撞的防碰撞算法主要分为：基于ALOHA的时隙类算法,如：时隙ALOHA算法(S-ALOHA)、帧时隙ALOHA算法(FSA)；基于树搜索的树型算法,如：查询树算法(QT)、二进制树算法(BT)。几乎所有已知防碰撞算法的识别效率都低于50%,这不能满足实际生产应用的需要。因此,提高多标签识别效率,打破多标签识别效率瓶颈,成为防碰撞算法研究的重要内容和目标。同时,在防碰撞算法研究中,通常假设标签编号成均匀分布。事实上,均匀分布之外的其它分布模式,如连续分布、部分连续分布,在很多应用场合使用更加频繁,例如：集装箱码头、大型货仓、进出口检测等。因为,这些场合中,许多附着RFID标签的物品属于同类物品,它们通常来自同一地域的同一生产厂商。根据标签编号分配和使用原则,它们所使用标签的编号主要是连续分布。所以,类似这样的分布模式,在防碰撞算法研究中应当给予充分的关注。论文首先针对当前防碰撞算法中存在的效率瓶颈问题,提出了一种高效的防碰撞算法,即碰撞树算法(collision tree protocol, CT)。CT算法成功的打破了先前防碰撞算法的效率瓶颈,首次将多标签识别效率提高到50%以上。碰撞行为和碰撞位的处理是CT算法的关键和核心。CT算法根据阅读器检测到的碰撞位信息,直接生成两个新的前缀,同时将发生碰撞的标签组分为两个组。以此,CT算法完全消除了多标签识别过程中可能存在的空周期(idle cycle),大幅度提高了RFID多标签识别的性能。论文同时建立了一种新的二叉树结构,即碰撞树(collision tree),用于描述CT算法的多标签识别过程,分析CT算法的识别性能。根据碰撞树的定义,碰撞树的所有中间节点与CT算法的碰撞周期一一对应,碰撞树的所有叶子节点与CT算法的可读周期一对应。碰撞树是一种满二叉树(full binary tree),碰撞树中没有空节点(idle node)。根据碰撞树的性质,可以简单直接的计算和分析CT算法的识别性能。CT算法的另一个重要优势在于其识别性能的稳定性(stability)。稳定性是论文提出的用于分析和评价防碰撞算法性能的一项新指标。在流水生产、自动控制等许多RFID应用系统中,标签识别算法的稳定性具有非常重要的意义。因为这些系统对标签的识别时间和系统能耗等具有较为严格或精确的定量控制要求。防碰撞算法的稳定性是指算法的识别性能只与识别标签的数量有关,而不受其它因素的影响,同时,算法的平均识别性能趋于一个常数。理论分析和实验结果均表明：CT算法是一个稳定高效的RFID多标签识别防碰撞算法。由于CT算法简单易于实现,能以较低的系统消耗,快速有效的完成RFID标签的识别,所以,CT算法能够适用于各种RFID标签识别系统,解决标签碰撞问题。由于CT算法完全消除了防碰撞算法中可能存在的空周期,将多标签识别效率提高到50%以上,打破了防碰撞算法的效率瓶颈,并且具有严格的碰撞树结构对其进行描述和分析,所以,CT算法开启了基于碰撞树的防碰撞算法系列,为后续防碰撞算法研究奠定了基础。在CT算法基础上,论文提出了两种新的防碰撞算法：二元确定性碰撞树算法(ICT)和双响应碰撞树算法(BCT)。两种算法的提出,进一步完善了基于碰撞树的防碰撞算法系列。在ICT算法中,论文提出了二元确定性原理,并将其用于RFID多标签识别过程,提高算法的识别性能。同时,标签编号连续分布模式和部分连续分布模式被纳入了防碰撞算法的研究范畴。根据二元确定性原理,如果在阅读器收到的标签响应中,只有一位数据位发生碰撞时,ICT算法通过指派该碰撞位的值,就能在同一个查询周期中同时识别到两个标签,而无需继续查询。理论和实验结果表明：当标签编号连续分布时,ICT算法能将多标签识别效率提高到100%以上。因此,ICT算法特别适用于标签编号连续分布和部分连续分布的RFID应用场合。在BCT算法中,论文提出了双响应机制,将标签响应周期划分为两个子周期,使两组标签能够在两个响应子周期中分别独立地响应阅读器的查询请求。通过这种方式,BCT算法进一步提高了RFID系统多标签识别的性能。特别是在减少阅读器的查询次数,降低阅读器和标签的通信数据量,以及降低系统能耗等方面,BCT算法具有明显的优势。无论标签编号是均匀分布还是连续分布,BCT算法的识别效率均在100%以上。同CT算法和ICT算法一样,BCT算法中标签每次响应只与当前收到的前缀及其特征位有关,而与过往的查询过程和响应历史无关。因此,BCT也属于无记忆(memoryless)防碰撞算法,可适用于无源被动RFID多标签识别系统等各种RFID应用系统,解决标签碰撞问题。论文提出了三种基于碰撞树的RFID多标签识别防碰撞算法,将标签识别效率提高到50%以上,同时建立了基于碰撞树的防碰撞算法分支系列,为后续防碰撞算法研究和应用奠定了基础。