Method of addressing messages and communications system

• US 20060209781A1
• Filed: 05/02/2006
• Published: 09/21/2006
• Est. Priority Date: 02/19/1998
• Status: Active Grant

• Current Assignee: Round Rock Research LLC
• Original Assignee: Micron Technology, Inc.
• Inventors: Wood, Clifton W. Jr.
• Granted Patent: US 7,639,638 B2
• Time in Patent Office: Days
• US Class Current: 370/347
• 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

A method of establishing wireless communications between an interrogator and individual ones of multiple wireless identification devices, the method comprising combining tree search and Aloha methods to establish communications between the interrogator and individual ones of the multiple wireless identification devices without collision. A system comprising an interrogator, and a plurality of wireless identification devices configured to communicate with the interrogator in a wireless fashion, the respective wireless identification devices having a unique identification number, the interrogator being configured to employ tree search and Aloha techniques to determine the unique identification numbers of the different wireless identification devices so as to be able to establish communications between the interrogator and individual ones of the multiple wireless identification devices without collision by multiple wireless identification devices attempting to respond to the interrogator at the same time.

Claims

1-40. -40. (canceled)

41. A method comprising:

sending a first command 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; and

sending a second command 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.

42. The method of claim 41, 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.

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

44. The method of claim 41, 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.

45. The method of claim 44, 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.

46. The method of claim 41, 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.

47. The method of claim 46, wherein the mask indicates a bit length of the value.

48. The method of claim 47, 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.

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

50. The method of claim 41, 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.

51. The method of claim 41, 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.

52. A method comprising:

sending a first command 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 Aloha scheme; and

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 an independently selected one of a second number of time slots in accordance with the adaptive Aloha scheme.

53. The method of claim 52, 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.

54. The method of claim 53, 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.

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

56. The method of claim 52, wherein the first subset includes the second subset.

57. The method of claim 56, wherein the first subset includes all wireless identification devices capable of communicating and participating in the adaptive Aloha scheme when the first command is sent, and the second subset includes all wireless identification devices capable of communicating and participating in the adaptive Aloha scheme when the second command is sent.

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

59. The method of claim 58, 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.

60. The method of claim 52, 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.

61. The method of claim 60, wherein the respective values are each randomly generated.

62. The method of claim 60, wherein the respective values are each four bits long.

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

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

65. The method of claim 52, 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 without collision.

66. The method of claim 65, 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 without collision in response to the first command.

67. The method of claim 52, further comprising sending a plurality of signals in accordance with the adaptive Aloha scheme, each of the plurality of signals indicating a beginning of each of the time slots.

68. The method of claim 52, 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.

69. A wireless identification device comprising:

a receiver operable 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 operable to store a unique identification number; and

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

70. The device of claim 69, wherein the first and second responses are to include a four bit number independently generated by the wireless identification device in addition to the unique identification number, the four bit number to be used to individually address the wireless identification device.

71. The device of claim 69, wherein the backscatter transmitter is to time transmission of the first and second responses using synchronization pulses to be received by the receiver in accordance with the adaptive Aloha scheme.

72. The device of claim 69, 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.

73. A method comprising the steps of:

sending a first command 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; and

sending a second command 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.

74. A wireless identification device comprising:

a receiver to receive a first command comprising a first mask and a first value associated with a search tree of a tree search scheme, the first mask indicating a bit length of the first value;

a memory to store an identification number, a first portion of the identification number to be selected using the first mask and to be compared to the first value in response to receiving the first command in accordance with the tree search scheme; and

a backscatter transmitter to transmit a first response in an independently selected one of a plurality of time slots in accordance with an Aloha scheme if it is determined that the first portion of the identification number is equal to the first value.

75. The device of claim 74, wherein the receiver is to receive a second command comprising a second mask of “

0” and

the backscatter transmitter is to transmit a second response in the independently selected one of the plurality of time slots regardless of the identification number.

76. The device of claim 74, wherein:

the receiver is to further receive a second command comprising a second mask and a second value associated with the search tree of the tree search scheme, the second mask indicating a bit length of the second value;

a second portion of the identification number is to be selected using the second mask and is to be compared to the second value in response to receiving the second command in accordance with the tree search scheme; and

the backscatter transmitter is to further transmit a second response, without delay, in accordance with the tree search scheme if it is determined that the second portion of the identification number is equal to the second value.

77. The device of claim 74, wherein the response excludes the first portion of the identification number.

78. The device of claim 74, wherein the backscatter transmitter is to time transmission of the first response using synchronization pulses to be received by the receiver in accordance with the Aloha scheme.

79. An interrogator comprising:

a transmitter circuit operable to send a command comprising a mask and a value to a plurality of RFID devices to select a subset of the RFID devices associated with a branch of a search tree in accordance with a tree search scheme, the mask indicating a bit length of the value, the transmitter further operable to send coordination pulses to delimit a plurality of time slots during which the subset of the RFID devices are to respond in accordance with an Aloha scheme;

a receiver circuit operable to receive a plurality of backscatter responses from the subset of the RFID devices; and

a collision detection circuit operable to determine if there is a collision in the plurality of responses, the transmitter further operable to send an acknowledgement signal if a response is received without collision.

80. A system comprising:

an interrogator to send a command to select a subset of a plurality of RFID devices and to provide coordination pulses to delimit time slots associated with an adaptive Aloha scheme; and

an RFID device affixed to an object to identify the object, the RFID device, responsive to the interrogator, to send an independently generated number along with a unique identification number in accordance with the adaptive Aloha scheme if the RFID device determines that the RFID device is a member of the subset, the interrogator to individually address the RFID device using the independently generated number.