Method of Addressing Messages and Communications System
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 search tree having multiple nodes respectively representing subgroups of the multiple wireless identification devices, the method further comprising, for a node, transmitting a command, using the interrogator, requesting that devices within the subgroup represented by the node respond, determining with the interrogator if a collision occurred in response to the command and, if not, repeating the command at the same node.
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 attempt to identify individual ones of the multiple wireless identification devices so as to be able to perform 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 nodes respectively representing subgroups of the multiple wireless identification devices, wherein the interrogator transmits a command at a node, requesting that devices within the subgroup represented by the node respond, wherein the interrogator determines if a collision occurs in response to the command and, if not, repeats the command at the same node. An interrogator configured to transmit a command at a node, requesting that devices within the subgroup represented by the node respond, the interrogator further being configured to determine if a collision occurs in response to the command and, if not, to repeat the command at the same node includes: transmitting by an interrogator a first signal including a first set of bits, the interrogator to identify a first subgroup of a group of possible random numbers; communicating by each of one or more RFID devices a first response if the one or more RFID devices has generated a random number that is included in the first subgroup; receiving by the interrogator one or more received responses from respective ones of the one or more RFID devices; and responsive to receiving one of the one or more received responses without a collision, retransmitting by the interrogator at least the first signal.
144 Citations
171 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 search tree having multiple nodes respectively representing subgroups of the multiple wireless identification devices, the method further comprising, for a node, transmitting a command, using the interrogator, requesting that devices within the subgroup represented by the node respond, determining with the interrogator if a collision occurred in response to the command and, if not, repeating the command at the same node.
-
7. 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 first 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 first 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 second specified group smaller than the first specified group; and
, if not, again transmitting a communication requesting devices having random values within the first specified group of random values to respond. - View Dependent Claims (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:
-
establishing unique identification numbers for respective devices;
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 plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels, the specified group being defined as being at one of the nodes;
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 transponder; and
, if not, not sending a reply; and
determining using the transponder if a collision occurred between devices that sent a reply and, if so, creating a new, smaller, specified group by descending in the tree; and
, if not, transmitting a communication at the same node. - View Dependent Claims (12, 13)
-
-
14. 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 a command using the interrogator requesting devices having random values within a specified group of a plurality of possible groups of random values to respond, the specified group being equal to or less than the entire set of random values, the plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels;
receiving the command at multiple RFID devices, RFID devices receiving the command respectively determining if their chosen random values fall within the specified group and, only if so, sending a reply to the interrogator, wherein sending a reply to the interrogator comprises transmitting 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 different level of the tree, the interrogator transmitting a command requesting devices having random values within the new specified group of random values to respond; and
, if not, the interrogator re-transmitting a command requesting devices having random values within the first mentioned 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 (15, 16, 17, 18, 19, 20)
-
- 21. A communications system comprising an interrogator, and a plurality of wireless identification devices configured to communicate with the interrogator using RF, the interrogator being configured to employ tree searching to attempt to identify individual ones of the multiple wireless identification devices, so as to be able to perform communications without collision between the interrogator and individual ones of the multiple wireless identification devices, the interrogator being configured to follow a search tree, the tree having multiple nodes respectively representing subgroups of the multiple wireless identification devices, the interrogator being configured to transmit a command at a node, requesting that devices within the subgroup represented by the node respond, the interrogator further being configured to determine if a collision occurs in response to the command and, if not, to repeat the command at the same node.
-
27. 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; and
, if not, transmit a command requesting devices having random values within the same specified group of random values to respond. - View Dependent Claims (28, 29, 30)
-
-
31. A system comprising:
-
an interrogator configured to communicate to a selected one or more of a number of communications devices; and
a plurality of communications devices;
the devices being configured to select random values, wherein respective devices choose random values independently of random values selected by the other devices;
the interrogator being configured to transmit 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 the entire set of random values, the plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels, the specified group being defined as being at one of the nodes;
devices receiving the command being configured to respectively determine if their chosen random values fall within the specified group and, only if so, send a reply to the interrogator, wherein sending a reply to the interrogator comprises transmitting the unique identification number of the device sending the reply;
the interrogator being configured to determine if a collision occurred between devices that sent a reply and, if so, create a new, smaller, specified group using a different level of the tree, the interrogator being configured to transmit a command requesting devices having random values within the new specified group of random values to respond; and
, if not, the interrogator being configured to re-transmit a command requesting devices having random values within the first mentioned specified group of random values to respond. - View Dependent Claims (32, 33, 34)
-
-
35. A system comprising:
-
an interrogator configured to communicate to a selected one or more of a number of RFID devices;
a plurality of RFID devices, respective devices being configured to store a unique identification number, respective devices being further configured to store a random value;
the interrogator being configured to transmit a command requesting devices having random values within a specified group of a plurality of possible groups of random values to respond, the plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels, the specified group being defined as being at one of the nodes;
devices receiving the command respectively being configured to determine if their chosen random values fall within the specified group and, if so, send a reply to the interrogator; and
, if not, not send a reply; and
the interrogator being configured to determine if a collision occurred between devices that sent a reply and, if so, to create a new, smaller, specified group by descending in the tree; and
, if not, to transmit a command at the same node. - View Dependent Claims (36, 37, 38)
-
-
39. A method for performing radio frequency communications, the method comprising:
-
transmitting by an interrogator a first signal, the first signal including a first set of bits to identify a first subgroup of a group of possible random numbers;
receiving by one or more RFID devices the first signal;
communicating by each of the one or more RFID devices a first response if the one or more RFID devices has generated a random number that is included in the first subgroup;
receiving by the interrogator one or more received responses, the one or more received responses being received from respective ones of the one or more RFID devices; and
responsive to receiving one of the one or more received responses without a collision, retransmitting by the interrogator at least the first signal. - View Dependent Claims (40, 41, 42, 43, 44, 45, 46, 47, 48, 49)
-
-
50. A system for performing radio frequency communications, the system comprising:
-
a first radio frequency identification (RFID) device configured to generate a random number and to communicate a response, including at least a portion of the random number, upon receiving a request that includes an indication of a subset of possible random numbers if the first RFID device determines that the subset includes the random number generated by the first RFID device;
an antenna positioned in a first region; and
an interrogator coupled to the antenna, the interrogator configured to transmit a signal comprising a portion of an identifier and to receive a reply to the signal from a target RFID device that has generated a random number having a portion equal to the portion of the identifier, the interrogator further configured to re-transmit the signal, including at least the portion of the identifier, if the reply is received without a collision. - View Dependent Claims (51, 52, 53, 54, 55, 56, 57)
-
-
58. An interrogator comprising:
-
one or more antennas;
a receiver communicatively coupled to at least one of the one or more antennas to receive one or more messages from one or more radio frequency identification (RFID) devices;
a transmitter communicatively coupled to at least one of the one or more antennas to transmit one or more messages; and
a control unit communicatively coupled to the transmitter and the receiver, the control unit configured to implement an algorithm to detect at least a single RFID device in a field of the interrogator, including re-transmitting a first signal responsive to receipt of a first response from the one or more RFID devices without a collision, the first signal including a first set of bits of at least a first portion of possible random numbers that may be generated by the one or more RFID devices, and the first response including at least a second portion of a random number generated by the one or more RFID devices. - View Dependent Claims (59, 60, 61, 62, 63, 64)
-
-
65. A method comprising:
providing an interrogator to generate an RF field and to initiate the implementation of an algorithm to detect at least a single target RFID device out of potentially multiple target RFID devices in the RF field, the algorithm including;
defining a first subgroup of possible random numbers that may be generated by the target device, the first subgroup being defined by a first set of bits common to the first subgroup;
transmitting a signal comprising at least the first set of bits to identify the first subgroup of possible random numbers and requesting the target device to respond if the target device has generated a random number included in the subgroup;
receiving a response from the target device if the target device has generated the random number included in the subgroup;
if no collision is detected in the receiving of the response from the target device, determining, from the response, the random number generated by the target device and retransmitting the signal; and
if a collision is detected in the receiving of the response from the target device, defining a second subgroup of possible random numbers that may be generated by the target device, the second subgroup being a subset of the first subgroup and being defined by a second set of bits common to the second subgroup, and retransmitting the signal. - View Dependent Claims (66, 67, 68, 69, 70, 71)
-
72. A method, comprising:
-
receiving a first signal from an interrogator in accordance with an algorithm to identify a radio frequency identification (RFID) device in a field of the interrogator, the first signal comprising a first set of bits and requesting a response from one or more RFID devices in the field selected in accordance with at least the first set of bits;
responsive to receiving the first signal, determining if the first set of bits is equal to a first portion of a random number generated by the RFID device, and, if so, modulating an RF field, provided by the interrogator, to communicate a reply to the interrogator in accordance with the algorithm; and
receiving, in accordance with the algorithm, a retransmission of the first signal from the interrogator in response to the interrogator receiving the reply without detecting a collision. - View Dependent Claims (73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84)
-
-
85. A system, comprising:
-
a radio frequency identification (RFID) device comprising a receiver to receive a first command including a portion of an identification number, a random number generator to generate a random number to identify the device, and a transmitter to communicate a reply to the first command if the portion of the identification number is equal to a first portion of the random number; and
an interrogator configured to implement an algorithm to identify one or more RFID devices in a field of the interrogator, the algorithm comprising transmitting a first signal with a first set of bits to request a response from a selected one or more devices, receiving a first response thereto from the selected one or more devices, detecting if a collision occurred in the first response, and retransmitting the first signal with at least the first set of bits to request a second response from at least one of the selected one or more devices in response to detecting no collision in the first response. - View Dependent Claims (86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103)
-
-
104. An apparatus for wirelessly reading radio frequency identification (RFID) devices, comprising:
-
a transmitter to transmit a command along with a first portion of a set of random numbers to request a response from at least one RFID device that has generated a random number in the set;
an antenna to provide an RF field to be modulated by the device;
a receiver to receive the response; and
processing circuitry to perform collision detection, to determine the random number using the response, and to cause the transmitter to retransmit the command along with at least the first portion of the set of random numbers responsive to detecting no collision in the response. - View Dependent Claims (105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121)
-
-
122. A radio frequency identification (RFID) reader, comprising:
-
a transmitter to transmit at least a first portion of an identifier along with an indication of a first number of bits in the first portion, and to request a first response from an RFID device that has generated a first portion of a random number equal to the first portion of the identifier;
a receiver to receive the first response from the device; and
a processing circuit coupled to the transmitter and receiver to implement an algorithm to detect at least one from among potentially multiple RFID devices, wherein in accordance with the algorithm the processing circuit is to perform collision detection on the first response and, in response to detecting no collision, to retransmit, via the transmitter, the at least first portion of the identifier and to request a second response thereto. - View Dependent Claims (123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135)
-
-
136. A system, comprising:
-
an RFID target device to receive a portion of an identifier, to compare the portion of the identifier to a portion of a random value generated by the target device, and to communicate a reply value if the portion of the identifier is equal to the portion of the random value; and
an RFID initiating device to initiate communication with one or more RFID target devices, the initiating device to transmit a first request including a first command and first information, to receive a first response to the first request from each of one or more RFID target devices that has generated a respective random number that is included in a first subgroup of one or more of a group of possible random numbers indicated by the first information, to perform collision detection on the first response, and to transmit a second request including a retransmission of at least the first command and the first information responsive to detecting no collision. - View Dependent Claims (137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156)
-
-
157. A radio frequency identification (RFID) device, comprising:
-
a random number generator to generate a first random number identifier;
a receiver coupled to an antenna to receive a transmission of a first set of bits from a reader in accordance with an algorithm to enable the reader to determine the first identifier;
processing circuitry to compare the first set of bits to a first portion of the first identifier; and
a modulating circuit to modulate an RF field produced by the reader to communicate a second set of bits to the reader if the first set of bits is equal to the first portion of the first identifier, wherein the first identifier comprises the second set of bits, and wherein in accordance with the algorithm the receiver is to further receive a retransmission of at least the first set of bits from the reader if the reader receives the second set of bits without collision. - View Dependent Claims (158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171)
-
Specification