在無線射頻辨認系統的架構中，由於碰撞(Collisions)會延長辨認時間，所以架構中最重要的一個議題是如何有效地解決碰撞問題並快速完成辨認。本篇論文是以適性二元分割演算法(Adaptive Binary Splitting, ABS)為基礎提出具動態縮減機制的適性初始分配二元分割演算法(Adaptive Initial Size ABS, AISA)來減少碰撞的發生。ABS是為避免已辨認過的標籤彼此之間發生碰撞，所以會記取標籤的先前傳送順序。為此，ABS必須保留的時槽數量(slot size) 必須等同於在上一回辨認流程的標籤數量。然而，此做法並不適用於當許多標籤突然離開的情形。因此，繼承ABS記憶標籤資訊的AISA，它會依據標籤數量的估計值來動態地調整初始的時槽數量給目前標籤，以避免標籤嚴重地相互碰撞或浪費時槽。從數學式分析結果中，AISA與ABS相較下，能有效地縮短其延遲辨認時間(Identification delay)，其最多可達到98%。

How to solve collisions efficiently and accomplish the identification is an important issue of Radio Frequency Identification (RFID) since collisions slow down the identification. This paper proposes a novel anti-collision algorithm, Adaptive Initial Size ABS (AISA), based on adaptive binary splitting algorithm (ABS), to reduce collisions. ABS remembers the information of identified tags in the previous process to avoid collisions from these tags. However, that it must reserves a slot size which equals the number of recognized tags in the previous process is not proper when many tags leave. Therefore, AISA inheriting ABS dynamically adjusts the initial number of slots according to the estimation of the number of tags for preventing that tags seriously collide or waste slots. From analysis, AISA efficiently shortens up to 98% of identification delay compared with ABS.

[1] L. Liu and S. Lai, “Aloha-based anti-collision algorithms used in RFID system,” International Conference on Wireless Communications, Networking and Mobile Computing, 2006.
[2] J. R. Cha and J. H. Kim, “Dynamic frame slotted aloha algorithms using fast tag estimation method for RFID system,” 3rd Consumer Communication and Networking Conference, Jan. 2006.
[3] S. R. Cha and J. H. Kim, “An enhanced dynamic framed slotted aloha algorithm for RFID tag identification,” 2nd Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, Jul. 2005.
[4] EPC Radio-Frequency Identification Protocols Class-1 Generatio-2 UHF RFID Protocol for Communications at 860MHz-960MHz Version 1.1.0, EPCglobal, Dec. 2005.
[5] Draft Protocol Specification for a 900 MHz Class 0 Radio Frequency Identification Tag, Auto-ID Center, Feb. 2003.
[6] W. C. Chen, S. J. Horng, and P. Fan, “An enhanced anti-collision algorithm in RFID based on counter and stack,” IEEE Second International Conference on Systems and Networks Communications, Aug. 2007.
[7] T. P. Wang, “Enhanced binary search with cut-through operation for anti-collision in RFID system,” IEEE Communication Letters, vol. 10, no. 4, pp. 236-238, Apr. 2006.
[8] J. H. Choi, D. Lee, and H. Lee, “Bi-slotted tree based anti-collision protocols for fast tag identification in RFID systems,” IEEE Communication Letters, vol. 10, pp. 861-863, Dec. 2006.
[9] J. Ryu, H. Lee, Y. Seok, T. Kwon, and Y. Choi, “An hybrid query tree protocol for tag collision arbitration in RFID systems,” IEEE International conference on Communications, Jun. 2007.
[10] J. H. Choi, D. Lee, Y. Youn, H. Jeon, and H. Lee, “Scanning-based pre-processing for enhanced RFID tag anti-collision protocols,” Communications and Information Technologyes, pp. 1207-1211, Oct. 2006.
[11] K. W. Chiang, C. Hua, and T. S. P. Yum, “Prefix-randomized query-tree protocol for RFID systems,” International Conference on Communications, Jun. 2006.
[12] S. Kim, Y. Kim, S. Lee and K. Ahn, “An improved anti collision algorithm using parity bit in RFID system,” Seventh IEEE International Symposium on Network Computing and Applications, 2008.
[13] J. Myung, W. Lee, and T. K. Shih, “An adaptive memoryless protocol for RFID tag collision arbitration,” IEEE Transactions on Multmedia, vol. 8, pp. 1096-1101, Oct. 2006.
[14] J. Myung, W. Lee, J. Srivastava and T. k. Shin, “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.
[15] 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.