簡易檢索 / 詳目顯示

研究生: 陳泓桔
Hong-Jie Chen
論文名稱: 於無線射頻標籤辨識中具位元追蹤之新詢問樹協定
A Novel Query Tree Protocol with Bit Tracking in RFID Tag Identification
指導教授: 賴源正
Yuan-Cheng Lai
口試委員: 江振瑞
Jehn-Ruey Jiang
洪西進
Shi-Jinn Horng
學位類別: 碩士
Master
系所名稱: 管理學院 - 資訊管理系
Department of Information Management
論文出版年: 2012
畢業學年度: 100
語文別: 英文
論文頁數: 43
中文關鍵詞: 無線射頻標籤辨識標籤辨識防碰撞位元追蹤曼徹斯特碼
外文關鍵詞: RFID, tag identification, anti-collision, bit tracking, Manchester code
相關次數: 點閱:254下載:5
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 防止標籤訊號碰撞的問題在無線射頻標籤辨識系統中一直是重要的研究議題。最近有許多研究學者採用位元追蹤技術於碰撞時槽中尋找碰撞位元的位置藉以加快標籤辨識的速度,然而這些方法在標籤辨識開始時仍然會產生過多的標籤碰撞。因此,本論文提出了最佳化詢問追蹤樹協定(OQTT),嘗試先將所有的標籤分割成較小的群組以減少辨識開始時的碰撞。OQTT首先透過碰撞位元的位置估計標籤的數量,再根據此數量決定最佳的標籤分群數目,接著在辨識過程中會利用第一個碰撞位元的位置將碰撞的標籤切割成兩個子群。此論文並分析了OQTT的效率,結果顯示其效率接近於0.614,這是目前我們所知之最高效率。模擬結果更進一步地指出OQTT勝於其他現存的演算法。
    時槽區間在真實環境下長度通常會根據其狀態而不同,也就是碰撞時槽會比閒置時槽的區間還要長。因此我們提出了另一個以時槽區間為基準的最佳化詢問追蹤樹協定(SOQTT)。SOQTT根據不同時槽區間的比例決定最佳的分群數目以最大化辨識效率。結果顯示當閒置時槽區間為碰撞時槽區間的1倍或0.1倍時,其效率分別可達到0.614與0.749。


    Tag anti-collision has long been an important issue in RFID systems. To accelerate tag identification, some researchers have recently adopted bit tracking technology that allows the reader to detect the locations of collided bits in a collision slot. However, these methods still encounter the problem of too many collisions occurring at the beginning of identification. This thesis proposes an optimal query tracking tree protocol (OQTT) that tries to separate all of the tags into smaller sets to reduce collisions at the beginning of identification. OQTT first estimates the number of tags based on the locations of collided bits, and then determines the optimal number of the initial sets based on this estimation. OQTT splits a set of collided tags into two subsets using the first collided bit in the tag IDs during identification process. This thesis analyzes the efficiency of OQTT, which represents how many tags can be identified in a slot. Results show that its efficiency is close to 0.614, the highest efficiency published to date. The simulation results further show that OQTT outperforms other existing algorithms. ,
    Slot durations often differ by slot states, i.e., the duration of collision slot is longer than the duration of an idle slot, in real environment. Thus we propose another slot-duration based optimal query tracking tree protocol (SOQTT). It maximizes the performance of identification by setting the optimum initial number of sets according to different slot durations ratio. Result shows the efficiency of SOQTT can achieve 0.614 and 0.749 when the length of an idle slot is equal to and 0.1 times that of a collision slot, respectively.

    Table of Contents 摘要.............................................................I Abstract........................................................II 誌謝.............................................................III Table of Contents...............................................IV List of Figures.................................................V List of Tables..................................................VI Chapter 1. Introduction.........................................1 Chapter 2. Background...........................................4 2.1 Bit tracking technology.....................................5 2.2 Collision tracking tree (CTTA) algorithm....................6 2.3 Enhanced anti-collision (EAA) algorithm.....................7 2.4 New enhanced anti-collision (NEAA) algorithm................8 Chapter 3. Optimal query tracking tree..........................11 3.1 Bit estimation..............................................12 3.2 Optimal partition...........................................13 3.3 Query tracking tree.........................................15 3.4 Pseudo code of OQTT.........................................16 Chapter 4. Performance analysis.................................19 4.1 CTTA and EAA................................................19 4.2 OQTT........................................................20 4.2.1 Query tracking tree.......................................20 4.2.2 Bit estimation............................................22 4.2.3 Performance of OQTT.......................................24 Chapter 5. Simulation and analytical results....................25 5.1 Impact of the number of tags................................25 5.2 Impact of tag ID length.....................................29 5.3 Accuracy of bit estimation..................................31 Chapter 6. Slot-duration based optimal query tracking tree......33 6.1 Optimal partition...........................................33 6.2 Simulation and analytical results...........................36 Chapter 7. Conclusions and future work..........................38 Reference.......................................................40 List of Figures Fig. 2.1. Example of Manchester Code............................5 Fig. 2.2. Pseudo code of parameters adjustment in each slot.....9 Fig. 3.1. Optimum number of initial tag sets (n=1000tags).......15 Fig. 3.2. Pseudo codes of OQTT..................................17 Fig. 3.3. Example of OQTT.......................................18 Fig. 4.1. DBE(n)/n vs. n (b=128bits)............................24 Fig. 5.1. Impact of the number of tags (b=128 bits).............28 Fig. 5.2. Impact of tag ID length (n=500).......................31 Fig. 5.3. EER and DDR vs. the number of tags (b=128 bits).......32 Fig. 6.1. R on varying k........................................36 Fig. 6.2. TE of EAA, CTTA, SOQTT, and NEAA......................37 List of Tables Tab. 6.1. Corresponding table between k and R...................36

    [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, J. R. Jiang, and S. T. Huang, “Parallel response query tree splitting for RFID tag anti-collision,” 40th International Conference on Parallel Processing Workshops, pp. 6-15, Sept. 2011.
    [5] 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, pp. 1096-1101, Oct. 2006.
    [6] 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, pp.85-87, Jan. 2007.
    [7] H. Gou, H. C. Jeong, and Y. Yoo, “A bit collision detection based query tree protocol for anti-collision in RFID system,” IEEE 6th International Conference on Wireless and Mobile Computing, Networking and Communications, pp. 421-428, Oct. 2010.
    [8] W. Zein-Elabdeen and E. Shaaban, “An enhanced binary tree anti-collision technique for dynamically added tags in RFID systems,” 2nd International Conference on Computer Engineering and Technology, pp. 349-353, Apr. 2010.
    [9] 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.
    [10] 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.
    [11] V. Namboodiri and L. Gao, “Energy-aware tag anticollision protocols for RFID systems,” IEEE Transactions on Mobile Computing, vol. 9, no. 1, pp. 44-59, Jan. 2010.
    [12] Y. C. Lai and L. Y. Hsiao, “General binary tree protocol for coping with the capture effect in RFID tag identification,” IEEE Communications Letters, vol. 14, no. 3, pp. 208-210, Mar. 2010.
    [13] 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, pp.539-541, May 2011.
    [14] H. Vogt, “Efficient object identification with passive RFID tags,” Pervasive 2002, LNCS 2414, pp. 98–113, Jan. 2002.
    [15] Z. Lei and T. S. P. Yum, “The optimal reading strategy for EPC Gen-2 RFID anti-collision systems,” IEEE Transactions on Communications, vol. 58, no. 9, pp. 2725-2733, Sept. 2010.
    [16] Y. Maguire and R. Pappu, “An optimal Q-Algorithm for the ISO 18000-6C RFID protocol,” IEEE Transactions on Automation Science and Engineering, pp. 16-24, Jan. 2009.
    [17] Z. Lei and T. S. P. Yum, “Optimal framed aloha based anti-collision algorithms for RFID systems,” IEEE Transactions on Communications, vol. 58, no. 12, pp. 3583-3592, Dec. 2010.
    [18] 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, pp. 861-863, Nov. 2008.
    [19] 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, pp. 9-15, Jan. 2009.
    [20] C. F. Lin and F. Y. S. Lin, “Efficient estimation and collision-group-based anti-collision algorithms for dynamic frame-slotted aloha in RFID networks,” IEEE Transactions on Automation Science and Engineering, vol. 7, no. 4, pp. 840-848, Oct. 2010.
    [21] 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, Mar. 2011.
    [22] 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.
    [23] 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.
    [24] 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.
    [25] K. Finkenzeller, “RFID handbook: radio-frequency identification fundamentals and applications,” 2nd Ed. New York: Wiley, 2003.
    [26] J. Choi, I. Lee, D. Z. Du, and W. Lee, “FTTP: A Fast Tree Traversal Protocol for Efficient Tag Identification in RFID Networks,” IEEE Communications Letters, vol.14, no. 8, pp. 713-715, Aug. 2010.
    [27] K. Dohmen, “An improvement of the inclusion-exclusion principle,” Archiv der Mathematik, vol. 72, no. 4, pp. 298-303, 199

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