Method of addressing messages and communications system

• US 20060056325A1
• Filed: 11/08/2005
• Published: 03/16/2006
• Est. Priority Date: 02/19/1998
• Status: Active Grant

• Current Assignee: Round Rock Research LLC
• Original Assignee: Round Rock Research LLC
• Inventors: Wood, Clifton W. Jr.
• Granted Patent: US 7,672,260 B2
• Time in Patent Office: Days
• 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

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. 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.

2. The method of claim 1, further comprising the step of 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 the step of 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 the step of 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 the step of 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 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.

13. The device of claim 12, 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.

14. The device of claim 12, 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.

15. The device of claim 12, wherein the response excludes the first portion of the identification number.

16. The device of claim 12, 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.

17. 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.

18. 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.