臺灣博碩士論文加值系統

一個有效率的RFID系統在進行標籤辨識時一定會盡力避免訊號碰撞的產生，訊號碰撞會導致訊號傳遞失敗，造成標籤辨識的障礙，因此，如何有效的提升標籤辨識效率，避免訊號碰撞，便成為近年來在RFID技術研究上相當熱門的
議題。

運用防碰撞演算法是無射射頻辨識系統實現標籤快速辨識的關鍵，本研究透過Vogt 對Framed Slotted ALOHA演算法辨識過程的分析並引進馬可夫鏈來對其辨識過程建立轉移機率矩陣，我們針對其所推導的馬可夫鏈轉移機率矩陣去做修正與改善，在更貼近實務操作的情況下，我們控制每回合欲辨識的標籤數，建立新的轉移機率矩陣，在與Vogt的方法比較之下，我們的方法大幅地減少了辨識完成所需的回合數，意即大幅提升了辨識效率。

An efficient RFID system need to avoid tag-collision when doing tag
identification. Tag-collision leads to the failure of signal transmission making tag identification failed. Therefore, how to enhance the efficiency of tag identification by avoiding tag-collision becomes a popular topic in the research of RFID technology in recent years.

Using anti-collision algorithm is the key of RFID system to identify tags rapidly. In this research, we propose a new framed slotted ALOHA algorithm initially proposed by Vogt. Vogt analyzed the identification process of the framed slotted ALOHA algorithm by a Markov chain model. To be more close to the real situation, we revise Vogt’s Markov model by controlling the number of tags to be identified in each round. Empirical results show that the proposed method significantly reduces the number of read cycles, and significantly improves the identification efficiency.

第一彰 導論……………………………………………………………………………-1-
1.1 研究動機………………………………………………………………………-1-
1.2 研究目的………………………………………………………………………-2-
1.3 論文架構………………………………………………………………………-2-

第二章 理論與文獻探討………………………………………………………………-3-

2.1 Tree-based演算法……………………………………………………………-3-
2.2 ALOHA-based演算法…………………………………………………………-6-
2.3馬可夫鏈………………………………………………………………………-9-
2.3.1馬可夫鏈之概述…………………………………………………………-9-
2.3.2馬可夫鏈之基本定義……………………………………………………-9-
2.3.3運用馬可夫鏈於Frame Slotted ALOHA演算法…………………………-11-

第三章 研究方法………………………………………………………………………-14-

第四章 實驗結果………………………………………………………………………-17-

第五章 結論……………………………………………………………………………-22-

參考文獻……………………………………………………………………………………-23-

[1]. H. Vogt, “Efficient Object Identification with Passive RFID Tags,” in Proceedings International Conference on Pervasive Computing, pp.98-113, Apr, 2002.
[2]. J. Myung, W. Lee, and J. Srivastava, “Adaptive binary splitting for efficient RFID tag anti-collision,” IEEE Commun. Lett., vol. 10, pp.144–146, Mar. 2006.
[3]. Yuan-Cheng Lai, and Chih-Chung Lin, “Two Blocking Algorithms on Adaptive Binary Splitting: Single and Pair Resolutions for RFID Tag Identification, ” IEEE Trans. Networking, vol. 17, pp.962-975, Jun 2009.
[4]. J. Myung, W. Lee, and T. K. Shih, “An adaptive memoryless protocol for RFID tag collision arbitration,” IEEE Trans. Multimedia, vol. 8, pp.1096–1101, Oct. 2006.
[5]. J. Ryu, H. Lee, Y. Seok, T. Kwon, and Y. Choi, “An hybrid query tree protocol for tag collision arbitration in RFID systems,” IEEE International conference on Communications, Jun. 2007.
[6]. J.R. Cha and J.H. Kim, “Novel anti-collision algorithms for fast object identification in RFID system,” in Proc. Parallel and Distibuted System, vol. 2, pp. 63-67, Jul. 2005.
[7]. J. R. Cha and J. H. Kim, “Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system,” IEEE 3rd Consumer Communications and Networking Conference, pp. 768-772, Jan. 2006.
[8]. 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, pp. 166-172, Jul. 2005.
[9].高孔廉與張緯良,“作業研究, ”五南圖書出版有限公司, 台北, 2000.
[10]. Armstrong, B. and D. Davis, “Finite Mathematics,” Prentice Hall, New Jersey ,2003.
[11].李朝賢,“作業研究概論,”弘業文化實業股份有限公司, 台北, 1977.
[12].鍾雲恭譯, B. E. Gillett著,“作業研究FORTRAN之應用,”道明出版社, 台北, 1983.
[13].楊蓉昌與趙浡霖,“作業研究(計畫管制), ”新學識文教出版中心, 台北, 1988.
[14].台灣科技大學楊維寧博士, “統計學,”新陸書局, 台北, 2007.