簡易檢索 / 詳目顯示

研究生: 蕭令彥
Ling-yen Hsiao
論文名稱: 具有阻隔技術與動態縮減之無線射頻反碰撞演算法
RFID Anti-Collision Algorithms with Blocking Technology and Dynamic Condensation
指導教授: 賴源正
Yuan-Cheng Lai
口試委員: 陳彥文
Yen-Wen Chen
黎碧煌
Bih-Hwang Lee
學位類別: 碩士
Master
系所名稱: 管理學院 - 資訊管理系
Department of Information Management
論文出版年: 2008
畢業學年度: 96
語文別: 英文
論文頁數: 37
中文關鍵詞: 無線射頻辨識反碰撞偵測協定樹架構演算法標籤碰撞標籤辨識碰撞解決
外文關鍵詞: RFID, Anti-collision protocol, Tree based algorithms, Tag Anti-collision, Tag Identification, Collision Resolution
相關次數: 點閱:296下載:0
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 針對無線射頻辨識反碰撞問題,本篇論文以適性二元分割演算法(Adaptive Binary Splitting, ABS)為基礎提出兩種新的演算法,阻隔適性二元分割演算法(Blocking ABS, BABS)與動態阻隔適性二元分割演算法(Dynamic Blocking ABS, DBABS)。這兩種演算法繼承了ABS的記憶特性以避免己辨識標籤彼此之間的碰撞,BABS採用了阻隔機制,DBABS更是進一步的利用了動態縮滅機制以提升效能。阻隔機制防止了未辨識的標籤碰撞己辨識的標籤,動態縮滅機制則是滅少之前己辨識的標籤從讀取器的訊號範圍離開時產生的空閒時間(Idle Time)。而在數學分析與模擬結果中,BABS與DBABS都能於辨識延遲(Identification Delay)上展現出優於ABS的效能。


    In this thesis, based on Adaptive Binary Splitting (ABS), two tree-based algorithms, blocking ABS (BABS) and dynamic blocking ABS (DBABS), are proposed for RFID tag anti-collision. They inheriting the features from ABS gain the information of identified tags to avoid collisions caused from staying tags colliding to each other. BABS uses the blocking mechanism and DBABS further adopts dynamic condensation. The blocking mechanism prevents collisions between identified tags and non-identified tags and dynamic condensation reduces the idle times caused from leaving tags in the identification process. Analytical and simulation results show that they have the better performance than ABS on identification delay.

    TABLE OF CONTENTS 中文摘要 I ABSTRACT II 誌 謝 III TABLE OF CONTENTS IV LIST OF FIGURES V Chapter 1. Introduction 1 Chapter 2. Background 3 2.1. Binary Tree (BT) 3 2.2. Adaptive Binary Splitting (ABS) 5 Chapter 3. Blocking ABS (BABS) 8 3.1. The procedure of BABS 8 3.2. A Example of BABS 11 Chapter 4. Dynamic Blocking ABS (DBABS) 12 4.1. The procedure of DBABS 13 4.2. A Example of DBABS 17 Chapter 5. Performance Analysis 18 Chapter 6. Simulation and Performance Comparison 22 6.1. Impact of staying tags and arriving tags 22 6.2. Impact of the tag mobility velocity 26 6.3. Impact of the tag stationary probability 26 6.4. Impact of the number of tags 28 Chapter 7. Conclusion 29 References 30 LIST OF FIGURES Fig. 1 Process of tag identification for BT 4 Fig. 2 Process of tag identification for ABS 7 Fig. 3 Pseudo code of BABS 10 Fig. 4 Process of tag identification at BABS 11 Fig. 5 Comparison of BT and OBT in condensation mechanism 13 Fig. 6 Pseudo code of DBABS 15 Fig. 7 Optimal CR 16 Fig. 8 OBT for collisions of staying tags in DBABS 16 Fig. 9 Process of tag identification at DBABS 17 Fig. 10 The simulation results with fixed ra and increasing rs 24 Fig. 11 The simulation results with fixed rs and increasing ra 25 Fig. 12 The simulation results with increasing velocity 27 Fig. 13 The simulation results with increasing stationary probability 27 Fig. 14 The simulation results with increasing number of tags 28

    [1] N. Abramson, “The Aloha System—Another Alternative for Computer Communications,” Proc. Fall Joint Computer Conf., Am. Federation of Information Processing Soc. Conf, vol. 37, pp. 281-285, Nov. 1970.
    [2] “Information technology - radio frequency identification for item management - part 6: parameters for air interface communications at 860 MHz to 960 MHz,” ISO/IEC 18000-6:2004(E), pp. 17-121.
    [3] D. H. Shih, P. L. Sun, D. C. Yen, and S. M. Huang, “Taxonomy and survey of RFID anti-collision protocols,” Computer Communications, vol. 29, no. 11, pp. 2150-2166, Jul. 2006.
    [4] “EPCTM radio-frequency identity protocols class 1 generation-2 UHF RFID protocol for communications at 860-960MHz version 1.0.9,” EPCglobal IncTM, Jan. 2005.
    [5] “Information technology - radio frequency identification for item management - part 6: parameters for air interface communications at 860 MHz to 960 MHz, amendment 1: extension with type C and update of types A and B,” ISO/IEC 18000-6:2004/Amd. 1 :( E), Jun. 2006.
    [6] V. Anatharam, “The Stability Region of the Finite-User Slotted ALOHA Protocol,” IEEE Trans. Information Theory, vol. 37, no. 3, pp. 535-540, May 1991.
    [7] I. Teletar and R. Gallager, “Combining Queuing Theory and Information Theory for Multiaccess,” IEEE J. Selected Areas in Comm., vol. 13, no. 6, pp. 963-969, Aug. 1995.
    [8] M. A. Bonuccelli, F. Lonetti, and F. Martelli, “Tree slotted aloha: a new protocol for tag identification in RFID networks,” International Symposium on a World of Wireless, Mobile and Multimedia Networks, Jun. 2006.
    [9] J. Park, M. Y. Chung, and T. J. Lee, “Identification of RFID tags in framed-slotted ALOHA with robust estimation and binary selection,” IEEE Communications Letters, vol.11, no. 5, pp. 452-454, May 2007.
    [10] T. W. Hwang, B. G. Lee, Y. S. Kim, D. Y. Suh, and J. S. Kim “Improved anti-collision scheme for high speed identification in RFID system,” First International Conference on Innovative Computing, Information and Control, pp. 449-452, Aug. 2006.
    [11] Q. Peng, M. Zhang, and W. Wu, “Variant enhanced dynamic frame slotted ALOHA algorithm for fast object identification in RFID system,” IEEE International Workshop on Anti-counterfeiting, Security, Identification, pp. 88-91, Apr. 2007.
    [12] J. Zhai and G. N. Wang, “An anti-collision algorithm using two-functioned estimation for RFID tags,” Lecture Notes in Computer Science, vol. 3483, Springer Berlin/Heidelberg5, pp. 702-711, May 2005.
    [13] J. R. Cha and J. H. Kim, “Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system,” 3rd Consumer Communications and Networking Conference, pp. 768-772, Jan. 2006.
    [14] 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.
    [15] J. Zhai and G. N. Wang, “An anti-collision algorithm using two-functioned estimation for RFID tags,” Lecture Notes in Computer Science, vol. 3483, Springer Berlin/Heidelberg, pp. 702-711, May 2005.
    [16] Draft Protocol Specification for a 900 MHz Class 0 Radio Frequency Identification Tag,” Auto-ID Center, Feb. 2003.
    [17] S. Weis, S. Sarma, R. Rivest, and D. Engels, “Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems,”Proc. First Ann. Conf. Security in Pervasive Computing, pp. 201-212, Mar. 2003.
    [18] J. Waldrop, D. Engels, and S. Sarma, “Colorwave: An Anticollision Algorithm for the Reader Collision,” Proc. IEEE Int’l Conf. Comm., pp. 1206-1210, May 2003.
    [19] C. Floerkemeier and M. Lampe, “Issues with RFID Usage in Ubiquitous Computing Applications,” Proc. Second Int’l Conf. Pervasive Computing, pp. 188-193, Apr. 2004.
    [20] EPC Radio-Frequency Identification Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860MHz-960MHz Version 1.0.8, EPCglobal, Dec. 2004.
    [21] C. Law, K. Lee, and K. Siu, “Efficient Memoryless Protocol for Tag Identification,” Proc. Fourth Int’l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm., pp. 75-84, Aug. 2000.
    [22] F. Zhou, C. Chen, D. Jin, C. Huang, and H. Min, “Evaluating and Optimizing Power Consumption of Anti-Collision Protocols for Applications in RFID Systems,” Proc. Int’l Symp. Low Power Electronics and Design, pp. 357-362, Aug. 2004.
    [23] 860MHz-930MHz class 1 radio frequency identification tag radio frequency & logical communication interface specification candidate recommendation, Auto-ID Center, version 1.0.1, pp. 3-9, Nov. 2002.
    [24] T. P. Wang, “Enhanced binary search with cut-through operation for anti-collision in RFID systems,” IEEE Communications Letters, vol. 10, no. 4, pp. 236-238, Apr. 2006.
    [25] J. Ryu, H. Lee, Y. Seok, T. Kwon, and Y. Choi, “A hybrid query tree protocol for tag collision arbitration in RFID systems,” IEEE International Conference on Communications, pp. 5981-5986, Jun. 2007.
    [26] K. W. Chiang, C. Hua, and T.-S. Peter Yum, “Prefix-randomized query-tree protocol for RFID systems,” International Conference on Communications, pp. 1653-1657, Jun. 2006.
    [27] J. H. Choi, D. Lee, and H. Lee, “Bi-slotted tree based anti-collision protocols for fast tag identification in RFID systems,” IEEE Communications Letters, vol. 10, no. 12, pp. 861-863, Dec. 2006.
    [28] J. Myung, W. Lee, and J. Srivastava, “Adaptive binary splitting for efficient RFID tag anti-collision,” IEEE Communications Letters, vol. 10, no. 3, pp. 144-146, Mar. 2006.
    [29] J. Myung, W. Lee, J. Srivastava, and T. K. Shih, “Tag-splitting: adaptive collision arbitration protocols for RFID tag identification, ”IEEE Transactions on Parallel and Distributed Systems, vol.18, no. 6, pp. 763-775, Jun. 2007.
    [30] J. Myung and W. Lee, “An Adaptive Memoryless Tag Anti-Collision Protocol for RFID Networks,” Proc. IEEE INFOCOM, Mar. 2005.
    [31] J. Eom, T.-J. Lee, “Framed-slotted ALOHA with estimation by pilot frame and identification by binary selection for RFID anti-collision,” International Symposium on Communications and Information Technologies, pp. 1027-1031, Oct. 2007.
    [32] A. J. E. M. Janssen, M. J. M. de Jong, “Analysis of contention tree algorithms,” IEEE Transactions on Information Theory, vol. 46, no. 6, pp. 2163-2172, Sept. 2000.

    無法下載圖示 全文公開日期 2013/07/15 (校內網路)
    全文公開日期 本全文未授權公開 (校外網路)
    全文公開日期 本全文未授權公開 (國家圖書館:臺灣博碩士論文系統)
    QR CODE