基于QT算法的RFID跨层查询反碰撞改进算法

孔凡凤，龙林德，朱永平

(湖南邮电职业技术学院移动通信系, 湖南 长沙410015)

基于QT算法的RFID跨层查询反碰撞改进算法

孔凡凤，龙林德，朱永平

(湖南邮电职业技术学院移动通信系, 湖南 长沙410015)

现有RFID系统的QT算法在电子标签数量和密度增加及EPC较长时会造成查询次数过多、碰撞次数增加、系统效率低等问题.针对QT算法的缺点，提出了改进型的跨层查询算法，包括SQT算法和MQSQT算法.SQT算法通过改进QT算法将查询电子标签位元串方式改为跨层查询方式，MQSQT算法通过询问EPC字串的下2个位元值并进行异或逻辑运算，以求出包含跨层查询所必需的字串最小集合.仿真结果表明改进型算法减少了碰撞次数，平均查询次数有较大改善，提高了RFID系统的效率.

RFID; 电子标签; 反碰撞; QT

RFID即射频识别，是一种非接触式的无线通信识别技术，通过射频信号来自动识别特定目标并读取其相关信息，具有防水、防磁、耐高温、使用寿命长、读取距离大、非可视穿透、电子标签上数据可加密[1]、存储数据容量大、存储信息方便等优点.因此，近年来RFID系统被广泛应用于门禁系统、物流仓储、交通运输等方面[2].

RFID系统由阅读器、电子标签和天线组成.每个电子标签都有一个唯一的电子产品代码EPC，阅读器通过射频信号来识别电子标签的EPC及标签中其他各种有用信息.RFID系统常用的工作频率包含低频的135KHz、高频的13.56MHz及超高频的433MHz、860MHz～930MHz、2.45GHz.

通常，RFID系统阅读器在一个时间内只能跟一个电子标签通信.因此，RFID在识别电子标签时可能发生各种碰撞[3]，如电子标签-电子标签[4]的碰撞、电子标签-阅读器的碰撞、阅读器-阅读器的碰撞.针对电子标签-电子标签碰撞，通常的反碰撞算法有AHOHA算法、Binary Tree算法、Query Tree查询树算法(简称QT算法)等.

1 QT 算法

QT算法是按照队列先进先出的询问方式进行的.其基本原理是：阅读器广播一个查询字串前缀，与查询字串前缀匹配的标签响应阅读器.如果发生碰撞，则在此查询字串前缀后面分别加上一个0或者1，从而生成新的查询字串前缀，阅读器以此再进行查询，依次下去[5].

如图1所示，共有6个RFID电子标签，其EPC分别为：000、001、100、101、110、111，阅读器首先广播查询字串前缀0，由于与查询字串前缀0相符的电子标签EPC有000、001两个，因而阅读器发生了000、001两个电子标签的碰撞.此时在查询字串前缀0后面分别加上一个0和1，生成00和01两个新的查询字串前缀，并加入查询字串前缀队列1后面.阅读器再次广播查询字串前缀1，由于与查询字串前缀1相符的电子标签EPC有100、101、110、111四个，因而阅读器发生了100、101、110、111四个电子标签的碰撞.于是在查询字串前缀1后面分别加上一个0和1，生成10和11两个新的查询字串前缀，并加入查询字串前缀队列11的后面.阅读器再广播查询字串前缀00，又发生000、001两个电子标签的碰撞，此时又在查询字串前缀00后面分别加上一个0和1，生成000和001两个新的查询字串前缀，并分别加入查询字串前缀队列11后面，阅读器再次广播查询字串前缀000，依此下去[6].

图1 QT算法询问方式

表1为此例的查询步骤及状态，由表1可看出图1的电子标签查询步骤数量、电子标签空闲数量和电子标签碰撞数量.

表1 QT算法运作流程

2 跨层查询SQT算法

由于传统QT算法仅在电子标签数量少、电子标签密度较小及EPC长度较短的情况下使用才能发挥较佳效率.随着电子标签数量、密度及EPC长度增加，将造成查询次数和碰撞次数增多，从而使得系统的效率降低[7].为此，这里提出了一种改进的跳跃式查询算法，即跨层查询SQT算法.该算法以QT算法为基础，改进传统QT算法原有的逐层查询方式为跨层查询方式，以避免过多的碰撞数量.SQT算法的步骤如下：

