Estimation of the cardinality of a set of wireless devices

• US 7,688,180 B2
• Filed: 09/22/2006
• Issued: 03/30/2010
• Est. Priority Date: 09/22/2006
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Nandagopal, Thyagarajan, Kodialam, Muralidharan S.
• Primary Examiner(s): Wu, Daniel
• Assistant Examiner(s): WILSON, BRIAN P
• Application Number:
  US11/525,339
• Publication Number:
  US 20080079544A1
• Time in Patent Office: 1,285 Days
• Field of Search: None
• US Class Current: 340/10.1
• CPC Class Codes: G06K 7/10029 the collision being resolved in the time domain, e.g. using binary tree search or RFID responses allocated to a random time slot
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02

Abstract

In one embodiment, a method for estimating the cardinality of one or more tags in a system that has the one or more tags and one or more readers. The reader issues a command requesting that the tags identify themselves. The command includes timing information defining a total number of timeslots. In response to the command, each of the one or more tags (i) selects a timeslot in which to reply to the command and (ii) issues a reply in the selected timeslot. The method includes: (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 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 that has no tags transmitting therein, (ii) the number of singleton slots, wherein a singleton slot is a timeslot that has only one tag transmitting therein, and (iii) the number of collision slots, wherein a collision slot is a timeslot that has more than one tag transmitting therein.

Claims

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₀ in the equation

e<sup>−

(t0/f)</sup>=n₀/f,

wherein f is the total number of timeslots, and n₀ 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₀ in the equation

e<sup>−

(pt0/f)</sup>=n₀/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₁ in the equation

(t₁/f)e<sup>−

(t1/f)</sup>=n₁/f,

wherein f is the total number of timeslots, and n₁ 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<sup>−

(tc/f)</sup>=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<sup>−

(ptc/f)</sup>=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₀ in the equation

e⁻

(t^0/f)=n₀/f,

wherein f is the total number of timeslots, and n₀ 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₀ in the equation

e⁻

(pt^0/f)=n₀/f,

wherein f is the total number of timeslots, n₀ 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₁ in the equation

(t₁/f)e⁻

(t^1/f)=n₁/f,

wherein f is the total number of timeslots, and n₁ 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<sup>−

(tc/f)</sup>=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<sup>−

(ptc/f)</sup>=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₀ in the equation

e<sup>−

(t0/f)</sup>=n₀/f,

wherein f is the total number of timeslots, and n₀ 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₀ in the equation

e<sup>−

(pt0/f)</sup>=n₀/f,

wherein f is the total number of timeslots, n₀ 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₁ in the equation

(t₁/f)e<sup>−

(t1/f)</sup>=n₁/f,

wherein f is the total number of timeslots, and n₁ 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<sup>−

(tc/f)</sup>=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<sup>−

(ptc/f)</sup>=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₀ in the equation

e⁻

(t^0/f)=n₀/f,

wherein f is the total number of timeslots, and n₀ 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₀ in the equation

e⁻

(pt^0/f)=n₀/f,

wherein f is the total number of timeslots, n₀ 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₁ in the equation

(t₁/f)e⁻

(t^1/f)=n₁/f,

wherein f is the total number of timeslots, and n₁ 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<sup>−

(tc/f)</sup>=n₀/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<sup>−

(ptc/f)</sup>=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₀ in the equation

e<sup>−

(t0/f)</sup>=n₀/f,

wherein f is the total number of timeslots, and n₀ 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₀ in the equation

e<sup>−

(pt0/f)</sup>=n₀/f,

wherein f is the total number of timeslots, n₀ 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₁ in the equation

(t₁/f)e<sup>−

(t1/f)</sup>=n₁/f,

wherein f is the total number of timeslots, and n₁ 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<sup>−

(tc/f)</sup>=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<sup>−

(ptc/f)</sup>=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.