Basic Search / Detailed Display

Author: 陳勇君
Yung-Chun Chen
Thesis Title: RFID 標籤之可調適反碰撞辨識機制
Adaptive Anti-Collision Mechanism for RFID Tag Identification
Advisor: 羅乃維
Nai-Wei Lo
Committee: 吳宗成
Tzong-Chen Wu
Yuan-Cheng Lai
Chin-Laung Lei
Wei-Hua He
Degree: 博士
Department: 管理學院 - 資訊管理系
Department of Information Management
Thesis Publication Year: 2014
Graduation Academic Year: 102
Language: 中文
Pages: 99
Keywords (in Chinese): 反碰撞標籤識別無線射頻識別技術(RFID)多元樹
Keywords (in other languages): K-ary Tree, RFID, Tag Identification, Anti-Collision
Reference times: Clicks: 366Downloads: 6
School Collection Retrieve National Library Collection Retrieve Error Report

無論在小型或者大型RFID 應用系統中,所有的讀取器(Reader)與標籤(Tag)之間的通訊都是透過共享單一無線通訊頻道來進行。因此當讀取器執行所謂標籤識別程序(Tag Identification Process)來嘗試收集該讀取器無線通訊審訊區域範圍內所有標籤的識別碼(ID)過程時候,將會產生大量標籤與讀取器之間的訊號碰撞 (Signal Collision)現象發生,此現象通常會導致標籤識別之時間、頻寬、能量以及效能的浪費與衝擊。為了解決這種標籤訊號碰撞問題,本論文設計一個更有效率的標籤識別通訊協定(Tag Identification Protocol)來同時改善該標籤識別程序的識別延遲(Identification Delay)與通訊負擔(Communication Overhead),我們主要運用多元樹(K-ary Tree)之原理與架構來事先取得為何在目前的標籤查詢運算(Tag Inquiry Operation)中會發生訊號碰撞的屬性原因資訊,進而解析與改善此訊號碰撞的問題,本方法跟已存在的學術研究不同,過去他們通常會強調在每一個完整審訊時間區隔(Interrogation Time Period)中,如何辨識與判斷是否發生標籤識別訊號碰撞現象。然而我們則事先取得並且運用這些有價值的訊號碰撞前置(Prefix)屬性原因資訊,所以在一個標籤識別審訊會談(Tag Identification Session)中,將可以大量降低標籤識別訊號碰撞的次數頻率,同時也可以避免所有標籤處於通訊等待Idle 狀態。最後,我們也透過嚴謹的實驗效能量化結果,證明本論文所提出的標籤識別通訊協定確實優於目前其他同樣運用 Tree-Based多元樹原理的既有標籤識別通訊協定。

In large scale RFID systems, all of the communications between readers and tags are via a shared wireless channel. When a reader intends to collect all IDs from numerous existing tags, a tag identification process is invoked by the reader to collect the tags’ IDs. This phenomenon results in tag-to-reader signal collisions which may suppress the system performance greatly. To solve this problem, we design an efficient tag identification protocol in which a significant gain is obtained in terms of both identification delay and communication overhead. A k-ary tree based abstract is adopted in our proposed tag identification protocol as underlying architecture for collision resolution. Instead of just recognizing whether tag collision happens at each interrogation time period, the reader can further obtain the reason of why the collision occurs in the current tag inquiry operation. With this valuable information, we can reduce tag signal collisions significantly and at the same time avoid all of the tag idle scenarios during a tag identification session. The rigorous performance analysis and evaluation show that our proposed tag identification protocol outperforms existing tree based schemes.

