 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：54 、訪客IP：18.217.203.172
姓名 葉明貴(Ming-Kuei Yeh) 查詢紙本館藏 畢業系所 資訊工程學系 論文名稱 無線射頻辨識系統反碰撞協定
(Anti-Collision Protocols In RFID System)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 在無線射頻辨識(RFID)系統中，讀取器(reader)係經由共享的無線通訊頻道藉由詢問電子標籤(tag)上的識別碼的方式來辨識電子標籤的存在。當有多個電子標籤同時回應識別碼時，將會產生訊號碰撞而降低了電子標籤辨識的效能。如何減低碰撞以提升辨識的效能就變成是一件重要的工作。有一些反碰撞(anti-collision)的協定被提出來以解決電子標籤碰撞的問題。他們可以被分類成兩大類：以阿囉哈(ALOHA)為基礎的協定以及樹狀(tree)為基礎的協定。其中樹狀基礎協定可以再分為確定性樹狀基礎以及機率性計數基礎兩個子類別。
在本論文中，我們提出了兩個屬於機率性計數基礎的協定(「適應性分群及預先信號」及「平行分裂」協定)以及一個確定性查詢樹狀基礎的反碰撞協定(「平行反向回應」協定)。其中，「適應性分群及預先信號」協定利用「適應性分群」方案來預估將要處理的計數器中電子標籤的數量，並予以適當分裂，期望可以達到每個電子標籤均有一個獨一的技術器值；併採用「預先信號」方案預先收集下一個計數器中電子標籤的數量為零、一或是多個，進而採取不同的處理程序，以簡省不需的迭代(iteration)數量。而「平行分裂」協定的概念則是讓所有尚未辨識的電子標籤一起分裂，而非只有計數器值為0的電子標籤進行分裂，以提升辨識效能；同時輔以「辨識樹高度調整」方案，使辨識樹的葉節點數與實際的電子標籤數接近，以縮短所需的迭代數量。至於「平行反向回應」協定則是使用「平行字首符合」方案，利用字首互補的方式增加符合字首辨識的電子標籤數量，並將符合條件的電子標籤透過「平行雙副載波回應」的設計方案提高回應成功率。我們亦對所提的三種協定進行分析以及模擬，並與相關的協定進行比較以了解所提協定的優點。
摘要(英) In the RFID system, the reader identifies tags by interrogating their IDs through a shared wireless communication channel. Collisions occur when multiple tags transmit their IDs to the reader simultaneously, degrading the performance of tag identification. How to reduce tag collisions to speed up the identification is thus important. There are several anti-collision protocols proposed for dealing with tag collisions. They can be categorized into two classes: ALOHA-based protocols and tree-based protocols that include deterministic tree-based and probabilistic counter-based subclasses of protocols.
In this dissertation, we propose two probabilistic counter-based (“Adaptive Splitting and Pre-Signaling” and “Parallel Splitting”) protocols and one deterministic query tree-based (“Parallel Reverse Response”) anti-collision protocol. 1) “Adaptive Splitting and Pre-Signaling” protocol uses the idea of “Adaptive Splitting” scheme to estimate the number K of oncoming identification tags and split them into K proper subgroups, besides “Pre-Signaling” scheme is proposed to reduce the number of messages sent between the reader and tags by detecting the number of tags (null, one or multiple tags) with counter=1 previously. 2) “Parallel Splitting” protocol uses the idea of “parallel splitting” scheme to split the unidentified tags concurrently instead of only the tags with counter = 0 as in the ISO 18000-6B standard. It also utilizes “adaptive identification-tree height adjustment” scheme to adjust the number of leaf nodes of identification tree to approach the number of tags. 3) “Parallel Reverse Response” protocol integrates the ideaof “parallel prefix matching” and “Parallel Two Sub-carriers Response” schemes to let the tags with prefix ID matching the request bit string S or complementary of S be arranged to respond in two sub-carriers simultaneously in order to speed up RFID tagidentification. We analyze and simulate these three proposed protocols and compare them with related protocols to demonstrate their advantages.
關鍵字(中) ★ 無線射頻辨識系統
★ 確定性查詢樹狀基礎
★ 反碰撞
★ 機率性計數基礎
★ 電子標籤辨識關鍵字(英) ★ RFID
★ anti-collision
★ probabilistic counter-based
★ deterministic query tree-based
★ tag identification論文目次 摘要 ........................................................................................................................ I
Abstract ............................................................................................................... II
誌謝 ..................................................................................................................... IV
Contents ............................................................................................................. V
List of Figures ................................................................................................... IX
List of Tables ..................................................................................................... XI
1. Introduction ................................................................................................................. 1
2. Related Works ............................................................................................................. 6
2.1. The ALOHA-based Protocols ............................................................................................................. 6
2.1.1. ALOHA Protocol ..................................................................................................................... 7
2.1.2. Slotted ALOHA Protocol ........................................................................................................ 7
2.1.3. Frame Slotted ALOHA Protocol ............................................................................................. 8
2.2. Deterministic Tree-based Protocols .................................................................................................. 11
2.2.1. Query Tree Protocol .............................................................................................................. 11
2.2.2. BSQTA and BSCTTA Protocol ............................................................................................. 16
2.2.3. Adaptive Query Splitting (AQS) Protocol ............................................................................. 18
2.2.4. Hybrid Query Tree (HQT) Protocol ...................................................................................... 19
2.2.5. Bit-by-bit Binary Tree Protocol ............................................................................................. 20
2.3. Probabilistic Counter-based Protocols .............................................................................................. 24
2.3.1. ISO/IEC 18000-6B Protocol ................................................................................................. 24
2.3.2. ABS Protocol ......................................................................................................................... 28
3. Adaptive Splitting and Pre-Signaling (ASPS) Protocol ................................. 30
3.1. Adaptive Splitting Scheme ............................................................................................................... 30
3.1.1. The Basic Idea of Adaptive Splitting..................................................................................... 30
3.1.2. The Operation of Reader and Tag.......................................................................................... 33
3.1.3. Simulation of AS Protocol..................................................................................................... 37
3.2. Pre-Signaling Scheme....................................................................................................................... 38
3.2.1. The Basic Idea of Pre-Signaling ............................................................................................ 38
3.2.2. The Hardware Support of Pre-Signaling ............................................................................... 40
3.3. Adaptive Splitting and Pre-Signaling Protocol ................................................................................. 41
3.3.1. Operation Details .................................................................................................................. 41
3.3.2. Simulation of ASPS Protocol ................................................................................................ 46
3.3.2.1. The Number of Collisions Occurred ....................................................................... 46
3.3.2.2. The Number of Messages Sent by the Reader ........................................................ 47
3.3.2.3. The Tag Identification Delay ................................................................................... 49
3.3.2.4. The Error on the Estimated Number of Tags ........................................................... 50
3.3.2.5 The Effect of Pre-Signaling Scheme ........................................................................ 52
3.3.2.6. System Efficiency ................................................................................................... 53
3.4. Summary ......................................................................................................................................... 54
4. Parallel Splitting (PS) Protocol ............................................................................ 56
4.1. The Observations of Counter-based Protocol ................................................................................... 56
4.2. Parallel Splitting Scheme .................................................................................................................. 58
4.3. Adaptive Identification-tree Height Adjustment Scheme ................................................................. 59
4.4. Parallel Splitting Protocol ................................................................................................................. 63
4.4.1. Operation Details .................................................................................................................. 63
4.4.2. Analysis of PS Protocol ......................................................................................................... 65
4.4.2.1. The Average Number of Iterations for Identifying All Tags .................................... 65
4.4.2.2. The Minimum Number of Iterations for Identifying All Tags ................................. 68
4.4.2.3. The Extra Space Required by the Reader and Tags................................................. 69
4.4.3. Simulation of PS Protocol ..................................................................................................... 70
4.4.3.1. The Relation Between the Height of the Identification Tree and the Number of Iterations Needed ................................................................................................... 70
4.4.3.2. Comparison of PS, ASPS and ISO/IEC 1800-6B Protocols.................................... 72
4.4.3.3. System Efficiency ................................................................................................... 73
4.5. Summary ......................................................................................................................................... 74
5. Parallel Reverse Response (PRR) Protocol ...................................................... 76
5.1. The 4-ary Query Tree ....................................................................................................................... 76
5.2. Parallel Prefix Matching Scheme ..................................................................................................... 79
5.3. Parallel Two Subcarriers Response Scheme ..................................................................................... 79
5.4. Parallel Reverse Response Protocol ................................................................................................. 81
5.4.1. Operation Details .................................................................................................................. 81
5.4.2. Analysis of PRR Protocol ...................................................................................................... 85
5.4.2.1. Uniform tag ID distribution .................................................................................... 85
5.4.2.2. Consecutive tag ID distribution .............................................................................. 88
5.4.3. Simulation of PRR Protocol .................................................................................................. 91
5.4.3.1. The impact of number of tags under uniform ID distribution ................................. 91
5.4.3.2. The impact of number of tags under consecutive ID distribution ........................... 92
5.4.3.3. The impact of length of tag ID under uniform ID distribution ................................ 94
5.4.3.4. The impact of length of tag ID under consecutive ID distribution .......................... 95
5.4.3.5. Number of identification iterations ......................................................................... 95
5.4.3.6. Number of transmission Bits ................................................................................... 97
5.5. Summary ......................................................................................................................................... 98
6. Conclusions .................................................................................................. 99
Bibliography ................................................................................................................ 101
Publication List ........................................................................................................... 104
參考文獻 [1] Peter Schaar, “Working document on data protection issues related to RFID technology,” Working Document Article 29 - 10107/05/EN, European Union Data Protection Working Party, January 2005.
[2] H. Chae, D. Yeager, J. Smith, K. Fu, “Maximalist Cryptography and Computation on the WISP UHF RFID Tag,” in Proc. of the Conference on RFID Security, 2007.
[3] Shailesh M. Birari, Sridhar Iyer, “PULSE: A MAC Protocol for RFID Networks,” in Proc. of the EUC Workshops 2005: 1036-1046
[4] Kim, D. Y., B. J. Jang, H. G. Yoon, J. S. Park, and J. G. Yook, “Effects of reader interference on the RFID interrogation range,” in Proc. the 37th European Microwave Conference (EuMC’07), pp. 728–731, Munich, Oct. 2007.
[5] N. Abramson, “The ALOHA System-Another Alternative for Computer Communications,” in Proc. of Fall Joint Computer Conference of AFIPS, Vol. 37, pp. 281-285, 1970.
[6] Leian Liu, Shengli Lai, “ALOHA-Based Anti-Collision Algorithms Used in RFID System,” in Proc. of Int’l Conf. on Wireless Communications, Networking and Mobile Computing 2006 (WiCOM 2006), pp.1 – 4, Sep. 22-24, 2006.
[7] H. Vogt, “Efficient Object Identification with Passive RFID Tags,” in Proc. of Pervasive Computing 2002, pp.98–113, 2002.
[8] H. Choi, J. R. Cha and J. H. Kim, “Fast wireless anti-collision algorithm in ubiquitous ID system,” in Proc. of IEEE VTC '04, 2004.
[9] Feng Zhou et al., “Evaluating and optimizing power consumption of anti-collision protocols for applications in RFID systems,” in Proc. of the 2004 international symposium on Low power electronics and design, 2004.
[10] M. A. Bonuccelli, F. Lonetti, F. Martelli. “Tree Slotted Aloha: a New Protocol for Tag Identification in RFID Networks,” in Proc. of the 4th IEEE International Workshop on Mobile Distributed Computing (MDC'06), 2006.
[11] Ji Hwan Choi, Dongwook Lee, Hyuckjae Lee , “Bi-slotted tree based anti-collision protocols for fast tag identification in RFID systems,” IEEE Communications Letters, Vol. 10, Issue 12, pp. 861-863, 2006.
[12] Draft protocol specification for a 900 MHz Class 0 Radio Frequency Identification Tag, MIT Auto-ID Center, Feb 2003.
[13] D. H. Shih, P. L. Sun, and D. C. Yen, “Taxonomy and Survey of RFID Anti-Collision Protocols,” Computer Communications, Vol.29, No.11, pp.2150-2166, 2006.
[14] Ming-Kuei Yeh and Jehn-Ruey Jiang, “Adaptive k-Way Splitting and Pre-Signaling for RFID Tag Anti-Collision,” in Proc. of the 33rd Annual Conference of the IEEE Industrial Electronics Society (IECON'07), 2007.
[15] D. Krebs and M.J. Liard, “White Paper: Global Markets and Applications for Radio Frequency Identification,” Venture Development Corporation, 2001.
[16] ISO/IEC, “Information technology automatic identification and data capture techniques – radio frequency identification for item management air interface - part 6: parameters for air interface communications at 860-960 MHz,” Final Draft International Standard ISO 18000-6, Nov. 2003.
[17] Philips Semiconductors, UCODE, http://www.semiconductors.philips.com, 2005.
[18] Jae-Ryong Cha , Jae-Hyun Kim, “Novel Anti-collision Algorithms for Fast Object Identification in RFID System,” in Proc. of the 11th International Conference on Parallel and Distributed Systems -Workshops (ICPADS'05), pp.63-67, 2005.
[19] Girish Khandelwal et al., “ASAP: A MAC Protocol for Dense and Time Constrained RFID Systems,” in Proc. of IEEE International Conference on Communications (ICC’06), 2006.
[20] S. Lee, S.D. Joo, and C.W. Lee, “An enhanced dynamic framed slotted aloha algorithm for RFID tag identification,” in Proc. of Mobiquitous 2005, pp.166-172, 2005.
[21] L. G. Roberts, “Extensions of Packet Communication Technology to a Hand Held Personal Terminal,” in Proc. of AFIPS Spring Joint Computer Conf., vol. 40, pp. 295-298, 1972.
[22] M. Kodialam and Thyaga Nandagopal, “Fast and Reliable Estimation Schemes in RFID Systems,” in Proc. of ACM Mobicom 2006, 2006.
[23] Ming-Kuei Yeh, Jehn-Ruey Jiang and Shing-Tsaan Huang, “A 4-ary Query Tree Anti-Collision Algorithm in RFID Systems,” Technical report, National Central University, Taiwan, 2010.
[24] Jehn-Ruey Jiang and Ming-Kuei Yeh, “Anti-collision protocols for the RFID system,” RFID and SensorNetworks: Architectures, Protocols, Security and Integrations, Ed. Yan Zhang et al., Auerbach Publications, Taylor&Francis Group, USA, 2009.
[25] Jihoon Myung, Wonjun Lee, “Adaptive splitting protocols for RFID tag collision arbitration,” in Proc. of MobiHoc 2006: pp. 202-213, 2006.
[26] P.Mathys and P.Flajolet, “Q-ary collision resolution algorithms in random-access systems with free or blocked channel access,” IEEE Trans. Inform. Theory, vol. 31, no. 4, pp. 217-243, March 1985.
[27] Jiho Ryu, Hojin Lee, Yongho Seok, Taekyoung Kwon, and Yanghee Choi, “A Hybrid Query Tree Protocol for Tag Collision Arbitration in RFID systems,” IEEE International Conference on Communications, 2007. ICC '07, Page(s):5981 – 5986, June 2007.
[28] A. Micic, A. Nayak, D. Simplot-Ryl, I. Stojmenovic, “A hybrid randomized protocol for RFID tag identification,” in Proc. of the 1st IEEE Int’l Workshop on Next Generation Wireless Networks (WoNGeN’05), Dec. 2005.
[29] K. Finkenzeller, RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification, Wiley, New York, 2003.
指導教授 黃興燦、江振瑞
(Shing-Tsaan Huang、Jehn-Ruey Jiang)審核日期 2010-7-24 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit