Please explain the tree-walking protocol used when there is more than one tag within a read field.
—Ken
———
Dear Ken,
One challenge with RFID systems involves ensuring that a reader talks to only one tag at a time when there are multiple tags within a read field. If multiple tags respond to the device, it can not decipher the information, due to what is known as tag collision (see What Is Tag Collision? and How Can Companies Avoid Collision?).
There are different methods for ensuring that tags can be read when there are multiple tags within a read field. One is the tree-walking algorithm. There are a variety of tree-based algorithms, but they essentially operate in the same manner that a teacher might organize students in a large class. The teacher might say, “If your last name starts with an A, please stand up.” If five students stand up, he or she might then say, “If your last name starts with an A and the second letter is a B, remain standing. Everyone else sit down.” If two students remain standing, the instructor might then say, “If your last name starts with an A, the second letter is a B, and the third letter is an A, remain standing. If not, please sit down.” And so forth. In so doing, the teacher can identify the first student in an alphabetical progression.
Similarly, a reader will say to a tag, “If the first binary digit in your serial number is a 0, respond.” Ten tags might respond. The reader can then say, “If your first digit is a 0 and your second digit is a 1, respond.” Five tags might respond. The device can then ask about the third digit and so forth, until only a single tag responds.
Another method of enabling a reader to talk to tags individually is the ALOHA protocol, developed in the 1970s for a packet radio network at the University of Hawaii. With the ALOHA protocol, a station transmits data whenever it has something to send. The transmitting station learns whether the transmission was successful or experienced a tag collision with other transmissions, by listening to the broadcast. In the event of a collision, the sender station transmits again after a random wait period. The ALOHA protocol was adapted for RFID, whereby a reader transmits to tags and then just listens. A tag periodically sends data packets after a random period in which it is not responding.
Another method for solving the tag-collision problem is to have a reader listen for multiple tag responses. When that occurs, the interrogator then sends out a special signal, known as a “gap pulse.” When the tags receive this signal, each waits for a random interval before transmitting its data. That interval is determined by a counter stored on the tag’s chip. Each tag should generate a unique number interval, so the tags send their information at different times.
I hope that answers your question.
—Mark Roberti, Founder and Editor, RFID Journal