2013 Proceedings IEEE INFOCOM TABLE II 250 TBC ESTIMATION TIME COMPARISON WHEN O =99%AND B=1% 200 GT…… Estimation Time in minutes(/),seconds(/) 150 TBC GT UPE Enhanced FNEB 1=0.1h 1'14" 349" 556'50" 336'36" 100 1=0.3h1'42" 426" 55650" 33636" 50 1=0.5h3'05 615" 55650 33636 l=0.7h 4'51" 912" 55650" 33636" 1002003004005006007008009001000 l=0.9h 621" 11'58" 55650" 33636" Number of above-threshold groups S TABLE III Fig.2.Execution time with respect to the number of groups S which are ESTIMATION TIME COMPARISON WHEN =95%AND 8=5% supposed to be reported when a =99%,B =1%and I =0.1h.The total number of tags n is fixed to be 500,000 at each point. Estimation Time in minutes(/),seconds(/) TBC GT UPE Enhanced FNEB GT uses a simple,fast threshold checking scheme (TCS) l=0.1h 447 1'55" 17'31M 1027" to probabilistically identify populous groups with size larger l=0.3h 1'6" 2'9" 1731" 1027" than a threshold.However,TCS incurs a large variance in 1=0.5h 1'47" 257" 55650" 33636" its estimated result.To satisfy a high accuracy requirement, l=0.7h 2394 411" 55650% 33636" a large number of TCS executions are required,which =0.9h 4'4" 6'36" 556W50" 33636" lengthens execution time.In addition,GT has to identify whether a slot is empty,singleton or collision,resulting in TABLE IV longer slots.It is not efficient to invoke UPE and Enhanced ESTIMATION TIME COMPARISON WHEN =90%AND B=10% FNEB to estimate the size of each group one at a time.In Estimation Time in minutes(/),seconds(/) addition,UPE requires tags to transmit 10-bit responses to TBC GT UPE Enhanced FNEB distinguish singleton slots from collision slots.TBC estimate =0.1h 38 1'33" 10/37M 75m all group sizes together and share slots among all groups.It =0.3h 52' 1'51" 1037 75" only needs to know whether each slot is empty or not.Hence, l=0.5h 1'17" 2'18" 55650" 336'36" its execution time is the shortest. =0.7h 36 55650" 33636" In Table II,when l/h becomes larger,both TBC and 1'56 =0.9h 2'504 4'55" 556Y50 336'36" GT need more time to classify the above-threshold groups. This is because a larger ratio of l/h means a higher accuracy requirement for above-threshold classification.The performance gain by TBC over GT shrinks as l/h increases, 250 but remains significant.For example,when I=0.1h,the TBC 200 GT execution time required by GT is 3.09 times that of TBC. When I=0.9h,the time by GT becomes 1.9 times that of 150 TBC. Tables III and IV compare the execution time of the four 100 protocols when a=95%,B=5%,and a =90%,B=10%, 50 respectively.These two tables show that TBC outperforms other protocols under different parameter settings.When 0 1002003004005006007008009001000 comparing with Table II,we see that given the same values Number of above-threshold groups S of h and l,the execution times of all protocols are reduced when a decreases or B increases. Fig.3.Execution time with respect to the number of groups S which are supposed to be reported when a =99%,B=1%and I =0.1h.The total C.Execution time required in terms of the number of above- number of tags n for all the groups increases along with S. threshold groups In the previous comparison,the number of above-threshold viewed as a constant even when the number of groups is groups is set at the default value 1,000.We further compare different.Such an observation agrees with (21),which does TBC and GT by varying the number of above-threshold not include S in its formulation.In Fig.3,we allow the total groups,denoted as S.Let a=99%and B=1%.In Fig.2.number of tags to change.Each below-threshold group takes we keep n 500,000 and vary the the number of above- a random population in the range of(0,250)and each above- threshold groups from 100 to 1,000.As we see in the figure, threshold group takes a random population in the range of TBC outperforms GT,and the execution time of TBC is 250,500.From the figure,we observe that the classification insensitive to S.As long as the total number of tags in the times of TBC and GT are approximately proportional to the system is the same,the execution time can be approximately number of above-threshold groups.However,the line of GT 8970 50 100 150 200 250 100 200 300 400 500 600 700 800 900 1000 Time in seconds Number of above-threshold groups S TBC GT Fig. 2. Execution time with respect to the number of groups S which are supposed to be reported when α = 99%, β = 1% and l = 0.1h. The total number of tags n is fixed to be 500,000 at each point. GT uses a simple, fast threshold checking scheme (TCS) to probabilistically identify populous groups with size larger than a threshold. However, TCS incurs a large variance in its estimated result. To satisfy a high accuracy requirement, a large number of TCS executions are required, which lengthens execution time. In addition, GT has to identify whether a slot is empty, singleton or collision, resulting in longer slots. It is not efficient to invoke UPE and Enhanced FNEB to estimate the size of each group one at a time. In addition, UPE requires tags to transmit 10-bit responses to distinguish singleton slots from collision slots. TBC estimate all group sizes together and share slots among all groups. It only needs to know whether each slot is empty or not. Hence, its execution time is the shortest. In Table II, when l/h becomes larger, both TBC and GT need more time to classify the above-threshold groups. This is because a larger ratio of l/h means a higher accuracy requirement for above-threshold classification. The performance gain by TBC over GT shrinks as l/h increases, but remains significant. For example, when l = 0.1h, the execution time required by GT is 3.09 times that of TBC. When l = 0.9h, the time by GT becomes 1.9 times that of TBC. Tables III and IV compare the execution time of the four protocols when α = 95%, β = 5%, and α = 90%, β = 10%, respectively. These two tables show that TBC outperforms other protocols under different parameter settings. When comparing with Table II, we see that given the same values of h and l, the execution times of all protocols are reduced when α decreases or β increases. C. Execution time required in terms of the number of above￾threshold groups In the previous comparison, the number of above-threshold groups is set at the default value 1,000. We further compare TBC and GT by varying the number of above-threshold groups, denoted as S. Let α = 99% and β = 1%. In Fig. 2, we keep n = 500, 000 and vary the the number of above￾threshold groups from 100 to 1,000. As we see in the figure, TBC outperforms GT, and the execution time of TBC is insensitive to S. As long as the total number of tags in the system is the same, the execution time can be approximately TABLE II ESTIMATION TIME COMPARISON WHEN α = 99% AND β = 1% Estimation Time in minutes(), seconds() TBC GT UPE Enhanced FNEB l = 0.1h 1 14 3 49 556 50 336 36 l = 0.3h 1 42 4 26 556 50 336 36 l = 0.5h 3 05 615 55650 33636 l = 0.7h 4 51 9 12 556 50 336 36 l = 0.9h 6 21 11 58 55650 33636 TABLE III ESTIMATION TIME COMPARISON WHEN α = 95% AND β = 5% Estimation Time in minutes(), seconds() TBC GT UPE Enhanced FNEB l = 0.1h 44 1 55 17 31 10 27 l = 0.3h 16 2 9 17 31 1027 l = 0.5h 1 47 2 57 556 50 336 36 l = 0.7h 239 411 55650 33636 l = 0.9h 4 4 6 36 556 50 336 36 TABLE IV ESTIMATION TIME COMPARISON WHEN α = 90% AND β = 10% Estimation Time in minutes(), seconds() TBC GT UPE Enhanced FNEB l = 0.1h 38 133 10 37 7 5 l = 0.3h 52 1 51 10 37 7 5 l = 0.5h 1 17 218 55650 33636 l = 0.7h 1 56 3 6 556 50 336 36 l = 0.9h 250 455 55650 33636 0 50 100 150 200 250 100 200 300 400 500 600 700 800 900 1000 Time in seconds Number of above-threshold groups S TBC GT Fig. 3. Execution time with respect to the number of groups S which are supposed to be reported when α = 99%, β = 1% and l = 0.1h. The total number of tags n for all the groups increases along with S. viewed as a constant even when the number of groups is different. Such an observation agrees with (21), which does not include S in its formulation. In Fig. 3, we allow the total number of tags to change. Each below-threshold group takes a random population in the range of (0, 250) and each above￾threshold group takes a random population in the range of [250, 500]. From the figure, we observe that the classification times of TBC and GT are approximately proportional to the number of above-threshold groups. However, the line of GT 2013 Proceedings IEEE INFOCOM 897