臺灣博碩士論文加值系統

無線射頻辨識系統(Radio Frequency IDentification，RFID)在運作時，最困擾的就是訊號碰撞(Collision)問題，此問題將會造成整體系統效能降低。如何減少碰撞的問題，以提高其辨識效率是目前RFID系統極熱門的研究議題。本論文將針對RFID系統在運作時之碰撞問題提出兩種有效的解決方法。我們提出的兩種方法分別為SQT演算法(Stride Query Tree Algorithm)及MQSQT演算法(Minimal Query Set QT Algorithm)都是以Query Tree Algorithm(QT)為基礎並加以改良。其中SQT演算法將原來QT詢問標籤的方式改為跨層詢問的方式，結果顯示SQT可大幅降低詢問過程中所產生的碰撞次數，為了減少在跨層過程中帶來閒置(idle)次數過多的問題，我們也進一步修改了SQT詢問資訊的產生方式，以邏輯運算的方式找出下一個詢問節點，使整個系統能同時減少碰撞及閒置問題，此新方法稱為MQSQT，模擬結果顯示我們所提出的演算法在碰撞及閒置兩種問題上均獲得明顯的改善。

During the operation of Radio frequency Identification systems (RFID), the most difficult aspect is the problem of signal collision. The collision of RFID systems results in lower efficiency. How to decrease the problem of collision so as to enhance its identification rate is the hot issue of RFID systems. In this dissertation, we propose two efficient solutions, called Stride Query Tree (SQT) and Minimal Query Set QT (MQSQT), to solve the collision problem of RFID systems respectively. All of the SQT and MQSQT are Query Tree -Based algorithms which are based on QT algorithm to improve their performance. The SQT algorithm changes the original layer-by-layer query of tags into the method of striding-layer tag query. It shows that the SQT therefore substantially decreased the collision times during querying. In order to decrease the times of idle during tag query in SQT, we proposed the MQSQT algorithm that further modified the production method of the next query string by XOR logic operation. This enables the whole system to decrease collision and idle problems in a tag identification process. The simulation results show that both problems of collision and idle were improved significantly.

目錄
中文摘要 IV
Abstract V
致謝 VI
目錄 VII
表目錄 IX
圖目錄 X
第一章 序論 1
1.1 前言 1
1.2 RFID之特性 4
1.3 RFID之工作頻率 6
1.4 研究動機 7
1.5 論文架構 10
第二章 相關研究 11
2.1 ALOHA Algorithm 11
2.2 Binary Tree Algorithm 14
2.3 Query Tree Algorithm 15
2.4 其他相關研究 18
第三章 跨層詢問反碰撞演算法 22
3.1 SQT 演算法 22
3.2 MQSQT 演算法 26
第四章 模擬與結果 34
4.1 模擬參數設定 34
4.2 模擬結果分析 ..35
第五章 結論 45


表目錄
表1.1 RFID與條碼系統比較表 2
表1.2 標籤特性比較表 3
表1.3 RFID之分類與特性比較表 7
表2.1 BT Algorithm運作流程 16
表2.2 QT Algorithm運作流程 17
表3.1 SQT Algorithm運作流程 24
表3.2 流程圖參數定義表 27
表3.3 MQSQT Algorithm運作流程 33
表4.1 模擬之系統參數設定 34
表4.2 標籤密度模擬參數設定 39
表4.3 標籤密度與碰撞次數關係表 41
表4.4 標籤密度與閒置次數關係表 42
表4.5 標籤密度與總詢問次數關係表 44


圖目錄
圖1.1 RFID系統之運作方式 2
圖1.2 Tag-Tag碰撞示意圖 8
圖1.3 Tag-Reader碰撞示意圖 9
圖1.4 Reader-Reader碰撞示意圖 10
圖2.1 ALOHA Algorithm 12
圖2.2 Slotted-ALOHA Algorithm 13
圖2.3 BT Algorithm之詢問方式 15
圖2.4 QT Algorithm之詢問方式 17
圖2.5 SDMA示意圖 18
圖2.6 FDMA示意圖 19
圖2.7 CDMA示意圖 20
圖2.8 TDMA 示意圖 21
圖3.1 SQT Algorithm 之詢問方式 23
圖3.2 SQT演算法 25
圖3.3 MQSQT演算法之流程圖 28
圖3.4 MQSQT演算法 29
圖3.5 紀錄回應標籤目前詢問位置下兩個UID位元 30
圖3.6 邏輯運算運作流程 30
圖4.1 標籤數量與碰撞次數關係 35
圖4.2 標籤數量與閒置次數關係 36
圖4.3 標籤數量與總詢問次數關係 37
圖4.4 標籤密度與碰撞次數關係 40
圖4.5 標籤密度與閒置次數關係 41
圖4.6 標籤密度與總詢問次數關係 43

