Research on Dynamic Framed Binary Tree Anti-collision Algorithm for RFID System

doi:10.16182/j.issn1004731x.joss.201803037

Abstract

Abstract: Based on dynamic frame-slotted ALOHA algorithm and binary search tree algorithm, a dynamic framed binary tree (DFBT) anti-collision algorithm is presented to solve the problem of multi-tag collision in radio frequency identification (RFID). Vogt algorithm is adopted to estimate tags number, then the dynamic frame-slotted ALOHA (DFSA) algorithm is used to identify tags, and the unidentified tags are extracted and the highest collision bit is judged by readers. The highest collision tags are grouped by the collision bit within the binary search tree (BST) algorithm. Simulation results show that the DFBT algorithm can improve the identification efficiency and stability which reduces the total time slots and the cost. When the tags number is about 1000, identification efficiency of the DFBT algorithm is about 64%. Compared with the DFSA algorithm and the regressive-style binary search tree (RBST) algorithm, the proposed algorithm enhances the identification efficiency by 210% and 30% respectively.

Key words: radio frequency identification, dynamic frame-slotted ALOHA algorithm, binary search tree algorithm, anti-collision algorithm, identification efficiency

CLC Number:

TN911.23

Zhang Xiaohong, Zhou Weihui. Research on Dynamic Framed Binary Tree Anti-collision Algorithm for RFID System[J]. Journal of System Simulation, 2018, 30(3): 1063-1073.

References 20

[1]	张智文. 射频识别技术理论与实践[M]. 中国科学技术出版社, 2008: 10-22.Zhang Zhiwen. Theory and practice of RFID Technology[M]. China Science and Technology Press, 2008: 10-22.
[2]	张小红, 肖娟凤. 无源RFID系统标签防碰撞优化算法研究[J]. 系统仿真学报, 2014, 26(6): 1320-1326, 1361.Zhang Xiaohong, Xiao Juanfeng. Passive RFID system tag anti-collision optimization algorithms[J]. Journal of System Simulation, 2014, 26(6): 1320-1326, 1361.
[3]	Yoon W, Vaidya N H.RFID reader collision problem: performance analysis and medium access[J]. Wireless Communications and Mobile Computing (S1530-8669), 2012, 12(5): 420-430.
[4]	Yang X, Wu H, Zeng Y, et al.Capture-aware estimation for the number of RFID tags with lower complexity[J]. IEEE Communications Letters (S1089-7798), 2013, 17(10): 1873-1876.
[5]	魏静, 冯秀芳. 基于自适应分组的帧时隙ALOHA算法在RFID中的研究[J]. 计算机技术与发展, 2012, 22(11): 57-60. Wei Jing, Feng Xiufang. Research on a frame-slotted ALOHA based on adaptive splitting method for RFID[J]. Computer Technology and Development, 2012, 22(11): 57-60.
[6]	Liva G.Graph-based analysis and optimization of contention resolution diversity slotted ALOHA[J]. IEEE Transactions on Communications (S0090-6778), 2011, 59(2): 477-487.
[7]	Wu H, Zeng Y.Efficient framed slotted Aloha protocol for RFID tag anti-collision[J]. IEEE Transactions on Automation Science and Engineering (S1545-5955), 2011, 8(3): 581-588.
[8]	Deng D J, Tsao H W.Optimal dynamic framed slotted ALOHA based anti-collision algorithm for RFID systems[J]. Wireless Personal Communications (S0929-6212), 2011, 59(1): 109-122.
[9]	鞠伟成, 俞承芳. 一种基于动态二进制的 RFID 抗冲突算法[J]. 复旦学报(自然科学版), 2005, 44(1): 46-47. Ju Weicheng, Yu Chengfang. An anti-collision RFID algorithm based on the dynamic binary[J]. Journal of Fudan University (Natural Science), 2005, 44(1): 46-47.
[10]	Crain T, Gramoli V, Raynal M.A Speculation-friendly binary search tree[J]. Acm Sigplan Notices (S0362-1340), 2012, 47(8): 161-170.
[11]	樊文静, 张姗姗, 田智慧. 基于后退式二进制搜索的RFID防碰撞算法的研究[J]. 计算机应用与软件, 2012, 29(5): 191-194.Fan Wenjing, Zhang Shanshan, Tian Zhihui. Research on RFID anti-collision algorithm based on regressive-style binary search[J]. Computer Applications and Software, 2012, 29(5): 191-194.
[12]	王亚奇, 蒋国平. 基于分组机制的跳跃式动态二进制防碰撞算法[J]. 自动化学报, 2012, 36(10): 1390-1400.Wang Yaqi, Jiang Guoping. Anti-collision algorithm based on grouping mechanism and jumping dynamic binary[J]. Acta Automatic Sinica, 2012, 36(10): 1390-1400.
[13]	Yang C N, He J Y.An effective 16-bit random number aided query tree algorithm for RFID tag anti-collision[J]. IEEE Communications Letters (S1089-7798), 2011, 15(5): 539-541.
[14]	丁治国, 朱学永, 郭立, 等. 自适应多叉树防碰撞算法研究[J]. 自动化学报, 2010, 36(2): 237-241.Ding Zhiguo, Zu Xueyong, Guo li, et al. An adaptive anti-collision algorithm based on multi-tree search[J]. Acta Automatic Sinica, 2010, 36(2): 237-241.
[15]	吴海锋, 曾玉. RFID动态帧时隙ALOHA防冲突中的标签估计和帧长确定[J]. 自动化学报, 2010, 36(4): 620-624.Wu Haifeng, Zeng Yu. Tag estimate and fame length for dynamic frame slotted ALOHA anti-collision RFID system[J]. Acta Automatic Sinica, 2010, 36(4): 620-624.
[16]	Schoute F C.Dynamic frame length ALOHA[J]. IEEE Transactions on Communications (S0090-6778), 1983, 31(4): 565-568.
[17]	Chen W T.An accurate tag estimate method for improving the performance of an RFID anti-collision algorithm based on dynamic frame length ALOHA[J]. IEEE Transactions on Automation Science and Engineering (S1545-5955), 2009, 6(1): 9-15.
[18]	庞宇, 彭琦, 林金朝, 等. 基于分组动态帧的射频识别防碰撞算法[J]. 物理学报, 2013, 62(14): 148401.Pang Yu, Peng Qi, Lin Jinzhao, et al. Reducing tag collision in radio frequency identification systems by using a grouped dynamic frame slotted ALOHA algorithm[J]. Acta Physica Sinica, 2013, 62(14): 148401.
[19]	尹君, 何恰刚, 李兵, 等. 基于分组动态帧时隙的 RFID 防碰撞算法[J]. 计算机工程, 2009, 35(20): 267-269.Yin Jun, He Qiagang, Li Bing, et al. RFID Anti-collision algorithm based on grouping dynamic frame slotted[J]. Computer Engineering, 2009, 35(20): 267-269.
[20]	宋建华, 郭亚军, 韩兰胜, 等. 自调整混合树 RFID 多标签防碰撞算法[J]. 电子学报, 2014, 42(4): 685-689.Song Jianhua, Guo Yajun, Han Lansheng, et al. An adjustive hybrid tree anti-collision algorithm for RFID multi-tag identification[J]. Acta Electronica Sinica, 2014, 42(4): 685-689.