基于查询树的射频标签防碰撞算法优化

摘 要射频标签 （RFID tag）又称电子标签，是二十世纪八九十年代兴起的一种非接触式的物品单元自动识别通信技术，在跟踪、物流、定位等领域已得到广泛应用。其中，用于解决射频读写器作用范围内多标签识别情景下的射频标签识别防碰撞方法已成为该领域的重要研究点。相对于基于通讯信道竞争的ALOHA算法，经典的查询树（Query Tree，下文简称QT）射频标签防碰撞算法由于标签侧电路设计简单，比较适用于利用射频读写器反射能量的被动标签。本文对近年来针对查询树（QT）射频标签防碰撞算法的各种优化技术进行总结分析，并提出下一步的研究方向。

【关键词】射频标签 查询树 防碰撞 优化

1 研究背景和概述

射频标签 （RFID tag）又称电子标签，是二十世纪八九十年代兴起的一种非接触式的物品单元自动识别通信技术，可通过无线信号识别特定目标并读写相应数据。在跟踪、物流、定位等领域已得到广泛应用，例如：图书馆门禁系统，交通收费，仓储管理、货架管理以及食品安全溯源等。其中，用于解决读写器作用范围内多标签识别情景下的射频标签识别防碰撞方法已成为该领域的重要研究点。

射频标签的防碰撞方法主要是为了解决在射频标签识别设备的有效通信区域内，当多个射频标签同时与识别设备进行通信时产生的无线冲突问题。目前，常用的防碰撞方法主要有两类，一类是基于时隙随机分配的ALOHA方法，由于该类方法的时隙是随机分配的，某一标签在相当一段时间内可能无法识别，造成“饥饿”（Tag starvation）问题。另一类是采用二叉树搜索的方法，又称查询树算法，用射频标签识别设备发送的标签地址前缀对射频标签的地址空间进行空间分区搜索，利用该方法，射频标签可以简化设计、降低成本，是目前多射频标签识别防碰撞算法的研究热点。

2 查询树（QT）算法及相关概念

QT算法利用了二进制前缀树（Binary Trie）数据结构，该数据结构由节点（TNode）和节点间的边组成，节点分布在树的n个分层中。节点类型分为根节点，内部节点和叶子节点。每一个根节点或者内部节点可能有1个或者2个子节点，叶子节点都在树的最低层。节点和它的子节点间有直接相连的边，每条边对应一个标签：字符‘0或者字符‘1。一般每个节点与左子节点间的边（若有）对应字符‘0，与右子节点间的边（若有）对应字符‘1。从根节点到每一个叶子节点的无重复节点的依次连接的边组成一条路径。在基于QT的射频标签防碰撞算法中，把长度为n的射频标签的地址集合组织为深度为n+1的二进制前缀树，每个射频标签地址和二进制前缀树的路径一一对应。例如，一个长度为3，地址个数为3的射频标签地址集合Seta为{“010”，“011”， “110”}，此射频标签地址集合对应的二进制前缀树如图1所示。

QT算法采用前缀匹配法对射频标签的地址空间进行分割。该算法工作时，首先给出一个1比特前缀，所有与该前缀匹配的射频标签进行响应。如果响应的射频标签数量大于1个，产生冲突，则算法给出一个2比特的前缀，依次不断增加发出的地址前缀的长度，直到没有冲突，读取一个射频标签地址。算法按照类似二叉树深度优先搜索的方式，对射频标签的地址空间进行遍历，读取所有射频读写器通讯范围以内的射频标签。

例如对于图1表示的RFID地址集合，QT算法发出地址前缀“0”，地址为“010”和“011”的射频标签响应，出现冲突。然后QT算法发出地址前缀“00”，无标签响应。然后QT算法发出地址前缀“01”，地址为“010”和“011”标签响应，出现冲突。然后QT算法发出地址前缀“010”，地址为“010”的标签响应，完成一个标签读取。然后QT算法发出地址前缀“011”，地址为“011”的标签响应，完成一个标签读取。对于图1所示Trie树的左分支，QT算法发出5个地址前缀，读取2个标签地址，读取全部3个地址，需要发出6个地址前缀。

