Method and apparatus for an arbitration scheme for radio frequency identification devices

• US 7,639,638 B2
• Filed: 05/02/2006
• Issued: 12/29/2009
• Est. Priority Date: 02/19/1998
• Status: Expired due to Fees

• Current Assignee: Round Rock Research LLC
• Original Assignee: Keystone Technology Solutions, LLC
• Inventors: Wood, Clifton W. Jr.
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US11/416,846
• Publication Number:
  US 20060209781A1
• Time in Patent Office: 1,337 Days
• Field of Search: None
• 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

RFID tags are identified. In one embodiment, RFID tags may be chosen to respond to an interrogator in accordance with an arbitration scheme. According to one arbitration scheme, each chosen tag may randomly pick a slot value. The interrogator may indicate that the number of slot values is to be adjusted. Each chosen tag may respond to the interrogator with a random number.

Claims

1. A method comprising:

sending a first command from an interrogator to a plurality of wireless identification devices to select a first subset of the plurality of wireless identification devices in accordance with an arbitration scheme, the first subset associated with a first branch of a search tree corresponding to a tree search scheme, the first command requesting each of the plurality of wireless identification devices of the first subset to respond approximately simultaneously;

sending a second command from the interrogator to the plurality of wireless identification devices to select a second subset of the plurality of wireless identification devices in accordance with the arbitration scheme, the second subset associated with a second branch of the search tree, the second command requesting each of the plurality of wireless identification devices of the second subset to respond in an independently selected one of a plurality of time slots in accordance with an Aloha scheme;

detecting a collision between at least two wireless identification devices of the plurality of wireless identification devices; and

skipping at least one level of the search tree in response to detecting the collision.

2. The method of claim 1, further comprising receiving a plurality of replies from the plurality of wireless identification devices in accordance with the arbitration scheme, each of the plurality of replies including a respective number independently generated by a respective wireless identification device to identify that wireless identification device.

3. The method of claim 2, wherein the number generated by a respective device is randomly generated.

4. The method of claim 1, further comprising sending a third command to request the plurality of wireless identification devices to respond approximately simultaneously, wherein the plurality of wireless identification devices comprises all wireless identification devices capable of communicating and participating in the arbitration scheme when the third command is sent.

5. The method of claim 4, wherein the third command comprises a mask, the mask to be used to select a portion of an identification number stored in each of the plurality of wireless identification devices for comparison to a value, the mask being “

0”

such that no portion of the identification number is selected.

6. The method of claim 1, wherein the first and second commands each comprise a mask and a value, the mask to be used to select a portion of an identification number stored in each of the plurality of wireless identification devices for comparison to the value.

7. The method of claim 6, wherein the mask indicates a bit length of the value.

8. The method of claim 7, wherein the mask corresponds to a level of the search tree, and the value corresponds to a subset within the level of the search tree.

9. The method of claim 7, wherein the mask is applied bitwise to the identification number to select the portion of the identification number.

10. The method of claim 1, further comprising receiving a plurality of replies from the second subset of the plurality of wireless identification devices in response to the second command, the second command comprising a mask to be used to select a portion of a number stored in each of the plurality of wireless identification devices for comparison to a value, the plurality of replies excluding the portion of the number.

11. The method of claim 1, further comprising sending a plurality of signals in accordance with the Aloha scheme, each of the plurality of signals indicating to the second subset of wireless identification devices a beginning of each of the plurality of time slots.

12. A method comprising:

sending a first command from an interrogator to a plurality of wireless identification devices to select a first subset of the plurality of wireless identification devices and to request each wireless identification device of the first subset to respond in an independently selected one of a first number of time slots in accordance with an adaptive arbitration scheme; and

sending a second command from the interrogator to the plurality of wireless identification devices to select a second subset of wireless identification devices and to request each wireless identification device of the second subset to respond in an independently selected one of a second number of time slots in accordance with the adaptive arbitration scheme.

13. The method of claim 12, wherein the first and second commands each include a respective value to indicate which of the plurality of wireless identification devices are members of the first subset and which of the plurality of wireless identification devices are members of the second subset.

14. The method of claim 13, further comprising a wireless identification device of the plurality of wireless identification devices receiving the value and comparing the value to a number stored in the wireless identification device to determine if the wireless identification device is a member of any of the first and second subsets.

