Methods and apparatuses to identify devices

• US 20050114326A1
• Filed: 11/05/2004
• Published: 05/26/2005
• Est. Priority Date: 11/07/2003
• Status: Active Grant

• Current Assignee: RUIZHANG TECHNOLOGY LIMITED COMPANY
• Original Assignee: Alien Technology Corporation
• Inventors: Smith, John Stephen, Carrender, Curtis L.
• Granted Patent: US 7,716,160 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/10009 sensing by radiation using wavelengths larger than 0.1 mm, e.g. radio-waves or microwaves
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Embodiments of the present invention include systems with Readers and Tags in which a Reader queries the Tags with a parameter that includes a level of probability of reply according to which the Tags individually and randomly decide whether or not to reply. In one embodiment, the Tags can switch between two states: A and B. The query command also specifies a state (A or B) so that only the Tags in the specified state can reply. After successfully sending the Tag identification data from a Tag to the Reader, the Tag switches to the other state from the specified state. In one embodiment, the operations about the two states are symmetric. In one embodiment, the Tags can remember the parameters used in a query so that a short form of query command can be used to repeat the query with the same query parameters.

Claims

1. A method to query a plurality of Tags, the method comprising:

broadcasting one or more first query commands including a first value of a probability parameter, the first value of the probability parameter indicating a first probability of reply, wherein each of the plurality of Tags randomly determines whether or not to reply; and

detecting a reply in response to the first query command.

2. The method of claim 1, further comprising:

broadcasting, responsive to a determination that there is no reply to the one or more first query commands, a second query command including a second value of the probability parameter, the second value of the probability parameter indicating a second probability of reply which is greater than the first probability of reply.

3. The method of claim 1, further comprising:

broadcasting, responsive to a determination that there is no legible reply to the one or more first query commands, a second query command including a second value of the probability parameter, the second value of the probability parameter indicating a second probability of reply which is less than the first probability of reply.

4. The method of claim 1, wherein the first value of the probability parameter is an integer Q, the first probability of reply for one of the plurality of Tags is substantially equal to p^Q, and p is less than 1.

5. The method of claim 4, wherein p is substantially equal to 0.5.

6. The method of claim 1, wherein the first probability of reply for a first one of the plurality of Tags is different from the first probability of reply for a second one of the plurality of Tags.

7. The method of claim 1, wherein the first query command further includes a state flag indicating a first state, wherein Tags in a second state do not reply to the first query command and Tags in the first state reply to the first query command randomly according to the first value of the probability parameter.

8. The method of claim 7, further comprising:

broadcasting a second query command including a second value of the probability parameter and a state flag indicating the second state, wherein Tags in the first state do not reply to the second query command and Tags in the second state reply to the second query command randomly according to the second value of the probability parameter; and

detecting a reply in response to the second query command.

9. The method of claim 8, wherein the first and second query commands are symmetric with respect to the first and second states.

10. The method of claim 7, further comprising:

sending, responsive to a legible reply to the first query command, wherein the legible reply includes first handshaking data, a second command including the first handshaking data; and

receiving Tag identification data as a reply to the second command.

11. The method of claim 10, further comprising:

sending a command to indicate an error in receiving the Tag identification data when the Tag identification data is not received successfully.

12. The method of claim 1, further comprising:

broadcasting a second query command without including a value of the probability parameter.

13. The method of claim 12, wherein

the first query command includes first values of a plurality of parameters including the first value of the probability parameter;

and

the second query command does not include values of the plurality of parameters.

14. The method of claim 13, wherein the second query command is substantially shorter than the first query command.

15. A method for a Tag to respond to queries from a Reader, the method comprising:

receiving from the Reader a first query command including a first value of a probability parameter; and

deciding randomly whether or not to reply to the first query command, wherein a probability of reply is determined by the first value of the probability parameter.

16. The method of claim 15, further comprising:

sending, responsive to a random decision to reply, a reply with first handshaking data.

17. The method of claim 16, wherein the first handshaking data is a random number generated in response to the first query command.

18. The method of claim 15, wherein the first value of the probability parameter is an integer Q, the first probability of reply is substantially equal to p^Q, and p is less than 1.

19. The method of claim 18, wherein p is substantially equal to 0.5.

20. The method of claim 15, wherein the first query command further includes a state flag indicating a first state, and wherein the Tag does not reply to the first query command if the Tag is in a second state, and the Tag replies to the first query command randomly according to the first value of the probability parameter if the Tag is in the first state.

21. The method of claim 20, further comprising:

receiving a second query command including a second value of the probability parameter and a state flag indicating the second state; and

