Method of addressing messages and communications

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 . In one aspect, a method implemented in an RFID device includes: receiving a first command, comprising a first set of bit values, from an interrogator to select the RFID device based on a comparison between the first set of bit values and data stored in the RFID device; transmitting a response to the first command, the response including an identifier of the RFID device; if the response is received at an interrogator, remaining silent when the first command is subsequently repeated; and if the response is not received at the interrogator, re- transmitting the response when the first command is subsequently repeated.

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. A method in accordance with  claim 1  and further comprising, if a collision occurred in response to the first mentioned command, sending a command at a different node, using the interrogator. 
     
     
       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 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. 
     
     
       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.    
     
     
       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 7  wherein sending a reply to the interrogator comprises transmitting the unique identification number of the device sending the reply. 
     
     
       9. A method in accordance with  claim 7  wherein one of the first and second specified groups contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, and wherein the device that is not within communications range of the interrogator does not respond to the interrogator. 
     
     
       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 7  wherein, after receiving a reply without collision from a device, the interrogator sends a communication 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:
 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.    
     
     
       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  wherein establishing unique identification numbers for respective devices comprises establishing a predetermined number of bits to be used for the unique identification numbers. 
     
     
       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 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.    
     
     
       15. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with  claim 14  wherein the first mentioned specified group contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, and wherein the device that is not within communications range of the interrogator does not respond to the transmitting of the command or the re-transmitting of the command. 
     
     
       16. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with  claim 14  wherein the first mentioned specified group contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, and wherein the device that is within communications range of the interrogator responds to the transmitting of the command and the re-transmitting of the command. 
     
     
       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 14  wherein a device in the first mentioned specified group is capable of changing between being within communications range of the interrogator and not being within communications range of the interrogator over time. 
     
     
       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 14  wherein the devices respectively comprise an integrated circuit including a receiver, a modulator, and a microprocessor in communication with the receiver and modulator. 
     
     
       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 14  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.    
     
     
       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 19  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 capable of communicating with the interrogator are identified.    
     
     
       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. 
     
     
       22. A communications system in accordance with  claim 21  wherein the interrogator is configured to send a command at a different node if a collision occurs in response to the first mentioned command. 
     
     
       23. A communications system in accordance with  claim 21  wherein 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. 
     
     
       24. A communications system in accordance with  claim 21  wherein 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, and wherein the device that is within communications range of the interrogator responds to the command. 
     
     
       25. A communications system in accordance with  claim 21  wherein a device in a subgroup is movable relative to the interrogator so as to be capable of changing between being within communications range of the interrogator and not being within communications range. 
     
     
       26. A communications system in accordance with  claim 21  wherein the wireless identification device comprises an integrated circuit including a receiver, a modulator, and a microprocessor in communication with the receiver and modulator. 
     
     
       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.    
     
     
       28. A system in accordance with  claim 27  wherein sending a reply to the interrogator comprises transmitting the unique identification number of the device sending the reply. 
     
     
       29. A system in accordance with  claim 27  wherein a specified group contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator. 
     
     
       30. A system in accordance with  claim 27  wherein the interrogator further includes means for, after receiving a reply without collision from a device, sending a command individually addressed to that device. 
     
     
       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.    
     
     
       32. A system in accordance with  claim 31  wherein the first mentioned specified group contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator. 
     
     
       33. A system in accordance with  claim 31  wherein a device in the first mentioned specified group is capable of changing between being within communications range of the interrogator and not being within communications range of the interrogator over time. 
     
     
       34. A system in accordance with  claim 31  wherein the respective devices comprise an integrated circuit including a receiver, a modulator, and a microprocessor in communication with the receiver and modulator. 
     
     
       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.    
     
     
       36. A system in accordance with  claim 35  wherein the unique identification numbers for respective devices are stored in digital form and respectively comprise a predetermined number of bits. 
     
     
       37. A system in accordance with  claim 35  wherein the random values for respective devices are stored in digital form and respectively comprise a predetermined number of bits. 
     
     
       38. A system in accordance with  claim 35  wherein the interrogator is configured to determine if a collision occurred between devices that sent a reply in response to respective Identify commands and, if so, to create further new specified groups and repeat 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 responding devices capable of responding are identified. 
     
     
       39. A radio frequency identification ( RFID )  system, comprising:      a plurality of RFID tags; and        at least one interrogator, the interrogator to transmit a first request to the plurality of RFID tags, the first request specifying a first subgroup of a group of random numbers, among the plurality of RFID tags at least one RFID tag having generated a random number that is within the first subgroup to provide a first response, the interrogator to receive one or more responses, including the first response, from one or more of the plurality of RFID tags respectively, and the interrogator to repeat the first request if the first response is received without a detected collision.     
     
     
       40. The system of  claim 39 , wherein the first request includes a selection indicator; and the one or more of the plurality of RFID tags provides the one or more responses only if the selection indicator corresponds to one or more selection bits stored on the one or more of the plurality of RFID tags. 
     
     
       41. The system of  claim 39 , wherein the one or more of the plurality of RFID tags are configured to set an inventoried flag to a first state to indicate that a respective RFID tag has responded to the interrogator. 
     
     
       42. The system of  claim 39 , wherein the interrogator is configured to transmit a wake- up signal to cause the one or more of the plurality of RFID tags to transition from a battery - saving mode to an operational mode.   
     
     
       43. The system of  claim 39 , wherein the interrogator is configured to send a sleep command to the RFID tag that provides the first response. 
     
     
       44. The system of  claim 39 , wherein the first response includes the random number generated by the RFID tag that provides the first response; and the interrogator is to send at least one additional command to the RFID tag, the first RFID tag being identified in the at least one additional command by the random number. 
     
     
       45. A method implemented in a radio frequency identification ( RFID )  system having at least one RFID tag and at least one RFID interrogator, the method comprising:      generating random numbers at a plurality of RFID tags, including an RFID tag affixed to an object;        transmitting a first command from the interrogator to select RFID tags, including the RFID tag affixed to the object, that have generated random numbers that are within a subset of random numbers;        the selected RFID tags transmitting a response, including a random number generated by the RFID tag affixed to the object;        if the random number is received at the interrogator, retransmitting the first command.     
     
     
       46. The method of  claim 45 , wherein the selected RFID tags transmitting the response to indicate data stored on the selected RFID tags matches one or more selection bits specified by the first command. 
     
     
       47. The method of  claim 45 , wherein the RFID tag is further configured to communicate the response at a time based at least in part upon a random number. 
     
     
       48. The method of  claim 45 , further comprising transmitting a command to silence the RFID tag affixed to the object upon receiving the response. 
     
     
       49. An interrogator, comprising:
   one or more antennas to poll a plurality of radio frequency identification  ( RFID )  tags;        means for transmitting a first command to select a first subset of the plurality of RFID tags;        means for receiving one or more responses from the subset of RFID tags, the one or more responses including a random number generated at a first RFID tag of the plurality of RFID tags;        means for transmitting the first command if at least one of the one or more responses is received without a collision; and        means for transmitting a second command to select a second subset of the plurality of RFID tags if a collision is detected in the one or more responses.     
     
     
       50. The interrogator of  claim 49 , wherein the first command includes a selection indicator that identifies a class of one or more of a plurality of RFID tags from which a response is being requested. 
     
     
       51. The interrogator of  claim 49 , further comprising repeatedly redefining the subgroup to include fewer possible random numbers and transmitting a new request for RFID tags having a random number within the subgroup to respond until receiving a response without a collision or receiving no response. 
     
     
       52. A method implemented in a radio frequency identification ( RFID )  device, the method comprising:      receiving a first command, comprising a first set of bit values, from an interrogator to select the RFID device based on a comparison between the first set of bit values and data stored in the RFID device;        transmitting a response to the first command, the response including an identifier of the RFID device;        if the response is received at an interrogator, remaining silent when the first command is subsequently repeated; and        if the response is not received at the interrogator, retransmitting the response when the first command is subsequently repeated.     
     
     
       53. The method of  claim 52 , wherein transmitting the response is done in a randomly selected slot; and the method further comprises transmitting an identification code to identify a person with whom the RFID device is associated. 
     
     
       54. A method implemented in a radio frequency identification ( RFID )  system having an interrogator to poll a plurality of RFID tags, the method comprising:      transmitting a first command to select a first subset of RFID tags;        receiving one or more responses from the subset of RFID tags, the one or more responses including a random number generated at a first RFID tag of the plurality of RFID tags; and        retransmitting the first command if at least one of the one or more responses is received without a collision.     
     
     
       55. The method of  claim 54 , further comprising:
   affixing the plurality of RFID tags to a plurality of objects to track as inventory is added and removed.     
     
     
       56. The method of  claim 54 , further comprising:
   after receiving the one or more responses and prior to retransmitting the first command, transmitting a command to silence an RFID tag from which a response is received without a collision.     
     
     
       57. The method of  claim 54 , wherein the first command includes a selection indicator that identifies a class of one or more of a plurality of RFID tags from which a response is being requested. 
     
     
       58. The method of  claim 54 , further comprising repeatedly redefining the subgroup to include fewer possible random numbers and transmitting a new request for RFID tags having a random number within the subgroup to respond until receiving a response without a collision or receiving no response. 
     
     
       59. A radio frequency identification ( RFID )  device, comprising:      an antenna;        a receiver coupled to the antenna to receive a first command from an interrogator, the first command comprising a first value having multiple bits to select a group of one or more RFID devices in a field of the interrogator;        processing circuitry to determine if the RFID device is selected by the interrogator based on the first value; and        a transmitter to communicate a response to the first command in a first time slot with a first probability if the RFID device is selected by the interrogator in accordance with the first value, wherein the response includes an identifier of the RFID device and the first probability is indicated by the first command;        wherein if the first command, including the first value to select the group, is subsequently repeated by the interrogator while the RFID device remains within the field of the interrogator, the RFID device is configured to:      remain silent, if the response was received at the interrogator without detecting a collision, and        retransmit the response if the response was not received at the interrogator without detecting a collision.       
     
     
       60. The RFID device of  claim 59 , wherein the identifier comprises a random number generated by the RFID device. 
     
     
       61. The RFID device of  claim 60 , wherein the response includes the multiple bits of the first value. 
     
     
       62. The RFID device of  claim 59 , wherein the receiver is configured to receive signals each indicating a beginning of a time slot; and wherein the transmitter is configured to communicate the response to the first command in a selected one of a number of time slots indicated by the first command. 
     
     
       63. The RFID device of  claim 59 , wherein the response includes the multiple bits of the first value. 
     
     
       64. The RFID device of  claim 59 , wherein the RFID device is further configured to transmit an identification code to identify a person with whom the RFID device is associated. 
     
     
       65. The RFID device of  claim 59 , wherein the interrogator is to transmit the first command before the RFID device first communicates to the interrogator. 
     
     
       66. A radio frequency identification ( RFID )  interrogator, comprising:      an antenna;        a transmitter coupled to the antenna to transmit a first command comprising a value, having multiple bits, corresponding to a group of one or more RFID devices to be selected in a field of the interrogator;        a receiver to receive a response to the first command from an RFID device selected by the first command in accordance with the value, the response to include an identifier of the RFID device and to be received in a time slot in accordance with a time slot method; and        processing circuitry to determine if the response is received without a collision, and if so, to transmit a second command to silence the RFID device and to retransmit the first command, including the value, to reselect the group to respond to the first command.     
     
     
       67. The interrogator of  claim 66 , wherein the identifier comprises a random number generated by the RFID device. 
     
     
       68. The interrogator of  claim 66 , wherein the receiver is to receive the response in a first time slot with a first probability in accordance with the time slot method. 
     
     
       69. The interrogator of  claim 66 , wherein the receiver is to further receive an identification code from the RFID device to identify a person with whom the RFID device is associated. 
     
     
       70. The interrogator of  claim 66 , wherein the response includes the multiple bits of the value. 
     
     
       71. The interrogator of  claim 66 , wherein the transmitter is to transmit the first command after the RFID device enters the field of the interrogator but before the RFID device communicates any responses to the interrogator. 
     
     
       72. A method comprising:
   transmitting from an interrogator a first command, including a first identifier comprising a plurality of bits, to select a set of one or more RFID devices, corresponding to the first identifier, in a field of the interrogator, and to request the set to respond in accordance with a time slot method in which an RFID device responds in a first time slot with a probability indicated by the first command;        receiving a first response to the first command from a first RFID device of the set, wherein the first response is received in a time slot in accordance with the time slot method and the first response includes a second identifier of the RFID device;        detecting no collision in the first response from the first RFID device; and        retransmitting from the interrogator the first command, including the first identifier, to select the set of one or more RFID devices and to request the set to respond while the set remains in the field of the interrogator.     
     
     
       73. The method of  claim 72 , wherein the second identifier comprises a random number generated by the RFID device. 
     
     
       74. The method of  claim 72 , further comprising transmitting a plurality of signals from the interrogator, each of the plurality of signals defining the start of a time slot in accordance with the time slot method. 
     
     
       75. The method of  claim 72 , further comprising transmitting from the interrogator a second command, wherein the second command indicates a change in the probability. 
     
     
       76. The method of  claim 72 , wherein the response includes the plurality of bits of the first identifier. 
     
     
       77. The method of  claim 72 , further comprising:
   receiving an identification code from the RFID device to identify a person with whom the RFID device is associated.     
     
     
       78. The method of  claim 72 , wherein transmitting the first command is performed after the RFID device enters the field of the interrogator but before the RFID device communicates any signals to the interrogator. 
     
     
       79. A radio frequency identification ( RFID )  system, comprising:      an interrogator to transmit a first command to select a group of one or more RFID devices in a field of the interrogator, wherein the first command includes a first identifier, comprising a plurality of bits, that corresponds to the group of one or more RFID devices; and        an RFID device in the field of the interrogator to determine, using the first identifier, if the RFID device is selected as one of the group, and if so, to communicate a response to the first command in a first time slot with a first probability, wherein the response includes a second identifier of the RFID device;        wherein the interrogator is to retransmit the first command, including the first identifier, after the interrogator receives the response, without a collision, from the RFID device and while the group remains in the field of the interrogator.     
     
     
       80. The system of  claim 79 , wherein the interrogator is configured to transmit a plurality of signals, each defining a start of a time slot for one or more responses to the first command, and the RFID device is configured to transmit the response to the first command in a randomly selected time slot. 
     
     
       81. The system of  claim 79 , wherein the response from the first RFID device includes the plurality of bits of the first identifier. 
     
     
       82. The system of  claim 79 , wherein the second identifier comprises a random number generated by the RFID device. 
     
     
       83. The system of  claim 79 , wherein the RFID device stores an identification code that identifies an associated person. 
     
     
       84. The system of  claim 79 , wherein the first probability is indicated by the first command. 
     
     
       85. The system of  claim 79 , wherein the interrogator is to transmit the first command after the RFID device enters the field of the interrogator but before the RFID device subsequently communicates to the interrogator.