15. The method of claim 13, wherein the value is selected to indicate that the first subset includes all wireless identification devices capable of communicating and participating in the adaptive arbitration scheme when the first command is sent.

16. The method of claim 12, wherein the first subset includes the second subset.

17. The method of claim 16, wherein the first subset includes all wireless identification devices receiving the first command and participating in the arbitration scheme, and the second subset includes all wireless identification devices receiving the second command and participating in the arbitration scheme.

18. The method of claim 16, wherein the second subset excludes at least one wireless identification device of the first subset that is identified before the second command is sent.

19. The method of claim 18, further comprising receiving an error-free response from the one wireless identification device of the first subset in response to the first command before the second command is sent, the error-free response including at least a portion of an identification number of the one wireless identification device.

20. The method of claim 12, further comprising:

receiving a first plurality of replies in response to sending the first command, each of the first plurality of replies including a respective value independently generated by each respective wireless identification device of the first subset; and

receiving a second plurality of replies in response to sending the second command, each of the second plurality of replies including a respective value independently generated by each respective wireless identification device of the second subset.

21. The method of claim 20, wherein the respective values are each randomly generated.

22. The method of claim 20, wherein the respective values are each sixteen bits long.

23. The method of claim 22, wherein each of the first and second plurality of replies further includes a unique identification number.

24. The method of claim 23, further comprising sending a third command individually addressed to one of the plurality of wireless identification devices by sending a sixteen bit value independently generated by the one of the plurality of wireless identification devices.

25. The method of claim 12, wherein the second number of time slots is different than the first number of time slots, and is determined based on a number of responses received.

26. The method of claim 12, wherein the second number of time slots is selected to be less than the first number of time slots if a threshold number of responses are received in response to the first command.

27. The method of claim 12, further comprising sending a plurality of signals in accordance with the adaptive arbitration scheme, each of the plurality of signals indicating a beginning of each of the time slots.

28. The method of claim 12, wherein the one of the second number of time slots in which to respond is independently selected by each respective one of the plurality of wireless identification devices of the second subset using an independently generated respective random number.

84. The method of claim 12, wherein the first subset includes less than all of the plurality of wireless identification devices.

85. The method of claim 23, wherein the first subset is fewer in number than all of the plurality of wireless identification devices.

29. A wireless identification device comprising:

a receiver to receive a first command comprising a first value, and a second command comprising a second value, the first and second values to select a plurality of wireless identification devices;

a memory storing an identification number to be transmitted;

a random number generator to generate a random number; and

a backscatter transmitter to transmit a first response in an independently selected one of a first plurality of time slots in accordance with an arbitration scheme if it is determined, using the first value, that the wireless identification device is selected to respond to the first command, the backscatter transmitter further to transmit a second response in an independently selected one of a second plurality of time slots in accordance with the arbitration scheme if it is determined, using the second value, that the wireless identification device is selected to respond to the second command, the second plurality of time slots to be different in number than the first plurality of time slots.

30. The device of claim 29, wherein the second value is different from the first value.

31. The device of claim 29, wherein the selected one of the first plurality of time slots is to be selected by the wireless identification device using a first randomly generated number and the selected one of the second plurality of time slots is to be selected by the wireless identification device using a second randomly generated number.

32. The device of claim 29, further comprising circuitry to compare the first value to the random number to determine if the wireless identification device is to respond to the first command.

33. The device of claim 29, wherein:

the first value corresponds to a first subset of the plurality of wireless identification devices;

the second value corresponds to a second subset of the plurality of wireless identification devices; and

the first subset includes the second subset.

34. The device of claim 33, wherein:

the first subset includes all wireless identification devices receiving the first command and participating in the arbitration scheme; and

the second subset includes all wireless identification devices receiving the second command and participating in the arbitration scheme.

35. The device of claim 33, wherein the second subset excludes at least one wireless identification device of the first subset that is identified before the second command is sent.

36. The device of claim 29, wherein the first and second values are each multibit values, the first value corresponds to the same set of wireless identification devices as the second value, and the transmitter is to transmit the identification number to identify a person associated with the device.

37. The device of claim 29, wherein the second response includes the random number and at least a portion of the identification number.

38. The device of claim 37, wherein the random number is sixteen bits long.

39. The device of claim 38, wherein the receiver is further to receive a third command individually addressed to the wireless identification device using the random number.

