article

Two blocking algorithms on adaptive binary splitting: single and pair resolutions for RFID tag identification

Authors:

Yuan-Cheng Lai,

Chih-Chung LinAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 3

Pages 962 - 975

https://doi.org/10.1109/TNET.2008.2002558

Published: 01 June 2009 Publication History

Abstract

In radio frequency identification (RFID) systems, the reader identifies tags through communication over a shared wireless channel. When multiple tags transmit their IDs simultaneously, their signals collide, increasing the identification delay. Therefore, many previous anti-collision algorithms, including an adaptive query splitting algorithm (AQS) and an adaptive binary splitting algorithm (ABS), focused on solving this problem. This paper proposes two blocking algorithms, a single resolution blocking ABS algorithm (SRB) and a pair resolution blocking ABS algorithm (PRB), based on ABS. SRB not only inherits the essence of ABS which uses the information of recognized tags obtained from the last process of tag identification, but also adopts a blocking technique which prevents recognized tags from being collided by unrecognized tags. PRB further adopts a pair resolution technique which couples recognized tags and thus only needs half time for next identifying these recognized tags. We formally analyze the performance of SRB and PRB. Finally, the analytic and simulation results show that SRB slightly outperforms ABS and PRB significantly surpasses ABS.

References

[1]

S. Shepard, RFID: Radio Frequency Identification. New York: Mc-Graw-Hill, 2005, pp. 55-61.

[2]

Draft Protocol Specification for a 900 MHz Class 0 Radio Frequency Identification Tag, Auto-ID Center, 2003.

[3]

Information Technology--Radio Frequency Identification for Item Management--Part 6: Parameters for Air Interface Communications at 860 MHz to 960 MHz, ISO/IEC 18000-6(E), 2004.

[4]

W. C. Chen, S. J. Horng, and P. Fan, "An enhanced anti-collision algorithm in RFID based on counter and stack," in Proc. 2nd Int. Conf. Systems and Networks Communications, Aug. 2007, pp. 21-24.

Digital Library

[5]

860 MHz-930 MHz Class 1 Radio Frequency Identification Tag Radio Frequency and Logical Communication Interface Specification Candidate Recommendation Version 1.0.1 Auto-ID Center, 2002.

[6]

T. P. Wang, "Enhanced binary search with cut-through operation for anti-collision in RFID systems," IEEE Commun. Lett., vol. 10, pp. 236-238, Apr. 2006.

[7]

J. Ryu, H. Lee, Y. Seok, T. Kwon, and Y. Choi, "A hybrid query tree protocol for tag collision arbitration in RFID systems," in Proc. IEEE Int. Conf. Communications, Jun. 2007, pp. 5981-5986.

[8]

K. W. Chiang, C. Hua, and T. S. P. Yum, "Prefix-randomized query-tree protocol for RFID systems," in Proc. IEEE Int. Conf. Communications , Jun. 2006, pp. 1653-1657.

[9]

J. H. Choi, D. Lee, and H. Lee, "Bi-slotted tree based anticollision protocols for fast tag identification in RFID systems," IEEE Commun. Lett., vol. 10, pp. 861-863, Dec. 2006.

[10]

J. I. Capetanakis, "Tree algorithms for packet broadcast channels," IEEE Trans. Inf. Theory, vol. 25, pp. 505-515, Sep. 1979.

Digital Library

[11]

J. Mosely and P. Humblet, "A class of efficient contention resolution algorithms for multiple access channels," IEEE Trans. Commun., vol. 33, no. 2, pp. 145-151, Feb. 1985.

[12]

EPC™ Radio-Frequency Identity Protocols Class 1 Generation-2 UHF RFID Protocol for Communications at 860-960 MHz Version 1.0.9, EPC Global Inc., 2005.

[13]

Information Technology--Radio Frequency Identification for Item Management--Part 6: Parameters for Air Interface Communications at 860 MHz to 960 MHz, Amendment 1: Extension With Type C and Update of Types A and B, ISO/IEC 18000-6:2004/Amd. 1:(E), Jun. 2006.

