簡易檢索 / 詳目顯示

研究生: 林志宗
Chih-Chung Lin
論文名稱: 在無線射頻標籤辨識上具有阻隔、配對及象徵性回應技術之反碰撞協定
Anti-Collision Protocols with Blocking, Pairing, and Symbolic Response Technologies in RFID Tag Identification
指導教授: 賴源正
Yuan-Cheng Lai
口試委員: 周立德
none
李忠憲
none
江振瑞
none
羅乃維
none
學位類別: 博士
Doctor
系所名稱: 管理學院 - 資訊管理系
Department of Information Management
論文出版年: 2010
畢業學年度: 98
語文別: 英文
論文頁數: 154
中文關鍵詞: 無線射頻辨識反碰撞標籤辨識阻隔演算法配對演算法
外文關鍵詞: RFID, anti-collision, tag identification, blocking algorithm, pair resolution
相關次數: 點閱:373下載:3
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 在RFID系統中,讀取器經由與標籤共享的無線傳輸管道來辨識標籤,當有多個標籤同時傳送它們獨有的編碼(ID)時,它們的訊號會彼此碰撞,進而增加辨識時間的延遲。因此,許多之前的反碰撞演算法,例如:adaptive query splitting algorithm (AQS)與adaptive binary splitting algorithm (ABS)專注於解決這個問題。為了加速辨識停留的標籤,在AQS與ABS中的讀取器保留上一次辨識標籤過程中所獲得的資訊,利用這個資訊,AQS與ABS成功地避免停留標籤(staying tag)之間的碰撞。從之前的研究中可得知,ABS能有較快速的辨識延遲,而AQS則僅需較簡單的標籤規格。
    我們以ABS與AQS為基礎,提出三種新技術來加速RFID標籤的辨識,分別是阻隔技術(Blocking technique)、配對技術(Pairing technique)及象徵性回應技術(Symbolic Response technique)。首先,因為AQS與ABS會讓新進標籤(arriving tag)與停留標籤(staying tag)碰撞在一起,我們建議採用阻隔技術來防止新進標籤(arriving tag)與停留標籤(staying tag)碰撞。藉由阻隔技術成功分開新進標籤與停留標籤後,我們不只使用阻隔技術還進一步採用配對技術,配對技術能允許停留標籤成對地同時傳送它們的ID。然後,我們也發現當分開停留標籤與新進標籤後,其實停留的標籤無須回應完整的IDs,因為讀取器在之前的辨識中,已經保留有這些標籤的IDs,因此我們提出象徵性回應技術(symbolic response technique)來允許每個停留標籤不用回傳完整標籤ID字串,而只需回應一個象徵性回應。
    我們以ABS與AQS為基礎,分別採用Blocking technique提出兩個演算法:Single resolution blocking ABS algorithm (SRBBT)與Single resolution blocking AQS algorithm (SRBQT)。然而這兩個演算法仍然是一個個依順序來辨識停留的標籤。因此,我們採用配對與阻隔技術來提出Pair resolution blocking ABS algorithm (PRBBT)與Pair resolution blocking AQS algorithm (PRBQT),再者,PRBQT的配對技術只是藉著在每一次詢問中傳送兩個ID前序條件,進而能夠成對地配對停留標籤,來減少辨識停留標籤的時間,也就是對於每一對停留標籤,PRBQT準備了兩個詢問條件,因此,我們再提出Enhanced pair resolution blocking AQS algorithm (EPRBQT),其採用與PRBQT相同的阻隔技術,但是採用了不同的配對技術,在EPRBQT中,每一次詢問只包含一個ID前序條件,但仍可以配對辨識成對的停留標籤,因此,EPRBQT能比PRBQT有較少的訊號位元傳送。最後,我們使用象徵性回應技術來分別修改SRBBT、SRBQT、PRBBT、PRBQT及EPRBQT,進而發展出SSRBBT、SSRBQT、SPRBBT及SPRBQT,此技術允許每個停留標籤不用回傳完整標籤ID字串,而只需回應一個象徵性回應。
    在此論文中,我們所提出的演算法之效能都經過正式的數學分析,且分析與模擬的結果顯示我們所提出的演算法勝過ABS與AQS。具阻隔技術的演算法可以比無阻隔技術的演算法避免較多的碰撞,再者,藉由配對技術,擁有配對阻隔技術的演算法在辨識停留標籤時,會比沒有配對技術但有阻隔技術的演算法節省大約一半的時間。還有,在具阻隔技術的演算法中使用象徵性回應技術,此類演算法成功減少許多傳送時間。最後,因為SPRBBT結合三個技術:阻隔、配對及象徵性回應,它表現出最佳的效率。


    In Radio Frequency Identification (RFID) systems, the reader identifies tags through communication over a shared wireless channel. When multiple tags transmit their IDs simultaneously, their signals collide, increasing the identification delay. Therefore, many previous anti-collision algorithms, including an adaptive query splitting algorithm (AQS) and an adaptive binary splitting algorithm (ABS), focused on solving this problem. The reader, using AQS or ABS, reserves information obtained from the last process of tag identification in order to fast re-identify the staying tags. Using this information, AQS and ABS can successfully avoid collisions among staying tags. From the previous study, ABS may have the shorter identification delay, while AQS requires lighter tag specification.
    We propose three techniques based on ABS and AQS to accelerate identifying RFID tags, i.e., Blocking technique, Pairing technique, and Symbolic Response technique. First, because AQS and ABS let staying tags collide with arriving tags that newly appear in the current frame and were not recognized in the last frame, we propose Blocking technique to successfully prevent staying tags from be collided by arriving tags. After successfully dividing tags into arriving tags and staying tags, to accelerate identifying staying tags, we not only use Blocking technique but also further adopt Pair technique, which allows each pair of the tags recognized in the last frame to transmit their IDs simultaneously in the current frame. Then, we also discover staying tags do not need to respond complete IDs when arriving tags and staying tags are divided, because the algorithms already retained these IDs obtained from the last frame. Thus, we propose Symbolic Response technique to allow each staying tag to respond a symbolic response replacing the tag ID when re-identifying these recognized tags.
    We adopt Blocking technique on ABS and AQS to respectively propose Single resolution blocking ABS algorithm (SRBBT) and Single resolution blocking AQS algorithm (SRBQT), but they still identify staying tags one by one. Then, therefore, we adopt Pair and Blocking technique to propose Pair resolution blocking ABS algorithm (PRBBT) and Pair resolution blocking AQS algorithm (PRBQT). Moreover, PRBQT couples staying tags by sending a query that includes two ID prefixes to reduce the time at identifying staying tags. That means that PRBQT prepares two ID prefixes for each pair of staying tags. Thus, we further propose Enhanced pair resolution blocking AQS algorithm (EPRBQT), which also adopts the same Blocking technique as PRBQT, but uses a different Pair technique from it. EPRBQT uses a query that includes only one ID prefix to couple staying tags; thus, it has fewer transmitted bits compared to PRBQT. Finally, we use Symbolic response technique and respectively modify SRBBT, SRBQT, PRBBT, and PRBQT to develop SSRBBT, SSRBQT, SPRBBT, and SPRBQT, which allow each staying tag to respond a symbolic response replacing the tag ID when re-identifying these recognized tags.
    In this presentation, the performance of all algorithms is formally analyzed. And then, the analytic and simulation results show that our algorithms are better than ABS and AQS. The blocking algorithms can avoid more collisions than the non-blocking algorithms. And then, by Pair technology, the pairing blocking algorithms reduce about the half time at identifying staying tags compared with non-pairing blocking algorithms. Moreover, using Symbolic Response technology in blocking algorithms, this kind of algorithms successfully reduces much transmission time. Finally, because SPRBBT combines three technologies, i.e., blocking, pairing, and symbolic response, it shows the best performance.

    摘要 I ABSTRACT III 誌謝 VI TABLE OF CONTENTS VII LIST OF FIGURES IX LIST OF TABLES XI Chapter 1. Introduction 1 Chapter 2. Related works 6 2.1. Brief introduction for RFID standards 6 2.2. Binary tree algorithm (BT) 9 2.3. Query tree algorithm (QT) 12 2.4. Adaptive binary splitting algorithm (ABS) 15 2.5. Adaptive query splitting algorithm (AQS) 19 Chapter 3. Two blocking algorithms on adaptive binary splitting: single and pair resolutions 24 3.1. Single resolution blocking ABS algorithm (SRB) 24 3.2. Pair resolution blocking ABS algorithm (PRB) 28 3.3. Performance analysis 35 3.4. Performance comparison 37 3.5. Summary 48 Chapter 4. Blocking and semi-blocking algorithms on adaptive query splitting 51 4.1. Blocking AQS algorithm (BA) 51 4.2. Semi-blocking AQS algorithm (SBA) 54 4.3. Performance comparison 57 4.4. Summary 67 Chapter 5. Two couple-resolution blocking algorithms on adaptive query splitting 69 5.1. Couple resolution blocking AQS algorithm (CRB) 69 5.2. Enhanced couple resolution blocking AQS algorithm (ECRB) 75 5.3. Performance analysis 78 5.4. Performance comparison 84 5.5. Summary 93 Chapter 6. Two blocking algorithms with symbolic response and optimal slot assignment 95 6.1. Symbolic response SRB algorithm (SSRB) 95 6.2. Symbolic response PRB algorithm (SPRB) 101 6.3. Performance analysis 104 6.4. Performance comparison 116 6.5. Summary 124 Chapter 7. Some suppliements 126 7.1. Computation effort required by the tag and the reader 126 7.2. Comparison among CRB, ECRB, and PRB 127 Chapter 8. Conclusions and future works 128 8.1. Conclusions 128 8.2. Future works 130 References 132 Glossary 139 Publication List 141 Vita 143

    [1] S. Shepard, RFID: Radio Frequency Identification. New York: McGraw-Hill, 2005, pp. 55-61.
    [2] “Draft protocol specification for a 900 MHz class 0 radio frequency identification tag,” Auto-ID Center, Feb. 2003.
    [3] “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(E), Aug. 2004.
    [4] “860MHz-930MHz class 1 radio frequency identification tag radio frequency & logical communication interface specification candidate recommendation version 1.0.1,” Auto-ID Center, Nov. 2002.
    [5] W. C. Chen, S. J. Horng, and P. Fan, “An enhanced anti-collision algorithm in RFID based on counter and stack,” Second International Conference on Systems and Networks Communications, Aug. 2007, pp. 21-24.
    [6] T. P. Wang, “Enhanced binary search with cut-through operation for anti-collision in RFID systems,” IEEE Communications Letters, vol. 10, no. 4, Apr. 2006, pp. 236-238.
    [7] 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, Jun. 2007, pp. 5981-5986.
    [8] K. W. Chiang, C. Hua, and T. S. Peter Yum, “Prefix-randomized query-tree protocol for RFID systems,” International Conference on Communications, Jun. 2006, pp. 1653-1657.
    [9] 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, Dec. 2006, pp. 861-863.
    [10] J. I. Capetanakis, “Tree algorithms for packet broadcast channels,” IEEE Transactions on Information Theory, vol. 25, no. 5, Sep. 1979, pp. 505-515.
    [11] J. Mosely and P. Humblet, “A class of efficient contention resolution algorithms for multiple access channels,” IEEE Transactions on Communications, vol. 33, no. 2, Feb. 1985, pp. 145-151.
    [12] “EPCTM radio-frequency identity protocols class 1 generation-2 UHF RFID protocol for communications at 860-960MHz version 1.2.0,” EPCglobal Inc., Oct. 2008.
    [13] “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.
    [14] H. Vogt, “Efficient object identification with passive RFID tags,” Lecture Notes in Computer Science, vol. 2414, Springer Berlin/Heidelberg, Aug. 2002.
    [15] 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, Jan. 2006, pp. 768-772.
    [16] S. R. Lee, S. D. Joo, and C. W. Lee, “An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification,” Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, Jul. 2005, pp. 166-172.
    [17] 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.
    [18] 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, May 2007, pp. 452-454.
    [19] 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, Apr. 2007, pp. 88-91.
    [20] F. Schoute, “Dynamic frame length ALOHA,” IEEE Transactions on Communications, vol. 31, no. 4, Apr. 1983, pp. 565-568.
    [21] J. E. Wieselthier, A. Ephremides, and L. A. Michaels, “An exact analysis and performance evaluation of framed ALOHA with capture,” IEEE Transactions on Communications, vol. 37, no. 2, Feb. 1989, pp. 125-137.
    [22] J. Myung, W. Lee, and J. Srivastava, “Adaptive binary splitting for efficient RFID tag anti-collision,” IEEE Communications Letters, vol. 10, no. 3, Mar. 2006, pp. 144-146.
    [23] J. Myung, W. Lee, and T. K. Shih, “An adaptive memoryless protocol for RFID tag collision arbitration,” IEEE Transactions on Multimedia, vol. 8, no. 5, Oct. 2006, pp. 1096-1101.
    [24] 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, Jun. 2007, pp. 763-775.
    [25] J. B. Eom and 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, Oct. 2007, pp. 1027-1031.
    [26] F. Zhou, D. Jin, C. Huang, and M. Hao, “Optimize the power consumption of passive electronic tags for anti-collision schemes,” Fifth International Conference on ASIC, vol. 2, Oct. 2003, pp. 1213-1217.
    [27] J. H. Choi, D. Lee, Y. Youn, H. Jeon, and H. Lee, “Scanning-based pre-processing for enhanced tag anti-collision protocols,” International Symposium on Communications and Information Technologies, Sept. 2006, pp. 1207-1211.
    [28] J. G. Kim, “A divide-and-conquer technique for throughput enhancement of RFID anti-collision protocol,” IEEE Communications Letters, vol. 12, no. 6, Jun. 2008, pp. 474-476.
    [29] M. L. Molle and G. C. Polyzos, “Conflict resolution algorithms and their performance analysis,” Technical Report Number CS93-300, Department of Computer Science and Engineering, University of California at San Diego, Jul. 1993, pp. 9-10.
    [30] Y.-C. Lai and C.-C. Lin, “A pair-resolution blocking algorithm on adaptive binary splitting for RFID tag identification,” IEEE Communications Letters, vol. 12, no. 6, Jun. 2008, pp. 432-434.
    [31] Y.-C. Lai and C.-C. Lin, “Two blocking algorithms on adaptive binary splitting: single and pair resolutions for RFID tag identification,” IEEE/ACM Transactions on Networking, vol. 17, no. 3, Jun. 2009, pp. 962-975.
    [32] M. William, W. D. Dennis, and S. L. Richard, “Mathematical statistics with applications,” 4th ed., PWS-KENT Pub. Co., 1990, pp. 171-172.
    [33] J. H. Choi, D. Lee, and H. Lee, “Query tree-based reservation for efficient RFID tag anti-collision,” IEEE Communications Letters, vol. 11, no. 1, Jan. 2007, pp. 85-87.
    [34] J.-B. Eom, T.-J. Lee, R. Rietman, and A. Yener, “An efficient framed-slotted ALOHA algorithm with pilot frame and binary selection for anti-collision of RFID tags,” IEEE Communications Letters, vol. 12, no. 11, Nov. 2008, pp. 861-863.
    [35] C. P. Wong and Q. Feng, “Grouping based bit-slot ALOHA protocol for tag anti-collision in RFID systems,” IEEE Communications Letters, vol. 11, no. 12, Dec. 2007, pp. 946-948.
    [36] X. Yan, Z. Yin, and Y. Xiong, “A query tree dynamic frame slot ALOHA collision resolution protocol for RFID tags,” Second International Conference on Future Generation Communication and Networking, Dec. 2008, pp. 198-201.
    [37] 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, Jun. 2007, pp. 5981-5986.
    [38] M. A. Bonuccelli, F. Lonetti, and F. Martelli, “Exploiting signal strength detection and collision cancellation for tag identification in RFID systems,” IEEE Symposium on Computers and Communications, Jul. 2009, pp. 500-506.
    [39] Z.-Y. Yang, J.-L. Chen, and Z.-J. Mao, “Study on the performance of tag-tag collision avoidance algorithms in RFID systems,” Third Asia International Conference on Modelling & Simulation, May 2009, pp. 757-760.
    [40] S. S. Kim, Y. H. Kim, S. J. Lee, and K. S. Ahn, “An improved anti-collision algorithm using parity bit in RFID system,” Seventh IEEE International Symposium on Network Computing and Applications, Jul. 2008, pp. 224-227.
    [41] 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, Elsevier B.V., 2006, pp. 2150-2166.
    [42] N. Bhandari, A. Sahoo, and S. Iyer, “Intelligent query tree (IQT) protocol to improve RFID tag read efficiency,” 9th International Conference on Information Technology, 2006, pp. 46-51.
    [43] 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,” Proceedings of the 2004 international symposium on Low power electronics and design, 2004, pp. 357-362.
    [44] H. Lee and J. Kim, “QT-CBP: a new RFID tag anti-collision algorithm using collision bit positioning,” Lecture Notes in Computer Science, vol. 4097, Springer Berlin/Heidelberg, 2006, pp.591-600.
    [45] 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, 2005, pp. 702-711.
    [46] Y.-C. Ko, S. Roy, J. R. Smith, H.-W. Lee, and C.-H. Cho, “RFID MAC performance evaluation based on ISO/IEC 18000-6 Type C,” IEEE Communications Letters, vol. 12, no. 6, June 2008, pp. 426-428.
    [47] K. Sohraby, M. Daneshmand, C. Wang, and B. Li, “Performance analysis of RFID generation-2 protocol,” IEEE Transactions on Wireless Communications, vol. 8, no. 5, May 2009, pp.2592-2601.
    [48] J. Kim, W. Lee, E. Kim, D. Kim, and K. Suh, “Optimized transmission power control of interrogators for collision arbitration in UHF RFID systems,” IEEE Communications Letters, vol. 11, no. 1, Jan. 2007, pp. 22-24.
    [49] Y.-C. Ko, S. Roy, C.-H. Cho, and H.-W. Lee, “An enhanced multiple-feedback algorithm for RFID MAC protocols,” IEEE International Conference on Communications, June 2009, pp.1-6.
    [50] H. J. Yeo, Y. H. Kim, H. Y. Lim, Y. S. Park, and K. S. Ahn, “ID prediction algorithm for tag collision arbitration in RFID system,” 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Aug. 2007, pp. 476-481.

    QR CODE