臺灣博碩士論文加值系統

在無線射頻辨識(Radio Frequency Identification, RFID)系統中，讀取器(Reader)與標籤(Tag)相互溝通的過程，若讀取器同時接收到多個標籤之回覆訊息將發生碰撞。由於碰撞次數的增加，會使得讀取器詢問次數和傳輸資料量劇增，進而導致系統整體效能降低，本論文主要著重在標籤碰撞的議題上，我們所提出反碰撞演算法(Retentive Backtracking Bit Competed Anti-Collision Algorithm, RBBCA)可有效減少標籤回應讀取器時發生之碰撞次數。在RBBCA演算法中，讀取器會將競爭過程失敗標籤的競爭資訊記錄於堆疊中，若有多個標籤同時競爭，在每次成功辨識一個標籤後，僅需從堆疊抓取競爭資訊(即前次競爭失敗標籤的UID和下一個競爭位元的位置)從前次競爭停駐點繼續進行辨識，不但不需重頭詢問標籤UID(Unique Identification)可減少資料傳輸量，同時也減少參與競爭的標籤數，因此可大幅減少碰撞發生率和詢問次數。將我們的反碰撞演算法和其它演算法以電腦模擬進行效能評估，結果顯示無論在碰撞次數、詢問次數、標籤辨識率、讀取器計算量、請求及回應總位元數的額外負擔(overhead)等均可獲得有效改善。

In the process of communication between reader and tag in Radio Frequency Identification systems (RFID), collisions occur when the reader simultaneously receives reply messages from multiple tags. Reader request frequency and transmitted overhead both increase sharply as the number of collisions increases, thus, the overall efficiency of the system decreases. In this study, we proposed an retentive backtracking bit competed anti-collision algorithm (RBBCA) to effectively reduce the number of collisions when a tag responds to the reader. In the RBBCA algorithm, the reader identifies the competitive information of the process, which it will be pushed in the stack. If there are multiple competing tags, once a tag is successfully identified, the competitive information (i.e. UID of the previous competition failure tag and the position of next competitive bit) can be pop from the stack, and identification proceeds from the previous competition stop point, thus, there is no need to re-inquire tag Unique Identification (UID). Data transmission volume can be thus reduced. The efficiency of the proposed anti-collision algorithm and other algorithms were evaluated through computer simulation. The results showed that the collision number, request number, identification rate, reader calculation amount, and request-response number (overhead) were effectively improved.

目錄
中文摘要 ………………..…………………………………………………...IV
Abstract ………………..……………………………………………………V
致謝 ………………..…………………………………………………...VI
目錄 ………………..…………………………………………………..VII
表目錄 ………………..……………………………………………….......IX
圖目錄 ………………..…………………………………………………....X
第一章 序論……………………………...…………………………...….....1
1.1 前言…...…………………………...………………….……...….....1
1.2 RFID系統架構…...…………………………..……………...……..3
1.3 工作使用頻率………………………………...…………..…...…...7
1.4 研究動機…..……………………………………...…………...…...9
1.5 論文架構………………………………………...…………...…...13
第二章 相關研究…..……………………………….………………...…...14
2.1 Tree-based演算法……………………………...…………...….....15
2.1.1 Binary tree演算法……………………………...……...……..16
2.1.2 Query tree演算法……………………………...……...……...18
2.2 ALOHA-based演算法………………………...…………...……..20
2.2.1 Pure ALOHA演算法……………………………...……...…..20
2.2.2 Slotted ALOHA演算法……………………………...…….....21
2.3 Bit Competed Algorithm反碰撞演算法………………………….23
2.4 相關通訊技術多重存取方法之介紹………………………….…24
第三章 RBBCA演算法…...………………………………..………...…...28
3.1 RBBCA演算法步驟流程…………………………….……...…...28
3.2 實例說明RBBCA演算法…..……………………...………...…...34
第四章 模擬與結果……….…………………..……………………...…...37
4.1 模擬參數設定……….…………………..…………………...…...37
4.2 模擬結果之分析…………………………………………......…...38
第五章 結論與未來展望……………………………………………….....46
5.1 結論…...…………………………………………………………..46
5.2 未來展望…...………………………………………………...…...46
參考文獻…...……..………………………...…………………………...…...48

