function T()to denote the time cost in each round.Given k, programming problem,or bound a small search range to t,and f,T()can be expressed as exhaustively find the optimal values of f and k.Both T(k,t,f) methods can reduce the computation cost in practice. Since the ratio is relatively stable,the optimal number =∑=(u+1)Pr(X=u)+∑I=k(k+log2f)Pr(X=u) of rounds n will not get obvious increase,when tmax ∑-6P+log2fPb becomes large.Therefore,as shown in the evaluation = 瑞+-loga fP, section,our algorithm performs well even if we count a huge amount of tags. where the first term describes the cost of using the original send-and-reply protocol,if there is a reply within k slots.The D.Enhancement:Adjusting Skewed tmar second term,indicating the cost of using our new send-and- In practice,users may overestimate the upper bound tmaz. reply protocol,is a constant k+log2 f.Both of them are The actual t may be much smaller than the bound.Thus,the multiplied by their probabilities. optimal parameters f and k computed by tmaz may be too large Therefore,n.T(k,t,f)is the estimating time of our algo- for estimation,since it causes many empty slots before the first rithm for a specified t.Our goal is to find parameters f and k reply in each round.We call this the skewed tmaz problem. to minimize the time cost averaging over all possible values of t from 1 to tmaz.Then,the problem is to minimize (a) ) 80000 20000 © 1 n.T(k,t,f) 10000 tmaz t=1 16000 1000 60000 100 subject to k,f∈N,and0≤k≤f,where 2 12000 C2e-tmarlf(etmarlf-e-etmarl)2 n= 40000 (1-e-etmaz/f)2 8000 T(k,t,f)= 1-P +logz fPo. 1-P% 20000 4000 0 0.05 0.1 .1 0.5 1.0 This is a nonlinear programming problem with two unknown integer variables.Although it is difficult to find an expression Fig.3.Time cost versus the normalized number of tags for different tmax: of f and k,the problem is solvable by enumerating all possible (a)comparison under t/.1;(b)comparison under t/tmar>0.1 parameters to find the optimal values.Given parameters:tmar, e and 6,we first fix f and enumerate all values of k from I to To show the effect of different tmax on the performance of f to find the best value of k which can minimize the objective our FNEB estimator,we plot the estimating time in number of function.Then,we repeat the process to search for the optimal slots against t under three different tmax(see Fig.3).To ease f.Note that these procedures are all computed by the reader comparison,we normalize t by tmaz and separate the figure into offline. two parts.As we see,when the value of t/tmaz approaches 1, Table II shows the optimal parameters for some specified the time cost decreases significantly.Also,for the same value tmaz under that e=5%and 6=1%.In the table,nop,fop, of t/tmar,the smaller tmaz will spend less time,when t is and kop indicate the optimal number of rounds,frame size,and absolutely close to tmaz. number of waiting slots for each tmax respectively.The ratio Based on these observations,we propose an enhanced ap- in the last column is computed by tmaz over fop. proach to solve the skewed tmaz problem.As mentioned before, a larger tmaz usually causes more empty slots.Therefore,we TABLE II can use the position of first reply to decide whether tmaz is too OPTIMAL PARAMETERS FOR DIFFERENT tma WITH 6=0.01,E=0.05 large for t.If it is,we will adaptively shrink tmaz in the next t Kop Ratio (=tmar/fop) round.The main algorithm is shown in Algorithm 4.which 10 3927 55 0 1.818 should be appended at the end of each iteration (between lines 500 4024 264 8 1.894 12 and 13)in Algorithm 3. I000 4058 521 1.919 5000 4014 265T 1.886 Recall that X is the random variable indicating the number 100004024 5279 1.894 of empty slots before the first reply from tags,and Xi is the 50000. 4042 26205 1.908 observed value of X in the ith round.Let variable N enumerate all possible numbers of tags,decreasing from tmar to 1.Then, From the table,we have the following observations. Pr[X =Xilt =N]is the probability of observing Xi empty The ratio of tmar to fop is close to 1.9,and k is close to slots on the condition that t=N.According to Bayes'theorem, log2 f.Based on this observation,we can either directly we have use the quasi-optimal parameters:f1.9 and k log2 f Prt=NX=x]=PK=X北=N (5) for our estimating algorithm without solving the non-linear PrX=Xilfunction T (·) to denote the time cost in each round. Given k, t, and f, T (·) can be expressed as T (k, t, f) = Pk−1 u=0(u+1)P r(X=u)+Pf−1 u=k (k+log2 f)P r(X=u) = Pk−1 u=0 P u 0 +log2 f·P k 0 = 1−P k 0 1−P0 +log2 fP k 0 , where the first term describes the cost of using the original send-and-reply protocol, if there is a reply within k slots. The second term, indicating the cost of using our new send-and￾reply protocol, is a constant k + log2 f. Both of them are multiplied by their probabilities. Therefore, n · T (k, t, f) is the estimating time of our algo￾rithm for a specified t. Our goal is to find parameters f and k to minimize the time cost averaging over all possible values of t from 1 to tmax. Then, the problem is to minimize 1 tmax tXmax t=1 n · T (k, t, f) subject to k, f ∈ N, and 0 6 k 6 f, where n = c 2 e −tmax/f (e tmax/f − e −ǫtmax/f ) 2 (1 − e−ǫtmax/f ) 2 T (k, t, f) = 1 − P k 0 1 − P0 + log2 fPk 0 . This is a nonlinear programming problem with two unknown integer variables. Although it is difficult to find an expression of f and k, the problem is solvable by enumerating all possible parameters to find the optimal values. Given parameters: tmax, ǫ and δ, we first fix f and enumerate all values of k from 1 to f to find the best value of k which can minimize the objective function. Then, we repeat the process to search for the optimal f. Note that these procedures are all computed by the reader offline. Table II shows the optimal parameters for some specified tmax under that ǫ = 5% and δ = 1%. In the table, nop, fop, and kop indicate the optimal number of rounds, frame size, and number of waiting slots for each tmax respectively. The ratio in the last column is computed by tmax over fop. TABLE II OPTIMAL PARAMETERS FOR DIFFERENT tmax WITH δ = 0.01, ǫ = 0.05 tmax nop fop kop Ratio (= tmax/fop) 100 3927 55 6 1.818 500 4024 264 8 1.894 1000 4058 521 9 1.919 5000 4014 2651 12 1.886 10000 4024 5279 13 1.894 50000 4042 26205 15 1.908 From the table, we have the following observations. • The ratio of tmax to fop is close to 1.9, and k is close to log2 f. Based on this observation, we can either directly use the quasi-optimal parameters: f ≈ 1.9 and k ≈ log2 f for our estimating algorithm without solving the non-linear programming problem, or bound a small search range to exhaustively find the optimal values of f and k. Both methods can reduce the computation cost in practice. • Since the ratio is relatively stable, the optimal number of rounds n will not get obvious increase, when tmax becomes large. Therefore, as shown in the evaluation section, our algorithm performs well even if we count a huge amount of tags. D. Enhancement: Adjusting Skewed tmax In practice, users may overestimate the upper bound tmax. The actual t may be much smaller than the bound. Thus, the optimal parameters f and k computed by tmax may be too large for estimation, since it causes many empty slots before the first reply in each round. We call this the skewed tmax problem. 80000 60000 40000 20000 0 0.05 0.1 Spending time (in number of slots) t/tmax (a) tmax: 10000 1000 100 80000 60000 40000 20000 0 0.05 0.1 Spending time (in number of slots) t/tmax (a) tmax: 10000 1000 100 20000 16000 12000 8000 4000 0.1 0.5 1.0 Spending time (in number of slots) t/tmax (b) tmax: 10000 1000 100 Fig. 3. Time cost versus the normalized number of tags for different tmax: (a) comparison under t/tmax 6 0.1; (b) comparison under t/tmax > 0.1 To show the effect of different tmax on the performance of our FNEB estimator, we plot the estimating time in number of slots against t under three different tmax (see Fig. 3). To ease comparison, we normalize t by tmax and separate the figure into two parts. As we see, when the value of t/tmax approaches 1, the time cost decreases significantly. Also, for the same value of t/tmax, the smaller tmax will spend less time, when t is absolutely close to tmax. Based on these observations, we propose an enhanced ap￾proach to solve the skewed tmax problem. As mentioned before, a larger tmax usually causes more empty slots. Therefore, we can use the position of first reply to decide whether tmax is too large for t. If it is, we will adaptively shrink tmax in the next round. The main algorithm is shown in Algorithm 4, which should be appended at the end of each iteration (between lines 12 and 13) in Algorithm 3. Recall that X is the random variable indicating the number of empty slots before the first reply from tags, and Xi is the observed value of X in the ith round. Let variable N enumerate all possible numbers of tags, decreasing from tmax to 1. Then, P r[X = Xi |t = N] is the probability of observing Xi empty slots on the condition that t = N. According to Bayes’ theorem, we have P r[t = N|X = Xi ] = P r[X = Xi |t = N] P r[X = Xi ] , (5)