XIE ET AL.:EFFICIENT PROTOCOLS FOR COLLECTING HISTOGRAMS IN LARGE-SCALE RFID SYSTEMS 2425 can use estimators in [9],[24],[32]etc.to estimate the overall Proof.See Appendix B,available in the online supple- tag size.Then,according to the response in each singleton slot, mental material. the category ID is obtained from the first s bits in the tag ID. Based on the sampling from the singleton slots,the tag size for each category can be estimated.The reason is as follows: 5.2.2 Reducing the Variance through Repeated Tests Assume that there exists m categories C1,C2,...,Cm,the As the frame size for each query cycle has a maximum overall tag size is n,and the tag size for each category is value,by estimating from the ensemble sampling within m,n2,...,nm.We define an indicator variable Xij to denote only one query cycle,the estimated tag size may not be whether one tag of category Ci selects a slot j inside the accurate enough for the accuracy constraint.In this situa- frame with the size f.We set Xij=1 if only one tag of cate- tion,multiple query cycles are essential to reduce the vari- gory Ci selects the slot j,and Xi.j=0 otherwise.Moreover, ance through repeated tests.Suppose the reader issues l we use Pr[Xij=1]to denote the probability that only one query cycles over the same set of categories,in regard to a tag of category Ci selects the slot j,then, specified category Ci,by utilizing the weighted statistical averaging method,the averaged tag size=n.k; here k= and respectively denote the esti If we use n.i to denote the number of singleton slots mated tag size and variance for each cycle k.Then,the vari- selected by tags of category Ci,thus n=then, ance ofs∑克 the expected value Therefore,according to the accuracy constraint in the problem formulation,we rely on the following theorem to express this constraint in the form of the variance. Theorem 2.Suppose the variance of the averaged tag size ni is o.The accuracy constraint is satisfied for a specified cate- Furthermore,let n,denote the number of singleton slots,the expected value E(n)=(1"n.Then,Thus 8onyC,as long as≤(z-e2.n,Zi-is the1-号per centile for the standard normal distribution. we can approximate the tag size of category Ci as follows: Proof.See Appendix C,available in the online supplemental 元，=n.元 material. ▣ (6) ns According to Theorem 2,we can verify if the accuracy Here,n is the estimated value of the overall tag size.Let constraint is satisfied for each category through directly d=hem元=：元 checking the variance against the threshold (If 1-B=95%,then Z1-/2=1.96. 5.2 Accuracy Analysis 5.2.1 Accuracy of the ES Estimator 5.2.3 Property of the Ensemble Sampling In the ensemble sampling-based estimation,since the esti- According to Theorem 1,the normalized variance of the SE mators such as [9],[24],[32]can be utilized for estimating estimator=产is equivalent to,k=告·=+ the overall number of tags,we use 8 to denote the variance +2e-.Leta=ne出，b=+ng-.Then,the nor- -(eP+n-1) of n.We have the property in Lemma 1. e+n-1 n-(eP+n-1) malized variance A:=a.+b.Since the SE estimator can Lemma 1.The number of singleton slots ns and the number of utilize any estimator like [9],[24],[32]to estimate the overall singleton slots nsi selected by the tags of category Ci,respec- tag size,then,without loss of generality,if we use the esti- tively,have the following expectations: mator in [9],we can prove that a<0 for any value of n >0,f>0.The following theorem shows this property in )=（-n+号(（1-)22-m the normalized variance. E(m)=（1-》·n+号.(（1-)·(m-m) Theorem 3.<for any walue of nf>0. Proof.See Appendix D,available in the online supplemen- Proof.See Appendix A,which can be found on the Computer tal material. Society Digital Library at http://doi.ieeecomputersociety. org/10.1109/TPDS.2014.2357021. This property applies to any estimator with variance 0 smaller than 8o in ZE,which simply estimates the overall We rely on the following theorem to illustrate the accu-tag size based on the observed number of empty slots. racy of the estimator SE. According to Theorem 3,in order to satisfy the accuracy Theorem 1.Let 8;represent the variance of the estimator SE, cosit,we should ensureAsforall the load factor p=then, values of f,it infers that the larger the value ni is,the faster it will be for the specified category to satisfy the accuracy con- n5eP+mi-1.(6+m2)-m 6= (7) straint.On the contrary,the smaller the value n;is,the slower n e+n-1 it will be for the specified category to satisfy the accuracycan use estimators in [9], [24], [32] etc. to estimate the overall tag size. Then, according to the response in each singleton slot, the category ID is obtained from the first s bits in the tag ID. Based on the sampling from the singleton slots, the tag size for each category can be estimated. The reason is as follows: Assume that there exists m categories C1; C2; ... ; Cm, the overall tag size is n, and the tag size for each category is n1; n2; ... ; nm. We define an indicator variable Xi;j to denote whether one tag of category Ci selects a slot j inside the frame with the size f. We set Xi;j ¼ 1 if only one tag of cate￾gory Ci selects the slot j, and Xi;j ¼ 0 otherwise. Moreover, we use Pr½Xi;j ¼ 1 to denote the probability that only one tag of category Ci selects the slot j, then, Pr½Xi;j ¼ 1 ¼ 1 f  1 1 f n1  ni: If we use ns;i to denote the number of singleton slots selected by tags of category Ci, thus ns;i ¼ Pf j¼1 Xi;j, then, the expected value Eðns;iÞ ¼ X f j¼1 Pr½Xi;j ¼ 1 ¼ 1 1 f n1  ni: Furthermore, let ns denote the number of singleton slots, the expected value EðnsÞ¼ð1 1 fÞ n1  n. Then, Eðns;iÞ EðnsÞ ¼ ni n . Thus we can approximate the tag size of category Ci as follows: nbi ¼ ns;i ns  n: b (6) Here, nb is the estimated value of the overall tag size. Let abi ¼ ns;i ns , then nbi ¼ abi  nb. 5.2 Accuracy Analysis 5.2.1 Accuracy of the ES Estimator In the ensemble sampling-based estimation, since the esti￾mators such as [9], [24], [32] can be utilized for estimating the overall number of tags, we use d to denote the variance of nb. We have the property in Lemma 1. Lemma 1. The number of singleton slots ns and the number of singleton slots ns;i selected by the tags of category Ci, respec￾tively, have the following expectations: Eðn2 s Þ ¼ 1 1 f  n1  n þ f1 f  1 2 f  n2  ðn2 nÞ; Eðn2 s;iÞ ¼ 1 1 f  n1  ni þ f1 f  1 2 f  n2  ðn2 i niÞ: 8 >< >: Proof. See Appendix A, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety. org/10.1109/TPDS.2014.2357021. tu We rely on the following theorem to illustrate the accu￾racy of the estimator SE. Theorem 1. Let di represent the variance of the estimator SE nbi, the load factor r ¼ n f, then, di ¼ ni n  er þ ni 1 er þ n 1  ðd þ n2 Þ n2 i : (7) Proof. See Appendix B, available in the online supple￾mental material. tu 5.2.2 Reducing the Variance through Repeated Tests As the frame size for each query cycle has a maximum value, by estimating from the ensemble sampling within only one query cycle, the estimated tag size may not be accurate enough for the accuracy constraint. In this situa￾tion, multiple query cycles are essential to reduce the vari￾ance through repeated tests. Suppose the reader issues l query cycles over the same set of categories, in regard to a specified category Ci, by utilizing the weighted statistical averaging method, the averaged tag size nbi ¼ Pl k¼1 vk  nci;k; here vk ¼ 1 d P i;k l k¼1 1 di;k , nci;k and di;k respectively denote the esti￾mated tag size and variance for each cycle k. Then, the vari￾ance of nbi is s2 i ¼ P 1 l k¼1 1 di;k . Therefore, according to the accuracy constraint in the problem formulation, we rely on the following theorem to express this constraint in the form of the variance. Theorem 2. Suppose the variance of the averaged tag size nbi is s2 i . The accuracy constraint is satisfied for a specified cate￾gory Ci, as long as s2 i  ð Z1b=2 Þ 2  n2 i , Z1b=2 is the 1 b 2 per￾centile for the standard normal distribution. Proof. See Appendix C, available in the online supplemental material. tu According to Theorem 2, we can verify if the accuracy constraint is satisfied for each category through directly checking the variance against the threshold ð Z1b=2 Þ 2  n2 i . If 1 b ¼ 95%, then Z1b=2 ¼ 1:96. 5.2.3 Property of the Ensemble Sampling According to Theorem 1, the normalized variance of the SE estimator i ¼ di ni is equivalent to i ¼ dner þ n er þ n 1  ni n þ ðd þ n2Þðer 1Þ nðer þ n 1Þ . Let a ¼ d ner þ n er þ n 1 , b ¼ ðd þ n2Þðer 1Þ nðer þ n 1Þ . Then, the nor￾malized variance i ¼ a  ni n þ b. Since the SE estimator can utilize any estimator like [9], [24], [32] to estimate the overall tag size, then, without loss of generality, if we use the esti￾mator in [9], we can prove that a < 0 for any value of n > 0;f> 0. The following theorem shows this property in the normalized variance. Theorem 3. d ner þ n er þ n 1 < 0 for any value of n > 0;f> 0. Proof. See Appendix D, available in the online supplemen￾tal material. tu This property applies to any estimator with variance smaller than d0 in ZE, which simply estimates the overall tag size based on the observed number of empty slots. According to Theorem 3, in order to satisfy the accuracy constraint, we should ensure i  ð Z1b=2 Þ 2  ni. As a < 0 for all values of f, it infers that the larger the value ni is, the faster it will be for the specified category to satisfy the accuracy con￾straint. On the contrary, the smaller the value ni is, the slower it will be for the specified category to satisfy the accuracy XIE ET AL.: EFFICIENT PROTOCOLS FOR COLLECTING HISTOGRAMS IN LARGE-SCALE RFID SYSTEMS 2425