This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the main Technical Program at IEEE INFOCOM 2010. the reader issues a Query command instead of the QueryAdjust Here T(f)is the time interval for the frame of size f,and we command to start each frame.The above process continues till have T(f)=no(n,r,f).te+ni(n,r,f).ts+ne(n,r,f).te, both the number of single slots n and the number of collision and r =V(d+0.5fvAt)2+h2 slots ne are equal to 0.Due to the probabilistic propagation loss,this gives a tighter constraint to finish the reading cycle B.Estimate the number of tags than simply checking if ne=0,thus making the number of For each query round the reader needs to estimate the tags left unread as small as possible. number of active tags,so as to provide an accurate input Algorithm 1 Decide optimal frame sizes for slotted-ALOHA parameter for selecting the next optimal frame size.Current estimation schemes [12][21]are not really suitable for our 1:△d=v·△t probabilistic model,because their methodology is based on 2:M=△t D 3:fori∈o,M-1ldo the ideal case when pi(r)=p:(r)=1.Therefore we propose an alternative scheme to estimate the number of tags.Our F[o[同=0，f[0[=0 methodology is based on Theorem 2. 5: d=(i-M/2)·△d Theorem 2:As defined in Eq.(7),no(n,r,f)is monotoni- 6 r=vp+h2 cally decreasing with n.n(n,r,f)is monotonically increas- F啊=「o严l,f同=1 ing with n. 8:end for Due to lack of space,we omit the proof of Theorem 2. 9g:forn∈[2，N]do fori∈[0，M-1do According to Theorem 2,since no(n,r,f)and ne(n,r,f) 10: are monotonic with variable n,given the constant values of 11: d=(i-M/2)·△d Pt(r),pi(r),f,the reader will obtain various expected values 12 r=v(d+0.5·f·△d02+h2 of no:n with various n.Based on this property,we can 13: g(n,d,f)=Ln-n(n,r,f)·p(r)·pt(r)J estimate the number of tags n by leveraging the binary search 14 FIn][i]=minto<fsM-if+Flg(n,d,f)i+fl} method,according to either no(n,r,f)or n(n,r,f).Here f[n]li]arg mingo<fsM-i){f +Flg(n,d,f)l[i+ we take the observed number of empty slots no(n,r,f)as the A) metric for estimation.Assume that the upper bound for n is 16: end for N,i.e.,n E[0,N],then the corresponding expected number 17:end for of empty slots no [no(N,r,f),no(0,r,f)].We now use binary search to find the value of n according to no.We start Algorithm 2 Tag identification with optimal frame sizes from the value n'=N/2,and compare no(n',r,f)with no. 1:△d=v·△t If no(n',r,f)>no.then n falls into the range (N/2,N]. 2:d=-D/2 If no(n',r,f)<no,then n falls into the range [0,N/2). 3:[no,n1,ne,ns]=performReadRound(C) Otherwise n =N/2.We continue the iterative search until we 4:[n]=performTagSizeEstimate(f,d,no,n1,nc) find an exact point value for n.This binary search procedure 5:d=d+C.△d will iterate at most log2(N)steps. 6:while ne≠0orn1≠0do 7: [f*]=selectOptimalFrameSize(n-ns,d) C.Adaptive frame size selection 8 no,n1,ne,ns]=performReadRound(f*) In Section VI-A we have proposed a dynamic programming 9 [n]=performTagSizeEstimate(f,d,no,n1,nc) based solution for selecting optimal frame sizes.By using 10: d=d+f*·△d this methodology we can accurately select the optimal frame 11:end while sizes as the container moves along the conveyor.However,the dynamic program requires to maintain two (N+1)x M sized Note that the objective for the optimization problem is to tables.Algorithm 1 needs (N+1)x M iterations to calculate minimizing the total time for identifying all the tags.Since values for the tables.For each iteration different frame sizes in the problem formulation we make the assumption that f (0,M-i]should be tested.According to Eq.(7)for the average time intervals for empty/single/collision slots are each f it requires at most N iterations to calculate n(n,r,f). nearly equal to At,the optimization problem is equivalent thus the computation complexity is O(N2.M2).Although the to minimize the total used slots.Actually if we consider two tables can be preprocessed in the reader beforehand,the distinct time intervals for various kinds of slots,the dynamic values of N and M can be rather large numbers.Hence in programming still works with slightly modification.Suppose some situations the reader may not afford to conduct such the average time intervals for empty/single/collision slots are calculations. respectively te,ts and te,then F(n,d)can be reformulated as: Therefore an adaptive approach is essential for the reader to quickly select appropriate frame sizes while guaranteeing F(n.d)= efficiency for the anti-collision scheme.We attempt to obtain 0 if n=0 a local optimal frame size for each Ouery Round,so as to (P()(p()).ts if n=1 maximize the proportion of single slots within each frame. min(o<fst(d))[T(f)+F(g(n,d,f),d+T(f))}Otherwise Our solution relies on the following Theorem. Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply.the reader issues a Query command instead of the QueryAdjust command to start each frame. The above process continues till both the number of single slots n1 and the number of collision slots nc are equal to 0. Due to the probabilistic propagation loss, this gives a tighter constraint to finish the reading cycle than simply checking if nc = 0, thus making the number of tags left unread as small as possible. Algorithm 1 Decide optimal frame sizes for slotted-ALOHA 1: Δd = v · Δt 2: M = D v·Δt 3: for i ∈ [0, M − 1] do 4: F[0][i]=0, f[0][i]=0 5: d = (i − M/2) · Δd 6: r = √ d2 + h2 7: F[1][i] =  1 (pi(r))2·(pt(r))2 , f[1][i]=1 8: end for 9: for n ∈ [2, N] do 10: for i ∈ [0, M − 1] do 11: d = (i − M/2) · Δd 12: r = (d + 0.5 · f · Δd)2 + h2 13: g(n, d, f) = n − n 1(n, r, f) · pi(r) · pt(r) 14: F[n][i] = min{0<f≤M−i}{f + F[g(n, d, f)][i + f]} 15: f[n][i] = arg min{0<f≤M−i}{f + F[g(n, d, f)][i + f]} 16: end for 17: end for Algorithm 2 Tag identification with optimal frame sizes 1: Δd = v · Δt 2: d = −D/2 3: [n0, n1, nc, ns]=performReadRound(C) 4: [n]=performTagSizeEstimate(f, d, n0, n1, nc) 5: d = d + C · Δd 6: while nc = 0 or n1 = 0 do 7: [f ∗]=selectOptimalFrameSize(n − ns, d) 8: [n0, n1, nc, ns]=performReadRound(f ∗) 9: [n]=performTagSizeEstimate(f, d, n0, n1, nc) 10: d = d + f ∗ · Δd 11: end while Note that the objective for the optimization problem is to minimizing the total time for identifying all the tags. Since in the problem formulation we make the assumption that the average time intervals for empty/single/collision slots are nearly equal to Δt, the optimization problem is equivalent to minimize the total used slots. Actually if we consider distinct time intervals for various kinds of slots, the dynamic programming still works with slightly modification. Suppose the average time intervals for empty/single/collision slots are respectively te, ts and tc, then F(n, d) can be reformulated as: F(n, d) = ⎧ ⎨ ⎩ 0 if n = 0 ( 1 (pi(r))2·(pt(r))2 ) · ts if n = 1 min{0<f≤t(d)}{T(f) + F(g(n, d, f), d + vT(f))}Otherwise Here T(f) is the time interval for the frame of size f, and we have T(f) = n 0(n, r, f)·te + n 1(n, r, f)·ts + n c(n, r, f)·tc, and r = (d + 0.5fvΔt)2 + h2. B. Estimate the number of tags For each query round the reader needs to estimate the number of active tags, so as to provide an accurate input parameter for selecting the next optimal frame size. Current estimation schemes [12] [21] are not really suitable for our probabilistic model, because their methodology is based on the ideal case when pi(r) = pt(r)=1. Therefore we propose an alternative scheme to estimate the number of tags. Our methodology is based on Theorem 2. Theorem 2: As defined in Eq. (7), n 0(n, r, f) is monotoni￾cally decreasing with n. n c(n, r, f) is monotonically increas￾ing with n. Due to lack of space, we omit the proof of Theorem 2. According to Theorem 2, since n 0(n, r, f) and n c(n, r, f) are monotonic with variable n, given the constant values of pt(r), pi(r), f, the reader will obtain various expected values of n 0, n c with various n. Based on this property, we can estimate the number of tags n by leveraging the binary search method, according to either n 0(n, r, f) or n c(n, r, f). Here we take the observed number of empty slots n 0(n, r, f) as the metric for estimation. Assume that the upper bound for n is N, i.e., n ∈ [0, N], then the corresponding expected number of empty slots n 0 ∈ [n 0(N, r, f), n 0(0, r, f)]. We now use binary search to find the value of n according to n 0. We start from the value n = N/2, and compare n 0(n , r, f) with n 0. If n 0(n , r, f) > n 0, then n falls into the range (N/2, N]. If n 0(n , r, f) < n 0, then n falls into the range [0, N/2). Otherwise n = N/2. We continue the iterative search until we find an exact point value for n. This binary search procedure will iterate at most log2(N) steps. C. Adaptive frame size selection In Section VI-A we have proposed a dynamic programming based solution for selecting optimal frame sizes. By using this methodology we can accurately select the optimal frame sizes as the container moves along the conveyor. However, the dynamic program requires to maintain two (N + 1)×M sized tables. Algorithm 1 needs (N + 1)×M iterations to calculate values for the tables. For each iteration different frame sizes f ∈ (0, M − i] should be tested. According to Eq.(7) for each f it requires at most N iterations to calculate n 1(n, r, f), thus the computation complexity is O(N2 ·M2). Although the two tables can be preprocessed in the reader beforehand, the values of N and M can be rather large numbers. Hence in some situations the reader may not afford to conduct such calculations. Therefore an adaptive approach is essential for the reader to quickly select appropriate frame sizes while guaranteeing efficiency for the anti-collision scheme. We attempt to obtain a local optimal frame size for each Query Round, so as to maximize the proportion of single slots within each frame. Our solution relies on the following Theorem. This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the main Technical Program at IEEE INFOCOM 2010. Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore. Restrictions apply.