臺灣博碩士論文加值系統

近年來，由於無線通訊技術的發展與進步，使得無線設備被廣泛使用在各種領域之中，而無線技術的成熟、手持式設備功能的提昇，更促成行動通訊、行動計算的可行性，前述技術的應用為人們帶來更多的便利性及多元化的服務。無線射頻辨識系統(Radio Frequency Identification, RFID)為無線通訊中一項新興的應用，無線射頻辨識(RFID)系統乃是一種透過無線射頻(RF)技術的自動辨識系統，簡而言之，此項技術是透過無線電波來傳遞識別資料，可用來快速辨識出環境中各種不同用途的tag，透過tag中所預存的資訊來取得所需的各種資料。當多個tag同時傳送它們的唯一識別碼(Unique Identification, UID)給reader時，則會造成辨識上的干擾，造成reader無法準確的辨識出每一個tag的UID，此現象稱之為tag碰撞，故需要設計一個有效預防碰撞演算法，來改善reader的辨識率，以達到快速準確辨識出每一個tag，此為目前RFID重要且熱門的研究議題。
在此論文中，我們提出了一個有效預防碰撞的方法，稱之為bit competed algorithm(BCA)，來改善無線射頻辨識系統辨識上所發生的碰撞問題，進而提昇系統的辨識效能。在我們所提出的方法中，reader會將同時回應請求傳送訊息之tag的UID進行優先權競爭，所利用的技巧為以簡單布林代數的或運算(Boolean OR)進行逐位元(bit-by-bit)優先權競爭。我們進行大量電腦模擬分析，並和已被提出的預防碰撞演算法進行比較，實驗的結果顯示我們所提出的方法可有效改善碰撞問題，提昇系統整體的效能，比其他方法有更佳的效能。

Radio frequency identification (RFID) is an automatic identification system working through radio frequency (RF). Tag collision occurs while two or more than two tags deliver their unique identification (UID) to the reader at the same time. Since collision, which would significantly affect the efficacy of RFID, has been one of the major study issues for RFID technology, we have developed a solution, bit competed algorithm (BCA), to solve the collision problem occurred in RFID system and consequently improve the efficacy of RFID. While receiving the UIDs, the reader will identify the tags through Boolean OR operation for bit-by-bit priority competition. The massive computer simulation results and the comparison with other algorithms for collision prevention proved our method can effectively solve the collision problem and improve the efficacy of RFID system.

目錄
摘要 IV
Abstract VI
致謝 VIIII
目錄 VIIIII
圖目錄 XI
表目錄 XIII
第一章 序論 1
1.1 研究背景 1
1.2 RFID系統架構 3
1.3 RFID的優缺點 6
1.4 RFID標準 9
1.5 研究動機 17
1.6 論文架構 20
第二章 相關研究 21
2.1 相關研究方法簡介 21
2.2 Tree-based演算法 26
2.2.1 Binary Tree演算法 27
2.2.2 Query Tree演算法 30
2.3 Aloha-based演算法 32
2.3.1 Pure-Aloha演算法 33
2.3.2 Slotted-Aloha演算法 34
2.4 問題探討 36
第三章 Bit Competed演算法 39
3.1 BCA演算法介紹 39
3.2 BCA演算法之標籤存取優先權競爭程序 40
3.3 BCA流程圖及演算法 42
3.4 實例解說 45
第四章 實驗 47
4.1 模擬實驗之假設 47
4.2 系統模組 49
4.3 實驗設定 50
4.4 實驗結果 51
4.4.1 標籤總數與辨識效能的關係 51
4.4.2 標籤UID位元長度與辨識效能的關係 54
第五章 結論與未來展望 59
5.1 結論 59
5.2 未來展望 59
參考文獻 60

圖目錄
圖1-1. 無線射頻辨識系統 2
圖1-2. EPC基本編碼結構 14
圖1-3. RFID運作程序 15
圖1-4. 標籤碰撞 18
圖1-5. 讀取器碰撞 19
圖2-1. 空間分割多重存取 22
圖2-2. 分頻多重存取 23
圖2-3. 分碼多重存取 24
圖2-4. 分時多重存取 25
圖2-5. Binary Tree演算法 28
圖2-6. Query Tree演算法 31
圖2-7. Pure-Aloha演算法 34
圖2-8. Slotted-Aloha演算法 36
圖3-1. n bits UID位元示意圖 40
圖3-2. BCA流程圖 42
圖3-3. BCA演算法 43
圖3-4. BCA競爭程序 44
圖4-1. 標籤總數與碰撞次數關係 52
圖4-2. 標籤總數與請求回應次數關係 53
圖4-3. 標籤總數與請求-回應總位元(bits)次數關係 54
圖4-4. 標籤UID位元長度與碰撞次數關係 55
圖4-5. 標籤UID位元長度與請求回應次數關係 56
圖4-6. 標籤UID位元長度與請求-回應總位元(bits)次數關係 57

