無線射頻技術（Radio Frequency Identification, RFID），是一種非接觸式的自動辨識技術於無線通道中進行讀取器與標籤之間的溝通識別。隨著這個能力，RFID技術已經應用於許多實際案例，如物流、庫存控制以及供應鏈管理。在供應鏈的流程中放在一起的物品，通常會有連續的標籤號碼，當讀取器打算取得所有標籤的身份時，號碼相近的標籤其回應訊號可能因互相碰撞而導致讀取器辨識失敗，此種情形稱為訊號碰撞。這種現象將會降低標籤識別的效率。
本篇論文將採用k元樹的抽象概念，發展出一套高效能的標籤識別協定（稱為k-ary Tree-based Anti-collision Scheme, k-TAS），用以解決供應鏈上物品辨識時的訊號碰撞問題，並且提升辨識效率。另外，我們建構了一個供應鏈網路的模擬流程，用以評估我們所提出的協定與其他既有協定間的效率優劣。實驗結果顯示，無論在辨識延遲或是通訊成本方面，我們所提出的標籤識別協定皆優於其他既有的RFID反碰撞標籤辨識協定。

Radio Frequency Identification (RFID) is a contactless automatic identification technology which communications between readers and tags via a shared wireless channel. With the ability of contactless identification, RFID has been adopted in several practical applications, such as logistics, inventory control, and supply chain management. In the supply chain process, the items which put together usually have continuous tag IDs. When a reader intends to gather all IDs from numerous existing tags, the tag-to-reader response may collide with each other and result in an identification failure called signal collision. This phenomenon will greatly degrade the tag recognition efficiency. To solve this problem, we design an efficient tag identification protocol for better tag recognition efficiency. A k-ary tree based abstract is adopted in our proposed protocol, called k-ary Tree-based Anti-collision Scheme (k-TAS), as an underlying architecture for collision resolution. In addition, we construct a supply chain network simulation process to evaluate the performance of our proposed RFID anti-collision protocol and other existing ones. The performance evaluation shows that our proposed tag identification protocol outperforms the existing RFID anti-collision schemes in terms of the identification delay and communication overhead.

中文摘要 I
Abstract II
誌 謝 III
Contents IV
List of Figures V
List of Tables VI
Chapter 1 Introduction 1
Chapter 2 Related Work 5
2.1 Electronic Product Code (EPC) 5
2.2 RFID Tree-based Anti-collision Algorithms 10
Chapter 3 Proposed Scheme 14
3.1 k-ary Tree-based Anti-collision Scheme (k-TAS) 15
3.2 An Example of k-TAS 21
Chapter 4 Performance Evaluation 26
4.1 Supply Chain Network Scenario 27
4.2 Impact of the system parameter i 29
4.3 Impact of the number of tags 32
4.3.1 Scenario I (Nc=1, Nt=1)–Inventory management 32
4.3.2 Scenario II (Nc=1, Nt=3)–Manufacturer delivery 35
4.3.3 Scenario III (Nc=3, Nt=10)–Distributor picking 37
Chapter 5 Conclusion 39
Reference 40

