臺灣博碩士論文加值系統

無線射頻識別(RFID)系統是一項應用廣泛的系統。它提供了自動辨識的方便性和快速性。在系統辨識的過程中有可能會遇到數個標籤同時傳送訊號給讀取器的情形。這種狀況會造成讀取器無法辨識這些標籤傳送的訊號代表的意義。此種情形我們稱作訊號碰撞(collision)。訊號碰撞的情形會造成辨識時間的延遲，而致使整個辨識過程效率不彰。所以我們需要一個協定來改善讀取器和標籤間的訊號碰撞問題。本文提出一個以ALOHA為基礎的防碰撞(Anti-collision)演算法來減少標籤訊號的碰撞問題。在本文提出的方法中主要是在當讀取器收到標籤碰撞的訊號時會第一個時間處理碰撞的標籤，而拋棄目前正在處理的回合。這樣的做法有別於ALOHA把全部碰撞的標籤累積到下一回合中再處理。這樣使得每次處裡的標籤數目相對的來說比較少。用這種方式來改善碰撞的情形，使得整個辨識過程所花費的時槽 (timeslot)數目相較於DFSA演算法來得還要少。尤其在標籤數目多的時候效果比較明顯，在標籤數目為一千個時所花費的時槽數目約只有DFSA演算法的54%。

Radio Frequency Identification (RFID) system is a widely applied system. It offers the convenience of automatic identification. In the process of identification, system may be encountered the situation that several tags transmit a message to reader simultaneously. The reader can not recognize the meaning of message in this situation. The situation is called collision. Collision will cause delay of identification and make efficiency low. Therefore, we need to have a protocol for improving the problem of collision. This thesis proposes an anti-collision method based on ALOHA to improve the problem of collision. Reader will deal with the collision tags immediately and abandon current process if collision occurs. The course is different from ALOHA which accumulate all collision tags to into next cycle. It will make the number of tags fewer in every reading cycle. The process of identification costs about 54% of the timeslots of DFSA when the number of tags is 1000. This approach can improve the problem of collision and the process of identification cost fewer timeslots than DFSA. Especially, when the number of tags is big, the efficiency is better than the other algorithms.

目 錄
中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 ix

第一章 緒論 1
1.1 研究背景與動機 1
1.2 防碰撞協定 3
1.2.1 防碰撞協定之類型 4
1.3 相關研究探討 5
1.3.1 樹狀演算法 6
1.3.2查詢樹演算法 7
1.3.3 Framed Slotted ALOHA(FSA)演算法 9
1.3.4 Dynamic Framed Slotted ALOHA(DFSA)演算法 11
1.4 文章結構 13
第二章 碰撞分隔式演算法 14
2.1 演算法流程 14
2.2 演算法架構 20
2.3 框頁尺寸之設定與分析 26
第三章 模擬結果 35
3.1 模擬方法 35
3.2 模擬結果 39
3.3 結果分析 44
第四章 結論 54
參考文獻 55
論文發表 60

圖目錄
圖1.1 RFID系統架構 1
圖1.2 樹狀演算法示意圖 6
圖1.3 查詢樹防碰撞演算法示意圖 8
圖1.4 Framed Slotted ALOHA示意圖 10
圖1.5 DFSA演算法示意圖 12
圖2.1 碰撞分隔式演算法之流程圖 16
圖2.2 框頁尺寸與時槽數目的組成 17
圖2.3 讀取器初始設定 21
圖2.4 示意碼之時槽狀態判別 22
圖2.5 碰撞分隔之處理 23
圖2.6 標籤之設置 24
圖2.7 辨識效率與框頁尺寸關係圖 30
圖2.8(a) 框頁尺寸與效率關係模擬結果圖(標籤數目：10) 32
圖2.8(b) 框頁尺寸與效率關係模擬結果圖(標籤數目：30) 32
圖2.8(c) 框頁尺寸與效率關係模擬結果圖(標籤數目：90) 33
圖2.8(d) 框頁尺寸與效率關係模擬結果圖(標籤數目：150) 33
圖2.8(e) 框頁尺寸與效率關係模擬結果圖(標籤數目：300) 34
圖3.1 模擬500次之結果累計(標籤數目：90個) 35
圖3.2模擬1000次之結果累計(標籤數目：90個) 36
圖3.3模擬2000次之結果累計(標籤數目：90個) 37
圖3.4模擬3000次之結果累計(標籤數目：90個) 37
圖3.5辨識時槽數目對300個辨識標籤之關係(使用(2.1)式) 39
圖3.6辨識時槽數目對300個辨識標籤之關係(使用(2.2)式) 40
圖3.7辨識時槽數目對1000個辨識標籤之關係(使用(2.1)式) 41
圖3.8辨識時槽數目對1000個辨識標籤之關係(使用(2.2)式) 42
圖3.9模擬結果之最佳值與平均值曲線 43
圖3.10最壞之情況示意圖 44
圖3.11 標籤數目3~32之機率分析 45
圖3.12 標籤數目3~64之機率分析 46
圖3.13(a) 佔據時槽之機率圖(a) 47
圖3.13(b) 佔據時槽之機率圖(b) 48
圖3.14 樹狀演算法vs. Proposed method時槽差距數目(使用(2.1)式) 49
圖3.15 樹狀演算法vs. Proposed method時槽差距數目(使用(2.2)式) 49
圖3.16 DFSA vs. Proposed method時槽差距數目(使用(2.1)式) 50
圖3.17 DFSA vs. Proposed method時槽差距數目(使用(2.2)式) 51
圖3.18模擬時間與標籤數目關係圖 52

