Method of communicating in a radio frequency identification system using aloha networks

• US 20080180222A1
• Filed: 01/26/2007
• Published: 07/31/2008
• Est. Priority Date: 01/26/2007
• Status: Active Grant

• Current Assignee: RF Accelerated LLC
• Original Assignee: RF Accelerated LLC
• Inventors: Hollister, Allen, Armstrong, John T., Barta, Gary
• Granted Patent: US 10,063,515 B2
• Time in Patent Office: Days
• US Class Current: 340/10.3
• CPC Class Codes: H04L 61/5046 Resolving address allocation conflicts; Testing of addresses testing when self-assigning an address H04L61/5092
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks

Abstract

A method is presented for taking an unknown field of transponders and converting them to a slotted Aloha architecture and increasing the throughput allowed by the slotted Aloha architecture by using several different techniques including shortening the time of empty and collided timeslots, implementing a unique random number generator that creates random numbers that are uniquely based on an individual tags location, and on an ability to estimate the total number of transponders and control the offered rate such that throughput is always maximum. While these techniques work well together and produce the most benefit when used together, they are independent techniques and any one may be used alone without the others. Thus a system might use the estimated total number of transponders technique and the timeslot shortening technique, but use a standard random number generator rather one based on transponder location with only a small decrease in overall performance.

Claims

1. A method of estimating a total number of RFID Tags in an unknown RFID Tag Field using an interrogator/reader, comprising:

(a) storing a predefined random number within each individual RFID Tag wherein said predefined random number is scaled between 1 and a “

Number” and

each individual RFID Tag having an internal counter for incrementing a number and each defines a timeslot;

(b) estimating the total number of RFID tags in the unknown RFID Tag Field by sending a first “

Number”

generated by the interrogator/reader to the RFID Tag Field wherein each individual RFID Tag uses said “

Number”

to dimension a space of numbers from which each individual RFID Tag randomly chooses one of said numbers from said space of numbers and stores said chosen random number;

(c) sending a series of read commands from the reader/interrogator to the RFID Tag Field until a Preselected Number of successful tag reads have occurred wherein with each associated read command said internal counter is incremented and compared against said random number for each individual RFID Tag wherein each individual RFID Tag will not attempt to communicate to the interrogator/reader unless said incremented internal counter has a number with a Predefined Relationship to said chosen random number; and

(d) inferring the size of the RFID Tag Field by using the ratio between successful and empty timeslots multiplied by said “

Number”

minus said Preselected Number wherein the interrogator/reader counts the number of empty timeslots that occurred while obtaining said Preselected Number of successful tag reads.

2. The method of claim 1 wherein said “

Number”

the interrogator/reader sends is an estimate larger than expected for possible number of RFID Tags in the RFID Tag Field.

3. The method of claim 1 wherein said “

Number”

the interrogator/reader sends is an estimate smaller than expected for the possible number of Tags in the Tag Field.

4. The method of claim 1 wherein said “

Number”

the interrogator/reader sends is an estimate larger than expected for the needed number of Aloha Timeslots.

5. The method of claim 1 wherein said “

Number”

the interrogator/reader sends is an estimate smaller than expected for the needed number of Aloha Timeslots.

6. The method of claim 1 wherein said “

Number”

the interrogator/reader sends is an arbitrary number.

7. The method of claim 1 wherein said Preselected Number of successful tag reads used is chosen at design time to optimize speed and accuracy.

8. The method of claim 1 wherein said Preselected Number of successful tag reads used is chosen at installation time to optimize speed and accuracy.

9. A method of claim 1 wherein said Predefined Relationship is equivalence.

10. A method of claim 1 wherein said Predefined Relationship is that one greater than the other.

11. The method of claim 1 wherein allowed throughput is increased by an Aloha architecture by shorting time periods of empty time slots, further comprising;

sending a read command to the RFID Tag Field wherein, the interrogator/reader listens for a response from any tag for a duration of time less than a time required to read a successful tag wherein if the interrogator/reader does not hear a response within a period of time sufficient to know that no response is going to be sent, it terminates said time slot early by sending another read command.

12. The method of claim 1 wherein allowed throughput is increased by an Aloha architecture by shorting said time periods of collided time slots, further comprising;