表目錄
表1.1 條碼與RFID特性比較表……………………………………....…...2
表1.2 RFID標籤類型之比較表….....……………………..……………......6
表1.3 RFID之頻率比較表……………...………………………………......8
表2.1 標籤及UID……………………………………...………………......15
表2.2 BT演算法運作流程……………..……………………...………......17
表2.3 QT演算法運作流程………………………………….......................19
表3.1 演算法流程圖參數之定義………………………………………….31
表4.1 軟硬體描述………………………………………………………….37
表4.2 模擬參數設定……………………………………………………….38
表4.3 標籤密度之模擬參數設定………………………………………….45


圖目錄
圖1.1 RFID系統架構圖…………………………………………………….3
圖1.2 Tag to Tag碰撞……………………...…………………...………….10
圖1.2 Reader to Reader碰撞 …...………………………………..………...11
圖1.4 Reader to Tag碰撞……….……………………………………….....12
圖2.1 BT演算法詢問方式…..…...……………………………………..…16
圖2.2 QT演算法詢問方式………………………………………………...18
圖2.3 Pure ALOHA演算法示意圖…………………………………...…...21
圖2.4 Slotted ALOHA演算法示意圖…………………………………......22
圖2.5 TDMA示意圖…..…...……………………………..…………….…24
圖2.6 CDMA示意圖…………………………………….………………...25
圖2.7 FDMA示意圖……………………………………..…………...…...26
圖2.8 SDMA示意圖……………………………………..……………......27
圖3.1 RBBCA演算法流程圖…………………………………………......32
圖3.2 RBBCA演算法之運作流程…………………….………………......33
圖4.1 標籤數量與碰撞次數關係圖……………..…………….………......39
圖4.2 標籤數量與總詢問次數關係圖………………………………….....40
圖4.3 標籤數量與讀取器計算量關係圖………………………………….41
圖4.4 標籤數量與overhead關係圖……………………………………….42
圖4.5 標籤數量與辨識率關係圖………………………………………….43
圖4.6 標籤密度與讀取器計算量關係圖………………………………….45

