双时隙二进制树堆栈式RFID防碰撞算法

魏绍蓉， 王晓英， 刘志强， 贾续涵

(青海大学 计算机技术与应用系，青海 西宁 810016)



双时隙二进制树堆栈式RFID防碰撞算法

魏绍蓉， 王晓英， 刘志强， 贾续涵

(青海大学 计算机技术与应用系，青海 西宁 810016)

随着射频识别系统的广泛应用，标签数量不断增加,导致了系统通信性能下降。文章通过分析和比较查询树算法(QT)、二进制树算法(BT)的优缺点，提出一种双时隙二进制树堆栈式标签防碰撞算法。该算法利用曼彻斯特编码的特性来确定标签识别过程中的ID碰撞位置，并且利用堆栈形成进一步搜索命令，逐一识别标签。通过仿真比较几个相关的算法，结果表明，双时隙二进制树堆栈式标签防碰撞算法在减少数据传输量、减少识别标签所需响应比特数及时隙数上明显优于现有QT和BT算法。

RFID; 多标签; 防碰撞; 堆栈

0 引 言

射频识别技术(Radio Frequency Identification, RFID)[1]利用无线电波来传输阅读器(reader)和标签(tag)之间的信息，该项技术已经在身份识别、生产制造、军队事务、医药、交通以及动物跟踪等许多领域应用。RFID技术被认为是21世纪的十大重要技术之一，让人类的日常生活最终实现U(Ubiquitous)化,即信息无所不在。RFID系统是由读写器、标签、中间件及信息系统四者构成。然而在实际应用中，会出现一个读写器同时收到多个标签发出的信息，而此时将会发生标签的信号碰撞(Collision)，导致阅读器无法准确读写标签[2]。针对标签碰撞问题，目前有3类较成熟的标签防碰撞算法：帧时隙 ALOHA 算法(Framed Slotted Aloha, FSA)、基于树的算法和综合算法[3-5]。目前，ISO/IEC、EPCglobal等国际组织制定的国际标准主要采用查询树算法(Query Tree Algorithm，QT)、二进制树算法(Binary Tree Algorithm，BT)、二进制搜索算法(BS)等树型算法，以及时隙类ALOHA算法进行多标签识别防碰撞处理[6]。这些算法的识别效率只能达到34%～36.8%左右，且识别性能不稳定，不能满足RFID多标签识别应用系统的实际需要。通过分析比较目前典型的标签防碰撞算法，研究并实现一种基于二进制树的双时隙堆栈式 RFID 标签防碰撞算法。该算法目的是减少识别延时并改进二进制树算法。通过仿真测试，算法比目前使用的基于时隙和二进制树的防碰撞算法具有更少的响应比特数和时隙，有效地提高RFID系统的通信性能[7-9]。

1 典型标签防碰撞算法研究

1.1 BT算法

BT算法是基于树的标签防碰撞算法[10-11]，通过标签的唯一身份(ID)对标签进行识别，标签有3个状态：活动、静默和休眠。标签被识别，则标签进入休眠状态直到识别过程结束。每个标签使用指针定位其 ID 中当前被查询的比特。阅读器每次只发送一个比特的查询，当指针指向的比特与查询信息相等，活动标签就发送下一个比特，然后将指针指向该比特，否则，标签保持静默，直到有一个标签被识别。如果在标签响应时发生碰撞，阅读器首先询问“0”，如果阅读器收到的是某个特定的二进制比特，它将用这个比特作为下一次查询。标签被识别后，转入休眠状态，而未被识别的标签被激活，指针重新指向最高位。

1.2 QT算法

QT[12]算法标签不记录当前状态或查询的比特位置。标签收到阅读器的查询后，比较其ID前缀与查询信息，相等则标签把ID传输给阅读器。当多个标签响应阅读器时，阅读器就会知道至少有两个相同前缀标签，因此，阅读器会在之前的查询信息后面加上0或1，并用这2个新的前缀分别对标签进行查询。直到查询信息和某个标签的ID唯一匹配，这个标签就可以被识别。因此，QT算法是通过扩充查询信息的前缀，直到只有和一个标签的ID匹配，才识别该标签。QT算法是无记忆的基于树的RFID防碰撞算法。QT算法的改进算法，双时隙查询树算法(Bi-Slotted Query Tree Algorithm，BSQTA)。BSQTA算法通过在每次阅读器的查询信息之后引入双时隙来改进QT 算法，BSQTA 在每识别一个标签所需的迭代次数和平均所需比特数方面的表现优于QT 算法[13]。

1.3 BT算法及QT算法分析与比较

