动态帧时隙的二进制树RFID防碰撞算法研究

doi:10.16182/j.issn1004731x.joss.201803037

系统仿真学报 ›› 2018, Vol. 30 ›› Issue (3): 1063-1073.doi: 10.16182/j.issn1004731x.joss.201803037

动态帧时隙的二进制树RFID防碰撞算法研究

张小红, 周伟辉

(江西理工大学信息工程学院,江西赣州 341000)

收稿日期:2016-04-06 出版日期:2018-03-08 发布日期:2019-01-02
作者简介:张小红(1966-),女,河北昌黎,博士,教授,研究方向为非线性动力学,无线识别技术。
基金资助:
.国家自然科学基金(61363076, 51665019),江西省教育厅重点科技项目(GJJ150621),江西省研究生创新专项资金(YC2015-S290)

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

Zhang Xiaohong, Zhou Weihui

School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China

Received:2016-04-06 Online:2018-03-08 Published:2019-01-02

摘要/Abstract

摘要： 为解决无线射频识别(Radio Frequency Identification,RFID)系统多标签碰撞问题,在分析动态帧时隙ALOHA算法和二进制搜索树算法基础上,提出一种基于动态帧时隙的二进制树RFID防碰撞算法(Dynamic Framed Binary Tree,DFBT)。采用Vogt算法预先估计待识别标签总数,利用动态帧时隙ALOHA算法对标签进行识别,阅读器将未识别的标签提取出来进行最高碰撞位的判断,根据最高碰撞位的情况结合二进制搜索树算法进行碰撞标签分裂。仿真结果表明：DFBT算法提高了识别效率和稳定性,减少了总时隙数,降低了标签成本。当标签数目达到1 000左右,算法识别效率可以达到64%左右,比动态帧时隙ALOHA算法和后退式二进制搜索树算法分别提高了210%和30%。

关键词: 无线射频识别, 动态帧时隙ALOHA算法, 二进制搜索树算法, 防碰撞算法, 识别效率

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

中图分类号:

TN911.23

张小红, 周伟辉. 动态帧时隙的二进制树RFID防碰撞算法研究[J]. 系统仿真学报, 2018, 30(3): 1063-1073.

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.

参考文献 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.

动态帧时隙的二进制树RFID防碰撞算法研究

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

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献 20

相关文章 4

编辑推荐

Metrics

本文评价

[1]	吴晨曦, 张旻, 王可人. 基于连续稀疏重构的宽频段二维波达方向估计[J]. 系统仿真学报, 2018, 30(8): 3015-3023.
[2]	金允钢, 张小红, 王秋丽. RFID系统欠定盲分离的汉明重分组防碰撞算法[J]. 系统仿真学报, 2017, 29(7): 1514-1520.
[3]	乔培, 肖丽媛, 韩妍妍, 高岭. 认知无线电系统中搜索空闲信道的平均时间优化算法[J]. 系统仿真学报, 2016, 28(3): 727-732.
[4]	张小红, 金允钢. 基于帧时隙的欠定盲分离RFID防碰撞算法研究[J]. 系统仿真学报, 2016, 28(5): 1100-1108.