You can work in pairs if you'd like.
(The pairs needn't be the same as in homework 1.)

Overview

The goal of this assignment is to design, iteratively refine, and evaluate an inventorying algorithm for an RFID reader. Evaluation is done using a simulation infrastructure that we provide. It comes completely working, meaning that a very, very bad inventorying algorithm is already implemented.

In our version of the inventorying problem, a number of tags simultaneously enter the field of the reader, sit there for a fixed time, and then simultaneously depart. When they leave, the reader has a list of EPCs it believes belong to tags in that group. There is no reader design that always gets this list just right. Among other things, if there are too many tags, and they stay in the reader's field for too short a time, it's simply impossible to read all the tags. That's an example of false negatives: the reader incorrectly asserts some EPCs were not in the group (by failing to list them). False negatives can occur even for small batches of tags, because communication is unreliable. The other kind of mistake the reader can make is false positives: the reader may list an EPC that doesn't belong to any of the actual tags. That can happen because of undetected communication errors.

We're going to measure quality of the reader's output using two metrics: precision and recall. Precision is the fraction of the EPC's on the reader's list that were actually owned by tags in the group that just passed by. Recall is the fraction of EPCs in that tag group that are on the reader's list. (If R is the set of EPCs on the reader's list, and T the actual set on the tags, then precision is |R∩T|/|R| and recall is |R∩T|/|T|.) There is typically a trade-off between them: higher recall algorithms have lower precision, and vice versa.

This graph profiles the performance of the (lousy) algorithm built in the skeleton code.

A perfect reader would have 100% precision and recall for all numbers of tags. A realizable reader can do a lot better than this one, but there will always be situations in which it makes mistakes.

The Open-Ended Goal

The recall and precision of a particular algorithm will depend on many factors. The ones controllable in the simulator are:

• the number of tags (20-160)
• the amount of time the tags stay in the reader's field (1000 msec.)
• the BER (bit error rate) of the channel, in both directions (1%)
• the bit rate of the channel (100,000 bps)
• the distribution of EPC values among the tags (uniform, gaussian, or consecutive)
  • uniform: EPCs chosen at random over [0,2⁶⁴-1]
  • consecutive: EPCs are consecutive starting at a randomly chosen value in [0,2⁶⁴-1]
  • gaussian: EPCs are chosen according to a Gaussian distribution centered at a random 64-bit value and with standard deviation of about 24 bits.
• the number of bits in the EPC (64)
• the decision to transmit error detection bits or not (CRC/no CRC)

To keep the problem to the size of a homework, you can assume that all of these factors have fixed values, except for the ones in red. The fixed values are the ones shown in parentheses. In that sense, the only environmental factors unknown when you're designing and implementing the algorithm are how many tags there will be and what the distribution of their EPC values will be. (You, the designer, make a design-time decision about whether or not to use CRCs.)

The ultimate goal is to design the "best" reader algorithm you can. As a result, a sub-goal is to decide what "best" means. One possibility is to aim for generality: a reader that does pretty well over a pretty wide range of situations. Another is to aim for peak performance: a reader that does an outstanding job over a narrow range of situations (but may not do very well outside that range, as a result).

It is intended that this process be experiential and iterative. You first decide on some goal (e.g., "generally good performance"). You design an algorithm you think will achieve that. You implement and get simulation results for it. You then modify your design/implementation in an attempt to get it to perform even better. That could involve tuning it (i.e., tweaking parameters of the algorithm), if it's behaving close to how you hoped, or perhaps making major changes, if the experiments point a more substantial flaw in the initial design. Ultimately you stop doing this. Ideally, when you stop, it's because you think it's not possible to create a reader that does a better job of achieving your goal than the one you have. Realistically, for this assignment, you stop either when you reach that conclusion or you run out of time to spend on this. (I anticipate that there's easily enough time for at least an implementation and a tweak, in the minimal case.) Especially if you work in pairs, it would also be okay to initially implement two quite different approaches, experiment with them, then select the more promising one and tweak it. (That approach is sensible, in general, when there are multiple very distinct approaches and reasons to think that each might in fact be the best.)

