Method of addressing messages, method of establishing wireless communications, and communications system

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.

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;
• 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 at least two levels in the tree.

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.

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.

A method for performing radio frequency communications, the method comprising:

• determining by an interrogator a group of a plurality of groups from a range of possible random numbers;
• transmitting by the interrogator a first request for a response from each of one or more radio frequency identification (RFID) devices that has generated a random number included in the group;
• receiving by the one or more RFID devices the first request;
• communicating by each of one or more responding RFID devices a response, wherein each of the one or more responding RFID devices has generated a random number within the group;
• receiving by the interrogator one or more responses from the one or more responding RFID devices;
• and
• determining by the interrogator if there is a collision between the one or more responses, and if such a collision is determined to occur, then determining by the interrogator a subgroup of a plurality of subgroups of possible random numbers within the group and transmitting by the interrogator a second request for response from each of one or more RFID devices that has generated a random number included in the subgroup, wherein, in a hierarchy of the group and the plurality of subgroups having multiple levels, the subgroup is more than one level lower than the group.

A system for performing radio frequency communications, the system comprising:

• a radio frequency identification (RFID) device comprising a random number generator to generate a random value;
• one or more antennas positioned in a first region;
• and
• an interrogator communicatively coupled to the one or more antennas, the interrogator to repeatedly select a subgroup of numbers from a plurality of possible subgroups of numbers from a group of numbers and to transmit a first request for responses from one or more RFID devices;
• storing a number in the selected subgroup until the interrogator receives one or more responses from one or more RFID devices without a collision, wherein the group and the plurality of subgroups correspond to a plurality of levels, with each subgroup containing a fewer number of numbers than the group, and at least one level is skipped at least during one of repeated subgroup selections.

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 to implement a sequence comprising a loop to repeatedly determine a subgroup for a first request such that the subgroup includes a subset of possible numbers of a previous subgroup and to repeatedly cause the transmitter to transmit the first request until the control unit receives a response without a collision occurring between a plurality of responding RFID devices, the first request including an indication of the subgroup, wherein in accordance with the sequence, in at least one of repeated subgroup determinations, the determined subgroup includes less than half of possible numbers of the successively previous subgroup.

A method of operating a target radio frequency identification (RFID) device to operate in accordance with a process that enables the target device to be individually selected for further communication, the method comprising:

• causing one or more RFID devices including the target RFID device to communicate a respective identifier, and if a collision occurs, performing operations comprising:
• defining a first subgroup of a plurality of subgroups of possible identifiers;
• transmitting a first request to RFID devices for each of RFID devices having a respective identifier within the first subgroup to respond;
• receiving one or more responses, and if a collision occurs, repeatedly redefining the first subgroup to include fewer possible identifiers, and retransmitting the first request for each of RFID devices having a respective identifier within the redefined first subgroup to respond until a response is received without a collision, wherein one or more levels in a hierarchical structure of subgroups is skipped between at least one of the first subgroups and the redefined first subgroup that follows the at least one first subgroup in succession.

A method of operating a target radio frequency identification (RFID) device to operate in accordance with a process that enables the target device to be individually selected for further communication, the method comprising:

• causing one or more RFID devices including the target RFID device to communicate a respective identifier, and if a collision occurs, performing operations comprising:
• defining a first subgroup of a plurality of subgroups of possible identifiers;
• transmitting a first request to RFID devices for each of RFID devices having a respective identifier within the first subgroup to respond;
• and
• receiving one or more responses, and if a collision occurs, repeatedly redefining the first subgroup to include fewer possible identifiers, and retransmitting the first request for each of RFID devices having a respective identifier within the redefined first subgroup to respond until a response is received without a collision, wherein one or more levels in a hierarchical structure of subgroups is skipped between at least one of the first subgroups and the redefined first subgroup that follows the at least one first subgroup in succession;
• determining an owner of the target RFID device based at least in part on said respective identifier of said target RFID device;
• and
• debiting an account held by said owner.

A method for performing radio frequency communications in a system comprised of one or more radio frequency identification (RFID) devices, one or more antennas positioned in a first region and an interrogator communicatively coupled to the one or more antennas, the method comprising:

• repeatedly selecting a subgroup of numbers from a plurality of possible subgroups of numbers from a group of numbers;
• transmitting a first request from the interrogator for responses from the one or more RFID devices;
• storing a number in the selected subgroup until the interrogator receives one or more responses from a target RFID device without a collision, wherein the group and the plurality of subgroups correspond to a plurality of levels, with each subgroup containing a fewer number of numbers than the group, and at least one level is skipped at least during one of repeated subgroup selections;
• determining an owner of the target RFID device based at least in part on the one or more responses from the target RFID device;
• and
• debiting an account held by the owner.

A method of conducting a financial transaction, the method enabling a target radio frequency device to be individually selected for further communication, the method comprising:

• causing one or more radio frequency devices including the target radio frequency device to communicate a respective identifier, and performing operations comprising:
• defining a first subgroup of a plurality of subgroups of possible identifiers;
• transmitting a first request to radio frequency devices for each of radio frequency devices having a respective identifier within the first subgroup to respond;
• and
• receiving one or more responses, and if a collision occurs, repeatedly redefining the first subgroup to include fewer possible identifiers, and
• retransmitting the first request for each of radio frequency devices having a respective identifier within the redefined first subgroup to respond until a response is received without a collision, wherein one or more levels in a hierarchical structure of subgroups is skipped between at least one of the first subgroups and the redefined first subgroup that follows the at least one first subgroup in succession;
• and
• debiting a financial account associated with the target radio frequency device based at least in part on said respective identifier of said target radio frequency device.

A method for performing radio frequency communications in a system comprised of one or more radio frequency devices, one or more antennas positioned in a first region, and an interrogator communicatively coupled to the one or more antennas, the method comprising:

• repeatedly selecting a subgroup of numbers from a plurality of possible subgroups of numbers from a group of numbers;
• transmitting a first request from the interrogator for responses from the one or more radio frequency devices;
• storing a number in the selected subgroup until the interrogator receives one or more responses from a target radio frequency device without a collision, wherein the group and the plurality of subgroups correspond to a plurality of levels, with each subgroup containing a fewer number of numbers than the group, and at least one level is skipped at least during one of repeated subgroup selections;
• and
• debiting a financial account associated with the target radio frequency device based at least in part on the one or more responses from the target radio frequency device.