表目錄

表2.1 框頁尺寸設定 29
表3.1 不同標籤數之模擬次數與結果統計表 38

參考文獻

[1]. Klaus Finkenzeller. “RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification,” Second Edition. 2003, John Wiley & Sons, Ltd.
[2]. 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.
[3]. Tao Cheng; Li Jin “Analysis and Simulation of RFID Anti-collision Algorithms,” The 9th International Conference on Advanced Communication Technology, Volume 1, 12-14 Feb. 2007 Page(s):697 – 701.
[4]. Tae-Wook Hwang, Byong-Gyo Lee, Young Soo Kim, Doug Young Suh, Jin Sang Kim, “Improved Anti-collision Scheme for High Speed Identification in RFID System,” 2006. ICICIC '06. First International Conference on Innovative Computing, Information and Control, Volume 2, 30-01 Aug. 2006 Page(s):449 – 452.
[5]. Cao Xiaohua, Zhou Qiang, “An Anti-Collision Algorithm Based on Subset-division and Dynamic Matching Mechanism for Intelligent Tags,” Control Conference, 2007. CCC 2007. Chinese, July 26 2007-June 31 2007 Page(s):576 – 579.
[6]. Tae-Wook Hwang, Byong-Gyo Lee, Young Soo Kim, Hoongee Yang, Jong-Gwan Yook, “An Anti-collision Method for Fast Recognition of Multiple RFID Tags,” The Joint International Conference on Optical Internet and Next Generation Network, 2006. COIN-NGNCON 2006, 9-13 July 2006 Page(s):287 – 290.
[7]. Ji Hwan Choi, Dongwook Lee, Hyuckjae Lee, “Bi-slotted tree based anti-collision protocols for fast tag identification in RFID systems,” IEEE Communications Letters, Volume 10, Issue 12, Dec. 2006 Page(s):861 – 863.
[8]. Ji Hwan Choi, Dongwook Lee, Hyoungsuk Jeon, Jongsub Cha,Hyuckjae Lee, “Enhanced Binary Search with Time-Divided Responses for Efficient RFID Tag Anti-Collision,”2007.ICC '07 IEEE International Conference on Communications, 24-28 June 2007 Page(s):3853 – 3858.
[9]. Bo Feng, Jin-Tao Li, Jun-Bo Guo, Zhen-Hua Ding. “ID-Binary Tree Stack Anticollision Algorithm for RFID,” ISCC '06. Proceedings. 11th IEEE Symposium on Computers and Communications, 2006, 26-29 June 2006 Page(s):207 – 212.
[10]. Don R. Hush, Cliff Wood, “Analysis of tree algorithms for RFID arbitration,” 1998 IEEE International Symposium on Information Theory, 1998. Proceedings, 16-21 Aug. 1998 Page(s):107.
[11]. Tsan-Pin Wang, “Enhanced binary search with cut-through operation for anti-collision in RFID systems,” IEEE Communications Letters, Volume 10, Issue 4, Apr 2006 Page(s):236 – 238.
[12]. Sung Hyun Kim, PooGyeon Park, “An Efficient Tree-Based Tag Anti-Collision Protocol for RFID Systems,” IEEE Communications Letters, Volume 11, Issue 5, May 2007 Page(s):449 – 451.
[13]. Jihoon Myung, Wonjun Lee, Srivastava Jaideep, Timothy K Shih, “Tag-Splitting: Adaptive Collision Arbitration Protocols for RFID Tag Identification,” IEEE Transactions on Parallel and Distributed Systems, Volume 18, Issue 6, June 2007 Page(s):763 – 775.
[14]. Jihoon Myung, Wonjun Lee, Srivastava Jaideep, “An Adaptive Memoryless Protocol for RFID Tag Collision Arbitration,” IEEE Transactions on Multimedia, Volume 8, Issue 5, Oct. 2006 Page(s):1096 – 1101.
[15]. Naval Bhandari, Anirudha Sahoo , Sridhar Iyer, “Intelligent Query Tree (IQT) Protocol to Improve RFID Tag Read Efficiency,”2006 ICIT'06 9th International Conference on Information Technology, 18-21 Dec. 2006 Page(s):46 – 51.
[16]. Jae-Min Seol,Seong-Whan Kim, “Collision-Resilient Multi-State Query Tree Protocol for Fast RFID Tag Identification” 2006 International Conference on Computational Intelligence and Security, Volume 2, 3-6 Nov. 2006 Page(s):1159 – 1162.
[17]. Jihoon Myung, Wonjun Lee, “Adaptive binary splitting: a RFID tag collision arbitration protocol for tag identification,” 2005 2nd International Conference on Broadband Networks, Volume 1,3-7 Oct. 2005 Page(s):347 – 355.
[18]. Jae-Min Seol, Seong-Whan Kim, “Collision-Resilient Multi-State Query Tree Protocol for Fast RFID Tag Identification,” 2006 International Conference on Computational Intelligence and Security, Volume 2, 3-6 Nov. 2006 Page(s):1159 – 1162.
[19]. Jihoon Myung, Wonjun Lee, Srivastava J, “Adaptive binary splitting for efficient RFID tag anti-collision” IEEE Communications Letters, Volume 10, Issue 3, Mar 2006 Page(s):144 – 146.
[20]. Jiho Ryu, Hojin Lee, Yongho Seok, Taekyoung Kwon, Yanghee Choi, “A Hybrid Query Tree Protocol for Tag Collision Arbitration in RFID systems,” IEEE International Conference on Communications, 2007. ICC '07, 24-28 June 2007 Page(s):5981 – 5986.
[21]. Jongho Park, Min Young Chung, Tae-Jin Lee, “Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection,” IEEE Communications Letters, Volume 11, Issue 5, May 2007 Page(s):452 – 454.
[22]. Jongho Park, Min Young Chung, Tae-Jin Lee, “Identification of RFID Tags in Framed-Slotted ALOHA with Tag Estimation and Binary Splitting,” 2006. ICCE '06 First International Conference on Communications and Electronics, 10-11 Oct. 2006 Page(s):368 – 372.
[23]. Junbong Eom,Tae-Jin Lee, “Framed-slotted ALOHA with estimation by pilot frame and identification by binary selection for RFID anti-collision,” 2007. ISCIT '07. International Symposium on Communications and Information Technologies, 17-19 Oct. 2007 Page(s):1027 – 1031.
[24]. Vogt, H. “Efficient Object Identification with Passive RFID Tags,” In international Conference on Pervasive Computing, LNCS, Springer-Verlag 2002.
[25]. Vogt, H. “Multiple Object Identification with Passive RFID Tags,” 2002 IEEE International Conference on Systems, Man and Cybernetics, Volume 3, p.6-9 Oct. 2002.
[26]. Xu Huang, Son Le, “Efficient Dynamic Framed Slotted ALOHA for RFID Passive Tags,” The 9th International Conference on Advanced Communication Technology, Volume 1, 12-14 Feb. 2007 Page(s):94 – 97.
[27]. Qingsong Peng, Ming Zhang, Weimin Wu, “Variant Enhanced Dynamic Frame Slotted ALOHA Algorithm for Fast Object Identification in RFID System,” 2007 IEEE International Workshop on Anti-counterfeiting, Security, Identification, 16-18 April 2007 Page(s):88 – 91.
[28]. Su-Ryun Lee, Sung-Don Joo, Chae-Woo Lee, “An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification,” Mobile and Ubiquitous Systems: The Second Annual International Conference on Networking and Services, 2005. MobiQuitous 2005, 17-21 July 2005 Page(s):166 – 172.
[29]. C.P.Wong, Quanyuan Feng, “Grouping based bit-slot ALOHA protocol for tag anti-collision in RFID systems,” IEEE Communications Letters, Volume 11, Issue 12, December 2007 Page(s):946 – 948.
[30]. Leian Liu, Shengli Lai, “ALOHA-Based Anti-Collision Algorithms Used in RFID System,” 2006. WiCOM 2006. International Conference on Wireless Communications, Networking and Mobile Computing, 22-24 Sept. 2006 Page(s):1 – 4.
[31]. Jae-Ryong Cha, Jae-Hyun Kim, “Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system,” 2006. CCNC 2006. 2006 3rd IEEE Consumer Communications and Networking Conference, Volume 2, 8-10 Jan. 2006 Page(s):768 – 772.
[32]. Wen-Tzu Chen, Guan-Hung Lin, “An Efficient Anti-Collision Method for Tag Identification in a RFID System,” IEICE Transactions on Communications, Volume E89-B,Dec. 2006.