Method and apparatus to manage RFID tags
First Claim
1. A method of establishing wireless communications between an interrogator and wireless identification devices, the method comprising utilizing a tree search technique to establish communications without collision between the interrogator and individual ones of the multiple wireless identification devices, the method including using a binary search tree having multiple levels representing subgroups of the multiple wireless identification devices, the number of devices in a subgroup in one level being less than the number of devices in the next level, the tree search technique employing level skipping wherein every second level of the tree is skipped.
2 Assignments
0 Petitions
Accused Products
Abstract
A method of establishing wireless communications between an interrogator and individual ones of multiple wireless identification devices, the method comprising utilizing a tree search method to establish communications without collision between the interrogator and individual ones of the multiple wireless identification devices, a search tree being defined for the tree search method, the tree having multiple levels representing subgroups of the multiple wireless identification devices, the number of devices in a subgroup in one level being half of the number of devices in the next higher level, the tree search method employing level skipping wherein at least one level of the tree is skipped. A communications system comprising an interrogator, and a plurality of wireless identification devices configured to communicate with the interrogator in a wireless fashion, the respective wireless identification devices having a unique identification number, the interrogator being configured to employ a tree search technique to determine the unique identification numbers of the different wireless identification devices so as to be able to establish communications between the interrogator and individual ones of the multiple wireless identification devices without collision by multiple wireless identification devices attempting to respond to the interrogator at the same time, wherein levels of the tree are occasionally skipped. In one aspect, a method includes: transmitting by an interrogator a first wireless signal, specifying a first set of bit values, to request first replies from radio frequency identification (RFID) devices that have the first set of bit values; and responsive to a collision in the first replies, transmitting by the interrogator a second wireless signal, specifying a second set of bit values having at least two more bits than the first set, to request second replies from RFID devices that have the second set of bit values.
119 Citations
92 Claims
- 1. A method of establishing wireless communications between an interrogator and wireless identification devices, the method comprising utilizing a tree search technique to establish communications without collision between the interrogator and individual ones of the multiple wireless identification devices, the method including using a binary search tree having multiple levels representing subgroups of the multiple wireless identification devices, the number of devices in a subgroup in one level being less than the number of devices in the next level, the tree search technique employing level skipping wherein every second level of the tree is skipped.
-
6. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices, the method comprising:
-
establishing for respective devices unique identification numbers; causing the devices to select random values, wherein respective devices choose random values independently of random values selected by the other devices; transmitting a communication, from the interrogator, requesting devices having random values within a specified group of random values to respond; receiving the communication at multiple devices, devices receiving the communication respectively determining if the random value chosen by the device falls within the specified group and, if so, sending a reply to the interrogator; and determining using the interrogator if a collision occurred between devices that sent a reply and, if so, creating a new, smaller, specified group, using a search tree, that is one quarter of the first mentioned specified group, wherein at least one level of a search tree is skipped. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A method of addressing messages from a transponder to a selected one or more of a number of communications devices, the method comprising:
-
causing the devices to select random values, wherein respective devices choose random values independently of random values selected by the other devices; transmitting a communication, from the transponder, requesting devices having random values within a specified group of a plurality of possible groups of random values to respond, the specified group being less than or equal to the entire set of random values, the plurality of possible groups being organized in a binary tree having a plurality of levels, wherein groups of random values decrease in size with each level descended; devices receiving the communication respectively determining if the random value chosen by the device falls within the specified group and, if so, sending a reply to the transponder; and
, if not, not sending a reply; anddetermining using the transponder if a collision occurred between devices that sent a reply and, if so, creating a new, smaller, specified group by descending at least two levels in the tree. - View Dependent Claims (12, 13, 14, 15)
-
-
16. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices, the method comprising:
-
establishing for respective devices unique identification numbers; causing the devices to select random values, wherein respective devices choose random values independently of random values selected by the other devices; transmitting from the interrogator a command requesting devices having random values within a specified group of a plurality of possible groups of random values to respond, the specified group being less than or equal to the entire set of random values, the plurality of possible groups being organized in a binary tree having a plurality of levels, wherein groups of random values decrease in size with each level; receiving the command at multiple of the devices, the devices receiving the command respectively determining if the random value chosen by the device falls within the specified group and, only if so, sending a reply to the interrogator, wherein sending a reply to the interrogator comprises transmitting both the random value of the device sending the reply and the unique identification number of the device sending the reply; determining using the interrogator if a collision occurred between devices that sent a reply and, if so, creating a new, smaller, specified group using a level of the tree different from the level used in the interrogator transmitting, wherein at least one level of the tree is skipped, the interrogator transmitting a command requesting devices having random values within the new specified group of random values to respond; and if a reply without collision is received from a device, the interrogator subsequently sending a command individually addressed to that device. - View Dependent Claims (17, 18, 19, 20, 21)
-
-
22. A system comprising:
-
an interrogator; a number of communications devices capable of wireless communications with the interrogator; means for establishing for respective devices unique identification numbers respectively having the first predetermined number of bits; means for causing the devices to select random values, wherein respective devices choose random values independently of random values selected by the other devices; means for causing the interrogator to transmit a command requesting devices having random values within a specified group of random values to respond; means for causing devices receiving the command to determine if their chosen random values fall within the specified group and, if so, to send a reply to the interrogator; and means for causing the interrogator to determine if a collision occurred between devices that sent a reply and, if so, to create a new, smaller, specified group that is one quarter of the first mentioned specified group, wherein at least one level of the tree is skipped. - View Dependent Claims (23, 24, 25, 26)
-
-
27. A method for initiating wireless communication with radio frequency identification (RFID) devices, comprising:
-
transmitting a first command specifying a first bit sequence; receiving a first response to the first command from an RFID device having a first portion of a random number identifier generated by the RFID device equal to the first bit sequence, the first response including at least a second portion of the random number identifier generated by the RFID device; detecting a collision in the first response; responsive to detecting the collision, transmitting a second command following the first command in succession and absent any intervening commands, the second command specifying a second bit sequence that includes the first bit sequence and is at least two bits longer than the first bit sequence; and receiving a second response to the second command from the RFID device indicating that the random number identifier generated by the RFID device includes the second bit sequence. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34)
-
-
35. A radio frequency identification (RFID) system, comprising:
-
an RFID device to generate a random number identifier and to store an identification number, separate from the random number identifier, for use in identifying a person with whom the RFID device is associated; and an interrogator to transmit a command comprising a first bit string to cause the RFID device to transmit at least a portion of the random number generated by the RFID device if the RFID device determines that the random number includes the first bit string, and to transmit a successive command, comprising a second bit string, absent any intervening commands, to cause the RFID device to transmit a response if the RFID device determines that the random number includes the second bit string, wherein the second bit string includes the first bit string plus at least two additional bits. - View Dependent Claims (36, 37, 38, 39, 40, 41)
-
-
42. A wireless payment method, comprising:
-
transmitting by an interrogator a first wireless command, specifying a first set of bit values, to request one or more first replies from one or more radio frequency identification (RFID) devices that have randomly generated the first set of bit values; responsive to detecting a collision in the first replies, transmitting by the interrogator a second wireless command successively following the first wireless command, absent any intervening commands, and specifying a second set of bit values that include the first set of bit values and have at least two more bits than the first set, to request one or more second replies from one or more RFID devices that have randomly generated the second set of bit values; responsive to receiving a reply, without collision, from an RFID device of the one or more RFID devices, transmitting by the interrogator a third wireless command comprising an identifier randomly generated by the RFID device to select the RFID device, the identifier including the second set of bit values; and receiving by the interrogator an identification code, separate from the identifier, from the RFID device to identify a person to be charged for payment. - View Dependent Claims (43, 44, 45, 46, 47, 48, 49, 50, 51)
-
-
52. An initiating radio frequency identification (RFID) device, comprising:
-
a transmitter to send a first signal, including a first portion of a first set of random numbers, to request a first set of one or more target RFID devices that have generated the first portion to respond with one or more first random values, and to send a second signal, including a second portion of a second set of one or more random numbers, to request a second set of one or more target RFID devices that have generated the second portion to respond, wherein the first set of random numbers includes the second set of random numbers; an antenna to provide a radio frequency (RF) field to be modulated by the first and second sets of one or more target RFID devices to respond to the first and second signals; a receiver to receive responses to the first and second signals; and processing circuitry to detect a collision in the responses, wherein the second signal is to be sent successively after the first signal in response to a collision detected by the processing circuitry after the first signal is sent, and the second set of one or more random numbers is less than half of the first set of random numbers. - View Dependent Claims (53, 54, 55, 56)
-
-
57. A target radio frequency identification (RFID) device, comprising:
-
memory storing information for use in determining an identity of a person with whom the RFID device is associated; a receiver to receive, in succession, a first wireless command from an initiating RFID device and a second wireless command from the initiating RFID device, absent reception of any intervening wireless commands from the initiating RFID device, the first wireless command to provide a first set of bits and the second wireless command to provide a second set of bits, wherein the second set of bits includes the first set of bits and is longer than the first set of bits by at least two bits; a random number generator to generate a random number identifier of the RFID device; processing circuitry to compare the first set of bits with a first portion of the random number identifier to determine if they are equal, and to compare the second set of bits with a second portion of the random number identifier to determine if they are equal; and a transmitter to transmit at least a third portion of the random number identifier in response to the first wireless command, before the second wireless command is received, if the first set of bits are determined to be equal to the first portion of the random number identifier, to transmit a response to the second wireless command if the second set of bits are determined to be equal to the second portion of the random number identifier, and to transmit the information. - View Dependent Claims (58, 59, 60, 61, 62, 63, 64)
-
-
65. A wireless payment method, comprising:
-
transmitting a first command specifying a first bit sequence; receiving a first response to the first command from an RFID device having a first portion of a unique number identifier equal to the first bit sequence, the first response including at least a second portion of the unique number identifier; detecting that a collision has occurred with respect to the first response; responsive to detecting that the collision has occurred, transmitting a second command following the first command in succession and absent any intervening commands, the second command specifying a second bit sequence that includes the first bit sequence and is at least two bits longer than the first bit sequence; receiving a second response to the second command from the RFID device indicating that the unique number identifier includes the second bit sequence; determining an owner of the RFID device based at least in part on said unique number identifier of said RFID device; and causing debiting of an account held by said owner. - View Dependent Claims (66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78)
-
-
79. A wireless payment method, comprising:
-
transmitting by an interrogator a first wireless command, specifying a first set of bit values to request one or more first replies from one or more radio frequency identification (RFID) devices that have a respective unique identifier containing a portion equal to the first set of bit values; responsive to detecting a collision in the first replies, transmitting by the interrogator a second wireless command successively following the first wireless command, absent any intervening commands, and specifying a second set of bit values that include the first set of bit values and have at least two more bits than the first set of bit values, to request one or more second replies from one or more RFID devices that have a respective unique identifier containing a portion equal to the second set of bit values; responsive to receiving a reply, without collision, from an RFID device of the one or more RFID devices, transmitting by the interrogator a third wireless command comprising a unique identifier of the RFID device to select the RFID device, the unique identifier of the RFID device including the second set of bit values; and receiving funds for the remote payment of goods or services based at least on part on the reply and the unique identifier of the RFID device. - View Dependent Claims (80, 81)
-
-
82. A wireless payment method, comprising:
-
transmitting by an interrogator a first wireless command, specifying a first set of bit values to request one or more first replies from one or more radio frequency identification (RFID) devices that have a respective unique identifier containing a portion equal to the first set of bit values; responsive to detecting a collision in the first replies, transmitting by the interrogator a second wireless command successively following the first wireless command, absent any intervening commands, and specifying a second set of bit values that include the first set of bit values and have at least two more bits than the first set of bit values, to request one or more second replies from one or more RFID devices that have a respective unique identifier containing a portion equal to the second set of bit values; responsive to receiving a reply, without collision, from an RFID device of the one or more RFID devices, transmitting by the interrogator a third wireless command comprising a unique identifier of the RFID device to select the RFID device, the identifier including the second set of bit values; identifying an account to be charged for payment based at least in part on the reply and the unique identifier of the RFID device; and debiting funds of the identified account associated with the RFID device. - View Dependent Claims (83, 84)
-
-
85. A wireless payment method, comprising:
-
transmitting a first command specifying a first bit sequence; receiving a first response to the first command from an RFID device having a first portion of a unique identifier equal to the first bit sequence, the first response including at least a second portion of the unique identifier; detecting that a collision has occurred with respect to the first response; responsive to detecting that the collision has occurred, transmitting a second command following the first command in succession and absent any intervening commands, the second command specifying a second bit sequence that includes the first bit sequence and is at least two bits longer than the first bit sequence; receiving a response to the second command from the RFID device indicating that the unique identifier includes the second bit sequence; and receiving funds for the remote payment of goods or services based at least in part on the response to the second command received from the RFID device. - View Dependent Claims (86, 87, 88)
-
-
89. A wireless payment method, comprising:
-
transmitting a first command specifying a first bit sequence; receiving a first response to the first command from an RFID device having a first portion of a unique identifier equal to the first bit sequence, the first response including at least a second portion of the unique identifier; detecting that a collision has occurred with respect to the first response; responsive to detecting that the collision has occurred, transmitting a second command following the first command in succession and absent any intervening commands, the second command specifying a second bit sequence that includes the first bit sequence and is at least two bits longer than the first bit sequence; receiving a response to the second command from the RFID device indicating that the unique identifier includes the second bit sequence; determining an account of the RFID device based at least in part on the response to the second command received from the RFID device; and causing the debiting of funds associated with the determined account. - View Dependent Claims (90, 91, 92)
-
Specification