Adaptive N Tree Anti-Collision Algorithm Based on Bitmap Construction

Abstract

Abstract:

Abstract： Aimed at the RFID (radio frequency identification) collision problem caused by multiple access of shared channel, this paper proposed two RFID adaptive N tree anticollision algorithms based on bitmap construction, single frame bitmap track N tree algorithm (SFBTNA) and multiframe bitmap track N tree algorithm(MFBTNA). First of all, the two methods take advantage of the maximum likelihood tag numbers estimation method (MLBE) that can effectively estimate the number of tags. Secondly, based on the MLBE, it put forward the probe method construct bitmap. The SFBTNA adaptively adjusts the optimization value of N and builds N trees on one frame based on bitmap. The MFBTNA adaptively adjusts optimization value of N and builds N trees frame by frame. At the same time, the SFBTNA and MFBTNA identify the subtrees using collision track tree algorithm (CT). The combination of bitmap and CT greatly reduces the impact of collision time slot. Theoretical analysis and simulation experiments show that the performance of the two algorithms is higher than that of the other existing anticollision algorithms.

Key words: radio frequency identification (RFID), anticollision, adaptive, throughput rate

CLC Number:

TP 393

WANG Xin1,JIA Qingxuan1,GAO Xin1,CHEN Gang1,ZHAO Bing2. Adaptive N Tree Anti-Collision Algorithm Based on Bitmap Construction[J]. Journal of Shanghai Jiaotong University, 2015, 49(02): 150-157.

References

［1］Ullah S, Alsalih W, Alshaim A, et al. A review of tags anticollision and localization protocols in RFID networks ［J］. Journal of Medical Systems, 2012, 36(6): 40374050.

［2］Klair K, Chin W, Raad R. A survey and tutorial of RFID anticollision protocols ［J］. IEEE Communications Surveys and Tutorials, 2010, 12(3): 400421.

［3］Namboodiri V, DeSilva M, Deegala K, et al. An extensive study of slotted Alohabased RFID anticollision protocols ［J］. Computer Communications, 2013, 35(16): 19551966.

［4］Rao S S, Rajan E G, Lalkishore K. ASAF ALOHA protocol for dense RFID systems ［J］. Wireless Personal Communications, 2013, 66(4): 667681.

［5］Javier V A, Victoria B D, Esteban E L, et al. Multiframe maximumlikelihood tag estimation for RFID anticollision protocols ［J］. IEEE Trans on Industrial Informatics, 2011, 7(3): 487496.

［6］He Y J, Wang X Y. An Alohabased improved anticollision algorithm for RFID systems ［J］. IEEE Wireless Communications, 2013, 20(5): 152158.

［7］Yang C N, Hu L J, Lai J B. Query tree algorithm for RFID tag with binarycoded decimal EPC ［J］. IEEE Communications Letters, 2012, 16(10): 16161619.

［8］Gou H, Yoo Y. Bit collision detection based query tree protocol for anticollision in RFID system ［J］. International Journal of Innovative Computing Information and Control, 2012, 8(5A): 30813102.

［9］Lai Y C, Hsiao L Y. General binary tree protocol for coping with the capture effect in RFID tag identification ［J］. IEEE Communications Letters, 2010, 14(3): 208210.

［10］Jia X L, Feng Q Y, Yu L S, et al. Stability analysis of an efficient anticollision protocol for RFID tag identification ［J］. IEEE Transactions on Communications, 2012, 60(8): 22852294.

［11］Lai Y C, Chen H J, Lai C N, et al. A novel query tree protocol with bit tracking in RFID tag identification ［J］. IEEE Transactions on Mobile Computing, 2013, 12(10): 20632074.

［12］Chen W T, Lin G H. An efficient scheme for multiple access in a RFID system ［J］. IEICE Trans Commun, 2006, E89B(12): 33863392.

［13］EPCGLOBAL. EPCGLOBC1G2: Radiofrequency identity protocol Class1 Generation2 UHF RFID protocol for communication at 860MHZ960MHZ Version1.2.0. ［EB/OL］. （20081023) ［20140507］,http:∥www.gs1.org/gsmp/kc/epcglobal/uhfc1g2/uhfc1g2_1_2_0standard20080511.pdf.

