梅佳伟，李 晖

（沈阳工业大学 信息科学与工程学院，辽宁 沈阳110870）

0 引 言

射频识别（Radio Frequency Identifcation，RFID）技术起始于1973年。作为自动识别和数据获取的一部分，RFID系统通过无线网与网络系统进行互交，能够单独识别追踪并捕获包装中货物、动物甚至人的标签状态或信息[1]。因此，RFID将会取代现在普遍使用的条形码广泛应用于物流、零售和存储管理等领域[2]。

由于标签的体积和造价等原因限制，一个阅读器读取范围内同时出现多个标签时，它们会同时响应阅读器的查询信息，而标签本身无法感知到周围标签的存在，此时就会出现标签信息的碰撞[3]，导致阅读器无法顺利获取标签信息。因此，射频标签的防碰撞成为射频识别过程中的一个关键技术[4]。

受现有标签技术和成本制约，目前的标签防碰撞算法主要分为两类：一种是以ALOHA算法为主的非确定性算法[5-8]，一种是以二进制搜索算法为基础的确定性算法。其中，ALOHA算法容易出现有一些标签可能长时间与其他标签发生碰撞而不能被识别的现象，即标签饿死现象。二进制树搜索的防碰撞算法主要包括动态的二分支搜索DBS算法、查询树QT算法[9]和碰撞树CT算法[10]等。这些算法主要通过不断对标签池查询的方式，达到完全识别未读取的标签的目的。它不存在标签饿死现象，但是造成了通信量的大量增加和识别时间长的问题。

在此基础上出现了一些多叉树的防碰撞算法，识别过程中通过降低查询轮数或者提高查询码的准确程度来降低通信量和空闲时隙。……