臺灣博碩士論文加值系統

RFID技術在未來勢必被廣泛的運用，諸如醫療、軍事、商業活動等。但此科技本身也擁有著不少嚴重的問題，例如安全性問題、隱私權問題、訊號碰撞問題。RFID系統裝置是透過無線電波進行資料交換，因此若是同時有多個裝置發出無線電波，將會造成訊號碰撞，以致於其它裝置無法讀取到正確資訊。訊號碰撞一般可分為讀取器訊號碰撞以及電子標籤訊號碰撞兩大類，讀取器訊號碰撞指的是同一個電子標籤同時收到多個讀取器所發出的訊號，電子標籤訊號碰撞指的是同一台讀取器同時收到多個電子標籤所發出的訊號。依照 Class 1 Generation 2 的規定，讀取器以及電子標籤傳遞訊息所使用的頻率不同，因此碰撞只會由讀取器和讀取器所發出的訊號互相碰撞產生，稱為讀取器碰撞；或是電子標籤和電子標籤所發出的訊號相互碰撞產生，稱為電子標籤碰撞。
而本篇論文主要是探討電子標籤訊號碰撞問題。先討論改變各種反碰撞演算法之參數所帶來的利弊，再依照其利弊，分析每種反碰撞演算法適用的情況。最後綜合上述結論，實做出一套可調適的反碰撞演算法，在不同的情況，做出不同的調整，已達到較好的效益。

Radio frequency identification (RFID) technology has been extensively used in various application domains, such as medical management,
military affairs, retail business, {em etc}. There are several serious problems with the RFID technology, for instance, the problems
of security, privacy and the signal collision. An RFID system includes two kinds of device, interrogator and tag, exchanging
information through radio wave. Radio transmission will cause signal collision when there are too many devices transmitting
signal at the same time. Usually, two types of collision are considered: interrogator collision and tag collision. Interrogator collision means that
one tag receives more than one signal sent simultaneously by interrogators; tag collision means that one interrogator receives
more than one signal sent simultaneously by tags. There are mainly two types of anti-collision algorithms used to
resolve signal collisions. One is tree-based anti-collision algorithm and another one is Aloha-based anti-collision algorithm.
Tree-based anti-collision algorithms classified tags into several different sets by translating a sequence of masks until
each set contains only one tag. Aloha-based anti-collision algorithms used time-slicing skill, making tags respond in
different time to avoid signal collision. This paper mainly discusses the problems of tag collision. We design an adaptive
anti-collision algorithm which uses historical tag information and implement the algorithm with EPC C1 Gen2 commands. This adaptive
anti-collision algorithm can determine whether the historical tag information is suitable for inventory or not. Interrogator
employs this algorithm to query tag with historical tag information if historical tag information is suitable for inventory
tags and abandon historical tag information if it is not suitable. The adaptive algorithm achieves better performance
than tranitional tag anti-collision algorithm.

1 Introduction 1
2 RelatedWork 6
2.1 Aloha algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Tree Walk algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Class-1 Generation-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Tag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2 Interrogator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.3 Commands of Class-1 Generation-2 . . . . . . . . . . . . . . . 11
2.4 Implement of Tree Walk and Aloha Using EPC C1 Gen2 Command . . 15
2.4.1 Tree Walk Anti-Collision Algorithm . . . . . . . . . . . . . . . 15
2.4.2 Aloha Anti-Collision Algorithm . . . . . . . . . . . . . . . . . 16
2.5 Compare Tree Walk with Aloha . . . . . . . . . . . . . . . . . . . . . 17
3 Methodology 18
3.1 Performance of anti-collision algorithma . . . . . . . . . . . . . . . . . 18
3.2 Related Math model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Adaptive Anti-Collision Algorithm 26
4.1 Adaptive Anti-Collision Algorithm . . . . . . . . . . . . . . . . . . . . 26
4.2 Class-1 Generation-2 Simulator . . . . . . . . . . . . . . . . . . . . . 26
4.3 Implementation of each algorithm in simulator . . . . . . . . . . . . . . 29
4.3.1 Implementation of Tree Walk Algorithm in Simulator . . . . . . 29
4.3.2 Implementation of Aloha Algorithm in Simulator . . . . . . . . 32
4.3.3 Implementation of Adaptive anti-collision algorithm in simulator 34
5 Performance analysis 35
6 Conclusions 38

