臺灣博碩士論文加值系統

近年來，由於射頻辨識(RFID)系統具有快速識別與無需直視路徑的優點，使得此系統被廣泛的應用在日常生活中。因此，RFID之研究受到學界與業界之重視。RFID系統之一潛在問題是多個標籤同時傳送信號給讀取機所造成的碰撞問題，而碰撞會延長辨識所需時間。因此，反碰撞協定之研究非常重要。目前標籤的反碰撞演算法主要可分成兩種型態：ALOHA-based and Tree-based 演算法。ALOHA-based 演算法之缺點是再碰撞機率較高，而 Tree-based 演算法之缺點是overhead較重。在這篇論文中，我們試圖結合ALOHA與Tree這兩種演算法之優點，其中進一步利用分群以解決訊框大小不得超過256時槽之限制，並利用動態訊框大小來預估標籤之總數。我們考慮二種情境:靜止標籤與行動標籤。首先，我們針對靜止標籤提出Group Dynamic Frame Tree Slotted Aloha (GDFTSA)，其中首先預估未辨識的標籤總數目，接著根據預估之標籤總數來調整群組數目以改善系統效率。接著，我們針對行動標籤提出Group Dynamic Frame Tree Slotted Aloha-Adaptive Binary Splitting (GDFTSA-ABS)，其中使用上一次標籤識別資訊被用來在GDFTSA與ABS之中做一適當選擇。我們所感興趣之效能指標是系統效率，辨識所需之總時槽數目，碰撞時槽數目，與傳送位元數目。我們以C語言自行撰寫相關之電腦模擬程式。透過廣泛之數值實驗，我們顯示GDFTSA以及GDFTSA-ABS在大多數所考慮之情形下皆勝過其他考慮之反碰撞協定。

In recent years, as the radio frequency identification (RFID) system can achieve fast identification and does not need line-of-sight transmission paths, this system has been widely used in daily life. Therefore, both academic and industry show great interest in the research of RFID. A potential problem of RFID systems is that a number of tags may send signals to the reader at the same time and a collision results, and the collision results in a longer time required for identifying tags. Therefore, the study of anti-collision algorithms is very important. At present, there are two major types of anti-collision algorithms: ALOHA-based and Tree-based algorithms. One drawback of ALOHA-based algorithms is the higher probability of re-collisions, whereas that of Tree-based algorithms is the heavier overhead. In this thesis, we propose to combine the advantages of ALOHA-based and tree-based algorithms, where furthermore grouping is adopted to overcome the limitation of at most 256 slots per frame, and dynamic frame size is utilized to estimate the total number of tags. We consider two kinds of scenarios: stationary tags and mobile tags. First of all, we propose the Group Dynamic Frame Tree Slotted Aloha (GDFTSA) algorithm for stationary tags, where first we estimate the total number of unidentified tags with dynamic frame size, and according to the estimated total number of tags the number of groups is adjusted to improve the system efficiency. Next, we propose the Group Dynamic Frame Tree Slotted Aloha – Adaptive Binary Splitting (GDFTSA-ABS) algorithm for mobile tags, where the tag identification information of the last run is utilized to make an appropriate choice between GDFTSA and ABS. The performance metrics of interest are the system efficiency, the total number of time slots needed for identification, the number of collision slots, and the number of transmitted bits. Computer simulation programs are written in C language. With extensive numerical experiments, it is shown that GDFTSA and GDFTSA-ABS outperform the other anti-collision algorithms in most of the cases studied.

CONTENTS
摘要……………………………………………………………………….………………....i
Abstract……………………………………………………………………………………..ii
誌謝……………………………………………………………………………………… ..iii
Contents…………………………………………………………………………………….iv
List of Figures………………………………………………………………………………v
List of Tables…………………………………………………………………………..….viii
Chapter 1 Introduction…………………………………………………………………1
Chapter 2 Related Works……………………………………………....………………4 2.1 Standards of Anti-Collision Algorithms…………………..…………...4
2.1.1 ISO 18000-6 A standard: ALOHA LST /FST Anti-Collision Protocol………………………………..4
2.1.2 ISO 18000-6 B Standard: Btree Anti-Collision Protocol………………………………………..………5
2.1.3 ISO 18000-6 C Standard: Random Slotted Anti-Collision Protocol………………………………..6
2.2 Classification of Anti-collision Algorithms……………………………7
2.2.1 Tree Anti-Collision Protocols……………………………………7
2.2.2 Aloha Anti-Collision Protocol…………………………………...7
Chapter 3 System Model……………………………………………………………….7
3.1 Anti-Collision Algorithms for Stationary Tags………...……………...9
3.1.1 Binary Tree Algorithm….......................................................9
3.1.2 Basic Frame Slotted Aloha (BFSA) Algorithm………………………………………………….10
3.1.3 Dynamic Frame Slot Aloha (DFSA) Algorithm……..….………………………………….…….12
3.1.4 Enhance Dynamic Frame slotted Aloha (EDFSA) Algorithm………...………………….…………………….14
3.1.5 Tree Slotted Aloha (TSA) Algorithm ……………………..16
3.1.6 Group Dynamic Frame Tree Slotted Aloha (GDFTSA) Algorithm………………………………………………….20
3.2 Anti-Collision Algorithms for Mobile Tags……………………...…..23
3.2.1 Adaptive Binary Slotted (ABS) Algorithm……………..…23
3.2.2 Groups Dynamic Frame Tree Slotted Aloha – Adaptive Binary Splitting (GDFTSA-ABS) Algorithm...…………...26
Chapter 4 Simulation results………………….………………………………………29
4.1 Simulation Environment……………………………………………..29
4.2 Simulation Results for Stationary Tags……………….………….......30
4.3 Simulation Results with Mobile Tags…………….……….…………35
Chapter 5 Conclusions………………………………………………………………..58
Reference…………………………………………………………………………………..59


















