吉林大学学报(工学版) ›› 2021, Vol. 51 ›› Issue (5): 1830-1837.doi: 10.13229/j.cnki.jdxbgxb20200808

• 计算机科学与技术 • 上一篇    

基于查询树的双向分段防碰撞算法

赵宏伟1,2(),张子健1,李蛟3(),张媛1,胡黄水4,臧雪柏1   

  1. 1.吉林大学 计算机科学与技术学院，长春 130012
    2.吉林大学 符号计算与知识工程教育部重点实验室，长春 130012
    3.吉林大学 图书馆，长春 130012
    4.长春工业大学 计算机科学与工程学院，长春 130012
  • 收稿日期:2020-10-22 出版日期:2021-09-01 发布日期:2021-09-16
  • 通讯作者: 李蛟 E-mail:zhaohw@jlu.edu.cn;lijiao@jlu.edu.cn
  • 作者简介:赵宏伟（1962-），男，教授，博士生导师.研究方向：嵌入式人工智能.E-mail：zhaohw@jlu.edu.cn
  • 基金资助:
    吉林省省级科技创新专项项目(20190302026GX);吉林省自然科学基金项目(20200201037JC);吉林省发改委产业技术研究与开发项目(2019C054-4);中国高校科技期刊研究会青年基金资助项目(CUJS-QN-2021-049)

Bi⁃direction segmented anti⁃collision algorithm based on query tree

Hong-wei ZHAO1,2(),Zi-jian ZHANG1,Jiao LI3(),Yuan ZHANG1,Huang-shui HU4,Xue-bai ZANG1   

  1. 1.College of Computer Science and Technology，Jilin University，Changchun 130012，China
    2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education，Jilin University，Changchun 130012，China
    3.Library，Jilin University，Changchun 130012，China
    4.School of Computer Science and Engineering，Changchun University of Technology，Changchun 130012，China
  • Received:2020-10-22 Online:2021-09-01 Published:2021-09-16
  • Contact: Jiao LI E-mail:zhaohw@jlu.edu.cn;lijiao@jlu.edu.cn

RICH HTML

 6   

PDF (PC)

75

摘要：

针对射频识别系统中由多标签碰撞导致系统效率低的问题，提出了一种基于查询树算法的防碰撞算法，意在减少系统能量损耗以及提高通信效率。该方法将标签分两组并将ID分段，使两组标签分别响应查询命令中的前缀和后缀，且根据查询命令中的状态码，只传输查询段的部分ID序列。与传统的查询树算法比较，该算法显著减少了对识别过程无用的比特信息的传输，消除了空闲时隙，同时提高了系统吞吐率。理论分析和仿真结果表明：本文算法优于现有的查询树防碰撞算法，有助于设计高效的RFID识别系统。

关键词: 计算机应用技术, 射频识别, 防碰撞, 双向, 预识别

Abstract:

Focusing on the problem of the low system efficiency caused by multi-tags collision of RFID system， this paper proposes an anti-collision algorithm based on query tree， intended to reduce system energy consumption and improve communication efficiency. The method divides the tags into two groups and segments the IDs so that the tags respectively respond to the prefix and suffix in the query command and only transmit the partial ID sequence of the query segment according to the state code. Compared with the traditional query tree algorithm， the algorithm significantly reduces the transmission of bits useless for identification， eliminates idle time slots， and improves system throughput. Theoretical analysis and simulation results show that the proposed algorithm performs better than the existing query tree anti-collision algorithm and helps to design an efficient RFID identification system.

Key words: computer application technology, radio frequency identification, anti-collision algorithm, bi-direction, pre identification

中图分类号: 

  • TP393

表1

QT算法实例"

时隙查询前缀响应时隙状态
1εxxxx碰撞
200xx碰撞
31x0x碰撞
400xx碰撞
501-空闲
61001识别A
71100识别B
80001识别C
90010识别D

图1

查询命令与对应的标签响应"

表2

双向匹配算法识别示例"

时隙查询命令标签响应数据时隙状态
PrefixSuffixState_PState_S
10ε00xxxxx0x碰撞
20111110x10P预识别“0110”，S预识别“0101”、“1101”
3011011012201001100P识别E，S识别D
400010112x01011P预识别“0000”、“0001”，S识别F
50001021xxxx100S预识别“1000”
6000111000220011001P识别G
700010ε23110P识别C
80000ε231011P识别A

