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. on the propagation probability due to the various message Now we need to calculate g(n,d,f),the expected number lengths,because these command messages all have very small of tags left unread in frame size f.As the tags'container is message lengths.If it is necessary to take the message length continuously moving on the conveyor,the container's position into consideration.we can similarly estimate the bit-wise actually changes slightly for each slot inside the frame.Since propagation probability parameters according to the above the candidate frame size f is restricted in [1,t(d)],according to methodology the definition of t(d)in table I,as long as we set a not so large value for fmar (empirically fmaz should not be larger than VI.EFFICIENT TAG IDENTIFICATION ACCORDING TO THE n for efficiency reason),we can assume that the container's PROBABILISTIC MODEL position does not change too much within each selected frame. A.Dynamic programming based solution Then the average position for those tags within the frame is d'=d+0.5.fvAt.Thus the average distance between In this section we solve the optimization problem proposed the tags and the reader within the frame is r=vd2+h2. in Section IV by using dynamic programming.According to the problem statement in Section IV,we further summarize According to the probabilistic model,the expected number of tags successfully read within the frame size f is the notations in Table I. h(n,d,f)=n(n,r,f)·p(r）pt(r). TABLE I NOTATION OF PARAMETERS Hence, Parameters Definitions g(n,d,f)=n-h(n,d,f). F(n,d) The minimum expected number of slots required to read n tags starting from horizontal position d Based on the above analysis,as the total number of tags in h(n,d,f) Given n tags,the expected number of tags read in frame size f starting from position d one container is N,and the starting position for the container g(n,d,f) Given n tags,the expected number of tags left unread to enter the reader's range is d=-D/2,the objective for the in frame size f starting from position d optimization problem is to calculate F(N,-D/2).According △t The average time interval for one slot to the formulation of F(n.d),this optimization problem has td)】 The upper bound for candidate frame sizes,which is the minimum value of the supported maximum frame size overlapping subproblems and optimal substructures.We can 1.e. solve it with dynamic programming.Algorithm 1 utilizes the dynamic programming methodology to calculate various F(n,d)for various (n,d)pairs.We set M=as the Without loss of generality,we assume by adjusting the speed number of discrete positions at different slots,and we use of the conveyor,v,all tags can be identified within the reader's i(0<i<M)to denote the index of the discrete positions. effective range for average cases,i.e.,the expected duration then the corresponding discrete position d=(i-M/2).v.At. for identifying all N tags is smaller than D/v.For F(n,d), Then we maintain a table F[n][i]of size (N+1)x M to which is the minimum expected number of slots required to store all discrete values for F(n,d),and a table f[n][i]of read n tags starting from position d(-D/2 dD/2),it size (N+1)x M to store the optimal values for the first has the formulation as follows: frame size f corresponding to F(n,d).Inside this algorithm. we first initialize the F[n][i]values for n =0,1.Then we F(n,d)= iteratively calculate the optimal values for F[n]]and f[n] 0 if n=0 in a bottom-up approach.When the iteration finishes,all the (N+1).M values are calculated. (P()2(P:() if n=1 minto<fst(d))f +F(g(n,d,f),d+fvt)}otherwise. By utilizing the optimal parameters stored in f[n,we propose Algorithm 2 to perform the RFID tag identification. In the above formulation,if n =0,there is no tag left The reader first performs a read round with initial frame size C to be read,then the minimum number of slots required is and obtains no,n,nc and ns.Here no,n,ne are respectively equal to 0.If n=1,then the number of slots required is the number of empty/single/collision slots,while ns is the expected to be ()whererv+h2 and h number of tags successfully identified in the single slots.Then is the height of the reader over the conveyor.Otherwise when the reader estimates the number of active tags for this round n 1,by enumerating all possible frame sizes f E [1,t(d)] as n,thus the number of tags left unread is n-ns.In the for the first frame,F(n,d)is obtained from the minimum following steps for each round the reader first selects the value of f+F(g(n,d,f),d+fvAt),where the second term optimal frame size f*.Given the number of tags left unread denotes the minimum expected number of slots needed to read n-ns and the current position of the container d,the function all tags left after we choose the first frame size f.Note the selectOptimalFrameSize(n-n d)in Alg.2,line 7 just outputs position is updated to d+f.v.At.Here we assume we can f=f[n-nli]as the optimal frame size,wherei △d choose any integer value for the frame size f.If we need to Then the reader performs a read round with the frame size conform to the o protocol [1],we can select the candidate f*.After that the reader estimates the number of active tags frame size f from the set 20,21,...,2Q,for 2Q<t(d)and for this round.In order to guarantee those tags left unread Q≤15. to always have opportunities to seize a slot inside the frame, Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply.on the propagation probability due to the various message lengths, because these command messages all have very small message lengths. If it is necessary to take the message length into consideration, we can similarly estimate the bit-wise propagation probability parameters according to the above methodology. VI. EFFICIENT TAG IDENTIFICATION ACCORDING TO THE PROBABILISTIC MODEL A. Dynamic programming based solution In this section we solve the optimization problem proposed in Section IV by using dynamic programming. According to the problem statement in Section IV, we further summarize the notations in Table I. TABLE I NOTATION OF PARAMETERS Parameters Definitions F(n, d) The minimum expected number of slots required to read n tags starting from horizontal position d h(n, d, f) Given n tags, the expected number of tags read in frame size f starting from position d g(n, d, f) Given n tags, the expected number of tags left unread in frame size f starting from position d Δt The average time interval for one slot t(d) The upper bound for candidate frame sizes, which is the minimum value of the supported maximum frame size fmax and the number of available time slots fava, i.e., t(d) = min{fmax, fava}, where fava = D/2−d v·Δt Without loss of generality, we assume by adjusting the speed of the conveyor, v, all tags can be identified within the reader’s effective range for average cases, i.e., the expected duration for identifying all N tags is smaller than D/v. For F(n, d), which is the minimum expected number of slots required to read n tags starting from position d(−D/2 ≤ d ≤ D/2), it has the formulation as follows: F(n, d) = ⎧ ⎨ ⎩ 0 if n = 0 1 (pi(r))2·(pt(r))2 if n = 1 min{0<f≤t(d)}{f + F(g(n, d, f), d + fvΔt)} otherwise. In the above formulation, if n = 0, there is no tag left to be read, then the minimum number of slots required is equal to 0. If n = 1, then the number of slots required is expected to be 1 (pi(r))2·(pt(r))2 , where r = √d2 + h2, and h is the height of the reader over the conveyor. Otherwise when n > 1, by enumerating all possible frame sizes f ∈ [1, t(d)] for the first frame, F(n, d) is obtained from the minimum value of f + F(g(n, d, f), d + fvΔt), where the second term denotes the minimum expected number of slots needed to read all tags left after we choose the first frame size f. Note the position is updated to d + f · v · Δt. Here we assume we can choose any integer value for the frame size f. If we need to conform to the Q protocol [1], we can select the candidate frame size f from the set 20, 21, ..., 2Q, for 2Q ≤ t(d) and Q ≤ 15. Now we need to calculate g(n, d, f), the expected number of tags left unread in frame size f. As the tags’ container is continuously moving on the conveyor, the container’s position actually changes slightly for each slot inside the frame. Since the candidate frame size f is restricted in [1, t(d)], according to the definition of t(d) in table I, as long as we set a not so large value for fmax (empirically fmax should not be larger than n for efficiency reason), we can assume that the container’s position does not change too much within each selected frame. Then the average position for those tags within the frame is d = d + 0.5 · fvΔt. Thus the average distance between the tags and the reader within the frame is r = √d2 + h2. According to the probabilistic model, the expected number of tags successfully read within the frame size f is h(n, d, f) = n 1(n, r, f) · pi(r) · pt(r). Hence, g(n, d, f) = n − h(n, d, f). Based on the above analysis, as the total number of tags in one container is N, and the starting position for the container to enter the reader’s range is d = −D/2, the objective for the optimization problem is to calculate F(N, −D/2). According to the formulation of F(n, d), this optimization problem has overlapping subproblems and optimal substructures. We can solve it with dynamic programming. Algorithm 1 utilizes the dynamic programming methodology to calculate various F(n, d) for various (n, d) pairs. We set M = D v·Δt as the number of discrete positions at different slots, and we use i(0 < i ≤ M) to denote the index of the discrete positions, then the corresponding discrete position d = (i−M/2)·v ·Δt. Then we maintain a table F[n][i] of size (N + 1) × M to store all discrete values for F(n, d), and a table f[n][i] of size (N + 1) × M to store the optimal values for the first frame size f corresponding to F(n, d). Inside this algorithm, we first initialize the F[n][i] values for n = 0, 1. Then we iteratively calculate the optimal values for F[n][i] and f[n][i] in a bottom-up approach. When the iteration finishes, all the (N + 1) · M values are calculated. By utilizing the optimal parameters stored in f[n][i], we propose Algorithm 2 to perform the RFID tag identification. The reader first performs a read round with initial frame size C and obtains n0, n1, nc and ns. Here n0, n1, nc are respectively the number of empty/single/collision slots, while ns is the number of tags successfully identified in the single slots. Then the reader estimates the number of active tags for this round as n, thus the number of tags left unread is n − ns. In the following steps for each round the reader first selects the optimal frame size f ∗. Given the number of tags left unread n−ns and the current position of the container d, the function selectOptimalFrameSize(n−ns, d) in Alg.2, line 7 just outputs f ∗ = f[n−ns][i] as the optimal frame size, where i = d+D/2 Δd . Then the reader performs a read round with the frame size f ∗. After that the reader estimates the number of active tags for this round. In order to guarantee those tags left unread to always have opportunities to seize a slot inside the frame, 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.