Optimization of a binary tree traversal with secure communications

• US 20040134984A1
• Filed: 10/27/2003
• Published: 07/15/2004
• Est. Priority Date: 10/25/2002
• Status: Active Grant

• Current Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Original Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Inventors: Bandy, William R., Powell, Kevin J., Shanks, Wayne E.
• Granted Patent: US 7,195,173 B2
• Time in Patent Office: Days
• US Class Current: 235/451
• CPC Class Codes: G06K 7/0008 General problems related to the reading of electronic memory record carriers, independent of its reading method, e.g. power transfer
• CPC Class Codes: G06K 7/10049 binary tree

Abstract

Methods and systems for the negotiation of a population of RFID tags with improved security is provided. In one aspect, a binary traversal is performed to singulate tags without using information that directly identifies the tags in the tag population. A key is generated to identify each RFID tag of the population of RFID tags. The generated key does not include bits identifying an item with which the particular RFID tag is associated. A binary tree algorithm is operated to identify one or more tags in the population of RFIDs tags using the generated keys. In another aspect, frequency hopping and/or spread spectrum techniques are used to provide improved security while negotiating tags. In another aspect, the reader causes the tags to scroll series of bits back to the reader for each bit sent to the tags to provide improved security.

Claims

1. A method for a radio frequency identification (RFID) tag to communicate with a RFID reader, wherein the tag stores a corresponding identification number, wherein the identification number comprises a first bit pattern, comprising:

(a) receiving a first at least one bit from the reader to cause the tag to respond to a binary traversal operation with a second bit pattern;

(b) engaging in a binary traversal operation with the reader, including the steps of;

(1) receiving a series of bits from the reader, and

(2) responding to each bit of the series of bits with a corresponding bit of the second bit pattern.

2. The method of claim 1, wherein step (b) comprises:

reading the second bit pattern from storage in the tag.

3. The method of claim 1, wherein step (b) comprises:

randomly generating a bit value for each bit of the second bit pattern.

4. The method of claim 3, further comprising:

(c) storing the second bit pattern.

5. The method of claim 4, further comprising:

(d) engaging in a second binary traversal operation with the reader, including the steps of;

(1) receiving a second series of bits from the reader, and

(2) responding to each bit of the series of bits with a corresponding bit of the stored second bit pattern.

6. The method of claim 3, further comprising:

(d) engaging in a second binary traversal operation with the reader, including the steps of;

(1) receiving a second series of bits from the reader, and

(2) responding to each bit of the series of bits with a second randomly generated bit value.

7. The method of claim 1, further comprising:

(c) receiving at least one bit from the reader to cause the first tag to transmit its identification number; and

(d) transmitting the identification number.

8. The method of claim 1, further comprising:

(c) receiving a command from the reader; and

(d) executing the command.

9. A radio frequency identification (RFID) tag, comprising:

an antenna;

a modulator coupled to said antenna, wherein said modulator is configured to backscatter modulate bits received from said antenna with response bits;

a first storage that stores a first bit pattern that defines an identification number; and

a second storage that stores a second bit pattern that does not include bits identifying an item with which the RFID tag is associated;

wherein a first bit combination received from a reader causes said tag to respond to a binary traversal with the first bit pattern; and

wherein a second bit combination received from the reader causes said tag to respond to a binary traversal with the second bit pattern.

10. The RFID tag of claim 9, wherein said second bit pattern is a random bit pattern.

11. The RFID tag of claim 10, further comprising:

a random bit pattern generator that generates said second bit pattern.

12. The RFID tag of claim 11, wherein said random bit pattern generator comprises an oscillator.

13. The RFID tag of claim 9, wherein said second bit pattern is non-correlated with said first bit pattern.

14. The RFID tag of claim 9, wherein said second bit pattern is a fixed bit pattern.

15. The RFID tag of claim 9, wherein said second bit pattern includes bits corresponding to a location on wafer for an integrated circuit chip of the RFID tag.

16. The RFID tag of claim 9, wherein said second bit pattern includes bits corresponding to a time stamp.

17. The RFID tag of claim 9, wherein said second bit pattern includes a portion of the first bit pattern.

18. The RFID tag of claim 9, wherein said second bit pattern includes hashed bits from the first bit pattern.

19. A method for a radio frequency identification (RFID) tag to communicate with a RFID reader, wherein the tag stores a corresponding identification number, comprising:

(a) receiving a first at least one bit from the reader to cause the tag to respond to a binary traversal operation with a key;

(b) engaging in a binary traversal operation with the reader, including the steps of;

(1) receiving a series of bits from the reader, and

(2) responding to each bit of the series of bits with a randomly generated bit of the key.

20. A radio frequency identification (RFID) tag, comprising:

an antenna;

a modulator coupled to said antenna, wherein said modulator is configured to backscatter modulate bits received from said antenna with response bits;

a storage that stores a bit pattern that defines an identification number; and

a random bit pattern generator that generates said second bit pattern;

wherein a first bit combination received from a reader causes said tag to respond to a binary traversal with the first bit pattern; and

wherein a second bit combination received from the reader causes said tag to respond to a binary traversal with bits generated by said random bit pattern generator.

21. A method for a radio frequency identification (RFID) reader to communicate with a population of RFID tags, wherein each tag stores a corresponding identification number, wherein the identification number comprises a first bit pattern, comprising:

(a) transmitting a first at least one bit to the population of tags to cause tags to respond to a binary traversal operation with a second bit pattern;

(b) performing a binary traversal operation to singulate a first tag of the population of tags, including the step of;

(1) transmitting a series of bits to the population of tags, and

(2) receiving a corresponding bit of the second bit pattern from the first tag in response to each bit of the series of bits.

22. The method of claim 21, further comprising:

(c) after step (b), causing the first tag to transmit its identification number.

23. The method of claim 21, further comprising:

(c) after step (b), transmitting a command for execution by the first tag.

24. The method of claim 21, wherein the series of bits includes a number of bits predetermined to be sufficient to identify tags within a communication range of the reader, wherein step (1) comprises:

transmitting the predetermined number of bits to the population of tags.

25. A method in a radio frequency identification (RFID) system the includes at least one RFID reader that communicates with a population of RFID tags, wherein each RFID tag stores a corresponding identification number, comprising:

generating a key to identify an RFID tag of the population of RFID tags, wherein the key does not include bits identifying an item with which the RFID tag is associated;

operating a binary tree algorithm to at least identify the RFID tag in the population of RFIDs tags; and

receiving bits of the generated key from the RFID tag during the binary tree algorithm.

26. The method of claim 25, wherein said generating step includes the step of:

selecting a number from a sequence of numbers to use as the key.

27. The method of claim 25, wherein said generating step includes the step of:

using a randomly generated number as the key.

28. The method of claim 25, wherein said generating step includes the step of:

dynamically generating a number prior to each traversal of the population of RFID tags to use as the key.

29. A method for a radio frequency identification (RFID) reader to communicate with a population of RFID tags, wherein each tag stores a corresponding identification number, wherein the identification number includes a first bit pattern, comprising:

(a) transmitting a first at least one bit to the population of tags to cause tags to respond to a binary traversal operation with a second bit pattern;

(b) performing a binary traversal operation to singulate a first tag of the population of tags;

(c) transmitting a substantially constant signal to the population of tags; and

(d) receiving a plurality of bits of the first bit pattern from the first tag during transmission of the substantially constant signal.

30. The method of claim 29, further comprising:

(e) terminating transmission of the substantially constant signal to the population of tags to stop the first tag from transmitting further bits of the first bit pattern.

31. The method of claim 30, further comprising:

(f) transmitting a second substantially constant signal to the population of tags;

(g) receiving a second plurality of bits of the first bit pattern from the first tag during transmission of the second substantially constant signal; and

(h) terminating transmission of the second substantially constant signal to the population of tags to stop the first tag from transmitting further bits of the first bit pattern.

32. The method of claim 31, further comprising:

(i) repeating steps (f)-(h) for subsequent substantially constant signals.

33. A method in a radio frequency identification (RFID) system the includes at least one RFID reader that communicates with a population of RFID tags, wherein each RFID tag stores a corresponding identification number, comprising:

(a) generating a bit to identify an RFID tag of the population of RFID tags, wherein the bit does not include bits identifying an item with which the RFID tag is associated;

(b) operating a binary tree algorithm to at least identify the RFID tag in the population of RFIDs tags;

(c) receiving the generated bit from the RFID tag during the binary tree algorithm; and

(d) repeating steps (a)-(c) until the RFID tag is singulated.

34. A method for a radio frequency identification (RFID) reader to communicate with a population of RFID tags, wherein each tag stores a corresponding identification number, wherein the identification number includes a first bit pattern, comprising:

(a) transmitting a first at least one bit to the population of tags to cause tags to respond to a binary traversal operation with the first bit pattern;

(b) transmitting a substantially constant signal to the population of tags; and

(c) receiving a plurality of bits of the first bit pattern from a first tag during transmission of the substantially constant signal.

35. The method of claim 34, further comprising:

(d) terminating transmission of the substantially constant signal to the population of tags to stop the first tag from transmitting further bits of the first bit pattern.