List of Figures
Figure 1-1 A basic model of the RFID system…………………………………………1
Figure 2-1 Tag State Transition Diagram of ALOHA...………………………………..4
Figure 2-2 Tag State Transition Diagram of Btree…………………………..…………5
Figure 2-3 State of Btree algorithm…………………………………………….………6
Figure 2-5 A Tree-based algorithm…….………………………………………….……7
Figure 2-6 Slotted Aloha with frame size = 8…….……………………………….……8
Figure 3-1 The flowchart of BT………………………………………………...……..10
Figure 3-2 The flowchart of BFSA………………………………………..….……….12
Figure 3-3 The flowchart of DFSA……………………………………….......……….12
Figure 3-4 The flowchart of EDFSA…………………………………………..…..….16
Figure 3-5 The flowchart of TSA……………………………………………………..19
Figure 3-6 System efficiency vs. frame size…………………………………………..20
Figure 3-7 System efficiency vs. the number of tag groups…………………………..21
Figure 3-8 Estimation error of Vogt’s method…………...……………........................21
Figure 3-9 The flowchart of GDFTSA…………………………….………………….23
Figure 3-10 The flowchart of ABS……………………………………………………..24
Figure 3-11 The flowchart of GDFTSA-ABS…...…….……….………………………27
Figure 4-1 System efficiency for stationary tags….. ….. …………..………………...42
Figure 4-2 Total number of slots for stationary tags….. …….. ………………………42
Figure 4-3 Average number of collision slots for stationary tags ………………….....43
Figure 4-4 Average number of transmitted bits for stationary tags…………………...43
Figure 4-5 Identification delay for stationary tags..………….. ………………………44
Figure 4-6 System efficiency for stationary tags……………………...………………44
Figure 4-7 Total number of slot for stationary tags..……………………….………….45
Figure 4-8 Average number of collision slots Stationary tags for stationary tags….....45
Figure 4-9 Average number of transmitted bits for stationary tags…...……………....46
Figure 4-10 Figure 4-10 Identification delay for stationary tags..…………...……... …46
Figure 4-11 System efficiency for stationary tags…...…………...………………... ….47
Figure 4-12 Total number of slots for stationary tags…...……………..... …………….47
Figure 4-13 Average number of collision slots for stationary tags...………………...…48
Figure 4-14 Average number of transmitted bits Stationary tags for stationary tags ..…48
Figure 4-15 Identification delay for stationary tags…..………………...………………49
Figure 4-16 Average number of collision slots with for mobile tags.....………….49
Figure 4-17 Total number of slots with for mobile tags…………….…...………..50
Figure 4-18 System efficiency with for mobile tags..…………….………………50
Figure 4-19 Average number of transmitted bits with for mobile tags.....….….....51
Figure 4-20 Average number of collision slots with for mobile tags……….…51
Figure 4-21 Total number of slots with for mobile tags……………..... .....…52
Figure 4-22 System efficiency with for mobile tags………. …….………….52
Figure 4-23 Average number of transmitted bits with for mobile tags…........53
Figure 4-24 Average number of collision slots with for mobile tags…………..53
Figure 4-25 Total number of slots with for mobile tags...........…………...........54
Figure 4-26 System efficiency with for mobile tags……...……………………54
Figure 4-27 Average number of transmitted bits with for mobile tags.....……..55
Figure 4-28 Average number of collision slots with for mobile tags…...........55
Figure 4-29 Total number of slots with for mobile tags…..…….. …….…….56
Figure 4-30 System efficiency with for mobile tags.………………..……….56
Figure 4-31 Average number of transmitted bits with for mobile tags………57



