sending a read command to the tag field wherein the interrogator/reader listens for a response from any tag for a duration of time less than a time required to read a successful tag and long enough to determine that said timeslot is not empty and does not contain a valid message wherein the interrogator/reader determines that a timeslot contains a collided message by observing a portion of a transmission from the RFID Tag and sends a continue command in an event said message is valid and a new read command if said message is invalid.

13. The method of claim 1 wherein allowed throughput is increased by an Aloha architecture by shortening said time periods of empty and collided timeslots;

14. The method of claim 1 wherein the RFID Tag response within a given timeslot is controlled by a random number generated from an individual RFID tag'"'"'s location.

15. The method of claim 1 utilizing the estimated value of the RFID Tag Field size for maximizing throughput for reading all RFID tags in the RFID Tag Field.

16. A method to determine a value for the offered rate in a slotted Aloha network when using timeslot shortening to increase throughput which allows RFID Tags in a RFID Tag Field to be read in the least amount of time, comprising:

(a) calculating a value for producing an offered rate for maximizing throughput in the slotted Aloha network using a relationship between time durations of empty and collided timeslots; and

(b) computing a ratio of the difference in durations between said empty and collided timeslots and a scaled duration of a collided timeslot;

operating on this ratio through a ProductLog function and adding 1 to obtain a desired value of said offered rate.

17. The method of claim 16 wherein the value of said calculated offered rate may be applied to a collision based communication system operating in a slotted Aloha architecture to provide maximum throughput under a situation of time slot shortening.

18. A method to determine if there are any unread RFID Tags in an RFID Tag Field by sending from an interrogator/reader to the RFID Tag Field a “

Number”

which causes all unprocessed RFID Tags in the RFID Tag Field to respond.

19. The method of claim 18 wherein said “

Number”

the interrogator/reader sends is an estimate of 1 tag for the expected possible number of Tags in the Tag Field, further comprises;

(a) each unread tag in the RFID Tag Field tries to scale its internally generated random number to be between 1 tag and the estimate of the number of tags being 1, thus forcing the tag'"'"'s random number to be 1;

(b) a read command is sent to the tag field by the interrogator/reader;

(c) if there is only one tag remaining in the tag field, then it will be read, and the number of successful time slots will be 1;

(d) if there is more than one tag in the tag field, then a collision will result and the number of collided time slots will be 1; and

(e) if there are no remaining tags in the tag field, then the result will be an empty timeslot wherein the number of empty time slots will be 1.

20. The method of claim 18 wherein said “

Number”

the interrogator/reader sends is an estimate of 1 for the expected possible number of Aloha Timeslots, further comprises;

(a) each unread tag in the tag field tries to scale its random number to be between 1 and the estimate of the needed time slots, which is also 1, thus forcing the tags random number to be 1;

(b) a read command is sent to the tag field by the reader/interrogator;

(c) if there is only one tag remaining in the tag field, then it will be read, and the number of successful time slots will be 1;

(d) if there is more than one tag in the tag field, then a collision will result and the number of collided time slots will be 1; and

(e) if there are no remaining tags in the tag field, then the result will be an empty timeslot wherein the number of empty time slots will be 1.

21. The method of claim 18 wherein said “

Number”

the interrogator/reader sends is an arbitrary number known to the tag as a command to reply.

22. A method in a slotted Aloha network to read all RFID tags in an RFID tag field in a least amount of time by first using determined values for optimized value of an offered rate and estimating a Field Size, comprising:

(a) computing the optimized value of an estimate of Field Size for maximum read throughput by dividing a total estimated number Field Size by the optimized offered rate;

(b) sending by an interrogator/reader, the optimized value of the estimate of Field Size for maximum read throughput to each tag in the tag field and using this number as a maximum for scaling, the tags choose an internal Random Number scaled between 1 and the optimized value of the estimate of the Field Size for maximum read throughput;

(c) incrementing an internal counter each time a read command is received from the interrogator/reader, the tag attempts to communicate with the interrogator/reader when the relationship between the counter and the internal Random Number is a Predefined Relationship;

(d) if the attempt is unsuccessful, then it is assumed that a collision resulted and the tag takes a Predetermined Action;

(e) the interrogator/reader keeps track of the total number of successful time slots read, the total number of empty timeslots that occurred, and the total number of collided time slots that occurred during a particular set of read cycles;

