slotted time frame during which the tags respond.The polling A.Overview request from the reader carries a contention probability 0< MLEA uses the polling protocol described in Section III-B p 1 and a frame size f.Each tag will participate in the The frame size f is fixed to be one slot.The reader adjusts the current polling with probability p.If it decides to participate, contention probability for each polling.Let pi be the contention it will pick a slot uniformly at random from the frame,and probability of the ith polling.MLEA only records whether the transmit a bit string (called response)in that slot.The format of the response depends on the application.If the tag decides sole slot in each polling is empty or non-empty.Based on this information,it refines the estimate N until the accuracy to not participate,it will keep silent.In our solutions,p will requirement is met.Let z;be the slot state of the ith polling. be set in the order of When at least one tag responds,the slot is non-empty and If we know a lower bound Nmin of N,the contention zi=1.When no tag responds,it is empty and zi=0.The probability can be implemented efficiently to conserve energy. sequence of zi,i>1,forms the response vector. For example,a company's inventory of certain goods may be At the ith polling,each tag has a probability of pi to transmit routinely in thousands and never be reduced below a certain and,if any tag transmits,z;will be one.Hence, number before,or the company has a policy on the minimum inventory,or the RFID estimation becomes unnecessary when Prob{zi=1}=1-(1-pi)N1-e-NpL, (1) the number of tags is below a threshold.In these cases,we will have a lower bound Nmin,which can be much smaller than N. where N is the the actual number of tags. At the beginning of a polling,each tag makes a probabilistic If the contention probabilities of the pollings are picked decision:It goes to sleep for the whole polling period with too small,the response vector will contain mostly zeros.If probability 1-N and wakes up until the next period starts. the contention probabilities are picked too large,the response or it stays awaketo receive the polling request with probability vector will contain mostly ones.Both cases do not provide 1and then decides to respond with probability px Nmin. sufficient statistical information for accurate estimation.As Nmin For example,if N =10,000 and Nmin =1,000,then only will be discussed shortly,our analysis shows that the optimal 10 tags stay awake in each polling.In Section IV-D,another contention probability is pi=1.594/N.The problem is that energy-reduction method,called request-less pollings,will be we do not know N(which is the quantity we want to estimate). proposed to eliminate most polling requests. In order to determine pi,MLEA consists of an initialization Optionally,the reader's request may include a predicate phase and an iterative phase.The former quickly produces and only tags that satisfy the predicate will participate in the a coarse estimation of N.The latter refines the contention polling.For example,suppose all tags deployed in one section probability and generates the estimation result of a warehouse carry the 96-bit GEN2 IDs that begin with "000"in the Serial Number field.In order to estimate the B.Initialization Phase number of tags in this section,the request carries a predicate We want to pick a small value for the initial contention testing whether the first three bits of a tag's Serial Number is probability.The expected number of responding tags at the “000*」 first polling is Np1.If p is picked too large,a lot of A slot is said to be empty if no tag responds (transmits) tags will respond,which is wasteful because one response in the slot.It is called a singleton slot if exactly one tag or many responses produce the same information-a non- responds.It is a collision slot if more than one tag responds.A empty slot.Suppose we know an upper bound Nmax of N. singleton or collision slot is also called a non-empty slot.The This information is often available in practice.For example, Philips I-Code system [16]requires a slot length of 10 bits we know Nmaz is 10,000 if the warehouse is designed to in order to distinguish singleton slots from collision slots.On hold no more than 10,000 microwaves (each tagged with a the contrary.one bit is enough if we only need to distinguish RFID),or the company's inventory policy requires that in-store empty slots from non-empty slots-'0'means empty and'1' microwaves should not exceed 10,000,or the warehouse only means non-empty.Hence,the response will be much shorter has 10,000 RFID tags in use.Nmar can be much bigger than (or consume much less energy)if an algorithm only needs to N.We pick p=such that the expected number of know empty/non-empty slots,instead of all three types of slots responding tags is no more than one.If=0.we multiply the as required by [3]. contention probability by a constant C(>1),i.e.,p2=p1x C In order to prolong the lifetime of the tags,there are for the second polling.We continue multiplying the contention two ways to reduce their energy consumption:reducing the probability by C after each polling until a non-empty slot is size of each response and reducing the number of responses. observed.When that happens (say,at the Ith polling),we have We will design algorithms that require only the knowledge a coarse estimation of N to be 1/p.Then we move to the of empty/non-empty slots and employ statistical methods to next phase.When C is relatively large,the initialization phase minimize the transmissions needed from the tags. only takes a few pollings to complete due to the exponential increase of the contention probability. IV.MAXIMUM LIKELIHOOD ESTIMATION ALGORITHM Our first estimator for the number of RFID tags is called C.Iterative Phase the maximum likelihood estimation algorithm (MLEA).It fully This phase iteratively refines the estimation result after each utilizes the information from all pollings in order to minimize polling,and terminates when the specified accuracy require- the number of tag responses it needs to meet the accuracy ment is met.Let N;be the estimated number of tags after the requirement ith polling.The reader performs three tasks.First,it sets theslotted time frame during which the tags respond. The polling request from the reader carries a contention probability 0 < p ≤ 1 and a frame size f. Each tag will participate in the current polling with probability p. If it decides to participate, it will pick a slot uniformly at random from the frame, and transmit a bit string (called response) in that slot. The format of the response depends on the application. If the tag decides to not participate, it will keep silent. In our solutions, p will be set in the order of 1 N . If we know a lower bound Nmin of N, the contention probability can be implemented efficiently to conserve energy. For example, a company’s inventory of certain goods may be routinely in thousands and never be reduced below a certain number before, or the company has a policy on the minimum inventory, or the RFID estimation becomes unnecessary when the number of tags is below a threshold. In these cases, we will have a lower bound Nmin, which can be much smaller than N. At the beginning of a polling, each tag makes a probabilistic decision: It goes to sleep for the whole polling period with probability 1− 1 Nmin and wakes up until the next period starts, or it stays awake to receive the polling request with probability 1 Nmin and then decides to respond with probability p × Nmin. For example, if N = 10, 000 and Nmin = 1, 000, then only 10 tags stay awake in each polling. In Section IV-D, another energy-reduction method, called request-less pollings, will be proposed to eliminate most polling requests. Optionally, the reader’s request may include a predicate and only tags that satisfy the predicate will participate in the polling. For example, suppose all tags deployed in one section of a warehouse carry the 96-bit GEN2 IDs that begin with “000” in the Serial Number field. In order to estimate the number of tags in this section, the request carries a predicate testing whether the first three bits of a tag’s Serial Number is “000”. A slot is said to be empty if no tag responds (transmits) in the slot. It is called a singleton slot if exactly one tag responds. It is a collision slot if more than one tag responds. A singleton or collision slot is also called a non-empty slot. The Philips I-Code system [16] requires a slot length of 10 bits in order to distinguish singleton slots from collision slots. On the contrary, one bit is enough if we only need to distinguish empty slots from non-empty slots — ‘0’ means empty and ‘1’ means non-empty. Hence, the response will be much shorter (or consume much less energy) if an algorithm only needs to know empty/non-empty slots, instead of all three types of slots as required by [3]. In order to prolong the lifetime of the tags, there are two ways to reduce their energy consumption: reducing the size of each response and reducing the number of responses. We will design algorithms that require only the knowledge of empty/non-empty slots and employ statistical methods to minimize the transmissions needed from the tags. IV. MAXIMUM LIKELIHOOD ESTIMATION ALGORITHM Our first estimator for the number of RFID tags is called the maximum likelihood estimation algorithm (MLEA). It fully utilizes the information from all pollings in order to minimize the number of tag responses it needs to meet the accuracy requirement. A. Overview MLEA uses the polling protocol described in Section III-B. The frame size f is fixed to be one slot. The reader adjusts the contention probability for each polling. Let pi be the contention probability of the ith polling. MLEA only records whether the sole slot in each polling is empty or non-empty. Based on this information, it refines the estimate Nˆ until the accuracy requirement is met. Let zi be the slot state of the ith polling. When at least one tag responds, the slot is non-empty and zi = 1. When no tag responds, it is empty and zi = 0. The sequence of zi , i ≥ 1, forms the response vector. At the ith polling, each tag has a probability of pi to transmit and, if any tag transmits, zi will be one. Hence, P rob{zi = 1} = 1 − (1 − pi) N ≈ 1 − e −Npi , (1) where N is the the actual number of tags. If the contention probabilities of the pollings are picked too small, the response vector will contain mostly zeros. If the contention probabilities are picked too large, the response vector will contain mostly ones. Both cases do not provide sufficient statistical information for accurate estimation. As will be discussed shortly, our analysis shows that the optimal contention probability is pi = 1.594/N. The problem is that we do not know N (which is the quantity we want to estimate). In order to determine pi , MLEA consists of an initialization phase and an iterative phase. The former quickly produces a coarse estimation of N. The latter refines the contention probability and generates the estimation result. B. Initialization Phase We want to pick a small value for the initial contention probability. The expected number of responding tags at the first polling is N p1. If p1 is picked too large, a lot of tags will respond, which is wasteful because one response or many responses produce the same information — a non￾empty slot. Suppose we know an upper bound Nmax of N. This information is often available in practice. For example, we know Nmax is 10,000 if the warehouse is designed to hold no more than 10,000 microwaves (each tagged with a RFID), or the company’s inventory policy requires that in-store microwaves should not exceed 10,000, or the warehouse only has 10,000 RFID tags in use. Nmax can be much bigger than N. We pick p1 = 1 Nmax such that the expected number of responding tags is no more than one. If z1 = 0, we multiply the contention probability by a constant C(> 1), i.e., p2 = p1 ×C for the second polling. We continue multiplying the contention probability by C after each polling until a non-empty slot is observed. When that happens (say, at the lth polling), we have a coarse estimation of N to be 1/pl . Then we move to the next phase. When C is relatively large, the initialization phase only takes a few pollings to complete due to the exponential increase of the contention probability. C. Iterative Phase This phase iteratively refines the estimation result after each polling, and terminates when the specified accuracy require￾ment is met. Let Nˆ i be the estimated number of tags after the ith polling. The reader performs three tasks. First, it sets the