Algorithm 4 Adaptively shrink skewed tmaz directly apply our previous algorithms on each tag set,these /After getting Xi,we test whether to shrink tmaz */ overlapping tags will be counted multiple times,resulting in 1:p=0 erroneous overall estimations. 2:for N tmaz to 1 do We have extended our FNEB algorithms to estimate multiple 3: Pr[X=Xilt=N] p=p+maPr=Xt=司 tag sets.Due to page limit,we cannot include the details in this 4: if 1-p<0.1%and N<tmar then paper.The intuition of the protocol is as follows.Suppose we 5: tmar =N have m tag sets S1,S2,...,Sm,and for each set the number of 6: Recompute f,k,and n,and restart new rounds empty slots before the first non-empty slot is X1,X2,...,Xm. 7: break In a global view,min(X1,X2,...,Xm)infers the total tag size 8: end if IS1US2U...USml.However,each set i(iE [1,m])does not 9:end for know whether Xi is minimal.Therefore,we need to track all sets to record the minimal number.In practice,the optimization is used to speed up the above process.If no tag replied before where Pr[X =X=Pr[X =Xilt i].In the the minimal number of empty slots that we already know,we algorithm,Eq.5 is added to variable p as N decreases in each just terminate reading such a set,because it does not change iteration (line 3).So p presents the probability PrIN <t the minimal value. tmaz]on condition that Xi empty slots have been observed. The reason why we can minimize slot count from different and 1-p is the probability Pr[1 <t<N]correspondingly. sets is that the reply slot by each tag is only dependent on Once 1-p is smaller than a very small probability (like 0.1% the frame size f and random seed R.So long as the same in our algorithm),it means that t can not be larger than N with parameters are used,a tag will always pick the same slot in high possibility.Therefore,we can shrink tmar to the value of the frame.Based on this property,any reply that occurs before N.Recall the analysis in Section V-B.PrX =Xilt =N can the first reply in other sets must belong to a new tag.In other be computed by (e-N/)X.(1-e-N/f). words,even if the same tags have responded in multiple sets, However,when the shrinking occurs in the latter rounds, the first non-empty slot will remain the same.The final result is restarting new rounds may incur a large overhead.Therefore, equivalent to having all distinct tags belong to one large single we constrain the number of rounds for shrinking.If tmaz set.Therefore,our extended approach remains accurate while remains unchanged in certain consecutive rounds,the current significantly reducing time cost. tmaz is deemed stable enough.We will not run Algorithm 4 VI.PERFORMANCE EVALUATION after those rounds.In the simulation,we set a heuristic value of 30 rounds which is large enough for adjustment. The goal of this paper is to design an estimator to count tags efficiently and anonymously in both static and dynamic TABLEⅢ environments.Here,we evaluate the performance of our FNEB RESULTS FROM THE ADAPTIVE SHRINK ALGORITHM FOR SINGLE SET OF estimator,the enhanced FNEB estimator for single set of RFID TAGS WITH tmaz =10000,6 =0.01,AND=0.05 tags,and the extended FNEB estimator for multiple sets of No.of No.of Final value Shrinking Total time tags.Through extensive simulation,we compare our estimators tags shrinks of tma overhead (slots) against several well-known estimators mentioned in the related 0 5.6 44 350.7 5525.9 work.They are the Combined Simple Estimator(CSE)[12],the 50 5.5 69.9 365.1 5738.0 Unified Probabilistic Estimator(UPE)[12],and the Enhanced I00 5.4 35.7 418.8 572.4 500 667.6 444.9 5758.8 Zero-Based(EZB)estimator [13].These estimators are selected I000 4.9 T07.3 44.3 5683.2 for two reasons.First,they can all provide the desired estimat- 5000 .9 6467.5 371.3 5660.8 ing accuracy (say,Prlt-t<et]>1-6).Second,they are more efficient than other estimators we do not list here Table III shows the performance of our enhanced FNEB All estimators were implemented in Java.We first investigate estimator.From that,we find that the final value of tmar can be the estimators for static set,then the estimators for multiple adjusted close to t within several shrinks.As a result,different sets.Unless otherwise specified,we set the maximum number numbers of tags can lead to almost the same total time. of RFID tags tmaz to 10000,the confidence level e to 0.05, E.Extension:Estimating Multiple Tag Sets and the error probability 6 to 0.01.Each result is the average of 100 iterations.These experiments test the hypothesis that our Previously,we only considered a static tag set.However,for estimators can be more efficient than other estimators. certain applications,we may need to count multiple tag sets in a dynamic environment where either the tags or reader is mobile. A.Time Efficiency For example,a single reader cannot cover all the tags in a large Prior work in [12]and [13]uses the number of slots that warehouse.Instead,we have to either deploy multiple readers a reader has to scan as an indicator of time efficiency.The or dispatch a mobile reader moving through the warehouse reader that scans a few slots will perform faster than the reader to cover all tags.In that case,different tag sets queried by that needs to scan many slots.However,the number of slots readers at different places could have overlapping tags.If we used is misleading,since different types of slots have variantAlgorithm 4 Adaptively shrink skewed tmax /* After getting Xi , we test whether to shrink tmax */ 1: p = 0 2: for N = tmax to 1 do 3: p = p + P P r[X=Xi|t=N] tmax i=1 P r[X=Xi|t=i] 4: if 1 − p < 0.1% and N < tmax then 5: tmax = N 6: Recompute f, k, and n, and restart new rounds 7: break 8: end if 9: end for where P r[X = Xi ] = Ptmax i=1 P r[X = Xi |t = i]. In the algorithm, Eq. 5 is added to variable p as N decreases in each iteration (line 3). So p presents the probability P r[N ≤ t ≤ tmax] on condition that Xi empty slots have been observed, and 1 − p is the probability P r[1 ≤ t < N] correspondingly. Once 1 − p is smaller than a very small probability (like 0.1% in our algorithm), it means that t can not be larger than N with high possibility. Therefore, we can shrink tmax to the value of N. Recall the analysis in Section V-B, P r[X = Xi |t = N] can be computed by (e −N/f ) Xi · (1 − e −N/f ). However, when the shrinking occurs in the latter rounds, restarting new rounds may incur a large overhead. Therefore, we constrain the number of rounds for shrinking. If tmax remains unchanged in certain consecutive rounds, the current tmax is deemed stable enough. We will not run Algorithm 4 after those rounds. In the simulation, we set a heuristic value of 30 rounds which is large enough for adjustment. TABLE III RESULTS FROM THE ADAPTIVE SHRINK ALGORITHM FOR SINGLE SET OF RFID TAGS WITH tmax = 10000, δ = 0.01, AND ǫ = 0.05 No. of No. of Final value Shrinking Total time tags shrinks of tmax overhead (slots) 10 5.6 14.4 350.7 5525.9 50 5.5 69.9 365.1 5738.0 100 5.4 135.7 418.8 5732.4 500 5.2 667.6 444.9 5758.8 1000 4.9 1307.3 441.3 5683.2 5000 1.9 6467.5 371.3 5660.8 Table III shows the performance of our enhanced FNEB estimator. From that, we find that the final value of tmax can be adjusted close to t within several shrinks. As a result, different numbers of tags can lead to almost the same total time. E. Extension: Estimating Multiple Tag Sets Previously, we only considered a static tag set. However, for certain applications, we may need to count multiple tag sets in a dynamic environment where either the tags or reader is mobile. For example, a single reader cannot cover all the tags in a large warehouse. Instead, we have to either deploy multiple readers or dispatch a mobile reader moving through the warehouse to cover all tags. In that case, different tag sets queried by readers at different places could have overlapping tags. If we directly apply our previous algorithms on each tag set, these overlapping tags will be counted multiple times, resulting in erroneous overall estimations. We have extended our FNEB algorithms to estimate multiple tag sets. Due to page limit, we cannot include the details in this paper. The intuition of the protocol is as follows. Suppose we have m tag sets S1, S2, ..., Sm, and for each set the number of empty slots before the first non-empty slot is X1, X2, ..., Xm. In a global view, min(X1, X2, ..., Xm) infers the total tag size |S1 ∪ S2 ∪ ... ∪ Sm|. However, each set i (i ∈ [1, m]) does not know whether Xi is minimal. Therefore, we need to track all sets to record the minimal number. In practice, the optimization is used to speed up the above process. If no tag replied before the minimal number of empty slots that we already know, we just terminate reading such a set, because it does not change the minimal value. The reason why we can minimize slot count from different sets is that the reply slot by each tag is only dependent on the frame size f and random seed R. So long as the same parameters are used, a tag will always pick the same slot in the frame. Based on this property, any reply that occurs before the first reply in other sets must belong to a new tag. In other words, even if the same tags have responded in multiple sets, the first non-empty slot will remain the same. The final result is equivalent to having all distinct tags belong to one large single set. Therefore, our extended approach remains accurate while significantly reducing time cost. VI. PERFORMANCE EVALUATION The goal of this paper is to design an estimator to count tags efficiently and anonymously in both static and dynamic environments. Here, we evaluate the performance of our FNEB estimator, the enhanced FNEB estimator for single set of tags, and the extended FNEB estimator for multiple sets of tags. Through extensive simulation, we compare our estimators against several well-known estimators mentioned in the related work. They are the Combined Simple Estimator (CSE) [12], the Unified Probabilistic Estimator (UPE) [12], and the Enhanced Zero-Based (EZB) estimator [13]. These estimators are selected for two reasons. First, they can all provide the desired estimat￾ing accuracy (say, P r[|t˜− t| ≤ ǫt] ≥ 1 − δ). Second, they are more efficient than other estimators we do not list here. All estimators were implemented in Java. We first investigate the estimators for static set, then the estimators for multiple sets. Unless otherwise specified, we set the maximum number of RFID tags tmax to 10000, the confidence level ǫ to 0.05, and the error probability δ to 0.01. Each result is the average of 100 iterations. These experiments test the hypothesis that our estimators can be more efficient than other estimators. A. Time Efficiency Prior work in [12] and [13] uses the number of slots that a reader has to scan as an indicator of time efficiency. The reader that scans a few slots will perform faster than the reader that needs to scan many slots. However, the number of slots used is misleading, since different types of slots have variant