2013 Proceedings IEEE INFOCOM where ui mw(1-)n-h(1-)h and 012 u(1-(1- identifies populous groups whose sizes are larger than a )-(1-品)) threshold. Similarly,the second performance objective in (1)can be Our simulation setting is based on the Philips I-Code translated into the following constraint, specification [22].Any two consecutive transmissions(from a reader to tags or from a tag to the reader)are separated by a 1 e ≤B, (20) waiting time of 0.302 ms.According to the specification,the transmission rate from a tag to the reader is different from the transmission rate from the reader to a tag.The rate from where u2=mw(1-)-(1-)and 22=u2(1-(1-a tag to the reader is 53 Kb/sec;it takes 0.018 ms for a tag )m-(1-a). to transmit one bit.The length of a slot is calculated as the Our goal is to find optimal system parameters that sum of a waiting time and the time for the tag to transmit minimize the execution time required by TBC,i.e.,w x f, a certain number of bits.Since the type of slots used by subject to the above two constraints. TBC and Enhanced FNEB,Tshort,contains only one bit,the slot length is 0.321 ms.The type of slots used by UPE and GT needs to detect collision and contains 10 bits.Their slot Minimize w×f, 21) length is Tiong=0.49ms.Comparing with the time used by C 1 tags to transmit to the reader,the time used by the reader to subject to 211 0V2m京 transmit to the tags are negligible in all four protocols. In our simulation,n =500,000,the range of group sizes 1 -(1-42)2 is (0.500].h =250,and the value of l varies.There 2022 0V2m02 are 2,000 groups,and the number z of above-threshold(h) groups may vary in simulation,but its default value is 1 C =mw(- 1,000.First,we randomly choose the sizes for the above- 1- threshold groups from[250,500].After that,we distribute the remaining M tags into the below-threshold groups.For the 1=mw(1 n-h(1-二)》 first below-threshold group,we generate a random number between 1 and min49.tobe its population,which 2=1-1-m-1-) is denoted as s1.For the second below-threshold group,we select a random value between I and min{49,as 2=m(1- --》 its population,which is denoted as s2.Similarly,we assign a random value between 1 and min(249,)as the 2=1-1--1- population for the third below-threshold group.This process m is repeated for all remaining below-threshold groups.If there The parameters h,l,a and B are given by the performance are still tags left unassigned,we assign them arbitrarily to objectives (1).To solve the above constrained optimization below-threshold groups as long as their sizes are below 250. problem,we need to determine the optimal values of the For each simulation,TBC will compute the optimal value remaining four system parameters w,f,m and T,such that of w x f (together with the optimal system parameters). w x f is minimized.Since all these parameters are bounded Once w x f is determined,the execution time is known, integers,we may find the optimal set of parameters by which is Tshort x w x f plus the time for broadcasting exhaustive search,which occurs offline before the TBC polling requests.GT will also compute its optimal system protocol is executed.The computation process includes four parameters,including the time frame size f,the number R loops to enumerate all possible discrete values for the four of rounds,and the number W of shuffled groups W.The parameters. execution time required by GT is Tiong×f×W×R.UPE and Enhanced FNEB work under the settings based on their V.NUMERICAL RESULTS original papers.Their execution times are the sum of the A.Setting times for measuring the populations of individual groups. We evaluate the performance of TBC and compare it B.Execution time required in terms of a,B and I/h with the existing work,including the Unified Probabilistic We compare TBC,GT,UPE and Enhanced FNEB in terms Estimator(UPE)[12],the Enhanced First Non-Empty slots of execution time.Tables II-IV show our simulation results Based Estimator (Enhanced FNEB)[20],and the Group under different values of l/h,a and B. Testing(GT)[2].UPE and Enhanced FNEB are designed for Table II shows the execution time required when a =99% RFID population estimation,not for satisfying the probability and B=1%.From the table,we can see that TBC has a much performance objectives in(1).However,the estimation results smaller execution time than GT,UPE and Enhanced FNEB. from these two estimators can be used for classification by GT takes 1'14"when I =0.1h,which is 3.09 times of TBC. reporting those groups whose estimated sizes are above a UPE and Enhanced FNEB consume an order of magnitude threshold.GT is the most related work.It probabilistically or more time than GT and TBC. 896where μ1 = mw(1− 1 f )n−h(1− 1 m )h and σ1 2 = μ1(1−(1− 1 f )n−h(1 − 1 m )h). Similarly, the second performance objective in (1) can be translated into the following constraint,  C j=0 1 √2πσ22 e −(j−μ2)2 2σ22 ≤ β, (20) where μ2 = mw(1 − 1 f )n−l (1 − 1 m )l and σ2 2 = μ2(1 − (1 − 1 f )n−l (1 − 1 m )l ). Our goal is to find optimal system parameters that minimize the execution time required by TBC, i.e., w × f, subject to the above two constraints. Minimize w × f, (21) subject to  C j=0 1 √2πσ12 e −(j−μ1)2 2σ12 ≥ α  C j=0 1 √2πσ22 e −(j−μ2)2 2σ22 ≤ β C = mw( 1 − 1 m 1 − 1 f ) T (1 − 1 f ) n μ1 = mw(1 − 1 f ) n−h(1 − 1 m) h σ1 2 = μ1(1 − (1 − 1 f ) n−h(1 − 1 m) h) μ2 = mw(1 − 1 f ) n−l (1 − 1 m) l σ2 2 = μ2(1 − (1 − 1 f ) n−l (1 − 1 m) l ). The parameters h, l, α and β are given by the performance objectives (1). To solve the above constrained optimization problem, we need to determine the optimal values of the remaining four system parameters w, f, m and T , such that w × f is minimized. Since all these parameters are bounded integers, we may find the optimal set of parameters by exhaustive search, which occurs offline before the TBC protocol is executed. The computation process includes four loops to enumerate all possible discrete values for the four parameters. V. NUMERICAL RESULTS A. Setting We evaluate the performance of TBC and compare it with the existing work, including the Unified Probabilistic Estimator (UPE) [12], the Enhanced First Non-Empty slots Based Estimator (Enhanced FNEB) [20], and the Group Testing (GT) [2]. UPE and Enhanced FNEB are designed for RFID population estimation, not for satisfying the probability performance objectives in (1). However, the estimation results from these two estimators can be used for classification by reporting those groups whose estimated sizes are above a threshold. GT is the most related work. It probabilistically identifies populous groups whose sizes are larger than a threshold. Our simulation setting is based on the Philips I-Code specification [22]. Any two consecutive transmissions (from a reader to tags or from a tag to the reader) are separated by a waiting time of 0.302 ms. According to the specification, the transmission rate from a tag to the reader is different from the transmission rate from the reader to a tag. The rate from a tag to the reader is 53 Kb/sec; it takes 0.018 ms for a tag to transmit one bit. The length of a slot is calculated as the sum of a waiting time and the time for the tag to transmit a certain number of bits. Since the type of slots used by TBC and Enhanced FNEB, Tshort, contains only one bit, the slot length is 0.321 ms. The type of slots used by UPE and GT needs to detect collision and contains 10 bits. Their slot length is Tlong = 0.49ms. Comparing with the time used by tags to transmit to the reader, the time used by the reader to transmit to the tags are negligible in all four protocols. In our simulation, n = 500, 000, the range of group sizes is (0, 500], h = 250, and the value of l varies. There are 2,000 groups, and the number x of above-threshold(h) groups may vary in simulation, but its default value is 1,000. First, we randomly choose the sizes for the above￾threshold groups from [250, 500]. After that, we distribute the remaining M tags into the below-threshold groups. For the first below-threshold group, we generate a random number between 1 and min{249, M 2000−x } to be its population, which is denoted as s1. For the second below-threshold group, we select a random value between 1 and min{249, M−s1 1999−x } as its population, which is denoted as s2. Similarly, we assign a random value between 1 and min{249, M−s1−s2 1998−x } as the population for the third below-threshold group. This process is repeated for all remaining below-threshold groups. If there are still tags left unassigned, we assign them arbitrarily to below-threshold groups as long as their sizes are below 250. For each simulation, TBC will compute the optimal value of w × f (together with the optimal system parameters). Once w × f is determined, the execution time is known, which is Tshort × w × f plus the time for broadcasting polling requests. GT will also compute its optimal system parameters, including the time frame size f, the number R of rounds, and the number W of shuffled groups W. The execution time required by GT is Tlong × f × W × R. UPE and Enhanced FNEB work under the settings based on their original papers. Their execution times are the sum of the times for measuring the populations of individual groups. B. Execution time required in terms of α, β and l/h We compare TBC, GT, UPE and Enhanced FNEB in terms of execution time. Tables II – IV show our simulation results under different values of l/h, α and β. Table II shows the execution time required when α = 99% and β = 1%. From the table, we can see that TBC has a much smaller execution time than GT, UPE and Enhanced FNEB. GT takes 1 14 when l = 0.1h, which is 3.09 times of TBC. UPE and Enhanced FNEB consume an order of magnitude or more time than GT and TBC. 2013 Proceedings IEEE INFOCOM 896