表目錄
表一、電子標籤的類型比較 5
表二、RFID與條碼的優缺點 8
表三、RFID常用頻率範圍 11
表四、各國開放供RFID使用之UHF頻段 11
表五、RFID Tag的種類及應用領域 12
表六、Binary Tree演算法 29
表七、Query Tree演算法 32

[1]D. Shih, P. L. Sun, D. C. Yen and S. M. Huang, “Taxonomy and Survey of RFID Anti-Collision Protocols,” Computer and Communications, 2006, vol. 29, pp. 2150-2166.
[2]T. Zhijun and H. Yigang, “Research of Multi-Access and Anti-Collision Protocols in RFID Systems,” Anti-counterfeiting, Security, Identification, IEEE International Workshop on 16-18, Apr. 2007, pp. 377-380.
[3]J. H. Chio, D. Lee and H. Lee, “Query Tree-based Reservation for Efficient RFID Tag Anti-Collision,” IEEE Communications Letter, Apr. 2006, vol. 10, no. 4, pp. 236-238.
[4]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.
[5]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.
[6]J. Myung and W. Lee, “Adaptive Splitting Protocols for RFID Tag Collision Arbitration,” MobiHoc, May. 2006, Florence, Italy, pp. 202-213.
[7]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.
[8]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.
[9]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.
[10]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.
[11]J. Park, M. Chung and T. J. Lee, “Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection,” IEEE Communications Letter, 2007, vol. 11, no. 5, pp. 452-454.
[12]S. Lee, S. Joo and C. Lee, “An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification,” in Proc. MobiQuitous, Jul. 2005, vol.2, pp. 166-172.
[13]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.
[14]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.
[15]J. Ho, D. W. Engels and S. E. Sarma, “HiQ: A Hierarchical Q-Learning Algorithm to Solve the Reader Collision Problem,” SAINTW, Jan. 2006, pp. 1-4.
[16]J. Waldrop, D. W. Engels and S. E. Sarma, “Colorwave: An Anti-Collision Algorithm for the Reader Collision Problem,” in IEEE Wireless Communications and Networking Conference, Mar. 2003, vol. 2, pp. 1206-1210.
[17]S. M. Birari and S. Iyer, “Mitigating the Reader Collision Problem in RFID Networks with Mobile Readers” Dissertation for Master of Technology, Indian Institute of Technology, 2005, India.
[18]A. M. Bonuccelli, F. Lonetti and F. Martelli, “Instant Collision Resolution for Tag Identification in RFID Networks,” Ad Hoc Networks, Nov. 2007, vol. 5, issue. 8, pp. 1220-1232.
[19]A. M. Bonuccelli, F. Lonetti and F. Martelli, “Tree Slotted ALOHA: A New Protocol for Tag Identification in RFID Networks, World of Wireless, Mobile and Multimedia Networks, WoWMoM, Aug. 2006, vol. 1, pp. 608-614.
[20]W. C. Chen, S. J. Horng and F. Pingzhi, “An Enhanced Anti-Collision Algorithm in RFID Based on Counter and Stack,” Systems and Networks Communications, ICSNC 2007. Second International Conference on 25-31 Aug. 2007, vol. 1, pp. 21-21.
[21]S. W. Jin and K. J. Geun, “Partitioning of Tags for Near-Optimum RFID Anti-Collision Performance,” Wireless Communications and Networking Conference, WCNC 2007 IEEE 11-15 Mar. 2007, vol. 1, pp. 1673-1678.
[22]C. Tao and L. Jin, “Analysis and Simulation of RFID Anti-Collision Algorithms,” Advanced Communication Technology, the 9th International Conference on 12-16, Feb. 2007, vol. 1, pp. 697-701.
[23]C. Yinghua and Y. Zhao, “Mathematical Analysis for Binary Tree Algorithm in RFID,” Vehicular Technology Conference, VTC Spring on 11-14, May. 2008, vol. 1, pp. 2725-2729.
[24]K. Finkenzeller, RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification(2003), 2nd ed, New York: Wiley.
[25]A. S. Tanenbaum, Computer networks, 2003, 2nd. ed, New Jersey, U.S.A.
[26]EPCglobal, TW http://www.epcglobal.org.tw/epcg/jsp/a11.htm.
[27]日經BP RFID技術編輯部，RFID 技術與應用，旗標出版社，台北，2004。
[28]李建斌、張復閔，RFID室內定位挑戰重重，新通訊元件雜誌，台北，2006。
[29]陳宏宇，RFID系統入門-無線射頻辨識系統，文魁資訊，台北，2004。