the objective is achieved while the coverage constraints are p,while satisfying the time/energy constraint,we can use satisfied. the power p for the maximum value of yr or ye as the In regard to the coverage constraint,since we need to optimal parameter and compute the corresponding moving guarantee p=1-(1-p)m≥0，i.e,1-(1-p)≥0， itis equivalent to ensure As the speed v*according to Eq.(12).In this way,the optimal solution (p,v*)for time/energy efficiency can be generated value of w,p'and Te all depends on the value of p,let Therefore,in regard to various tag densities p,we can collect w(p),p'(p)and Te(p)respectively denote the mapping the performance parameters like w,p'and Te in advance, pre-compute the optimal pairs of (p,v),and store them function from pe to w,p and Te,then in a table.When dealing with an arbitrary tag density,we v=m(1-0产 ,w(pw)·ln(1-p'(pm)川 (12) can directly use the optimal pair of (p,)to achieve the Te(Pw) time/energy efficiency. then,v*is the maximum allowable moving speed to satisfy 5.2.2 Estimate the tag density the coverage constraint. According to the measured data in realistic settings,it Since the length of the scanning area is l,the overall scan- is known that the tag density p has an important effect on ning time T=,and the overall used energy E=T.p= the performance metrics.In situations where the tag densi- Therefore,considering the time-efficiency,in order to ty cannot be pre-fetched or the tag density varies along the minimize T,it is equivalent to maximize v.Then,accord- forwarding direction.it is essential to accurately estimate ing to Eq.(12),it is essential to maximize ()It the current tag density,such that the optimized parameters is known that as the value of p increases,the value of (p)can be effectively computed.Due to the proba- w.In(1-p)and Te are both monotonically increasing,thus bilistic backscattering property,it is difficult to directly es- an optimized value of p should be selected to minimize T. timate the tag density according to the observed number Considering the energy constraint E<o,the optimal value of empty/singleton/collision slots 8,11.Furthermore,cur- p can be computed according to the following formulation: rent commercial RFID readers do not expose these low-level maximize r =IIn(1-p'(pu)w(p.) data to upper-layer applications.Therefore,it is essential (13) to estimate the tag density in a more practical way Te(Pw) According to Fig.1(k),we note that if the reader's power subject to po is set to a certain value,the number of identified tags In(1-p'(p))w(pw) 1-|ln(1-0)川 per cycle ne is varying as the tag density p varies,with a (14) pe·Tc(pw) very small standard deviation.Table 1 shows further detail- s for the average values of ne.These are obtained through Considering the energy-efficiency,in order to minimize E. 50 repetitive experiments with various values of p and p. it is equivalent to minimize then according to Eq.(12),it Due to the small variance of ne,there is a very stable pat- is essential to maximize (Therefore,considering tern between ne and p that varies with p.Therefore,given the time constraintT≤，the optimal value p元can be a reference tag density Pi,we can depict the values of ne computed according to the following formulation: with various powers as a vector Vi {ni,1,ni.2,...,ni.s}, maximizey=lnl-ppul·wpa） here s is the number of power levels.Then,in regard to (15) an unknown tag density p,assume the corresponding vec- pp·Tc(Pw） tor is V=fn,n2,...,n},we can estimate the value of p subject to by comparing V with the vectors of reference tag densities. 血1-p(p)w(pe)≥-血1-rl Therefore,we propose an algorithm to estimate the tag den- (16) sity,by leveraging the k-nearest neighbor method,as shown Te(pw】 in Algorithm 1. =p-10 Pw= 20.722.724.7 26.7 28.7 30.7 10-30 p=10 9 13 22 25 28 31 0-40 P=20 10 23 30 40 51 0. P=30 2 10 20 36 59 0.4 p=40 2 4 10 17 33 57 02 Table 1:The number of identified tags per cycle 2 Peader p 24 3 22 (a)The value of yr (b)The value of yE In Algorithm 1,the similarity sim(V,Vi)is actually cal- culated by using the cosine value of the angle between the two vectors,hence the value of similarity is between 0 and 1. Figure 4:Compute the value of yr and yE with var- We use the k-nearest neighbor method to estimate the tag ious values of pu density based on k-nearest reference tag densities.The es- In regard to a certain tag density p,by enumerating the timated tag density p is computed using an inverse distance candidate values of the power p,we can compute the value weighted average with the k-nearest multivariate neighbors of yr and yE.Fig.4(a)and Fig.4(b)respectively illustrate here the distance is defined as 1-sim(V,Vi).Since the val- the value of yr and ye while varying the reader's power p. ue of ne has a rather small variance,the accuracy of the We note that there exist a maximum value of yr and yE estimated tag density can be guaranteed if the number of for each tag density.In regard to a specified tag density samplings m is fairly large.In the algorithm.the mobilethe objective is achieved while the coverage constraints are satisfied. In regard to the coverage constraint, since we need to guarantee p = 1 − (1 − p ) m ≥ θ∗, i.e., 1 − (1 − p ) w v·τc ≥ θ∗, it is equivalent to ensure v ≤ 1 | ln(1−θ∗)| · w·| ln(1−p)| τc . As the value of w, p and τc all depends on the value of pw, let w(pw), p (pw) and τc(pw) respectively denote the mapping function from pw to w, p and τc, then v∗ = 1 | ln(1 − θ∗)| · w(pw) · | ln(1 − p (pw))| τc(pw) , (12) then, v∗ is the maximum allowable moving speed to satisfy the coverage constraint. Since the length of the scanning area is l, the overall scan￾ning time T = l v , and the overall used energy E = T · pw = pw·l v . Therefore, considering the time-efficiency, in order to minimize T , it is equivalent to maximize v. Then, accord￾ing to Eq.(12), it is essential to maximize w·| ln(1−p)| τc . It is known that as the value of pw increases, the value of w·| ln(1−p )| and τc are both monotonically increasing, thus an optimized value of pw should be selected to minimize T . Considering the energy constraint E ≤ α, the optimal value p∗ w can be computed according to the following formulation: maximize yT = | ln(1 − p (pw))| · w(pw) τc(pw) (13) subject to | ln(1 − p (pw))| · w(pw) pw · τc(pw) ≥ l · | ln(1 − θ∗)| α (14) Considering the energy-efficiency, in order to minimize E, it is equivalent to minimize pw v , then according to Eq.(12), it is essential to maximize | ln(1−p)|·w pw·τc . Therefore, considering the time constraint T ≤ γ, the optimal value p∗ w can be computed according to the following formulation: maximize yE = | ln(1 − p (pw))| · w(pw) pw · τc(pw) (15) subject to | ln(1 − p (pw))| · w(pw) τc(pw) ≥ l · | ln(1 − θ∗)| γ (16) 22 24 26 28 30 0 1 2 3 4 5 6 x 10−3 Reader power pw (dBm) The value of yT ρ=10 ρ=20 ρ=30 ρ=40 (a) The value of yT 22 24 26 28 30 0 0.2 0.4 0.6 0.8 1 1.2 x 10−5 Reader power pw (dBm) The value of yE ρ=10 ρ=20 ρ=30 ρ=40 (b) The value of yE Figure 4: Compute the value of yT and yE with var￾ious values of pw In regard to a certain tag density ρ, by enumerating the candidate values of the power pw, we can compute the value of yT and yE. Fig.4(a) and Fig.4(b) respectively illustrate the value of yT and yE while varying the reader’s power pw. We note that there exist a maximum value of yT and yE for each tag density. In regard to a specified tag density ρ, while satisfying the time/energy constraint, we can use the power p∗ w for the maximum value of yT or yE as the optimal parameter and compute the corresponding moving speed v∗ according to Eq.(12). In this way, the optimal solution (p∗ w, v∗) for time/energy efficiency can be generated. Therefore, in regard to various tag densities ρ, we can collect the performance parameters like w, p and τc in advance, pre-compute the optimal pairs of (p∗ w, v∗), and store them in a table. When dealing with an arbitrary tag density, we can directly use the optimal pair of (p∗ w, v∗) to achieve the time/energy efficiency. 5.2.2 Estimate the tag density According to the measured data in realistic settings, it is known that the tag density ρ has an important effect on the performance metrics. In situations where the tag densi￾ty cannot be pre-fetched or the tag density varies along the forwarding direction, it is essential to accurately estimate the current tag density, such that the optimized parameters (p∗ w, v∗) can be effectively computed. Due to the proba￾bilistic backscattering property, it is difficult to directly es￾timate the tag density according to the observed number of empty/singleton/collision slots [8, 11]. Furthermore, cur￾rent commercial RFID readers do not expose these low-level data to upper-layer applications. Therefore, it is essential to estimate the tag density in a more practical way. According to Fig.1(k), we note that if the reader’s power pw is set to a certain value, the number of identified tags per cycle nc is varying as the tag density ρ varies, with a very small standard deviation. Table 1 shows further detail￾s for the average values of nc. These are obtained through 50 repetitive experiments with various values of ρ and pw. Due to the small variance of nc, there is a very stable pat￾tern between nc and ρ that varies with pw. Therefore, given a reference tag density ρi, we can depict the values of nc with various powers as a vector Vi = {ni,1, ni,2, ..., ni,s}, here s is the number of power levels. Then, in regard to an unknown tag density ρ, assume the corresponding vec￾tor is V = {n1, n2, ..., ns}, we can estimate the value of ρ by comparing V with the vectors of reference tag densities. Therefore, we propose an algorithm to estimate the tag den￾sity, by leveraging the k-nearest neighbor method, as shown in Algorithm 1. pw= 20.7 22.7 24.7 26.7 28.7 30.7 ρ = 10 9 13 22 25 28 31 ρ = 20 2 10 23 30 40 51 ρ = 30 1 2 10 20 36 59 ρ = 40 2 4 10 17 33 57 Table 1: The number of identified tags per cycle In Algorithm 1, the similarity sim(V,Vi) is actually cal￾culated by using the cosine value of the angle between the two vectors, hence the value of similarity is between 0 and 1. We use the k-nearest neighbor method to estimate the tag density based on k-nearest reference tag densities. The es￾timated tag density ρ is computed using an inverse distance weighted average with the k-nearest multivariate neighbors, here the distance is defined as 1 − sim(V,Vi). Since the val￾ue of nc has a rather small variance, the accuracy of the estimated tag density can be guaranteed if the number of samplings m is fairly large. In the algorithm, the mobile