2013 Proceedings IEEE INFOCOM of(4)月 That is, n)=a-月a1-月+kn(-》 -≥T +(m-z)1-1-子)”-*1-清 n(号) (6) (12) Differentiating both sides of the above equation,we have 空≤m片Pu- 兴-加”护 Let C=wm()T(1-)".Therefore.the probability for the reader to report a group is Prob(k T)= xaa-品-h- (7) Prob(∑1xi≤C): From (2),we know that zi follows the binomial After setting the right side to zero and simplifying it,we distribution with parameters m and (1-)(1-): have the following estimator, (之 Bind(m.(( (13) (8) Since a binomial distribution Bino(a,b)can be excellently 血（季 approximated by a normal distribution Norm(ab,ab(1-b)) when a is large enough (which is the case for m),(13)can In (7),m and f are given parameters whose values are be approximately written as pre-computed by the reader.The values of zi,1 <i<m, are obtained from LBi(g).The total number n of tags can be estimated from the bitmaps,Bi,1<i<w.Let Xi be the 心Nomm-》-*- number of zeros in Bi.The probability for each tag to set a bit in Bi to '1'is.The probability for each bit to remain m1-子-*1--a-→"-*1-》.4 zero is approximately (1-)".The likelihood function for According to (14),we know us to observe Xi zeros in B,1≤i≤w,is c=Ⅱ1-nx(1-1-y-x (9) 之4~amml-r-a-大 Using the maximum likelihood estimation,we take the mu1-子-1-品产-a-分”-*a-点 logarithm of both sides,differentiate it,and then let the right (15) side be zero.We have Let u mw(1-)m-k(1-)k and o2 mw(1- -f-护=0 )-k(1-)k(1-(1-)n-k(1).then we have (16) n= (10) n(1-7)） Thus, where Xi,l≤i≤w,are obtained from Bi. Prob(k≥T)=Pro∑≤C) For each group g,after we estimate its population k based 11 on(8).we report the group(as an above-threshold group)if C k>T.where T is another system parameter that will be (17) determined in the next subsection based on the probabilistic performance objectives (1). The first performance objective in (1)can be translated E.Parameter-Precomputing Phase into Prob(k≥Tlk≥h)≥a,which is We first develop the constraints that the system parameters 、ae—2a 1 -(1-4)2 must satisfy in order to achieve the probabilistic performance (18) objectives.Based on the constraints,we determine the optimal values for the length m of logical bitmaps,the where k h.Since the left side of the inequality is an number w of pollings,the frame size f,and the parameter increasing function of k,we can replace the term k with h. T. Then,we have the first constraint for the system parameters. A group g whose estimated population is k will be reported C -(1-)2 if (19) k>T. (11) 895of (4): ln(L) = w i=1  xi((n − k) ln(1 − 1 f ) + k ln(1 − 1 m)) + (m − xi) ln(1 − (1 − 1 f ) n−k(1 − 1 m) k)) . (6) Differentiating both sides of the above equation, we have ∂ lnL ∂k = w i=1  ( xi − m(1 − 1 f )n−k(1 − 1 m)k 1 − (1 − 1 f )n−k(1 − 1 m )k ) × (ln(1 − 1 m) − ln(1 − 1 f )) . (7) After setting the right side to zero and simplifying it, we have the following estimator, ˆ k = ln( w i=1 xi mw(1− 1 f )n ) ln( 1− 1 m 1− 1 f ) . (8) In (7), m and f are given parameters whose values are pre-computed by the reader. The values of xi, 1 ≤ i ≤ m, are obtained from LBi(g). The total number n of tags can be estimated from the bitmaps, Bi, 1 ≤ i ≤ w. Let Xi be the number of zeros in Bi. The probability for each tag to set a bit in Bi to ‘1’ is 1 f . The probability for each bit to remain zero is approximately (1 − 1 f )n. The likelihood function for us to observe Xi zeros in Bi, 1 ≤ i ≤ w, is L = w i=1 (1 − 1 f ) nXi (1 − (1 − 1 f ) n) f−Xi (9) Using the maximum likelihood estimation, we take the logarithm of both sides, differentiate it, and then let the right side be zero. We have w i=1 Xi − wf(1 − 1 f ) n = 0 n = ln w i=1 Xi wf ln(1 − 1 f ) , (10) where Xi, 1 ≤ i ≤ w, are obtained from Bi. For each group g, after we estimate its population ˆ k based on (8), we report the group (as an above-threshold group) if ˆ k ≥ T , where T is another system parameter that will be determined in the next subsection based on the probabilistic performance objectives (1). E. Parameter-Precomputing Phase We first develop the constraints that the system parameters must satisfy in order to achieve the probabilistic performance objectives. Based on the constraints, we determine the optimal values for the length m of logical bitmaps, the number w of pollings, the frame size f, and the parameter T . A group g whose estimated population is ˆ k will be reported if ˆ k ≥ T. (11) That is, ln( w i=1 xi mw(1− 1 f )n ) ln( 1− 1 m 1− 1 f ) ≥ T w i=1 xi ≤ wm( 1 − 1 m 1 − 1 f ) T (1 − 1 f ) n. (12) Let C = wm( 1− 1 m 1− 1 f )T (1 − 1 f )n. Therefore, the probability for the reader to report a group is P rob(ˆ k ≥ T ) = P rob( w i=1 xi ≤ C). From (2), we know that xi follows the binomial distribution with parameters m and (1 − 1 f )n−k(1 − 1 m )k: xi ∼ Bino(m,(1 − 1 f ) n−k(1 − 1 m) k). (13) Since a binomial distribution Bino(a, b) can be excellently approximated by a normal distribution Norm(ab, ab(1 − b)) when a is large enough (which is the case for m), (13) can be approximately written as xi ∼ Norm(m(1 − 1 f ) n−k(1 − 1 m) k, m(1 − 1 f ) n−k(1 − 1 m) k(1 − (1 − 1 f ) n−k(1 − 1 m) k)). (14) According to (14), we know w i=1 xi ∼ Norm(mw(1 − 1 f ) n−k(1 − 1 m) k, mw(1 − 1 f ) n−k(1 − 1 m) k(1 − (1 − 1 f ) n−k(1 − 1 m) k)). (15) Let μ = mw(1 − 1 f )n−k(1 − 1 m )k and σ2 = mw(1 − 1 f )n−k(1 − 1 m )k(1 − (1 − 1 f )n−k(1 − 1 m)k), then we have P rob( w i=1 xi = j) = 1 √ 2πσ2 e −(j−μ)2 2σ2 (16) Thus, P rob(ˆ k ≥ T ) = P ro( w i=1 xi ≤ C) =  C j=0 1 √ 2πσ2 e −(j−μ)2 2σ2 (17) The first performance objective in (1) can be translated into P rob(ˆ k ≥ T |k ≥ h) ≥ α, which is  C j=0 1 √ 2πσ2 e −(j−μ)2 2σ2 ≥ α (18) where k ≥ h. Since the left side of the inequality is an increasing function of k, we can replace the term k with h. Then, we have the first constraint for the system parameters.  C j=0 1 √2πσ12 e −(j−μ1)2 2σ12 ≥ α, (19) 2013 Proceedings IEEE INFOCOM 895