基于碰撞树的自适应多叉树RFID防碰撞算法

吕敬祥，刘 清，过继红

基于碰撞树的自适应多叉树RFID防碰撞算法

*吕敬祥，刘 清，过继红

（井冈山大学电子与信息工程学院，江西，吉安 343009）

提出了一种自适应多叉树防碰撞算法，该算法构建了无碰撞时隙的二叉查询树，通过计算碰撞因子估计标签数量，从而自适应的选择二叉树或四叉树。理论和仿真表明：该算法克服了现有算法数据传输量大的缺点，同时在二叉树分支内实现了无碰撞时隙以减少总时隙，对多标签情况下，通过自适应的选择四叉碰撞树来减少碰撞时隙。算法有效地减少了数据传输量，提高了时隙利用率和系统吞吐率，具有一定的创新性。

射频识别；冲突树；防碰撞；多叉树；自适应；堆栈

射频识别（Radio frequency identification, RFID）技术无需人工干预就能完成信息输入和处理，具有保密性好、存储容量大等优点，因此在跟踪、定位、物连网等领域中有着广泛的应用[1]。RFID系统工作时，不可避免的会出现多个标签同时处在阅读器的作用范围内，因此会出现通信冲突，即碰撞，合理的解决这一问题成为了RFID领域的研究热点之一。

常用的防碰撞算法一般可分为两类，一类是随机算法，主要是ALOHA算法，包括时隙ALOHA(S-ALOHA, Slotted ALOHA)算法[2]，动态帧时隙ALOHA(Dynamic Framed Slotted ALOHA，DFSA)算法[3]，增强型动态帧时隙ALOHA (Enhanced Dynamic Framed Slotted ALOHA，EDFSA)算法[4]等。其特点是算法简单、便于实现，适应于低成本标签，但这类算法存在“标签疾饿”问题（某一标签在相当长的一定时间内无法识别）。另一类是确定性算法，主要是基于树分叉算法，其核心思想是读写器根据碰撞信号，按深度优先思想逐步缩小搜索范围直到找到符合指定条件的标签。主要有查询树算法(Query Tree QT)[5]、改进的四叉树(Improved 4-ary Query Tree Algorithm)算法[6]、ABS算法(Adaptive Binary Splitting)[7]等。这种基于树的算法可以达到100%的读取率，但算法设计较复杂，识别时间长。

本文在查询树的基础上，提出一种基于冲突树的自适应查询树防碰撞算法（Adaptive Query Multi-Tree Anti-Collition Algorithm based on Collision-Tree，AQMTC）。该算法通过阅读器的记忆功能，大量减少了数据传输量，通过修改命令和标签的记忆功能，优化查询前缀，从而避免了大量的空闲时隙。通过计算碰撞因子动态的选择查询树叉数，进而能自动适应阅读器范围内有大量标签的情况。文章通过数学分析准确地描述了AQMTC算法所需时隙数。

1 RFID防碰撞算法分析

树型搜索算法采用比特冲突检测协议作为防碰撞方案，阅读器必须能够准确的定位冲突比特位置。幸运的是，曼切斯特编码能很好的检测出多个标签碰撞时的碰撞比特，故可根据碰撞比特信息按一定规则重新搜索标签。

1.1 叉树自适应选择算法

图1分别利用二叉树和四叉树识别0100,1011,0011,1001四个标签的例子。由图1对比两种树，显然可知随着叉树的增多，虽然减少了碰撞时隙，但同时增加了空时隙。单一的使用某种叉树必然导致较多的碰撞时隙或空时隙，如果能自适应的选择叉树将能有效地提高搜索算法。

图1 二叉树和四叉树

为了有效地利用碰撞信息文献[8]定义了碰撞因子。

由上式看出，越大碰撞因子越大，故可根据碰撞因子估计待识别的标签树。

故有：

所需平均时隙数：

对上式求对L的偏导：

四叉树所需平均时隙为

1.2 二叉查询树减少空时隙算法讨论

由图1，可以看出普通的二叉树不仅搜索深度值大而且也存在一定的空时隙。如果能降低空时隙则算法的搜索效率明显能够得到改善。文献[8]提出一种二叉树分解的自适应防碰撞算法，通过引入碰撞堆栈，并根据时隙状态自适应调整搜索路径。文献[9]在二叉树算法的基础上提出一种以矩阵形式为搜索结构的混合防碰撞算法，从而缩短了标签的搜索时间。文献[10]在二叉树算法及其各种改进的算法基础上，提出一种基于冲突树的标签自适应防碰撞算法（ACT），合理的利用堆栈和后退搜索算法大量地除去了空闲时隙，从而提高了算法效率。综合大量文献，作者构造一种完全没有空时隙的算法，如图2所示的二叉树，只有冲突时隙和成功时隙。

图2 一种只有成功时隙和冲突时隙的二叉树

2 基于碰撞树的自适应多叉树防碰撞算法

2.1 AQMTC算法原理

采用上述算法以后，标签在二叉树时不会出现没有标签信息传输的空时隙，只存在碰撞时隙和成功时隙。在标签中设置状态寄存器用于标识标签处在等待、激活、休眠3中状态。

等待状态 标签状态寄存大于0，表示此时标签不传输信息，只需要等待。