List of Tables
Table 3-1 Estimated number of tags and optimal frame size………………………...8
Table 4-1 Simulation Parameters………………..……………..……………………28
Table 4-2 Mobile Scenarios…………………………………………………...........35

Reference
[1]D. H. Shih, P. L. Sun, D. C. Yen, and S.M. Huang, “Taxonomy and Survey of RFID Anti-Collision Protocols,” Computer Communication, pp. 2150-2166, Jan. 2006.
[2]M. Jacomet, A. Ehrsam, and U. Gehrig, “Contactless Identification Device with Anticollision Algorithm,” IEEE Conf. Circuits, System, Computers and Comm., pp. 269-273, July 1999.
[3]J. Ho, D. W. Engels and S. E. Sarma, “HiQ: A Hierarchical Q-Learning Algorithm to Solve the Reader Collision Problem,” IEEE SAINTW, 2005.
[4]A. Gupta and P. Mohapatra, “Slotted Scheduled Tag Access in Multi-Reader RFID Systems,” Computer Networks, Vol. 51, Issue 11, pp. 2976-2993, Aug. 2007.
[5]EPCglobal, “EPC Ratio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860MHz – 960MHz,” ver 1.1.0, 2004, 2005, 2006.
[6]Marcelo C. de Azambuja, C�臃ar A. M. Marcon, and Fabiano P. Hessel, “Survey of Standardized ISO 18000-6 RFID Anti-Collision Protocols,” 2008 IEEE DOI 10.1109/SENSORCOMM., pp. 468-473, 2008.
[7]K. Finkenzeller, “RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification,” John Wiley & Sons, 2003.
[8]J. Myung, W. Lee, J. Srivastava, and T. K. Shih, “Tag-Splitting Adaptive Collision Arbitration Protocols for RFID Tag Identification,” IEEE Transaction on Parallel and Distributed Systems, Vol. 18, NO. 6, pp. 763-775, June 2007.
[9]D. Hush and C. Wood, “Analysis of Tree Algorithms for RFID Arbitration,” IEEE Int’l Symp. Information Theory, p. 107, Aug. 1998.
[10]W. T. Chen, “Performance Comparison of Binary Search Tree and Framed ALOHA Algorithms for RFID Anti-Collision,” IEICE Trans. Commun., Vol.E91–B, No.4 Apr. 2008.

[11]ISO/IEC 18000-6, “Information Technology — Radio Frequency Identification for Item Management —Part 6: Parameters for Air Interface Communications at 860 MHz to 960 MHz,”.
[12]T. Cheng and L. Jin, “Analysis and Simulation of RFID Anti-Collision Algorithms,” ICACT, pp. 697-701, Feb. 2007.
[13]F. Zhou, C. Chen, D. Jin, C. Huang, and H. Min, “Evaluating and Optimizing Power Consumption of Anti-collision Protocols for Applications in RFID Systems,” ISLPED ’04, pp. 357–362, 2004.
[14]W. Shin and J. G. Kim, “Partitioning of Tags for Near-Optimum RFID Anti-Collision Performance,” WCNC 2007, pp. 1673–1678, 2007.
[15]F. Schoute, “Dynamic Frame Length ALOHA,” IEEE Trans. Commun., Vol. 13, No. 4, pp. 565-568, Apr. 1983.
[16]H. Vogt, “Efficient Object Identification with Passive RFID Tags,” Int’l Conf. Pervasive Computing, pp. 98-113, Apr. 2002.
[17]J. Zhai and G. Wang, “An Anti-Collision Algorithm Using Two-Functioned Estimation for RFID Tags,” Int’l Conf. Computational Science and Its Applications, pp.702-711, May 2005.
[18]S. Lee, S. Joo, and C. Lee, “An Enhanced Dynamic Framed Slotted Aloha Algorithm for RFID Tag Identification,” MobiQuitous 2005, pp. 166–172, 2005.
[19]M. A. Bonuccelli, F. L. D. Informatica, and F. Martelli, “Tree Slotted Aloha: a New Protocol for Tag Identification in RFID Networks,” 2006 International Symposium on a WoWMoMG, 2006.
[20]X. Huang and S. Le, “Efficient Dynamic Framed Slotted ALOHA for RFID Passive Tags,” ICACT2007, pp. 94-97, 2007.
[21]S. Kaewsirisin, P. Supanakoon, S. Promwong, N. Sukutamtanti, and U. Ketprom, “Performance Study of Dynamic Framed Slotted ALOHA for RFID Systems,” First International Conference on Broadband Networks, pp. 406-415, 2004.