[14]

H. Vogt, "Efficient object identification with passive RFID tags," in Lecture Notes in Computer Science, Vol. 2414. Berlin/Heidelberg, Germany: Springer, 2002.

Digital Library

[15]

J. R. Cha and J. H. Kim, "Dynamic framed slotted Aloha algorithms using fast tag estimation method for RFID system," in Proc. 3rd Consumer Communications and Networking Conf., Jan. 2006, pp. 768-772.

[16]

S. R. Lee, S. D. Joo, and C. W. Lee, "An enhanced dynamic framed slotted Aloha algorithm for RFID tag identification," in Proc. 2nd Annu. Int. Conf. Mobile and Ubiquitous Systems: Networking and Services, Jul. 2005, pp. 166-172.

Digital Library

[17]

M. A. Bonuccelli, F. Lonetti, and F. Martelli, "Tree slotted Aloha: A new protocol for tag identification in RFID networks," presented at the Int. Symp. World of Wireless, Mobile and Multimedia Networks (WOWMOM 2006), Buffalo, NY, Jun. 2006.

Digital Library

[18]

J. Park, M. Y. Chung, and T. J. Lee, "Identification of RFID tags in framed-slotted Aloha with robust estimation and binary selection," IEEE Commun. Lett., vol. 11, pp. 452-454, May 2007.

[19]

Q. Peng, M. Zhang, and W. Wu, "Variant enhanced dynamic frame slotted Aloha algorithm for fast object identification in RFID system," in Proc. IEEE Int. Workshop on Anti-Counterfeiting, Security, Identification , Apr. 2007, pp. 88-91.

[20]

F. Schoute, "Dynamic frame length Aloha," IEEE Trans. Commun., vol. 31, no. 4, pp. 565-568, Apr. 1983.

[21]

J. E. Wieselthier, A. Ephremides, and L. A. Michaels, "An exact analysis and performance evaluation of framed Aloha with capture," IEEE Trans. Commun., vol. 37, no. 2, pp. 125-137, Feb. 1989.

[22]

J. Myung, W. Lee, and J. Srivastava, "Adaptive binary splitting for efficient RFID tag anti-collision," IEEE Commun. Lett., vol. 10, pp. 144-146, Mar. 2006.

[23]

J. Myung, W. Lee, and T. K. Shih, "An adaptive memoryless protocol for RFID tag collision arbitration," IEEE Trans. Multimedia, vol. 8, pp. 1096-1101, Oct. 2006.

Digital Library

[24]

J. Myung, W. Lee, J. Srivastava, and T. K. Shih, "Tag-splitting: Adaptive collision arbitration protocols for RFID tag identification," IEEE Trans. Parallel Distrib. Syst., vol. 18, no. 6, pp. 763-775, Jun. 2007.

Digital Library

[25]

J. Eom and T. J. Lee, "Framed-slotted Aloha with estimation by pilot frame and identification by binary selection for RFID anti-collision," in Proc. Int. Symp. Communications and Information Technologies, Oct. 2007, pp. 1027-1031.

[26]

F. Zhou, D. Jin, C. Huang, and M. Hao, "Optimize the power consumption of passive electronic tags for anti-collision schemes," in Proc. 5th Int. Conf. ASIC, Oct. 2003, vol. 2, pp. 1213-1217.

[27]

J. H. Choi, D. Lee, Y. Youn, H. Jeon, and H. Lee, "Scanning-based pre-processing for enhanced tag anti-collision protocols," in Proc. Int. Symp. Communications and Information Technologies, Sep. 2006, pp. 1207-1211.

Cited By

