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

《基于查询树的射频标签防碰撞算法优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、优化　　1研究背景和概述　　射频标签（RFIDtag）又称电子标签，是二十世纪八九十年代兴起的一种非接触式的物品单元自动识别通信技术，可通过无线信号识别特定目标并读写相应数据。在跟踪、物流、定位等领域已得到广泛应用，例如：图书馆门禁系统，交通收费，仓储管理、货架管理以及食品安全溯源等。其中，用于解决读写器作用范围内多标签识别情景下的射频标签识别防碰撞方法已成为该领域的重要研究点。　　射频标签的防碰撞方法主要是为了解决在射频标签识别设备的有效通信区域内，当多个射频标签同时与识别设备进行通信时产生的无线冲突问题。目前，常用的防碰撞方法主要有两类，一类是基于时隙随机分配的ALOHA方法，由于该类

3、方法的时隙是随机分配的，某一标签在相当一段时间内可能无法识别，造成“饥饿”（Tagstarvation）问题。另一类是采用二叉树搜索的方法，又称查询树算法，用射频标签识别设备发送的标签地址前缀对射频标签的地址空间进行空间分区搜索，利用该方法，射频标签可以简化设计、降低成本，是目前多射频标签识别防碰撞算法的研究热点。　　2查询树（QT）算法及相关概念　　QT算法利用了二进制前缀树（BinaryTrie）数据结构，该数据结构由节点（TNode）和节点间的边组成，节点分布在树的n个分层中。节点类型分为根节点，内部节点和叶子节点。每一个根节点或者内部节点可能有1个或者2个子节点，叶子节点都在树的最

4、低层。节点和它的子节点间有直接相连的边，每条边对应一个标签：字符‘0’或者字符‘1’。一般每个节点与左子节点间的边（若有）对应字符‘0’，与右子节点间的边（若有）对应字符‘1’。从根节点到每一个叶子节点的无重复节点的依次连接的边组成一条路径。在基于QT的射频标签防碰撞算法中，把长度为n的射频标签的地址集合组织为深度为n+1的二进制前缀树，每个射频标签地址和二进制前缀树的路径一一对应。例如，一个长度为3，地址个数为3的射频标签地址集合Seta为{“010”，“011”，“110”}，此射频标签地址集合对应的二进制前缀树如图1所示。　　QT算法采用前缀匹配法对射频标签的地址空间进行分割。该算法

5、工作时，首先给出一个1比特前缀，所有与该前缀匹配的射频标签进行响应。如果响应的射频标签数量大于1个，产生冲突，则算法给出一个2比特的前缀，依次不断增加发出的地址前缀的长度，直到没有冲突，读取一个射频标签地址。算法按照类似二叉树深度优先搜索的方式，对射频标签的地址空间进行遍历，读取所有射频读写器通讯范围以内的射频标签。　　例如对于图1表示的RFID地址集合，QT算法发出地址前缀“0”，地址为“010”和“011”的射频标签响应，出现冲突。然后QT算法发出地址前缀“00”，无标签响应。然后QT算法发出地址前缀“01”，地址为“010”和“011”标签响应，出现冲突。然后QT算法发出地址前缀“0

6、10”，地址为“010”的标签响应，完成一个标签读取。然后QT算法发出地址前缀“011”，地址为“011”的标签响应，完成一个标签读取。对于图1所示Trie树的左分支，QT算法发出5个地址前缀，读取2个标签地址，读取全部3个地址，需要发出6个地址前缀。　　3查询树算法优化方法综述　　QT算法并不能保证每发出一个地址前缀就可以读取一个射频标签地址。对于读写器发出的射频标签地址前缀，如果有多个标签进行响应，就会出现冲突的问题；如果没有标签响应，就会出现空读取的问题。研究人员提出了多种方案，避免上述两个问题，提高射频标签的读取效率。　　3.1分支推断优化　　如果射频读写器发出一个地址前缀p，出现

7、冲突；射频读写器又发出一个地址前缀“p0”，响应的射频标签数量是0；那么射频读写器可以推断出，如果发出地址前缀“p1”，一定会出现多标签冲突；因此射频读写器不发送地址前缀“p1”，直接发送地址前缀“p10”，和“p11”，至少优化了一次地址前缀发送。　　3.2多叉树搜索优化　　在基本的QT算法中，如果射频读写器发送地址前缀“p”匹配出现冲突，下一次发送地址前缀“p0”和“p1”。而如果采用基于多叉树搜索的QT算法，如果地