近年來，因為科技的進步，電腦的記憶體容量與運算速度逐漸加快，而射頻辨識系統（RFID）的相關應用在近幾年更是熱門的話題。如Wal-Mark在2003年年底宣佈將在2004年開始在其賣場導入射頻辨識系統，使得射頻辨識系統再度成為廠商發展的重點。而在射頻辨識系統相關應用逐漸廣泛的未來，勢必會出現一個讀取器必須同時辨識多個標籤也就是所謂碰撞避免（Anti-collision）的問題，由於目前射頻辨識系統仍然沒有統一規格，所以射頻辨識系統碰撞避免的問題目前還是由各廠商自行研發。而碰撞避免的問題在射頻辨識系統廣泛的應用後，將會越來越重要。目前射頻辨識系統的碰撞避免主要分成兩個型態：決定型以及隨機型。本篇論文主要是以隨機型碰撞避免演算法（slotted-ALOHA）為基礎，提出二個碰撞避免的演算法，並將碰撞避免的問題分成兩個部份：一、估計讀取器周圍標籤可能的數目。二、根據第一部份所估計出的標籤數目調整下一回合的框頁數大小。而根據模擬結果證實本論文所提出的兩個碰撞避免演算法相對於其他隨機型碰撞避免演算法有較佳的效率。而在論文最後則是算出所提出的兩個碰撞避免演算法的執行時間與決定型演算法中的樹演算法（Tree algorithm）以及查詢樹演算法(memoryless protocol)作比較，發現所提出的兩個碰撞避免演算法均有較短的執行時間。

Radio frequency identification (RFID) technology is becoming increasingly attractive because of high storage capacity and reprogrammed capability. Recently, RFID systems have become very popular in many industries. For example, Wal-Mark announced that they will lead RFID systems to their business model. There is a challenge to be overcome when a reader needs to read a number of tags within the reader’s interrogation zone at the same time. However, there are very little researches about Anti-collision protocol in the RFID system at present and manufacturers don’t come out specifications for their systems into the open. In this thesis, we proposed a collision avoidance protocol in a RFID system. The scheme is based on dynamic framed ALOHA protocol developed for radio networks. In our scheme, we propose two methods to estimate the number of tags and derive the optimal frame length. In our protocol, we propose two methods to estimate the number of tags and derive the optimal frame length. Simulation results indicate that the error of our tag estimate method can be less than 1%. The total number of time slots for reading all tags is about 4 times of the number of tags needed to be read, including acknowledgement time slots. The main advantage of our scheme is the easy implementation for both readers and tags.