中文摘要 I Abstract III 誌 謝 IV 目 次 VI 圖 目 次 VIII 表 目 次 X 1. 簡介 1 1.1. RFID標籤識別效能標準 1 1.2. RFID標籤識別通訊協定分類 3 1.3. 章節架構 8 2. RFID應用範例情境 9 2.1. 機場行李檢查系統之應用情境 9 2.2. 庫存管理系統之應用情境 10 2.3. 物流商品追蹤系統之應用情境 11 3. A-TAP 標籤識別通訊協定 (New Tag Identification Protocol) 13 3.1. 名詞與符號定義 13 3.2. A-TAP反碰撞標籤識別通訊協定程序說明 16 3.3. A-TAP範例實作說明 31 4. A-TAP效能分析 54 4.1. A-TAP 通訊協定之符號定義 54 4.2. A-TAP:論點Lemma (1) 數學公式之說明 56 4.3. A-TAP:論點Lemma (1) 數學公式之證明 56 4.4. A-TAP:論點Lemma (2) 數學公式之說明 59 4.5. A-TAP:定理Theorem (1) 數學公式之推論與證明 60 4.6. A-TAP:定理Theorem (2) 數學公式之推論與證明 62 4.7. A-TAP效能分析之因素相關性 66 5. A-TAP效能評估比較 68 5.1. 效能評估比較實驗參數說明 68 5.2. 實驗(一):A-TAP【 i值】的效能影響 71 5.3. 實驗(二):A-TAP與其他通訊協定之效能比較 75 5.4. 實驗(三):A-TAP【標籤數量】與【標籤長度】的效能影響 81 6. 結論 87 7. 參考文獻 89 8. 附錄 94 8.1. 作者簡介 94 8.2. 著作清單 98

