Radio Frequency Identification: Analysis of Tag Collision using Tree Algorithms

  IJETT-book-cover  International Journal of Engineering Trends and Technology (IJETT)          
© 2016 by IJETT Journal
Volume-36 Number-4
Year of Publication : 2016
Authors : Harsha Kosta


Harsha Kosta"Radio Frequency Identification: Analysis of Tag Collision using Tree Algorithms", International Journal of Engineering Trends and Technology (IJETT), V36(4),203-207 June 2016. ISSN:2231-5381. published by seventh sense research group

Radio Frequency Identification (RFID), uses electromagnetic fields to automatically identify and track tags attached to objects. The tags contain electronically stored information. Passive tags collect energy from a nearby RFID reader's interrogating radio waves. Active tags have a local power source such as a battery and may operate at hundreds of meters from the RFID reader. In these case, often more than one tag will respond to a tag reader, for example, many individual products with tags may be shipped in a common box or on a common pallet. Collision detection is important to allow reading of data. Collision detection is essential to read the data of individual tags accurately. This being the major contributor of performance in RFIDsystem, it has attracted a lot of researchers for developing fast algorithms. Binary search tree, back tracking based, and, matrix based algorithms are Some of the other widely used tree based algorithms discussed. A MATLAB simulation is performed for these tree based algorithms. NRZ encoding is used by binary search algorithm to find the collision bits and on its basis as it searches for the least valued tag. The procedure of searching for the least value tag is backtracked to search for the next least value tag in back track algorithm. The tags are further made into groups to decrease the likelihoods of collision in matrix based algorithm. All these algorithms are simulated using MATLAB, and, simulation results are compared and displayed using line graph.


[1] Mingsheng Hu, ZhijuanJia,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 (RFID) Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification”, 3rd edition, John Wiley & Sons.
[3]Haosong Gou, YounghwanYoo, “Bit Collision Detection Based Query Tree Protocol For Anti Collision In RFID (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 (RFID) Tag Identification”, Advances in information Sciences and Service Sciences (AISS), Volume5, Number13, pp. 126123, August 2013.
[6] Usama S. MOHAMMED, Mostafa SALAH , “Tag Anti-collision Algorithm for RFID (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 (RFID)”, RFID Fundamentals and Applications Bringing Research to Practice, Cristina Turcu (Ed.), ISBN: 978953-7619-73-2,InTech, Available from: and-applications-bringing-researchto-practice/anti-collisionalgorithms- for-multi-tag-RFID (RFID)
[8] X.-L. Shi, X.-W. Shi, Q.-L. Huang, and F. Wei, “An enhanced Binary Anti-Collision algorithm of backtracking in RFID (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 RFIDTag Anti-Collision”, IEEE COMMUNICATIONS LETTERS, VOL. 10, NO. 3, pp 144-146, MARCH 2006.
[10] AnchalaKumari, Rama Tripathi, Mita Pal and SoubhikChakraborty, “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, RishikeshMisal, and TanayaMokashi, “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] RFID (RFID)- presentation37643386
[16] etics.html
[17] Spoorthi M, Srilekha K, Sanjana J, Kushal Kumar B N “Automatic Educational Document Classification using Natural Language Processing”, International Journal of Engineering Trends and Technology (2231-5381), Volume 35- No. 4, May 2016.

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