[1]. Klaus Finkenzeller. “RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification,” Second Edition. 2003, John Wiley & Sons, Ltd.
[2]. AutoID labs. “860 MHz-960 MHz class 1 radio frequency identification tag radio frequency and logical communication interface specification recommended standard, version 1.0.0.” Technical Report MIT-AUTOID-WH-007, Auto-ID Labs, 2002. Referenced 23 Dec. 2003 at http://www.autoidlabs.com.
[3]. ISO/IEC 18000-1. Information technology AIDC techniques – RFID for item management – air interface, part1 – generic parameters for air interface communication for globally accepted frequencies. http://www.iso.org.
[4]. Ari Juels. “yoking-proofs” for RFID tags. In Ravi Sandhu and Roshan Thomas, editors, Workshop on Pervasive Computing and Communications Security – PerSec 2004, pages 138–143, Orlando, Florida, USA, March 2004.IEEE.
[5]. Ranasinghe, D.C. , Engels, D.W. and Cole, P.H. “Security and privacy solutions for low-cost RFID systems,” Intelligent Sensors, Sensor Networks and Information Processing Conference, 2004. Proceedings of the 2004, 14-17 Dec. 2004 Page(s):337 – 342
[6]. Dirk Henrici and Paul Muller. “Hash-based enhancement of location privacy for radio-frequency identification devices using varying identifiers.” In Ravi Sandhu and Roshan Thomas, editors, Workshop on Pervasive Computing and Communications Security – PerSec 2004, pages 149–153, Orlando, Florida, USA, March 2004. IEEE.
[7]. Don R. Hush and Cliff Wood, “Analysis of Tree Algorithm for RFID Arbitration,” In IEEE International Symposium on Information Theory, 1998.
[8]. C. Law, K. Lee, and K.-Y. Siu, “Efficient memoryless protocol for tag identification.” In Proceedings of the 4th International Workshop on Discrete Algorithm and Methods for Mobile Computing and Communications, p. 75-84, Boston, MA, August 2000.
[9]. Vogt, H. “Efficient Object Identification with Passive RFID Tags.” In international Conference on Pervasive Computing, LNCS, Springer-Verlag 2002.
[10]. Vogt, H. “Multiple Object Identification with Passive RFID Tags.” Systems, Man and Cybernetics, 2002 IEEE International Conference on Volume 3, p.6-9 Oct. 2002.
[11]. Jia Zhai, Gi-Nam Wang “An Anti-collision Algorithm Using Two-Functioned Estimation for RFID Tags.” Computational Science and Its Applications – ICCSA 2005: International Conference, Singapore, May 9-12, 2005, Proceedings, Part IV, Volume 3483, p.702-711, Apr. 2005.
[12]. W. Feller, “An Introduction to Probability Theory and Its Applications Volume1” Third Edition. 1984 John Wiley & Sons, INC. New York.
[13]. Nanjundaiah, M., Chaudhary, V. “Improvement to the Anticollision Protocol Specification for 900MHz Class 0 Radio Frequency Identification Tag” Advanced Information Networking and Applications, AINA 2005. 19th International Conference, Volume 2, p.616-620, Mar. 2005.
[14]. Jihoon Myung and Wonjun Lee “An Adaptive Memoryless Tag Anti-Collision Protocol for RFID Networks”, 2005.dawn.cs.umbc.edu/INFOCOM2005/lee-myung-sl.pdf
[15]. “Draft Protocol Specification for a 900MHz Class 0 Radio Frequency Identification Tag” MIT Auto-ID Center, 23rd Feb 2003, www.epcglobalinc.org
[16]. Feng Zhou, Dawei Jin, Chenking Huang and Min Hao, “Optimize the Power Consumption of Passive Electronic Tags for Anti-collision Schemes”, ASIC Proceedings of 5th International Conference. Oct 2003. Volume 2, p. 1213-1217.
[17]. “Draft evaluating the merits of various RFID tagging protocols with respect to the protocol characteristics” Chris Turner IEng MIIE, Mar 2003. www.rfipsolutions.com/downloads/evaluating_various_rfid_tagging_protocols.pdf
[18]. “Auto-ID Reader protocol 1.0: Working Draft Version of 5 September 2003” Auto-ID Center, 2003. www.gs1-germany.de/content/e39/e466/e468/datei/ccg/5_auto_id_reader-protocol.pdf
[19]. “860MHz-930MHz Class 0 Radio Frequency Identification Tag Protocol Specification Candidate Recommendation, Version 1.0.0” MIT Auto-ID Center, July 2003 www.autoidlabs.org
[20]. “13.56MHz ISM Band Class 1 Radio Frequency Identification Tag Interface Specification: Candidate Recommendation, Version 1.0.0” MIT Auto-ID Center, May 2003 www.autoidlabs.org
[21]. “860MHz-930MHz Class 1 Radio Frequency Identification Tag & Logical Communication Interface Specification Candidate Recommendation, Version 1.0.1” MIT Auto-ID center, Nov 2002 www.autoidlabs.org

[22]. “Draft protocol specification for a 900 MHz Class 0 Radio Frequency Identification Tag” MIT Auto-ID center, Feb 2003 www.autoidlabs.org
[23]. Hernandez, P. Sandoval, J.D. Puente, F. Perez, F. “Mathematical model for a multiread anticollision protocol” Communications, Computers and signal Processing, 2001. PACRIM. 2001 IEEE Pacific Rim Conference , Aug. 2001 Volume: 2 p.647-650
[24]. Peter Popovski, Frank H. P. Fitzek, Ramjee Prasad “Batch conflict resolution algorithm with progressively accurate multiplicity estimation” Workshop on Discrete Algothrithms and Methods for MOBILE Computing and Communications Proceedings of the 2004 joint workshop on Foundations of mobile computing, 2004 p.31-40.
[25]. Philips Semiconductors www.semiconductors.philips.com/
[26]. Su-Ryun Lee, Sung-Don Joo and Chae-Woo Lee “An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification” Proceedings of the Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services 2005.
[27]. Jae-Ryong Cha and Jae-Hyun Kim “Novel Anti-collision Algorithms for Fast Object Identification in RFID System” Proceedings of the 2005 11th International Conference on Parallel and Distributed Systems 2005