Method of addressing messages and communications system

• US 8,040,829 B2
• Filed: 09/14/2007
• Issued: 10/18/2011
• Est. Priority Date: 02/19/1998
• Status: Expired due to Fees

• Current Assignee: Round Rock Research LLC
• Original Assignee: Round Rock Research LLC
• Inventors: Wood, Clifton W. Jr.
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US11/855,860
• Publication Number:
  US 20080007412A1
• Time in Patent Office: 1,495 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

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 system for performing radio frequency communications, the system comprising:

a radio frequency identification (RFID) tag attached to one or more items to be tracked, the RFID tag generating a first random number and a second random number, the RFID tag configured to communicate a response including at least one of the first random number and the second random number at a time based at least in part on the second random number upon receipt of a request identifying a subgroup that includes the first random number;

one or more antennas positioned in a first region; and

an interrogator communicatively coupled to the one or more antennas to transmit one or more requests and to receive one or more responses, the interrogator being configured to repeatedly define a subgroup of possible random numbers such that each subgroup is a subset of a previous subgroup and to transmit requests for RFID tags having a random number within the subgroup until the interrogator receives the response from the RFID tag without a collision.

2. The system of claim 1, wherein the request includes a selection indicator, the selection indicator identifying one or more of a plurality of RFID tags, the RFID tag being configured to only communicate the response if the selection indicator matches one or more selection bits stored on the RFID tag.

3. The system of claim 1, wherein the interrogator is configured to utilize a binary search tree to define the subgroup.

4. The system of claim 3, wherein the interrogator is configured to skip one or more levels when a collision is detected.

5. The system of claim 1, wherein the first random number is different than the second random number.

6. The system of claim 1, wherein the second random number is regenerated whenever the subgroup is defined.

7. The system of claim 1, wherein the interrogator is further configured to identify the RFID tag by at least one random number generated by the RFID tag in at least one further communication.

8. The system of claim 1, wherein the RFID tag utilizes an ALOHA scheme to communicate the response.

9. The system of claim 1, wherein the RFID tag includes a battery.

10. A radio frequency identification (RFID) tag comprising:

a substrate;

an antenna on the substrate; and

an integrated circuit operably coupled to the antenna to receive a request, the request including an indication of a subset of possible random numbers, the integrated circuit configured to cause the antenna to communicate a response at a time based at least in part on a first random number generated by the RFID tag, the response including a second random number generated by the RFID tag.

11. The RFID tag of claim 10, wherein the request includes a selection indicator, the selection indicator identifying one or more of a plurality of RFID tags, the integrated circuit being configured to only communicate the response if the selection indicator matches one or more selection bits stored on the RFID tag.

12. The RFID tag of claim 10, wherein the first random number is different than the second random number.

13. The RFID tag of claim 10, wherein the first random number is regenerated for each new subset.

14. The RFID tag of claim 10, wherein the integrated circuit is further configured to receive and respond to at least one additional command that identifies the RFID tag by at least one of the first random number and the second random number.

15. The RFID tag of claim 10, wherein the integrated circuit is configured to utilize an ALOHA scheme to communicate the response.

16. The RFID tag of claim 10, further comprising a battery electrically coupled to the integrated circuit.

17. An interrogator comprising:

one or more antennas;

a receiver communicatively coupled to at least one of the one or more antennas to receive a response from a radio frequency identification (RFID) tag, the response including at least a first random number generated by the RFID tag;

a transmitter communicatively coupled to at least one of the one or more antennas to transmit requests, one or more of the requests including an indication of a subgroup of possible random numbers; and

a control unit communicatively coupled to the transmitter and the receiver, the control unit configured to repeatedly determine the subgroup for a first request such that the subgroup includes a smaller number of possible random numbers than a previous subgroup and cause the transmitter to transmit the first request until the control unit receives the response without a collision occurring between a plurality of responding RFID tags, wherein the receiver is configured to receive the response at a time based at least in part on a second random number generated by the RFID tag after the transmitter transmits the first request.

18. The interrogator of claim 17, wherein the first request includes a selection indicator, the selection indicator identifying one or more of a plurality of RFID tags from which a response is being requested.

19. The interrogator of claim 17, wherein the control unit is further configured to utilize a binary search tree to determine the subgroup.

