Method of addressing messages, method of establishing wireless communications 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 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.
0 Assignments
0 Petitions
Accused Products
Abstract
A method of and apparatus for 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, the method comprises transmitting a first command to select a group of RFID devices based at least in part on a first memory range beginning at a first bit location. The method further comprises transmitting a second command, successively following the first command, to select a subgroup of the group of RFID devices based at least in part on a second memory range beginning at a second bit location. The second bit location is shifted by two or more bits from the first bit location and receives a reply from at least one RFID device of the subgroup of RFID devices. The reply includes an identifier to uniquely identify the RFID device.
126 Citations
44 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, 33)
-
-
27. An interrogator that, when operated, performs a method comprising:
-
transmitting a first command to select a group of RFID devices based, at least in part, on a first memory range beginning at a first bit location; transmitting a second command, successively following the first command, to select a subgroup of the group of RFID devices based, at least in part, on a second memory range beginning at a second bit location, wherein the second bit location is shifted by two or more bits from the first bit location; and receiving a reply from at least one RFID device of the subgroup of RFID devices, the reply including an identifier to uniquely identify the RFID device. - View Dependent Claims (28, 29, 30, 31, 32)
-
-
34. A method, comprising:
-
providing an RFID device storing an identification number to identify a person; sending a first command from an interrogator, the first command configured to select a group of RFID devices based, at least in part, on a respective first value stored in each respective RFID device of the group of RFID devices, the respective first value bounded at a respective first bit location within a memory of the respective RFID device; sending a second command from the interrogator after sending the first command and before sending any intervening command from the interrogator, the second command configured to select a subgroup of the group of RFID devices based, at least in part, on a respective second value stored in the respective RFID device of the group of RFID devices, the respective second value bounded at a respective second bit location within the memory of the respective RFID device, wherein the second bit location is at least two bits away from the first bit location; and receiving a unique identifier of the RFID device from the RFID device, the RFID device belonging to the subgroup, the unique identifier being separate from the identification number. - View Dependent Claims (35, 36, 37, 38, 39, 40)
-
-
41. A system comprising:
-
an RFID reader configured to send a first command to indicate a first bit string and a first range of bits, followed, without any intervening query commands, by a second command to indicate a second bit string and a second range of bits, wherein the first range of bits differs from the second range of bits by at least two bits; an RFID device storing an identification code, the RFID device configured to compare the first bit string to a first value stored in memory corresponding to the first range of bits, to compare the second bit string to a second value stored in memory corresponding to the second range of bits, to provide an identifier to uniquely identify the RFID device, and to provide the identification code. - View Dependent Claims (42, 43, 44)
-
Specification