3 查询树算法优化方法综述

QT算法并不能保证每发出一个地址前缀就可以读取一个射频标签地址。对于读写器发出的射频标签地址前缀，如果有多个标签进行响应，就会出现冲突的问题；如果没有标签响应，就会出现空读取的问题。研究人员提出了多种方案，避免上述两个问题，提高射频标签的读取效率。

3.1 分支推断优化

如果射频读写器发出一个地址前缀p，出现冲突；射频读写器又发出一个地址前缀“p0”，响应的射频标签数量是0；那么射频读写器可以推断出，如果发出地址前缀“p1”，一定会出现多标签冲突；因此射频读写器不发送地址前缀“p1”，直接发送地址前缀“p10”，和“p11”，至少优化了一次地址前缀发送。

3.2 多叉树搜索优化

在基本的QT算法中，如果射频读写器发送地址前缀“p”匹配出现冲突，下一次发送地址前缀“p0”和“p1”。而如果采用基于多叉树搜索的QT算法，如果地址前缀“p”匹配失败，下一步射频读写器直接发送“p00”，“p01”，“p10”和“p11”。研究表明，一般情况下，基于多叉树搜索的QT算法性能并不优于基本的QT算法。

3.3 发送递增前缀优化

在基本的QT算法中，如果射频读写器发送地址前缀“p”匹配出现冲突，则下一次发送地址前缀“p0”和“p1”。而采用了递增前缀的QT算法，下一次只发送“0”或者“1”。这種技术需要射频标签跟踪射频读写器的状态，容易发生状态不同步的问题。

3.4 冲突位置检测优化

射频标签识别的通讯协议一般采用曼切斯特编码。曼切斯特编码的核心特征是在每一位数据的中心都有跳变，当发生冲突时，曼切斯特编码中心的跳变消失。因此如果设计了相应的检测电路，射频读写器可以识别出发生冲突地址的第一个比特位置。下一次，射频读写器可以从该位置开始发出查询前缀，避免了中间地址前缀的发送过程。如图2所示，射频读写器发出地址前缀“q”后，地址为“q010”，“q011”，“q111”的三个射频标签响应，出现冲突。基本的QT算法，射频读写器发出前缀“q0”，仍然出现冲突，然后射频读写器继续发出“q01”，仍然出现冲突，然后射频读写器发出前缀“q010”，读取一个射频标签。而具有冲突位置检测能力的QT算法，在射频读写器发出地址前缀“q0”时，能够根据射频标签的响应确定冲突位于地址前缀“q01”，所以射频读写器不发送地址前缀“q01”，直接发送地址前缀“q010”，减少了一次产生冲突的前缀匹配过程，优化了射频标签识别效率。

3.5 提前终止优化

在能够进行冲突位置检测的基础上，射频读写器可以在发现冲突后命令射频标签停止进行响应，不发送已发生冲突后无意义的后续射频标签地址。

3.6 混合算法优化

一些研究表明，综合利用查询树和ALOHA的射频标签识别算法能够获得更高的射频标签识别吞吐率，但是这些算法相对都比较复杂，不易于在使用反射能量的被动射频标签上，在本文中不讨论该类算法。

4 查询树算法优化方向分析与研究

4.1 结合物理层协议进行研究

在前文所述的递增发送前缀、冲突位置检测和提前终止等方法对射频通讯环境进行了比较理想的假设，没有充分考虑出现通讯错误导致射频读写器和射频标签的状态不同步、射频标签识别提前终止命令没有被所有标签接收、由于不同标签射频信号的动态范围不同导致冲突位置检测失败等问题。如果结合射频标签使用的物理层协议对上述问题进行全面的理论分析与仿真，并提出解决方案，必将推动上述方法的实用化。

4.2 研究参考待识别标签数量信息的自适应算法

上文提到，研究表明，一般情況下，多叉树搜索的QT算法性能并不优于基本的QT算法。但是如果根据待读取标签的数量动态调整每次地址前缀扩展的长度，就可以即减少冲突，又避免没有标签响应的空查询，提高射频标签识别效率。研究参考待识别标签数量信息的自适应算法、以及研究对待读取射频标签的数量进行估计的方法，都是目前学术界较活跃的研究方向。