第一步：阅读器选择查询字串前缀信息，向读取范围内的电子标签发出识别请求信息，并等待电子标签的响应.

第二步：判断电子标签响应状态，如果电子标签响应发生碰撞，则跳至第三步；如果只有一个电子标签响应，则代表该电子标签成功识别，则跳至第四步；反之，如没有电子标签响应，则表示为空闲状态，则跳至第五步.

第三步：将目前的查询字串前缀分别与00、01、10、11合并组成新的查询字串前缀，加入查询字串前缀队列中，并跳回第一步，阅读器继续进行识别动作，直至所有电子标签辨识完成.

第四步：成功辨识，则进行电子标签信息的的读取，成功辨识的电子标签暂时进入睡眠状态，不进入下次竞争队列，信息读取完后则跳回第一步，直到电子标签全被辨识完毕为止.

第五步：结束电子标签的识别读取.

仍然以图1为例，阅读器首先广播查询字串前缀0，由于电子标签000、001同时满足查询条件，发生了两个电子标签的碰撞，于是阅读器将下面跨层的四个查询字串前缀000、001、010、011依次加入到查询字串队列1后面；同样的，当阅读器广播查询字串前缀1时，由于电子标签100、101、110、111同时满足新的查询条件，发生了新的四个电子标签的碰撞，于是阅读器将下面跨层的四个查询字串前缀100、101、110、111依次加入到查询字串队列011的后面.

下表2为图1为例的SQT算法查询步骤及状态，由表2可看出图1的电子标签SQT算法查询步骤数量、电子标签空闲数量和电子标签碰撞数量.

表2 SQT算法运作流程

对比表2和表1可知，SQT算法在碰撞次数和询问次数上都比QT算法要少，但空闲数量增加了，会影响到RFID系统整体的运行效率.因此，下面将介绍一种相对于QT算法，既能减少碰撞次数和询问次数，也能降低空闲数量的MQSQT防碰撞算法.

3 最小查询字串集跨层MQSQT算法

MQSQT算法即利用或逻辑运算来协助过滤掉重复的查询字串，并计算出查询位元串信息的最小集，将求得的最小查询字串集存入到查询队列里，以提升运作效率.

MQSQT算法步骤如下：

第一步：阅读器获取当前查询队列中字串信息，并发出查询请求信息给读取范围内参与竞争的电子标签，然后等待电子标签的回应.

首先阅读器会取出队列中的第一笔查询信息并发出查询信息，然后等待电子标签的回应信息.

第二步：判断电子标签回应状态.如果信息发生碰撞，则跳至第三步，若只有一个电子标签回应即为成功识别，则跳至第五步；反之，若非以上两个状态即为空闲状态，则跳至第六步.

依电子标签的回应状态，可将阅读器的识别状态分为：空闲、成功识别和碰撞三种状态.若在有效时限内没有收到电子标签的回应信息，表示无任何电子标签需要传输信息，则为空闲状态，阅读器将空闲次数Idle值加1(参数Idle用以记录系统的空闲次数，数值类型为整数，其起始值为0)；若仅收到一个电子标签的回应信息即为成功识别电子标签，阅读器可顺利读取电子标签中的信息并读完信息后让此电子标签进入睡眠状态.

第三步：阅读器将发生碰撞的电子标签当前查询位置之后的两个EPC位元记录于阵列LO(参数LO用以记录欲进行逻辑运算的EPC信息字串,数值类型为字串，其起始值为空字串)中，并进行XOR逻辑运算，如图2所示.

图2 记录回应电子标签目前询问位置下的两个EPC位元

若阅读器同时收到多个电子标签的回应信息，即表示电子标签发生碰撞无法成功识别，此时，读取器会将碰撞次数Col值加1(参数Col用以记录系统的碰撞次数，数值类型为整数，其起始值为0).同时，阅读器将会记录所有回应碰撞电子标签此次查询位置之后的两个EPC位元，然后将所记录EPC位元进行XOR逻辑运算以求出此次可能新增位串的最小集合，其做法是阅读器会取出先前所记录的电子标签后两位元进行XOR运算.

