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

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

摘要/Abstract

摘要：

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

关键词: RFID, 标签防碰撞, 查询树, 分组机制

Abstract:

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 resu 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.

Key words: RFID, tag anti-collision, query tree, grouping mechanism

付钰,钱志鸿,程超,刘晓慧. 基于分组机制的位仲裁查询树防碰撞算法[J]. 通信学报, 2016, 37(1): 123-129.

Yu FU,hong QIANZhi,Chao CHENG,hui LIUXiao. Bit arbitration query tree anti-collision algorithm based on grouping mechanism[J]. Journal on Communications, 2016, 37(1): 123-129.

图/表 8

图1

图2

表1

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

阅读器查询命令	响应的标签	碰撞信息	查询堆栈S
REQUEST(e )	Tag1~Tag 6	碰撞,XXX,G=X	S为空
REQUEST(e,0)	Tag1~Tag 5	碰撞，0XX	S={000,011}
REQUEST(e,1)	Tag6	识别	S={000,011}
REQUEST(000)	Tag1~Tag 3	碰撞，XXX,G =0	$S = {011, 000 \underline{000}, 000 \underline{011}, 000 \underline{101}, 000 \underline{110}}$
REQUEST(011)	Tag4、Tag5	碰撞，X1X,G =1	$S = {000 \underline{000}, 000 \underline{011}, 000 \underline{101}, 000 \underline{110}, 011 \underline{010}, 011 \underline{111}}$
$R E Q U E S T (000 \underline{000})$	-	空闲	$S = {000 \underline{011}, 000 \underline{101}, 000 \underline{110}, 011 \underline{010}, 011 \underline{111}}$
$R E Q U E S T (000 \underline{011})$	Tag3	识别	$S = {000 \underline{101}, 000 \underline{110}, 011 \underline{010}, 011 \underline{111}}$
$R E Q U E S T (000 \underline{101})$	Tag2	识别	$S = {000 \underline{110}, 011 \underline{010}, 011 \underline{111}}$
$R E Q U E S T (000 \underline{110})$	Tag1	识别	$S = {011 \underline{010}, 011 \underline{111}}$
$R E Q U E S T (011 \underline{010})$	Tag5	识别	$S = {011 \underline{111}}$
$R E Q U E S T (011 \underline{111})$	Tag4	识别	空

表1

图3

图4

图5

图6

图7

参考文献 14

[1]	BLETSAS A , KIMIONIS J , DIMITRIOUS A G , et al. Single-antenna coherent detection of collided FM0 RFID signals[J]. IEEE Transac-tions 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 al. Slot-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 algo-rithms for RFID systems[J]. IEEE Transactions on Commu ications, 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 Let-ters, 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 Algo-rithms and Methods for Mobile Computing and CommunicationsBos-ton. c2000:75-84.
[9]	HUSH D R , WOOD C . Analysis of tree algorithms for RFID arbitra-tion[C]// IEEE International Symposium on Information Theory. Cam-bridge, c1998:107.
[10]	JIA X L , FENG Q Y , YU L S . Stability analysis of an ef icient an-ti-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 IEEE Transactions on Industrial Informatics. 2012,6(1): 105-121.
[14]	ZHANG W , GUO Y J , TANG X M , et al. An efficient adaptive anti-collision algorithm based on 4-ary pruning query tree. International Journal of Distributed Sensor Networks, 2013,14(2): 135-143.

[1]	张莉涓, 范明秋, 雷磊, 王勇, 袁代数. 捕获效应下基于比特检测的多分支树RFID标签识别协议[J]. 通信学报, 2021, 42(11): 205-216.
[2]	张兴，韩冬，曹光辉，贾旭. 基于PRESENT算法的RFID安全认证协议[J]. 通信学报, 2015, 36(Z1): 65-74.
[3]	王雪,钱志鸿,刘晓慧,程超. 改进的树型结构RFID防碰撞算法[J]. 通信学报, 2015, 36(7): 129-137.
[4]	吴海锋,曾玉. 物理层的超高频RFID标签信号分离[J]. 通信学报, 2015, 36(2): 20-28.
[5]	朱大立，荣文晶，王思叶，庞娜. 基于树形模型的轻量级RFID组证明协议[J]. 通信学报, 2015, 36(11): 15-24.
[6]	袁红林,包志华,严燕. 基于对数谱射频指纹识别的RFID系统信息监控方法[J]. 通信学报, 2014, 35(7): 86-93.
[7]	杨茜,吴海锋,曾玉. 捕获效应下RFID标签的CATPE防冲突协议[J]. 通信学报, 2014, 35(7): 215-222.
[8]	杨茜，吴海锋，曾玉. 捕获效应下RFID标签的CATPE防冲突协议[J]. 通信学报, 2014, 35(7): 26-222.
[9]	袁红林，包志华. 基于对数谱射频指纹识别的RFID系统信息监控方法[J]. 通信学报, 2014, 35(7): 11-93.
[10]	黄琼,凌江涛,张敏,阳小龙. LRST：低冗余搜索树防碰撞算法[J]. 通信学报, 2014, 35(6): 110-115.
[11]	黄琼，凌江涛，张敏，阳小龙. LRST：低冗余搜索树防碰撞算法[J]. 通信学报, 2014, 35(6): 14-116.
[12]	杨玉龙,彭长根,周洲,张晓培. 基于Edwards曲线的移动RFID安全认证协议[J]. 通信学报, 2014, 35(11): 132-138.
[13]	杨玉龙，彭长根，周洲，张晓培. 基于Edwards曲线的移动RFID安全认证协议[J]. 通信学报, 2014, 35(11): 15-137.
[14]	李文秀,郭亚红,李金宝,郭龙江,张绍斌. 物联网中基于多reader合作机制的RFID-sensor信息收集协议[J]. 通信学报, 2013, 34(Z1): 292-302.
[15]	陈兵，郑嘉琦. 轻型的RFID安全认证协议LAP[J]. 通信学报, 2013, 34(Z1): 1-7.