BT算法，当一个标签被识别后，阅读器重新从最高比特开始对其他标签进行查询，因为阅读器在新的查询中并没有利用之前查询中获取的碰撞位置或其他可能的前缀等信息，所以增加了识别过程的时延。 QT算法，标签是无记忆的，所以阅读器和标签在识别的过程中都必须传输更多的比特，导致了大量时延。鉴于分析比较BT与QT算法所存在的问题，结合两者优势，提出双时隙二进制树堆栈式防碰撞(Bi-Slotted Binary Tree Algorithm，BSBTA)算法。该算法利用曼彻斯特编码的特性来确定标签识别过程中的ID碰撞位置，并且利用堆栈记录碰撞的前缀，形成进一步搜索命令，阅读器就可以利用之前所获取的信息进行查询，并在一个标签被识别之后，从最近一次发生碰撞的位置对其他标签进行查询。同时也引入双时隙来减少标签需要发送的比特数。

2 BSBTA设计与实现

2.1 BSBTA 采用曼彻斯特编码

曼彻斯特编码通过上升或下降的变化来描述逻辑 0或逻辑 1[14]，如果多个标签同时传输不同的二进制序列，那么 0或1的覆盖在编码中将始终保持上升或下降的变化，如果发生碰撞，那么就没有上升或下降的变化，因此阅读器无法识别。

图1 曼彻斯特编码碰撞例子

2.2 BSBTA算法总体描述

假设标签的ID是一个m比特的字符串，记为t0,t1,…,tm-1，其中ti∈{0,1}(i=0,1,…,m-1)。定义一个堆栈stack，stack的初始值为{00,01, 10, 11}代表所有标签的最高两位，阅读器通过堆栈stack记录碰撞的前缀，阅读器利用变量p跟踪被查询的标签。

其流程如图2所示，具体步骤如下：

(1) 初始化堆栈。stack = {00, 01, 10, 11}。初始化阶段每个标签的指针P都指向标签的最高位，记为第0比特，P=0。

(2) 阅读器发送查询。prefix =POP(stack)。假设 prefix=a0,a1,…,an-2,an-1，其中prefix的长度是n，n是标签的ID长度m减2，其中ai∈{0,1} (i= 0, 1, …,n-1)。定义Q=an-2an-1，p=n-3。传输Q||p，为标签响应预留两个时隙。

(3) 第一个时隙

① 没有响应，不做任何事情。

② 收到某个比特b0：

如果p==m-4，则当前接收到的是标签ID中的最后一位，因此，阅读器能够识别这个标签，其ID为prefix||0b0，b0前面的“0”表示是第一个时隙。

如果p

③ 碰撞：

如果p==m-4，则当前碰撞是由标签ID的最后一位引起的，因为使用的是曼彻斯特编码，碰撞表明最后一位为“0”和“1”的标签都存在，所以阅读器同时识别两个标签，其ID分别为prefix||00和prefix||01，prefix后面的“0”表示这是第一个时隙。

如果p

图2 BSBTA算法流程图

(4) 第二个时隙

① 没有响应，不做任何事情。

② 收到了某个比特b1(0 或 1)：

如果p==m-4，表明当前接收到的是标签ID中的最后一位，因此，阅读器能够识别这个标签，其ID为prefix||1b1，b1前面的“1”表示这是第二个时隙。

如果p

③ 碰撞：

如果p==m-4，表明当前碰撞是由标签ID的最后一位引起的，由于这里使用的是曼彻斯特编码，碰撞表明最后一位为“0”和最后一位为“1”的标签都存在，所以，阅读器同时识别两个标签，其ID分别为prefix||10和prefix||11，prefix后面的“1”表示这是第二个时隙。

如果p

(5) 算法结束判断

① 如果stack非空，回到2)。

② 如果stack为空，识别过程结束。

每个标签使用一个二进制变量P来记录标签ID中被查询的比特的位置。P的初始值为0，表示标签未被阅读器查询，只有当标签将它ID中的比特发送给阅读器之后，P才会向低一位比特移动。

3 系统仿真及性能评估

3.1 识别一个标签的平均响应比特数

系统吞吐率是衡量系统性能的重要指标，在Matlab平台下，通过计算机仿真比较 BSBTA 、 BT[15]和QT[16]算法的性能。仿真程序由 Java 语言编写，假设在查询范围内只有一个阅读器，标签的数量从 5 个递增到800 个，标签 ID 的长度为 96 比特，且 ID 值呈一致分布。图3描述了每识别一个标签的平均响应比特数。在 BT 算法中每个标签在被识别之前需发送 除了最高比特之外，标签需要传输所有 ID，95 比特。因为BSBTA算法使用双时隙，所以每个双时隙都表示一个比特，这样至少节约了两个响应比特，BSBTA算法中的响应比特数约为 BT 的一半。因为QT算法是无记忆的，每个标签都需要用剩余的所有比特响应阅读器，QT算法则需要更多的比特来识别标签，而不像 BSBTA 算法，每次只要响应 1 比特，BSBTA 中的响应比特数只约为QT 的1/4左右。

图3 标签的平均响应比特数

3.2 识别一个标签的平均时隙数