[1] S. M. Birari and S. Iyer. Mitigating the reader collision problem in RFID networks
with mobile readers. In Proceedings of the 13th IEEE International Conference
on Networks jointly held with the 7th IEEE Malaysia International Conference on
Communications, pages 463–468, 2005.
[2] K. W. Chiang, C. Hua, and T.-S. P. Yum. Prefix-randomized query-tree protocol
for RFID systems. In Proceedings of 2006 IEEE International Conference on
Communications, volume 4, pages 1653–1657, 2006.
[3] EPCglobal. EPC radio-frequency identity protocols class-1 generation-2 UHF
RFID protocol for communications at 860 MHz – 960 MHz version 1.0.9. Technical
report, EPCglobal, Inc., 2004.
[4] B. Feng, L. J. Tao, G. J. Bo, and D. Z. Hua. Id-binary tree stack anticollision
algorithm for rfid. IEEE Transactions on Computers, pages 207–212, 2006.
[5] P. Hernandez, J.D. Sandoval, F. Puente, and F. Perez. Mathematical model for
a multiread anticollision protocol. In Proceedings of 2001 IEEE International
Conference on Communications, volume 11, 2001.
[6] ISO/IEC FCD 14443-1. Identification cards – Contactless integrated circuit(s)
cards – Proximity cards, Part 1: Physical characteristics, 1997.
[7] ISO/IEC FCD 14443-2. Identification cards – Contactless integrated circuit(s)
cards – Proximity cards, Part 2: Radio frequency power and signal interface, 1999.
[8] ISO/IEC FCD 14443-3. Identification cards – Contactless integrated circuit(s)
cards – Proximi cards, Part 3: Initialization and anticollision, 2000.
[9] ISO/IEC FCD 14443-4. Identification cards – Contactless integrated circuit(s)
cards – Proximi cards, Part 4: Transmission protocol, 2000.
[10] ISO/IEC FCD 15693-1. Identification cards X- Contactless integrated circuit(s)
cards X- Vicinity Integrated Circuit(s) Card, Part 1: Physical characteristics, 2000.
[11] ISO/IEC FCD 15693-2. Identification cards X- Contactless integrated circuit(s)
cards X- Vicinity Integrated Circuit(s) Card, Part 2: Radio frequency power and
signal interface, 2000.
[12] ISO/IEC FCD 15693-3. Identification cards X- Contactless integrated circuit(s)
cards X- Vicinity Integrated Circuit(s) Card, Part 3: Anti-collision and transmission
protocol, 2000.
[13] ISO/IEC FDIS 18000-2. ISO 18000 Series: Information technology AIDC techniques
– RFID for item management – Part 2 – Parameters for air interface communications
below 135 kHz, 2003.
[14] ISO/IEC FDIS 18000-3. ISO 18000 Series: Information technology AIDC techniques
– RFID for item management – Part 3 – Parameters for air interface communications
at 13.56 MHz, 2003.
[15] ISO/IEC FDIS 18000-4. ISO 18000 Series: Information technology AIDC techniques
– RFID for item management – Part 4 – Parameters for air interface communications
at 2.45 GHz, 2003.
[16] ISO/IEC FDIS 18000-6. ISO 18000 Series: Information technology AIDC techniques
– RFID for item management – Part 6 – Parameters for air interface communications
at 860-960 MHz, 2003.
[17] ISO/IEC FDIS 18000-7. ISO 18000 Series: Information technology AIDC techniques
– RFID for item management – Part 7 – Parameters for air interface communications
at 433 MHz, 2003.
[18] K. S. Leong, M. L. Ng, and P. H. Cole. Positioning analysis of multiple antennas
in a dense rfid reader environment. In Proceedings of the International Symposium
on Applications and the Internet Workshops, pages 56–59, 2005.
[19] J. Myung, L. Wonjun, S. Jadideep, and K. Timothy. Tag-splitting: Adaptive collision
arbitration protocols for RFID tag identification. IEEE Transactions on
Computers, pages 56–59, 2007.
[20] J. Myung, L. Wonjun, and J. Srivastava. Adaptive binary splitting for efficient
RFID tag anti-collision. IEEE Transactions on Computers, pages 144–146, 2006.
[21] J. Myung, L. Wonjun, and K. S. Timothy. An adaptive memoryless protocol for
RFID tag collision arbitration. IEEE Transactions on Computers, pages 1096
–1101, 2006.