40. The device of claim 29, wherein:

the first and second commands are received from an interrogator; and

the number of the second plurality of time slots is determined based on a number of responses received by the interrogator.

41. The device of claim 40, wherein the number of the second plurality of time slots is selected to be less than the number of the first plurality of time slots if a threshold number of responses are received by the interrogator in response to the first command.

42. The device of claim 29, wherein the receiver is further to receive a plurality of signals in accordance with the adaptive arbitration scheme, each of the plurality of signals indicating a beginning of each of the time slots.

43. A system for tracking a plurality of objects, the system comprising:

a plurality of wireless identification devices, each device attached to a respective one of the plurality of objects and storing a respective identification number to identify the respective object, and each device including a random number generator to generate a respective random number to be transmitted; and

an interrogator to;

send a first command to the plurality of wireless identification devices, the first command to include a first value to select a first set of the plurality of wireless identification devices in accordance with the first value, wherein in response to the first command at least a first wireless identification device of the first set is to respond with multiple bits of its respective identification number and random number in a randomly selected one of a first number of time slots in accordance with an arbitration scheme; and

send a second command to the plurality of wireless identification devices, the second command to include a second value, different from the first value, to select a second set of the plurality of wireless identification devices in accordance with the second value, wherein in response to the second command at least a second wireless identification device of the second set is to respond with multiple bits of its respective identification number and random number in a randomly selected one of a second number of time slots in accordance with the arbitration scheme.

44. The system of claim 43, wherein the second value is different from the first value.

45. The system of claim 44, wherein the first wireless identification device of the plurality of wireless identification devices is to receive the first value and compare the first value to a number stored in the first wireless identification device to determine if the first wireless identification device is a member of the first set, and wherein the second number of time slots is different from the first number of time slots.

46. The system of claim 44, wherein the interrogator is further to select the first value to indicate that the first set includes all wireless identification devices within a field of the interrogator.

47. The system of claim 43, wherein the first set includes the second set.

48. The system of claim 47, wherein the first set includes all wireless identification devices within a field of the interrogator, and the second set includes all wireless identification devices within the field of the interrogator.

49. The system of claim 47, wherein the second set excludes at least one wireless identification device of the first set that is identified before the second command is sent.

50. The system of claim 43, wherein the interrogator is further to:

receive a first plurality of replies in response to sending the first command, each of the first plurality of replies including the random number generated by each respective wireless identification device of the first set; and

receive a second plurality of replies in response to sending the second command, each of the second plurality of replies including the random number generated by each respective wireless identification device of the second set.

51. The system of claim 50, wherein the random numbers are each sixteen bits long.

52. The system of claim 51, wherein the interrogator is to determine the identification number of the respective wireless identification device from the first and second plurality of replies.

53. The system of claim 52, wherein the interrogator is further to send a third command individually addressed to one of the plurality of wireless identification devices by sending a random number independently generated by the one of the plurality of wireless identification devices.

54. The system of claim 43, wherein the second number of time slots is different than the first number of time slots.

55. The system of claim 43, wherein the second number of time slots is selected to be less than the first number of time slots if a predetermined number of responses are received in response to the first command.

56. The system of claim 43, wherein the interrogator is further to send a plurality of signals in accordance with the arbitration scheme, each of the plurality of signals indicating a beginning of each of the time slots.

86. The system of claim 52, wherein the first set includes less than all of the plurality of wireless identification devices.

57. A system comprising:

an interrogator to send a first command comprising a first value, and a second command comprising a second value; and

at least one wireless identification device comprising a receiver, memory storing an identification number, a random number generator, and a transmitter, the wireless identification device to implement an arbitration scheme comprising;

receiving the first and second commands; and

transmitting a first signal in an independently selected one of a first plurality of time slots in accordance with the arbitration scheme if it is determined, using the first value, that the wireless identification device is selected for response to the first command, and transmitting a second signal in an independently selected one of a second plurality of time slots in accordance with the arbitration scheme if it is determined, using the second value, that the wireless identification device is selected for response to the second command, wherein in accordance with the arbitration scheme the second plurality of time slots may differ in number from the first plurality of time slots.

58. The system of claim 57, wherein the second signal is to include a random number, and the interrogator is to determine the identification number from the second signal.

