Anonymous tracking using a set of wireless devices

• US 8,299,900 B2
• Filed: 06/29/2007
• Issued: 10/30/2012
• Est. Priority Date: 09/27/2006
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Nandagopal, Thyagarajan, Lau, Wing Cheong, Kodialam, Muralidharan S.
• Primary Examiner(s): Zimmerman, Brian
• Assistant Examiner(s): Nguyen, An T
• Application Number:
  US11/824,469
• Publication Number:
  US 20080074238A1
• Time in Patent Office: 1,950 Days
• Field of Search: 340 101- 105, 3405721-5729, 370/206, 370/314, 370/336, 370/342, 370/345, 370/458, 370/445, 370/448
• US Class Current: 340/10.2
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02

Abstract

In one embodiment, a method for estimating the number of tags in a set of tags in a system of tags and readers. The method includes, during each of a plurality of time intervals: (i) transmitting a command requesting that each tag that receives the command determine whether to transmit a reply; and (ii) receiving, in one or more timeslots of a frame corresponding to the time interval, replies from one or more tags. The method further includes providing an estimate of the number of tags in the set of one or more tags based on (i) timeslots in each of the plurality of time intervals that are zero timeslots, i.e., timeslots having no received reply, and (ii) the total number of timeslots in each frame.

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 transmit a command requesting that each tag that receives the command determine whether to transmit a reply;

each receiving tag is adapted to determine whether to transmit a reply based on a specified probability level; and

each receiving tag that determines to transmit a reply (i) selects a timeslot of a frame in which to transmit the reply based on (1) a specified total number of timeslots in the frame and (2) a specified random-number seed and (ii) transmits the reply in the selected timeslot;

the method comprising;

(a) during each of a plurality of time intervals;

(a1) transmitting a command requesting that each tag that receives the command determine whether to transmit a reply; and

(a2) receiving, in one or more timeslots of a frame corresponding to the time interval, replies from one or more tags; and

(b) providing an estimate of the cardinality of the set of one or more tags in the system based on (i) timeslots in each of the plurality of time intervals that are zero timeslots, wherein a zero timeslot is a timeslot having no received reply, and (ii) the total number of timeslots in each frame'"'"',

wherein the estimate t₀ of the cardinality of the set of one or more tags in the system in step (b) is calculated using at least;

(i) the total number f of timeslots in each frame, (ii) the probability p that a tag will reply in a timeslot, (iii) a load factor ρ

₀ defined as a ratio of a number of tags to frame size, and (iv) the number z_i of zero timeslots for time interval i,

wherein the estimate t₀ of the cardinality of the set of one or more tags in the system in step (b) is derived using the equations

2. The invention of claim 1, wherein:

step (a) further comprises, during each of a plurality of time intervals, (a3) determining a number of zero timeslots in the frame; and

step (b) provides the estimate of the cardinality of the set of one or more tags in the system based on (i) a sum of the numbers of zero timeslots for the plurality of time intervals and (ii) the total number of timeslots in each frame.

3. The invention of claim 1, wherein the command comprises (1) the specified probability level, (2) the specified total number of timeslots in the frame, and (3) the specified random-number seed.

4. The invention of claim 1, wherein the value of pρ

₀ is selected to minimize variance of the estimate of the cardinality of the set of one or more tags in the system.

5. The invention of claim 1, wherein different random-number seeds are used during at least two different time intervals.

6. The invention of claim 1, wherein the same total number of timeslots in each frame, probability level, and random-number seed are used during at least two different time intervals.

7. The invention of claim 1, further comprising:

(c) performing steps (a) and (b) a plurality of times to generate a plurality of cardinality estimates; and

(d) providing a modified cardinality estimate based on the plurality of cardinality estimates.

8. The invention of claim 7, wherein step (d) comprises applying one or more of a union operation, an intersection operation, and a difference operation to the plurality of cardinality estimates.

9. The invention of claim 7, wherein:

step (c) is performed one or more times for a first tag-set size bound by a first set of upper and lower limits; and

step (c) is performed one or more times for a second tag-set size bound by a second set of upper and lower limits.

10. The invention of claim 1, wherein an optimal number n of time intervals in the plurality of time intervals is selected using the equation

11. The invention of claim 1, wherein an optimal number of timeslots f is selected using the equations

12. A system 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 (i) timing information defining a total number of timeslots for the reply, (ii) a probability that a tag will reply in a given timeslot, and (iii) a random-number seed; 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 system adapted to;

(a) during each of a plurality of time intervals;