图2

分段查询算法碰撞树"

图3

BDS算法流程"

图4

BDS算法平均传输数据量随分段点长度变化情况"

图5

BDS算法不同分段点长度下的平均传输数据量"

图6

不同算法的吞吐率"

图7

不同算法的平均传输数据量"

1 黄凯锋, 刘为超, 李莉. Hash函数与椭圆曲线密码相融合的双向认证方案[J]. 吉林大学学报: 理学版, 2017, 55(2): 340-344.
Huang Kai-feng, Liu Wei-chao, Li Li. Mutual-authentication scheme based on Hash function and elliptic curve cryptography[J]. Journal of Jilin University(Science Edition), 2017, 55(2): 340-344.
2 胡黄水, 张国, 王宏志, 等. 一种基于等区域划分的RFID防碰撞算法[J]. 吉林大学学报: 理学版, 2020, 58(1): 120-126.
Hu Huang-shui,Zhang Guo, Wang Hong-zhi, et al.An RFID anti-collision algorithm based on equal area division[J]. Journal of Jilin University(Science Edition), 2020, 58(1): 120-126.
3 Liu L, Lai S. ALOHA-based anti-collision algorithms used in RFID system[C]∥International Conference on Wireless Communications, Networking and Mobile Computing, Wuhan, 2006: 1-4.
4 Vogt H. Efficient object identification with passive RFID tags[C]∥International Conference on Pervasive Computing, Berlin, Heidelberg, 2002: 98-113.
5 Lee S R, Joo S D, Lee C W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C]∥The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, San Diego, 2005: 166-172.
6 Law C, Lee K, Siu K Y. Efficient memoryless protocol for tag identification[C]∥Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Boston, 2000: 75-84.
7 Finkenzeller K. RFID Handbook: Fundamentals and Applications in Contactless Smart Cards, Radio Frequency Identification and Near-Field Communication[M]. Hoboken: John wiley & sons, 2010.
8 Su J, Wen G, Hong D. A new RFID anti-collision algorithm based on the Q-ary search scheme[J]. Chinese Journal of Electronics, 2015, 24(4): 679-683.
9 Landaluce H, Perallos A, Angulo I. Managing the number of tag bits transmitted in a bit-tracking RFID collision resolution protocol[J]. Sensors, 2014, 14(1): 1010-1027.
10 王鑫, 贾庆轩, 高欣, 等. 高效无线射频识别自适应型跟踪树防碰撞算法[J]. 吉林大学学报: 工学版, 2015, 45(4): 1225-1233.
Wang Xin, Jia Qing-xuan, Gao Xin, et al. Highly efficient RFID adaptive tracking tree anti-collision algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2015, 45(4): 1225-1233.
11 Su J, Sheng Z, Liu A X, et al. A group-based binary splitting algorithm for UHF RFID anti-collision systems[J]. IEEE Transactions on Communications, 2019, 68(2): 998-1012.
12 胡黄水, 秦贵和. 基于实际无线环境的无线传感器网络拓扑控制算法[J]. 吉林大学学报: 工学版, 2012, 42(4): 958-962.
Hu Huang-shui, Qin Gui-he. Real wireless environment based topology control algorithm for wireless sensor networks[J]. Journal of Jilin University(Engineering and Technology Edition), 2012, 42(4): 958-962.
13 Jia X, Feng Q, Yu L. Stability analysis of an efficient anti-collision protocol for RFID tag identification[J]. IEEE Transactions on Communications, 2012, 60(8): 2285-2294.
14 Djeddou M, Khelladi R, Benssalah M. Improved RFID anti-collision algorithm[J]. AEU-international Journal of Electronics and Communications, 2013, 67(3): 256-262.
15 张志宏, 刘传领. 基于灰狼算法优化深度学习网络的网络流量预测[J]. 吉林大学学报: 理学版, 2021, 59(3): 619-626.
Zhang Zhi-hong, Liu Chuan-ling. Grey wolf algorithm to optimize network traffic prediction of deep learning network[J]. Journal of Jilin University(Science Edition), 2021, 59(3): 619-626.
16 王宏志, 郭嫚嫚, 胡黄水, 等. 基于改进烟花算法的以太网通信链路调度方法[J]. 吉林大学学报: 理学版, 2021, 59(2): 359-364.
Wang Hong-zhi, Guo Man-man, Hu Huang-shui, et al.Ethernet communication link scheduling Method Based on improved fireworks algorithm[J].Journal of Jilin University(Science Edition),2021,59(2):359-364.
17 张森悦, 谭文安, 王楠. 基于布谷鸟搜索算法参数优化的组合核极限学习机[J]. 吉林大学学报: 理学版, 2019, 57(5): 1185-1192.
Zhang Sen-yue, Tan Wen-an, Wang Nan. Combined kernel extreme learning machine based on cuckoo search algorithm parameter optimization[J]. Journal of Jilin University(Science Edition), 2019, 57(5): 1185-1192.
18 王颖, 曹捷, 邱志洋. 基于乌鸦搜索算法的新型特征选择算法[J]. 吉林大学学报: 理学版, 2019, 57(4):869-874.
Wang Ying, Cao Jie, Qiu Zhi-yang. A novel feature selection algorithm based on crow search algorithm[J]. Journal of Jilin University(Science Edition), 2019, 57(4): 869-874.
[1] 曹洁,屈雪,李晓旭. 基于滑动特征向量的小样本图像分类方法[J]. 吉林大学学报(工学版), 2021, 51(5): 1785-1791.
[2] 王春波,底晓强. 基于标签分类的云数据完整性验证审计方案[J]. 吉林大学学报(工学版), 2021, 51(4): 1364-1369.
[3] 钱榕,张茹,张克君,金鑫,葛诗靓,江晟. 融合全局和局部特征的胶囊图神经网络[J]. 吉林大学学报(工学版), 2021, 51(3): 1048-1054.
[4] 周炳海,吴琼. 基于多目标的机器人装配线平衡算法[J]. 吉林大学学报(工学版), 2021, 51(2): 720-727.
[5] 许骞艺,秦贵和,孙铭会,孟诚训. 基于改进的ResNeSt驾驶员头部状态分类算法[J]. 吉林大学学报(工学版), 2021, 51(2): 704-711.
[6] 宋元,周丹媛,石文昌. 增强OpenStack Swift云存储系统安全功能的方法[J]. 吉林大学学报(工学版), 2021, 51(1): 314-322.
[7] 车翔玖,董有政. 基于多尺度信息融合的图像识别改进算法[J]. 吉林大学学报(工学版), 2020, 50(5): 1747-1754.
[8] 倪涛,刘海强,王林林,邹少元,张红彦,黄玲涛. 基于双向长短期记忆模型的起重机智能操控方法[J]. 吉林大学学报(工学版), 2020, 50(2): 445-453.
[9] 刘红喜, 孙俊喜, 孙宏彬, 刘广文. 样本块双向匹配图像修补算法[J]. 吉林大学学报(工学版), 2016, 46(6): 2111-2115.
[10] 胡冠宇, 乔佩利. 基于云群的高维差分进化算法及其在网络安全态势预测上的应用[J]. 吉林大学学报(工学版), 2016, 46(2): 568-577.
[11] 陈增强， 国峰， 牛攀峰， 张青. 加入虚拟标签的射频识别室内定位算法[J]. 吉林大学学报(工学版), 2015, 45(6): 1887-1894.
[12] 王鑫, 贾庆轩, 高欣, 赵兵, 崔宝江. 高效无线射频识别自适应型跟踪树防碰撞算法[J]. 吉林大学学报(工学版), 2015, 45(4): 1225-1233.
[13] 郑宏宇, 宗长富, 何磊, 陈国迎, 刘明辉. 基于双向控制的线控转向系统路感设计[J]. 吉林大学学报(工学版), 2014, 44(6): 1545-1549.
[14] 林婷婷, 史文龙, 齐鑫, 林君. 下水探测全波收录系统[J]. 吉林大学学报(工学版), 2014, 44(4): 1024-1030.
[15] 佟金, 王亚辉, 樊雪梅, 张书军, 陈东辉. 生鲜农产品冷链物流状态监控信息系统[J]. 吉林大学学报(工学版), 2013, 43(06): 1707-1711.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发