一种自调整多叉树RFID 多标签防碰撞算法

张娜，王志勇*

（浙江理工大学信息学院，浙江杭州，310018）

一种自调整多叉树RFID 多标签防碰撞算法

张娜，王志勇*

（浙江理工大学信息学院，浙江杭州，310018）

随着RFID技术应用领域的拓宽，有效地解决多标签碰撞问题是提高RFID系统性能的关键。在树型搜索防碰撞算法分析的基础上，提出一种自调整多叉树防碰撞算法。该算法利用曼彻斯特编码提取标签碰撞位，组合成新的标签序列号，然后阅读器选取两位序列号进行异或运算，并根据运算结果自调整搜索树的叉数搜索标签。该算法增加检测命令，可以减少空时隙的数目，仿真实验表明，自调整多叉树算法在阅读器查询次数、系统吞吐率和传输比特数上比QT算法和改进的四叉树算法都有所提升，在多标签识别中更有竞争力。

RFID；防碰撞；多叉树；自调整

引言

近年来，自动识别方法在货物销售、企业生产和材料流通领域得到了快速的普及和推广，射频识别(Radio Frequency Identification，RFID)技术是一种先进的自动识别和数据采集技术。RFID技术具有读取方便、识别速度快和安全性高等众多优点，对物联网领域的进步具有重要意义[1]。RFID系统一般有阅读器、电子标签和天线组成。在RFID系统数据通信的过程中，经常会有多个阅读器或多个标签在同一场合中，就会造成标签之间或者阅读器之间相互干扰，这种干扰被称为碰撞[2],阅读器自身解决碰撞性能强，多个阅读器之间产生的碰撞相对多个标签之间产生的碰撞要容易解决。本文讨论的是多个标签之间产生碰撞的问题，当有多个标签在同一时间响应阅读器的信号，就会导致标签的信号相互干扰，不能被阅读器成功识别，造成阅读器和标签通信失败。

目前解决标签碰撞问题主要采用时分多路法，该方法分为确定性算法和非确定性算法。ALOHA算法属于非确定性算法[3]，纯 ALOHA算法实现原理简单，但是标签获得处理时间不能掌控，如果一个标签连续发生碰撞，就会导致该标签处于一种“休眠”状态[4]。王勇等[5]采用动态自适应的方式，根据标签估计算法得到预测因子，使帧长和未识别的标签数量相等，从而提高系统吞吐率，但是每次重新计算预测因子的过程比较繁琐。文献[6]中阅读器对时隙进行扫描之后，发送给每个标签，略去空时隙和碰撞时隙，加快识别标签的速度。二进制树搜索算法属于典型的确定性算法[7]，阅读器逐位划分碰撞标签，缩小识别标签的数量，该算法识别成功率很高，但应用起来比较慢。张学军等[8]通过计算碰撞因子动态的选择搜索树的叉数，从而减少产生空时隙，提高了标签识别效率。文献[9]在QT算法的基础进行改进，动态地改变查询前缀，减少碰撞次数和传输位数。

针对目前大部分防碰撞算法识别周期过长，存在过多的空时隙的问题，本文提出一种自调整多叉树防碰撞方法，根据标签序列号异或运算结果动态地选择二叉或四叉搜索树识别标签，增加检测指令，可以减少空时隙的数量和缩减阅读器平均查询次数，从而提高了系统的效率。

1 自调整多叉树防碰撞算法

实现该算法需要能准确地定位到发生碰撞位的位置,本文选用曼彻斯特编码法，此编码法时通过半个周期的电平变化来得到的，在半个位周期时的负跳变(即电平由1变为0)表示二进制“1”，正跳变(即电平由0变为1)表示二进制“0”。当两个标签同时发送的比特位不相同时，上升沿和下降沿会相互抵消，造成电平未发生变化，会被系统当作错误处理，所以阅读器利用该错误就可以判断发生的具体位置。阅读器利用曼彻斯特编码检测标签1和标签2碰撞位的示意图如图1所示，检测出位置3和4为碰撞位。

图1 曼彻斯特编码检测冲突示意图

1.1 算法约定指令

为了便于描述算法，引入以下指令：

Request(prefix)请求指令，查询前缀prefix由多个x组成，x∈{0,1}，满足条件的标签响应阅读器的请求。

XOR(S)异或运算指令，S为进行异或运算比特的位置，阅读器发送XOR(S)命令，同一个标签的S和S+1位上的比特进行异或运算。

Push(prefix)入栈命令，将查询前缀prefix放入堆栈中。

Pop出栈命令，将查询前缀prefix从栈中取出。

Check(S)检测命令，选取标签的S和S+1位的比特分别进行异或运算。

Choose(S)选择指令，选取两个查询前缀。Verify(V)确认指令，查看值为V的位置。