4.3 研究已知射频标签地址范围信息情况下的算法

如果射频标签的地址长度是n个bits，QT算法假设射频标签的所有地址的总数量是2n，我们假设这2n个射频标签的地址集合是S2n，某一次射频标签列表操作需要读取的射频标签地址集合为Sr。基本的QT算法相当于是在集合S2n，中通过地址空间分割和遍历识别Sr中的每一个射频标签。实际上，假设在一个超级市场、一个仓库、或者一个区域内进行射频标签识别操作，我们只关心已经入库的射频标签，该类射频标签的地址集合称为系统可能标签地址集合Sp。显然，Sp∈S2n，我们可以设计射频标签识别算法在地址集合Sp内搜索，而不是在S2n中搜索，从而获得较高的射频标记列表操作吞吐率。基本的思路是研究用二叉树表示的射频标签地址集合Sp，只在可能存在射频标签地址的二叉树分支路径上搜索，从而减少射频标签地址前缀的发送数量，优化射频标签识别效率。

4.4 研究射频标签地址编码策略对算法的影响

EPC（Electronic Product Code）即电子产品编码，是一种编码系统。它建立在EAN.UCC（即全球统一标识系统）条型编码的基础之上，并对该条形编码系统做了一些扩充，用以实现对单品进行标志。EPC编码分为很多类型，例如EPC-96编码由头字段、EPC管理、对象类别和序列号四个字段组成。 EPC编码是一种层次化的编码策略。而“随机编码”策略，顾名思义，就是对每一个射频标签随机生成和分配一个地址。通过计算机仿真，可以得出结论，对于同样数量的待识别射频标签，如果采用“随机编码”策略，利用QT算法可以获得比类似EPC编码的层次化编码策略明显更高的射频标签识别吞吐率。而类似EPC编码的层次化编码策略也有一定的应用需求，如何优化QT算法，提高采用类似EPC编码的层次化编码策略时的射频标签识别吞吐率，也是具有较大实用价值的研究方向。

5 结论

射频标签又称电子标签，是一种得到广泛应用的物品单元自动识别通信技术。解决射频读写器作用范围内多标签识别情景下的射频标签识别防碰撞方法已成为该领域的重要研究点。经典的查询树（QUERY TREE）射频标签防碰撞算法由于标签侧电路设计简单，比较适用于利用射频读写器反射能量的被动标签。本文对近年来基于查询树的射频标签防碰撞算法的各种优化技术进行总结分析，并提出了结合物理层协议进行防碰撞算法设计、研究参考待读取标签数量信息的自适应算法、研究已知射频标签地址范围信息情况下的算法、研究射频标签地址编码策略对算法的影响等多个具有较大实用价值和现实意义的研究方向。

参考文献

[1]C.Law，K.Lee，and K.-Y.Siu，“Efficient memoryless protocol for tag identification，”in Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications，（Toronto，CA），pp.75-84，Aug.2000.

[2]J.H.Choi，D.Lee，and H.Lee，“Query tree-based reservation for efficient RFID tag anti-collision，”IEEE Commun.Lett.，vol.11，no.1，pp.85-87，2007.

[3]李竞.生活必需品现场保障数据系统的设计与实现[J].中国安全生产科学技术，2014（11）：94-100.

[4] 张予帅，蒋泰，苏平，罗义学，肖煌.ISO 18000-6 Type B与Type C标准的分析与比较[J].广西科学院学报，2009（04）：336-339.

[5]Ziling，Zhou Binbin Chen，Haifeng Yu，“Understanding RFID counting protocols”，IEEE/ACM Transactions on Networking （TON），vol.24，（01），pp312-327，2016.

作者简介

李竞（1979-），男，河北省承德市人，硕士学位，现为高级工程师。主要研究方向：信息技术在应急指挥、应急救援与应急保障方向的应用。

作者单位

1.中国安全生产科学研究院 北京市 100012

2.重大危险源监控与事故应急技术国家安全监管总局安全生产重点实验室 北京市 100012