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. Theorem 3:To maximize the proportion of single slotsslots for various strategies.We find that using the dynamic within each frame,the local optimal frame size is f*=program based strategy (DP)always leads to the smallest n.(p(r))2.pe(r),and the efficiency is=1.here e is the number of slots to complete the tag reading,compared with natural number. the other strategies.The adaptive strategy (AD)to select Proof:According to the probabilistic model,after the local optimal frame sizes also achieves good performance for phases (1)and (2),only n'=n.pi(r)2 tags are able to reading the tags,in that its required number of slots is only be involved in the Query Round.We denote these tags as 7%-8%larger than the former.Both strategies require fewer a set S.Then due to the probabilistic propagation in the slots than the strategy that selects f=n,which proves to be reverse channel with probability pt(r),the final number of near optimal in the ideal propagation situation.The fixed frame single slots is n.For those tags in set S,since each tag size strategy with f=32 always requires the largest number will uniformly select a slot and successfully backscatter RN/6 of slots,due to the lack of dynamic adjustment for frame with probability pa(r),we can depict the process with an size.In Fig.4(c)we compare the required number of slots for equivalent model as follows.Each tag in set S is able to the above four strategies under the two different propagation uniformly select a slot inside the frame with probability p(r) situations,when the number of tags is 50.From left to right and backscatter with probability equal to 1.Then based on this the required numbers of slots are respectively corresponding model the final number of tags involved in the Query Round to:(1)dynamic program based strategy,(2)adaptive strategy, is nf =n'.p(r).According to the conclusion in [6],for the (3)"f n"strategy,and (4)fixed frame size strategy.We ideal propagation case,the local optimal frame size should observe that for each strategy the required numbers of slots be f*=nf in order to maximize the channel efficiency for under the controlled situation are always smaller than the each frame,and the fraction of single slots is Thus we have noisy situation.The reason is that in the noisy situation,the f=n'.pe(r)=n(pi(r))2.p(r),and the efficiency=. propagation loss is more frequent than the controlled situation, thus causing the reader to need more slots to finish reading the The theorem gets proved. tags.In Fig.4(d)we evaluate the normalized throughput for Based on Theorem 3,for each Ouery Round the reader various initial frame sizes according to the dynamic program can quickly calculate f*according to the current number based strategy.The normalized throughput is defined as the of active tags n,propagation probability pi(r),and p(r)at number of identified tags divided by the required total number the container's position d.Therefore the adaptive approach of slots.As the number of tags increases from 10 to 40,the to select frame sizes is as follows:As the container enters throughput increases rapidly.When the number of tags is over the reader's effective range,the reader continuously tracks its 40,the throughput increases slowly and converges to about position according to d=v.t-D/2.For each Query Round 0.25.The achieved throughput is smaller than 0.368,which is the reader first estimates the number of tags left unread n. the theoretical maximum throughput for the ideal propagation Since the values of pi(r)and pt(r)have already been captured situation. for various distances r =vd2+h2,then according to the We evaluate the performance of estimating the number of current position d for the tags,the reader issues a new frame tags in Fig.4(e).We track a query cycle and compare the with size f*=n.(pi(r))2.pt(r).The process continues until estimated number of active tags and the actual number of no collision slots or single slots exist inside the frame. active tags.We observe that for each round the estimated VII.PERFORMANCE EVALUATION number of tags is very near the actual number of tags.The maximum estimate error is at most 14%when the number of We have conducted simulations in Matlab.We consider actual tags is larger than 20.As the number of tags reduces. a scenario of reading moving tags on the conveyor,where the maximum estimate error is at most 50%,this is because the effective range for the reader is D 12 meters (m), when the tag size is small,the variance for the number of the moving speed of the conveyor is v=3 meters/second empty slots or collision slots becomes relatively large,thus (m/s),and the average time interval of each slot is At =10 causing the estimate error larger than the large tag size case. millisecond (ms).For the Query Cycle we set the default In Fig.4(f)we measure the expected maximum number of value for the initial frame size as f =10.We respectively tags which can be identified for various conveyor speeds, consider two situations for the propagation environment.The under the noisy condition.We use the dynamic program based first situation is a controlled condition which is near to the strategy to read tags,varying the conveyor speed v.For each free space environment,and the second situation is a noisy specified conveyor speed v,we gradually increase the number condition where propagation attenuations are distinct.We of tags n to see if they can be identified in time.We run 500 use the parameters in Fig.4(a)to simulate the propagation simulations for each settings,if we find that those tags can probability for pi(r)and p(r).Here for simplification we set be identified for most cases (>50%),we keep increasing Pi(r)=pt(r).As the reader's effective range is D =12m,n,otherwise we stop and get the corresponding expected the distance between the tag and the reader ranges from Om maximum number of tags,nmaz(v).As v increases from to 6m. 1m/s to 4m/s,the expected number of available slots reduces We evaluate the performance of various strategies to select from 1200 to 300,hence nma(v)reduces from 250 to 65. frame sizes.In Fig.4(b)we compare the required number of It means that given a fixed conveyor speed,if the tag size Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions applyTheorem 3: To maximize the proportion of single slots within each frame, n 1 f , the local optimal frame size is f ∗ = n ·(pi(r))2 · pt(r), and the efficiency is n 1 f ∗ = 1 e , here e is the natural number. Proof: According to the probabilistic model, after the phases (1) and (2), only n = n · pi(r)2 tags are able to be involved in the Query Round. We denote these tags as a set S. Then due to the probabilistic propagation in the reverse channel with probability pt(r), the final number of single slots is n 1. For those tags in set S, since each tag will uniformly select a slot and successfully backscatter RN16 with probability pt(r), we can depict the process with an equivalent model as follows. Each tag in set S is able to uniformly select a slot inside the frame with probability pt(r) and backscatter with probability equal to 1. Then based on this model the final number of tags involved in the Query Round is nf = n · pt(r). According to the conclusion in [6], for the ideal propagation case, the local optimal frame size should be f ∗ = nf in order to maximize the channel efficiency for each frame, and the fraction of single slots is 1 e . Thus we have f ∗ = n ·pt(r) = n·(pi(r))2 ·pt(r), and the efficiency n 1 f ∗ = 1 e . The theorem gets proved. Based on Theorem 3, for each Query Round the reader can quickly calculate f ∗ according to the current number of active tags n, propagation probability pi(r), and pt(r) at the container’s position d. Therefore the adaptive approach to select frame sizes is as follows: As the container enters the reader’s effective range, the reader continuously tracks its position according to d = v · t − D/2. For each Query Round the reader first estimates the number of tags left unread n. Since the values of pi(r) and pt(r) have already been captured for various distances r = √d2 + h2, then according to the current position d for the tags, the reader issues a new frame with size f ∗ = n·(pi(r))2 · pt(r). The process continues until no collision slots or single slots exist inside the frame. VII. PERFORMANCE EVALUATION We have conducted simulations in Matlab. We consider a scenario of reading moving tags on the conveyor, where the effective range for the reader is D = 12 meters (m), the moving speed of the conveyor is v = 3 meters/second (m/s), and the average time interval of each slot is Δt = 10 millisecond (ms). For the Query Cycle we set the default value for the initial frame size as f = 10. We respectively consider two situations for the propagation environment. The first situation is a controlled condition which is near to the free space environment, and the second situation is a noisy condition where propagation attenuations are distinct. We use the parameters in Fig. 4(a) to simulate the propagation probability for pi(r) and pt(r). Here for simplification we set pi(r) = pt(r). As the reader’s effective range is D = 12m, the distance between the tag and the reader ranges from 0m to 6m. We evaluate the performance of various strategies to select frame sizes. In Fig. 4(b) we compare the required number of slots for various strategies. We find that using the dynamic program based strategy (DP) always leads to the smallest number of slots to complete the tag reading, compared with the other strategies. The adaptive strategy (AD) to select local optimal frame sizes also achieves good performance for reading the tags, in that its required number of slots is only 7%-8% larger than the former. Both strategies require fewer slots than the strategy that selects f = n, which proves to be near optimal in the ideal propagation situation. The fixed frame size strategy with f = 32 always requires the largest number of slots, due to the lack of dynamic adjustment for frame size. In Fig. 4(c) we compare the required number of slots for the above four strategies under the two different propagation situations, when the number of tags is 50. From left to right the required numbers of slots are respectively corresponding to: (1) dynamic program based strategy, (2) adaptive strategy, (3) “f = n” strategy, and (4) fixed frame size strategy. We observe that for each strategy the required numbers of slots under the controlled situation are always smaller than the noisy situation. The reason is that in the noisy situation, the propagation loss is more frequent than the controlled situation, thus causing the reader to need more slots to finish reading the tags. In Fig. 4(d) we evaluate the normalized throughput for various initial frame sizes according to the dynamic program based strategy. The normalized throughput is defined as the number of identified tags divided by the required total number of slots. As the number of tags increases from 10 to 40, the throughput increases rapidly. When the number of tags is over 40, the throughput increases slowly and converges to about 0.25. The achieved throughput is smaller than 0.368, which is the theoretical maximum throughput for the ideal propagation situation. We evaluate the performance of estimating the number of tags in Fig.4(e). We track a query cycle and compare the estimated number of active tags and the actual number of active tags. We observe that for each round the estimated number of tags is very near the actual number of tags. The maximum estimate error is at most 14% when the number of actual tags is larger than 20. As the number of tags reduces, the maximum estimate error is at most 50%, this is because when the tag size is small, the variance for the number of empty slots or collision slots becomes relatively large, thus causing the estimate error larger than the large tag size case. In Fig.4(f) we measure the expected maximum number of tags which can be identified for various conveyor speeds, under the noisy condition. We use the dynamic program based strategy to read tags, varying the conveyor speed v. For each specified conveyor speed v, we gradually increase the number of tags n to see if they can be identified in time. We run 500 simulations for each settings, if we find that those tags can be identified for most cases (≥ 50%), we keep increasing n, otherwise we stop and get the corresponding expected maximum number of tags, nmax(v). As v increases from 1m/s to 4m/s, the expected number of available slots reduces from 1200 to 300, hence nmax(v) reduces from 250 to 65. It means that given a fixed conveyor speed, if the tag size 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.