研究生: |
蕭令彥 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 |
相關次數: | 點閱:398 下載: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.
[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.