第四步：合并目前查询字串及逻辑运算后之结果，产生新查询字串并将结果存入查询队列中，并跳回第一步，阅读器将会持续进行识别动作，直到电子标签被识别完毕为止.

经过XOR逻辑运算后得到无重复的字串信息，最后再将当前的查询字串信息与XOR逻辑运算后的结果合并存入查询字串信息队列中.整个系统会反复执行上述步骤，直到所有电子标签均被成功识别完成为止.

第五步：成功识别，进行电子标签信息的读取，成功识别的电子标签进入睡眠状态，不进入下一次的竞争，信息读取完毕后则跳回第一步，直到电子标签全被识别完毕为止.

第六步：结束.

以图3为例说明MQSQT算法与SQT算法的比较：假设阅读器一开始发出查询字串为0时，因电子标签1、2、3、4的第一位元值均为“0”，所以此四个电子标签均会回应信息给阅读器，在SQT算法里此时阅读器会分别将“000”、“001”、“010”及“011”四笔字串分别存入查询队列中；若采用MQSQT算法，则只需将“000”和“001”两笔字串加入查询队列中，其余两笔为重复多余的查询字串则会被摈弃，所以MQSQT算法的空闲次数会较SQT算法少.在MQSQT算法中，当阅读器收到电子标签回复后，会记录所有回应电子标签此次询问位置之后两个EPC位元值，分别为“00”、“01”、“00”与“01”；然后阅读器对“00”、“01”的第一个位元与第二个位元分别进行XOR运算，算出“00”、“01”第一个位元XOR运算后的结果为“0”，第二个位元XOR运算后的结果为“1”，由此可知此四个电子标签用于XOR运算的两位元中的第一位元值必完全相同，而第二位元必有不同的值，即必含有“0”与“1”.因此，可取出第一位元的值“0” 分别与第二位元必有的“0”及“1”组合出所有可能的位元串“00”与“01”，最后，再将目前的查询位元“0”分别与逻辑运算得出的结果“00”与“01”合并后，即可分别组合出两个新的查询字串“000” 和“001”，将之存入队列中以供下次查询之用.

图3 逻辑运算运作流程

表3 MQSQT算法运作流程

查询步骤阅读器广播的查询字串前缀响应电子标签电子标签状态第一步0标签1、标签2标签3、标签4碰撞第二步1标签5、标签6碰撞第三步000标签1、标签3碰撞第四步001标签2、标签4碰撞第五步101标签5识别第六步111标签6识别第七步0000标签1识别第八步0001标签3识别第九步0010标签4识别第十步0011标签2识别

表3为MQSQT算法的运作流程.由表3可看出经过XOR逻辑运算后，并没有产生任何的空闲状态.因此，通过MQSQT算法可降低采用SQT算法查询过程中所产生的空闲次数过多的问题.

4 仿真参数设置

各种模拟参数设置如表4所示，且假设在模拟仿真环境中无任何干扰，电子标签数量范围为50～500个，每次增加50个，EPC的长度为15bits，所有模拟数据为对每种电子标签数量进行100次模拟所得数据的平均值.

表4 模拟参数设置表

5 模拟结果分析

QT算法与SQT算法其运作的差别在于每次查询位元串所新增加的bit数，前者以每次增加1个bit的方式组成新的查询位元串，而后者以每次增加2bits的方式，仿真结果如图4所示.从图5可知采用QT算法的碰撞次数远多于采用SQT算法时，而MQSQT算法则是在SQT算法上增加了逻辑运算，其查询的方式与SQT算法相同，因此，在碰撞次数上与采用SQT算法差不多.

图4 电子标签数量与碰撞次数的关系图

图5为三种算法的空闲数量的比较图，图中显示SQT算法比QT算法在空闲数量部分有较差的性能且差异非常大，这是因为QT算法是以每次增加1bit方式来得到新的查询字串，而SQT算法则是以每次增加2bits的方式来得到新的查询字串.因此，采用QT算法会比采用SQT算法较早且较上层就发现空闲状况，整体的空闲数量也相对较低，而MQSQT算法由于部分修改了增加查询字串信息的限制，利用逻辑XOR运算求出最符合的2bit查询字串信息，改善了采用SQT算法时空闲次数过多的问题.由图6可清楚看出MQSQT算法所表现出的性能有较明显的改善.

