Granted Patent B2

US 7,688,180 · App. 11/525,339 · Granted Mar 30, 2010

Abstract

Claims (153)

1. A method for estimating the cardinality of a set of one or more tags in a system that comprises the set of one or more tags and one or more readers, wherein:

the one or more readers are adapted to issue a command requesting that the tags issue a reply to identify themselves, the command including timing information defining a total number of timeslots for the reply; and

in response to the command, one or more of the tags is adapted to (i) select a timeslot in which to reply to the command and (ii) issue the reply in the selected timeslot;

the method comprising:

(a) issuing the command;

(b) receiving, in one or more timeslots, replies from the one or more tags; and

(c) deriving an estimate of the cardinality of the set of one or more tags in the system, wherein the cardinality estimate is at least one of:

(i) based on the number of zero slots, wherein a zero slot is a timeslot identified as having no tags transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(t 0 /f) =n 0 /f,

wherein f is the total number of timeslots, and n 0 is the number of zero slots;

(ii) based on the number of zero slots, wherein a zero slot is a timeslot identified as having no tags transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(pt 0 /f) =n 0 /f,

wherein f is the total number of timeslots, n o is the number of zero slots, and p is the probability that a tag will select a given timeslot;

(iii) based on the number of singleton slots, wherein a singleton slot is a timeslot identified as having only one tag transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 1 in the equation

( t 1 /f ) e −(t 1 /f) =n 1 /f,

wherein f is the total number of timeslots, and n 1 is the number of singleton slots;

(iv) based on the number of collision slots, wherein a collision slot is a timeslot identified as having more than one tag transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1−(1+( t c /f )) e −(t c /f) =n c /f,

wherein f is the total number of timeslots, and n c is the number of collision slots; and

(v) based on the number of collision slots, wherein a collision slot is a timeslot identified as having more than one tag transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1+(1+( pt c /f )) e −(pt c /f) =n c /f,

wherein f is the total number of timeslots, n c is the number of collision slots, and p is the probability that a tag will select a given timeslot.

2. The invention of claim 1 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(t 0 /f) =n 0 /f,

wherein f is the total number of timeslots, and n 0 is the number of zero slots.

3. The invention of claim 1 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(pt 0 /f) =n 0 /f,

wherein f is the total number of timeslots, n 0 is the number of zero slots, and p is the probability that a tag will select a given timeslot.

4. The invention of claim 1 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 1 in the equation

( t 1 /f ) e −(t 1 /f) =n 1 /f,

wherein f is the total number of timeslots, and n 1 is the number of singleton slots.

5. The invention of claim 1 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1−(1+( t c /f )) e −(t c /f) =n c /f,

wherein f is the total number of timeslots, and n c is the number of collision slots.

6. The invention of claim 1 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1−(1+( pt c /f )) e −(pt c /f) =n c /f,

wherein f is the total number of timeslots, n c is the number of collision slots, and p is the probability that a tag will select a given timeslot.

7. The invention of claim 1 , wherein step (c) further comprises:

determining, based on a load factor of the system, whether to use the number of zero slots or the number of collision slots in deriving the estimate of the cardinality of the set.

8. The invention of claim 7 , wherein:

the load factor is a relationship between (i) an estimated or actual number of tags in the system and (ii) the total number of time slots in the reply;

the number of collision slots is used to derive the estimate of the cardinality of the set of one or more tags in the system when the load factor exceeds a specified threshold; and

the number of zero slots is used to derive the estimate of the cardinality of the set of one or more tags in the system when the load factor does not exceed the specified threshold.

9. The invention of claim 1 , wherein:

steps (a), (b), and (c) are implemented multiple times to generate multiple estimates of cardinality; and

the method further comprises deriving a variance of an estimate of the cardinality of the set of one or more tags in the system based on the multiple estimates.

10. The invention of claim 9 , further comprising:

deriving a first variance by obtaining a first set of multiple estimates using the number of collision slots;

deriving a second variance by obtaining a second set of multiple estimates using the number of zero slots;

if the first variance is lower than the second variance, then obtaining one or more subsequent estimates of the cardinality of the set of one or more tags in the system using the number of collision slots; and

if the first variance is not lower than the second variance, then obtaining one or more subsequent estimates of the cardinality of the set of one or more tags in the system using the number of zero slots.

11. Apparatus for estimating the cardinality of a set of one or more tags in a system that comprises the set of one or more tags and one or more readers, wherein:

