基于分组机制的位仲裁查询树防碰撞算法

付钰，钱志鸿，程超，刘晓慧



基于分组机制的位仲裁查询树防碰撞算法

付钰1，钱志鸿1，程超2，刘晓慧1

（1. 吉林大学通信工程学院，吉林长春 130012；2. 长春工业大学计算机科学与工程学院，吉林长春 130012）

提出了一种基于分组机制的位仲裁查询树(GBAQT, bit arbitration query tree based on grouping mechanism)算法。该算法根据标签ID自身特征分组，采用3位仲裁位来取代传统1位仲裁识别标签的方式，通过碰撞位信息得到传输数据，从而能避免一些空闲时隙。算法的性能分析和仿真结果表明，GBAQT防碰撞算法具有较少的总时隙数，系统效率和时隙利用率也明显优于其他算法。

RFID；标签防碰撞；查询树；分组机制

1 引言

物联网已经成为当下最具潜力的产业之一，其概念最初是在1999年被提出，通过射频识别技术和传感器等信息传感设备，把任何物品与互联网连接起来，实现监控、定位功能的智能化网络。现如今，尽管“物联网”的概念得到了进一步的完善，但RFID技术作为物联网的感知层，在物联网的核心技术中仍起着至关重要的作用。RFID是一种非接触式自动识别技术，利用空间的射频信号实现双向数据的无线通信。在《中国物联网RFID2013年度报告》中显示，2013年中国物联网市场规模达到4896亿元，RFID市场规模达到318.4亿元，比上一年增长了34.6%。RFID技术的应用领域更加广泛，如军事、航空、医疗、制造业和零售业等[1]。通常，RFID系统主要由阅读器、电子标签以及后台服务器构成[2]。阅读器主要负责控制和标签的双向通信；每个电子标签都具有能被识别的、全球唯一的电子编码；后台服务器是提供服务和管理的控制中心。

由于标签本身无法知道其他标签的存在，各标签只能按照阅读器的命令发送信息。单个阅读器只有一个通信信道，当2个或更多的标签同时向阅读器发送它们的ID信息时，就会产生信号干扰，即发生标签碰撞问题，碰撞问题会严重地影响标签数据的完整性，使标签无法被正确识别。标签碰撞问题是RFID系统中重要的难题之一，极大地制约了RFID技术的发展。

目前，有很多优秀的协议来解决标签碰撞问题，这些算法主要分为2大类：一类是基于ALOHA的不确定性算法[3~5]；另一类是基于树的确定性算法[6,7]。前者包括纯ALOHA算法[8]、时隙ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法及其改进算法等。后者包括了二进制搜索树算法、查询树（QT, query tree）算法[9]、碰撞树算法[10]等多种基于图的树型算法。

1.1 曼彻斯特编码

基于树的算法中常常使用曼彻斯特编码作为检测碰撞位的方法[11~13]。曼彻斯特编码将数据包含在数据流中，每位编码有一跳变，用下降沿表示比特“1”，上升沿表示比特“0”。在RFID系统中，如果有多个标签同时传输不同比特，那么上升沿和下降沿将被抵消。然而在数据传输过程中曼彻斯特编码不允许出现这种情况，因此使用曼彻斯特编码能判断该位为碰撞位。本文亦采用曼彻斯特编码，已达到阅读器能在接收数据中准确检测出碰撞位的目的。例如，假设系统中存在2个标签，分别为Tag A(0101)和Tag B(0011)。当Tag A和Tag B同时传送ID的数据信息时，阅读器通过曼彻斯特编码接收到的信号为“0XX1”(X表示碰撞位），即第1位和第2位均为碰撞位。图1所示为标签使用曼彻斯特编码的响应过程。

1.2 查询树算法

查询树算法主要由轮询和响应2个部分构成。在每一轮中，阅读器要发送一个字符串（即查询前缀），查询标签ID是否含有特定的前缀。只有ID与查询前缀相匹配的标签才能响应轮询命令。如果只有一个标签响应，那么该标签可以被成功识别，并将自己的ID发送给阅读器。如果有多个标签响应，那么就会发生标签碰撞，然后阅读器在该查询前缀后分别添加0和1构成了新的查询前缀。通过扩展前缀，直到只有一个标签的ID匹配。因此该算法可以识别所有的标签。

然而，在基本的查询树算法中如果没有标签的ID和查询前缀匹配，那么将会产生多余的空闲时隙。例如2个标签，它们的ID只有最后一位不同，其余各位均一致。那么为了识别这2个标签，将会产生许多的碰撞时隙和空闲时隙。同样，也会增加查询时间，使系统的查询效率下降。

1.3 基于查询树算法最近的研究成果

鉴于查询树算法的不足，研究学者们提出了许多基于查询树的改进算法。其中，Zhang等[14]提出了自适应四叉修剪查询树(A4PQT, adaptive 4-ary pruning query tree)算法。根据碰撞位的特点对四叉查询树进行改善，以减少不必要的空闲时隙。阅读器向读取范围内的标签发送查询前缀，匹配前缀的标签将除前缀外余下的ID发送给阅读器。当标签发生碰撞时，假设标签ID长度为bit，阅读器接收数据信息为12…p−1pp1…p，p为首碰撞位，那么可以分成3种情况。

1) 如果p1=0，那么阅读器将产生2个新的查询前缀，分别为12…p−100和12…p−110，并将原四叉树的“01”和“11”分支剔除。

