Communication methods using slotted replies

• US 7,315,522 B2
• Filed: 03/28/2001
• Issued: 01/01/2008
• Est. Priority Date: 02/19/1998
• Status: Expired due to Fees

• Current Assignee: Round Rock Research LLC
• Original Assignee: Micron Technology, Inc.
• Inventors: Wood, Clifton W. Jr.
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Hyun; Soon D.
• Application Number:
  US09/820,467
• Publication Number:
  US 20010014090A1
• Time in Patent Office: 2,470 Days
• Field of Search: 370/312, 370/313, 370/329, 370/330, 370/346, 370/347, 370/280, 370/282, 370/445, 370/443, 370/447, 370/449
• US Class Current: 370/312
• CPC Class Codes: G06K 7/0008 General problems related to the reading of electronic memory record carriers, independent of its reading method, e.g. power transfer
• CPC Class Codes: G06K 7/10019 resolving collision on the communication channels between simultaneously or concurrently interrogated record carriers. collision between the communication channels used by wireless communication devices, where the solution is not particularly adapted for RFIDs or the like, H04W74/08
• CPC Class Codes: G06Q 20/24 Credit schemes, i.e. "pay after"
• CPC Class Codes: G06Q 20/26 Debit schemes, e.g. "pay now"
• CPC Class Codes: G06Q 20/3223 Realising banking transactions through M-devices
• CPC Class Codes: G07B 15/00 Arrangements or apparatus for collecting fares, tolls or entrance fees at one or more control points handling coins or valuable papers, e.g. banknotes, G07D; apparatus for vending or hiring articles or services activated by coins, credit cards, paper currency or the like G07F7/00, G07F17/00
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 74/06 using polling
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02
• CPC Class Codes: H04W 76/11 Allocation or use of connection identifiers
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support

Abstract

An RFID tag population is selected by an interrogator. Each tag of the selected tag population then responds to the interrogator in accordance with a slotted arbitration scheme. According to the slotted arbitration scheme, each tag of the selected tag population picks its own random value from a range of integers indicated by the interrogator. The random value corresponds to a slot. The interrogator may indicate that the range of integers is to be adjusted. Each tag of the selected tag population responds to the interrogator with a random number.

Claims

1. A method comprising the steps of:

sending a first signal from an interrogator to a plurality of radio frequency identification (RFID) tags, the first signal including parameters that describe bit storage locations of memory and a bit string;

each of the plurality of tags receiving the first signal and comparing the bit string against respective bits stored in the bit storage locations of memory of each respective tag to determine if the respective tag is a member of a selected tag group;

each tag of the selected tag group independently picking a respective first random slot value from a first number of slot values in accordance with an arbitration scheme; and

a first tag of the selected tag group backscattering a first reply to the interrogator, the first reply including a first random number independently generated by the first tag, the first tag replying in accordance with a first sequence determined at least in part by the respective first random slot value independently picked by each tag of the selected tag group.

2. The method of claim 1, wherein the first random number is 16 bits in length.

3. The method of claim 1, further comprising the steps of:

sending a second signal from the interrogator to the plurality of tags;

each tag of at least a portion of the selected tag group independently picking a respective second random slot value from a second number of slot values in response to the second signal in accordance with the arbitration scheme, and the second number of slot values is different from the first number of slot values; and

a second tag of the at least a portion of the selected tag group backscattering a second reply to the interrogator, the second reply including a second random number independently generated by the second tag, the second tag replying in accordance with a second sequence determined at least in part by the respective second random slot value independently picked by each tag of the at least a portion of the selected tag group.

4. The method of claim 3, wherein the second number of slots values varies from the first number of slot values depending, at least in part, on collisions detected by the interrogator.

5. The method of claim 4, wherein the first random number is 16 bits in length, and the second random number is 16 bits in length.

6. The method of claim 1, further comprising the step of the interrogator receiving the first reply from the first tag, and, in response thereto, the interrogator sending an acknowledge signal to acknowledge the first tag.

7. The method of claim 6, further comprising the step of the first tag backscattering at least a portion of an identification number that identifies an object to which the first tag is affixed.

