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]	Liu Ziyan, Jiang Zuhua. Hybrid Meta-Heuristic Algorithm for a Pickup and Delivery Problem of Ship Outfitting Pallets Distribution Considering Carbon Emissions [J]. J Shanghai Jiaotong Univ Sci, 2026, 31(2): 440-457.
[2]	WU Yonghua, MEI Ying, LU Chengbo. Concept Drift Data Stream Classification Algorithm Based on Incremental Weighting [J]. Journal of Shanghai Jiao Tong University, 2026, 60(1): 112-122.
[3]	SONG Zihao, WEI Handi, XIAO Longfei, et al. Straight-Line Trajectory Tracking Control of Surface-Towed Vehicles under Complex Disturbances [J]. Ocean Engineering Equipment and Technology, 2026, 13(1): 34-45.
[4]	LIU Qi, HE Yifei, GU Ming, CHEN Zihao, LI Yunhao, WANG Tao. Density Cluster-Based Clutter Removal Technology for Millimeter-Wave Radar Target Point Cloud [J]. Air & Space Defense, 2026, 9(1): 63-72.
[5]	Liu Qunpo, Li Jiakun, Fei Shumin, Bo Xuhui, Naohiko Hanajima. Design of Composite Two-Channel Disturbance Estimation Adaptive Controller for Backlash-Like Hysteretic Nonlinear Systems [J]. J Shanghai Jiaotong Univ Sci, 2026, 31(1): 106-116.
[6]	Li Guolin, Chen Tong, He Shaoying, Yin Debin. Input Mapping-Based Model Predictive Control with Event-Triggered Adaptive Strategy for Rigid-Soft Hybrid Manipulator [J]. J Shanghai Jiaotong Univ Sci, 2026, 31(1): 36-47.
[7]	WAN Yuan, MAO Xuchu. Comprehensive Analysis of Beidou-3 PPP-B2b Performance Based on Adaptive Robust Extend Kalman Filter [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(6): 1208-1219.
[8]	WANG Yuyang, ZHANG Chen, ZHANG Yu, WANG Yiming, XU Po, CAI Xu. Reactive Power-Voltage Droop Gain Online Tuning Method of Photovoltaic Inverters for Improvement of Stable Output Power Capability in Weak Grids [J]. Journal of Shanghai Jiao Tong University, 2025, 59(6): 845-856.
[9]	MA Changxi, HUANG Xiaoting, MENG Wei. Predicting Parking Spaces Using CEEMDAN and GRU [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(5): 962-975.
[10]	DING Leqi, WANG Biyun, YAO Lixiu, CAI Yunze. MAGPNet: Multi-Domain Attention-Guided Pyramid Network for Infrared Small Object Detection [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(5): 935-951.
[11]	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.
[12]	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.
[13]	MIAO Yuheng, LI Rufei, E Bin, WANG Xiaogang, CUI Naigang. Glide Trajectory Optimization for Hypersonic Vehicles Based on Adaptive Chebyshev Pseudo-Spectral Method [J]. Air & Space Defense, 2025, 8(3): 123-131.
[14]	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.
[15]	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.