2) 如果p1=1，那么阅读器将产生2个新的查询前缀，分别为12…p−101和12…p−111，并将原四叉树的“00”和“10”分支剔除。

3) 如果p1也是碰撞位，那么阅读器将产生4个新的查询前缀，分别为12…p−100、12…p−101、12…p−110和12…p−111，不剔除掉四叉树任何分支。

因此，A4PQT算法可以减少一些空闲时隙，所需要的总时隙为至2−3之间。然而，如果2个标签的ID分别为“01”和“10”，那么阅读器通过曼彻斯特编码得到的数据为“XX”，根据A4PQT算法将要产生4个查询前缀，由此将产生2个额外的空闲时隙。

针对上述研究所存在的问题，本文基于分组机制和查询树识别，提出一种基于分组机制的位仲裁查询树(GBAQT, bit arbitration query tree based on grouping mechanism)防碰撞算法。在GBAQT算法中标签根据ID自身特征，通过3位仲裁的方式将未识别标签分成2组，阅读器根据各组标签特点和接收数据的碰撞位信息能得到传输数据，减少了大量空闲时隙。仿真结果显示，与其他标签防碰撞算法相比，GBAQT算法具有较高的系统效率和时隙利用率，并且在较多标签存在的环境下具有明显的优势。

2 算法描述

目前，基于树的确定性算法中通常使用前缀来识别标签，在识别树中一般包括3个时隙。

碰撞时隙：在该时隙中，多个标签同时响应阅读器的查询，阅读器将不能识别任何标签，称该时隙为碰撞时隙。

成功时隙：在该时隙中只有1个标签响应阅读器，则标签能被成功识别，称该时隙为成功时隙。

空闲时隙：在该时隙中没有标签响应，则为空闲时隙。

2.1 基本思想

本文采用3位仲裁的方式来代替传统的1位仲裁，尽管采用多叉查询树能有效地减少碰撞时隙，但会带来大量的空闲时隙。因此，GBAQT算法对空闲时隙数进行了优化，通过标签ID的自身特征分组，由碰撞信息尽量准确地推断出传输数据的组合形式。

分组机制描述如下。假设标签ID长度为，标签的第位开始相邻3位为pp+1p+2，定义为异或运算符，如果pp+1=p+2，则pp+1p+2为第0组，表示为=0; 如果pp+1≠p+2，则pp+1p+2为第1组，表示为=1。例如标签的ID中3位连续数据为140516，符合1405=16，那么=0。另外，还发现以下规则：对于=0组的标签，pp1p23位数据符合其中任意2位异或都等于其余一位，由此定义=0组标签具有异或特征；而=1组标签，pp1p23位数据符合其中任意2位同或等于其余一位，由此定义=1组标签具有同或特征。

例如，在RFID系统中存在2个标签，分别为Tag A(101)和Tag B(110)，标签发送ID与组号信息，阅读器得到“1XX”和=0。根据=0组标签的异或特征，可得到传输数据的组合形式为：101和110，能准确地判断标签ID。相比A4PQT算法，可以减少2个空闲时隙。

2.2 算法相关指令

REQUEST(12…q,)请求命令，12…q为查询前缀，其中，{0,1},。表示组号，∈{0,1}。阅读器发送REQUEST(12…q,)命令，符合查询前缀为12…q且组号为的标签响应，处于激活状态。