8. The method of claim 7, further comprising the step of the interrogator accessing the first tag individually after receiving both the first random number and the at least portion of the identification number from the first tag, the step of the interrogator accessing the first tag including the interrogator sending a command that includes a number randomly generated by the first tag.

9. The method of claim 8, wherein the number randomly generated by the first tag is the first random number.

10. The method of claim 1, further comprising the step of the first tag backscattering at least a portion of an identification number, the identification number identifying an object to which the first tag is affixed.

11. The method of claim 1, wherein comparing the bit string against the respective bits stored in the bit storage locations of memory of each respective tag of the plurality of tags comprises each and every tag of the plurality of tags determining itself to be a member of the selected tag group and the plurality of tags includes all tags in a field of the interrogator.

12. A method comprising the steps of:

sending a first signal from an interrogator to a plurality of radio frequency identification (RFID) tags to select a tag group, the first signal including a set of parameters that describe bit storage locations of memory and a bit string;

each of the plurality of tags receiving the first signal and comparing the bit string to a respective number contained in the respective bit storage locations of memory within each of the plurality of tags to determine if a respective tag is a member of the tag group;

sending a second signal from the interrogator;

each tag of the tag group picking a respective first random slot value from a first number of slot values in response to the second signal, a first sequence in which tags of the tag group are to reply to the interrogator being determined at least in part by the first random slot values associated with the tag group;

a first tag of the tag group backscattering a first reply to the interrogator, the first reply including a first random number generated by the first tag, the first tag replying in accordance with the first sequence;

the interrogator receiving the first reply from the first tag, and, in response thereto, the interrogator sending an acknowledge signal to acknowledge the first tag;

sending a third signal from the interrogator; and

a second tag of the tag group backscattering a second reply to the interrogator in response to the third signal, the second reply including a second random number generated by the second tag, the second tag replying in accordance with the first sequence.

13. The method of claim 12, further comprising the interrogator sending a fourth signal after the step of each tag of the tag group picking a respective first random slot value, wherein the step of the first tag of the tag group backscattering the first reply to the interrogator is performed in response to the fourth signal.

14. The method of claim 12, further comprising the steps of:

each tag of at least a portion of the tag group picking a respective second random slot value from a second number of slot values in response to a signal indicating that a number of slots is to be adjusted, a second sequence in which tags are to reply to the interrogator being determined at least in part by the second random slot values associated with the portion of the tag group; and

a third tag of the at least a portion of the tag group backscattering a third reply to the interrogator, the third reply including a third random number generated by the third tag, the third tag replying in accordance with the second sequence.

15. The method of claim 14, further comprising the interrogator sending a fifth signal after the step of each tag of the at least a portion of the tag group picking a respective second random slot value, wherein the step of the third tag of the at least a portion of the tag group backscattering the third reply to the interrogator is performed in response to the fifth signal.

16. The method of claim 14, wherein the second number of slot values varies from the first number of slot values based, at least in part, on collisions detected by the interrogator.

17. The method of claim 12, further comprising the step of the first tag backscattering at least a portion of an identification number that identifies an object to which the first tag is affixed.

18. The method of claim 17, further comprising the step of the interrogator accessing the first tag individually after receiving both the first random number and the at least portion of the identification number from the first tag, the step of the interrogator accessing the first tag including the step of the interrogator sending a command including a number randomly generated by the first tag to identify the first tag.

19. The method of claim 18, wherein the number randomly generated by the first tag to identify the first tag is the first random number.

20. The method of claim 12, further comprising each and every one of the plurality of tags determining itself to be a member of the tag group in response to receiving the first signal, wherein the plurality of tags includes all tags in a field of the interrogator.

21. The method of claim 20, wherein the first and second random numbers are each 16 bits in length.

22. A method comprising the steps of:

sending a query command from an interrogator to a plurality of wireless identification devices, the query command including a first set of fields comprising first bit values;

each device of the plurality of devices using the first bit values to determine if the respective device belongs to a group of chosen wireless identification devices that may respond to the query command;

each device of the group of chosen devices picking a respective first random slot value from a first number of slot values in response to the query command, the first number of slot values being determined using the first bit values;