20. The interrogator of claim 19, wherein the control unit is further configured to skip one or more intermediate levels in the binary search tree.

21. The interrogator of claim 17, wherein the first random number is different than the second random number.

22. The interrogator of claim 17, wherein the time based at least in part on the second random number varies each time the subgroup is defined.

23. The interrogator of claim 17, wherein the interrogator is configured to cause the transmitter to transmit at least one message after receiving the response without a collision, the at least one message including at least one of the first random number and the second random number to identify a responding RFID tag.

24. A method for performing radio frequency communications, the method comprising:

receiving a request, said request including a defined subgroup of possible numbers;

generating a first random number and a second random number; and

communicating a response including at least one of the first random number and the second random number at a time based at least in part on the second random number upon receipt of a request identifying the defined subgroup.

25. The method of claim 24, further comprising utilizing a binary search tree to define the subgroup.

26. The method of claim 24, wherein the first random number is different than the second random number.

27. The method of claim 24, wherein the second random number is regenerated whenever the subgroup is defined.

28. A radio frequency device comprising:

an integrated circuit coupled to an antenna so as to receive a request, the request including an indication of a subset of possible numbers, the integrated circuit configured to cause the antenna to communicate a response at a time based at least in part on a first random number generated by the radio frequency device, the response including a second random number generated by the radio frequency device.

29. The radio frequency device of claim 28, wherein the first random number is different than the second random number.

30. The radio frequency device of claim 28, wherein the first random number is regenerated for each new subset.

31. An interrogation apparatus, comprising:

one or more antennas;

a receiver communicatively coupled to at least one of the one or more antennas to receive a response from a radio frequency device, the response including at least a first random number generated by the radio frequency device;

a transmitter communicatively coupled to at least one of the one or more antennas to transmit requests, one or more of the requests including an indication of a subgroup of possible numbers; and

a control unit communicatively coupled to the transmitter and the receiver, the control unit configured to repeatedly determine the subgroup for a first request such that the subgroup includes a smaller number of possible numbers than a previous subgroup, and cause the transmitter to transmit the first request until the control unit receives the response without a collision occurring between a plurality of responding radio frequency devices;

wherein the receiver is configured to receive the response at a time based at least in part on a second random number generated by the radio frequency device after the transmitter transmits the first request.

32. The interrogation apparatus of claim 31, wherein the control unit is further configured to skip one or more intermediate levels in a binary search tree.

33. The interrogation apparatus of claim 31, wherein the first random number is different than the second random number.

34. The interrogation apparatus of claim 31, wherein the time based at least in part on the second random number varies each time the subgroup is defined.

35. The interrogation apparatus of claim 31, wherein the interrogator is configured to cause the transmitter to transmit at least one message after receiving the response without a collision, the at least one message including at least one of the first random number and the second random number to identify a responding radio frequency device.

36. A method for performing radio frequency communications, the method comprising:

a step for receiving a request including a defined subgroup of possible numbers;

a step for generating a first random number and a second random number; and

a step for communicating a response including at least one of the first random number and the second random number at a time based at least in part on the second random number upon receipt of a request identifying the defined subgroup.

37. The method of claim 36, further comprising a step for utilizing a binary search tree to define the subgroup.

38. The method of claim 37, wherein the first random number is different than the second random number.

39. An interrogation apparatus, comprising:

an antenna;

means for receiving a response from a radio frequency device via the antenna, the response including at least a first random number generated by the radio frequency device;

means for transmitting requests via the antenna, one or more of the requests including an indication of a subgroup of possible numbers; and

control logic communicatively coupled to the transmitter and the receiver, the control logic configured to repeatedly determine the subgroup for a first request such that the subgroup includes a smaller number of possible numbers than a previous subgroup, and cause the means for transmitting to transmit the first request until the control logic receives the response without a collision occurring between a plurality of responding radio frequency devices;

wherein the means for receiving is configured to receive the response at a time based at least in part on a second random number generated by the radio frequency device after the means for transmitting transmits the first request.

40. The interrogation apparatus of claim 39, wherein:

the control logic is further configured to skip one or more intermediate levels in a binary search tree, and

the first random number is different than the second random number.