PUSH()读写指令，将作为新的查询前缀压入栈的底部。

SELECT()选择指令，选择符合此ID的标签。

READ-DATA读取指令，读出标签ID的数据信息。

SILENCE静默指令，将标签置于静默状态，不再参与识别过程。

“”表示连接符，将2组数据连接组合成一组，如“0001”，表示将“00”和“01”连接成“0001”。

2.3 算法流程

GBAQT算法流程如图2所示。

第1步 初始化，阅读器置查询前缀堆栈和组号存储器为空。

第2步 阅读器发送REQUEST(12…q)。首次发送该命令时置查询前缀为，即读取范围内的标签全部响应。

第3步 与查询前缀12…q相匹配的标签响应。如果没有标签响应，则为空闲时隙，转到第6步；否则转到第4步。

第4步 阅读器查询标签是否发生碰撞。如果未发生碰撞，则该标签可以被成功识别，阅读器发送SELECT和READ-DATA指令，对标签读写操作后阅读器发送SILENCE指令，将标签置为静默状态，转到第6步；如果发生碰撞，则转到第5步。

第5步 假设阅读器接收的数据为12…p−1pp+1p+2，其中{0,1}，p表示最高碰撞位。从标签ID的p位开始的连续3位pp+1p+2为一组，执行分组指令，相应的置标签内部组号存储器为0或1。标签发送数据“pp+1p+2”。根据阅读器中组号存储器接收数据是否碰撞可分为以下2种情况讨论。

1) 如果阅读器的组号存储器发生碰撞，则先查询=0的标签，然后再查询=1的标签。若该组中没有标签响应，则为空闲时隙；若该组中只有一个标签响应，则可以直接识别，阅读器发送SELECT和READ-DATA指令，对标签读写操作后阅读器发送SILENCE指令，将标签置为静默状态；若该组发生碰撞，那么通过碰撞位信息，遵循其异或（或同或）特征可推断传输数据的组合形式，将“查询前缀传输数据”压入栈底，转到第6步。

2) 如果阅读器的组号存储器未发生碰撞，即为单一组号时，只查询符合该组的标签即可，转到第6步。

第6步 查询堆栈是否为空。若栈不为空，则从栈顶弹出数据作为新的查询前缀，转到第2步；若栈为空，则查询过程结束。

阅读器根据碰撞位信息，利用各组的异或（或同或）特征推断出传输数据的组合形式，具体描述如下，=0的标签中，若pp+1p+2中有2位碰撞位，利用该组的异或特征，从传输数据中已知的一位数据信息推断出另2位的组合形式，例如pp+1p+2= 1XX，则发送PUSH(12…q12…p−1101)和PUSH(12…q12…p−1110)；若pp+1p+2中的各位均为碰撞位，则推断为PUSH(12…q12…p−1000), PUSH(12…q12…p−1011), PUSH (qq…q12…p−1101), PUSH (12…q12…p−1110)。同样，的标签中，若pp+1p+2只有2位碰撞位，利用该组的同或特征，亦可以推断出这2个碰撞位的组合形式，例如pp+1p+2= 1XX，则发送PUSH(12…12…p−1100)和PUSH(12…12…p−1111)；若3位均为碰撞位则发送PUSH(12…q12…p−1001), PUSH(12…q12…p−1010), PUSH(12…q12…p−1100), PUSH(12…q12…p−1111)。

下面举例说明GBAQT算法识别标签的步骤。设有6个待识别标签，标签ID分别为Tag1(000110)、Tag2(000101)、Tag3(000011)、Tag4(011111)、Tag5(011010)、Tag6(111111)。GBAQT算法阅读器查询和标签响应过程如表1所示，对应的查询树结构如图3所示。

表1 阅读器查询和标签响应情况

3 算法性能分析

在RFID系统中，衡量防碰撞算法的优劣主要有2个指标：总时隙数和系统效率。下面通过计算总时隙数和系统效率来分析GBAQT算法性能。假设系统中有个标签，在第层的时候，对于完全八叉树有8个节点，由于每个节点可分为=0组和=1组，那么该层有组。由于每个标签的分配是相互独立的，其中有个标签在第层分配到同一组内的概率服从二项分布

该组为空闲的概率为

