Methods and apparatuses to identify devices

• US 7,716,160 B2
• Filed: 11/05/2004
• Issued: 05/11/2010
• 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.
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Rostami; Mohammad S
• Application Number:
  US10/982,557
• Publication Number:
  US 20050114326A1
• Time in Patent Office: 2,013 Days
• Field of Search: 340/10.2, 709/237
• US Class Current: 340/10.2
• 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 through an antenna, one or more first query commands, a first query command of the one or more first query commands including a first value of a probability parameter, the first value of the probability parameter indicating a first level of probability of reply according to which each of the plurality of Tags randomly determines whether or not to reply with handshaking data which comprises a random number, wherein the first value of the probability parameter includes a first number Q, and the probability of reply for one of the plurality of tags includes a second number p based on the first number Q; and

detecting a reply in response to the first query command, the reply including the handshaking data comprising the random number generated in response to the first query command, wherein the first query command further includes a state fin 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;

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, wherein the first and second query commands arc symmetric with respect to the first and second states.

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 level of probability of reply which is greater than the first level of 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 parameters the second value of the probability parameter indicating a second level of probability of reply which is less than the first level of probability of reply.

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

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

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

7. The method of claim 1, further comprising:

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

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

8. The method of claim 7, further comprising:

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

9. The method of claim 1, further comprising:

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

10. The method of claim 9, 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.

11. The method of claim 10, wherein the second query command is shorter than the first query command.

12. The method of claim 1, further comprising frequency hopping by a reader.

13. The method of claim 12, wherein the reader comprises an Ethernet network interface.

14. The method of claim 12, wherein the reader comprises first and second antennas.

15. The method of claim 1, wherein the Tag comprises a single antenna.

16. The method of claim 1, wherein the Tag is passive, backscatter transponder.

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

receiving, through an antenna from the Reader a first query command including a first value of a probability parameter that indicates a first level of probability of reply;

deciding randomly whether or not to reply to the first query command according to the first value of the probability parameter, wherein the first value of the probability parameter includes a first number Q, and the probability of reply includes a second number p based on the first number Q; and

sending, responsive to a random decision to reply, a reply with handshaking data which comprises a random number generated in response to the first query command, wherein the first query command further includes a state flag indicating a first slate, 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;

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 the level of 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, wherein the Tag processes the first and second query commands with symmetry with respect to the first and second states.

18. The method of claim 17, wherein the Tag comprises a single integrated circuit which includes all necessary logic of the Tag, excluding an antenna.

19. The method of claim 18, wherein the random number is generated in response to the first query command and wherein the Tag comprises a persistent node.

20. The method of claim 17, wherein the first number Q is an integer, the first level of probability of reply is equal to p^Q, and p is less than 1.

21. The method of claim 20, wherein p is equal to 0.5.

22. The method of claim 17, further comprising:

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

23. The method of claim 22, 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.

24. The method of claim 17, 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 level of probability of reply is determined by the first value of the probability parameter.

25. The method of claim 24, 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.

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

27. The method of claim 17, wherein the Tag comprises a single antenna.

28. The method of claim 17, wherein the Tag is a passive, backscatter transponder.

29. The method of claim 17, wherein the antenna of the tag receives different frequencies the Reader performs frequency hopping.

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

means for broadcasting one or more first query commands, a first query command of the one or more first query commands including a first value of a probability parameter, the first value of the probability parameter indicating a first level of probability of reply according to which each of the plurality of Tags randomly determines whether or not to reply with handshaking data which comprises a random number, wherein the first value of the probability parameter includes a first number Q, and the probability of reply for one of the plurality of tags includes a second number p based on the first number Q; and

means for detecting a reply in response to the first query command, the reply including the handshaking data comprising the random number generated in response to the first query command, wherein the first tier 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;

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 tier command, wherein the first and second query commands are symmetric with respect to the first and second states.

31. The Reader of claim 30, 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 level of probability of reply which is greater than the first level of probability of reply.

32. The Reader of claim 30, 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 level of probability of reply which is less than the first level of probability of reply.

33. The Reader of claim 30, wherein the first number Q is an integer, the first level of probability of reply for one of the plurality of Tags is equal to p^Q, and p is less than 1.

34. The Reader of claim 33, wherein p is equal to 0.5.

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

36. The Reader of claim 30, further comprising:

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

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

37. The Reader of claim 36, 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.

38. The Reader of claim 30, further comprising:

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

39. The Reader of claim 38, 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.

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

41. The Reader of claim 30, wherein the Reader performs frequency hopping.

42. The Reader of claim 30, wherein the Reader comprises an Ethernet network interface.

43. The Reader of claim 30, wherein the Reader comprises first and second antennas.

44. 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 that indicates a level of probability of reply;

means for deciding randomly whether or not to reply to the first query command according to the first value of the probability parameter, wherein the first value of the probability parameter includes a first number Q, and the probability of reply includes a second number p based on the first number Q; and

means for sending, responsive to a random decision to reply, a reply with handshaking data which comprises a random number generated in response to the first query command, 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;

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

means for deciding randomly whether or not to reply to the second query command, wherein a level of 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, wherein the Tag processes the first and second query commands with symmetry with respect to the first and second states.

45. The Tag of claim 44, wherein the Tag comprises a single integrated circuit which includes all necessary logic of the Tag, excluding the antenna.

46. The Tag of claim 45, wherein the random number is generated in response to the first query command and wherein the Tag comprises a persistent node.

47. The Tag of claim 44, wherein the first number Q is an integer, the first level of probability of reply for one of the plurality of Tags is equal to p^Q, and p is less than 1.

48. The Tag of claim 47, wherein p is equal to 0.5.

49. The Tag of claim 44, further comprising:

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

50. The Tag of claim 49, 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.

51. The Tag of claim 44, 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 level of probability of reply is determined by the first value of the probability parameter.

52. The Tag of claim 51, 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.

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

54. A machine readable storage medium storing 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, a first query command of the one or more first query commands including a first value of a probability parameter, the first value of the probability parameter indicating a first level of probability of reply according to which each of the plurality of Tags randomly determines whether or not to reply with handshaking data which comprises a random number, wherein the first value of the probability parameter includes a first number Q, and the probability of reply for one of the plurality of tags includes a second number p based on the first number Q; and

detecting a reply in response to the first query command, the reply including the handshaking data comprising the random number generated in response to the first query command, wherein the first query command further includes a slate 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, 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, wherein the first and second query commands arc symmetric with respect to the first and second states.

55. The medium of claim 54, 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 level of probability of reply which is greater than the first level of probability of reply.

56. The medium of claim 54, 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 level of probability of reply which is less than the first level of probability of reply.

57. The medium of claim 54, wherein the first number Q is an integer, the first level of probability of reply for one of the plurality of Tags is equal to p^Q, and p is less than 1.

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

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

60. The medium of claim 54, wherein the method further comprises:

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

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

61. The medium of claim 60, 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.

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

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

63. The medium of claim 62, 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.

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

65. The method of claim 54, wherein the system includes a reader performing frequency hopping.

66. The method of claim 54, wherein the system includes a reader that comprises an Ethernet network interface.