無線射頻辨識(RFID)一種非接觸式的識別技術，擁有高速辨識的能力。在最近幾年來，RFID已被廣泛的應用，從供應鏈關理系統、高速公路電子收費系統、醫療保鍵等等。RFID的讀取器擁有迅速的讀取標籤的能力，但是由於讀取器與標籤之間的通訊使用了相同的頻道，當多個標記同時傳送他們的識別至讀取器時，它們所傳送的訊號將互相碰撞變成了雜訊並且無法被讀取器辨識，造成了讀取時間的延遲以及能源上的浪費。因此，為了解決訊號碰撞的問題以提高RFID的讀取效能，反碰撞演算法是必須存在的。在此本論文中，我們提出了基於樹狀架構的新反碰撞演算法，稱為八位式反碰撞演算法（Octad）。八位式反碰撞演算法使用了二個新的概念：三位元檢查字串及三位元加密字串以製作標籤回應訊息的規則與元件。根據模擬的結果顯示，八位式反碰撞演算法所改善的延遲時間及能源浪費勝過其他現有的基於樹狀架構的的反撞演算法。

Radio Frequency IDentification (RFID), a non-contact identification technology, which has high speed identification ability, is widely implemented in several applications, such as supply-chain management systems, Electronic Toll Collection, healthcare facilities, etc. The concept of RFID is to use the reader to gather the information from the tags as quickly as it can. The communication between the reader and the tags uses a shared wireless channel. When multiple tags simultaneously transmit their IDs back to the reader, signal collision will occur, increases the higher transmission delay and communication overhead. Thus, it is urgently needed a signal collision resolution for efficient tag identification. In this paper, we propose a novel, tree-based anti-collision scheme, called The Octad Algorithm (Octad) which embeds two novel concepts, i.e. 3-bit parity string and 3-bit encoding string. The simulation results show that Octad outperforms other existing tree-based anti-collision schemes in terms of identification delay and communication overhead.

[1] K.W. Chiang, C. Hua and T.S. Peter Yum, “Prefix Randomized Query Tree Protocol for RFID Systems,” in proc. of IEEE International Conference on Communications, pp. 1653-1657, June 2006.
[2] J.S. Cho, J.D. Shin and S.K. Kimg, "RFID Tag Anti-Collision Protocol: Query Tree with Reversed IDs," in proc. of 10th International Conference on Advanced Communication Technology, pp. 225-230, February 2008.
[3] H. S. Choi, J. R. Cha and J.H. Kim, “Fast Wireless Anti-Collision Algorithm in Ubiquitous ID System,” in proc. of IEEE 60th Vehicular Technology Conference, pp.4589-4592, September 2004.
[4] J.H. Choi, D. Lee and H. Lee, "Query Tree-Based Reservation for Efficient RFID Tag Anti-Collision," in proc. of IEEE Communications Letters Vol. 11, Issue 1, pp. 85-87, January 2007.
[5] EPC™ Radio-Frequency Identity Protocols Class 1 Generation-2UHF RFID Protocol for Communications at 860–960 MHz Version 1.0.9, EPC Global Inc., 2005.
[6] K. Finkenzeller, RFID Handbook: Radio-Frequency Identification, Fundamentals and Applications, John Wiley & Sons Ltd, 1999.
[7] C.H. Hsu, C.H. Yu, Y.P. Huang and K.J. Ha, "An Enhanced Query Tree (EQT) Protocol for Memoryless Tag Anti-Collision in RFID Systems," in proc. of 2nd International Conference on Future Generation Communication and Networking, pp. 427-432, December 2008
[8] S.S. Kim, Y.H. Kim, S.J. Lee and K.S. Ahn, “An Improved Anti Collision Algorithm using Parity Bit in RFID System,” in proc. of 7th IEEE International Symposium, pp. 224-227, July 2008.
[9] S.H. Kim and P.G. Park, "An Efficient Tree-Based Tag Anti-Collision Protocol for RFID Systems," in proc. of IEEE Communication Letters, Vol. 11, Issue 5, pp. 449-451, May 2007.
[10] D.K. Klair and K.W. Chin, "A Novel Anti-Collision Protocol for Energy Efficient Identification and Monitoring in RFID-Enhanced WSNs," in proc. of 17th International Conference on Computer Communications and Networks, pp. 1-8, August 2008.
[11] Y. C. Lai and C. C. Lin, “A Pair Resolution Blocking Algorithm on Adaptive Binary Splitting for RFID Tag Identification,” in proc. of IEEE Communications Letters, vol.12, Issue .6, pp. 432-434, June 2008.
[12] Y.C. Lai and C.C. Lin, "Two Blocking Algorithms on Adaptive Binary Splitting: Single and Pair Resolutions for RFID Tag Identification," in proc. of IEEE/ACM Transactions on Networking 2009, pp. 962-975, June 2009.
[13] L. Liu, Z. Xie, J. Xi and S. Lai, “An Improved Anti-collision Algorithm in RFID System,” in proc. of 2nd International Conference on Mobile Technology, Applications and Systems, pp. 15-17, November 2005.
[14] J. Myung, W. Lee and J. Srivastava, “Adaptive Binary Splitting for Efficient RFID Tag Anti-Collision,” in proc. of IEEE Communications Letters, vol.10, Issue.3, pp. 144-146,.March 2006.
[15] J. Myung and W. Lee, "Adaptive Binary Splitting: A RFID Tag collision Arbitration Protocol for Tag Identification," in proc. of 2nd International Conference on Broadband Networks, pp. 347-355, October 2005.
[16] J.H. Park, M.Y. Chung and T.J. Lee, "Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection," in proc. of IEEE Communication Letters, Vol. 11, Issue 5, pp. 452-454, May 2007.
[17] J. Ryu, H. Lee, Y. Seok, T. Kwon and Y.H. Choi, “A Hybrid Query Tree Protocol for Tag Collision Arbitration in RFID systems,” in proc. of IEEE International Conference on Communications 2007, pp. 5981-5986, June 2007.
[18] J. Waldrop, D.W. Engels and S.E. Sarma, "Colorwave: an AntiCollision Algorithm for The Reader Collision Problem," in proc. of IEEE International Conference on Communications 2003, pp. 1206-1210 vol.2, May 2003.
[19] T.P Wang, "Enhanced Binary Search with Cut-Through Operation for Anti-Collision in RFID Systems," in proc. of IEEE Communication Letters, Vol. 10, Issue 4, pp. 236-238, April 2006.
[20] C.P. Wong and Q. Feng, "Grouping Based Bit-Slot ALOHA Protocol for Tag Anti-Collision in RFID Systems," in proc. of IEEE Communication Letters Vol.11, Issue 12, pp. 946-948, December 2007.
[21] J. Wang, Y. Zhao and D. Wang, "A Novel Fast Anti-Collision Algorithm for RFID Systems," in proc. of International Conference on Wireless Communications, Networking and Mobile Computing 2007, pp. 2044–2047, September 2007.
[22] K.H. Yeh, N.W. Lo and Enrico Winata, "An Efficient Tree-Based Tag Identification Protocol for RFID Systems," in proc. of 22nd International Conference on Advanced Information Networking and Applications Workshops 2008, pp. 966-970, March 2008.