deciding randomly whether or not to reply to the second query command, wherein a probability of reply is determined by the second value of the probability parameter if the Tag is in the second state, and wherein the Tag does not reply to the second query command if the Tag is in the first state.

22. The method of claim 21, wherein the Tag processes the first and second query commands with symmetry with respect to the first and second states.

23. The method of claim 20, further comprising:

sending, responsive to a random decision to reply, a first reply with first handshaking data; and

sending, responsive to receiving from the Reader a second command including the first handshaking data, a second reply with Tag identification data.

24. The method of claim 23, further comprising:

switching, responsive to receiving a query command after sending the second reply, from the first state to the second state, wherein after receiving a command indicating an error in receiving the Tag identification data at the Reader, the Tag remains in the first state if a query command is received after the command indicating the error.

25. The method of claim 15, further comprising:

receiving a second query command which does not include a value of the probability parameter; and

deciding randomly whether or not to reply to the second query command, wherein a probability of reply is determined by the first value of the probability parameter.

26. The method of claim 25, wherein

the first query command includes first values of a plurality of parameters including the first value of the probability parameter;

the second query command does not include values of the plurality of parameters; and

the Tag processes the second query command according to the first values of the plurality of parameters.

27. The method of claim 26, wherein the second query command is substantially shorter than the first query command.

94. The method of claim 18, wherein p is substantially equal to 0.5.

28. A Reader to query a plurality of Tags, the Reader comprising:

means for broadcasting one or more first query commands including a first value of a probability parameter, the first value of the probability parameter indicating a first probability of reply, wherein each of the plurality of Tags randomly determines whether or not to reply; and

means for detecting a reply in response to the first query command.

29. The Reader of claim 28, further comprising:

means for broadcasting, responsive to a determination that there is no reply to the one or more first query commands, a second query command including a second value of the probability parameter, the second value of the probability parameter indicating a second probability of reply which is greater than the first probability of reply.

30. The Reader of claim 28, further comprising:

means for broadcasting, responsive to a determination that there is no legible reply to the one or more first query commands, a second query command with a second value of the probability parameter, the second value of the probability parameter indicating a second probability of reply which is less than the first probability of reply.

31. The Reader of claim 28, wherein the first value of the probability parameter is an integer Q, the first probability of reply for one of the plurality of Tags is substantially equal to p^Q, and p is less than 1.

32. The Reader of claim 31, wherein p is substantially equal to 0.5.

33. The Reader of claim 28, wherein the first probability of reply for a first one of the plurality of Tags is different from the first probability of reply for a second one of the plurality of Tags.

34. The Reader of claim 28, wherein the first query command further includes a state flag indicating a first state, wherein Tags in a second state do not reply to the first query command and Tags in the first state reply to the first query command randomly according to the first value of the probability parameter.

35. The Reader of claim 34, further comprising:

means for broadcasting a second query command including a second value of the probability parameter and a state flag indicating the second state, wherein Tags in the first state do not reply to the second query command and Tags in the second state reply to the second query command randomly according to the second value of the probability parameter; and

means for detecting a reply in response to the second query command.

36. The Reader of claim 35, wherein the first and second query commands are symmetric with respect to the first and second states.

37. The Reader of claim 34, further comprising:

means for sending, responsive to a legible reply to the first query command, wherein the legible reply includes first handshaking data, a second command including the first handshaking data; and

means for receiving Tag identification data as a reply to the second command.

38. The Reader of claim 37, further comprising:

means for sending a command to indicate an error in receiving the Tag identification data when the Tag identification data is not received successfully.

39. The Reader of claim 28, further comprising:

means for broadcasting a second query command without including a value of the probability parameter.

40. The Reader of claim 39, wherein

the first query command includes first values of a plurality of parameters including the first value of the probability parameter;

and

the second query command does not include values of the plurality of parameters.

41. The Reader of claim 40, wherein the second query command is substantially shorter than the first query command.

42. A Tag responsive to queries from a Reader, the Tag comprising:

means for receiving from the Reader a first query command including a first value of a probability parameter; and

means for deciding randomly whether or not to reply to the first query command, wherein a probability of reply is determined by the first value of the probability parameter.

43. The Tag of claim 42, further comprising:

means for sending, responsive to a random decision to reply, a reply with first handshaking data.

44. The Tag of claim 43, wherein the first handshaking data is a random number generated in response to the first query command.

45. The Tag of claim 42, wherein the first value of the probability parameter is an integer Q, the first probability of reply for one of the plurality of Tags is substantially equal to p^Q, and p is less than 1.

46. The Tag of claim 45, wherein p is substantially equal to 0.5.

