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

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.

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. A method in accordance with  claim 1  wherein the wireless identification device comprises an integrated circuit including a receiver, a modulator, and a microprocessor in communication with the receiver and modulator. 
     
     
       3. A method in accordance with  claim 1  wherein when a subgroup contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, the device that is not within communications range of the interrogator does not respond to the command. 
     
     
       4. A method in accordance with  claim 1  wherein when a subgroup contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, the device that is within communications range of the interrogator responds to the command. 
     
     
       5. A method in accordance with  claim 1  wherein a device in a subgroup changes between being within communications range of the interrogator and not being within communications range, over time. 
     
     
       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.   
     
     
       7. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with  claim 6  wherein sending a reply to the interrogator comprises transmitting the unique identification number of the device sending the reply. 
     
     
       8. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with  claim 6  wherein sending a reply to the interrogator comprises transmitting the random value of the device sending the reply. 
     
     
       9. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with  claim 6  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. 
     
     
       10. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with  claim 6  wherein, after receiving a reply without collision from a device, the interrogator sends a command individually addressed to that device. 
     
     
       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; 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.   
     
     
       12. A method of addressing messages from a transponder to a selected one or more of a number of communications devices in accordance with  claim 11  and further comprising establishing unique identification numbers for respective devices. 
     
     
       13. A method of addressing messages from a transponder to a selected one or more of a number of communications devices in accordance with  claim 12  and further including establishing a predetermined number of bits to be used for the random values. 
     
     
       14. A method of addressing messages from a transponder to a selected one or more of a number of communications devices in accordance with  claim 13  wherein the predetermined number of bits to be used for the random values comprises sixteen bits. 
     
     
       15. A method of addressing messages from a transponder to a selected one or more of a number of communications devices in accordance with  claim 13  wherein devices sending a reply to the transponder do so within a randomly selected time slot of a number of slots. 
     
     
       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.   
     
     
       17. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with  claim 16  wherein every second level is skipped. 
     
     
       18. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with  claim 16  wherein the unique identification numbers are respectively defined by a predetermined number of bits. 
     
     
       19. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with  claim 16  wherein the unique identification numbers are respectively defined by a predetermined number of bits and wherein the random values are respectively defined by a predetermined number of bits. 
     
     
       20. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with  claim 16  and further comprising, after the interrogator transmits a command requesting devices having random values within the new specified group of random values to respond:
 devices receiving the command respectively determining if their chosen random values fall within the new smaller specified group and, if so, sending a reply to the interrogator. 
 
     
     
       21. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with  claim 20  and further comprising, after the interrogator transmits a command requesting devices having random values within the new specified group of random values to respond:
 determining if a collision occurred between devices that sent a reply and, if so, creating a new specified group and repeating the transmitting of the command requesting devices having random values within a specified group of random values to respond using different specified groups until all of the devices within communications range are identified. 
 
     
     
       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.   
     
     
       23. A system in accordance with  claim 22  wherein sending a reply to the interrogator comprises transmitting the unique identification number of the device sending the reply. 
     
     
       24. A system in accordance with  claim 22  wherein sending a reply to the interrogator comprises transmitting the random value of the device sending the reply. 
     
     
       25. A system in accordance with  claim 22  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. 
     
     
       26. A system in accordance with  claim 22  wherein the interrogator further includes means for, after receiving a reply without collision from a device, sending a command individually addressed to that device. 
     
     
       27. 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.   
     
     
       28. The method of claim 27, wherein the first request includes a selection indicator, the selection indicator selecting each of one or more RFID devices that has generated a random number included in the group for communication. 
     
     
       29. The method of claim 27, further comprising transmitting by the interrogator a wake-up signal, the wake-up signal causing the one or more RFID devices to transition from a non-responsive state to a responsive state. 
     
     
       30. The method of claim 27, wherein the hierarchy forms a binary tree and each of the multiple levels corresponds to a number of valid bits common to corresponding subgroups. 
     
     
       31. The method of claim 27, wherein the communicating by the one or more responding RFID devices comprises the one or more responding RFID devices communicating a value randomly generated by each of the one or more responding RFID devices. 
     
     
       32. The method of claim 27, further comprising transmitting by the interrogator a second request indicating a number of slots from which each of the one or more responding RFID devices is to randomly select a slot in which to respond with a randomly generated multi-bit identifier. 
     
     
       33. The method of claim 32, wherein the second request comprises a multi-bit value to select the at least one RFID device for response to the second request. 
     
     
       34. The method of claim 33, further comprising determining by the interrogator at least one identification number stored in at least one of the one or more responding RFID devices, the at least one identification number to identify a person. 
     
     
       35. The method of claim 32, further comprising determining by the interrogator at least one identification number stored in at least one of the one or more responding RFID devices, the at least one identification number to identify a person. 
     
     
       36. The method of claim 27, further comprising determining by the interrogator at least one identification number stored in at least one of the one or more responding RFID devices, the at least one identification number to identify a person associated with the at least one of the one or more RFID responding devices. 
     
     
       37. 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.   
     
     
       38. The system of claim 37, wherein the first request includes a selection indicator, the selection indicator identifying one or more RFID devices storing a number in the selected subgroup for communication. 
     
     
       39. The system of claim 37, wherein the interrogator is further configured to transmit a wake-up signal, and one or more RFID devices are further configured to transition out of a sleep state upon receipt of the wake-up signal, wherein the sleep state is a non-responsive state. 
     
     
       40. The system of claim 37, wherein the plurality of levels correspond to a binary tree with each of the plurality of levels corresponding to a number of valid bits common to associated subgroups. 
     
     
       41. The system of claim 37, wherein the RFID device is one of the one or more RFID devices from which the interrogator receives the one or more responses. 
     
     
       42. The system of claim 37, wherein the interrogator is to transmit a second request indicating a number of slots from which at least one RFID device is to randomly select a slot in which to respond with an identifier. 
     
     
       43. The system of claim 42, wherein the second request comprises a plurality of bits to select the at least one RFID device corresponding to the bits. 
     
     
       44. The system of claim 43, wherein the RFID device stores an identification number to identify a person with whom the RFID device is associated. 
     
     
       45. The system of claim 42, wherein the number stored in the one or more RFID devices is a random number generated by the one or more RFID devices, and the identifier is randomly generated by the at least one RFID device. 
     
     
       46. The system of claim 42, wherein the RFID device stores an identification number to identify a person with whom the RFID device is associated. 
     
     
       47. The system of claim 37, wherein the RFID device stores an identification number to identify a person with whom the RFID device is associated. 
     
     
       48. 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.   
     
     
       49. The interrogator of claim 48, wherein the control unit is further configured to utilize a binary search tree to determine the subgroup. 
     
     
       50. The interrogator of claim 49, wherein the control unit is further configured to skip one or more intermediate levels in the binary search tree. 
     
     
       51. The interrogator of claim 48, wherein the response includes a random number generated by a responding RFID tag. 
     
     
       52. The interrogator of claim 48, wherein the transmitter is to transmit a second request to indicate a number of slots from which at least one RFID device is to randomly select a slot in which to respond with an identifier. 
     
     
       53. The interrogator of claim 52, wherein the second request is to comprise a plurality of bits to select the at least one RFID device, corresponding to the bits, to respond. 
     
     
       54. The interrogator of claim 53, wherein the receiver is to receive an identification number from the at least one RFID device to identify a person. 
     
     
       55. The interrogator of claim 53, wherein the subgroup includes a subset of possible random numbers generated by the one or more RFID devices, the response includes a number randomly generated by a responding RFID device of the one or more RFID devices, and the identifier is randomly generated by the at least one RFID device. 
     
     
       56. The interrogator of claim 52, wherein the subgroup includes a subset of possible random numbers generated by the one or more RFID devices, the response includes a number randomly generated by a responding RFID device of the one or more RFID devices, and the identifier is randomly generated by the at least one RFID device. 
     
     
       57. The interrogator of claim 56, wherein the receiver is to receive an identification number from the one or more RFID devices to identify a person. 
     
     
       58. The interrogator of claim 48, wherein the receiver is to receive an identification number from the one or more RFID devices to identify a person. 
     
     
       59. 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. 
   
     
     
       60. The method of claim 59, wherein the request includes a selection indicator, the selection indicator identifying one or more RFID devices from which a response is being requested. 
     
     
       61. The method of claim 59, wherein the target device is to transition from a non-responsive state to a responsive state in response to a wake-up signal. 
     
     
       62. The method of claim 59, wherein the defining and the redefining are performed at least in part in accordance with a binary search tree. 
     
     
       63. The method of claim 59, wherein the one or more responses include one or more respective random numbers generated by one or more respective RFID devices. 
     
     
       64. The method of claim 59, wherein the operations further comprise transmitting a second request indicating a number of slots, and at least one RFID device responding in a randomly selected slot of the number of slots indicated by the second request. 
     
     
       65. The method of claim 64, wherein in accordance with the process the second request comprises a multi-bit value that selects the at least one RFID device for response to the second request. 
     
     
       66. The method of claim 65, further comprising an identification number stored in a memory region of the target RFID device, the identification number corresponding to a person associated with the target RFID device. 
     
     
       67. The method of claim 64, wherein the identifiers are randomly generated by the one or more RFID devices, and the receiving the one or more responses comprises receiving one or more randomly generated numbers. 
     
     
       68. The method of claim 64, further comprising an identification number stored in a memory region of the target RFID device, the identification number corresponding to a person associated with the target RFID device. 
     
     
       69. The method of claim 59, further comprising an identification number stored in a memory region of the target RFID device, the identification number corresponding to a person associated with the target RFID device. 
     
     
       70. 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.   
     
     
       71. The method of claim 70, wherein the debiting of the account held by the owner is associated with the payment of a toll. 
     
     
       72. The method of claim 71, wherein a master wireless device is disposed within a toll booth, and said method further comprises operating said master wireless device disposed within said toll both at least when said target RFID device communicating the respective identifier is in proximity thereto. 
     
     
       73. The method of claim 71, wherein the debiting of the account comprises receiving a credit card number against which the toll can be charged. 
     
     
       74. The method of claim 70, wherein the debiting of the account comprises receiving a credit card number which can be charged. 
     
     
       75. The method of claim 70, wherein the debiting of the account held by the owner is for payment for goods or services. 
     
     
       76. 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.   
     
     
       77. The method of claim 76, wherein the debiting of the account held by the owner is associated with the payment of a toll. 
     
     
       78. The method of claim 77, wherein the interrogator is disposed within a toll both, and said method further comprises operating the interrogator disposed within said toll both at least when said target RFID device communicating is in proximity thereto. 
     
     
       79. The method of claim 77, wherein the debiting of the account comprises receiving a credit card number against which the toll can be charged. 
     
     
       80. The method of claim 76, wherein the debiting of the account comprises receiving a credit card number which can be charged. 
     
     
       81. The method of claim 76, wherein the debiting of the account held by the owner is for payment for goods or services. 
     
     
       82. 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.   
     
     
       83. The method of claim 82, wherein the debiting of the account is associated with the payment of a toll. 
     
     
       84. The method of claim 83, wherein a master wireless device is disposed within a toll booth, and said method further comprises operating said master wireless device disposed within said toll booth at least when said target radio frequency device communicating the respective identifier is in proximity thereto. 
     
     
       85. The method of claim 83, wherein the debiting of the account comprises receiving a credit card number against which the toll can be charged. 
     
     
       86. The method of claim 82, wherein the debiting of the account comprises receiving a credit card number which can be charged. 
     
     
       87. The method of claim 82, wherein the debiting of the account is for payment for goods or services. 
     
     
       88. 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.   
     
     
       89. The method of claim 88, wherein the debiting of the account is associated with the payment of a toll. 
     
     
       90. The method of claim 89, wherein the interrogator is disposed within a toll both, and said method further comprises operating the interrogator disposed within said toll both at least when said target radio frequency device communicating is in proximity thereto. 
     
     
       91. The method of claim 89, wherein the debiting of the account comprises receiving a credit card number against which the toll can be charged. 
     
     
       92. The method of claim 88, wherein the debiting of the account comprises receiving a credit card number which can be charged. 
     
     
       93. The method of claim 88, wherein the debiting of the account is for payment for goods or services.