參考文獻
[1]C. P. Wong and Q. Feng, “Grouping based Bit-Slot ALOHA Protocol for Tag Anti-Collision in RFID Systems,” IEEE Communications Letter, Dec. 2007, vol. 11, pp. 946-948.
[2]C. S. Kim, K. L. Park, H. C. Kim and S. D. Kim, “An Efficient Stochastic Anti-Collision Algorithm using Bit-Slot Mechanism,” PDPTA04, 2004, pp.652-656.
[3]H. Vogt, “Efficient object identification with passive RFID tags,” Proc. of the 1st Int’l Conf., on Pervasive Computing, 2002, pp. 98-113.
[4]J. Cha and J. Kim, “Novel Anti-Collision Algorithms for Fast Object Identification in RFID System,” in Proc. of Parallel and Distributed System, Jul. 2005, vol. 2, pp. 63-67.
[5]J. H. Chio, D. Lee and H. Lee, “Bi-Slotted Tree based Anti-Collision Protocols for Fast Tag Identification in RFID Systems,” IEEE Communications Letter, Dec. 2006, vol. 10, pp. 861-863.
[6]J. Kim, W. Lee, J. Yu, J. Myung, E. Kim and C. Lee, “Effect of Localized Optimal Clustering for Reader Anti-Collision in RFID Networks: Fairness Aspects to the Readers,” Proceedings 14th International Conference on Computer Communications and Networks, Oct. 2005, vol.1, pp. 497-502.
[7]J. Myung, W. Lee, and J. Srivastava, “Adaptive Binary Splitting for Efficient RFID Tag Anti-Collision,” IEEE Communications Letter, Mar. 2006, vol. 10, no. 3, pp. 144-146.
[8]J. Myung and W. Lee, “Adaptive Splitting Protocols for RFID Tag Collision Arbitration,” MobiHoc, May 2006, Florence, Italy, pp. 202-213.
[9]J. Park, M. Chung and T. J. Lee, “Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selecti on,” IEEE Communications Letter, 2007, vol. 11, no. 5, pp. 452-454.
[10]Jung-Chung Lee, “An Adaptive Anti-Collision Algorithm towards Efficient RFID Tag Identification,” Department of Computer Science and Information Engineering, Chung-Hua University, Taiwan, Jul. 2008.
[11]L. Liu and S. Lai, “ALOHA-based anti-collision algorithm used in RFID system,” Proc. of the Int’l Conf., on Wireless Communications, Networking and Mobile Computing (WiCOM 2006), Sep. 2006, pp. 1-4.
[12]Ming-Kuei Yeh, Jehn-Ruey Jiang, Shing-Tsaan Huang, “Adaptive splitting and pre-signing for RFID tag anti-collision,” Computer Communications , 15 Nov. 2009, vol. 32, pp. 1862-1870.
[13]N. Abramson, “The ALOHA system-another alternative for computer communications,” Proc. of AFIPS Spring Joint Computer Conf., 1970, vol. 37, pp. 281-285.
[14]S. H. Kim and P. Park, “An Efficient Tree-Based Tag Anti-Collision Protocol for RFID Systems,” IEEE Communications Letters, May 2007, vol. 11, pp. 449-451.
[15]S. Lee, S. Joo, C. Lee, “An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification,” in Proc. MobiQuitous, Jul. 2005, vol. 2, pp. 166-172.
[16]T. Wang, “Enhanced Binary Search with Cut-through Operation for Anti-Collision in RFID Systems,” IEEE Communications Letter, Apr. 2006, vol. 10, no. 4, pp. 236-238.
[17]Zhi-Ying Yang, Jun-Liang Chen, Zhi-Jun Mao, “Study on the Performance of Tag-Tag Collision Avoidance Algorithms in RFID System,” Third Asia International Conference on Modeling & Simulation. 2009, pp. 757-760.
[18]邱瑩青，RFID實踐：非接觸式智慧卡系統開發，學貫行銷，2007。
[19]陳昱仁、廖耕億、許建隆、林仲志，RFID概論，華泰文化，2009。
[20]戴江淮，RFID工程概論，學貫行銷，2008。