Read_Data读取数据指令，读取标签内存储的信息。

Select(UID)选择指令，UID为每个标签拥有唯一的序列号，阅读器发送选择指令，序列号为SNR的标签将被选中。

Unselect(UID)取消指令，将序列号为 UID的标签舍去，让标签进入“休眠”状态。

1.2 算法设计

首先，将阅读器中的堆栈初始化为空，阅读器发送查询请求Request(111…111)，范围内标签响应请求，如果没有响应，算法运行结束，否则，标签将返回自身的序列号作为回应。阅读器根据曼彻斯特编码将碰撞位置1，其他位置0，形成查询序列号ID，并发送给标签，例如，a标签(10110101)、b标签(11010111)、c标签(10100111)、d标签(11000011)，阅读器译码结果为1XXX0XX1，得到的查询序列号ID为01110110，将查询序列号发送给标签，标签接收到ID，与自身序列号进行比对，提取出1对应位的值，组合成标签新的 UID号。如上例，阅读器发送ID(01110110)后，a、b、c和d标签分别得到新的序列号a(01110)、b(10111)、c(01011)、d(10001)。

得到新的标签后，阅读器发送异或指令 XOR(S),标签的序列号S和S+1位上的比特进行异或运算，运算结果如下：

a）如果只有0，阅读器发送Push(00)和Push(11)命令。

b）如果只有1，阅读器发送Push(01)和Push(10)命令。

c）如果即有1又有0，阅读器发送Check(S)指令。

对于 a和 b种情况，阅读器从堆栈中取出查询前缀，发送Request(prefix)，如果只有一个标签响应，说明在传输中没有发生标签碰撞，则阅读器选择该标签，读取标签内的信息之后，发送Unselect命令，让标签“睡眠”，不再响应阅读器的请求。如果发生碰撞，异或运算位S后移两位，阅读器先判断S和S+1位是否相等，如果相等，继续后移两位，如果不相等，让其继续进行异或运算，一直循环，直到堆栈为空，标签识别完成。

对于c种情况，算法增加了检测机制，因为出现既有1和0的有很多种组合，例如11、10、01的组合，00、01、11的组合，11、01的组合等等，经过异或运算得到的值既有0又有1。为了避免此种情况的发生，阅读器先发送Check(S)命令，让标签的S和S+1位上的比特分别进行异或运算。如果运算结果都为1，则将查询前缀 00、01、10、11全部压入堆栈。如果运算结果两个值不相等，则发送Choose(S)确认指令，查看Check(S)运算结果为0位上的值等于多少，

a）如果为0，发送Push(00)命令。

b）如果为1，发送Push(11)命令。发送 Verify(V)确认指令，查看 Check(S)运算得到的值为 1的位置，

a）如果在S位，发送Push(10)命令。

b）如果在S+1位，发送Push(01)命令。

例如a(01110)和c(01011)在查询前缀01节点发生了碰撞，S和 S + 1(S=2)位的数值为11和01，异或运算得到的结果既有0又有1，执行Check(S)指令之后，发现S和S+1位上的值不相等，则继续发送Choose (S)指令和Verify(V)指令，发现0位上的值为1且在S+1位上，则只将查询前缀11和10压入堆栈中，舍弃00和 01，这样可以避免多产生两个空时隙，提高了系统识别准确率。算法流程如图2所示。

图2 算法流程图

2 算法性能分析

本文从阅读器查询次数、吞吐率和通信复杂度三个方面分析算法的性能。

2.1 阅读器查询次数

阅读器查询次数的多少可以反映算法识别标签的效率的高低，对阅读器范围内的n个标签的查询过程可以用一棵二叉和四叉组合树的方式来表示，成功识别的标签对应组合树的叶子节点，发生碰撞的标签对应组合树的内部节点(除去叶子节点的其他节点)，对标签的搜索类似于对组合树的遍历过程。阅读器每次选取标签序列号的两位进行异或运算，根据运算结果选择二叉树或者四叉树搜索标签。

（a）当进行异或运算的比特位为00、01、10、11中的任意三个组合时，共有种情况；

（b）当异或运算为00、01、10、11时，此时产生0个空节点，共1种情况；

在（a）和（b）种情形下，阅读器会选择四叉树进行搜索标签，但（a）情况会产生一个空节点。

（c） 当进行异或运算的查询前缀为00和11的组合或者01和10的组合，经过阅读器的异或运算之后，选择二叉树查询；

（d）当00与10、00与01、11与01、11与10的组合，经过阅读器运算之后，会出现既有0又有1的情况，开始会选择四叉树查询，但是经过检测命令(check)检测之后，最终还是选择二叉树搜索。