What you'll hand in when done is your code and a report indicating what you did: what your goals were; what your initial design was and why you chose it; what the outcomes of experiments with its implementation were; what changes you decided to make, and why you thought they'd improve things; experimental results having made those changes; and finally a discussion of what you'd do next if you had more time.

This assignment is really about the process just outlined (which we'll understand through your report, rather than the code or even the final algorithm itself). It is not required that the reader you end up with beats anyone else's reader at anything, for instance. It is intended that you cannot really start any of this until you understand what the possible approaches are, and what choices you (meaning you) have to make. It is also intended that your process make sense: it should get you to your final reader design efficiently. This isn't about just building anything and seeing how it works. What we're trying to do is a prefix of building the best reader in minimal time, where the "prefix" is because we have only an assignment's worth of time to work on this.

(If any of that isn't clear, definitely ask questions!)

Basic Reader/Tag Operation

All communication in this "network" is initiated by the reader - the tags never speak unless spoken to. Because the reader doesn't know which tags are there, it's not possible for it to send unicast frames: to do that requires a destination address (i.e., a name for a particular tag), and that's what it's trying to find out. Instead, all frames sent by the reader are broadcast. Frames cause tags to change their internal state. The action a tag takes on receiving a frame differs depending on its current state. The trick is to manipulate the (unknown) states of all the tags in a way that causes just one to be in a state where it will answer a request to send its EPC, and then to send that request.

Because the tags are primitive, they have very limited memory, and can only do a few things. Those things are defined by their specification and built into their hardware (and so not modifiable by you, the designer of the reader's software). The tags used in the simulator are based on the EPC Class-1 Generation-2 UHF RFID Protocol specification. (That's a local copy of the spec, now slightly out of date. That spec, and it's more recent updates, an be found on this page.) The tags implemented in the simulator are somewhat simpler. This page gives an overview of them, and how they differ from the specification cited.

The essential problem in inventorying the tags is reliability, which for these involves issues of error detection and collision resolution, both of which we've looked at in the context of Ethernet and 802.11 wireless networks. In the case of RFIDs, collisions occur because multiple tags are likely to respond to a reader's request for EPCs. An apparent novelty of RFID collision resolution is that it runs in the receiver, rather than the senders, of the colliding frames. That isn't terribly important, except that it implies that all colliders are synchronized (by the reception times of frames from the reader) and almost certainly have to operate homogeneously.

You should read the description of the simulator and refer to the specification on which its based to gain a full understanding of how the system operates. But here it is in a nutshell. (See Figure 6.19, page 41 of the specification.)

Each tag has a Selected bit (SL), an Inventoried bit (INV), and an electronic product code (EPC). Both SL and INV are initially false.

The reader sends a Select directive, allowing it to set the SL or INV bits on some or all tags. Tags decide whether or not to set their bit depeneding on a mask sent in the Select frame. If the mask matches some substring of their EPC (which is a 64-bit string), they do so; otherwise they do nothing. A mask of length 0 is matched by all tags.

The reader can also send any of three forms of Query directive. Queries provide a window size and matching values for SL and INV. Tags whose current SL and INV values match those in the Query frame pick a random number from 0 to the window size minus one. If they pick 0, they respond with an RN16 frame containing a random number. The random number serves as a temporary address for the tag.

If the reader gets back just one random number, it sends an ACK frame to that random number. The tag that sent it originally recognizes it, and responds with an EPC frame, providing the reader its EPC. If the next frame that tag hears is one of the Query frames, it sets its INV bit to true (footnote, Figure 6.19 of the specification).

A Strawman Collision Resolution Scheme

A strawman collision resolution algorithm is implemented in the simulator code. It causes each tag that has not yet been inventoried to pick a random slot between 0 and 31. Tags respond only if they have picked slot 0. If one tag does so, an EPC is (eventually) sent back to the reader, and that tag stops participating. Otherwise, there has been a collision or no tag has picked slot 0, and no progress has been made. Whether or not progress has been made, the reader just repeats this scheme over and over. (It has no reason to stop. For one thing, it can never know if it has managed to hear from all the tags. For another, it has nothing better to do anyway.)

Like the tags, the reader can be thought of as a simple FSA. Here's a picture of the strawman reader's FSA. The transition label A/B means "if I hear an A frame, send a B frame and take this transition". If A is empty it means take the transition without hearing anything, and B empty means don't send anything. Other matches any condition not matched by other transitions. That includes a timeout, if nothing is heard back from the tags for long enough.

This scheme is particularly simple to analyze, so it's worth doing because the results can tell us something about how well it can work. If there are N tags in the reader's field, and they pick from Q slots, the probability that exactly one picks slot 0 is N(1/Q)((Q-1)/Q)N-1. The expected time to identify one tag, I(N,Q), is therefore the inverse (assuming packets are lost only due to collisions), QN/(N(Q-1)N-1).

Let T(N,Q) be the expected time to identify all tags when N tags start in the reader's field, and packets are lost only due to collisions. T(N,Q) = I(N,Q) + T(N-1,Q), with the boundary condition T(0,Q) = 0. That isn't too useful, except that it provides a handy way to compute T(N,Q). Here are some results, obtained using Excel for Q = 32:

Experience with the simulator indicates our reader/tags should be able to get through somewhere around a thousand "rounds" of the algorithm in a second, so we expect to get pretty good results from this simple scheme for N < 125 or so.

Warm-Up Exercise

There is an intentionally introduced issue in the strawman algorithm. The strawman code implements the FSA shown above; the issue is with the FSA. The warmup is to change the FSA that is implemented. This is a one token change to the code where nearly all your activity will be, in RFIDReader.inventory().

The graph at the top of this assignment shows the profile for the strawman once the change is made. Here is the profile for the code you actually get, pre-change:

It should be obvious looking at it that something is very wrong: it is unable to identify all the tags even for numbers far below what our analysis indicated should be possible. The issue is that the analysis assumes all messages are reliable, whereas in fact they're not. Failed messages affect the FSA in a couple of ways. One is that the reader sends the SELECT command only once; any tag not receiving it can never be inventoried. A second is a bit more subtle. When the reader is in state ACKed (in the diagram - it has a different name in the code), it's waiting for a tag to send its EPC. If the tag sends it, and the next command the tag hears is any kind of query, the tag turns on its inventoried bit. That effectively stops it from engaging further in the protocol. The problem is that the EPC it sent might not be received by the reader, due to transmission errors. When that happens, it can never be inventoried.

As this is just a warm-up, we're looking for something easy to do that might address these problems, in an attempt to improve recall. The simplest thing is to return to the START state every once in a while. There are many ways to do this, with minimal code changes, but my suggestion is to do so whenever no tag responds to a QUERY message. Making that change, you should end up with results that look like the graph at the top of the assignment. (Note that recall improves, but precision is somewhat worse. It should be clear to you why that happened.)

Collaborative Graphing

The graphs shown on this page were produced by a tool that is available to you. See this page for details.

Obtainables

Simulator Javadoc

Most all your code goes in method sim.RFIDReader.inventory(). The Javadoc and simulator documentation should help explain anything else you need to know.

Simulator source

It comes with a makefile - just say make in the topmost directory to build. It comes with an optional driver to run "the standard experiments." See the graphs page for more information.

To run from the command line, say something like this:

java -cp classes sim/RFIDSim 500 20 uniform .01 100000 1000

The command line arguments are explained in a comment preceding sim.RFIDSim.main() in the source (and so are in the Javadoc as well).

EPC Class-1 Generation-2 UHF RFID Protocol Specification

Simulator Description

Results Page
Make sure to read the graphs page before trying this link. (Otherwise, the link won't show you want you're probably looking for.)

Turn-In Procedures

• Report
  Prepare a document named Report.xxx, where 'xxx' is either pdf or txt.
  Turn this file in online, along with the other required files (described next).

• Online Turnin
  Do a make clean (or equivalent if you're using something other than make to build). Then turn in all your files, including your report. Please do not tar or zip your files - the turnin software does that already, and it's easier on our end if we don't have to figure out how many times to have to untar/unzip the submission to get to the files.

• One Turnin per Team or Person