该组能被成功识别的概率为

(3)

该组发生碰撞的概率为

若该组为碰撞时隙，那么可以将树结构分为以下3种情况。

1) 只有2个子节点时，则一定没有空闲时隙；

2) 有3个子节点时，则必然产生3个非空闲时隙（其状态为碰撞还是成功时隙需有+1层进行判断）和一个空闲时隙；

3) 有4个子节点，则4个都是非空闲时隙。

因此，最佳树的情况应该没有空闲时隙，最差树的情况则是每个碰撞组有一个空闲时隙。

有3个节点的概率为

(6)

有4个节点的概率为

对于每组都只有2个节点的树结构，若只需要1层即可识别所有标签，那么总时隙

(8)

每组都有3个节点的树结构，若需要2层即可识别所有标签，那么总时隙

每组都有4个节点的树结构，若需要3层即可识别所有标签，那么总时隙

(10)

在GBAQT算法树结构中是2个节点、3个节点和4个节点混合的情况，为了便于分析，这里按各个情况发生的概率占总体发生概率的百分比得到：发生2个节点的概率；发生3个节点的概率；发生2个节点的概率。那么得到总时隙

空闲时隙数

(12)

系统效率为

4 仿真及分析

以Matlab2012a为仿真平台对算法进行仿真，阅读器读取范围内的标签数量取值范围为100~1 000，且标签ID随机产生，ID长度为96 bit进行仿真。下列结果仿真20次取平均值，下面将GBAQT算法与A4PQT算法、QT算法、八叉树算法进行仿真，分别从空闲时隙数、总时隙数、系统效率和时隙利用率4个方面的性能进行对比。

图4为GBAQT算法、A4PQT算法、QT算法和八叉树算法空闲时隙数比较，可以看出GBAQT算法的空闲时隙数远远小于A4PQT算法、QT算法和八叉树算法，并且随着值的增加，其空闲时隙数的增加趋势缓慢而稳定。然而八叉树的空闲时隙数增加的速度最快，在标签数量为1 000时，八叉树的空闲时隙数几乎是GBAQT算法的28倍。因此，当存在大量标签时，GBAQT算法的优势更加明显。

图5为GBAQT算法、A4PQT算法、QT算法和八叉树算法总时隙数的比较。识别个标签时，GBAQT算法所需的总时隙数明显小于A4PQT算法、QT算法和八叉树算法，并且在标签数量较多时，可有效地减少搜索的总时隙数。

图6对GBAQT算法、A4PQT算法、QT算法和八叉树算法的系统效率进行了比较，可以看出GBAQT算法的系统效率明显要优于A4PQT算法、QT算法和八叉树算法，可维持在0.54左右。其次是A4QPT算法效率，不超过0.49。四叉树算法系统效率次之，保持在0.35左右。八叉树算法的系统效率最低，在0.25至0.28之间浮动。

图7表示GBAQT算法、A4PQT算法、QT算法和八叉树算法的时隙利用率，其中时隙利用率=。由于GBAQT算法可以利用碰撞时隙反演出标签，因此碰撞时隙和成功时隙都是有用时隙。可以看出GBAQT的时隙利用率要优于其他3种算法，达到了0.95。其次是QT算法，时隙利用率维持在0.85左右。A4PQT算法次之，在0.77附近浮动。尽管八叉树算法能减少碰撞时隙，但同时也伴随着大量空闲时隙的产生，因此其系统利用率最低，不超过0.4。

5 结束语

本文基于分组机制和查询树识别，提出一种基于分组机制的位仲裁查询树防碰撞算法，该算法采用3位仲裁位的方式减少碰撞时隙，并根据标签ID自身特征分组，通过碰撞位信息得到的传输数据从而能避免一些空闲时隙。理论和仿真分析表明：GBAQT算法能有效地减少空闲时隙数，具有较低的总时隙数，并且能有效地提高系统效率和时隙利用率。在标签数量较多的情况下，GBAQT性能明显优于其他算法。

[1] BLETSAS A, KIMIONIS J, DIMITRIOUS A G, et al. Single-antenna coherent detection of collided FM0 RFID signals[J]. IEEE Transactions on Communications, 2012, 60(3):756-766.

[2] HSU C H, CHAO H C, PARK J H. Threshold jumping and wrap-around scan techniques toward efficient tag identification in high density RFID systems[J]. Information Systems Frontiers, 2011, 13(4):471-480.