a first device of the group of chosen devices backscattering a first random number during a first time, the first random number generated by the first device;

sending a subsequent command from the interrogator to the group of chosen devices, the subsequent command including a second set of fields comprising second bit values;

each device of at least a portion of the group of chosen devices picking a respective second random slot value from a second number of slot values in response to the subsequent command, the second number of slot values varying from the first number of slot values and determined using the second bit values; and

a second device of the at least a portion of the group of chosen devices backscattering a second random number during a second time, the second random number generated by the second device.

23. The method of claim 22, wherein the first and second random numbers are each 16 bits in length.

24. The method of claim 22, further comprising the step of the interrogator receiving the first random number from the first device, and, in response thereto, the interrogator sending an acknowledge command to acknowledge the first device.

25. The method of claim 24, further comprising the step of the first device backscattering at least a portion of a first identification code that identifies a first object to which the first device is affixed.

26. The method of claim 25, further comprising the step of the interrogator receiving the second random number from the second device, and, in response thereto, the interrogator sending an acknowledge command to acknowledge the second device.

27. The method of claim 26, further comprising the step of the second device backscattering at least a portion of a second identification code that identifies a second object to which the second device is affixed.

28. The method of claim 27, further comprising the step of the interrogator transmitting the first random number back to the first device to individually access the first device.

29. The method of claim 22, wherein the subsequent command is a query command.

30. A method comprising:

sending a first signal from an interrogator to first and second radio frequency identification (RFID) tags, the first signal including a bit string and indicating bit storage locations of memory, the first tag having stored therein a first set of bits in bit storage locations corresponding to the bit storage locations of memory, and the second tag having stored therein a second set of bits in bit storage locations corresponding to the bit storage locations of memory;

the first tag receiving the first signal and comparing the bit string against the first set of bits to determine that the first tag is selected;

the second tag receiving the first signal and comparing the bit string against the second set of bits to determine that the second tag is selected;

sending a query command from the interrogator, the query command including a set of fields to select the first and second tags for response to the query command;

the first tag picking a first random slot value from a first number of slot values in response to the query command in accordance with an arbitration scheme;

the second tag picking a second random slot value from the first number of slot values in response to the query command in accordance with the arbitration scheme;

the first tag backscattering a first reply to the interrogator during a first period of time, the first reply including a first random number generated by the first tag; and

the second tag backscattering a second reply to the interrogator during a second period of time, the second reply including a second random number generated by the second tag.

31. The method of claim 30, further comprising the interrogator receiving the first reply from the first tag, and, in response thereto, the interrogator sending an acknowledge signal to acknowledge the first tag.

32. The method of claim 31, further comprising the first tag backscattering at least a portion of an identification number that identifies an object to which the first tag is affixed.

33. The method of claim 32, further comprising the interrogator accessing the first tag individually after receiving both the first random number and the at least portion of the identification number from the first tag, wherein accessing the first tag includes the interrogator sending a command that includes a number randomly generated by the first tag.

34. The method of claim 33, wherein the number randomly generated by the first tag is the first random number, and the first random number is 16 bits in length.

35. The method of claim 34, further comprising each and every one of a plurality of tags determining itself to be selected in resoonse to receiving the first signal, wherein the plurality of tags includes all tags in a field of the interrogator.

36. The method of claim 34, further comprising sending a second signal from the interrogator after the step of the first tag picking the first random slot value, the first tag backscattering the first reply in response to receiving the second signal.

37. The method of claim 30, further comprising sending a second signal from the interrogator after the step of the first tag picking the first random slot value, the first tag backscattering the first reply in response to receiving the second signal.

38. A method comprising the steps of:

sending a first command from an interrogator to a radio frequency identification (RFID) tag, the first command including a bit string and indicating bit storage locations of memory, the tag having stored therein an identifier, a portion of the identifier being stored in a location that corresponds to the bit storage locations of memory indicated by the first command;

the tag comparing the bit string against the portion of the identifier to determine if the tag is selected;

sending a second command from the interrogator;

the tag picking a first random value from a first range of values in response to the second command, the first range of values corresponding to slots in accordance with an arbitration scheme;