59. The system of claim 57, wherein the selected one of the first plurality of time slots is to be selected by the wireless identification device using a first randomly generated number and the selected one of the second plurality of time slots is to be selected by the wireless identification device using a second randomly generated number.

60. The system of claim 57, wherein the wireless identification device is further to compare the first value to the random number to determine if the wireless identification device is to respond to the first command.

61. The system of claim 57, wherein:

the first value corresponds to a first set of a plurality of wireless identification devices;

the second value corresponds to a second set of the plurality of wireless identification devices; and

the first set includes the second set.

62. The system of claim 61, wherein:

the first set includes all wireless identification devices receiving the first command and participating in the arbitration scheme; and

the second set includes all wireless identification devices receiving the second command and participating in the arbitration scheme.

63. The system of claim 61, wherein the second set excludes at least one wireless identification device of the first set that is identified before the second command is sent.

64. The system of claim 57, wherein the first and second values are each multibit values, the first value corresponds to the same wireless identification devices as the second value, and the transmitter is to transmit the identification number to identify a person associated with the device.

65. The system of claim 57, wherein the first signal includes a plurality of bits of the identification number and a random number generated by the random number generator.

66. The system of claim 65, wherein the random number is sixteen bits long.

67. The system of claim 66, wherein the receiver is further to receive a third command from the interrogator individually addressed to the wireless identification device using the random number.

68. The system of claim 57, wherein the number of the second plurality of time slots is determined based on a number of responses received by the interrogator.

69. The system of claim 68, wherein the number of the second plurality of time slots is selected to be less than the number of the first plurality of time slots if a predetermined number of responses are received by the interrogator in response to the first command.

70. The system of claim 57, wherein the receiver is further to receive a plurality of signals in accordance with the arbitration scheme, each of the plurality of signals indicating a beginning of each of the time slots.

71. A method for tracking a plurality of objects, the method comprising:

attaching each of a plurality of wireless identification devices to a respective one of the plurality of objects, each device storing an identification number to identify the respective object, and each device including a random number generator to generate a random number;

sending a first command to the plurality of wireless identification devices to select a first subset of the plurality of wireless identification devices and to request each wireless identification device of the first subset to respond in a randomly selected one of a first number of time slots in accordance with an arbitration scheme;

sending a second command to the plurality of wireless identification devices to select a second subset of wireless identification devices and to request each wireless identification device of the second subset to respond in a randomly selected one of a second number of time slots in accordance with the arbitration scheme; and

receiving a plurality of replies, each of the plurality of replies including the identification number and a random number for each respective wireless identification device.

72. The method of claim 71, wherein the first and second commands each include a respective value to indicate which of the plurality of wireless identification devices are members of the first subset and which of the plurality of wireless identification devices are members of the second subset.

73. The method of claim 72, further comprising a wireless identification device of the plurality of wireless identification devices receiving the value and comparing the value to a number stored in the wireless identification device to determine if the wireless identification device is a member of any of the first and second subsets.

74. The method of claim 72, wherein the value is selected to indicate that the first subset includes all wireless identification devices receiving the first command.

75. The method of claim 71, wherein the first subset includes the second subset.

76. The method of claim 75, wherein the first subset includes all wireless identification devices receiving the first command, and the second subset includes all wireless identification devices receiving the second command.

77. The method of claim 75, wherein the second subset excludes at least one wireless identification device of the first subset that is identified before the second command is sent.

78. The method of claim 77, further comprising receiving an error-free response from each of the at least one wireless identification device of the first subset in response to the request to each wireless identification device of the first subset before the second command is sent, the error-free response including at least a portion of the identification number of the respective device.

79. The method of claim 71, wherein the random number for each respective wireless identification device of the first subset is sixteen bits long.

80. The method of claim 79, further comprising sending a third command individually addressed to one of the plurality of wireless identification devices by sending a random number independently generated by the one of the plurality of wireless identification devices.

81. The method of claim 71, wherein the second number of time slots is different than the first number of time slots.

82. The method of claim 71, wherein the second number of time slots is selected to be less than the first number of time slots if a threshold number of responses are received in response to the first command.

83. The method of claim 71, further comprising sending a plurality of signals in accordance with the arbitration scheme, each of the plurality of signals indicating a beginning of each of the time slots.

87. The method of claim 71, wherein the first subset is fewer in number than all of the plurality of wireless identification devices.