RFID: Review & Comparison of Tree Based Tag Collision Resolution Algorithms

International Journal of Electronics and Communication Engineering

© 2015 by SSRG - IJECE Journal

Volume 2 Issue 3

Year of Publication : 2015

Authors : Shilpa Bhatt , Deepak Dhadwal and Ayush Bhatt

10.14445/23488549/IJECE-V2I3P116

How to Cite?

Shilpa Bhatt , Deepak Dhadwal and Ayush Bhatt, "RFID: Review & Comparison of Tree Based Tag Collision Resolution Algorithms," SSRG International Journal of Electronics and Communication Engineering, vol. 2,  no. 3, pp. 15-19, 2015. Crossref, https://doi.org/10.14445/23488549/IJECE-V2I3P116

Abstract:

In RFID, large number of tags communicates with small number of readers by simultaneous transmission. This situation leads to collisions for which several algorithms have been developed keeping in mind the goal of its avoidance. This being the major contributor of performance in a RFID system, it has attracted a lot of researchers for developing fast algorithms. Some of such widely used tree based algorithms includes binary search tree, back tracking based, and, matrix based algorithms are discussed, and, there MATLAB simulation is performed. Binary search algorithm uses NRZ encoding to find the collision bits and on its basis, it finds the least valued tag. In back track algorithm the process of finding the lease value tag is backtracked to find the next least value tag. In matrix based algorithm, the tags are divided into groups to reduce the chances of collision. All these algorithms are simulated using MATLAB, and, simulation results are compared and displayed using line graph.

Keywords:

Anti-Collision, Algorithm, RFID, Binary tree, Backtrack Binary Tree, Matrix

References:

[1] Mingsheng Hu, Zhijuan Jia, Xiaoyu Ji and Liu Hong, “RFID Anti-Collision Algorithm Based on Occurrence Position”, Research Journal of Applied Sciences, Engineering and Technology, vol. 5, pp. 23- 29, January 2013.
[2] Klaus Finkenzeller [2010]. “RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification”, 3rd edition, John Wiley & Sons.
[3] Haosong Gou, Younghwan Yoo, “Bit Collision Detection Based Query Tree Protocol For Anti Collision In RFID System”, International Journal of Innovation Computing, Information & Control , vol. 8, Number 5(A) , pp. 3081- 3102, May 2012. 
[4] Wang Jianfang, “A Novel Anti-collision Backtracking Algorithm Based on Binary-tree Search in UHF”, Proceedings of the Third International Symposium on Computer Science and Computational Technology, ISCSCT 2010, pp. 212-214, August 2010.
[5] Lvqing Yang, Caili Wang, Wenhua Zeng, “Research of Matrix-based Grouping Method on Anti-collision Algorithm for RFID Tag Identification”, Advances in information Sciences and Service Sciences (AISS), Volume5, Number13, pp. 126-123, August 2013.
[6] Usama S. MOHAMMED, Mostafa SALAH  , “Tag Anti-collision Algorithm for RFID Systems  with Minimum Overhead Information  in the Identification Process”, RADIOENGINEERING, VOL. 20, NO. 1, pp. 61-68 APRIL 2011.
[7] Geng Shu-qin, Wu Wu-chen, Hou Li-gang and Zhang Wang (2010). “Anti-Collision Algorithms for Multi-Tag RFID”, Radio Frequency Identification Fundamentals and Applications Bringing Research to Practice, Cristina Turcu (Ed.), ISBN: 978-953-7619-73-2,InTech, Available from: http://www.intechopen.com/books/radio-frequency-identification-fundamentals-and-applications-bringing-research-to-practice/anti-collision-algorithms-for-multi-tag-rfid
[8] X.-L. Shi, X.-W. Shi, Q.-L. Huang, and F. Wei, “An enhanced Binary Anti-Collision algorithm of backtracking in RFID System”, Progress In Electromagnetics Research B, Vol. 4, pp. 263–271, 2008.
[9] Jihoon Myung, Student Member, IEEE, Wonjun Lee, Senior Member, IEEE, and Jaideep Srivastava, Fellow, IEEE, “Adaptive Binary Splitting for Efficient RFID Tag Anti-Collision”, IEEE COMMUNICATIONS LETTERS, VOL. 10, NO. 3, pp 144-146, MARCH 2006.  
[10] Anchala Kumari, Rama Tripathi, Mita Pal and Soubhik Chakraborty, “Linear Search versus Binary Search:  A Statistical comparison for binomial inputs”, International Journal of Computer Science, Engineering and Applications (IJCSEA) Vol.2, No.2, pp. 29-39, April 2012.   
[11] Ankit R. Chadha, Rishikesh Misal, and Tanaya Mokashi, “Modified Binary Search Algorithm”, International Journal of Applied Information Systems (IJAIS) – ISSN : 2249-0868 Volume 7– No. 2, April 2014.
[12] Parveen Kumar, “Quadratic Search: A New and Fast Searching Algorithm (An extension of classical Binary search strategy)”, International Journal of Computer Applications (0975 – 8887), Volume 65– No.14, March 2013.
[13] Ajit Singh and Dr. Deepak Garg, “Implementation and Performance Analysis of Exponential Tree Sorting”, International Journal of Computer Applications (0975 – 8887), Volume 24– No.3, pp. 34-38, June 2011.
[14] http://www.slideshare.net/KALPNA06/rfid-presentation-37643386
[15] http://lbi.ro/teachinginnovatively/store/soft.php?soft=47
[16] http://wikipedia.unicefuganda.org/latest/A/Chemical%20kinetics.html