一个时隙表示一次对话，包括阅读器的查询和标签的响应。图4描述了每识别一个标签的平均时隙数。 QT需要很少的时隙识别标签，但是算法的无记忆性使得每个时隙中必须完整地传输至少 96 比特，所以每个时隙时间段都很长。BT 和 BSBTA每个时隙只传输几个比特，所以每个时隙的时长相对短。 BSBTA是双时隙，每次查询之后会有两个时隙，缺点是如果在没有标签与该时隙匹配时，双时隙会导致空余时隙，但是BSBTA的时隙仍然比 BT 要少。最主要的原因是BSBTA 中，阅读器利用堆栈记录了碰撞位置，所以，当一个标签被识别之后，下一次查询将直接从碰撞位置开始，而在 BT 中需要从头开始查询。

图4 识别一个标签的平均时隙数

4 结 语

本文通过分析典型的BT及QT标签防碰撞算法，提出利用曼彻斯特编码的特性来确定标签识别过程中的ID碰撞位置，利用堆栈记录碰撞前缀的BSBTA算法。该算法利用堆栈，改进了BT算法中阅读器在新的查询中没有利用之前查询获取的碰撞位置或其他可能的前缀等信息的缺陷；同时也改进了QT算法中标签的无记忆性，阅读器和标签在识别的过程中都必须传输更多的比特、导致大量时延的缺陷。仿真实验证明 BSBTA 在识别标签时所需的响应比特数和时隙数少于 BT和QT算法，由此提高了标签的识别速度，有效地改善了RFID系统的通信性能。

[1] 徐 燕. 基于RFID物联网的研究[J].微型电脑应用,2011,27(5):47-48.

[2] 夏 宏,吴济文.超高频RFID读写器系统的设计与实现[J].计算机应用，2012,32(8): 2369-2373.

[3] 王春华.改进的RFID标签防冲突算法[J].计算机工程与应用,2011，47(31):104-107.

[4] 孙文胜,金陈敏.新型的RFID动态帧时隙ALOHA防碰撞算法[J].信息与控制,2012,41(2)：233-237.

[5] Eom J ,Lee T. Accurate tag estimation for dynamic framed-slotted ALOHA in RFID system[J]．IEEE Communications Letters，2010,14 (1) : 60-62．

[6] 史长琼,肖瑞强,吴 丹.改进的动态帧时隙ALOHA防碰撞算法[J].计算机工程与设计,2014,35(6):1897-1901.

[7] 刘 青,杜 江.RFID 防碰撞算法中ALOHA算法的研究[J].科技信息，2012，18: 112．

[8] 王云峰,张 斌.基于扩频ALOHA的RFID防碰撞算法[J]. Computer Engineering and Design, 2014，40(3):2-5.

[9] 魏 静,冯秀芳.基于自适应分组的帧时隙ALOHA算法在RF1D中的研究[J].计算机技术与发展,2012,22(11): 57-60.

[10] 王晓梅,张英梅.基于Q值的RFID防碰撞改进算法的研究[J].太原理工大学学报,2014,45(3):339-342.

[11] 石封茶,崔 琛,余 剑.基于标签运动的一种新型RFID防碰撞算法[J].计算机科学,2013,40(6):76-79.

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

[13] Choi J H, Lee D, Lee H. Query tree-based reservation for efficient RFID tag anti-collision[J]. IEEE Communications Letters, 2007, 11(1), 85-87.

[14] Jia X, Feng Q, Ma C. An efficient anti-collision protocol for RFID tag identification [J]. IEEE Communications Letters, 2010, 14(11): 1014-1016.

[15] Zhu L., Yum T. S. P. The optimal reading strategy for EPC gen-2 RFID anti-collision systems [J]. IEEE Transactions on Communications, 2010, 58(9): 2725-2733.

[16] Law C., Lee K., Siu K. Y. Efficient memory less protocol for tag identification (extended abstract) [C]//In Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2000: 75-84.

RFID Anti-collision Algorithm Based on Bi-slotted Binary Tree Stackable

WEIShao-rong,WANGXiao-ying,LIUZhi-qiang,JIAXu-han

(Department of Computer Technology and Application, Qinghai University, Xining 810016, China)

With the extensive application of radio frequency identification systems, increasing the number of tags can cause system performance degradation of communication. By analyzing and comparing the query tree algorithm (QT) and binary tree algorithm (BT), this paper proposes a RFID anti-collision algorithm based on stackable bi-slotted binary tree. The algorithm uses features of Manchester code to determine the collision position of an identification tag. Furthermore, the algorithm uses the stack to form a further search order to identify each tag. The simulation results compare the performance of several related anti-collision algorithms. It is shown that anti-collision algorithm based on stackable bi-slotted binary tree can effectively reduce the amount of data transmitted, reduce the average number of responded bits and timeslots for the tag identification. So it outperforms the QT and BT algorithm.

RFID; multi-tag; anti-collision; stack

2015-03-22

国家自然科学基金项目(61363019); Google人才引进励教金科研培育项目(2014)

魏绍蓉(1973-)，女，甘肃兰州人，硕士，副教授，研究方向为RFID技术与应用，Tel．：13897410098；E-mail: wsr8808@163.com

TP 391

A

1006-7167(2015)11-0082-04