激活状态 标签状态寄存器为0，表示标签试图传输自身的信息。

休眠状态 标签状态寄存器小于0，表示标签不传输信息直到完全识别所有标签为止。

2.2 AQMTC算法流程

AQMTC算法步骤：

步骤7 如果堆栈中有数据，从堆栈中读取数据，对二叉树设置B=0，返回到步骤2，对四叉树，AB按如下状态转移00转到01，01转到10，10转到11，11转到00；如果堆栈中午数据转步骤8

步骤8 结束本次识别。

AQMTC算法流程如图3所示。

图3 AQMTC算法流程图

3 算法性能分析

3.1 时隙分析

即为此时总时隙数。

基于碰撞树的自适应多叉树算法总时隙推导如下。

根据吞吐率定义：

3.2 传输数据量分析

4 算法仿真

在Matlab7环境下对算法进行仿真，假设系统标签分布是均匀的。由前面的推导可知，当待识别的标签数大于3时平均时隙四叉树优于二叉树。本文构建冲突树，自适应的选择叉树不仅减少时隙数，使通信量大大的降低，有效的利用了信道。

图4 二叉树和四叉树时隙比较

图5 三种算法时隙比较

图6 两种算法通信量比较

设标签长度为8位，图6对比了QT算法和AQMTC算法的通信量。可看出AQMTC算法数据通信量远远小于QT算法，随着标签的增加优势更加明显。从以上三个图完全可以看出，新算法的时隙数，通信量明显有所提高，进而系统的吞吐量也会随之改善，因而算法优势是显而易见的。

5 结论

本文在全面总结二叉查询树、四叉查询树等算法的基础上，提出一种构建冲突树的自适应多叉树防碰撞算法。该算法利用曼切斯特编码准确定位碰撞位，在阅读器中设置状态寄存器，存储标签状态，同时在阅读器中设置堆栈，记录碰撞位的最高位、最低位和查询前缀；通过计算碰撞因子动态的估计标签数量，从而自适应的调整查询叉树，达到了减少数据传输量，降低标签识别所需时隙数，提高系统的吞吐率目的。

[1] 周晓光.射频识别技术原理与应用实例[M].北京:人民邮电出版社, 2006.

[2] Bin Z, Kobayashi M, Shimizu M. Framed ALOHA for Multiple RFID Objects Identification[M].Tokyo:Oxford University Press, 2005:991-999.

[3] Cha J R, Kim J H. Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system[A].Consumer Communications and Networking Conference,CCNC 2006,3rd IEEE[C].2006:768-772.

[4] Lee S, Joo S, Lee C. .An enhanced dynamic framed slotted ALOHA algorithm for RFID tag[C].the Second Annual International Conference on Mobile and Ubiquitous Systems:Networking and Services,San Diego,CA,United States,2005:166-172.

[5] Yang C N,He J Y.An effective 16-bit random number aided query tree algorithm for RFID tag anti-collsion[J]. Communications Letters,IEEE,2011,5(15): 539-541.

[6] Yonghwan Kim, Seong Joon Lee, Kwang Seon Ahn. Improved 4-ary Query Tree Algorithm for Anti-Collision in RFID System[C].Advanced Information Networking and Applications, 2009. AINA’09, International Conference on,2009:699-704.

[7] Wang Xue,Qian Zhihong, Hu Zhengchao, et al. Research on RFID anti-collision algorithms based on binary tree[J].Journal on Communications,2010,31(6): 49-57 (in Chinese).

[8] 丁治国,郭立.基于二叉树分解的自适应防碰撞算法[J].电子与信息学报,2009,31(6):1395-1399.

[9] 孙文胜,刘婷.一种改进的基于二叉树搜索的防碰撞算法[J].计算机工程,2011,37(10):257-259.

[10] 陈天娥,程载和.基于冲突树的RFID自适应防碰撞算法[J].计算机应用,2010,30(7):1728-1735.

Adaptive Query Multi-Tree Anti-Collision Algorithm based on Collision-Tree

*LÜ Jing-xiang，LIU Qing，GUO Ji-hong

(School of Electronics and Information Engineering, Jinggangshan University, Ji’an, Jiangxi 343009, China)

An adaptive query multi-tree anti-collision algorithm is proposed. The new algorithm computes the collision factor and estimates the number of the tags so that it can adaptively use the binary-tree or the quad-tree. The theory and simulation show that the new algorithm overcomes big data transmission by constructing collision-tree. It also can reduce total slots by reducing slot-free in the binary-tree and using adaptive binary-tree or the quad-tree in the case of many tags. The new algorithm has certain innovations.

radio frequency identification; collision-tree; anti-collision; multi-tree; adaptive; stack

TP301.6

A

10.3969/j.issn.1674-8085.2014.02.009

1674-8085(2014)02-0039-06

2013-11-03；

2014-01-18

*吕敬祥(1979-)，男，湖南邵阳人，讲师，硕士，主要从事RFID技术研究(Email: ljingxiang2013@163.com);

刘 清(1977-)，男，江西吉安人，副教授，博士，主要从事图像处理研究(Email: liuqing960@163.com);

过继红(1981-)，女，江西抚州人，讲师，硕士，主要从事通信系统研究(Email: gjh-81@163.com).