Benchmark Protocol

The benchmark algorithm: EPC Class1 protocol, which is developed upon binary tree algorithm

To my knowledge, two stream algorithms both have its own pros and cons, which mostly depends on the environment they are working in, or tasks they are dealing with. Environment like number of tags can exist is a typical consideration in choosing which algorithm to use. Different tasks like detect the existing of tags or monitor tags existing constantly are to be concerned. So it is hard to say one kind of or specific one algorithm is much better others. My point is it depends on the practical situation in our application.
Example, a system to check out in a supermarket may only detect the existing of an item once, whereas, a system to monitor goods in a fridge may sense the same item many time. First scenario mostly has different items in every sensing, but the later one may sensing mostly the same item constantly. Unfortunately, current algorithms only deal one scenario well, or good at one scenario comparing to the other algorithms.

The trend is class 1 Gen2 those days. I will implement Class 1 first, and then extend to Gen2. These two algorithms have been already standarized, and implemented in industry.

An explanation of EPCGlobal class 0, class 1, class 1 Gen2
http://www.enigmatic-consulting.com/Communications_articles/RFID/RFID_protocols.html

Official website for documentation of these protocols:
http://www.epcglobalinc.org/standards/

Research on Current Technique

We can identify the collision bit by bit if Manchester coding is used. This possibility is useful when there is not many tags in an interrogation area.

Weakness of Passive Tag:
Tag collisions is problematic as a tag has limited power and functionality. A passive tag can only transmit data by reflecting the reader transmitted electromagneticwaves, and hence, cannot detect nor communicate with the neighboring tags. The energy received by a tag is usually less than 100μW. Accordingly, CSMA-related methods are not practical anti-collision algorithms for the passive tags.

ISO 14443-3
Type A bit collision detection
Type B series of command sequence
ISO 15693
More detail about ISO, they are not just anti-collision protocols.
http://rfidwizards.com/index.php?option=com_content&task=view&id=242&Itemid=174

After review some anti-collision articles, I find out there are two main streams of anti-collision algorithm: ALOHA based and tree based. First one is probabilistic and the last one is deterministic.

After one weak research, I finished the first step in reviewing current papers about those proposed algorithms, and have better understanding the constrains existed in development process. I will concentrate on the most common scenario: passive tags with one reader sharing one channel, to consider the algorithm. Next step is brainstorming.

Understanding what have been achieved so far

Constraints in RFID communication in particular:
i. Lack of internal power source in the passive tags. This requires the tag reader to powerupthese tags whenever it needs to communicate with them.
ii. Total number of tags is unknown.
iii. Tags cannot communicate with each other. Hence collision resolution needs to be doneat the tag reader.
iv. Limited memory and computational capabilities at the tag. Thus the resolution protocolmust be simple and incur minimum overhead from the tag’s perspective.

Measurement in RFID anti-collision performance:
a. Minimal Delay: Time taken for identification of all the tags should be low. From a userpoint of view, this should not be perceptible.
b. Power consumption: Due to the absence of an internal power source, power consumedby the tags should be minimal. The amount of power consumed is influenced by the totalnumber of replies sent by each of the tags. An efficient protocol will minimize themessages between the tag and tag reader.
c. Reliability and Completeness: All the tags in the range of the tag reader should getidentified correctly.
d. Line-of-sight Independence: The object attached with the tag can be located anywhereas long as they are in the range of the tag reading device.
e. Robustness: The protocol should work irrespective of environmental conditions.
f. Scalability: The protocol should be scalable to accommodate an increase in the numberof tags.


Four basic algorithms in RFID:

• Splitting or Tree Search, use coin flipping or tag ID, needs feedback from reader, and counter


• Memoryless or Query Tree, maximum number of tag assumed, prefix p, feedback each cycle, no counter. This algorithm sometimes is refered as Binary Tree in many literatures
  
• I-Code or frame-slotted Aloha, not 100% detection of tag, need experimental measurement in refining protocol, particular in estimating number of tags


• Contactless, special modulation: 00ZZ->0, ZZ00-> 1

Source:
C. Abraham, V. Ahuja, A.K. Ghosh, P. Pakanati, InventoryManagement using Passive RFID Tags: A Survey, Department ofComputer Science, The University of Texas at Dallas, Richardson,Texas, pp. 1–16, October, 2002.
This is a very good paper, which is almost the first part of
Taxonomy and survey of RFID anti-collision protocols DH Shih, PLSun, DC Yen, SM Huang - Computer Communications, 2006

Standard Protocols:

EPCglobal Bit-based Avg. : 200 tags/sCLASS 0 Binary tree Max. : 800 tags/s(UHF) (Deterministic)

EPCglobal Binary tree Not specifiedCLASS 1 (Bin slot)(UHF) (Probabilistic)

ISO 18000-6 Dynamic Avg. : 100 tags/sTYPE - A Framed ALOHA(UHF) (Probabilistic)

ISO 18000-6 Binary Tree Avg. : 100 tags/sTYPE - B (Probabilistic)(UHF)

Binary Tree and Dynamic Frame-Slot Aloha(DFSA) are two commonly implemented algorithms. Grouping is a major investigating area in improving DFSA.

SSim - a Simple Discrete-Event Simulation Library:

http://serl.cs.colorado.edu/~carzanig/ssim/

First Day Research, deciding which path to go

Search some books about network simulation in the library.

Search the existed RFID simulator. Most of them are not on MAC level, but on application level, to help software programmer develop RFID application in real business case.

About Simulator:
NS-2 needs C++ and OTcl. After brief reading of the NS2 manual, I found out C++ must be used to customize the protocol. It seems not enough time to build the project upon this simulator. Lots of project built up based on performance measurement by this simulator, which is the benefit in using this tool.

J-Sim is out of date, not enough reference can be a problem.


Next Step
As to get familiar with simulator cost too much time, next step is to search the material in NS2 simulation, if these materials are insufficient in shortening the developing time, I may consider to build my own simulator, like the one we use in COMP5416

Design of a RFID anti-collision protocol for RFID Tag-Reader Communications

Project Topic:
Due to the receding cost of manufacturing, Radio Frequency Identification (RFID) systems are used in a variety of applications to tag and track physical objects. A typical RFID system operation involves numerous tags to be present simultaneously in the interrogation zone of a single reader. Any responses from the tags can collide, leading to retransmission of tag information that results in increase in the access delay. Besides, readers physically located near one another may interfere each other. Such reader collision must be minimized. In this project, we will design a procedure to deal with tag and reader problems, while taking environmental effects into account.
===========RFID====ERA=============