contention probability as follows before sending out the polling 3)Termination Condition:We show in Appendix A that, request: when i is large,N;approximately follows the Gaussian distri- Pi= (2) bution: N-1 Norm( (1-(1-p)) i(1-p)Nln2(1-p) where N-1 is the estimate after the previous polling and w is a constant,which will be determined shortly.Second,based According to (6),the variance of N can be written as p on the received z;and the history information,the reader finds Hence,the confidence interval of N is the new estimate of N that maximizes the following likelihood function: eNiPI-1 N:±Za·1 ip明 (9) L:=Π1-p)1-1-(1-p)), (3) where Z is the a percentile for the standard Gaussian distribu- =1 tion.For example,when a=95%,Za =1.96.Because N is where (1-p)N(1-)(1-(1-pj)N)=is the probability that undetermined,we use N;as an approximation when computing the standard deviation in (9) the state of the slot in the jth polling is zj.Namely,we want The termination condition for EMLA is therefore to find Ni arg max{Li} eNiP -1 (4) N ≤N·B, (10) 评 Third,after computing Ni,the reader has to determine if the where B is the error bound.The above inequality can be confidence interval of the estimation meets the requirement.In rewritten as the following,we show how the above tasks can be achieved. 1)Determine the Contention Probability:Using the i≥ ZaVeNIp:-1 (11) 6-method [17],we derive the variance of Ni in Appendix NipiB A. Because p:=1.594/N,we have Var(N)≈ 1-(1-p)N (5) i(1-p)N1n2(1-p) 1.544.Z8 i≥ (12) 32 When N is large and pi is small,we can approximate(1-p:)N as e-Npe and In(1-pi)as pi.The above variance becomes Hence we can theoretically compute the approximate number of pollings that is required in order to meet the accuracy Var()≈e-l requirements.For example,if a =95%and B =5%,2372 (6) ip pollings will be required.Note that (12)is independent with the actual number of tags,N.Hence,our approach has perfect We pick the value of pi that minimizes Var(Ni).Differen- scalability. tiating the right side of (6)and letting it be zero,we have Fig.I shows the simulation result of MLEA when N pi=1.594/N.Because MLE approach provides statistically 10.000.a =95%and 3=5%.The simulation setup can be consistent estimate,when i is large,N can be closely approx- found in Section VII.The middle curve is the estimated number imated by Ni-1.Hence,we set the value of pi as follows: of tags,Ni,with respect to the number pollings.It converges 1.594 to the true value N represented by the central straight line.The P1= (7) upper and lower curves represent the 95%confidence interval, N-1 which shrinks as the number of pollings increases. 2)Compute the value of Ni:We compute the new estimate D.Request-less Pollings of N that maximizes (3).Since the maxima is not affected by We observe that,after a number of pollings,the value of pi monotone transformations,we use logarithm to turn the right will stay in an increasingly small range and does not change side of the equation from product to summation: much.It becomes unnecessary for the reader to transmit it at each polling.Hence,we improve MLEA as follows:If In(Li 1-z)ln(1-p)+n(1-(1-p) the percentage change in pi during a certain number M of consecutive pollings is within a small threshold,the reader will broadcast the latest value of pi and indicate that it will no To find the maxima,we differentiate both sides: longer transmit polling requests (unless the value of p:changes beyond the threshold,in which case the reader will broadcast aln(Li) )血(1-)--p)1- the new value of pi one more time).Without receiving further 1-(1-p5)N polling requests,the tags will respond with the same contention (8) probability in the subsequent slots.This is called the request- We then set the right side to zero to solve for estimate Ni. less pollings.Note that the termination condition in (10) Note that the derivative is a monotone function of N.we can remains correct.With the threshold being 10%and M=10, numerically obtain Ni through the bisection search. the simulation results (which are omitted to save space)showcontention probability as follows before sending out the polling request: pi = ω Nˆ i−1 , (2) where Nˆ i−1 is the estimate after the previous polling and ω is a constant, which will be determined shortly. Second, based on the received zi and the history information, the reader finds the new estimate of N that maximizes the following likelihood function: Li = Y i j=1 (1 − pj ) N(1−zj ) (1 − (1 − pj ) N ) zj , (3) where (1−pj ) N(1−zj ) (1−(1−pj ) N ) zj is the probability that the state of the slot in the jth polling is zj . Namely, we want to find Nˆ i = arg max{Li} N . (4) Third, after computing Nˆ i , the reader has to determine if the confidence interval of the estimation meets the requirement. In the following, we show how the above tasks can be achieved. 1) Determine the Contention Probability: Using the δ−method [17], we derive the variance of Nˆ i in Appendix A. V ar(Nˆ i) ≈ 1 − (1 − pi) N i(1 − pi)N ln2 (1 − pi) . (5) When N is large and pi is small, we can approximate (1−pi) N as e −Npi and ln(1 − pi) as pi . The above variance becomes V ar(Nˆ i) ≈ e Npi − 1 ip2 i . (6) We pick the value of pi that minimizes V ar(Nˆ i). Differen￾tiating the right side of (6) and letting it be zero, we have pi = 1.594/N. Because MLE approach provides statistically consistent estimate, when i is large, N can be closely approx￾imated by Nˆ i−1. Hence, we set the value of pi as follows: pi = 1.594 Nˆ i−1 . (7) 2) Compute the value of Nˆ i: We compute the new estimate of N that maximizes (3). Since the maxima is not affected by monotone transformations, we use logarithm to turn the right side of the equation from product to summation: ln(Li) = X i j=1 · N(1 − zj ) ln(1 − pj ) + zj ln(1 − (1 − pj ) N ) ¸ . To find the maxima, we differentiate both sides: ∂ ln(Li) ∂N = Xi j=1 · (1 − zj ) ln(1 − pj ) − zj (1 − pj ) N ln(1 − pj ) 1 − (1 − pj )N ¸ . (8) We then set the right side to zero to solve for estimate Nˆ i . Note that the derivative is a monotone function of N, we can numerically obtain Nˆ i through the bisection search. 3) Termination Condition: We show in Appendix A that, when i is large, Nˆ i approximately follows the Gaussian distri￾bution: Normµ N, (1 − (1 − pi) N ) i(1 − pi)N ln2 (1 − pi) ¶ . According to (6), the variance of Nˆ i can be written as e Npi−1 ip2 i . Hence, the confidence interval of N is Nˆ i ± Zα · s eNˆipi − 1 ip2 i , (9) where Zα is the α percentile for the standard Gaussian distribu￾tion. For example, when α = 95%, Zα = 1.96. Because N is undetermined, we use Nˆ i as an approximation when computing the standard deviation in (9). The termination condition for EMLA is therefore Zα · s eNˆipi − 1 ip2 i ≤ Nˆ i · β, (10) where β is the error bound. The above inequality can be rewritten as √ i ≥ Zα p eNˆipi − 1 Nˆ ipiβ . (11) Because pi = 1.594/Nˆ i , we have i ≥ 1.544 · Z 2 α β 2 . (12) Hence we can theoretically compute the approximate number of pollings that is required in order to meet the accuracy requirements. For example, if α = 95% and β = 5%, 2372 pollings will be required. Note that (12) is independent with the actual number of tags, N. Hence, our approach has perfect scalability. Fig. 1 shows the simulation result of MLEA when N = 10, 000, α = 95% and β = 5%. The simulation setup can be found in Section VII. The middle curve is the estimated number of tags, Nˆ i , with respect to the number pollings. It converges to the true value N represented by the central straight line. The upper and lower curves represent the 95% confidence interval, which shrinks as the number of pollings increases. D. Request-less Pollings We observe that, after a number of pollings, the value of pi will stay in an increasingly small range and does not change much. It becomes unnecessary for the reader to transmit it at each polling. Hence, we improve MLEA as follows: If the percentage change in pi during a certain number M of consecutive pollings is within a small threshold, the reader will broadcast the latest value of pi and indicate that it will no longer transmit polling requests (unless the value of pi changes beyond the threshold, in which case the reader will broadcast the new value of pi one more time). Without receiving further polling requests, the tags will respond with the same contention probability in the subsequent slots. This is called the request￾less pollings. Note that the termination condition in (10) remains correct. With the threshold being 10% and M = 10, the simulation results (which are omitted to save space) show