所以（c）和（d）共有六种情况会选择二叉树搜索。所以选择二叉树查询的概率为6/11，选择四叉树查询的概率为5/11，设总的查询次数为N，产生四叉树的节点为n4，产生二叉树的节点为 n2，叶子节点(标签被成功识别)为 n0，空节点为 nk。则N=n4+n2+n0+nk,即得到

2.2 吞吐率

RFID系统的吞吐率为标签的数量比上阅读器发送的查询命令次数[10]，即

依照这个吞吐率的标准，自调整多叉树RFID多标签防碰撞算法吞吐率的表达式为

2.3 通信复杂度

通信复杂度是系统执行效率的另一个重要指标，是完成所有标签的识别，阅读器和标签之间传输的总比特数，用C(n)表示，n为标签的个数，阅读器在获得标签新的序列号之前，信道传输的比特数用 L1表示，阅读器获得标签新的序列号之后，信道传输的比特数用L2表示，则

为了将标签的碰撞位提取出来，组合成新的标签序列号，阅读器首先发送一个和标签序列号长度相等的查询命令，范围内的n个标签返回自身的序列号，长度为k，阅读器收到标签的序列号之后，将碰撞位置“1”，其他位置“0”，形成和标签长度k相等的查询序列号，标签接收到查询序列号，提取自身序列号和查询序列号为“1”对应的标签位，并返回给阅读器，假设新标签的长度用 knew表示，在最优的情况下knew为Integ(lbn)位(n代表标签的个数)，最差的情况和原来长度 k相等，所以形成新标签位数的区间为[Integ(lbn),k][11]，此时在信道上传输的比特长度为L1，则

提取标签碰撞位完成之后，阅读器发送异或运算指令，根据运算结果选择二叉树或者四叉树搜索，阅读器发送的查询前缀和标签返回的序列号之和等于新的标签序列号长度knew，

用Lcom表示阅读器发送的平均指令长度，由上文对阅读器查询次数的分析，传输的比特数L2为，

由公式(4)、(5)和(6)可得，

3 实验仿真与分析

实验选取自调整多叉树算法、查询树算法、一种改进的四叉树RFID防碰撞算法[12]在软件Matlab上进行仿真，标签序列号由16位二进制数组成，标签的数量n从0增加到2000，实验结果取 50次的均值。分别取标签序列号长度 k的值为Integ(lbn)、(Integ(lbn)+k)/2和k时，阅读器查询次数、吞吐率、传输的比特数和标签个数的关系图。

三种算法的阅读器查询次数随着标签数量的变化如图3所示，从图中可知，随着标签数量从 0增加到2000，三种算法的阅读器查询次数也都相应地在增多，QT算法增长的幅度尤为明显，改进的四叉树算法所需的平均搜索次数始终多于自调整多叉树算法。当图(a)中标签数量等于400时，QT算法的搜索次数约是本算法查询次数的三倍，改进的四叉树算法也比本算法多200多次查询，产生此结果的原因很可能是由于改进的四叉树RFID算法每次都是通过匹配对比矩阵中的四个比特数(00、01、10、11)，来选择搜索路径，随着标签数目的减少，产生的空时隙的数目就会增多，而本算法通过检测指令，成功避免了产生2个及以上的空时隙，提高了搜索的准确性。

图3 本算法与QT算法、改进的四叉树算法阅读器查询次数的比较

图4是自调整多叉树算法和QT算法以及改进的四叉树算法吞吐率的比较，从图中可以看出，本算法在吞吐率上明显优于其他两种算法，在图(a)中随着标签数目的增多，自调整多叉树算法吞吐率维持在0.55左右，而改进的四叉树算法在0.5左右，当标签的数量达到 1000左右时候，吞吐率下降较为明显。其中 QT算法的吞吐率最低，这很可能是由于QT算法中阅读器每次收到标签碰撞，就将查询前缀分别加上“0”和“1”，继续查询，直到没有发生碰撞，才成功识别标签。随标签的数目增多，逐位的查询，发生碰撞的概率很高，导致QT算法的吞吐率较低。

图4 本算法与FSA、改进的四叉树算法吞吐率的比较

图5是自调整多叉树算法和QT算法以及改进四叉树算法传输总比特数的比较，从图(a)中可以发现，当标签的序列号长度为Integ(lbn)时，自调整多叉树算法传输的比特数要少于另外两种算法，这是因为本算法通过曼彻斯特编码提取标签的碰撞位，组合成新的标签序列号，在识别过程中，减少传输的比特数的位数。当标签的序列号长度等于k时，传输的比特数和改进的四叉树算法相当，但在一般情况下，经过曼彻斯特编码之后，得到新的标签序列号长度要少于原标签序列号的长度，所以传输的比特数也会相应的减少。