(a1) issue a command;

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

(a3) determine the number of zero timeslots corresponding to the time interval, wherein a zero timeslot is a timeslot identified as having no tags transmitting therein during the time interval in reply to the command; and

(b) provide an estimate of the cardinality of the set of one or more tags in the system based on (i) a sum of the number of zero timeslots across the plurality of time intervals and (ii) the total number of timeslots,

wherein the estimate t₀ of the cardinality of the set of one or more tags in the system in step (b) is calculated using at least;

(i) the total number f of timeslots in each frame, (ii) the probability p that a tag will reply in a timeslot, (iii) a load factor ρ

₀ defined as a ratio of a number of tags to frame size, and (iv) the number z_i of zero timeslots for time interval i,

wherein the estimate t₀ of the cardinality of the set of one or more tags in the system in step (b) is derived using the equations

13. A non-transitory machine-readable 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 (i) timing information defining a total number of timeslots for the reply, (ii) a probability that a tag will reply in a given timeslot, and (iii) a random-number seed; 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) during each of a plurality of time intervals;

(a1) issuing a command;

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

(a3) determining the number of zero timeslots corresponding to the time interval, wherein a zero timeslot is a timeslot identified as having no tags transmitting therein during the time interval in reply to the command; and

(b) providing an estimate of the cardinality of the set of one or more tags in the system based on (i) a sum of the number of zero timeslots across the plurality of time intervals and (ii) the total number of timeslots,

wherein the estimate t₀ of the cardinality of the set of one or more tags in the system in step (b) is calculated using at least;

(i) the total number f of timeslots in each frame, (ii) the probability p that a tag will reply in a timeslot, (iii) a load factor ρ

₀ defined as a ratio of a number of tags to frame size, and (iv) the number z_i of zero timeslots for time interval i,

wherein the estimate t₀ of the cardinality of the set of one or more tags in the system in step (b) is derived using the equations

14. 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 transmit a command requesting that each tag that receives the command determine whether to transmit a reply;

each receiving tag is adapted to determine whether to transmit a reply based on a specified probability level; and

each receiving tag that determines to transmit a reply (i) selects a timeslot of a frame in which to transmit the reply based on (1) a specified total number of timeslots in the frame and (2) a specified random-number seed and (ii) transmits the reply in the selected timeslot;

the method comprising;

(a) during each of a plurality of time intervals;

(a1) transmitting a command requesting that each tag that receives the command determine whether to transmit a reply; and

(a2) receiving, in one or more timeslots of a frame corresponding to the time interval, replies from one or more tags; and

(b) providing an estimate of the cardinality of the set of one or more tags in the system based on (i) timeslots in each of the plurality of time intervals that are zero timeslots, wherein a zero timeslot is a timeslot having no received reply, and (ii) the total number of timeslots in each frame, wherein;

the estimate t₀ of the cardinality of the set of one or more tags in the system in step (b) is calculated using at least;

(i) the total number f of timeslots in each frame, (ii) the probability p that a tag will reply in a timeslot, (iii) a load factor ρ

₀ defined as a ratio of a number of tags to frame size, and (iv) the number z_i of zero timeslots for time interval i; and

an optimal number n of time intervals in the plurality of time intervals is selected using the equation

15. 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 transmit a command requesting that each tag that receives the command determine whether to transmit a reply;

each receiving tag is adapted to determine whether to transmit a reply based on a specified probability level; and

each receiving tag that determines to transmit a reply (i) selects a timeslot of a frame in which to transmit the reply based on (1) a specified total number of timeslots in the frame and (2) a specified random-number seed and (ii) transmits the reply in the selected timeslot;

the method comprising;

(a) during each of a plurality of time intervals;

(a1) transmitting a command requesting that each tag that receives the command determine whether to transmit a reply; and

(a2) receiving;

in one or more timeslots of a frame corresponding to the time interval, replies from one or more tags; and

(b) providing an estimate of the cardinality of the set of one or more tags in the system based on (i) timeslots in each of the plurality of time intervals that are zero timeslots, wherein a zero timeslot is a timeslot having no received reply, and (ii) the total number of timeslots in each frame, wherein;

the estimate t₀ of the cardinality of the set of one or more tags in the system in step (b) is calculated using at least;

(i) the total number f of timeslots in each frame, (ii) the probability p that a tag will reply in a timeslot, (iii) a load factor ρ

₀ defined as a ratio of a number of tags to frame size, and (iv) the number z_i of zero timeslots for time interval i; and

an optimal number of timeslots f is selected using the equations