[1] 860 MHz – 930 MHz Class 1 Radio Frequency Identification Tag Radio Frequency and Logical Communication Interface Specification Candidate Recommdation Version 1.0.1, Auto-ID Center, 2002.
[2] J. I. Capettanakis, “Tree Algorithms for Packet Broadcast Channels,” IEEE Trans. on Information Theory, vol.25, 1979, pp.505-515.
[3] T. Cheng and L. Jin, “Analysis and Simulation of RFID Anti-Collision Algorithms,” in proc. of 9th International Conference on Advanced Communication Technology, 2007, pp.697-701.
[4] K. W. Chiang, C. Hua and T. S. Peter Yum, “Prefix-Randomized Query-Tree Protocol for RFID Systems,” in proc. of IEEE International Conference on Communications, 2006, pp.1653-1657.
[5] I. Chamtac, C. Petrioli and J. Redi, “Energy-Conserving Access Protocols for Identification Networks,” IEEE/ACM Trans. on Networking, vol.7, no.1, 1999, pp.51-59.
[6] J. S. Cho, J. D. Shin and S. K. Kim, “RFID Tag Anti-Collision Protocol: Query Tree with Reversed IDs,” in proc. of 10th International Conference on Advanced Communication Technology, 2008, pp.225-230.
[7] H. S. Choi, J. R. Cha and J. H. Kim, “Fast Wireless Anti-Collision Algorithm in Ubiquitous ID System,” in proc. of IEEE 60th Vehicular Technology Conference, 2004, pp.4589-4592.
[8] 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, 2007, pp.85-87.
[9] Draft Protocol Specification for a 900MHz Class 0 Radio Frequency Identification Tag, Auto-ID Center, 2003.
[10] EPCTM Radio-Frequency Identification Protocols Class 1 Generation-2 UHF RFID Protocol for Communication at 860-960 MHz Version 1.0.9, EPCGlobal Inc., Dec. 2005.
[11] K. Finkenzeller, RFID Handbook: Radio-Frequency Identification, Fundamentals and Applications, John Wiley & Sons Ltd, 1999.
[12] C. Floerkemeier and M. Wille, “Comparison of Transmission Schemes for Framed ALOHA based RFID Protocols,” in proc. of International Symposium on Applications and the Internet Workshops, 2006, pp.92-97.
[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] D. K. Klair, K. W. Chin and R. Raad, “On the Suitability of Framed Slotted Aloha based RFID Anti-Collision Protocols for Use in RFID-enhanced WSNs,” in proc. of 17th International Conference on Computer Communications and Networks, 2007, pp.583-590.
[15] D. K. Klair and K. W. Chin, “A Novel Anti-Collision Protocol for Energy Efficient Identification and Monitoring in RFID-enhanced WSNs,” in proc. of 17th International Conference on Computer Communications and Networks, 2008, pp.1-8.
[16] 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, 2008, pp.432-434.
[17] Y. C. Lai and C. C. Lin, “Two Blocking Algorithms on Adaptive Binary Splitting: Single and Pair Resolutions for RFID Tag Identification,” IEEE/ACM Trans. on Networking, vol.17, no.3, 2009, pp.962-975.
[18] C. Law, K. Lee and K. Y. Siu, “Efficient Memoryless Protocol for Tag Identification,” in Proc. of the 4th International Workshop on Discrete Algorithm and Methods for Mobile Computing and Communication, 2000, pp.75-84.
[19] L. Liu, Z. H. Xie, J. T. Xi and S. L. Lai, “An Improved Anti-collision Algorithm in RFID System,” in proc. of 2nd International Conference on Mobile Technology, Applications and Systems, 2005, pp.1-5.
[20] Y. Maguire and R. Pappu, “An Optimal Q-algorithm for the ISO 18000-6C RFID Protocol,” IEEE Trans. on Automation Science and Engineering, vol.6, no.1, 2009, pp.16-24.
[21] J. Mosely and P. Humblet, “A Class of Efficient Contention Resolution Algorithms for Multiaccess Channels,” IEEE Trans on Communication, vol.33, no.2, 1985, pp.145-151.
[22] J. Myung, W. Lee and J. Srivastava, “Adaptive Binary Splitting for Efficient RFID Tag Anti-Collision,” IEEE Communications Letters, vol.10, no.3, 2006, pp.144-146.
[23] J. Myung, W. Lee and T. K. Shih, “An Adaptive Memoryless Protocol for RFID Tag Collision Arbitration,” IEEE Trans. on Multimedia, vol.8, pp.1096-1101, 2006.
[24] J. Myung, W. Lee, J. Srivastava and T. K. Shih, “Tag-Splitting: Adaptive Collision Arbitration Protocols for RFID Tag Identification,” IEEE Trans. on Parallel and Distributed Systems, vol.18, no.6, 2007, pp.763-775.
[25] V. Namboodiri and L. Gao, “Energy-Aware Tag Anti-Collision Protocols for RFID Systems,” IEEE Trans. on Mobile Computing, Accepted manuscript, 2009.
[26] H. S. Ning, Y. Cong, Z. Q. Xu, T. Hong, J. C. Chao and Y. Zhang, “Performance Evaluation of RFID Anti-Collision Algorithm with FPGA Implementation,” in proc. of 21st International Conference on Advanced Information Networking and Applications Workshops, 2007, pp.153-158.
[27] F. Schoute, “Dynamic Frame Length Aloha,” IEEE Trans. on Communication, vol.31, no.4, 1983, pp.565-568.
[28] T. P. Wang, “Enhanced Binary Search with Cut-Through Operation for Anti-Collision in RFID Systems,” IEEE Communications Letters, vol.10, no.4, 2006, pp.236-238.
[29] J. E. Wieselthier, A. Ephremides and L. A. Michaels, “An Exact Analysis and Performance Evaluation of Framed Aloha with Capture,” IEEE Trans. on Communication, vol.37, no.2, 1989, pp.125-137.
[30] 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, 2007, pp.946-948.
[31] K. H. Yeh, N. W. Lo and E. Winata, “An efficient tree-based tag identification protocol for RFID systems,” in proc. of 22nd International Conference on Advanced Information Networking and Applications Workshops, 2008, pp.966-970.
[32] ISO/IEC 14443. Inentification cards – Contactless integrated circuit cards – Proximity cards.
[33] ISO/IEC 15693. Inentification cards – Contactless integrated circuit cards – Vicinity cards.
[34] ISO/IEC 18000. ISO/IEC 18000 Information Technology AIDC Technologies – RFID for Item Management –Air Interface.
[35] T. La Porta, G. Maselli, C. Petrioli, "Anti-collision Protocols for Single-Reader RFID Systems: Temporal Analysis and Optimization," IEEE Trans. on Mobile Computing, vol.10, Issue 2, pp.267-279, 2011.
[36] X.L. Jia, Q.Y. Feng and C.Z. Ma, “An Efficient Anti-Collision Protocol for RFID Tag Identification,” IEEE Communication Letters, vol.14, no.11, pp.1014-1016, 2010.
[37] L. Zhu and T.S. P. Yum, “Optimal Framed Aloha Based Anti-Collision Algorithms for RFID Systems,” IEEE Trans. on Communicaitons, vol. 58, no. 12, pp.3583-3592, 2010.
[38] 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, pp.352-354, 2011.