20000 ASEA also consists of an initialization phase and an iterative phase.The initialization phase of ASEA is the same as the 15000 initialization phase of MLEA,except that when the reader 10000 obtains the first non-zero result z at the lth polling with probability pi.it computes a coarse estimation of N as 000 Then it moves to the next phase,which is described below. B.Iterative Phase 500100015002000 number of pollings This phase iteratively refines the estimation after each polling,and terminates when the specified accuracy require- Fig.1.The middle curve shows the estimated number of tags with respect ment is met.The reader performs four tasks in the ith iteration. to the number of pollings.The upper and lower curves show the confidence interval.The straightline shows the true number of tags First,it computes the contention probability pi by (13)before sending out the polling request. 1 that the performance difference caused by request-less pollings =- (13) is negligibly small even though the contention probability during request-less pollings may be slightly off the value set by (7).Request-less pollings can also be applied to the algorithms where Nis the estimation after the previous polling. in the next two sections. Second,the reader computes the number of responses zi in the current frame. E.Information Loss due to Collision Third,it computes Ni as follows: MLEA has a frame size of one slot.It obtains only binary information at each polling.Since the target contention prob- N= ∑=1+1z(1+ (14) ability is set to be 1.594/N,the probability for more than one ∑=+1 tag to respond in each polling is significant.However,no matter where s is introduced to compensate for collision and the how many tags respond,the information that the reader receives is always the same,i.e.,zi=1,which implies information iterative phase begins from the(1+1)th polling.The intuition loss when two or more tags decide to transmit at a polling behind (14)is given as follows:All pollings are performed Let's compare two scenarios.In one scenario,only one tag independent of each other.Hence,the previous pollings with responds at a polling.In the other,two tags respond.These the contention probability pi(l<j<i)and the number two scenarios generate the same information but the energy of responses zj can be treated as one polling with the con- cost of the second scenario is twice of the first.To address tention probability and the number of responses this problem.we design two more algorithms that reduce the j=11j.The correctness of this treatment will be estab- probability of collision and,moreover,compensate the impact lished by the analysis on the confidence interval and also by of collision in its computation. the simulation results. Fourth,after computing Ni,the reader determines if the V.AVERAGE SUM ESTIMATION ALGORITHM estimate meets the accuracy requirement.In the following,we The average sum estimation algorithm (ASEA)is our sec- discuss the details of the second and fourth steps. ond estimator for the number of RFID tags.It also utilizes 1)Compute the number of responses:At the ith polling, history information from previous pollings.However,instead the reader measures the number of non-empty slots in the of only obtaining binary information,it computes the number frame,denoted as zi,which is an integer in the range of [0..f] of responses in each polling.Because more information can be Due to possible collision,the actual number of responses, extracted,it requires a fewer number of responses than MLEA. denoted as,can be greater.However,we show that i closely Moreover,the computation performed by ASEA after each approximates x;.Their tiny difference can be computed and polling is much simpler than MLEA's complicated bisection corrected. search. Since each tag independently decides to respond with prob- A.Overview ability pi,follows a binomial distribution with parameters N and pi,i.e.. ASEA uses the same polling protocol as MLEA does,except that its frame size f is larger than one in order to reduce the Probfi=k}= p (1-p:)N-k (15) probability of collision.The result of the ith polling,i,is no longer a binary value.Instead,it is an estimate of the number IfpP;≈l/N and N is sufficiently large,.Prob{x幸=2}≈ of tags that respond at the polling. 0.1839,Prob{x=3}≈0.0613，Prob{x=4}≈0.0153， ASEA takes three steps to solve the collision.First,it slightly and the probability decreases exponentially with respect to k. reduces the contention probability p;.Second,it increases the frame size f such that the tags that decide to respond at a Probfz>4}is only about 0.0037.Next we compute the polling are likely to respond at different slots in the frame.We probability for collisions to happen at the ith polling,which is pick values for pi and f such that the collision probability is denoted as Probifcollision}. negligibly small.Third,we compensate the impact of collision 1We could also use (7).In that case,the frame size f would increase in our computation. accordingly to keep a small collision probability.0 5000 10000 15000 20000 0 500 1000 1500 2000 number of pollings Fig. 1. The middle curve shows the estimated number of tags with respect to the number of pollings. The upper and lower curves show the confidence interval. The straightline shows the true number of tags. that the performance difference caused by request-less pollings is negligibly small even though the contention probability during request-less pollings may be slightly off the value set by (7). Request-less pollings can also be applied to the algorithms in the next two sections. E. Information Loss due to Collision MLEA has a frame size of one slot. It obtains only binary information at each polling. Since the target contention prob￾ability is set to be 1.594/N, the probability for more than one tag to respond in each polling is significant. However, no matter how many tags respond, the information that the reader receives is always the same, i.e., zi = 1, which implies information loss when two or more tags decide to transmit at a polling. Let’s compare two scenarios. In one scenario, only one tag responds at a polling. In the other, two tags respond. These two scenarios generate the same information but the energy cost of the second scenario is twice of the first. To address this problem, we design two more algorithms that reduce the probability of collision and, moreover, compensate the impact of collision in its computation. V. AVERAGE SUM ESTIMATION ALGORITHM The average sum estimation algorithm (ASEA) is our sec￾ond estimator for the number of RFID tags. It also utilizes history information from previous pollings. However, instead of only obtaining binary information, it computes the number of responses in each polling. Because more information can be extracted, it requires a fewer number of responses than MLEA. Moreover, the computation performed by ASEA after each polling is much simpler than MLEA’s complicated bisection search. A. Overview ASEA uses the same polling protocol as MLEA does, except that its frame size f is larger than one in order to reduce the probability of collision. The result of the ith polling, xi , is no longer a binary value. Instead, it is an estimate of the number of tags that respond at the polling. ASEA takes three steps to solve the collision. First, it slightly reduces the contention probability pi . Second, it increases the frame size f such that the tags that decide to respond at a polling are likely to respond at different slots in the frame. We pick values for pi and f such that the collision probability is negligibly small. Third, we compensate the impact of collision in our computation. ASEA also consists of an initialization phase and an iterative phase. The initialization phase of ASEA is the same as the initialization phase of MLEA, except that when the reader obtains the first non-zero result xl at the lth polling with probability pl , it computes a coarse estimation of N as xl pl . Then it moves to the next phase, which is described below. B. Iterative Phase This phase iteratively refines the estimation after each polling, and terminates when the specified accuracy require￾ment is met. The reader performs four tasks in the ith iteration. First, it computes the contention probability pi by (13) before sending out the polling request. pi = 1 Nˆ i−1 , (13) where Nˆ i−1 is the estimation after the previous polling. 1 Second, the reader computes the number of responses xi in the current frame. Third, it computes Nˆ i as follows: Nˆ i = Pi j=l+1 xj (1 + ε) Pi j=l+1 pj , (14) where ε is introduced to compensate for collision and the iterative phase begins from the (l + 1)th polling. The intuition behind (14) is given as follows: All pollings are performed independent of each other. Hence, the previous pollings with the contention probability pj (l < j ≤ i) and the number of responses xj can be treated as one polling with the con￾tention probability Pi j=l+1 pj and the number of responses Pi j=l+1 xj . The correctness of this treatment will be estab￾lished by the analysis on the confidence interval and also by the simulation results. Fourth, after computing Nˆ i , the reader determines if the estimate meets the accuracy requirement. In the following, we discuss the details of the second and fourth steps. 1) Compute the number of responses: At the ith polling, the reader measures the number of non-empty slots in the frame, denoted as xi , which is an integer in the range of [0..f]. Due to possible collision, the actual number of responses, denoted as x ∗ i , can be greater. However, we show that xi closely approximates x ∗ i . Their tiny difference can be computed and corrected. Since each tag independently decides to respond with prob￾ability pi , x ∗ i follows a binomial distribution with parameters N and pi , i.e., P rob{x ∗ i = k} = µ N k ¶ p k i (1 − pi) N−k . (15) If pi ≈ 1/N and N is sufficiently large, P rob{x ∗ i = 2} ≈ 0.1839, P rob{x ∗ i = 3} ≈ 0.0613, P rob{x ∗ i = 4} ≈ 0.0153, and the probability decreases exponentially with respect to k. P rob{x ∗ i > 4} is only about 0.0037. Next we compute the probability for collisions to happen at the ith polling, which is denoted as P robi{collision}. 1We could also use (7). In that case, the frame size f would increase accordingly to keep a small collision probability