基于标签分组的RFID防碰撞算法

　　0引言

　　作为未来物联网的核心，无线射频识别（RadioFrequencyIDentification，RFID）技术有可能无处不在地感知一切。RFID技术是一项利用射频方式进行非接触式双向通信、通过信号识别目标对象后获取相关数据的自动识别技术。其最常见的应用是通过存储在电子标签中的ID码来唯一地识别一个物品。由于其具有不需人工干预、读取距离大、数据容量大、能在恶劣环境下工作等优点，在供应链物流管理、公共管理、消费和生产领域得到广泛应用[1-2]。

　　RFID系统由天线、阅读器和标签组成：天线用于在标签和阅读器间传递射频信号；阅读器用来读取（有时还可以写入）标签信息；每个标签具有唯一的电子编码，附着在物体上标识目标对象。读写碰撞是RFID中最常见的问题，大多数场合下，需要RFID系统在同一时间完成对多个电子标签的识别，这就要求标签应该具有防碰撞的能力。采用好的防碰撞算法能够使阅读器在处理多标签的能力上得到很大改善，从而提高整个RFID系统性能[3-4]。通常RFID的标签防碰撞算法分为两大类：基于概率的ALOHA协议和基于轮询的树型协议[5-6]。ALOHA协议中常用的是动态帧时隙ALOHA协议。该协议要求标签被阅读器激活以后，在一个帧内随机选择一个时隙向阅读器传送其ID，标签一旦被识别后会转入休眠状态。算法的效率取决于帧长的选定，阅读器在每个读取周期里通过一个标签估计函数动态改变下一次阅读时帧的大小，由于帧长随标签的数量动态调整，可以有效地提高时隙利用率和系统的吞吐率。该协议的缺点是标签的随机选择会产生不确定性，增加了标签接入的不可预见性，严重时会出现标签永远不能接入的情况[7]。

　　树型协议常采用查询树算法和二进制搜索算法。查询树算法采用前缀匹配方式，每个标签都要有一个前缀匹配电路。阅读器广播一个查询码q，有匹配前缀的标签响应。当多个标签有相同前缀时，阅读器给q添加一个0或1，生成一个新的查询码，继续查询[8-9]。查询树算法是一种无存储算法，实现简单，成本低，但识别延时长。二进制搜索算法是一种确定性的接入算法，要求阅读器使用Manchester编码逐位地监测标签的响应，那些ID小于查询码的标签响应，一旦碰撞发生，阅读器将查询码中碰撞的最高位置为0后重新发送。面对同样的标签，二进制搜索算法每次的读取过程、所用时隙数、空时隙数都是确定不变的，因此其系统可靠性较高。其缺陷是每当阅读器成功识别了一个标签后，阅读器都会从根节点重新开始查询，工作效率较低，特别是标签数目比较多时读取标签的延时比较严重[10-11]。

　　时隙ALOHA协议是简单的概率性算法，对多负载的动态适应性更好。而二进制搜索算法的优势在于使用Manchester编码能够确定碰撞的准确位置，以此可以提高阅读器的读取效率[7]。本文考虑将两者结合设计一种基于标签分组的时隙ALOHA算法来提高阅读器的性能。

　　那么能不能将两者结合，设计一种新的混合算法来提高阅读器的性能呢？答案是肯定的，下面将介绍一种基于标签分组的时隙ALOHA算法。

　　1标签分组算法的基本思想

　　基于标签分组的时隙ALOHA的防碰撞技术核心思想是阅读器通过发送指令将范围内的电子标签按组固定分配在一个与其他标签组相异的时隙，各组电子标签分别在自己的时隙内完成与阅读器的数据交换[12-14]。同组内的电子标签可以通过Manchester编码鉴别出ID码中碰撞的特征位置，再结合二进制码的特点，利用碰撞反演出ID码[7]。因此算法的关键在于如何将电子标签分组以及如何设置碰撞特征位的位置。

　　先举一个简单的例子来解释一下该算法。假设标签的ID码长度为4，某阅读器的可读范围内最多有16个标签，其ID码分组如表1所示。

　　2算法实现流程

　　算法前提是标签端有一个前缀匹配电路和一个比较电路。电子标签的EPC编码长度目前有64、96和256位[2]，如果整体放入一个码表中，码表将十分巨大。因此将标签的版本号、厂商信息、产品类型和序列号编入各自的码表，逐个识别。阅读器发出的查询码可能是版本号、版本号+厂商信息或是版本号+厂商信息+产品类型。比较电路记录的是标签待识别编码与阅读器发出的查询码相异的位数。

　　算法具体步骤如下：

　　步骤1指定标签的ID长度，阅读器以此生成所有查询码字并储存，然后向其阅读区域广播开始识别命令。

　　步骤2时隙开始后，标签接收阅读器的查询码字，如果前缀匹配且只有1位与查询码不同，标签激活，之后进入就绪状态，向阅读器发送其ID。

　　步骤3阅读器根据每个时隙的识别情况，做出以下调度反应[7]：

　　程序前

　　If该时隙没有标签响应，阅读器采用“提前结束”的方式，时隙提前结束。

　　Elseif该时隙没有碰撞，即只有一个标签响应，阅读器直接识别，时隙结束。

　　Else该时隙有碰撞，即有两个或以上的标签响应。阅读器根据查询码和碰撞的特征位反演出标签的ID，时隙结束。

　　4结语

　　本文在介绍常用的ALOHA和树型防碰撞算法后设计了结合两者优点的基于标签分组的帧时隙ALOHA算法，并对三种算法的吞吐率进行了比较。由于新算法将标签分组，并利用特征位对同组内的标签进行区别，既避免了不同组标签的碰

　　撞，又使得一个时隙内可以鉴别一组标签，在标签数较多时具

　　有明显的优势。文中对标签分组的基本思想和实现步骤分别作了介绍，并用软件进行了验证。当然该算法也存在不足，当标签在码表中比较分散或标签较少时将不可避免产生大量的空闲时隙，性能将明显下降，因此算法还有待改善与提高。