Bi-slotted Binary Tree Algorithm with Stack for Radio Frequency Identification Tag Anti-Collision

doi:10.1007/s12204-013-1380-7

上海交通大学学报（英文版） ›› 2013, Vol. 18 ›› Issue (2): 173-179.doi: 10.1007/s12204-013-1380-7

Bi-slotted Binary Tree Algorithm with Stack for Radio Frequency Identification Tag Anti-Collision

TIAN Yuna* (田芸), CHEN Gong-lianga (陈恭亮), LI Jian-huaa,b (李建华)

(a. School of Information Security Engineering; b. Department of Electronic Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

出版日期:2013-04-30 发布日期:2013-05-10
通讯作者: TIAN Yuna (田芸) E-mail:ruth_tian@sjtu.edu.cn

Bi-slotted Binary Tree Algorithm with Stack for Radio Frequency Identification Tag Anti-Collision

TIAN Yuna* (田芸), CHEN Gong-lianga (陈恭亮), LI Jian-huaa,b (李建华)

(a. School of Information Security Engineering; b. Department of Electronic Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

Online:2013-04-30 Published:2013-05-10
Contact: TIAN Yuna (田芸) E-mail:ruth_tian@sjtu.edu.cn

摘要/Abstract

摘要： A radio frequency identification (RFID) reader will fail to identify tags if a collision occurs. This paper proposes a bi-slotted binary tree algorithm (BSBTA) with stack for RFID tag anti-collision to improve the performance of binary tree algorithm (BTA). In BSBTA, the reader detects collisions by Manchester code and stores colliding prefixes in a stack. The query is composed of a two-bit prefix and an index value. Following every reader query, there are two timeslots for tags whose pointers and identities (IDs) match the query to respond, one for the tag whose next bit is 0 and the other for the tag with 1 as its next bit. Performance analysis and evaluation are also given. The time complexity and the communication complexity of BTA and BSBTA are derived. The simulation results compare the performance of BSBTA with several related anti-collision algorithms. It is shown that BSBTA outperforms BTA in terms of the average number of responded bits and timeslots for one tag identification.

关键词: radio frequency identification (RFID), anti-collision, binary tree, tag identification

Abstract: A radio frequency identification (RFID) reader will fail to identify tags if a collision occurs. This paper proposes a bi-slotted binary tree algorithm (BSBTA) with stack for RFID tag anti-collision to improve the performance of binary tree algorithm (BTA). In BSBTA, the reader detects collisions by Manchester code and stores colliding prefixes in a stack. The query is composed of a two-bit prefix and an index value. Following every reader query, there are two timeslots for tags whose pointers and identities (IDs) match the query to respond, one for the tag whose next bit is 0 and the other for the tag with 1 as its next bit. Performance analysis and evaluation are also given. The time complexity and the communication complexity of BTA and BSBTA are derived. The simulation results compare the performance of BSBTA with several related anti-collision algorithms. It is shown that BSBTA outperforms BTA in terms of the average number of responded bits and timeslots for one tag identification.

Key words: radio frequency identification (RFID), anti-collision, binary tree, tag identification

中图分类号:

TN 92

TIAN Yuna* (田芸), CHEN Gong-lianga (陈恭亮), LI Jian-huaa,b (李建华). Bi-slotted Binary Tree Algorithm with Stack for Radio Frequency Identification Tag Anti-Collision[J]. 上海交通大学学报（英文版）, 2013, 18(2): 173-179.

TIAN Yuna* (田芸), CHEN Gong-lianga (陈恭亮), LI Jian-huaa,b (李建华). Bi-slotted Binary Tree Algorithm with Stack for Radio Frequency Identification Tag Anti-Collision[J]. Journal of shanghai Jiaotong University (Science), 2013, 18(2): 173-179.

参考文献

[1] Zhen B, Kobayashi M, Shimizu M. Framed ALOHA for multiple RFID objects identification [J]. IEICE Transactions on Communications, 2005, E88-B(3): 991-999.
[2] Zhu L, Yum T S P. The optimal reading strategy for EPC gen-2 RFID anti-collision systems [J]. IEEE Transactions on Communications, 2010, 58(9): 2725-2733.
[3] Zhou F, Jin D, Huang C, et al. Optimize the power consumption of passive electronic tags for anti-collision schemes [C]//Proceedings of 5th International Conference on ASIC. Piscataway, NJ, USA: IEEE, 2003: 1212-1217
[4] Zhou F, Chen C, Jin D, et al. Evaluating and optimizing power consumption of anti-collision protocols for applications in RFID systems [C]//Proceedings of International Symposium on Low Power Electronics and Design. New York, NY, USA: ACM, 2004: 357-362.
[5] Law C, Lee K, Siu K Y. Efficient memoryless protocol for tag identification [C]//Proceedings of 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. New York, NY, USA: ACM, 2000: 75-84.
[6] Jia X, Feng Q, Ma C. An efficient anti-collision protocol for RFID tag identification [J]. IEEE Communications Letters, 2010, 14(11): 1014-1016.
[7] Yang C N, He J Y. An effective 16-bit random number aided query tree algorithm for RFID tag anti-collision [J]. IEEE Communications Letters, 2011, 15(5): 539-541.
[8] Choi J H, Lee D, Lee H. Bi-slotted tree based anti-collision protocols for fast tag identification in RFID systems [J]. IEEE Communications Letters, 2006, 10(12): 861-863.
[9] Zhu L, Yum T S P. A critical survey and analysis of RFID anti-collision mechanisms [J]. IEEE Communications Magazine, 2011, 59(5): 214-221.
[10] Klair D K, Chin K W, Raad R. A survey and tutorial of RFID anti-collision protocols [J]. IEEE Communications Surveys & Tutorials, 2010, 12(3): 400-421.
[11] Choi S Y, Lee J, Kim S H, et al. Hybrid anti-collision method based on maximum throughput for RFID system [J]. Electronics Letters, 2010, 46(19): 1346-1348.

Bi-slotted Binary Tree Algorithm with Stack for Radio Frequency Identification Tag Anti-Collision

Bi-slotted Binary Tree Algorithm with Stack for Radio Frequency Identification Tag Anti-Collision

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价