[1]許文力，無線射頻辨識系統預防碰撞演算法之設計，碩士論文，朝陽科技 大學資訊工程系，台中，2009。
[2]鄧嘉豪，RFID跨層詢問反碰撞演算法之設計，碩士論文，朝陽科技大學資訊工程系，台中，2010。
[3]謝建新、游戰清、張義強、戴青雲，吳權昌 校定，RFID理論與實務-無線射頻識別技術，網亦資訊，2006。
[4]Steven Shepared，林宛如 譯，RFID無線射頻辨識系統，碁峯資訊，2008。
[5]張晴翔、王偉驎，RFID無線射頻辨識系統，滄海書局，2007。
[6]Klaus Finkenzeller，吳曉峰、陳大才 譯，RFID手冊無線智慧卡與識別卡之基礎與應用，全華科技圖書，2007。
[7]D. Shih, P. L. Sun, D. C. Yen, and S. M. Huang, “Taxonomy and survey of RFID anti-collision protocols,” Computer and Communications, Jul 2006, vol.29, pp. 2150–2166.
[8]D. K. Klair, K. W. Chin, and R. Raad, “A Survey and Tutorial of RFID Anti-Collision Protocol,” Communications Surveys & Tutorials, Apr 2010, vol.12, pp. 400–421.
[9]T. Cheng, and L. Jin, “Analysis and simulation of RFID Anti- collision Algorithms” The 9th International Conference on Advanced Communication Technology, Feb 2007, pp.697-701.
[10]D. W. Engels, and S. E. Sarma, “The Reader Collision Problem,” IEEE International Conference on Systems Man and Cybernetics, Oct 2002, vol. 3, pp. 6.
[11]U. S. Mohammed, and M. Salah, “Parallel Binary Tree Splitting Protocol for Tag Anti-collision in RFID Systems,” The 4th Inter- national Design and Test Workshop, Nov 2009, pp. 1–6.
[12]T. F. Shih, and C. H. Teng, “The Design of a Stride Query Tree Algorithm for RFID Systems,” The 3th International Conference on Computational Intelligence, Communication Systems and Networks, Jul 2011, pp. 108-113.
[13]全瑞順，RFID概論與應用，全華圖書，2007。
[14]Agrawal、Zeng，吳明蔚 譯，無線通訊，東華書局，2006。
[15]黃奇津，第二代無線射頻辨識超高頻協定之讀取器及標籤運作原理，碩士論文，中正大學通訊工程學系，嘉義，2008。
[16]王亭懿，第二代無線射頻辨識超高頻協定之讀取器及標籤運作原理，碩士論文，輔仁大學資訊工程研究所，台北，2009。
[17]C. Law, K. Lee, and K. Y. Siu, “Efficient Memoryless Protocol for Tag Identification,” DIALM Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Computations, Aug 2000, pp. 75–84.
[18]W. D. Wang, Y. H. Zhang, Y. Sang, and S. F. Wang, “Analysis of Anti-Collision Algorithms in RFID System,” IEEE International Conference on Communications Technology and Application, Oct 2009, pp. 58–62.
[19]C. C. Liu, and Y. T. Chan, “Tag quantity estimation for RFID based on probability,” International Symposium on Computer Communication Control and Automation, May 2010, vol.1, pp. 264–267.
[20]H. Vogt, “Efficient Object Identification with Passive RFID Tags,” The first International Conference on Pervasive Computing, Aug 2002, pp. 98–113.
[21]J. R. Cha, and J. H. Kim, “Dynamic Framed Slotted ALOHA Algorithms using Fast Tag Estimation Method for RFID System,” Third IEEE Consumer Communications and Networking Conference, Jan 2006, vol.2, pp. 768–772.
[22]N. W. Lo, E. Winata, and K. H. Yeh, “Adaptive Delay Splitting for Efficient RFID Tag Identification,” Fourth International Conference on Innovative Computing, Information and Control, Dec 2009, pp. 79–82.
[23]T. F. Shih, and W. L. Hsu, “An efficient Anti-Collision Algorithm for RFID System,” The 8th WSEAS International Conference on ACACOS, May 2009, pp. 488–494.
[24]邵喻美、潘育群譯，電腦網路，東華書局，2003。
[25]J. S. Cho, J. D. Shin, and S. K. Kim, “RFID Tag Anti-Collision Protocol: Query Tree with Reversed IDs,” The 10th International Conference on Advanced Communication Technology, Feb 2008, vol.3, pp. 225–230.
[26]J. M. Seol, and S. W. Kim, “Efficient Collision-Resilient RFID Tag Identification using Balanced Incomplete Block Design Code,” The 6th IEEE International Conference on Computer and Information Technology, Sep 2006, pp. 220.
[27]M. K. Yeh, J. R. Jiang, and S. T. Huang, “Adaptive splitting and pre-signaling for RFID tag-collision,” Computer Communications, Nov 2009. vol. 32, pp. 1862–1870.
[28]S. S. Kim, Y. H. Kim, and K. S. Ahn, “An Enhanced Slotted Binary Tree Algorithm with Intelligent Separation in RFID Systems,” IEEE Symposium on Computers and Communications, Jul 2009, pp. 237–242.
[29]S. H. Seo, and S. C. Park, “Efficient RFID Anti-collision scheme with multi-collision reflected frame request,” The 6th IEEE Consumer Communications and Networking Conference, Jan 2009, pp. 1–5.
[30]S. R. Lee, S. D. Joo, and C. W. Lee, “An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification,” The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, Jul 2005, pp. 166–172.
[31]S. Makwimanloy, P. Kovintavewat, U. Ketprom, and C. Tantibundhit, “A Novel Anti-Collision Algorithm for High-Density RFID Tags,” The 6th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology, May 2009, vol.2, pp. 848–851.
[32]M. A. Bonuccelli, F. Lonetti, and F. Martelli, “Instant collision resolution for tag identification in RFID networks,” Ad Hoc Networks, Nov 2007, vol. 5, pp. 1220-1232.
[33]S. M. Wasikon, and S. Zurinah, “A framework of tag anti-collision algorithm for fast identification in RFID system,” International Conference on Computer and Communication Engineering, May 2008, pp. 1019-1022.