the one or more readers are adapted to issue a command requesting that the tags issue a reply to identify themselves, the command including timing information defining a total number of timeslots for the reply; and

in response to the command, one or more of the tags is adapted to (i) select a timeslot in which to reply to the command and (ii) issue the reply in the selected timeslot;

the apparatus adapted to:

(a) issue the command;

(b) receive, in one or more timeslots, replies from the one or more tags; and

(c) derive an estimate of the cardinality of the set of one or more tags in the system, wherein the cardinality estimate is at least one of:

(i) based on the number of zero slots, wherein a zero slot is a timeslot identified as having no tags transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(t 0 /f) =n 0 /f,

wherein f is the total number of timeslots, and n 0 is the number of zero slots;

(ii) based on the number of zero slots, wherein a zero slot is a timeslot identified as having no tags transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(pt 0 /f) =n 0 /f,

wherein f is the total number of timeslots, n 0 is the number of zero slots, and p is the probability that a tag will select a given timeslot;

(iii) based on the number of singleton slots, wherein a singleton slot is a timeslot identified as having only one tag transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 1 in the equation

( t 1 /f ) e −(t 1 /f) =n 1 /f,

wherein f is the total number of timeslots, and n 1 is the number of singleton slots;

(iv) based on the number of collision slots, wherein a collision slot is a time slot identified as having more than one tag transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1−(1+( t c /f )) e −(t c /f) =n c /f,

wherein f is the total number of timeslots, and n c is the number of collision slots; and

(v) based on the number of collision slots, wherein a collision slot is a timeslot identified as having more than one tag transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1−(1+( pt c /f )) e −(pt c /f) =n c /f,

wherein f is the total number of timeslots, n c is the number of collision slots, and p is the probability that a tag will select a given timeslot.

12. The invention of claim 11 , wherein the apparatus is further adapted to determine, based on a load factor of the system, whether to use the number of zero slots or the number of collision slots in deriving the estimate of the cardinality of the set.

13. The invention of claim 11 , wherein the apparatus is further adapted to:

implement steps (a), (b), and (c) multiple times to generate multiple estimates of cardinality; and

derive a variance of an estimate of the cardinality of the set of one or more tags in the system based on the multiple estimates.

14. The invention of claim 11 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(t 0 /f) =n 0 /f,

wherein f is the total number of timeslots, and n 0 is the number of zero slots.

15. The invention of claim 11 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(pt 0 /f) =n 0 /f,

wherein f is the total number of timeslots, n 0 is the number of zero slots, and p is the probability that a tag will select a given timeslot.

16. The invention of claim 11 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 1 in the equation

( t 1 /f ) e −(t 1 /f) =n 1 /f,

wherein f is the total number of timeslots, and n 1 is the number of singleton slots.

17. The invention of claim 11 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1−(1+( t c /f )) e −(t c /f) =n 0 /f,

wherein f is the total number of timeslots, and n c is the number of collision slots.

18. The invention of claim 11 , wherein the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1−(1+( pt c /f )) e −(pt c /f) =n c /f,

wherein f is the total number of timeslots, n c is the number of collision slots, and p is the probability that a tag will select a given timeslot.

19. A machine-readable storage medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method for estimating the cardinality of a set of one or more tags in a system that comprises the set of one or more tags and one or more readers, wherein:

the one or more readers are adapted to issue a command requesting that the tags issue a reply to identify themselves, the command including timing information defining a total number of timeslots for the reply; and

in response to the command, one or more of the tags is adapted to (i) select a timeslot in which to reply to the command and (ii) issue the reply in the selected timeslot;

the method comprising:

(a) issuing the command;

(b) receiving, in one or more timeslots, replies from the one or more tags; and

(c) deriving an estimate of the cardinality of the set of one or more tags in the system wherein the cardinality estimate is at least one of:

(i) based on the number of zero slots, wherein a zero slot is a timeslot identified as having no tags transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(t 0 /f) =n 0 /f,

wherein f is the total number of timeslots, and n 0 is the number of zero slots;

(ii) based on the number of zero slots, wherein a zero slot is a timeslot identified as having no tags transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 0 in the equation

e −(pt 0 /f) =n 0 /f,

wherein f is the total number of timeslots, n 0 is the number of zero slots, and p is the probability that a tag will select a given timeslot;

(iii) based on the number of singleton slots, wherein a singleton slot is a timeslot identified as having only one tag transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t 1 in the equation

( t 1 /f ) e −(t 1 /f) =n 1 /f,

wherein f is the total number of timeslots, and n 1 is the number of singleton slots;