the tag backscattering a first self-generated random number during a slot of time that corresponds to the first random value in accordance with the arbitration scheme;

the interrogator detecting a collision upon receiving the first random number;

sending a third command from the interrogator;

the tag picking a second random value from a second range of values different from the first range of values in response to the third command, the second range of values corresponding to slots in accordance with the arbitration scheme; and

the tag backscattering a second self-generated random number during a slot of time that corresponds to the second random value in accordance with the arbitration scheme.

39. The method of claim 38, further comprising the step of the interrogator receiving the second random number from the tag during the slot of time that corresponds to the second random value, and, in response thereto, the interrogator sending a fourth command to acknowledge the tag.

40. The method of claim 39, further comprising the step of the tag backscattering at least a portion of an identification number that identifies an object to which the tag is affixed.

41. The method of claim 40, wherein a difference between the first range of values and the second range of values depends on the third command.

42. The method of claim 38, further comprising the step of the interrogator accessing the tag individually by sending a fourth command that includes the second random number.

43. The method of claim 42, further comprising the step of the tag backscattering at least a portion of an identification number that identifies an object to which the tag is affixed.

44. The method of claim 43, wherein a difference between the first range of values and the second range of values depends on the third command.

45. The method of claim 38, further comprising the step of the interrogator receiving the second random number from the tag during the slot of time that corresponds to the second random value, and subsequently sending a fourth command to the tag, the fourth command including the second random number, the second random number being 16 bits in length.

46. The method of claim 45, further comprising the step of the tag backscattering at least a portion of an identification number that identifies an object to which the tag is affixed.

47. The method of claim 46, wherein a difference between the first range of values and the second range of values depends on the third command.

48. The method of claim 38, further comprising the step of the tag backscattering at least a portion of an identification number that identifies an object to which the tag is affixed.

49. The method of claim 48, wherein a difference between the first range of values and the second range of values depends on the third command.

50. The method of claim 38, wherein a difference between the first range of values and the second range of values depends on the third command.

51. The method of claim 50, wherein the difference between the first range of values and the second range of values depends on collisions detected by the interrogator.

52. The method of claim 38, wherein the first random number, the second random number, and the identifier are the same number.

53. A method comprising:

sending a first command from an interrogator, the first command including a first set of parameters;

a first radio frequency identification (RFID) device wirelessly receiving the first command and using the first set of parameters to determine if the first device is a participant that may respond to the first command and also to determine a first number of slots, the first device randomly picking a first slot from the first number of slots;

a second RFID device wirelessly receiving the first command and using the first set of parameters to determine if the second device is a participant that may respond to the first command and also to determine the first number of slots, the second device randomly picking a second slot from the first number of slots; and

the first device backscattering a first 16 bit random number during a period of time corresponding to the first slot randomly picked by the first device, the first random number generated by the first device.

54. The method of claim 53, further comprising the interrogator receiving the first random number from the first device, and responding by sending an acknowledge command to acknowledge the first device.

55. The method of claim 54, further comprising the first device backscattering at least a portion of an identification number that identifies an object to which the first device is affixed.

56. The method of claim 55, further comprising the interrogator accessing the first device including transmitting the first random number back to the first device.

57. The method of claim 53, further comprising the second device backscattering a second 16 bit random number during a period of time corresponding to the second slot randomly picked by the second device, wherein the second random number is generated by the second device, the first slot is equal to the second slot, and the interrogator detects a collision between the first and second random numbers;

sending a second command from the interrogator at least partially in response to detecting the collision, the second command including a second set of parameters;

the second device wirelessly receiving the second command and using the second set of parameters to determine if the second device is a participant that may respond to the second command and also to determine a second number of slots, wherein the second number of slots varies from the first number of slots, and the second device randomly picks a third slot from the second number of slots; and

the second device backscattering a third 16 bit random number during a period of time corresponding to the third slot, wherein the third random number is generated by the second device.

58. The method of claim 57, further comprising:

the first device backscattering at least a portion of a first identification number that identifies a first object to which the first device is affixed; and

the second device backscattering at least a portion of a second identification number that identifies a second object to which the second device is affixed.