[1]	BAO Jiahan, SUN Deshang, HUANG Jianzhong, HU Zheng. FAST Algorithm for Accurate Corner Points Detection of Section Steel Based on Adaptive Threshold [J]. Journal of Shanghai Jiao Tong University, 2025, 59(5): 691-702.
[2]	LI Yang, ZHANG Xiantao, XIAO Longfei. Parameter Control of Adaptive Bistable Point Absorber Wave Energy Converter in Irregular Waves [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 293-302.
[3]	XUE Ang, JIANG Enyu, ZHANG Wentao, LIN Shunfu, MI Yang. Detection of Foreign Bodies in Transmission Line Channels Based on Fusion of Swin Transformer and YOLOv5 [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 413-423.
[4]	Zhu Fangtao, Wang Quanbao, Xie Weicheng, Duan Dengping. Adjusting Accuracy of Digital Image Correlation Through Variable Subsets and Application in Airship Envelope [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 239-251.
[5]	XUE Yali, XU Xiayi, LI Jinyi, CUI Shan, HONG Jun, LIU Shihao. The Application and Development Prospects of Intelligent Control Technologies in Missile Guidance Systems [J]. Air & Space Defense, 2025, 8(2): 1-6.
[6]	BALASUBRAMANIAN S^1*, NARUKA Mahaveer Singh², TEWARI Gaurav³. Electrocardiogram Signal Denoising Using Optimized Adaptive Hybrid Filter with Empirical Wavelet Transform [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(1): 66-80.
[7]	LAO Wenjie, SHI Linjun, WU Feng, YANG Dongmei, LI Yang. Adaptive Frequency Regulation of Doubly-Fed Pumped Storage Unit Considering Speed and Power Limit [J]. Journal of Shanghai Jiao Tong University, 2025, 59(1): 28-37.
[8]	LIN Sen, WEN Shuli, ZHU Miao, DAI Qun, YAN Lun, ZHAO Yao, YE Huili. Optimal Allocation of Electric-Thermal Hybrid Energy Storage for Seaport Integrated Energy System Considering Carbon Trading Mechanism [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1344-1356.
[9]	LI Fen, SUN Ling, WANG Yawei, QU Aifang, MEI Nian, ZHAO Jinbin. Short-Term Interval Forecasting of Photovoltaic Power Based on CEEMDAN-GSA-LSTM and SVR [J]. Journal of Shanghai Jiao Tong University, 2024, 58(6): 806-818.
[10]	FU Wenxi, DOU Zhenlan, ZHANG Chunyan, WANG Lingling, JIANG Chuanwen, XIONG Zhan. Bi-Level Optimization Operation Method of Multi-H₂-IES Considering Dynamic Carbon Emission Factors [J]. Journal of Shanghai Jiao Tong University, 2024, 58(5): 610-623.
[11]	LIU Wenqian, SHAN Liang, ZHANG Weilong, LIU Chenglin, MA Qiang. Unmanned Aerial Vehicle Path Planning Algorithm Based on Improved Informed RRT^* in Complex Environment [J]. Journal of Shanghai Jiao Tong University, 2024, 58(4): 511-524.
[12]	GENG Zongsheng¹ (耿宗盛), ZHAO Dongdong^1,2 (赵东东), ZHOU Xingwen¹ (周兴文), YAN Lei¹ (闫磊), YAN Shi^1,2∗ (阎石). Leader-Following Consensus of Multi-Agent Systems via Fully Distributed Event-Based Control [J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 640-645.
[13]	LI Boqun, SUN Zhifeng. A Coronavirus Herd Immunity Optimizer Based on Swarm Division [J]. Journal of Shanghai Jiao Tong University, 2024, 58(4): 555-564.
[14]	WU Jiang, ZHANG Yan, LIU Zelong, CHENG Gang, LEI Dong, JIAO Chaoyong. State of Charge Estimation of Lithium-Ion Battery Considering Operating Conditions and Aging Degree [J]. Journal of Shanghai Jiao Tong University, 2024, 58(12): 1935-1945.
[15]	LIU Yu, WEN Liyan, JIANG Bin, MA Yajie, CUI Yukang. Adaptive Output Consensus of Heterogeneous Multi-Agent System with Switching Topology [J]. Journal of Shanghai Jiao Tong University, 2024, 58(11): 1805-1815.