图5 电子标签数量与空闲次数的关系图

因此，QT算法虽然在碰撞次数上多于SQT算法，但在空闲次数上要少于SQT算法.MQSQT算法不仅解决了QT算法碰撞次数过多的问题，同时也解决了SQT算法空闲状态过多的问题.图6中，比较了三种算法所执行的总查询次数，即成功识别次数、碰撞次数、空闲次数的总和.

图6 电子标签数量与总查询次数的关系图

从图6可看出，QT算法与SQT算法因为各有碰撞次数或空闲次数的优缺点，所以在整体的查询总次数上并没有太大的差异，而MQSQT算法则是因改善了SQT算法的缺点并保留了其优点，所以在总查询次数上有明显的改善.MQSQT算法提升了系统的整体性能.

6 总结

RFID系统中的标签碰撞与空闲的问题关系到系统的效率，文章针对两个问题所提出的SQT算法和MQSQT算法都是以QT算法为基础改进而来.SQT算法改进了QT算法，增加查询位元串的方式为跨层方式，降低了标签碰撞次数.但带来了空闲次数过多的弊端.针对SQT算法问题而改进的MQSQT算法，利用符合EPC当前查询字串后2个位元值进行逻辑运算，以求出包含下一层必需查询节点的所有可能的字串最小集合，达到了降低空闲次数的目的.由电脑模拟仿真结果显示，SQT与MQSQT算法在避免碰撞的能力上均比QT算法有更好的结果，在空闲模拟的部分，MQSQT算法显示有很好的效果，在整体性能上有明显的改善.

[1] Kim J, Lee W, Yu J, et al. Effect of localized optimal clustering for reader anti-collision in RFID networks: Fairness aspects to the readers[A]. Proceedings of 14th International Conference on Computer Communications and Networks[C]. 2005:497-502.

[2] Li B, Jing Z, Luo Y. A RFID anti-collision searching algorithm based on regressive style binary system[J].Computer Applications and Software, 2009, (12):96-98.

[3] Yang Z, Chen J, Mao Z. Study on the performance of tag-tag collision avoidance algorithms in RFID system[A].Proceedings of Third Asia International Conference on Modeling & Simulation.2012:757-760.

[4] Yeh M, Jiang J, Huang S. Adaptive splitting and pre-signing for RFID tag anti-collision[J].Computer Communications, 2009, (1):1862-1870

[5] Myung J, Lee W, Srivastava J. Adaptive binary splitting for efficient RFID tag anti-collision[J]. IEEE Communications Letter, 2006, (3):144-146.

[6] 高金辉, 郑晓彦.新型混合防碰撞算法[J].电子技术应用, 2011, (12):130-136.

[7] 王中祥, 王俊宇，刘丹，等.一种降低空时隙开销的防碰撞算法[J].通信学报, 2009, (9):1-6.

(责任编校：晴川)

RFID Anti-collision Algorithm of Cross Layer Query Based on QT

KONG Fanfeng, LONG Linde, ZHU Yongping

(Department of Mobile Communication, Hunan Post and Telecommunication College, Changsha Hunan 410115, China)

QT algorithm of current RFID system could result in increased query numbers, high collision frequency and low efficiency of the system when the number and density of EPC electronic label increase. In allusion to these shortcomings, this paper proposed a cross layer algorithm, including the SQT algorithm and MQSQT algorithm. SQT algorithm became cross layer query mode through improving the bit string mode of QT algorithm querying for electronic tag, and MQSQT algorithm conducted XOR logic operation based on 2 bits of EPC string of current query, so as to find the minimal set of query string needed for the cross layer search. The simulation results showed that the improved algorithm reduced the number of collisions, average numbers of queries had been greatly improved, and it improved the efficiency of RFID system.

RFID; electronic tag; anti-collision; QT

2015-04-29

湖南省教育厅科学研究项目(批准号：12C0963).

孔凡凤(1979— )，女，山东莱芜人，湖南邮电职业技术学院移动通信系讲师，硕士．研究方向：无线传感网络.

TP393

A

1008-4681(2015)05-0042-05