Journal of Jilin University(Engineering and Technology Edition) ›› 2021, Vol. 51 ›› Issue (5): 1830-1837.doi: 10.13229/j.cnki.jdxbgxb20200808

Previous Articles    

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)

91

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

CLC Number: 

  • TP393

Table 1

Example of QT"

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

Fig.1

Query command and samples of queries and corresponding responses of bidirectional algorithm"

Table 2

Example of bidirectional query algorithm"

时隙查询命令标签响应数据时隙状态
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

Fig.2

Collision tree of segmented query algorithm"

Fig.3

Flow chart of BDS algorithm"

Fig.4

Changes in average transmitted bits of BDS with length of segment point increasing"

Fig.5

Transmitted bits for one tag identification of BDS with different lengths of segment points"

Fig.6

Throughput rate of different algorithms"

Fig.7

Transmitted bits for one tag identification of different algorithms"

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] Jie CAO,Xue QU,Xiao-xu LI. Few⁃shot image classification method based on sliding feature vectors [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(5): 1785-1791.
[2] Chun-bo WANG,Xiao-qiang DI. Cloud storage integrity verification audit scheme based on label classification [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(4): 1364-1369.
[3] Rong QIAN,Ru ZHANG,Ke-jun ZHANG,Xin JIN,Shi-liang GE,Sheng JIANG. Capsule graph neural network based on global and local features fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1048-1054.
[4] Qian-yi XU,Gui-he QIN,Ming-hui SUN,Cheng-xun MENG. Classification of drivers' head status based on improved ResNeSt [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 704-711.
[5] Yuan SONG,Dan-yuan ZHOU,Wen-chang SHI. Method to enhance security function of OpenStack Swift cloud storage system [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(1): 314-322.
[6] Xiang-jiu CHE,You-zheng DONG. Improved image recognition algorithm based on multi⁃scale information fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1747-1754.
[7] HU Guan-yu, QIAO Pei-li. High dimensional differential evolutionary algorithm based on cloud population for network security prediction [J]. 吉林大学学报(工学版), 2016, 46(2): 568-577.
[8] CHEN Zeng-qiang, GUO Feng, NIU Pan-feng, ZHANG Qing. Radio frequency identification indoor location algorithm with virtual tags [J]. 吉林大学学报(工学版), 2015, 45(6): 1887-1894.
[9] TONG Jin, WANG Ya-hui, FAN Xue-mei, ZHANG Shu-jun, CHEN Dong-hui. Monitoring system of cold chain logistics for farm fresh produce [J]. 吉林大学学报(工学版), 2013, 43(06): 1707-1711.
[10] NING Fang-hua, ZHANG Yan-wei, YU Wu-jia. Security project for radio frequency identification access control system based on random hash-lock [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 317-321.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd