Algorithm 1 ZOE algorithm for RFID readers requirement can be represented as follows ca(x)ma 1:m←[exa P Pr{li-ml≤en}=Pr{e-1+e)≤≤e-A-e. 2:Initiate the estimation,broadcast 0 3:fori←1 to m do We define a random variable Y=where 4: Generate a random seed s and broadcast it E(X)=e-入，anda=o()=g9.By the central limit Vm 5: if there is no response in the slot then theorem [10],we know Y is asymptotically standard normal 6: X:←-1 distribution. 7: else 8: X:←-0 Given a particular error probability 6.we can find a constant 9: end if c that satisfies 10:end for 1:←品∑X -6=Pr-e≤y≤c=rf(5) 12:return←-29ln where erf is the Gaussian error function [10].Therefore,we can guarantee the accuracy requirement Prn-n<en}> Algorithm 2 ZOE algorithm for each RFID tag 1-6 if we have the following conditions 1:Receive the threshold 0 e-X(1+e)-e-X 2:while TRUE do ≤-c and e-A1-e)-e-H ≥c.(4) 3: Receive the random seed s;Compute R(id) ifR(id)≥0 then According to (4),we have 5: Respond immediately 6: else w2m 7: Keep silent 8: end if 9:end while ≥ (5) Therefore,with such m estimation frames,ZOE can guar- reply from one tag or replies from multiple tags)is antee the accuracy requirement of Pr{-n<en}>1-6. Pr(reply)=1-Pr(idle)≈1-e-n/2°=1-e-A Algorithm 1 regulates the behavior of the RFID reader.The reader calculates the estimation rounds m according to (5) We define a random variable X which takes value 1 with probability Pr(idle)e-n/2 given an accuracy requirement (line 1).The reader initiates e-and value 0 with probability Pr(reply)1-e-/2=1-e-.Then we the estimation process by energizing the tags and sending the threshold 6(line 2).The reader generates random seeds and have broadcasts them (line 3-4),and records the tags'responses Pr(X=1)≈e-入，Pr(X=0)≈1-e-A (line 5-9).The average X is thus calculated based on the Obviously,the random variable X follows the Bernoulli dis- m estimation rounds (line 11).Finally,the estimated tag tribution.Therefore,the expectation and the standard deviation cardinality is computed according to (3)(line 12). of X are as follows Each tag performs simple tasks as regulated in Algorithm E(X)=e-入，o(X)=VWar(X)=Ve-A(1-e-λ) 2.In each estimation round,when receiving a random seed s,the tag computes the random number R(id)according to The maximum standard deviation of X is (1).The tag keeps silent or responds to the reader according a(X)max =0.5,when e-=0.5. to R(id)and the threshold 0.If R(id)>the tag sends a We define the random process as the response,and otherwise keeps silent (line 2-9). 2 Yet one problem remains.In (5),we see that m depends on average of m independent observations,where Xi denotes the ith observation of random variable X.We assume the trials A=n/20 indicating that the threshold 0 may influence the of Xi(1<i<m)are i.i.d,then we have E(X)=E(X)and estimation efficiency.In the following,we discuss how to set (X)=N the threshold to guarantee the optimal performance of ZOE. m According to the law of large numbers [10],when m is C.Parameter setting large we have =E()=E(X)=e-n/2°=e-A Before we perform the estimation process,we need to set (2) the threshold 0 which directly influences the behaviors of the According to (2),we can estimate the load factor as follows tags and the estimation efficiency.If is too big,the reader 入=-lnx, will consistently observe idle slots,i.e.,X 1;if 0 is too where入denotes the estimation of入. small,the reader will observe busy slots in almost every time slots,i.e.,X=0,with high probability.In either situation,it The observation of can thus be used to estimate the tag consumes extra processing time to meet an accuracy require- cardinality n as follows ment.As a matter of fact,if we look at the lower bound of =-20 In. (3) the estimation round m measured in(⑤)，since入=n/2e,the Since the result may vary slightly because of the estimation lower bound depends on the tag cardinality which is not known variance,we seek a guaranteed cardinality estimation result, in advance.We denote by f()=e-(l-e-ea)≈e-xe入， e.g.,Pr-n<En}>1-6.The estimation accuracy the denominator of in (5).To reduce the numberAlgorithm 1 ZOE algorithm for RFID readers 1: m ← [ cσ(X)max e−λ(1−e−ελ) ] 2 2: Initiate the estimation, broadcast θ 3: for i ← 1 to m do 4: Generate a random seed s and broadcast it 5: if there is no response in the slot then 6: Xi ← 1 7: else 8: Xi ← 0 9: end if 10: end for 11: X¯ ← 1 m Pm i=1 Xi 12: return nˆ ← −2 θ ln X¯ Algorithm 2 ZOE algorithm for each RFID tag 1: Receive the threshold θ 2: while TRUE do 3: Receive the random seed s; Compute R(id) 4: if R(id) ≥ θ then 5: Respond immediately 6: else 7: Keep silent 8: end if 9: end while reply from one tag or replies from multiple tags) is Pr(reply) = 1 − Pr(idle) ≈ 1 − e −n/2 θ = 1 − e −λ . We define a random variable X which takes value 1 with probability Pr(idle) ≈ e −n/2 θ = e −λ and value 0 with probability Pr(reply) ≈ 1 − e −n/2 θ = 1 − e −λ . Then we have Pr(X = 1) ≈ e −λ ,Pr(X = 0) ≈ 1 − e −λ . Obviously, the random variable X follows the Bernoulli dis￾tribution. Therefore, the expectation and the standard deviation of X are as follows E(X) = e −λ , σ(X) = p V ar(X) = q e−λ(1 − e−λ). The maximum standard deviation of X is σ(X)max = 0.5, when e −λ = 0.5. We define the random process X¯ = 1 m Pm i=1 Xi as the average of m independent observations, where Xi denotes the ith observation of random variable X. We assume the trials of Xi(1 ≤ i ≤ m) are i.i.d, then we have E(X¯) = E(X) and σ(X¯) = σ(X) √m . According to the law of large numbers [10], when m is large we have X¯ = E(X¯) = E(X) = e −n/2 θ = e −λ . (2) According to (2), we can estimate the load factor as follows λˆ = − ln X, ¯ where λˆ denotes the estimation of λ. The observation of X¯ can thus be used to estimate the tag cardinality nˆ as follows nˆ = −2 θ ln X. ¯ (3) Since the result may vary slightly because of the estimation variance, we seek a guaranteed cardinality estimation result, e.g., P r{|nˆ − n| ≤ εn} ≥ 1 − δ. The estimation accuracy requirement can be represented as follows Pr{|nˆ − n| ≤ εn} = Pr{e −λ(1+ε) ≤ X¯ ≤ e −λ(1−ε) }. We define a random variable Y = X¯−µ σ , where µ = E(X¯) = e −λ , and σ = σ(X¯) = σ(X) √m . By the central limit theorem [10], we know Y is asymptotically standard normal distribution. Given a particular error probability δ, we can find a constant c that satisfies 1 − δ = Pr{−c ≤ Y ≤ c} = erf( c √ 2 ), where erf is the Gaussian error function [10]. Therefore, we can guarantee the accuracy requirement P r{|nˆ − n| ≤ εn} ≥ 1 − δ if we have the following conditions e −λ(1+ε) − e −λ σ ≤ −c and e −λ(1−ε) − e −λ σ ≥ c. (4) According to (4), we have m ≥ max{[ cσ(X)max e−λ(1 − e−ελ) ] 2 , [ cσ(X)max e−λ(e ελ − 1)] 2 } ≥ [ cσ(X)max e−λ(1 − e−ελ) ] 2 . (5) Therefore, with such m estimation frames, ZOE can guar￾antee the accuracy requirement of P r{|nˆ −n| ≤ εn} ≥ 1−δ. Algorithm 1 regulates the behavior of the RFID reader. The reader calculates the estimation rounds m according to (5) given an accuracy requirement (line 1). The reader initiates the estimation process by energizing the tags and sending the threshold θ (line 2). The reader generates random seeds and broadcasts them (line 3-4), and records the tags’ responses (line 5-9). The average X¯ is thus calculated based on the m estimation rounds (line 11). Finally, the estimated tag cardinality is computed according to (3) (line 12). Each tag performs simple tasks as regulated in Algorithm 2. In each estimation round, when receiving a random seed s, the tag computes the random number R(id) according to (1). The tag keeps silent or responds to the reader according to R(id) and the threshold θ. If R(id) ≥ θ the tag sends a response, and otherwise keeps silent (line 2-9). Yet one problem remains. In (5), we see that m depends on λ = n/2 θ indicating that the threshold θ may influence the estimation efficiency. In the following, we discuss how to set the threshold to guarantee the optimal performance of ZOE. C. Parameter setting Before we perform the estimation process, we need to set the threshold θ which directly influences the behaviors of the tags and the estimation efficiency. If θ is too big, the reader will consistently observe idle slots, i.e., X¯ = 1; if θ is too small, the reader will observe busy slots in almost every time slots, i.e., X¯ = 0, with high probability. In either situation, it consumes extra processing time to meet an accuracy require￾ment. As a matter of fact, if we look at the lower bound of the estimation round m measured in (5), since λ = n/2 θ , the lower bound depends on the tag cardinality which is not known in advance. We denote by f(λ) = e −λ (1 − e −ελ) ≈ e −λ ελ, the denominator of cσ(X)max e−λ(1−e−ελ) in (5). To reduce the number