臺灣博碩士論文加值系統

無線射頻辨識系統(RFID)為一種能自動辨識物件之系統，其組成為讀取器、電子標籤及主電腦應用系統。標籤內含一組獨一無二的ID，讀取器透過分享無線通訊頻道與附著於物件上之電子標籤進行溝通進而達到辨識之目的。當讀取器對範圍內之標籤發出質詢時，假設超過一個以上的電子標籤同時回傳其ID，便會導致標籤傳至讀取器之訊號發生碰撞，此碰撞會影響讀取器辨識標籤之效率，因此標籤防碰撞協定對於快速辨識物件而言是一項重要的議題。
本研究回顧主要收集整理近年來各學者所提出之標籤防碰撞協定；標籤防碰撞協定主要分為兩大類，分別為Tree-based協定及Aloha-based協定。研究內容涵蓋以Tree-based協定為基礎所發展出之七種協定，及以Aloha-based為基礎所研發出之六種協定；共論述十三種標籤防碰撞協定，分別做詳細介紹並舉例說明。本研究針對各協定之特性予以分類，並闡述分類依據、比較各協定之優劣，接著探討各協定之特性及適用狀況。基於上述成果，期望本研究回顧及分類能提供對此範疇有興趣之研究者為參考依據，以其發展出更有效率且完備之標籤防碰撞協定。

Radio Frequency Identification (RFID) is an automatic identification system for objects, which consists of readers、tags and host application system. A tag has a unique identification number (ID), and a reader communicates with tags which attached to objects over a shared wireless channel for tag identification. When reader interrogates tags within the reader’s range, and multiple tags transmit their IDs simultaneously, the tag-to-reader signals occur collision. Therefore, tag collision disturbs the reader’s identification efficiency. The tag anti-collision protocol is an important issue for fast recognizes objects. This research is major reviewed tag anti-collision protocols that be proposed recently. Tag anti-collision protocols can be grouped into two broad categories：Tree-based protocols and Aloha-based protocols. The research contains thirteen tag anti-collision protocols, seven of them are on the basis of Tree-based protocol, and the others are on the basis of Aloha-based protocol. This research classified these protocols by thier characteristic, and also provides a comparison between reviewed protocols, advantages and shortcomings, and suitable condition for use. This review could provide the basis for developing more efficient and perfect tag anti-collision protocols.

目錄
誌謝 I
摘要 II
ABSTRACT III
目錄 IV
表目錄 VII
圖目錄 IX
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍與限制 3
1.4 研究流程 3
1.5 論文架構 5
第二章 文獻探討 6
2.1 RFID基本介紹 6
2.1.1 系統組成 6
2.1.2運作原理 9
2.1.3系統規格 9
2.1.4應用實例 12
2.1.5 MIFARE卡之介紹 16
2.2 碰撞類型 19
2.2.1讀取器碰撞 19
2.2.2 標籤碰撞 21
2.3 基本標籤防碰撞協定 22
2.3.1 Tree-based標籤防碰撞協定之基本類型 22
2.3.2 Aloha-based標籤防碰撞協定之基本類型 29
2.4 RFID標準協定與防碰撞法則 33
2.5 現有調查性論文之探討 34
第三章 標籤防碰撞協定之近期發展 37
3.1 Binary Tree協定之發展歷程 38
3.1.1 Adaptive Binary Splitting協定 38
3.2 Query Tree協定之發展歷程 45
3.2.1 Adaptive Query Splitting協定 45
3.2.2 Noble Tree-based協定 54
3.2.3 穿透式增效二元搜尋法則 60
3.2.4 Hybrid Query Tree協定 63
3.3 Slotted-Aloha協定之發展歷程 67
3.3.1 Bit-slot協定 67
3.3.2 Groping Based Bit-slot ALOHA協定 69
3.4 Framed Slotted Aloha協定之發展歷程 71
3.4.1 EB-FSA協定 71
第四章 分析與討論 75
4.1 分類依據 75
4.2 各協定優劣之比較 81
4.3 特性探討 86
第五章 結論與建議 89
5.1 結論 89
5.2 研究貢獻 92
5.3 未來發展 92
參考文獻 93

