簡易檢索 / 詳目顯示

研究生: 蕭令彥
Ling-yen Hsiao
論文名稱: 在無線射頻標籤辨識上針對考量再辨識、捕獲效應與位元追蹤技術之反碰撞演算法
The Anti-Collision Algorithms with Considering Re-identification, Capture Effect and Bit Tracking for RFID Tag Recognition
指導教授: 賴源正
Yuan-Cheng Lai
林伯慎
Bor-Shen Lin
口試委員: 羅乃維
Nai-Wei Lo
江振瑞
Jehn-Ruey Jiang
李忠憲
Jung-Shian Li
學位類別: 博士
Doctor
系所名稱: 管理學院 - 資訊管理系
Department of Information Management
論文出版年: 2013
畢業學年度: 101
語文別: 英文
論文頁數: 150
中文關鍵詞: 無線射頻辨識反碰撞標籤辨識動態阻隔演算法捕獲效應位元追蹤
外文關鍵詞: RFID, anti-collision, tag identification, dynamic blocking algorithm, capture effect, bit tracking
相關次數: 點閱:295下載:5
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 在無線射頻辨識(RFID)系統中,讀取器將經由共享的無線頻道來辨識標籤。當有複數的標籤同時傳送他們的識別碼(ID)時,訊號碰撞將導致辨識的延遲。因此,標籤反碰撞法的研究一直是RFID系統的一個重要議題。近年來,有些學者開始針對運作在再辨識情境(re-identification)、捕獲效應(capture effect)以及採用位元追蹤(bit tracking)的RFID系統進行研究。
    在再辨識情境中,讀取器會重複辨識停留在讀取器訊號範圍內的相同標籤。現存的adaptive binary splitting(ABS)與single resolution blocking (SRB)能夠記住上一個辨識流程中標籤的辨識順序來快速辨識這些停留下的標籤。我們則是提出adaptive frame ABS (AFA) 和dynamic blocking adaptive binary splitting (DBA)兩種演算法來處理此情境。AFA使用動態管理(dynamic regulation)技術預測停留與新進標籤數並且最佳化配置的時槽數,減少標籤離開與新進時分別造成的閒置時槽(idle slot)與碰撞時槽(collision slot)。另外,動態管理使多個停留標籤(staying tag)共用時槽,AFA以依序分割(ordering splitting)來依照停留標籤之前的辨識順序來分群。DBA基於阻隔機制(blocking mechanism),避免新進標籤與停留標籤發生碰撞,然後以動態縮減 (dynamic condensation) 技術減少標籤離開時造成的閒置時槽,而縮減過程造成多個停留標籤必須共用時槽而產生的碰撞,則是利用依序位元樹(ordering binary tree)來有效的辨識。
    在捕獲效應中,即使多個標籤同時傳送訊號給讀取器,讀取器也能從訊號解譯出一個標籤的識別碼,導致沒被辨識的標籤將不會在這個辨識流程再次傳送。我們參考generalized query tree (GQT)所提出的generalized binary tree (GBT)會將標籤辨識流程分成數個位元樹(binary tree)循環來處理此問題。在當次位元樹循環沒被辨識的標籤,會反覆的參與下個週期直到它們被成功的辨識。
    當RFID系統採用了位元追蹤時,讀取器能夠偵測碰撞時槽(collision slot)中的碰撞位元位置,collision tracking tree algorithm (CTTA)、enhanced anti-collision algorithm (EAA)與new enhanced anti-collision algorithm (NEAA)都是利用此技術的演算法。我們所提出的optimal query tracking tree protocol (OQTT) 與optimal binary tracking tree protocol (OBTT)同樣是利用位元追蹤來提升標籤的辨識效能。首先,OQTT與OBTT都採用位元估計(bit estimation)技術估計標籤總數,接著根據估計的結果使用最佳化分群(optimal partition)來決定最適當的分群數。最後,OQTT使用詢問追蹤樹(query tracking tree)而OBTT使用二元追蹤樹(binary tracking tree)來依據碰撞位元位置來對標籤進行分群。
    我們所提出的演算法AFA, DBA, GBT, OQTT與OBTT均經過正式的數學分析。數學分析與模擬結果均呈現這些演算法比過去的演算法來得優異:AFA勝過ABS、DBA優於SRB、GBT比GQT出色,而OQTT與OBTT超越了CTTA, EAA 與NEAA。因此,我們可以說這些演算法都是快速而且有效率的。


    In Radio Frequency Identification (RFID) systems, the reader recognizes tags through communication over a shared wireless channel. When multiple tags send their IDs simultaneously, their signals collide, causing the identification delay. Thus, tag anti-collision algorithms have long been an important issue in RFID systems. Recently, some researchers have considered that the RFID system performs on the scenarios of re-identification, capture effect and adopting bit tracking technology.
    In re-identification, the reader repeatedly identifies the same staying tags which stayed in reader’s range. Existing anti-collision algorithms, e.g. adaptive binary splitting (ABS) and single resolution blocking (SRB), can rapidly identify the staying tags by remembering the order in which the tags were recognized. We propose adaptive frame ABS (AFA) and dynamic blocking adaptive binary splitting (DBA) to cope with re-identification. AFA utilizes the dynamic regulation that estimates the numbers of staying tags and newly-arriving tags and optimally adjusts the numbers of slots allocated for them to reduce idle slots when many recognized tags leave and reduce collision slots when many newly-arriving tags enter. Following the regulation, multiple staying tags may share the same slot and cause a collision among them. Thus, an efficient ordering splitting is designed to deterministically split the collided staying tags according to the order in which they were recognized. DBA based on the blocking mechanism, which prevents the newly-arriving tags from colliding with the staying tags. Moreover, DBA utilizes a dynamic condensation technique to reduce the number of idle slots produced when recognized tags leave. Following the condensation process, multiple staying tags may be required to share the same slot, and thus may cause collisions among them. Accordingly, an efficient ordering binary tree mechanism is proposed to split the collided tags deterministically.
    When capture effect occurs, the reader decodes a tag ID even when multiple tags simultaneously transmit signals, and causing some tags, which transmitted their IDs but not be identified in this slot, do not transmit IDs again in the current identification. By referring generalized query tree (GQT), we propose generalized binary tree (GBT) that separates the identification process into several binary tree (BT) cycles to solve the capture effect. Unrecognized tags, hidden by the capture effect in a BT cycle, will join subsequent cycles repeatedly until there are all identified.
    When a RFID system adopts bit tracking technology, the reader to detect the locations of collided bits in a collision slot, collision tracking tree algorithm (CTTA), enhanced anti-collision algorithm (EAA) and new enhanced anti-collision algorithm (NEAA) all adopt this technology. We also propose optimal query tracking tree protocol (OQTT) and optimal binary tracking tree protocol (OBTT) to improve the performance of tag identification by utilizing the bit tracking technology. First, they adopt bit estimation to estimates the number of tags based on the locations of collided bits, and then they use optimal partition to determine the number of the initial sets. Finally, OQTT uses query tracking tree and OBTT uses binary tracking tree to splits a set of collided tags into two subsets using the first collided bit.
    This dissertation formally analyzes the efficiency AFA, DBA, GBT, OQTT and OBTT, The analytical and simulation results show that our algorithms are better than previous algorithms: AFA outperforms ABS, DBA outperforms SRB, GBT outperforms GQT, OQTT and OBTT outperform than CTTA, EAA and NEAA. Thus, we can conclude these algorithms are fast, and efficiency.

    TABLE OF CONTENTS 摘要 I ABSTRACT III 誌謝 V TABLE OF CONTENTS VI LIST OF FIGURES IX LIST OF TABLES XI Chapter 1 Introduction 1 Chapter 2 Related works 6 2.1 RFID anti-collision algorithms 6 2.2 BT and QT 10 2.2.1 BT 10 2.2.2 QT 11 2.3 Re-identification 12 2.3.1 ABS 13 2.3.2 SRB 15 2.4 Capture effect 18 2.5 Bit tracking technology 19 2.5.1 CTTA 20 2.5.2 EAA 22 2.5.3 NEAA 24 Chapter 3 Adaptive frame ABS 26 3.1 Concept and procedure 26 3.1.1 Dynamic regulation 26 3.1.2 Ordering splitting 29 3.1.3 The procedure of AFA 32 3.1.4 An example of AFA 34 3.2 Performance analysis 35 3.3 Performance comparison 39 3.3.1 Impact of staying ratio and arriving ratio 40 3.3.2 Impact of wrong estimation for arriving ratio and staying ratio 41 3.4 Summary 42 Chapter 4 Dynamic blocking ABS 43 4.1 Concept and procedure 43 4.1.1 Dynamic condensation 43 4.1.2 Ordering binary tree mechanism 46 4.1.3 The procedure of DBA 48 4.1.4 An example of DBA 51 4.2 Performance analysis 53 4.3 Simulation and Performance Comparison 55 4.3.1 Effect of arriving tags 57 4.3.2 Effect of staying tags 60 4.3.3 Effect of tag velocity 63 4.3.4 Effect of stationary probability 65 4.3.5 Effect of number of tags 67 4.4 Summary 69 Chapter 5 General binary tree 70 5.1 Concept and procedure 70 5.1.1 The procedure of GBT 70 5.1.2 An example of GBT 72 5.2 Performance analysis 73 5.3 Performance comparison 74 5.4 Summary 76 Chapter 6 Optimal query tracking tree protocol 77 6.1 Concept and procedure 77 6.1.1 Bit estimation 78 6.1.2 Optimal partition 79 6.1.3 Query tracking tree 81 6.1.4 Pseudo code of OQTT 82 6.2 Performance analysis 84 6.2.1 Query tracking tree 85 6.2.2 Bit estimation 86 6.2.3 Performance of OQTT 88 6.3 Performance comparison 89 6.3.1 Impact of the number of tags 89 6.3.2 Impact of tag ID length 92 6.3.3 Accuracy of bit estimation 94 6.4 Supplementary Information 96 6.4.1 Comparison of algorithms without Bit Tracking Technology 96 6.4.2 Advantages and Enhancements of OQTT 99 6.5 Summary 101 Chapter 7 Optimal binary tracking tree protocol 102 7.1 Concept and procedure 102 7.1.1 Bit estimation 103 7.1.2 Optimal partition 105 7.1.3 Binary tracking tree 107 7.1.4 Pseudo code of OBTT 108 7.2 Performance analysis 110 7.2.1 Binary tracking tree 110 7.2.2 Bit estimation 111 7.2.3 Performance of OBTT 114 7.3 Performance comparison 114 7.3.1 Impact of the number of tags 115 7.3.2 Impact of tag ID length 118 7.3.3 Accuracy of bit estimation 120 7.4 Consideration of Slot Lengths 121 7.4.1 Time efficiency of OBTT 121 7.4.2 Evaluation of OBTT 124 7.5 Summary 126 Chapter 8 Conclusions and future works 128 References 133 Publication List 139 LIST OF FIGURES Figure 1 Existing RFID anti-collision algorithms 9 Figure 2 Example of Manchester Code 20 Figure 3 The concept of dynamic regulation 29 Figure 4 Ordering splitting for resolving the collisions among the staying tags 31 Figure 5 The operation of the reader and tags in AFA 34 Figure 6 The procedure of AFA 35 Figure 7 The superiority of AFA over ABS 41 Figure 8 Impact of the wrong estimation for the staying ratio and arriving ratio 42 Figure 9 Basic concept of dynamic condensation mechanism 44 Figure 10 Mapping of optimal condensation ratio versus estimated staying ratio 46 Figure 11 Use of OBT scheme in resolving collisions among staying tags 48 Figure 12 Pseudo code of DBA anti-collision algorithm 49 Figure 14 Effect of arriving ratio on identification performance 59 Figure 15 Effect of staying ratio on identification performance 62 Figure 16 Effect of tag velocity on identification performance 64 Figure 17 Effect of stationary probability on identification performance 66 Figure 18 Effect of number of tags on identification performance 68 Figure 19 Pseudo code of GBT 71 Figure 20 An example of GBT 72 Figure 21 Identification delay of GBT versus  (n100) 75 Figure 22 Simulation results for GBT, GQT1, and GQT2 (n100) 76 Figure 23 Optimum number of initial tag sets (n=1000tags) 81 Figure 24 Pseudo codes of OQTT 83 Figure 25 Example of OQTT 84 Figure 26 DBE(n)/n vs. n (b128bits) 88 Figure 27 Impact of the number of tags (b128 bits) 92 Figure 28 Impact of tag ID length (n500) 94 Figure 29 EER and DDR vs. the number of tags (b128 bits) 96 Figure 30 Impact of the number of tags (b128 bits) 99 Figure 31 Optimal number of initial tag sets 106 Figure 32 Pseudo codes of OBTT 109 Figure 33 Example of OBTT 110 Figure 34 DBE(n)/n versus n (b128bits) 113 Figure 35 Performance of algorithms versus the number of tags (b128 bits) 117 Figure 36 Performance of algorithms versus tag ID length (n12800) 119 Figure 37 EER and DDR versus the number of tags (b128 bits) 121 Figure 38 The optimal  and DE versus I in OBTT 125 Figure 39 Identifying time versus the length of idle slots (b=128 bits, n=12800) 125 LIST OF TABLES Table 1 Optimal RSRS and RARS for each pair of (RS, RA) 28 Table 2 The features and properties owned by each algorithm 130

    [1] “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.
    [2] “EPCTM radio-frequency identity protocols class 1 generation-2 UHF RFID protocol for communications at 860-960MHz version 1.2.0,” EPCglobal IncTM, May 2008.
    [3] M. Azambuja, C. A. M. Marcon, and F. P. Hessel, “Survey of standardized ISO 18000-6 RFID anti-collision protocols,” Second International Conference on Sensor Technologies and Applications, pp. 468-473, Aug. 2008.
    [4] M. K. Yeh and J. R. Jiang, “Adaptive k-Way Splitting and Pre-Signaling for RFID Tag Anti-Collision,” 33rd Annual Conference of the IEEE Industrial Electronics Society, Nov. 2007, pp. 40-45.
    [5] 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.
    [6] M. K. Yeh, J. R. Jiang, and S. T. Huang, “Adaptive splitting and pre-signaling for RFID tag anti-collision,” Computer Communications, vol. 32, no. 17, Nov. 2009, pp. 1862-1870.
    [7] 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.
    [8] V. Namboodiri and L. Gao, “Energy-Aware Tag Anti-Collision Protocols for RFID Systems,” 2007 Pervasive Computing and Communications, Mar. 2007, pp. 23-36.
    [9] C. N. Yang and J.Y. He. “An Effective 16-bit Random Number Aided Query Tree Algorithm for RFID Tag Anti-Collision,” IEEE Communications Letters, vol. 15, no. 5, May 2011, pp.539-541.
    [10] V. Namboodiri and L. Gao, “Energy-Aware Tag Anticollision Protocols for RFID Systems,” IEEE Transactions on Mobile Computing, vol. 9, no. 1, Jan. 2010, pp. 44-59.
    [11] 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.
    [12] 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, Jun. 2008, pp. 426-428.
    [13] Y. Maguire and R. Pappu, “An Optimal Q-Algorithm for the ISO 18000-6C RFID Protocol,” IEEE Transactions on Automation Science and Engineering, vol. 6, no. 1, Jan. 2009, pp. 16-24.
    [14] W. T. Chen, “An Accurate Tag Estimate Method for Improving the Performance of an RFID Anticollision Algorithm Based on Dynamic Frame Length ALOHA,” IEEE Transactions on Automation Science and Engineering, vol. 6, no. 1, Jan. 2009, pp. 9-15.
    [15] B. Li and J. Wang, “Efficient Anti-Collision Algorithm Utilizing the Capture Effect for ISO 18000-6C RFID Protocol,” IEEE Communications Letters, vol. 15, no. 3, Mar. 2011, pp. 352-354.
    [16] J. G. Kim, “A Divide-and-Conquer Technique for Throughput Enhancement of RFID Anti-collision Protocol,” IEEE Communications Letters, vol. 12, no. 6, June 2008, pp.474-476.
    [17] 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.
    [18] W. J. Shin and J. G. Kim, “A capture-aware access control method for enhanced RFID anti-collision performance,” IEEE Communications Letters, vol. 13, no. 5, May 2009, pp. 354-356.
    [19] Y. C. Ko, S. Ryo, C. H. Cho, H. W. Lee, and H. K. Garg, “Multiple Feedback Algorithm for RFID MAC Protocols,” IEEE Communications Letters, vol. 13, no. 9, Sep. 2009, pp. 640-642.
    [20] 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.
    [21] 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.
    [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] 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.
    [24] 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, pp. 962-975, Jun. 2009.
    [25] Y. Maguire and R. Pappu, “An Optimal Q-Algorithm for the ISO 18000-6C RFID Protocol,” IEEE Transactions on Automation Science and Engineering, vol. 6, no. 1, pp. 16-24, Jan. 2009.
    [26] C. Floerkemeier and M. Lampe, “Issues with RFID Usage in Ubiquitous Computing Applications,” Lecture Notes in Computer Science, vol. 3001, pp. 183-193, 2004.
    [27] K. Y. Wu and R. H. Campbell, “Using Generalized Query Tree to Cope with the Capture Effect in RFID Singulation,” IEEE Consumer Communications and Networking Conference (CCNC), pp. 1-5, Jan. 2009.
    [28] F. Zhou, D. Jin, C. Huang, and H. Min, “Optimize the power consumption of passive electronic tags for Anti-collision Schemes,” Auto-ID Center, Oct. 2003.
    [29] 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, pp. 1-4, Aug. 2007.
    [30] Y. H. Chen, S. J. Horng, R. S. Run, J. L. Lai, R. J. Chen, W. C. Chen, Y. Pan, and T. Takao, “A novel anti-collision algorithm in RFID systems for identifying passive tags,” IEEE Transactions on Industrial Informatics, vol. 6, no. 1, pp. 105-121, Feb. 2010.
    [31] K. Finkenzeller, “RFID handbook: radio-frequency identification fundamentals and applications,” 2nd Ed. New York: Wiley, 2003.
    [32] K. Finkenzeller, “RFID Handbook: Fundamentals and applications in contactless smart cards and identification,” 2nd Ed. John Wiley & Sons, 2003.
    [33] W. Rankl, and W. Effing, “Smart card handbook,” 3nd Ed. John Wiley & Sons, 2003.
    [34] H. Vogt, “Efficient object identification with passive RFID tags,” Pervasive 2002, LNCS 2414, pp. 98–113, Jan. 2002.
    [35] K. Dohmen, “An improvement of the inclusion-exclusion principle,” Archiv der Mathematik, vol. 72, no. 4, pp. 298-303, 1999.
    [36] J. Sounderpandian, R. V. Boppana, S. Chalasani, and A. M. Madni, “Models for cost-benefit analysis of RFID implementations in retail stores,” IEEE Systems Journal, vol. 1, no. 2, pp. 105-114, Dec. 2007.
    [37] Y. C. Lai and C. C. Lin, “Two couple-resolution blocking protocols on adaptive query splitting for RFID tag identification,” IEEE Transactions on Mobile Computing, DOI: 10.1109/TMC.2011.171.
    [38] J. Vales-Alonso, V. Bueno-Delgado, E. Egea-Lopez, F. J. Gonzalez-Castano, and J. Alcaraz, “Multiframe maximum-likelihood tag estimation for RFID anticollision protocols,” IEEE Transactions on Industrial Informatics, vol. 7, no.3, pp. 487-496, Aug. 2011.
    [39] L. Zhu, and P. Yum, “A critical survey and analysis of RFID anti-collision mechanisms,” IEEE Communications Magazine, vol. 49, no. 3, pp. 214-221, May 2011.
    [40] K. W. Chiang, C. Hua, and T. S. P. Yum, “Prefix-randomized query-tree protocol for RFID systems,” IEEE International Conference on Communications, vol. 4, pp. 1653-1657, Jun. 2006.
    [41] J. S. Cho, J. D. Shin, and S. K. Kim, “RFID tag anti-collision protocol: query tree with reversed IDs,” 10th International Conference on Advanced Communication Technology, pp. 225-230, Feb. 2008.
    [42] Y. C. Lai and L. Y. Hsiao, “General binary tree protocol for coping with the capture effect in RFID tag identification,” IEEE Communication Letters, vol. 14, no. 3, pp. 208-210, Mar. 2010.
    [43] “GS1 EPC Tag Data Standard,” GS1 EPC Global, Sept. 2011.
    [44] M. Kodialam and T. Nandagopal, “Fast and Reliable Estimation Schemes in RFID Systems,” MobiCom’06, pp. 322-333, 2006.
    [45] C. Qian, H. Ngan, Y. Liu, and L. M. Ni, “Cardinality Estimation for Large-Scale RFID Systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 9, pp. 1441-1454, Sep. 2011.
    [46] T. Li, S. Wu, S. Chen, and M. Yang, “Energy Efficient Algorithms for the RFID Estimation Problem,” INFOCOM, 2010.
    [47] H. Han, B. Sheng, C. C. Tan, Q. Li, W. Mao, and S. Lu, “Counting RFID Tags Efficiently and Anonymously,” INFOCOM, 2010.

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