47. The Tag of claim 42, wherein the first query command further includes a state flag indicating a first state, and wherein the Tag do not reply to the first query command if the Tag is in a second state, and the Tag replies to the first query command randomly according to the first value of the probability parameter if the Tag is in the first state.

48. The Tag of claim 47, further comprising:

means for receiving a second query command including a second value of the probability parameter and a state flag indicating the second state; and

means for deciding randomly whether or not to reply to the second query command, wherein a probability of reply is determined by the second value of the probability parameter if the Tag is in the second state, and wherein the Tag does not reply to the second query command if the Tag is in the first state.

49. The Tag of claim 48, wherein the Tag processes the first and second query commands with symmetry with respect to the first and second states.

50. The Tag of claim 47, further comprising:

means for sending, responsive to a random decision to reply, a first reply with first handshaking data; and

means for sending, responsive to receiving from the Reader a second command including the first handshake data, a second reply with Tag identification data.

51. The Tag of claim 50, further comprising:

means for switching, responsive to receiving a query command after sending the second reply, from the first state to the second state, wherein after receiving a command indicating an error in receiving the Tag identification data at the Reader, the Tag remains in the first state if a query command is received after the command indicating the error.

52. The Tag of claim 42, further comprising:

means for receiving a second query command which does not include a value of the probability parameter; and

means for deciding randomly whether or not to reply to the second query command, wherein a probability of reply is determined by the first value of the probability parameter.

53. The Tag of claim 52, wherein

the first query command includes first values of a plurality of parameters including the first value of the probability parameter;

the second query command does not include values of the plurality of parameters; and

the Tag processes the second query command according to the first values of the plurality of parameters.

54. The Tag of claim 53, wherein the second query command is substantially shorter than the first query command.

55. A machine readable medium containing instructions which when executed on a data processing system causes the system to perform a method to query a plurality of Tags, the method comprising:

broadcasting one or more first query commands including a first value of a probability parameter, the first value of the probability parameter indicating a first probability of reply, wherein each of the plurality of Tags randomly determines whether or not to reply; and

detecting a reply in response to the first query command.

56. The medium of claim 55, wherein the method further comprises:

broadcasting, responsive to a determination that there is no reply to the one or more first query commands, a second query command including a second value of the probability parameter, the second value of the probability parameter indicating a second probability of reply which is greater than the first probability of reply.

57. The medium of claim 55, wherein the method further comprises:

broadcasting, responsive to a determination that there is no legible reply to the one or more first query commands, a second query command with a second value of the probability parameter, the second value of the probability parameter indicating a second probability of reply which is less than the first probability of reply.

58. The medium of claim 55, wherein the first value of the probability parameter is an integer Q, the first probability of reply for one of the plurality of Tags is substantially equal to p^Q, and p is less than 1.

59. The medium of claim 58, wherein p is substantially equal to 0.5.

60. The medium of claim 55, wherein the first probability of reply for a first one of the plurality of Tags is different from the first probability of reply for a second one of the plurality of Tags.

61. The medium of claim 55, wherein the first query command further includes a state flag indicating a first state, wherein Tags in a second state do not reply to the first query command and Tags in the first state reply to the first query command randomly according to the first value of the probability parameter.

62. The medium of claim 61, wherein the method further comprises:

broadcasting a second query command including a second value of the probability parameter and a state flag indicating the second state, wherein Tags in the first state do not reply to the second query command and Tags in the second state reply to the second query command randomly according to the second value of the probability parameter; and

detecting a reply in response to the second query command.

63. The medium of claim 62, wherein the first and second query commands are symmetric with respect to the first and second states.

64. The medium of claim 61, wherein the method further comprises:

sending, responsive to a legible reply to the first query command, wherein the legible reply includes first handshaking data, a second command including the first handshaking data; and

receiving Tag identification data as a reply to the second command.

65. The medium of claim 64, wherein the method further comprises:

sending a command to indicate an error in receiving the Tag identification data when the identification Tag identification data is not received successfully.

66. The medium of claim 55, wherein the method further comprises:

broadcasting a second query command without including a value of the probability parameter.

67. The medium of claim 66, wherein

the first query command includes first values of a plurality of parameters including the first value of the probability parameter;

and

the second query command does not include values of the plurality of parameters.

68. The medium of claim 67, wherein the second query command is substantially shorter than the first query command.

69. A Tag responsive to queries from a Reader, the Tag comprising:

an antenna;

an Integrated Circuit (IC) coupled to the antenna to;

receive from the Reader a first query command with a first value of a probability parameter; and

decide randomly whether or not to reply to the first query command, wherein a probability of reply is determined by the first value of the probability parameter.

70. The Tag of claim 69, the IC coupled to the antenna further to send, responsive to a random decision to reply, a reply with first handshaking data.