參考文獻
[1] J. Landt, 2001, “Shrouds of Time ：The history of RFID”, http://www.rfidconsultation.eu/docs/ficheiros/shrouds_of_time.pdf
[2] “The History of RFID Technology”, http://www.rfidjournal.com/
article/view/1338/1/129
[3] N. Abramson, 1970, “The Aloha System－Another Alternative for Computer Communications”, Fall Joint Computer Conference, pp. 281-285
[4] D. Hush and C. Wood, 1998, “Analysis of Tree Algorithms for RFID Arbitration”, IEEE International Symposium on Information Theory, pp. 107-144.
[5] D. H. Shin, P. L. Sun, D.C. Yen and S. M. Huang, 2006, “Taxonomy and Survey of RFID Anti-Collision Protocols”, Computer Communications, Volume 29, Issue 11, pp. 2150-2166.
[6] 邱瑩青, 2005, “RFID實踐－非接觸式智慧卡系統開發”, 學貫行銷股份有限公司。
[7] 刁建成, 2005, “RFID原理與應用”, 社團法人日本自動辨識協會。
[8] 陳建宏, 2004, “RFID系統入門－無線射頻辨識系統”, 文魁資訊股份有限公司。
[9] K. Finkenzeller, 2007, ”RFID手冊－無線智慧卡與識別卡之基礎與應用”, 全華科技書圖股份有限公司。
[10] 日經BP RFID編輯部, 2004, “RFID 技術與應用”, 旗標出版股份有限公司。
[11] EPCglobal, http://www.epcglobalinc.org.
[12] “臺北大眾捷運股份有限公司”, http://www.trtc.com.tw/c/
[13] “臺北智慧卡票證公司”, http://www.easycard.com.tw/
[14] 林進修, 2007, “醫療腕帶超智慧病歷服藥全都錄”, 聯合新聞網http://data.udn.com/data/titlelist.jsp
[15] 邱瑞科、張彥群、何佳隆與黃珈瑩, 2008, “, RFID 及資通科技於醫療照護的推動與應用”, 數位科技與創新管理研討會http://dtim.mis.hfu.
edu.tw/2008/paper/C189.pdf
[16] 張花超、張慧蓉、杜宜凌與高鵬, 2006, “臺大圖書館法社分館暨醫學院圖書分館建置RFID系統成果報告(網路版)”, http://ntuml.mc.ntu.edu.
tw/research/950605RFID.pdf
[17] S. Sarma, D. Brock, and D. Engels, 2001, “Radio Frequency Identification and the Electronic Product Code”, IEEE Micro, Volume 21, Issue 6, pp. 50-54.
[18] S. Sarma, S. Weis, and D. Engels, 2002, “RFID Systems and Security and Privacy Implications”, Lecture Notes In Computer Science, Volume 2523, pp. 454-469.
[19] D. Engels, 2002, “The Reader Collision Problem”, Technical Report of Auto-ID Center.
[20] J. Waldrop, D. Engels, and S. Sarma, 2003, “Colorwave：An Aticollision Agorithm for the Rader Cllision”, IEEE International Conference on Communications, Volume 2, pp. 1206-1210.
[21] S. Birari, 2005, “Mitigating the Reader Collision Problem in RFID Networks with Mobile Readers”, IEEE International Conference on Networks, volume 1, pp. 16-18.
[22] F. Zhou, C. Chen, D. Jin, and H .Min, 2004, “Evaluating and Optimization Power Consumption of Anti-Collision Protocols for Applications in RFID Systems”, International Symposium on Low Power Electronics and Design, pp. 357-362.
[23] T.P. Wang, C.C. Tseng, and S.Y. Hwang, 1999, “A Fair Protocol for Fast Resource Assignment in Wireless PCS Networks”, Wireless Networks, Volume 5, pp. 33-40.
[24] S.Y Hwang, and T.P. Wang, 1999, “Two Auction-Based Protocols for Fair and Fast Resource Assignment in Wireless PCS”, Wireless Personal Communication : An International Journal, Volume 10, pp. 175-187.
[25] J. Capetanakis, 1979, “Tree Algorithms for Packet Broadcast Channels”, IEEE Transactions on Information Theory, Volume 25, pp. 505-515.
[26] J. Myung, and W. Lee, 2005, “Adaptive Binary Splitting：A RFID Tag Collision Arbitration Protocol for Tag Identification”, Mobile Networks and Applications, Volume 11, pp.711-722.
[27] J. Myung, W. Lee, and J. Srivastava, 2006, “Adaptive Binary Splitting for Efficient RFID Tag Anti-Collision”, IEEE Communication Letters, Volume 10, pp 144- 146.
[28] J. Myung, W. Lee, and T. Shin, 2006, “An Adaptive Memoryless Protocol for RFID Tag Collision Arbitration”, IEEE Transactions on Multimedia, Volume 8, pp. 1096-1101.
[29] J. Myung, W. Lee, J. Srivastava and T. Shin, 2007, “Tag-Splitting: Adaptive Collision Arbitration Protocols for RFID Tag Identification”, IEEE Transactions on Parallel and Distributed Systems, Volume 18, pp. 763-775.
[30] C. Law, K. Lee, and K.Y. Siu, 2000, “Efficient Memoryless Protocol for Tag Identification”, International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 75-84.
[31] Javvin, “Bursty Traffic”, http://www.javvin.com/networkingterms/Burs
tyTraffic.html
[32] Wikipedia, 2008, “Time Dvision Mltiple Access”, http://en.wikipedia.org/
wiki/Time-division_multiple_access
[33] L. Liu and S. Lai, 2006, “ALOHA-Based Anti-Collision Algorithms Used in RFID System”, International Conference on Wireless Communications, Networking and Mobile Computing, pp. 1-4.
[34] T. Cheng and L. Jin, 2007, “Analysis and Simulation of RFID Anti-Collision Algorithms”, The 9th International Conference on Advanced Communication Technology, Volume 1, pp. 697-701.
[35] R. Metcalfe, 1973, “Steady State Analysis of a Slotted and Controlled Aloha System with Blocking”, ACM SIGCOMM Computer Communication Review, Volume 5, Issue 1, pp. 24-31.
[36] S. Lam and L. Kleinrock, 1975, “Packet Switching in a Multi Access Broadcast Channel: Dynamic Control Procedures”, IEEE Transactions on Communications, Volume 23, Issue 9, pp. 891-904.
[37] R. Rao and A. Ephremides, 1988, “On the Stability of Interacting Queues in a Multiple-Access System”, IEEE Transactions on Information Theory, Volume 34, Issue 5, pp. 918-930.
[38] V. Anatharam, 1991, “The Stability Region of the Finite-User Slotted ALOHA Protocol”, IEEE Transactions on Information Theory, Volume 1, Issue 13, pp. 579–584.
[39] I. Teletar and R. Gallager, 1995, “Combining Queuing Theory and Information Theory for Multiaccess”, IEEE International Symposium on Information Theory, Volume 13, Issue 6, pp. 963-969.
[40] R. Rom and M. sidi, 1990, “Multiple Access Protocols：Performance and Analysis”, ACM SIGMETRICS Performance Evaluation Review, Volume 20, Issue 3, pp. 5-6.
[41] H. Vogt, 2002, “Efficient Object Identification with Passive RFID Tags”, First International Conference on Pervasive Computing, pp. 98-113.
[42] J.E. Wieselthier, A. Ephermides, and L. Michels, 1989, “An exact Analysis and Performance Evaluation of Framed ALOHA with Capture”, IEEE Transactions on Communications, Volume 37, Issue 2, pp. 125 – 137.
[43] H. Vogt, 2002, “Multiple Object Identification with Passive RFID Tags”, IEEE International Conference on Systems, Man and Cybernetics, Volume 3, pp. 93-99.
[44] S. Lee, S. Joo, and C. Lee, 2005, “An Enhance 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.
[45] J. Cha and J. Kim, 2005, “Novel Anti-Collision Algorithm for Fast Object Identification in RFID System”, International Conference on Parallel and Distributed Systems, Volume 2, pp. 63-67.
[46] K. Finkenzeller, 2003, “RFID handbook：Radio-Frequency Identification Fundamentals and Applications in Contactless Smart Cards and Identification”, Wiley & Sons LTD.
[47] J.G. Lee, S.J. Hwang, S.W. Kim, and S. Ahn, 2005, “Software Architecture for a Multi-Protocol RFID Reader on Mobile Devices”, International Conference on Embedded Software and System, pp. 81-88.
[48] C. Marcelo, A. Marcon, and P. Hessel, 2008, “Survey of Standardized ISO 1800-6 RFID Anti-Collision Protocols”, The Second International Conference on Sensor Technologies and Applications, pp. 468-473.
[49] A. Juels, 2006, “RFID Security and Privacy：A Research Survey”, IEEE Journal on Selection Areas in Communications, Volume 24, Issue 2, pp. 381-394.
[50] M. Langheinrich, 2007, “A Survey of RFID Privacy Approaches”, Workshop on Ubicomp Privacy - Technologies, Users, Policy. Workshop at Ubicomp.
[51] Y. Yousuf and V. Potdar, 2008, “A Survey of RFID Authentication Protocols”, 22nd International Conference on Advanced Information Networking and Applications－Workshops, pp. 1346-1350.
[52] A. Jeng、L.C. Chang and H.K. Ho, 2008, “Survey and Remedy of Mutual Authentication Protocols for RFID System”, International Conference on Machine Learning and Cybernetics, Volume 6, pp. 3361-3366.
[53] M. Jacomet, A. Ehrsam, and U. Geherig, 1999, “Contactless Identification Device with Anticollision Algorithm”, IEEE Computer Society, Conference on Circuits, Systems, Computers and Communications, pp. 269-273.
[54] S. Weis, S. Sarma, R. Rivest, and D.Engels, 2003, “Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems”, 1st International Conference on Security in Pervasive Computing, pp. 201-212.
[55] Y.C. Lai, and C.C Lin, 2008, “A Pair-Resolution Blocking Algorithm on Adaptive Binary Splitting for RFID Tag Identification”, IEEE Communication Letters, Volume 12, Issue 6, pp.432-434.
[56] Y.C. Lai, and C.C Lin, 2008, “Two Blocking Algorithms on Adaptive Binary Splitting：Single and Pair Resolutions for RFID Tag Identification”, IEEE/ACM Transactions on Networking.
[57] J. Myung, and W. Lee, 2006, “Adaptive Splitting Protocols for RFID Tag Collision Arbitration”, ACM international symposium on Mobile ad hoc networking and computing, pp. 202-213.
[58] S.H Kim, M.K Shin, and P. Park, 2006, “A New Tree-based Tag Anti-Collision Protocol for RFID System”, The 2006 World Congress in Computer Science Computer Engineering, and Applied Computing.
[59] S.H Kim, and P. Park, 2007, “An Efficient Tree-Based Tag Anti-Collision Protocol for RFID Systems”, IEEE Communications Letters, Volume 11, Issue 5, pp. 449-451.
[60] 縱向優先搜尋 (Depth-First Search)http://nthucad.cs.nthu.edu.tw/~
yyliu/personal/nou/04ds/dfs.html
[61] T.P. Wang, 2006, “Enhanced Binary Search with Cut-Through Operation for Anti-Collision in RFID Systems”, IEEE Communications Letters, Volume 10, Issue 4, pp. 236-238.
[62] J. Ryu, H. Lee, Y. Seko, T. Kwon, and Y. Choi, 2007, “A Hybrid Query Tree Protocol for Tag Collision Arbitration in RFID systems”, IEEE International Conference on Communication, pp. 5981-5986.
[63] P. Mathys and P. Flajolet, 1985, “Q-ary Collision Resolution Alogorithms in Random-Access Systems with Free or Blocked Chennel Access”, IEEE Transactions on Communications, Volume 31, Issue 2, pp. 217-243.
[64] C.S. Kim, K.L. Park, H.C. Kim, and S.D. Kim, 2004, “An Efficient Stochastic Anti-collision Algorithm Using Bit-Slot Mechanism”, Parallel and Distributed Processing Techniques and Applications.
[65] C.P. Wong and Q.Y. Feng, 2007, “Grouping Based Bit-Slot Aloha Protocol for Tag Anti-Collision in RFID Systems”, IEEE Communications Letters, Volume 11, Issue 12, pp. 946-948.
[66] J. Park, M.Y. Chung, and T.J. Lee, 2007, “Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection”, IEEE Communication Letters, Volume 11, Issue 5, pp. 452-454.