(f) calculating, at the end of a particular set of read cycles, a new estimate for the remaining number of tags in the tag field using the values of the total number of empty timeslots, and the total number of successful time slots that it counted during the last set of read cycles and iteratively looping back to (b) until the estimated number of remaining tags is in a Preset Range; and

(g) using the Preset Range for the optimized value of the estimate of the Field Size for maximum read throughput until the reader/interrogator has determined that all tags in the tag field have been read.

23. The method of claim 22 wherein the Field Size is determined by number of tags and the Predetermined Action is that the tag goes into a wait state until the next set of read cycles occur.

24. The method of claim 22 wherein the Field Size is determined by number of time slots and the Predetermined Action is that the tag chooses a new random number that lies between its current value and the optimized value of the estimate of the total number of time slots for maximum read throughput.

25. The method of claim 22 wherein the Predefined Relationship is equivalence.

26. The method of claim 22 wherein the Predefined Relationship is that one greater than the other.

27. A method of using timeslot shortening to increase throughput in a slotted Aloha based network, comprising:

sending a series of read commands from an interrogator/reader to an RFID tag field for the purpose of communicating with RFID tags and;

receiving data from the RFID tags to determine if empty and collided timeslots occur.

28. The method of claim 27 wherein an allowed throughput is increased by said Aloha architecture by shorting said time periods of empty time slots, further comprises;

sending a read command to the tag field wherein an interrogator/reader listens for a response from any tag for a duration of time less than the time required to read a successful tag; and

if the reader/interrogator does not hear a response within a period of time sufficient to know that no response is going to be sent, then it terminates the time slot early by sending another read command.

29. The method of claim 27 wherein the allowed throughput is increased by said Aloha architecture by shorting said time periods of collided time slots, further comprises;

(a) after sending a read command to the tag field, the interrogator/reader listens for a response from any tag for a duration of time less than the time required to read a successful tag and long enough to determine that the timeslot is not empty;

(b) the reader/interrogator determines that a timeslot contains a collide message by observing a portion of the transmission from the tag, and sends a continue command in the event the message is valid, and a new read command if the message is invalid; and

(c) shortening the timeslot period during collided data to a time less than that of a successful tag read.

30. The method of claim 27 wherein the allowed throughput is increased by said Aloha architecture by shortening said time periods of empty and collided time slots.

31. The method of claim 27 wherein the throughput rate can be increased in a collision based communication system operating in the slotted Aloha architecture to provide maximum throughput under the situation of time slot shortening.

32. A method to convert an Aloha Network architecture to that of an architecture where all timeslots are filled for maximum throughput and efficiency producing throughput at a maximum allowed by the communication link, further comprising:

(a) creating a series of unique random numbers by using a location in space of one or more individual tags wherein no two tags may occupy a same space at a same time and individual tag locations must be unique such that when a read command is performed, there would be no collisions;

(b) determining location by selecting parameters from a set that includes direction from an interrogator/reader, distance from the interrogator/reader as measured by signal strength, polarization of an antenna, and an identifying number for a given interrogator/reader if there is more than one interrogator/reader in the system;

(c) using the estimate of the number of tags in the tag field to determine in advance a reasonable size for the total number of locations needed to uniquely identify the tags;

(d) programming the location based random numbers into the tags during a special programming cycle generated by the interrogator/reader wherein the interrogator/reader begins by transmitting a signal using a highly directional antenna, beginning with low signal strength, and initial antenna polarization;

(e) using a Scaling Method, scale the number of directions used and the number of signal strengths used such that the total number of combinations of direction, signal strength and polarization is equal to the estimate for the number of tags in the tag field; and

(f) creating a unique random number sequence with no gaps between the numbers for each tag in the tag field resulting in no empty timeslots by the reader/interrogator transmitting data describing to the tags the number that discloses which direction the antenna is pointed, how much power is being transmitted, and what antenna polarization is being used wherein the interrogator/reader repeats this cycle until all possible combinations of direction, power, and polarization have been sent.

33. The method of claim 32 wherein the Scaling Method is to have the interrogator/reader tune the total number of combinations of direction, signal strength and polarization to match the total estimate for the number of tags in the tag field.

34. The method of claim 32 wherein the Scaling Method is to have the interrogator/reader transmit with full resolution all possible directions, signal strength and polarization. After this is done, send a scaling command to the tags such that the tags random number is scaled down to reflect the total number of tags in the tag field.