Efficient memoryless protocol for tag identification

• US 6,859,801 B1
• Filed: 05/30/2001
• Issued: 02/22/2005
• Est. Priority Date: 06/09/2000
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Lee, Kayi, Law, Ching, Siu, Kai-Yeung
• Primary Examiner(s): Kindred, Alford W.
• Assistant Examiner(s): RAYYAN, SUSAN F
• Application Number:
  US09/870,074
• Time in Patent Office: 1,364 Days
• Field of Search: 707/3, 340 1032- 1041, 340/10.31, 340/463, 340/465, 340/450, 342/450, 342/463, 342/465
• US Class Current: 1/1
• CPC Class Codes: G01S 13/751 wherein the responder or reflector radiates a coded signal
• CPC Class Codes: G06K 7/10049 binary tree
• CPC Class Codes: G06K 7/10861 sensing of data fields affixed to objects or articles, e.g. coded labels postal sorting B07C3/14, conveying articles B65G47/48
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The invention features a method and system for identifying a plurality of tags using an efficient memoryless protocol. The system includes a reader and a plurality of tags. The reader is adapted to maintain an ordered set of query strings; select a string from the set of query strings; broadcast a query message containing the selected string or a portion of the selected string to the tags; and receive a response from one of the tags. The tags operate without batteries and are adapted to respond to the selected string broadcast by the reader. Accordingly, the tag identification methods are efficient in terms of both time and communication complexities.

Claims

1. A method of identifying a plurality of tags, said method comprising:

(a) maintaining a set of query strings;

(b) selecting a string from the set of query strings;

(c) removing the selected string from the set of query strings;

(d) broadcasting to the plurality of tags a query message containing at least a portion of the selected string;

(e) receiving a response from the plurality of tags; and

(f) if the plurality of tags includes any unidentified tags, repeating steps (b) through (f).

2. The method of claim 1 wherein the query message includes the entire selected string.

3. The method of claim 1 further comprising if the received response identifies one of said plurality of tags, storing the identity of the identified tag.

4. The method of claim 1 further comprising if the received response indicates a collision has occurred, appending a first extension to the selected string to generate a first new query string and adding the first new query string to the set of query strings.

5. The method of claim 4 further comprising if the received response indicates a collision has occurred, appending a second extension to the selected string to generate a second new query string and adding the second new query string to the set of query strings.

6. The method of claim 5 wherein the appending the first extension to the selected string involves appending the first extension to the end of the selected string as a suffix to generate the first new query string.

7. The method of claim 6 wherein the appending the second extension to the selected string involves appending the second extension to the end of the selected string as a suffix to generate the second new query string.

8. The method of claim 4 wherein the first extension is a one.

9. The method of claim 5 wherein the second extension is a zero.

10. The method of claim 1 further comprising if the received response indicates a collision has occurred, appending a 00 to the selected string to generate a first new query string, appending a 01 to the selected string to generate a second new query string, appending a 10 to the selected string to generate a third new query string, appending a 11 to the selected string to generate a fourth new query string, and adding the first second, third, and fourth new query strings to the set of query strings.

11. The method of claim 1 wherein maintaining the set of query strings comprises initializing the set of query strings with a 0 and a 1.

12. The method of claim 1 further comprising repeating steps broadcasting the same query message and receiving the response for a pre-determined number of times if no collision is detected in the response.

13. The method of claim 1 wherein the receiving step further comprising estimating the number of tags in the response.

14. The method of claim 4 further comprising skipping a string having a second extension that is complementary to the first extension if there is no response to a query message containing the first new query string from the plurality of the tags.

15. The method of claim 1 wherein the broadcasting step includes broadcasting a short command in the query message to induce a one-bit response from the plurality of the tags.

16. The method of claim 1 wherein the set of query strings has an order wherein a length of any first query string occurring after a second query string is greater than or equal to a length of the second query string.

28. The method of claim 16 wherein the selected string is selected from the beginning of the set of query strings.

17. A system for identifying a plurality of tags, said system comprising:

a transceiver;

storage; and

a controller, said controller programmed to perform the functions of;

(a) maintaining a set of query strings;

(b) selecting a string from the set of query strings;

(c) removing the selected string from the set of query strings;

(d) causing the transmitter to broadcast to the plurality of tags a query message containing at least a portion of the selected string;

(e) receiving through the transceiver a response from the plurality of tags; and

(f) if the plurality of tags includes any unidentified tags, repeating steps (b) through (f).

18. The system of claim 17 wherein the query message includes the entire selected string.

19. The system of claim 17 wherein the controller is further programmed to perform the functions of storing the identity of the identified tag if the received response identifies one of said plurality of tags.

20. The system of claim 17 wherein the controller is further programmed to perform the functions of, if the received response indicates a collision has occurred, appending a first extension to the selected string to generate a first new query string and adding the first new query string to the set of query strings.

21. The system of claim 20 wherein the controller is further programmed to perform the functions of, if the received response indicates a collision has occurred, appending a second extension to the selected string to generate a second new query string and adding the second new query string to the set of query strings.

22. The system of claim 21 wherein the appending the first extension to the selected string involves appending the first extension to the end of the selected string as a suffix to generate the first new query string.

23. The system of claim 22 wherein the appending the second extension to the selected string involves appending the second extension to the end of the selected string as a suffix to generate the second new query string.

24. The system of claim 20 wherein the first extension is a one.

25. The system of claim 21 wherein the second extension is a zero.

26. The system of claim 17 wherein the controller is further programmed to perform the functions of, if the received response indicates a collision has occurred, appending a 00 to the selected string to generate a first new query string, appending a 01 to the selected string to generate a second new query string, appending a 10 to the selected string to generate a third new query string, appending a 11 to the selected string to generate a fourth new query string, and adding the first second, third, and fourth new query strings to the set of query strings.

27. The system of claim 17 wherein maintaining the set of query strings comprises initializing the set of query strings with a 0 and a 1.

29. The system of claim 17 wherein the set of query strings has an order wherein a length of any first query string occurring after a second query string is greater than or equal to a length of the second query string.

30. The system of claim 29 wherein the selected string is selected from the beginning of the set of query strings.