[3] 李萌, 钱志鸿, 张旭, 等. 基于时隙预测的 RFID 防碰撞 ALOHA 算法[J]. 通信学报, 2012, 32(12):43-50.

LI M, QIAN Z H, ZHANG X, et alSlot-predicting based ALOHA algorithm for RFID anti-collision[J]. Journal on Communications, 2012, 32(12):43-50.

[4] ZANELLA A. Adaptive batch resolution algorithm with deferred feedback for wireless systems[J]. IEEE Transactions on Wireless Communications, 2012, 11(10):3528-3539.

[5] ZHU L, YUM T P. Optimal framed Aloha based anti-collision algorithms for RFID systems[J]. IEEE Transactions on Communications, 2010, 58(12):3583-3592.

[6] JIANG Y, ZHANG R N. An adaptive combination query tree protocol for tag identification in RFID systems[J]. IEEE Communications Letters, 2012,16(8):1192-1195.

[7] YANG C N, HU L J, LAI J B. Query tree algorithm for RFID tag with binary-coded decimal EPC[J]. I IEEE Communications Letters, 2010, 16(10):1616-1619.

[8] LAW C, LEE K, SIU K Y. Efficient memory-less protocol for tag identification[C]//The 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and CommunicationsBoston. c2000: 75-84.

[9] HUSH D R, WOOD C. Analysis of tree algorithms for RFID arbitration[C]//IEEE International Symposium on Information Theory. Cambridge, c1998: 107.

[10] JIA X L, FENG Q Y, YU L S. Stability analysis of an efficient anti-collision protocol for RFID tag identification[J]. IEEE Transactions on Communications, 2012, 60(8):2285-2294.

[11] LIU X H, QIAN Z H, ZHAO Y H, et al. An adaptive tag anti-collision protocol in RFID wireless systems[J]. China Communications, 2014, 11(7):117-127.

[12] GAO J, WANG J, HE J, et al. QSA: query splitting-based anticollision for mobile RFID-based internet-of-things[J]. International Journal of Distributed Sensor Networks, 2013, DOI:10.1155/2013/674698.

[13] CHEN Y H, HORNG S J, RUN R S, et al. A novel anti-collision algorithm in RFID systems for identifying passive tags[J]. IEEE Transactions on Industrial Informatics, 2010, 6(1):105-121.

[14] ZHANG W, GUO Y J, TANG X M, et al. An efficient adaptive anticollision algorithm based on 4-ary pruning query tree[J]. International Journal of Distributed Sensor Networks, 2013, 14(2): 135-143.

Bit arbitration query tree anti-collision algorithm based on grouping mechanism

FU Yu1, QIAN Zhi-hong1, CHENG Chao2, LIU Xiao-hui1

(1. College of Communication Engineering, Jilin University, Changchun 130012, China; 2. School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012, China)

A bit arbitration query tree anti-collision algorithm based on grouping mechanism was proposed. GBAQT divided tags into two groups according to the tag ID’s feature and used three arbitration bits to identify tags instead of using one bit in traditional methods. The reader can obtain the transmit data based on information of collision bits and thus avoid some idle timeslots. The algorithm performance analysis and simulation results show that GBAQT anti-collision algorithm has fewer total number of timeslots. Timeslot utilization and system efficiency of GBAQT algorithm are significantly better than the other algorithms.

RFID, tag anti-collision, query tree, grouping mechanism

TN92

A

10.11959/j.issn.1000-436x.2016014

2014-11-19；

2015-01-20

国家自然科学基金资助项目(No.61371092)；吉林省科技厅基金资助项目(No.20140204019GX)

The National Natural Science Foundation of China (No.61371092); Research Project of Science and Technology Department of Jilin Province (No.20140204019GX)

付钰（1990-），女，吉林省吉林市人，吉林大学博士生，主要研究方向为RFID和物联网。

钱志鸿（1957-），男，吉林长春人，吉林大学教授、博士生导师，主要研究方向为物联网、RFID、Wi-Fi、无线传感器网络和无线定位等。

程超（1984-），男，吉林长春人，博士，长春工业大学讲师，主要研究方向为短距离无线通信理论。

刘晓慧（1989-），女，吉林长春人，吉林大学硕士生，主要研究方向为无线通信理论。