TABLE I FNEB KEY NOTATIONS Symbols Descriptions 234567890▣ n Actual number of tags Oin) ZOE 公 Estimated number of tags 20E OR 12345678 m Estimation rounds P H) A uniform hash function O(log n) 0(1) HB(.) Binary representation of (. ☐Idle slot ☐Busy slot R() Position of right-most zero in HB(.) (a)Estimation frame and interested slot (b)One aggregated slot A threshold affecting the behavior of tags Fig.1.An illustrative comparison of ZOE with conventional schemes of 入 Load factor n/20 FNEB,LoF and PET. Channel error rate cardinality estimation,we present detailed theoretical analysis A.Principle and consolidate the aforementioned design principle with a prototype system in the following. The conventional approaches take advantage of the frame- slotted Aloha protocol to estimate the number of tags.The B.Zero-One Estimator protocol RFID reader normally needs to examine the state of each time slot in the frame.Figure 1(a)presents illustrative examples of We describe the detailed ZOE protocol in this section. most recent protocols,e.g.,FNEB [11].LoF [16],and PET 1)Tag:When probed by a reader in the cardinality esti- [27].In FNEB,each tag randomly selects a slot from O(n) mation process,each tag independently computes a random slots with uniform distribution functions to send a response number with a uniform distribution hash function (id,s), in each estimation round.If the frame size is fixed,then the where s denotes a random seed.For simplicity,we omit the first busy slot (herein,slot 3)indicates the tag population (i.e., notation of s for the hash functions.We denote by HB(id)the the smaller the first busy slot is,the larger the tag population binary representation of H(id).We also denote by R(id)the would be).Leveraging the monotonic feature,FNEB locates index of the right-most zero bit in HB(id)as follows the first busy slot by examining O(logn)slots.LoF and R(id)=min{iHB(id)[i]=0}. (1) PET reduce the frame size to O(logn)by letting each tag If R(idi)>the tag responds to the reader where 6 is a select a slot with geometric distribution functions,such that threshold received from the reader;and if R(id)<0 the tag nearly 1/2i of tags respond in the ith slot.PET achieves keeps silent. O(log log n)time efficiency leveraging a probabilistic binary Let the random variable of R(id;)be Ri,1<i<n,then tree structure.The estimation results of such protocols may we have the probability statistically vary for each estimation round.For instance.the Pr(Ri)=pR(1-p), first busy slot in one estimation round might dramatically deviate from the expected value.Existing protocols thus need where p denotes the probability that a bit of HB(id)turns many independent estimation rounds to derive an average to out to be '1'.Typically,we assume p=0.5,i.e.,the hash accurately approximate the actual number of tags. function is a uniform distribution hash function.Then we have To improve the estimation efficiency,we propose the ZOE p=1-p=0.5,and protocol in which each frame only contains one slot.In particular,all the responses from tags aggregate at a single Pr(Ra)=p= slot,leading to either an idle slot if no tag responds or a busy The probability that a tag keeps silent given a threshold slot otherwise as illustrated in Figure 1(b).Suppose there exist 0-1 8-1 n RFID tags,and each tag responds with the probability of P,and keeps silent with the probability of 1-P.Intuitively, P(,<)=∑Pr(=∑2=1-2 k=0 k=0 the more tags there are,the higher probability that the reader observes a busy slot,and vice versa.We can thus measure the On the other hand,a tag will respond to the reader with the ratio of busy (idle)slots,and infer the tag population with a probability of 1-Pr(Ri<0)=. priori knowledge of P. 2)Reader:a reader initiates cardinality estimation by send- Unlike conventional approaches where only small portion ing a random seed and the threshold 0 to the tags,and waits of tags participate in each time slot,in ZOE the responses for the responses from the tags.In the case that R(id;)<, from all the tags aggregate in the single time slot,which ∀i∈{1,2，.，n,the reader observes no reply from the tags.Therefore,with the assumption of independent,identical allows ZOE to make extensive use of each time slot,thereby achieving higher time efficiency.By intelligently setting the distribution (i.i.d)for Ri,the probability that there is no reply system parameters,ZOE only needs comparable number of from the tags (i.e.,the channel is idle)is as follows estimation rounds with conventional approaches,meaning that 1 ≈e~n/2e =e-入， we reduce the overhead in each estimation round to O(1) Pr(ide=Pr(R:<]”=（1-2p while keeping the number of estimation rounds similar to where the load factor入=n/2,and入>0. those in conventional approaches.Towards the more efficient The probability that there is a reply (no matter a singletonTABLE I KEY NOTATIONS Symbols Descriptions n Actual number of tags nˆ Estimated number of tags m Estimation rounds H(.) A uniform hash function HB(.) Binary representation of H(.) R(.) Position of right-most zero in HB(.) θ A threshold affecting the behavior of tags λ Load factor n/2 θ q Channel error rate A. Principle The conventional approaches take advantage of the frame￾slotted Aloha protocol to estimate the number of tags. The RFID reader normally needs to examine the state of each time slot in the frame. Figure 1(a) presents illustrative examples of most recent protocols, e.g., FNEB [11], LoF [16], and PET [27]. In FNEB, each tag randomly selects a slot from O(n) slots with uniform distribution functions to send a response in each estimation round. If the frame size is fixed, then the first busy slot (herein, slot 3) indicates the tag population (i.e., the smaller the first busy slot is, the larger the tag population would be). Leveraging the monotonic feature, FNEB locates the first busy slot by examining O(log n) slots. LoF and PET reduce the frame size to O(log n) by letting each tag select a slot with geometric distribution functions, such that nearly 1/2 i of tags respond in the ith slot. PET achieves O(log log n) time efficiency leveraging a probabilistic binary tree structure. The estimation results of such protocols may statistically vary for each estimation round. For instance, the first busy slot in one estimation round might dramatically deviate from the expected value. Existing protocols thus need many independent estimation rounds to derive an average to accurately approximate the actual number of tags. To improve the estimation efficiency, we propose the ZOE protocol in which each frame only contains one slot. In particular, all the responses from tags aggregate at a single slot, leading to either an idle slot if no tag responds or a busy slot otherwise as illustrated in Figure 1(b). Suppose there exist n RFID tags, and each tag responds with the probability of P, and keeps silent with the probability of 1 − P. Intuitively, the more tags there are, the higher probability that the reader observes a busy slot, and vice versa. We can thus measure the ratio of busy (idle) slots, and infer the tag population with a priori knowledge of P. Unlike conventional approaches where only small portion of tags participate in each time slot, in ZOE the responses from all the tags aggregate in the single time slot, which allows ZOE to make extensive use of each time slot, thereby achieving higher time efficiency. By intelligently setting the system parameters, ZOE only needs comparable number of estimation rounds with conventional approaches, meaning that we reduce the overhead in each estimation round to O(1) while keeping the number of estimation rounds similar to those in conventional approaches. Towards the more efficient LoF PET FNEB 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 ZOE 1 Idle slot Busy slot (a) Estimation frame and interested slot LoF PET FNEB 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 ZOE Idle slot Busy slot id1 id2 idn ... id3 id4 OR P P P P P P ZOE id1 id2 idn OR P P P P id3 P id4 ... P ZOE id1 id2 idn OR P P P P id3 P id4 ... P (b) One aggregated slot Fig. 1. An illustrative comparison of ZOE with conventional schemes of FNEB, LoF and PET. cardinality estimation, we present detailed theoretical analysis and consolidate the aforementioned design principle with a prototype system in the following. B. Zero-One Estimator protocol We describe the detailed ZOE protocol in this section. 1) Tag: When probed by a reader in the cardinality esti￾mation process, each tag independently computes a random number with a uniform distribution hash function H(id, s), where s denotes a random seed. For simplicity, we omit the notation of s for the hash functions. We denote by HB(id) the binary representation of H(id). We also denote by R(id) the index of the right-most zero bit in HB(id) as follows R(id) = min{i|HB(id)[i] = 0}. (1) If R(idi) ≥ θ the tag responds to the reader where θ is a threshold received from the reader; and if R(idi) < θ the tag keeps silent. Let the random variable of R(idi) be Ri , 1 ≤ i ≤ n, then we have the probability Pr(Ri) = p Ri (1 − p), where p denotes the probability that a bit of HB(id) turns out to be ‘1’. Typically, we assume p = 0.5, i.e., the hash function is a uniform distribution hash function. Then we have p = 1 − p = 0.5, and Pr(Ri) = p Ri+1 = 1 2Ri+1 . The probability that a tag keeps silent given a threshold θ is Pr(Ri < θ) = X θ−1 k=0 Pr(k) =X θ−1 k=0 1 2 k+1 = 1 − 1 2 θ . On the other hand, a tag will respond to the reader with the probability of 1 − Pr(Ri < θ) = 1 2 θ . 2) Reader: a reader initiates cardinality estimation by send￾ing a random seed and the threshold θ to the tags, and waits for the responses from the tags. In the case that R(idi) < θ, ∀i ∈ {1, 2, . . . , n}, the reader observes no reply from the tags. Therefore, with the assumption of independent, identical distribution (i.i.d) for Ri , the probability that there is no reply from the tags (i.e., the channel is idle) is as follows Pr(idle) = [Pr(Ri < θ)]n =  1 − 1 2 θ n ≈ e −n/2 θ = e −λ , where the load factor λ = n/2 θ , and λ > 0. The probability that there is a reply (no matter a singleton