图5 本算法与QT算法、改进的四叉树算法传输比特数的比较

通过对实验结果进行分析比较，自调整多叉树防碰撞算法在阅读器查询次数、系统吞吐率和传输的比特数上都要优于另外两种算法，在解决标签防碰撞问题更有优势。

4 结束语

本文在以多叉树搜索标签为基础，通过提取标签序列号中发生碰撞的比特位，组合成新的标签序列号，舍去多余的比特位，减少了阅读器和标签通信时传输比特的位数。执行 XOR(S)和Check(S)指令，动态的选择多叉树识别标签，减少了空时隙的数目，提高系统的识别效率。通过实验仿真和性能分析，该算法在系统吞吐率、阅读器比较次数和传输比特数上更有优势。在后续的研究中，可以根据标签序列号的特征进行动态地分组，降低发生标签碰撞的概率，使系统性能更加优越。

[1]苏忠根. 射频识别天线蚀刻技术工艺流程及其精益化管理研究[J].科技管理研究,2014,34(1)： 218-223.

[2]康东. 射频识别 (RFID) 核心技术与典型应用开发案例[M]. 人民邮电出版社,2008.

[3]邢志鹏,杨恒新,张昀. 分段式位隙分组帧时隙Aloha算法[J]. 计算机技术与发展,2016,26(4)： 31-35.

[4]Hwang T W,Lee B G,Kim Y S,et al. Improved Anti-collision Scheme for High Speed Identification in RFID System[C]// International Conference on Innovative Computing,Information and Control. IEEE Computer Society,2006： 449-452.

[5]王勇,李婷. 改进的基于ALOHA的RFID防碰撞算法[J]. 电信科学,2016,32(8)： 77-81.

[6]张小红,胡应梦. 分组自适应分配时隙的 RFID防碰撞算法研究[J].电子学报,2016,44(6)： 1328-1335.

[7]Park J,Min Y C,Lee T J. Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection[J].Communications Letters IEEE,2007,11(5)： 452-454.

[8]张学军,蔡文琦,王锁萍. 改进型自适应多叉树防碰撞算法研究[J].电子学报,2012,40(1)： 193-198.

[9]肖菲,杨恒新,刘蕾蕾. 一种改进的二进制查询树RFID标签防碰撞算法[J]. 计算机技术与发展,2014(6)： 92-94.

[10]吴楠. 一种树型结构的RFID防碰撞算法研究[D]. 吉林大学,2014.

[11]Cover T M,Thomas J A. Elements of information theory (2. ed.)[M]//Elements of information theory /. Wiley,2006： 1600-1601.

[12]孙耀磊,吴晓波,陈元文,等. 一种改进的四叉树 RFID 防碰撞算法[J]. 计算机工程与应用,2014,50(4)： 63-68.

Anti-Collision Algorithm based on Self-adjusting Multi-tree For RFID Multi-Tag

ZHANG Na,WANG Zhiyong*
(School of Information Science and Technology,Zhejiang Sci-Tech University,Hangzhou 310018,China)

With the expansion of RFID technology applications,effectively solve the multi-label collision problem is to improve the performance of RFID system key. Based on the analysis of anti - collision algorithm of tree search,a self - adjusting multi - tree anti - collision algorithm is proposed. The algorithm uses the Manchester code to extract the label collision bits,and then combines the new tag serial number,and then the reader selects the two-bit serial number to XOR and transfers the data according to the result of the operation. By increasing the detection command,the system can achieve the effect of reducing the number of empty slots. The simulation results show that the self -adjusting multi - tree algorithm has improved the number of times of reader query,system throughput and transmission bits than QT algorithm and improved quadtree algorithm,and it is more competitive in multi - tag recognition.

RFID; collision; multi-tree; self-adjusting

TN92

A

1672-9129(2017)06-0004-04

10.19551/j.cnki.issn1672-9129.2017.06.002

张娜,王志勇. 一种自调整多叉树RFID多标签防碰撞算法[J]. 数码设计,2017,6(6)： 4-7.

Cite：ZHANG Na,WANG Zhiyong. Anti-Collision Algorithm based on Self-adjusting Multi-tree For RFID Multi-Tag[J]. Peak Data Science,2017,6(6)： 4-7.

2017-02-11；

2017-03-06。

浙江省重大科技专项重点工业项目： 面向公共安全的智能监控平台关键技术研究与示范(2014C01047)；国家自然科学基金（61502430）；浙江理工大学“521人才培养计划”。

张娜(1977—)，女，浙江杭州人，副教授，硕士，主要从事自适应软件、软件测试与智能信息处理方面的研究。王志勇(1992—)，男，安徽池州人，硕士研究生，研究的方向为物联网技术。

E-mail:wzystxk@163.com