Zhu WGong JLi MCao JHe ZXie R(2023)Multiple Resolution Bit Tracking for Continuous Reliable RFID Tag IdentificationIEEE Transactions on Mobile Computing10.1109/TMC.2022.318728922:10(6071-6085)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3187289
Yihong CQuanyuan F(2019)A Collision Avoidance Identification Algorithm for Mobile RFID DeviceIEEE Transactions on Consumer Electronics10.1109/TCE.2019.293915965:4(493-501)Online publication date: 23-Oct-2019
https://dl.acm.org/doi/10.1109/TCE.2019.2939159
Jayadi RLai YLin C(2019)Efficient time-oriented anti-collision protocol for RFID tag identificationComputer Communications10.1016/j.comcom.2017.08.016112:C(141-153)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.comcom.2017.08.016
Show More Cited By

Index Terms

Two blocking algorithms on adaptive binary splitting: single and pair resolutions for RFID tag identification

Recommendations

Adaptive binary splitting: a RFID tag collision arbitration protocol for tag identification

In the RFID system, a reader recognizes tags through communications over a shared wireless channel. When multiple tags transmit their IDs at the same time, the tag-to-reader signals lead to collision. Tag collision arbitration for passive RFID tags is ...
Adaptive splitting protocols for RFID tag collision arbitration
MobiHoc '06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing

Tag identification is an important tool in RFID systems with applications for monitoring and tracking. A RFID reader recognizes tags through communication over a shared wireless channel. When multiple tags simultaneously transmit their IDs to a reader, ...
A novel protocol of RFID tag identification using a single mobile reader

Classic RFID tag anti-collision protocols mainly aim at the identification of tags in small area. That is, all unidentified tags are located in the reader's read-write region. When there is one or more tag outside the reader coverage area, multi-reader ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 3

June 2009

329 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 June 2009

Revised: 01 May 2008

Received: 03 January 2008

Published in TON Volume 17, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
322
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu WGong JLi MCao JHe ZXie R(2023)Multiple Resolution Bit Tracking for Continuous Reliable RFID Tag IdentificationIEEE Transactions on Mobile Computing10.1109/TMC.2022.318728922:10(6071-6085)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3187289
Yihong CQuanyuan F(2019)A Collision Avoidance Identification Algorithm for Mobile RFID DeviceIEEE Transactions on Consumer Electronics10.1109/TCE.2019.293915965:4(493-501)Online publication date: 23-Oct-2019
https://dl.acm.org/doi/10.1109/TCE.2019.2939159
Jayadi RLai YLin C(2019)Efficient time-oriented anti-collision protocol for RFID tag identificationComputer Communications10.1016/j.comcom.2017.08.016112:C(141-153)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.comcom.2017.08.016
Choi HKim HChoi S(2017)Capture-Aware Couple-Resolution Blocking Protocol in RFID SystemsWireless Personal Communications: An International Journal10.1007/s11277-016-3940-293:4(969-986)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s11277-016-3940-2
Qing YJiancheng LHongyi W(2016)A collecting collision tree protocol for RFID tag identification with capture effectInternational Journal of Distributed Sensor Networks10.1155/2015/6732532015(193-193)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1155/2015/673253
Tsai SHu YChai CLi J(2016)Efficient tag reading protocol for large-scale RFID systems with pre-readingComputer Communications10.1016/j.comcom.2016.04.01988:C(73-83)Online publication date: 15-Aug-2016
https://dl.acm.org/doi/10.1016/j.comcom.2016.04.019
Lai YHsiao LLin B(2015)Optimal slot assignment for binary tracking tree protocol in RFID tag identificationIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2013.229583923:1(255-268)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TNET.2013.2295839
Yeh KLo NTsai KLi YWinata E(2014)A Novel RFID Tag Identification ProtocolWireless Personal Communications: An International Journal10.1007/s11277-014-1608-377:3(1775-1800)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/s11277-014-1608-3
Lai YHsiao LLin B(2013)An RFID anti-collision algorithm with dynamic condensation and ordering binary treeComputer Communications10.5555/2745552.274568436:17(1754-1767)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.5555/2745552.2745684

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents