在無線辨識系統(RFID)裡，標籤(tag)是藉由共用無線頻道傳送它們的二元編碼字串而被讀取器(reader)辨識。當多個標籤同時傳送它們的二元編碼字串，它們的訊號將會互相碰撞而造成讀取器需要花更多的時間來辨識它們。所以許多現存的反碰撞演算法：動態分割查詢演算法和動態二元分割演算都是為了解決這樣的問題。本篇論文提出兩個根基於動態分割演算法的阻隔式演算法：阻隔式動態分割演算法和半阻隔式動態分割演算法。阻隔式動態分割演算法和半阻隔式動態分割演算法皆承續著動態分割演算法之特點：保有上次已被辨識過之標籤所留下之資訊。不僅如此，前者更採用了全部阻隔的方式來避免已被辨識之標籤和未被辨識之標籤的碰撞，而後者使用半阻隔式來允許少數未被辨識之標籤和已被辨識之標籤造成碰撞，如此一來以機率完整分布的情況便可以正確地估記出另一個大多數未被辨識之標籤的數量。

In Radio Frequency Identification (RFID) system, tags are identified by the reader through transmitting their IDs over a shared wireless channel. When multiple tags respond their IDs simultaneously, their signals collide, increasing the identification delay. Thus, 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 blocking AQS algorithm (BA) and a semi-blocking AQS algorithm (SBA), based on AQS. BA and SBA all inherit the essence of AQS which uses the information of recognized tags obtained from the last process of tag identification. Moreover, the former further adopts a blocking technique which prevents all recognized tags from being collided by unrecognized tags, while the latter further uses a semi-blocking technique which permits the minority of unrecognized tags colliding with recognized tags to get a distributed probability so that can more correctly estimate the other majority of unrecognized tags.

[1] K. Finkenzeller, RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification, 2nd ed., New York: Wiley, 2003.
[2] S. Shepard, RFID: Radio Frequency Identification. New York: McGraw-Hill, pp. 55-61, 2005,.
[3] “Draft protocol specification for a 900 MHz class 0 radio frequency identification tag,” Auto-ID Center, Feb. 2003.
[4] “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), Aug. 2004.
[5] W. C. Chen, S. J. Horng, and Pingzhi Fan, “An enhanced anti-collision algorithm in RFID based on counter and stack,” Second International Conference on Systems and Networks Communications, pp. 21-24, Aug. 2007.
[6] C. Law, K. Lee, and K. Y. Siu, “Efficient Memaryless Protocol for Tag Identification,” In Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 75-84, Aug. 2000.
[7] “860MHz-930MHz class 1 radio frequency identification tag radio frequency & logical communication interface specification candidate recommendation version 1.0.1,” Auto-ID Center, Nov. 2002.
[8] F. Zhou, C. Chen, D. Jin, C. Huang, and H. Min, “Evaluating and optimizing power consumption of anti-collision protocols for applications in RFID systems,” 2004. ISLPED '04. Proceedings of the 2004 International Symposium on Low Power Electronics and Design, pp. 357-362, Aug. 2004.
[9] T. P. Wang, “Enhanced binary search with cut-through operation for anti-collision in RFID systems,” IEEE Communications Letters, vol. 10, no. 4, pp. 236-238, Apr. 2006,.
[10] K. W. Chiang, C. Hua, and T.-S. Peter Yum, “Prefix-randomized query-tree protocol for RFID systems,” International Conference on Communications, pp. 1653-1657, Jun. 2006.
[11] J. H. Choi, D. Lee, and H. Lee, “Bi-slotted tree based anti-collision protocols for fast tag identification in RFID systems,” IEEE Communications Letters, vol. 10, no. 12, pp. 861-863, Dec. 2006.
[12] J. Ryu, H. Lee, Y. Seok, T. Kwon, and Y. Choi, “A hybrid query tree protocol for tag collision arbitration in RFID systems,” IEEE International Conference on Communications, pp. 5981-5986, Jun. 2007.
[13] J. H. Choi, D. Lee, and H. Lee, ”Query tree-based reservation for efficient RFID tag anti-collision,” IEEE Communications Letters, vol. 11, is. 1, pp. 85-87, Jan. 2007.
[14] J. I. Capetanakis, “Tree algorithms for packet broadcast channels,” IEEE Transactions on Information Theory, vol. 25, no. 5, pp. 505-515, Sep. 1979.
[15] J. Mosely and P. Humblet, “A class of efficient contention resolution algorithms for multiple access channels,” IEEE Transactions on Communications, vol. 33, no. 2, pp. 145-151, Feb. 1985.
[16] H. Vogt, “Efficient object identification with passive RFID tags,” Lecture Notes in Computer Science, vol. 2414, Springer Berlin/Heidelberg, Aug. 2002.
[17] “EPCTM radio-frequency identity protocols class 1 generation-2 UHF RFID protocol for communications at 860-960MHz version 1.0.9,” EPCglobal IncTM, Jan. 2005.
[18] J. Zhai and G. N. Wang, “An anti-collision algorithm using two-functioned estimation for RFID tags,” Lecture Notes in Computer science, vol. 3483, Springer Berlin/Heidelberg, pp. 702-711, May 2005.
[19] S. R. Lee, S. D. Joo, and C. W. Lee, “An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification,” The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, pp. 166-172, Jul. 2005.
[20] J. R. Cha and J. H. Kim, “Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system,” 3rd Consumer Communications and Networking Conference, pp. 768-772, Jan. 2006.
[21] “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.
[22] M. A. Bonuccelli, F. Lonetti, and F. Martelli, “Tree slotted aloha: a new protocol for tag identification in RFID networks,” International Symposium on a World of Wireless, Mobile and Multimedia Networks, Jun. 2006.
[23] T. W. Hwang, B. G. Lee, Y. S. Kim, D. Y. Suh, and J. S. Kim “Improved anti-collision scheme for high speed identification in RFID system,” First International Conference on Innovative Computing, Information and Control, pp. 449-452, Aug. 2006.
[24] Q. Peng, M. Zhang, and W. Wu, “Variant enhanced dynamic frame slotted ALOHA algorithm for fast object identification in RFID system,” IEEE International Workshop on Anti-counterfeiting, Security, Identification, pp. 88-91, Apr. 2007.
[25] J. Park, M. Y. Chung, and T. J. Lee, “Identification of RFID tags in framed-slotted ALOHA with robust estimation and binary selection,” IEEE Communications Letters, vol.11, no. 5, pp. 452-454, May 2007.
[26] F. Schoute, “Dynamic frame length ALOHA,” IEEE Transactions on Communications, vol. 31, no. 4, pp. 565-568, Apr. 1983.
[27] J. E. Wieselthier, A. Ephremides, and L. A. Michaels, “An exact analysis and performance evaluation of framed ALOHA with capture,” IEEE Transactions on Communications, vol. 37, no. 2, pp. 125-137, Feb. 1989.
[28] J. Myung, W. Lee, and J. Srivastava, “Adaptive binary splitting for efficient RFID tag anti-collision,” IEEE Communications Letters, vol. 10, no. 3, pp. 144-146, Mar. 2006.
[29] J. Myung, W. Lee, and T. K. Shih, “An adaptive memoryless protocol for RFID tag collision arbitration,” IEEE Transactions on Multimedia, vol. 8, no. 5, pp. 1096-1101, Oct. 2006.
[30] J. Myung, W. Lee, J. Srivastava, and T. K. Shih, “Tag-splitting: adaptive collision arbitration protocols for RFID tag identification,” IEEE Transactions on Parallel and Distributed Systems, vol.18, no. 6, pp. 763-775, Jun. 2007.