最近這幾年下來，無線射頻辨識系統(Radio Frequency Identification, RFID)
已經被應用在我們生活上的個個角落，舉凡是悠遊卡、電子護照或是物流管理都
能看到 RFID 的身影，而 RFID 是一種內建無線電波技術的晶片，晶片中可儲
存一些資訊，例如產品序號、產品資料、日期等。晶片的體積可以做的極小，可
以隨附於所要辨識的產品上，或者是內嵌到產品裡，並能夠以無接觸的方式，快
速、且大量的讀寫晶片內容的資料。最大的好處就是能提高整體物品管理效率，
比目前條碼系統具有更高的效率與彈性。而簡單的 RFID 系統架構是由讀取器
(Reader)、標籤(Tag) 與後端伺服器系統(back-end host system) 組成，其運作方式
則是依照標籤的特性不同來決定，以被動式標籤來說，通常是先由讀取器發送特
定工作頻率的無線射頻信號給標籤，當標籤收到讀取器的信號時，利用不同的頻
率來對讀取器進行回應。然而對主動式標籤來說恰恰相反，主動式標籤和被動式
標籤最大的差異就在於電力的來源，被動式的標籤是需要讀取器提供他回應的電
源，而主動式標籤則是擁有自己的電力來源，而通訊方式則恰好相反，先由標籤
發送特定工作頻率的無線射頻信號給讀取器，當讀取器收到的信號以後再利用不
同的頻率來對標籤進行回應。由於當標籤和讀取器之間是透過開放式的空間來互
相傳遞訊息，對於主動式標籤來說，當有很多標籤同時對讀取器發送請求時，就
會產生碰撞(collision)，因此為了成功地挑出每一個 RFID 標籤讓它們能夠分批
的與讀取器通訊，我們必須使用特殊的方法來達成目標，這個方法就是防碰撞
(anti-collision) 機制。
一開始我們先針對被動式標籤的防碰撞協定做一個簡單的介紹之後，再介紹
有關目前所有主動式標籤的防碰撞協定，並且根據每個機制的特性對這些機制做
比較和討論。在 RFID 系統中，現存的 RFID 防碰撞方法有 Space Division
Multiple Access (SDMA)、Time Domain Multiple Access (TDMA)、Frequency
Domain Multiple Access (FDMA) 與 Code Division Multiple Access (CDMA) 四
大類，而其中又以 TDMA 最適用於 RFID 系統上且廣受討論。TDMA 又可分
成以讀取器來主導的 Reader-driven 與由標籤來主導的 Tag-driven 兩類，由於
被動式標籤的防碰撞已經討論的相當多了，反而主動式標籤擁有自己的電源較為
便利於防碰撞卻乏人問津，所以我們的討論焦點會集中於 Tag-driven 的部份。
不過雖說是對於 Tag-driven 的部份討論，但是有些方法卻是從 Reader-driven
的部份針對 Tag-driven 的防碰撞作變形而來，其中就以 ALOHA 和 Query Tree
這兩種樣式的機制最為明顯，當然除了這兩種機制之外還有 CDMA 和 PDC 這
兩種的防碰撞機制也是有針對於主動式標籤防碰撞的研究。所以針對以上的防碰
撞機制我們除了介紹 TDMA 之外，也會介紹有關於 CDMA 和 PDC 這兩種分
類的防碰撞機制。
除了碰撞的問題之外，由於目前一些RFID 標籤(EPC 標籤)已經廣泛的應用
於商務方面，像是在製藥業裡就扮演著防偽的工具。對於物品的辨識來說，RFID
標籤是相當有用的，而且還可以促成物品和藥物的履歷能夠詳細的編輯和紀錄。
由於當 RFID 標籤和讀取器是透過開放式的空間，來做自動辨識和無線控管，
RFID 標籤可能會洩漏產品的資訊，使得躲在暗處的敵人可以悄悄追蹤或監控這
個RFID 標籤。因此，為了避免偽造的標籤欺騙合法的讀取器，令讀取器以為該
標籤是合法標籤的一員，由此可知它們並不是很好的身份辨識碼。除此之外，它
們身上都會有一個很小的微晶片，這個晶片可以提供使用於安全目標上的功能。
此晶片內的功能促成它能夠辨識一個產品的身份，也因此可以偵測和預防偽造的
發生。為了要達成這些安全性的目標，RIFD 標籤需要抵抗很多種類的攻擊，比
較特殊的攻擊就是標籤的複製，因此，RFID 標籤的弱點是很容易遭受複製和偽
造的攻擊。在這章節中，我們介紹已知用來抵抗偽造 RFID 標籤的技術，並且
提出這些技術的缺失與改善的方法，一開始我們會概略的介紹在RFID 標籤上偽
造的議題，並且檢視如何在 RFID 標籤上預防複製或偽造的已知方法，然後針
對這些防偽的方法做個比較和列出它們的優缺點和差異性並且指出需要進一步
改善的一些缺失。
在防碰撞機制中，參與防碰撞機制的對象總是所有的標籤，但實際上，在標
籤數量眾多的情況下，這將會耗費大量的資源與時間在這兩種目的上，然而假如
有辦法能夠先依某些條件對這些標籤做分類，再依照這個分類將這些標籤做分批
的防碰撞，如此防碰撞的效率就能夠大大提升，就如同前文所說，我們將討論重
點擺在主動式標籤上，由於主動式標籤有自己擁有電源的特性，所以我們提出了
EPDC (Enhance Power-based Distance Clustering) 這個方法，經由接收到訊號強度
的大小來判定標籤與讀取器的距離，利用這個距離來對標籤做地區性的分類，再
依此來達到分批防碰撞的效果。而我們提出的 EPDC 可以與任何主動式標籤的
防碰撞機制來搭配運作，而且是允許在非封閉，而且標籤是可移動的情形下，我
們也會以前文所提到的主動式標籤防碰撞的機制來搭配 EPDC 做比較。過去總
是把防碰撞機制與標籤防偽分開探討，但是假如偽造的標籤能騙過合法的讀取器
時，那代表著的意義就是很多偽造的標籤將會造成讀取器在防碰撞上嚴重的負擔
和威脅，雖然，在應用方面防碰撞是必要的，而防偽可能只是功能上的附加價值，
但是它所能造成的威脅和後果是不能夠輕忽的，所以我們提出了Anti-collision &
防偽(anti-counterfeiting) 的結合，利用這個機制將所有偽造的標籤排除，以減輕
在防碰撞上所造成的負擔和威脅，就應用的部份而言，以貨倉管理來說，當產品
有相當數量且需要登記的時候，最怕就是有假冒的情形發生，但是在經過我們提
出的方法處理之後，對所有產品做辨識時不但可以因為防碰撞的技術節省時間，
更可以因為防偽的功能而減少有假冒在裡面企圖魚目混珠或瞞天過海的威脅。

In the recent year, Radio Frequency Identification (RFID) system has been
widely used in many different areas. Its main purpose is to identify an object quickly.
The most popular application of RFID is in supply chain management for barcode
replacement. Different from traditional barcode, RFID has many advantages such as
no line-of-sight requirement, high toleration of harsh environments, long read range,
large storage space, traceability, and multiple reads at once. A RFID system consists
of the Reader(s) (or Interrogator), the Tag(s) (or Transponder) and the back-end host
system. In a RFID system, the tags are classified into passive and the active tags. For
passive tags, usually a reader propagates a RF signal at its working frequency, and
then the tag responds with a RF signal at different frequency. On the contrary, the
active tag that forwards to the reader a RF signal, and then the reader responds to the
tag. Because the information conveyed between the reader and the tag is through RF
channel. Once multiple tags or readers transmit data simultaneously, these data will
affect each other and cannot be recognized. Therefore, in order to successfully
singulate each active tag by the reader we need a particular method, which is the
anti-collision protocol for active tags. Although there are many approaches to achieve
anti-collision, they are not perfect and cannot be applied to everywhere. Therefore, we
first survey the existing anti-collision protocols and then propose some remedies
especially with a special focus on how to significantly increase the practicability and
how to efficiently implement these anti-collision protocols.
First, we present an overview of the existing anti-collision protocols for passive
tags and then we present the overview of the existing active RFID anti-collision
protocols. We also classify and compare them according to their major characteristics.
The existing multiple access techniques in RFID system include Space Division
Multiple Access (SDMA), Time Domain Multiple Access (TDMA), Frequency
Domain Multiple Access (FDMA) and Code Division Multiple Access (CDMA) four
major categories. TDMA is the most popular approach to achieve anti-collision and
further divided into Reader-driven and Tag-driven. Because there are too many
discussions about Reader-driven, not discuss about Tag-driven. Therefore, we will
concentrate our discussions only on the Tag-driven anti-collision schemes, which are
the main streams in the active tags environment. In those schemes, a tag must
dominate the anti-collision protocol and tell the reader what it should do. Tag-driven
protocols could be classified into two major approaches, one is Query tree-style since
it uses the tag ID to build a binary tree, while the other is Slotted ALOHA-style since
it uses a contention-based multiple access scheme to assign each tag into a unique timeslot. On the other hand, there are also DCMA protocol and PDC scheme for
solving active tag anti-collision; we also introduce both them in our thesis.
Radio Frequency Identification (RFID) technology has been used for over half a
century since World War II. RFID was used in anti-counterfeiting area before it was
used in retailers, the logistics and the global supply chains applications. In 2003, it
was suggested using the RFID system plus Electronic Product Code (EPC) to prevent
fake drugs by the U.S. Food and Drug Administration (FDA), and in 2004, Pfizer
and Purdue Pharma companies used RFID tag which attached to the item to prevent
fake drugs of Viagra and OxyContin. In recent years, several technologies used for
RFID tags against counterfeiting have been proposed. RFID consists of readers and
tags. There is an antenna in the reader that is used to connect tags, and the antenna of
the tag itself is connected to the micro-chip that was embedded into the tag. Due to
the advancement of the technologies, the size of RFID tag becomes smaller, its speed
becomes faster, its price becomes cheaper, and it can be used easily. The RFID
antenna can also be printed on the product or embedded in them. Generally speaking,
RFID tags can used for identification as well as for anti-counterfeiting purpose. The
attack which we hear most frequently is duplicating. That means the attacker can
acquire RIFD tag easily and can study it and read the contents of its memory, and
make another new tag with the same memory content of the valid tag. If a duplicated
tag is used in the goods, the reader will not be able to discover that it is a fake tag. We
overview the existing anti-counterfeiting schemes and then provide the comparisons
and remedy guidelines of these schemes.
In the active anti-collision protocols, all tags always are objective for these
protocols. However, in fact, it costs the RFID system too much resources and time to
accomplish both purposes when there are many tags present on the scene. Therefore,
we provide EPDC to solve this problem, in this approach, the tags are clustered based
on their distance from the reader, and this distance-based clustering is achieved by
changing the reader’s antenna power level. However, this scheme cannot be used to
solve the active tags collision; therefore, we think this scheme can solve this problem.
We show how the EPDC protocol could be integrated with other anti-collision
protocol for active tag, it makes the anti-collision protocol for active tag more useful,
we also give how the EPDC implements. We also analyze the advantages and
superiority of the proposed EPDC protocol in this thesis, and ensure its feasibility
analysis under the practical environments. In the past, the anti-collision protocol and
anti-counterfeiting protocol are usually treated separately. Normally, an
anti-counterfeiting protocol will begin when an anti-collision protocol ends. In fact, it
costs the RFID system too much resources and time to accomplish both purposes when there are many tags present on the scene. Therefore we propose a new protocol
called CRPAC to make both of them working together. While the anti-collision
protocol is progressing, the anti-counterfeiting challenges are piggybacked with the
anti-collision commands sent by the reader and the tag will reply the answers after
finishing anti-collision. This combined approach can kill two birds with one stone by
achieving both anti-collision and anti-counterfeiting at the same time. Compared to
the traditional separate anti-collision and anti-counterfeiting schemes, this combined
approach can complete most of the anti-counterfeiting procedure by the time
anti-collision process is finished. It saves a lot of time and message overheads to
anti-counterfeiting the tags due to the parallel processing of the anti-counterfeiting
and anti-collision protocols. Furthermore, CRPAC doesn’t make use of any
complicated mathematical operations (e.g. cryptographic primitives). The proposed
CRPAC algorithms is especially applicable to multiple tags scenario that requires
anti-collision and anti-counterfeiting. The proposed CRPAC protocol will perform the
best, if all the challenges sent out are within the timeslot allocations that are required
to resolve the anti-collisions. We will also verify the comparisons of the proposed
CRPAC algorithms in this thesis, and ensure its security, privacy and un-traceability
under passive attacks, and active attacks for guessing and query. CRPAC could make
the practical active RFID system more useful and secure.

[1] R. Weinstein, “RFID: A technical overview and its application to the enterprise,”
IT Professional, Vol. 7, No. 3, pp.27-33, 2005.
[2] S. E. Sarma, S. A. Weis, and D.W. Engels, ”Radio-frequency identification
systems,” in CHES '02, Springer-Verlag, 2002. LNCS no. 2523, pp. 454-469.
[3] R. Damith and C. Peter, “Security in Low Cost RFID”, Technical Report
Adelaide-AUTOID-WP-HARDWARE-027, Adelaide Auto-ID Center, 2006
[4] A. B. Jeng, L. C. Chang, and T. E. Wei, “Survey and Remedy of the
Technologies for RFID Tags against counterfeiting”, International Conference
on Machine Learning and Cybernetics 2009 (ICMLC 2009), China, July, 2009
[5] 鄭博仁, 張立中, 魏得恩, “已知RFID標籤防偽技術的缺失與改善”, 2009資
訊管理學術與實務研討會, 台北, 6月, 2009
[6] K. Finkenzeller, RFID Handbook: Fundamentals and Application in Contactless
Smart cards and Identification 2nd edition. John Wiley & Sons, 2003.
[7] D. Shih, P. Sun, D. Yen and S. Huang, “Taxonomy and Survey of RFID
Anti-collision protocols”, Computer and communications, vol.29, pp. 2150–2166,
2006.
[8] Z. Tang, Y. He, “Research of Multi-access and Anti-collision Protocols in RFID
Systems”, IEEE International Workshop on Anti-counterfeiting, Security,
Identification, 2007.
[9] MIT Auto-ID Center, “Draft protocol specification for a 900 MHz Class 0 Radio
Frequency Identification Tag,” http://auto-id.mit.edu, February 2003.
[10] B. Feng, J. Li, J. Guo and Z.-H. Ding, “ID-Binary Tree Stack Anticollision
Algorithm for RFID,” In Proceedings of the 11th IEEE Symposium on
Computers and Communications (ISCC’06), 2006.
[11] C. Law, K. Lee and K. Siu, “Efficient Memoryless Protocol for Tag
Identification,” In Proceedings of the 4th International Workshop on Discrete
Algorithms and Methods for Mobile Computing and Communications, ACM,
pages 75-84, 2000.
[12] J. Choi, D. Lee and H. Lee, “Query Tree-Based Reservation for Efficient RFID
Tag Anti-Collision,” IEEE Commun. Lett., vol. 11, no. 1, pp.85-87, 2007.
[13] EPCTM, “Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID
Protocol for Communications at 860MHz-960MHz,” Version 1.1.0, 2007.
[14] J. Myung and W. Lee, “Adaptive Splitting Protocols for RFID Tag Collision
Arbitration," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no.
6, June 2007.
[15] D. Lee, K. Kim and W. Lee, Q+-Algorithm: An Enhanced RFID Tag Collision
Arbitration Algorithm," Springer-Verlag: Lecture Notes in Computer Science,
2007.
[16] J. Myung and W. Lee, “Adaptive Binary Splitting for Efficient RFID Tag
Anti-collision,” IEEE Commun. Lett., vol.10, no.3, pp.144–146, 2006.
[17] J. Park, M. Chung and T.-J. Lee, “Identification of RFID Tags in Framed-Slotted
ALOHA with Tag Estimation and Binary Splitting,” ICCE'06, 2006.
[18] W. Chen and S. Horng, P. Fan, “An Enhanced Anti-collision Algorithm in RFID
Based on Counter and Stack,” Systems and Networks Communications on ICSNC,
2007.
[19] K. Ali, H. Hassanein and A. Taha, “RFID Anti-collision Protocol for Dense
Passive Tag Environments,” 32nd IEEE Conference on Local Computer
Networks, 2007.
[20] H. Cho, W. Lee, and Y. Baek, “LDFSA: A Learning-Based Dynamic Framed
Slotted ALOHA for Collision Arbitration in Active RFID Systems”
Springer-Verlag, GPC 2007, LNCS 4459, pp. 655-665, Berlin Heidelberg, 2007
[21] N. Li, X. Duan, Y. Wu, S. Hua, B. Jiao, “An Anti-collision for Active RFID”,
2006 IEEE, 1-4244-0517-3/06, 2006
[22] Y. J. Lee, S. H. Kim, J. H. Sim, and Y. S. Lee, “A New RFID Active
Anti-collision Algorithm Fully Compatible With an ISO-IEC_CD 18000-6C
Generation 2 Standard”, School of Electrical and Electronic Engineering, Yonsei
University, Korea.
[23] S. H. Choi and C. H. Poon, An RFID-based Anti-counterfeiting System, IAENG
International Journal of Computer Science, 35:1, IJCS_35_1_12, 19 Feb. 2008.
[24] EPCTM Radio-Frequency Identity Protocols Class-1 generation-2 UHF RFID
Protocol for Communications at 860 MHz - 960 MHz, Version 1.0.8, 2005.
[25] Juels, A. Strengthening EPC Tags Against Cloning. in ACM Workshop on
Wireless Security (WiSe). 2005.
[26] Duc et al. Enhancing Security of EPCglobal Gen-2 RFID Tag against
Traceability and Cloning. in The 2006 Symposium on Cryptography and
Information Security. 2006. Hiroshima, Japan.
[27] P. Tuyls and L. Batina. RFID-tags for Anti-Counterfeiting. In D. Pointcheval,
editor, Topics in Cryptology - CT-RSA 2006, LNCS, San Jose, USA, February
13-17 2006. Springer Verlag.
[28] W. J. Yoon, S. H. Chung, S. J. Lee, and Y. S. Moon, “Design and
Implementation of an Active RFID System for Fast Tag Collection”, Seventh
International Conference on Computer and Information Technology, Department
of Computer Engineering, Pusan National University, Busan, Republic of Korea
[29] S. H. Choi and C. H. Poon, “An RFID-based Anti-counterfeiting System”,
IAENG International Journal of Computer Science, 35:1, IJCS_35_1_12, 19
February, 2008.