An Investigation on Tree-Based Tags Anti-Collision Algorithms in RFID

Xiaohao, Su; Baolong, Liu

doi:10.21307/iccnea.2017.19

Abstract

The tree-based tags anti-collision algorithm is an important method in the anti-collision algorithms. In this paper, several typical tree algorithms are evaluated. The comparison of algorithms is summarized including time complexity, communication complexity and recognition, and the characteristics and disadvantages of each algorithm are pointed out. Finally, the improvement strategies of tree anti-collision algorithm are proposed, and the future research directions are also prospected.

References

Yuan-Cheng Lai , Ling-Yen Hsiao, Bor-Shen Lin. An RFID anti-collision algorithm with dynamic condensation and ordering binary tree[J].Computer Communications,2013,36:1754-176710.1016/j.comcom.2013.09.001
Search in Google Scholar Back to article
Xin-Qing Yan , Yang Liu , Bin Li, et.al. A memoryless binary query tree based Successive Scheme for passive RFID tag collision resolution[J].Information Fusion,2015,22:26-3810.1016/j.inffus.2013.08.006
Search in Google Scholar Back to article
Filippo Gandino,Renato Ferrero,Bartolomeo Montrucchio,et al.Probabilistic DCS:An RFID reader-to-reader anti-collision protocal[J].Journal of Network and Computer Applications,2011,34:821-832.10.1016/j.jnca.2010.04.007
Search in Google Scholar Back to article
Wu Nan. Research on RFID anti-collision algorithm based on a tree structure [D]. Changchun: Jilin University, 2014
Search in Google Scholar Back to article
Yue Keqiang.RFID multi tag anti-collision algorithm research and application [D]. Hangzhou: Zhejiang University, 2014
Search in Google Scholar Back to article
Overview of multi-tag anti-collision algorithms in RFID[J]. Computer Integrated Manufacturing Systems, 2014,20 (2): 440-451.
Search in Google Scholar Back to article
Haidar Safa,Wassim El-Hajj,Christine Meguerditchian. A distributed multi-channel reader anti-collision algorithm for RFID environments[J].Computer Communications,2015,64:44-56.10.1016/j.comcom.2015.01.013
Search in Google Scholar Back to article
Yuan-Cheng Lai , Ling-Yen Hsiao, Bor-Shen Lin. An RFID anti-collision algorithm with dynamic condensation and ordering binary tree[J].Computer Communications,2013,36:1754-1767.10.1016/j.comcom.2013.09.001
Search in Google Scholar Back to article
Journal of Xidian University (Natural Science Edition), 2013,40 (6): 162-167 .Research on Adaptive Anti-collision Algorithm Based on Adaptive Multidimensional Dimensional Isolation [J]. Journal of Xidian University (Natural Science Edition), 2013,40 (6): 162-167.
Search in Google Scholar Back to article
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.10.1109/SURV.2010.031810.00037
Search in Google Scholar Back to article
Wang Yu .Research on RFID anti-collision algorithm [D]. Nanjing: Nanjing University of Posts and Telecommunications, 2011.
Search in Google Scholar Back to article
Jia Xiaolin. Research on Anti-collision Algorithm Based on collision tree for RFID multi label recognition [D]. Chengdu: Southwest Jiao Tong University, 2013.
Search in Google Scholar Back to article
J.Myung,W.Lee,J,Srivastava,et al.Tag-splitting:adaptive collision arbitration protocols for RFID tag identification[J].IEEE Transactions on Parallel and Distributed System,2007,18(6):763-775.10.1109/TPDS.2007.1020
Search in Google Scholar Back to article
Mingxing He,Shi-Jinn Horng,Pingzhi Fan,et al.A fast RFID tag identification algorithm based on counter and stack[J].Expert System with Application,2011,38:6829-6838.10.1016/j.eswa.2010.12.056
Search in Google Scholar Back to article
Jiang An, WU Jixiong, Huang Shengye, et al. Improved RFID binary search anti-collision algorithm [J]. Computer Engineering and Applications, 2009,45 (5): 229-235.
Search in Google Scholar Back to article
Chen Feiyu.Improvement of Anti-collision Algorithm Based on Dynamic Binary [D]. Shanghai: Shanghai Jiaotong University, 2013.
Search in Google Scholar Back to article
[17]Sarkar S, Kak AC, Rama GM. Metrics for measuring the quality of modularization of large-scale object- oriented software. IEEE Trans. on Software Engineering, 2008,34(5):700-720.10.1109/TSE.2008.43
Back to article
Mustapha Djeddou,Rafik Khelladi,Mustapha Benssalah.Improved RFID anti-collision algorithm[J]. International Journal of Electronics and Communications(AEÜ) ,2013,67:256-262.10.1016/j.aeue.2012.08.009
Search in Google Scholar Back to article
Chen Chong, XU Zhi, HE Minghua.Study on a New RFID Anti-collision Algorithm [J]. Journal of Fuzhou University, 2009,37 (3): 367-371.
Search in Google Scholar Back to article
Li Qingqing.Research on RFID anti-collision algorithm [D]. Nanchang: Nanchang Aviation University, 2012.
Search in Google Scholar Back to article
Di Chunyu.Research on RFID Anti-collision Algorithm Based on Search Tree [J]; Changchun: Jilin University; 2014.
Search in Google Scholar Back to article
Wang Xue, Qian Zhi-hong, HU Zhengchao, et al.Study on RFID anti-collision algorithm based on binary tree [J] .Journal of Communications, 2010,31 (6): 49-56.
Search in Google Scholar Back to article
Liu Xiao-hui.Study on RFID anti-collision algorithm based on binary number [D]. Changchun: Jilin University, 2015.
Search in Google Scholar Back to article
Shuen -Chih Tsai,Yu-Min Hu,Chen-Hsun Chai et al.Efficient tag reading protocol for large-scale RFID systems with pre-reading[J]. Computer Communications,2016,88:73-83.10.1016/j.comcom.2016.04.019
Search in Google Scholar Back to article
Zhang Bo. Research on Anti-collision Technology of CFD [D]. Shanghai: Donghua University, 2010.
Search in Google Scholar Back to article
Yang,C N,Lin C C.Two couple-resolution blocking protocols on adaptive query splitting for RFID tag identification[J].IEEE Transactions on Mobile Computing,2012,11( 10) :1450 — 1463.10.1109/TMC.2011.171
Search in Google Scholar Back to article
Jiao Chuan-hai,Wang Ke-ren.Multi-branch query tree protocol for solving RFID tag collision problem[J].The Journal of China University of Posts and Telecommunications,2008,15(4):51-54.10.1016/S1005-8885(08)60402-1
Search in Google Scholar Back to article
Jiang Wu, Yang Heng-xin, Zhang Yun.An improved Anti-collision Algorithm for Query Tag RFID Tag [J]. Computer Technology and Development, 2015,25 (2): 86-89.
Search in Google Scholar Back to article
Zhou Qing, Cai Ming.Improved RFID Hybrid Query Tree Anti-collision Algorithm [J]. Computer Engineering and Design, 2012,33 (1): 209-213.
Search in Google Scholar Back to article
Jia Xiaolin,Feng Quanyuan,Lei Quanshui.Multi-cycle Collision Tree Algorithm for RFID Tag Identification[J]. Journal of Southwest University of Science and Technology, 2014,29 (1), 39-44.
Search in Google Scholar Back to article
Jian Su,Zhengguo Sheng,Guangjun Wen.A Time Ffficient Tag Identification Algorithm Using Dual Prefix Probe Scheme(DPPS)[J].IEEE Signal Processing Letters,2016,23(3):386-389.10.1109/LSP.2016.2516768
Search in Google Scholar Back to article
He Na.Study on anti-collision algorithm in radio frequency identification system and its hardware implementation [D]. Guangzhou: Jinan University, 2007.
Search in Google Scholar Back to article
Klaus Finkenzeller,RFID Handbook[M].Hanser Verlag,Munich,March 2003.10.1002/0470868023
Search in Google Scholar Back to article
Shi Hao. A Hybrid RFID Anti-collision Algorithm [D]. Nanjing: Nanjing University of Posts and Telecommunications, 2012.
Search in Google Scholar Back to article
Jia Xiao-Lin,Feng Quan-yuan,Ma Cheng-zhen.An efficient anti-collision protocal for RFID tag identification[J].IEEE Communication Letters,2010,14(11):1014-1016.10.1109/LCOMM.2010.091710.100793
Search in Google Scholar Back to article
Jia Xiao-Lin,Feng Quan-yuan, Yu Li-shan.Stability analysis of an efficient anti-collision protocol for RFID tag identification[J].IEEE Transactions on Communications.2012,60(8):2285-2294.10.1109/TCOMM.2012.051512.110448
Search in Google Scholar Back to article
Hu Zhenchao.Study on RFID anti-collision algorithm based on binary tree [D]. Changchun: Jilin University, 2009.
Search in Google Scholar Back to article
Zhang Li, Yuan Meng-Meng, He Xing.Study on Dynamic Adjustable Algorithm for Multi-collision Bit Joint Lock Position [J] .Journal of Electronics Measurement and Instrumentation, 27 (8): 773-779.
Search in Google Scholar Back to article
Ding Zhi-guo, Zhu Xue-yong, Guo Li, et al.Study on adaptive multi-tree anti-collision algorithm [J] .2010,36 (2): 237-241.10.3724/SP.J.1004.2010.00237
Search in Google Scholar Back to article
Zhang Xue-jun, Cai Wen-qi, et al.Study on Improved Adaptive Multi-tree Anti-collision Algorithm [J]. Journal of Electronics, 2012,40 (1): 193-198.
Search in Google Scholar Back to article
Ren Shao-jie, Hao Yong-sheng, et al.A New self-adjusting multi-tree anti-collision algorithm [J]. Computer Measurement and Control, 2015,23 (12): 4180-4183.
Search in Google Scholar Back to article
Wang Xin,Jia Qing Xuan,Gao Xin, et al.Research on Grouping N-ray Tracking Tree RFID Anti-collision Algorithm[J]. Journal of Electronics,2016,44(2):437-444.
Search in Google Scholar Back to article
Pan L,Wu H.Smart Trend-Traversal:A Low Delay and Energy Tag Arbitration Protocal for Large RFID System[C].In Proceedings of 28th Annual Joint Conference of the IEEE Computer and Communications. Rio de Janeiro,Brazil,2009:2571-2575.10.1109/INFCOM.2009.5062189
Search in Google Scholar Back to article
Shuen-Chih Tsai,Yu-Min Hu,Chen-Hsun Chai,et al.Efficient tag reading protocol for large-scale RFID systems with pre-reading[J].Computer Communications,2016,88:73-8310.1016/j.comcom.2016.04.019
Search in Google Scholar Back to article
Tang Zhijun,Yang Yi,Wu Xiaofeng, et al.Novel Back-off Binary Tree Anti-Collision Algorithm for Ultra High Frequency RFID[J]. Computer science and exploration, 2016,10 (5): 612-621.
Search in Google Scholar Back to article

An Investigation on Tree-Based Tags Anti-Collision Algorithms in RFID

Abstract

Paradigm

My account