使用前序樹有效率的辨識已註冊的RFIDs

An Efficient Prefix-Tree Algorithm for Recognizing Pre-Registered RFIDs

黃勝宏(Sheng-Hung Huang)

指導教授 ： 何建明 ； 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2006年)

摘要

以往，每件商品都需一件一件的朝讀取機掃描。現在，我們為了節省大量的掃描時間，想要在一次掃描時間內辨識出所有的商品，這就是我們所採用的RFID無線射頻技術。
為了達到以上的目的，所要保證的一項重點就是不能有商品的辨識遺漏，滿足了這個條件，接下來的要求是增快辨識速率，以目前捷運悠遊卡為例，讀取一張卡片所需的時間為0.4秒，如果商品移動速度快就可能發生有商品遺漏的情況，因此要降低辨識所需時間。
我們所採用的Protocol是由EPC所以訂製的900MHz Class 0標準，此標準所採取的防止辨識遺漏的方式為binary tree方法。這個方法必須對每一個商品皆須完整讀取其條碼才能做出辨識。
在不影響其標準架構下，我們修改其演算方法，以達到我們所要加快辨識速率的目的，我們將原先的binary tree改進為prefix-tree。首先我們將所需的辨識的條碼註冊於我們所建造的prefix-tree，接著這些條碼需要被辨識時，便在我們所事先建造的prefix-tree做辨識。我們的作法不需完整讀取其條碼即能做出辨識，其效能顯而易見的可比較出。

關鍵字

前序樹 ； 效率 ； 無線射頻 ； 標籤 ； 演算法 ； 辨識 ； 註冊 ； 碰撞 ； 防碰撞 ； 多重存取 ； 倉庫

並列摘要

In the past, it was necessary to scan products one by one to record information about usage or the number of items in stock. Now, to reduce the scanning time, we want to recognize multiple products with only one scan. To this end, we implement a wireless technique called radio frequency identification (RFID), which allows multi-access.
Our objective is twofold. First, we must ensure that the system can recognize every product without loss of information. Second, we need to improve the recognition (scanning) speed. In this thesis, we take Easy Card (issued by Taipei Smart Card Corporation) as an example of RFID, where the reader takes 0.4 seconds to scan a card. Information would lost if the card is moved over the reader in less than 0.4 seconds, so we have to reduce the time required for recognition.
We follow the 900MHz Class 0 Protocol Standard of Electronic Product Code (EPC), which implements a binary tree algorithm for anti-collision to prevent information loss. The system has to read an ID code completely (as a string of binary digits) to ensure recognition.
Without changing whole architecture of the standard protocol, we modify the algorithm, which interacts with the reader and the tag. To speed up the recognition time, we improve the binary tree to prefix-tree. First, the process pre-registers the tags which need to be recognized to build a prefix-tree. Second, when the tags need to be recognized, we operate the prefix-tree for recognition. Our approach does not need to read the whole ID code. It only receives bits of the code that we need, and then the reader can get the IDs of the tags.

並列關鍵字

Prefix-Tree ； Efficient ； RFID ； Tag ； Algorithm ； Recognition ； Register ； Collision ； Anti-Collision ； Multi-Access ； Warehouse

參考文獻

[2] “Smart Dust: communicating with a cubic-millimeter computer”, Brett Warneke, Matt Last, Brian Liebowitz, Kristofer S.J. Pister, IEEE JNL, JAN 2001

[5] “Smart Identification Frameworks for Ubiquitous Computing Applications”, KAY R?MER*, THOMAS SCHOCH, FRIEDEMANN MATTERN, THOMAS DUBENDORFER, CH-8092 Zurich, Switzerland, Wireless Networks, Springer 2004

[12] “Colorwave: An Anticollision Algorithm for the Reader Collision Problem”, James Waldrop, Daniel W. Engels, Sanjay E. Sarma, MIT Auto-ID Center, Communications, ICC '03. IEEE International Conference

[13] “Draft Protocol Specification for a 900MHz Class 0 Radio Frequency Identification Tag”, MIT Auto-ID Center, 23 Feb 2003, http://www.epcglobalinc.org/standards/specs/

[15] “Efficient Memoryless Protocol for Tag Identification”, Ching Law, Kayi Lee, Kai-Yeung Siu, MIT Auto-ID Center, October 2000, http://auto-id.mit.edu/