71. The Tag of claim 70, wherein the first handshaking data is a random number generated in response to the first query command.

72. The Tag of claim 69, wherein the first value of the probability parameter is an integer Q, the first probability of reply for one of the plurality of Tags is substantially equal to p^Q, and p is less than 1.

73. The Tag of claim 72, wherein p is substantially equal to 0.5.

74. The Tag of claim 69, wherein the first query command further includes a state flag indicating a first state, wherein the Tag does not reply to the first query command if the Tag is in a second state, and the Tag replies to the first query command randomly according to the first value of the probability parameter if the Tag is in the first state.

75. The Tag of claim 74, the IC coupled to the antenna further to:

receive a second query command including a second value of the probability parameter and a state flag indicating the second state; and

decide randomly whether or not to reply to the second query command, wherein a probability of reply is according to the second value of the probability parameter if the Tag is in the second state, and wherein the Tag does not reply to the second query command if in the first state.

76. The Tag of claim 75, wherein the Tag processes the first and second query commands with symmetry with respect to the first and second states.

77. The Tag of claim 74, the IC coupled to the antenna further to:

send, responsive to a random decision to reply, a first reply with first handshaking data; and

send, responsive to receiving from the Reader a second command including the first handshake data, a second reply with Tag identification data.

78. The Tag of claim 77, the IC coupled to the antenna further to switch, responsive to receiving a query command after sending the second reply, from the first state to the second state, wherein after receiving a command indicating an error in receiving the Tag identification data at the Reader, the Tag remains in the first state if a query command is received after the command indicating the error.

79. The Tag of claim 69, the IC coupled to the antenna further to:

receive a second query command which does not include a value of the probability parameter; and

decide randomly whether or not to reply to the second query command, wherein a probability of reply is determined by the first value of the probability parameter.

80. The Tag of claim 79, wherein

the first query command includes first values of a plurality of parameters including the first value of the probability parameter;

the second query command does not include values of the plurality of parameters; and

the Tag processes the second query command according to the first values of the plurality of parameters.

81. The Tag of claim 80, wherein the second query command is substantially shorter than the first query command.

82. An apparatus to query a plurality of Tags, comprising:

an antenna; and

a Reader, comprising;

a receiver coupled to the antenna;

a transmitter coupled to the antenna;

a processor coupled to the receiver, the transmitter and a memory, the processor to control the transmitter and the receiver,

the Reader to broadcast one or more first query commands including a first value of a probability parameter, the first value of the probability parameter indicating a first probability of reply, wherein each of the plurality of Tags randomly determines whether or not to reply, and

the Reader further to detect a reply in response to the first query command.

83. The apparatus of claim 82, the Reader further to broadcast, responsive to a determination that there is no reply to the one or more first query commands, a second query command including a second value of the probability parameter, the second value of the probability parameter indicating a second probability of reply which is greater than the first probability of reply.

84. The apparatus of claim 82, the Reader further to broadcast, responsive to a determination that there is no legible reply to the one or more first query commands, a second query command including a second value of the probability parameter, the second value of the probability parameter indicating a second probability of reply which is less than the first probability of reply.

85. The apparatus of claim 82, wherein the first value of the probability parameter is an integer Q, the first probability of reply for one of the plurality of Tags is substantially equal to p^Q, and p is less than 1.

86. The apparatus of claim 82, wherein p is substantially equal to 0.5.

87. The apparatus of claim 82, wherein the first probability of reply for a first one of the plurality of Tags is different from the first probability of reply for a second one of the plurality of Tags.

88. The apparatus of claim 82, wherein the first query command further includes a state flag indicating a first state, wherein Tags in a second state do not reply to the first query command and Tags in the first state reply to the first query command randomly according to the first value of the probability parameter.

89. The apparatus of claim 88, the Reader further to broadcast a second query command including a second value of the probability parameter and a state flag indicating the second state, wherein Tags in the first state do not reply to the second query command and Tags in the second state reply to the second query command randomly according to the second value of the probability parameter, the Reader further to detect a reply in response to the second query command.

90. A machine readable medium containing instructions which when executed on a data processing system causes the system to perform a method to respond to queries from a Reader, the method comprising:

receiving from the Reader a first query command including a first value of a probability parameter; and

deciding randomly whether or not to reply to the first query command, wherein a probability of reply is determined by the first value of the probability parameter.

91. The method of claim 90, further comprising:

sending, responsive to a random decision to reply, a reply with first handshaking data.

92. The method of claim 91, wherein the first handshaking data is a random number generated in response to the first query command.

93. The method of claim 90, wherein the first value of the probability parameter is an integer Q, the first probability of reply is substantially equal to p^Q, and p is less than 1.