Optimization of a binary tree traversal with secure communications
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
35 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (22, 23, 24)
-
-
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. - View Dependent Claims (26, 27, 28)
-
-
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. - View Dependent Claims (30, 31, 32)
-
-
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. - View Dependent Claims (35)
-
Specification