Parallel Response Ternary Query Tree for RFID Tag Anti-Collision

Ching-Nung Yang, Song-Ruei Cai, Li-Zhe Sun

Department of Computer Science and Information Engineering, National Dong Hwa University, Hualien.

DOI: 10.4236/jcc.2015.35009                

Abstract

A tag-collision (or missed reads) in RFID system (Radio Frequency Identification) system degrades the identification efficiency. The so-called tag collision is that a reader cannot identify a tag when more than one tags respond to a reader at the same time. There are some major anti-collision protocols on resolving tag collision, e.g., ALOHA-based protocol, binary tree protocol, and Query Tree (QT) protocol. Up to date, most tag anti-collision protocols are QT protocols. QT protocols are categorized into M-ary query tree (QT). In the previous literature, choosing M = 3 (i.e., a ternary QT (TQT)) was proven to have the optimum performance for tag identification. Recently, Yeh et al. used parallel response approach to reduce the number of collisions. In this paper, we combine the partial response and TQT to propose an effective parallel response TQT (PRTQT) protocol. Simulation results reveal that our PRTQT outperforms Yeh et al.’s protocol and TQT protocol.

Keywords

Radio Frequency Identification (RFID), Tag Collision, Query Tree, Ternary Tree, Parallel Response

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Finkenzeller, K. (2000) RFID Handbook: Radio Frequency Identification Fundamentals and Applications. John Wiley & Sons.
[2]	Yang, C.N., He, J.Y. and Kun, Y.C. (2012) RFID Tag Anti-Collision Protocols. Chapter 7 in the book Advanced RFID Systems, Security, and Applications, IGI Global.
[3]	Sarma, S., Weis, S. and Engels, D. (2003) RFID Systems and Security and Privacy Implications. LNCS, 2523, 454-470. http://dx.doi.org/10.1007/3-540-36400-5_33
[4]	Lee, S.R., Joo, S.D. and Lee, C.W. (2005) An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification. Proceedings of MobiQuitous 2005, Jul., 166-172.
[5]	Zhou, F., Jin, D., Huang, C. and Hao, M. (2003) Optimize the Power Consumption of Passive Electronic Tags for Anti- Collision Schemes. Proceedings of the 5th International Conference on ASIC (ASIC 03), Oct., 1213-1217.
[6]	Feng, B., Li, J.T., Guo, J.B. and Ding, Z.H. (2006) Id-Binary Tree Stack Anti-Collision Algorithm for RFID. Proceedings of 11th IEEE Symposium on Computers and Communications (ISCC 06), Jun., 207-212. http://dx.doi.org/10.1109/ISCC.2006.86
[7]	Myung, J. and Lee, W. (2005) Adaptive Binary Splitting: A RFID Tag Collision Arbitration Protocol for Tag Identification. Proceedings of 2nd International Conference on Broadband Networks (BroadNets 05), Oct., 347-355.
[8]	Cui, Y. and Zhao, Y. (2008) Mathematical Analysis for Binary Tree Algorithm in RFID. Proceedings of 67th IEEE Vehicular Technology Conference (VTC 08), May, 2725-2729. http://dx.doi.org/10.1109/VETECS.2008.596
[9]	Hsu, C.H., Yu, C.H. and Huang, Y.P. (2008) An Enhanced Query Tree (EQT) Protocol for Memoryless Tag Anti- Collision in RFID System. Proceedings of 2nd International Conference on Future Generation Communication and Networking (FGCN 08), Dec., 427-432. http://dx.doi.org/10.1109/FGCN.2008.224
[10]	Pupunwiwat, P. and Stantic, B. (2009) Unified q-ary Tree for RFID Tag Anti-Collision Resolution. Proceedings of 20th Australasian Database Conference (ADC 09), Mar., 49-58.
[11]	Yang, C.N. and He, J.Y. (2011) An Effective 16-bit Random Number Aided Query Tree Algorithm for RFID Tag Anti- Collision. IEEE Communications Letters, 15, 539-541. http://dx.doi.org/10.1109/LCOMM.2011.031411.110213
[12]	Yang, C.N., Hu, L.J. and Lai, J.B. (2012) Query Tree Algorithm for RFID Tag with Binary-Coded Decimal EPC. IEEE Communications Letters, 16, 1616-1619. http://dx.doi.org/10.1109/LCOMM.2012.090312.121213
[13]	Mathys, P. and Flajolet, P. (1985) Q-ary Collision Resolution Algorithms in Random-access Systems with Free or Blocked Channel Access. IEEE Transactions on Information Theory, 31, 217-243. http://dx.doi.org/10.1109/TIT.1985.1057013
[14]	Yang, C.N., He, Y.C. and Wu, C.C. (2010) A Practical Implementation of Ternary Query Tree for RFID Tag Anti- Collision. Proceedings of 2010 IEEE International Conference on Information Theory and Information Security, Dec., 283-286. http://dx.doi.org/10.1109/ICITIS.2010.5689460
[15]	Yeh, M.K., Jiang, J.R. and Huang, S.T. (2011) Parallel Response Query Tree Splitting for RFID Tag Anti-Collision. Proceedings of 40th International Conference on Parallel Processing Workshops, Sep., 6-15.
[16]	Draft Protocol Specification for a 900 MHz Class 0 Radio Frequency Identification Tag, MIT Auto-ID Center, Feb. 2003.
[17]	Pupunwiwat, P. and Stantic, B. (2009) Unified q-ary Tree for RFID Tag Anticollision Resolution. Proceedings of Australasian Database Conference, 49-58.