(iv) based on the number of collision slots, wherein a collision slot is a time slot identified as having more than one tag transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1−(1+( t c /f )) e −(t c /f) =n c /f,

wherein f is the total number of timeslots, and n c is the number of collision slots; and

(v) based on the number of collision slots, wherein a collision slot is a timeslot identified as having more than one tag transmitting therein, and the estimate of the cardinality of the set of one or more tags in the system in step (c) is derived by solving for the variable t c in the equation

1−(1+( pt c /f )) e −(pt c /f) =n c /f,

wherein f is the total number of timeslots, n c is the number of collision slots, and p is the probability that a tag will select a given timeslot.

20. The invention of claim 19 , wherein step (c) further comprises:

determining, based on a load factor of the system, whether to use the number of zero slots or the number of collision slots in deriving the estimate of the cardinality of the set.

21. The invention of claim 19 , wherein:

steps (a), (b), and (c) are implemented multiple times to generate multiple estimates of cardinality; and

the method further comprises deriving a variance of an estimate of the cardinality of the set of one or more tags in the system based on the multiple estimates.

22. A method for estimating the cardinality of a set of one or more tags in a system that comprises the set of one or more tags and one or more readers, wherein:

the one or more readers are adapted to issue a command requesting that the tags issue a reply to identify themselves, the command including timing information defining a total number of timeslots for the reply; and

in response to the command, one or more of the tags is adapted to (i) select a timeslot in which to reply to the command and (ii) issue the reply in the selected timeslot;

the method comprising:

(a) issuing the command;

(b) receiving, in one or more timeslots, replies from the one or more tags; and

(c) deriving an estimate of the cardinality of the set of one or more tags in the system based on at least one of:

(i) the number of zero slots, wherein a zero slot is a timeslot identified as having no tags transmitting therein,

(ii) the number of singleton slots, wherein a singleton slot is a timeslot identified as having only one tag transmitting therein, and

(iii) the number of collision slots, wherein a collision slot is a timeslot identified as having more than one tag transmitting therein, wherein:

steps (a), (b), and (c) are implemented multiple times to generate multiple estimates of cardinality; and

the method further comprises:

(d) deriving variances of an estimate of the cardinality of the set of one or more tags in the system based on the multiple estimates, wherein step (d) further comprises:

(d1) deriving a first variance by obtaining a first set of multiple estimates using the number of collision slots;

(d2) deriving a second variance by obtaining a second set of multiple estimates using the number of zero slots;

(d3) if the first variance is lower than the second variance, then obtaining one or more subsequent estimates of the cardinality of the set of one or more tags in the system using the number of collision slots; and

(d4) if the first variance is not lower than the second variance, then obtaining one or more subsequent estimates of the cardinality of the set of one or more tags in the system using the number of zero slots.

23. Apparatus for estimating the cardinality of a set of one or more tags in a system that comprises the set of one or more tags and one or more readers, wherein:

the one or more readers are adapted to issue a command requesting that the tags issue a reply to identify themselves, the command including timing information defining a total number of timeslots for the reply; and

in response to the command, one or more of the tags is adapted to (i) select a timeslot in which to reply to the command and (ii) issue the reply in the selected timeslot;

the apparatus adapted to:

(a) issue the command;

(b) receive, in one or more timeslots, replies from the one or more tags; and

(c) derive an estimate of the cardinality of the set of one or more tags in the system based on at least one of:

(i) the number of zero slots, wherein a zero slot is a timeslot identified as having no tags transmitting therein,

(ii) the number of singleton slots, wherein a singleton slot is a timeslot identified as having only one tag transmitting therein, and

(iii) the number of collision slots, wherein a collision slot is a timeslot identified as having more than one tag transmitting therein, wherein:

steps (a), (b), and (c) are implemented multiple times to generate multiple estimates of cardinality; and

the method further comprises:

(d) deriving variances of an estimate of the cardinality of the set of one or more tags in the system based on the multiple estimates, wherein step (d) further comprises:

(d1) deriving a first variance by obtaining a first set of multiple estimates using the number of collision slots;

(d2) deriving a second variance by obtaining a second set of multiple estimates using the number of zero slots;

(d3) if the first variance is lower than the second variance, then obtaining one or more subsequent estimates of the cardinality of the set of one or more tags in the system using the number of collision slots; and

(d4) if the first variance is not lower than the second variance, then obtaining one or more subsequent estimates of the cardinality of the set of one or more tags in the system using the number of zero slots.

Assignments (8)