5.2 Minimizing Number of Rounds n f arbitrarily small,theoretically,it will still be possible to Using optimal persistence probability pop,the two equa- obtain the estimate accurately:however.in this case.n can tions in(24)hold.From them,we get be prohibitively large making it practically impossible to obtain the estimate as per the accuracy requirements. kafty 2 -kot =n= μ{1+)}-μ{t} μ{(1-B)}-μ{ 5.4 Observably Constant Estimation Time (26) Let be the cumulative distribution function of a standard There are three inputs to ART:confidence interval B,re- normal distribution and erf{.}be the standard error func- quired reliability a,and a population of t tags where t is un- tion,we get known.The total estimation time of ART is(fop+3)x nop, P{-k≤Z≤k}=Φ()-(-)=erf which from our experiments we observe to be dependent (27) only on B and a,i.e.,(fop+3)x nop is constant with re spect to (w.r.t.)t.Because (fop+3)x nop is highly com- From Equations(23)and(27),we get plex due to complex components such as Cov(Y,R)as ex- k=v2 erf a} (28) pressed in Equation (9),we have not yet formally proven that (fop +3)x nop is independent of t,although we hy- From Equations(26)and(28),we get pothesize that this is mathematically true.Intuitively,the 2erf1{a×a{t2 =n= (-V2erf-1{a}×o{t larger t is,the smaller pop is.Although t plays an important role in computing pop,nop,and fop individually,in formula 、μ{(1+)}-μ{t μ{(1-)t母-μ{t母 (fop+3)x nop the impact of t gets canceled out.From Equa- (29) tions(29)and(31),we observe that the value of nop depends Based on this equation,with B,a,p Pop,t=tm,and upon a,B,u,a and value of fop depends upon B,u,a.Here f fop,we can calculate the minimal value nop for n. (fop+3)x nop is independent of t because a and B are given values and u and o are functions of gi,if g is independent of 5.3 Optimizing Frame Size f t.Indeed gi is intuitively independent of t because g 1/t Our goal of optimizing ART parameters,namely p,n,and and pop obtained from Equation(19)decreases as the value f,is to minimize the total estimation time,which is(f+3)x of tm increases,as shown in Figure 8.A constant value of nop.Because B,a,and tm are known and pop is a function gi means that the probability of any slot in a frame being of f,nop is essentially a function of f.Thus,(f+3)x nop non-empty is the same,which in turn implies that average is a function of f.Next,we show how to find the optimal run size in a frame will also be the same regardless of t.Fig- frame size fop so that (f+3)x nop is minimized. ure 9 plots the value of g w.r.t.t using Equations(19)and Function (f+3)x nop is a convex function of f as seen (1).We observe that the value of gi stays perfectly constant from Figure 7.This means that an optimal frame size fop w.r.t.t.Figure 10 shows that the total estimation time of exists and can be obtained by differentiating (f+3)x nop ART stays constant w.r.t.t for given B and a. with respect to f as shown in the following equation: 5.5 Obtaining Population Upper Bound ti 哥+)×n,}=0 (30) So far we have assumed the knowledge of an upper bound tm on tag population size t.In some applications,tm is read- ily available.For example,the number of TVs in a TV ware- As both expressions for n given in Equation(29)have the house can be reasonably estimated by the warehouse size same value when p =pop:either of them can be used to and minimum TV size.However,this may not be available calculate the value of nop.By substituting nop in Equation for some applications where the tag population size changes (30)by the L.H.S of the nop expression in Equation(29),we in large magnitude.We next present a fast scheme to ob- get tain tm based on Flajolet and Martin's probabilistic count- 4+}--b+ ing algorithm used in databases 5.Before running ART the reader uses this scheme to obtain tm.In this scheme, -27[u+a_g the reader keeps issuing single-slot frames,where the persis- (31 tence probability p follows a geometric distribution starting fromp=1 (i.e.,p=zr in the i-th frame),until the reader whereandare obtained through the differen- gets an empty slot.Suppose the empty slot occurred in the 3 i-th frame,then tm =1.2897 x 2i-2 is an upper bound on tiation of expressions for EX and Var(X)in Equations t[5,14 (14)and (15),respectively. To obtain of fop from Equation(31),we need the value of 5.6 ART with Multiple Readers Pop,while to obtain the value of pop from Equation(19),we We next discuss how to obtain tm and t using multiple need the value of fop.Therefore,we have two simultaneous readers whose covered regions may overlap.To obtain tm equations,(19)and (31),with two unknowns,fop and Pop. using multiple readers,we can let each reader obtain the t These equations can be numerically solved simultaneously value on its own and then sum them up as the final overall using Levenberg-Marquardt Algorithm to obtain the values tm because of two reasons.First,our requirement on tm is of fop and pop. only a rough upper bound estimate.Second,deployment of Note that the estimation scheme will still work if we do multiple readers in practice often requires site surveys to en- not use f =fop,but in that case the value of n will be sure minimal overlapping between readers.To use multiple such that the (f+3)x n will not be minimum.If we make readers to obtain t more precisely,we adapt the approach 3735.2 Minimizing Number of Rounds n Using optimal persistence probability pop, the two equa￾tions in (24) hold. From them, we get  kσ {t} μ {(1 + β)t} − μ {t} 2 = n =  −kσ {t} μ {(1 − β)t} − μ {t} 2 (26) Let Φ be the cumulative distribution function of a standard normal distribution and erf {.} be the standard error func￾tion, we get P {−k ≤ Z ≤ k} = Φ(k) − Φ(−k) = erf  k √2  (27) From Equations (23) and (27), we get k = √ 2 erf−1 {α} (28) From Equations (26) and (28), we get √2 erf−1 {α} × σ {t} μ {(1 + β)t} − μ {t} 2 =n= − √2 erf−1 {α} × σ {t} μ {(1 − β)t} − μ {t} 2 (29) Based on this equation, with β, α, p = pop, t = tm, and f = fop, we can calculate the minimal value nop for n. 5.3 Optimizing Frame Size f Our goal of optimizing ART parameters, namely p, n, and f, is to minimize the total estimation time, which is (f +3)× nop. Because β, α, and tm are known and pop is a function of f, nop is essentially a function of f. Thus, (f + 3) × nop is a function of f. Next, we show how to find the optimal frame size fop so that (f + 3) × nop is minimized. Function (f + 3) × nop is a convex function of f as seen from Figure 7. This means that an optimal frame size fop exists and can be obtained by differentiating (f + 3) × nop with respect to f as shown in the following equation: d df (f + 3) × nop = 0 (30) As both expressions for n given in Equation (29) have the same value when p = pop, either of them can be used to calculate the value of nop. By substituting nop in Equation (30) by the L.H.S of the nop expression in Equation (29), we get μ (1 + β)tm − μ tm  σ tm + 2f ∂σ tm ∂f  −2fσ tm ∂μ (1 + β)tm ∂f − ∂μ tm ∂f  = 0 (31) where ∂μ . ∂f and ∂σ . ∂f are obtained through the differen￾tiation of expressions for E[Xb] and Var(Xb) in Equations (14) and (15), respectively. To obtain of fop from Equation (31), we need the value of pop, while to obtain the value of pop from Equation (19), we need the value of fop. Therefore, we have two simultaneous equations, (19) and (31), with two unknowns, fop and pop. These equations can be numerically solved simultaneously using Levenberg-Marquardt Algorithm to obtain the values of fop and pop. Note that the estimation scheme will still work if we do not use f = fop, but in that case the value of n will be such that the (f + 3) × n will not be minimum. If we make f arbitrarily small, theoretically, it will still be possible to obtain the estimate accurately; however, in this case, n can be prohibitively large making it practically impossible to obtain the estimate as per the accuracy requirements. 5.4 Observably Constant Estimation Time There are three inputs to ART: confidence interval β, re￾quired reliability α, and a population of t tags where t is un￾known. The total estimation time of ART is (fop + 3) × nop, which from our experiments we observe to be dependent only on β and α, i.e., (fop + 3) × nop is constant with re￾spect to (w.r.t.) t. Because (fop + 3) × nop is highly com￾plex due to complex components such as Cov(Yb, Rb) as ex￾pressed in Equation (9), we have not yet formally proven that (fop + 3) × nop is independent of t, although we hy￾pothesize that this is mathematically true. Intuitively, the larger t is, the smaller pop is. Although t plays an important role in computing pop, nop, and fop individually, in formula (fop+3)×nop the impact of t gets canceled out. From Equa￾tions (29) and (31), we observe that the value of nop depends upon α, β, μ, σ and value of fop depends upon β, μ, σ. Here (fop + 3)×nop is independent of t because α and β are given values and μ and σ are functions of q1, if q1 is independent of t. Indeed q1 is intuitively independent of t because q1 ∝ 1/t and pop obtained from Equation (19) decreases as the value of tm increases, as shown in Figure 8. A constant value of q1 means that the probability of any slot in a frame being non-empty is the same, which in turn implies that average run size in a frame will also be the same regardless of t. Fig￾ure 9 plots the value of q1 w.r.t. t using Equations (19) and (1). We observe that the value of q1 stays perfectly constant w.r.t. t. Figure 10 shows that the total estimation time of ART stays constant w.r.t. t for given β and α. 5.5 Obtaining Population Upper Bound tm So far we have assumed the knowledge of an upper bound tm on tag population size t. In some applications, tm is read￾ily available. For example, the number of TVs in a TV ware￾house can be reasonably estimated by the warehouse size and minimum TV size. However, this may not be available for some applications where the tag population size changes in large magnitude. We next present a fast scheme to ob￾tain tm based on Flajolet and Martin’s probabilistic count￾ing algorithm used in databases [5]. Before running ART, the reader uses this scheme to obtain tm. In this scheme, the reader keeps issuing single-slot frames, where the persis￾tence probability p follows a geometric distribution starting from p =1(i.e., p = 1 2i−1 in the i-th frame), until the reader gets an empty slot. Suppose the empty slot occurred in the i-th frame, then tm = 1.2897 × 2i−2 is an upper bound on t [5, 14]. 5.6 ART with Multiple Readers We next discuss how to obtain tm and t ˜ using multiple readers whose covered regions may overlap. To obtain tm using multiple readers, we can let each reader obtain the tm value on its own and then sum them up as the final overall tm because of two reasons. First, our requirement on tm is only a rough upper bound estimate. Second, deployment of multiple readers in practice often requires site surveys to en￾sure minimal overlapping between readers. To use multiple readers to obtain t ˜ more precisely, we adapt the approach 373