Method and apparatus to manage RFID tags

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.RFID tags are managed by an interrogator. In one embodiment, the interrogator sends a first command indicating a first value and a first memory range, and a second command indicating second value and a second memory range. The first memory range differs from the second memory range by at least two bits. RFID tags compare the first and second values to corresponding values stored in the tags to determine if the tags are selected. Selected tags may respond to the interrogator with independently generated random numbers.

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, comprising:
   sending a first command from an interrogator to a plurality of RFID devices, the first command comprising a first set of fields, wherein the first set of fields includes a first bit string and describes a first memory range that starts at a first bit location;        receiving the first command by an RFID device of the plurality of RFID devices, and in response, the RFID device comparing the first bit string to a first value stored in a first portion of a memory of the RFID device corresponding to the first memory range;        sending a second command from the interrogator to the plurality of RFID devices successively following the first command, the second command comprising a second set of fields, wherein the second set of fields includes a second bit string and describes a second memory range that starts at a second bit location offset from the first bit location by two or more bits;        receiving the second command by the RFID device, and in response, the RFID device comparing the second bit string to a second value stored in a second portion of the memory of the RFID device corresponding to the second memory range; and        receiving a reply from the RFID device based, at least in part, on a first result from the comparing of the first bit string to the first value, and on a second result from the comparing of the second bit string to the second value, wherein the reply includes a random number generated by the RFID device.      
     
     
       28. The method of  claim 27 , wherein the reply further includes an identification code that identifies an object to which the RFID device is attached.  
     
     
       29. The method of  claim 27 , further comprising sending a third command from the interrogator to the plurality of RFID devices after sending the second command and before receiving the reply from the RFID device.  
     
     
       30. The method of  claim 27 , wherein the reply is sent from the RFID device in accordance with an adaptive slotted arbitration scheme.  
     
     
       31. A method, comprising:
   sending a first command followed by a second command, absent any intervening commands, to a plurality of RFID devices, wherein the first command comprises first and second radio frequency (RF) signals and the second command comprises third and fourth RF signals;        receiving a reply from at least one RFID device, the reply indicating that a first number stored in a memory of the RFID device bounded at a first location indicated by the first RF signal is equal to a first value indicated by the second RF signal, and a second number stored in the memory of the RFID device bounded at a second location indicated by the third RF signal is equal to a second value indicated by the fourth RF signal, the reply including a random number independently generated by the RFID device, wherein the second location is offset by two or more bits from the first location in the memory of the RFID device.      
     
     
       32. The method of  claim 31 , further comprising detecting a collision in the reply.  
     
     
       33. The method of  claim 31 , wherein the reply includes an identification number.  
     
     
       34. The method of  claim 31 , wherein the reply is received in accordance with a slotted arbitration scheme.  
     
     
       35. The method of  claim 34 , wherein the random number is  16  bits.  
     
     
       36. The method of  claim 31 , further comprising the RFID device picking a random value from a variable range of integers, the random value corresponding to a slot.  
     
     
       37. The method of  claim 31 , further comprising individually accessing the RFID device including sending the random number to the RFID device.  
     
     
       38. The method of  claim 37 , wherein the random number is  16  bits.  
     
     
       39. A method performed by an interrogator, 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 a random number generated by the RFID device.     
     
     
       40. The method of  claim 39 , wherein the method further comprises transmitting a third command after transmitting the second command and before receiving the reply, the third command including a at least one field configured to select at least a portion of the subgroup of RFID devices to reply to the third command.  
     
     
       41. The method of  claim 40 , wherein the method further comprises transmitting a signal, the signal associated with a slotted arbitration scheme.  
     
     
       42. The method of  claim 39 , wherein the reply further includes an identification number that identifies an object to which the RFID device is attached.  
     
     
       43. The method of  claim 39 , wherein the method further comprises transmitting a command that causes the subgroup of RFID devices to independently generate random numbers.  
     
     
       44. The method of  claim 39 , wherein the method further comprises transmitting a signal after transmitting the second command and before receiving the reply, the signal indicating a number of slots in accordance with a slotted arbitration scheme.  
     
     
       45. The method of  claim 44 , wherein the reply further includes an identification number that identifies an object to which the RFID device is affixed.  
     
     
       46. The method of  claim 39 , wherein the method further comprises transmitting a  16  bit random number to the RFID device to access the RFID device.  
     
     
       47. The method of  claim 46 , wherein the reply further includes an identification number that identifies an object to which the RFID device is attached.  
     
     
       48. A method, comprising:
   providing an RFID device affixed to an object to identify the object, the RFID device storing an identification number;        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 random number from the RFID device, the RFID device belonging to the subgroup, the random number independently generated by the RFID device and being separate from the identification number.      
     
     
       49. The method of  claim 48 , wherein the respective first value of the RFID device comprises at least a portion of the random number.  
     
     
       50. The method of  claim 48 , further comprising receiving the identification number from the RFID device.  
     
     
       51. The method of  claim 50 , further comprising sending the random number to the device.  
     
     
       52. The method of  claim 51 , further comprising sending a third command to the RFID device, the third command associated with a slot value.  
     
     
       53. The method of  claim 48 , further comprising sending a third signal from the interrogator, the third signal being associated with a slotted random anticollision algorithm and indicating a number of slots for the RFID device.  
     
     
       54. The method of  claim 53 , further comprising receiving the identification number from the RFID device.  
     
     
       55. 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 object associated with an identification code; and        an RFID tag affixed to the object and storing the identification code, the RFID tag 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 backscatter a self-generated random number, and to backscatter the identification code.      
     
     
       56. The system of  claim 55 , wherein the reader is further configured to send the random number to the RFID tag.  
     
     
       57. The system of  claim 56 , wherein the RFID tag is further configured to pick a random slot value.  
     
     
       58. The system of  claim 57 , wherein the reader is further configured to send a third command to instruct the RFID tag to generate the random number.