59. The method of claim 58, further comprising the interrogator accessing the first device including transmitting the first random number back to the first device.

60. A method comprising:

sending a first query command from an interrogator to a radio frequency identification (RFID) tag, the first query command including a first set of fields;

the tag wirelessy receiving the first query command;

the tag determining, based on at least one field of the first set of fields, if the tag is chosen to participate in an arbitration scheme;

the tag picking a first random value from a first number of values, the first number of values being determined using at least one field of the first set of fields, the first random value corresponding to a first slot value in accordance with the arbitration scheme;

the tag backscattering a reply to the interrogator during a first period of time in accordance with the arbitration scheme;

sending a second command from the interrogator in response to the reply, the second command including a second set of fields;

the tag wirelessly receiving the second command;

the tag picking a second random value from a second number of values, the second number of values being determined using at least one field of the second set of fields, wherein the second number of values varies from the first number of values, the second random value corresponding to a second slot value in accordance with the arbitration scheme;

the tag backscattering a random number to the interrogator during a second period of time in accordance with the arbitration scheme, wherein the random number is independently generated by the tag; and

sending an acknowledge command from the interrogator to the tag if the random number is received by the interrogator without detecting a collision.

61. The method of claim 60, further comprising the tag determining, based on at least one field of the second set of fields, if the tag is a participant that may respond to the second command.

62. The method of claim 61, further comprising the tag backscattering at least a portion of an identification number that identifies an object to which the tag is affixed.

63. The method of claim 62, further comprising the interrogator detecting a collision upon receiving the reply.

64. The method of claim 63, wherein the second number of values varies from the first number of values based, at least in part, on collisions detected by the interrogator.

65. The method of claim 60, further comprising the interrogator transmitting the random number back to the tag to individually access the tag.

66. The method of claim 65, further comprising the tag backscattering at least a portion of an identification number that identifies an object to which the tag is affixed.

67. A method comprising:

transmitting a first command from an interrogator, the first command to choose a group of radio frequency identification (RFID) tags according to one or more fields of the first command;

causing each respective tag of a first portion of the group of tags to backscatter a respective, independently generated random number in a first order determined, at least in part, by a respective first slot value randomly picked from a first number of values by each respective tag of the first portion in accordance with an arbitration scheme;

causing each respective tag of a second portion of the group of tags to backscatter a respective, independently generated random number in a second order determined, at least in part, by a respective second slot value randomly picked from a second number of values by each respective tag of the second portion in accordance with the arbitration scheme, wherein the first number of values varies from the second number of values;

acknowledging each respective tag of the group of tags; and

causing each respective tag of the group of tags to backscatter at least a portion of a respective identification code that identifies a respective object to which each respective tag is affixed.

68. The method of claim 67, wherein a plurality of RFID tags are members of both the first and second portions of the group of tags.

69. The method of claim 67, wherein the group of tags is fewer than all RFID tags in a field of the interrogator.

70. The method of claim 67, wherein each respective, independently generated random number is 16 bits in length.

71. The method of claim 70, further comprising accessing an individual tag of the group of tags including sending back to the individual tag the respective random number independently generated by the respective individual tag.

72. The method of claim 71, wherein the first number of values is indicated by a field of the first command.

73. The method of claim 67, further comprising choosing the second portion of the group of tags, including comparing a value of a field of a second command to a respective value stored in each respective tag of the second portion, wherein the second command is transmitted by the interrogator after the first command is transmitted and before the respective second slot value is randomly picked by each respective tag of the second portion.

74. The method of claim 73, wherein the first number of values is indicated by a field of the first command, and the second number of values is indicated by a field of the second command.

75. The method of claim 74, further comprising accessing an individual tag of the group of tags including sending back to the respective individual tag the respective random number independently generated by the respective individual tag.

76. The method of claim 75, wherein each of the random numbers is 16 bits in length.

77. The method of claim 67, wherein each of the random numbers is 16 bits in length and the group of tags is fewer than all RFID tags in a field of the interrogator.

78. The method of claim 77, further comprising accessing an individual tag of the group of tags including transmitting to a respective individual tag the respective random number independently generated by the respective individual tag.