[1] M. Azambuja, C.A.M. Marcon and F.P. Hessel, "Survey of Standardized ISO 18000-6 RFID Anti-collision Protocols," in proc. of Second International Conference on Sensor Technologies and Applications, 2008, pp.468-473.
[2] T. Cheng and L. Jin, "Analysis and simulation of RFID anti-collision algorithms," in proc. of 9th International Conference on Advanced Communication Technology, 2007, pp.697-701.
[3] 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, 2006, pp.1653-1657.
[4] J.S. Cho, J.D. Shin and S.K. Kim, "RFID tag anti-collision protocol: query tree with reversed IDs," in proc. of 10th International Conference on Advanced Communication Technology, 2008, pp.225-230.
[5] 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, 2004, pp.4589-4592.
[6] J.H. Choi, D. Lee and H. Lee, "Query tree-based reservation for efficient RFID tag anti-collision," IEEE Communications Letters, vol.11, no.1, 2007, pp.85-87.
[7] EPCglobal Tag Data Standard (TDS) Version 1.4, EPCglobal Inc™, June 2008. http://www.epcglobalinc.org/standards/tds/tds_1_4-standard-20080611.pdf.
[8] EPC™ Radio-Frequency Identification Protocols Class 1 Generation-2 UHF RFID Protocol for Communication at 860-960 MHz Version 1.0.9, EPCglobal Inc., Dec. 2005.
[9] K. Finkenzeller, RFID Handbook: Radio-Frequency Identification, Fundamentals and Applications, John Wiley & Sons Ltd, 1999.
[10] C. Floerkemeier and M. Wille, "Comparison of transmission schemes for framed ALOHA based RFID protocols," in proc. of International Symposium on Applications and the Internet Workshops, 2006, pp.92-97.
[11] S.S. Kim, Y.H. Kim, S.J. Lee, K.S. Ahn, "An Improved Anti Collision Algorithm using Parity Bit in RFID System," Seventh IEEE International Symposium, 2008, pp. 224-227.
[12] D.K. Klair, K.W. Chin and R. Raad, "On the suitability of framed slotted aloha based RFID anti-collision protocols for use in RFID-enhanced WSNs," in proc. of 17th International Conference on Computer Communications and Networks, 2007, pp.583-590.
[13] 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, 2008, pp.1-8.
[14] Y.C. Lai and C.C. Lin, "A pair-resolution blocking algorithm on adaptive binary splitting for RFID tag identification," IEEE Communications Letters, vol.12, no.6, 2008, pp.432-434.
[15] Y.C. Lai and C.C. Lin, "Two blocking algorithms on adaptive binary splitting: single and pair resolutions for RFID tag identification," IEEE/ACM Trans. on Networking, vol.17, no.3, 2009, pp.962-975.
[16] C. Law, K. Lee and K.Y. Siu, "Efficient Memoryless Protocol for Tag Identification," in Proc. of the 4th International Workshop on Discrete Algorithm and Methods for Mobile Computing and Communication, 2000, pp.75-84.
[17] L. Liu, Z.H. Xie, J.T. Xi and S.L. Lai, "An improved anti-collision algorithm in RFID system," in proc. of 2nd International Conference on Mobile Technology, Applications and Systems, 2005, pp.1-5.
[18] Y. Maguire and R. Pappu, "An Optimal Q-algorithm for the ISO 18000-6C RFID Protocol," IEEE Trans. on Automation Science and Engineering, vol.6, no.1, 2009, pp.16-24.
[19] J. Myung, W. Lee and J. Srivastava, "Adaptive binary splitting for efficient RFID tag anti-collision," IEEE Communications Letters, vol.10, no.3, 2006, pp.144-146.
[20] J. Myung, W. Lee and T. K. Shih, "An Adaptive Memoryless Protocol for RFID Tag Collision Arbitration," IEEE Trans. on Multimedia, vol.8, 2006, pp.1096-1101.
[21] J. Myung, W. Lee, J. Srivastava and T. K. Shih, "Tag-splitting: adaptive collision arbitration protocols for RFID tag identification," IEEE Trans. on Parallel and Distributed Systems, vol.18, no.6, 2007, pp.763-775.
[22] V. Namboodiri and L. Gao, "Energy-Aware Tag Anti-Collision Protocols for RFID Systems," IEEE Trans. on Mobile Computing, vol.9, no.1, 2010, pp.44-59.
[23] H.S. Ning, Y. Cong, Z.Q. Xu, T. Hong, J. C. Chao and Y. Zhang, "Performance evaluation of RFID anti-collision algorithm with FPGA implementation," in Proc. of 21st International Conference on Advanced Information Networking and Applications Workshops, 2007, pp.153-158.
[24] J. Ryu, H. Lee, Y. Seok, T. Kwon, Y.H. Choi, "A Hybrid Query Tree Protocol for Tag Collision Arbitration in RFID systems," IEEE International Conference on Communications, 2007, pp. 5981-5986.
[25] D.H. Shih, P.L. Sun, David C. Yen and S.M. Huang, "Taxonomy and survey of RFID anti-collision protocols," Computer Communications, vol.29, issue 11, 2006, pp.2150-2166.
[26] T.P. Wang, "Enhanced binary search with cut-through operation for anti-collision in RFID systems," IEEE Communications Letters, vol.10, no.4, 2006, pp.236-238.
[27] C.P. Wong and Q. Feng, "Grouping based bit-slot ALOHA protocol for tag anti-collision in RFID systems," IEEE Communications Letters, vol.11, no.12, 2007, pp.946-948.
[28] K.H. Yeh, N.W. Lo and E. Winata, "An efficient tree-based tag identification protocol for RFID systems," in proc. of 22nd International Conference on Advanced Information Networking and Applications Workshops, pp.966-970.