计算机科学与技术（参考文献）Efficient Tag Identification in Mobile RFID Systems

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. Efficient Tag Identification in Mobile RFID Systems Lei Xiett,Bo Shengf,Chiu C.Tan,Hao Han,Qun Lit,Daoxu Chent fState Key Laboratory of Novel Software Technology, Department of Computer Science and Technology,Nanjing University,China College of William and Mary,Williamsburg,VA,USA Email:fxielei@dislab.nju.edu.cn,fshengbo,cct,hhan,liqun}@cs.wm.edu,'cdx @nju.edu.cn Abstract-In this paper we consider how to efficiently identify In this paper,we consider the important problem of im- tags on the moving conveyor.Considering conditions like the path proving reading performance for RFID tags under a moving loss and multi-path effect in realistic settings,we first propose a probabilistic model for RFID tag identification.Based on this conveyor belt.We first bridge the gap between theoretical anti- model,we propose efficient solutions to identify moving RFID collision protocols and real world conditions by introducing a tags,according to the fixed-path mobility on the conveyor.A probabilistic model for RFID tag identification.Our model of- dynamic program based solution and an adaptive solution are fers a fundamental guidance for setting MAC layer parameters. proposed to select optimized frame sizes during the query cycles. such as the frame size for ALOHA based protocols.Based Simulation results indicate that by leveraging the probabilistic model our solutions can achieve much better performance than on our model,we propose protocols that improve reading using parameters for the ideal propagation situations. performance for moving RFID tags.Our proposed solution reduces the reading time by 23%than using parameters I.INTRODUCTION derived under ideal conditions with no propagation loss[6]. This improvement is achieved while adhering to the existing Radio frequency identification(RFID)technology is widely EPC Class 1 Gen 2 RFID standards. used in supply chain management as a means of monitoring We make the following contributions in this paper. physical goods and assets.For large warehouses with tens of 1)We give a probabilistic model for the slotted ALOHA thousands of physical goods entering and leaving each day, based anti-collision schemes,in order to understand the the process of collecting RFID tag IDs is highly automated principles for RFID tag identification under the realistic through the use of conveyor belts.Once goods are placed onto settings.We analyze how the physical layer property a conveyor belt,they move along on a fixed path at a constant affects the behavior of the MAC layer protocol. speed until they are read by RFID readers carefully placed 2)We propose efficient solutions to identify moving tags along the conveyor belt's path.Given the crucial role of supply on the conveyor according to the probabilistic model. chains to the economy,improving the performance of reading We present a dynamic program based solution and an RFID tags on a conveyor belt is an important component in adaptive solution of selecting frame sizes for efficient improving the overall efficiency. tag identification. RFID tags are simple devices that are unable to self-regulate 3)To the best of our knowledge,this is the first theoretical their radio transmissions to avoid collisions.An anti-collision work which investigates the realistic model for RFID tag protocol is used to regulate tag replies in order to obtain all identification by taking the probabilistic propagation into the available tag IDs in the shortest amount of time.One consideration.We give a fundamental illustration of how of the most common standards for supply chain RFID tags the current anti-collision protocol works in the realistic is the EPC Class 1 Gen 2 RFID standards.This standard is settings,and give indications for a closer coupling of based on a slotted ALOHA process to regulate tag responses. the physical and MAC layers. Prior research [1][2]on improving performance have focused The rest of the paper is as follows.Sections II and III on optimizing the parameters used in this slotted ALOHA present the related work and RFID background respectively. model.However,these research only considered optimizing We formulate our problem in Section IV,and present our the parameters when reading static RFID tags under ideal probabilistic model in Section V.Section VI contains the environmental conditions.Real world environmental condi- protocols for efficient reading of mobile RFID tags.Our tions such as path loss and multi-path effects,as well as the evaluation is in Section VII,and we conclude in Section VIII. fixed-path mobility of RFID tags are not considered.As such, these results are less applicable to our problem.Other work II.RELATED WORKS by [3][4][5]performed practical experiments to determine the best parameters.However,it is unclear how well these findings RFID anti-collision protocols can be categorized into tree- can be generalized to other environmental settings based and ALOHA-based ones.Tree-based protocols resolve collisions by muting subsets of tags that are involved in This work was done when the first author worked as a visiting scholar at a collision [7].Pan et al.propose a Smart Trend-Traversal the College of William and Mary. protocol [8],a Query Tree-based scheme,to conduct RFID tag 978-1-4244-5837-0/10/S26.00©2010EEE Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply

Efficient Tag Identification in Mobile RFID Systems Lei Xie†‡, Bo Sheng‡, Chiu C. Tan‡, Hao Han‡, Qun Li‡, Daoxu Chen† †State Key Laboratory of Novel Software Technology, Department of Computer Science and Technology, Nanjing University, China ‡College of William and Mary, Williamsburg, VA, USA Email: †xielei@dislab.nju.edu.cn, ‡{shengbo, cct, hhan, liqun}@cs.wm.edu, †cdx@nju.edu.cn Abstract—In this paper we consider how to efficiently identify tags on the moving conveyor. Considering conditions like the path loss and multi-path effect in realistic settings, we first propose a probabilistic model for RFID tag identification. Based on this model, we propose efficient solutions to identify moving RFID tags, according to the fixed-path mobility on the conveyor. A dynamic program based solution and an adaptive solution are proposed to select optimized frame sizes during the query cycles. Simulation results indicate that by leveraging the probabilistic model our solutions can achieve much better performance than using parameters for the ideal propagation situations. I. INTRODUCTION Radio frequency identification (RFID) technology is widely used in supply chain management as a means of monitoring physical goods and assets. For large warehouses with tens of thousands of physical goods entering and leaving each day, the process of collecting RFID tag IDs is highly automated through the use of conveyor belts. Once goods are placed onto a conveyor belt, they move along on a fixed path at a constant speed until they are read by RFID readers carefully placed along the conveyor belt’s path. Given the crucial role of supply chains to the economy, improving the performance of reading RFID tags on a conveyor belt is an important component in improving the overall efficiency. RFID tags are simple devices that are unable to self-regulate their radio transmissions to avoid collisions. An anti-collision protocol is used to regulate tag replies in order to obtain all the available tag IDs in the shortest amount of time. One of the most common standards for supply chain RFID tags is the EPC Class 1 Gen 2 RFID standards. This standard is based on a slotted ALOHA process to regulate tag responses. Prior research [1][2] on improving performance have focused on optimizing the parameters used in this slotted ALOHA model. However, these research only considered optimizing the parameters when reading static RFID tags under ideal environmental conditions. Real world environmental condi￾tions such as path loss and multi-path effects, as well as the fixed-path mobility of RFID tags are not considered. As such, these results are less applicable to our problem. Other work by [3][4][5] performed practical experiments to determine the best parameters. However, it is unclear how well these findings can be generalized to other environmental settings. This work was done when the first author worked as a visiting scholar at the College of William and Mary. In this paper, we consider the important problem of im￾proving reading performance for RFID tags under a moving conveyor belt. We first bridge the gap between theoretical anti￾collision protocols and real world conditions by introducing a probabilistic model for RFID tag identification. Our model of￾fers a fundamental guidance for setting MAC layer parameters, such as the frame size for ALOHA based protocols. Based on our model, we propose protocols that improve reading performance for moving RFID tags. Our proposed solution reduces the reading time by 23% than using parameters derived under ideal conditions with no propagation loss[6]. This improvement is achieved while adhering to the existing EPC Class 1 Gen 2 RFID standards. We make the following contributions in this paper. 1) We give a probabilistic model for the slotted ALOHA based anti-collision schemes, in order to understand the principles for RFID tag identification under the realistic settings. We analyze how the physical layer property affects the behavior of the MAC layer protocol. 2) We propose efficient solutions to identify moving tags on the conveyor according to the probabilistic model. We present a dynamic program based solution and an adaptive solution of selecting frame sizes for efficient tag identification. 3) To the best of our knowledge, this is the first theoretical work which investigates the realistic model for RFID tag identification by taking the probabilistic propagation into consideration. We give a fundamental illustration of how the current anti-collision protocol works in the realistic settings, and give indications for a closer coupling of the physical and MAC layers. The rest of the paper is as follows. Sections II and III present the related work and RFID background respectively. We formulate our problem in Section IV, and present our probabilistic model in Section V. Section VI contains the protocols for efficient reading of mobile RFID tags. Our evaluation is in Section VII, and we conclude in Section VIII. II. RELATED WORKS RFID anti-collision protocols can be categorized into tree￾based and ALOHA-based ones. Tree-based protocols resolve collisions by muting subsets of tags that are involved in a collision [7]. Pan et al. propose a Smart Trend-Traversal protocol [8], a Query Tree-based scheme, to conduct RFID tag 978-1-4244-5837-0/10/$26.00 ©2010 IEEE 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

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. arbitration.The ALOHA protocol was first developed for ran- and the tag's antenna gain is Gt.The wave length is A.Assume dom access in packet radio networks.To improve efficiency for the transmitter power from the reader is P measured in watts. RFID systems,the slotted ALOHA is developed [1][2].In [9]. By considering power flux density,the power received at the Schoute analyzes the performance of the dynamic frame-sized tag is P According to the radar principle. ALOHA.In [10]Floerkemeier presents a Bayesian strategy the amount of energy reflected by an object is dependent on to dynamically determine frame size.In [11],Vogt uses the the reflective area of the object.This area is referred to as Markov process to model the read process and suggests a set of the radar cross section (RCS).We use o to denote the RCS. dynamic frame sizes in the read process.An estimate function then the reflected power from the tag towards the reader is is also proposed to estimate the tag quantity.In [6].Lee et al. PThe power density yielded at the receiver of adopt Vogt's tag estimation method and derive the dynamic the reader is given byP.According to the frame size for achieving maximum channel efficiency.They (4Tr4 above analysis,we have the path loss as follows: claim that if the frame size approximately equals the number of tags plus one,the maximum channel efficiency can be P-P- (1) obtained.In [12].Murali et al.provide very fast and reliable estimation mechanisms for tag quantity in a more practical According to Eq.(1),we define the free space path loss over approach.To address the multiple-reading problem,Qian et al. distance r as PL(r)=()2.Apparently the above free propose the Lottery Frame scheme [13],a replicate-insensitive space propagation model is deterministic.However,this model estimation protocol.In [14].Bo et al.consider the problem rarely describes the actual propagation situation accurately. of identifying popular categories of RFID tags out of a large In realistic settings the propagation is probabilistic,because collection of tags.In [15],a fast missing tag detection protocol orientations of tags affect the backscatter efficiency,and phe- for RFID based inventory control applications was provided. nomenons such as absorption and multi-path fading further The unreliability of the physical layer in RFID systems make the attenuation not accurately predicted. has a crucial impact on tag reading.To show the effect of We denote the down-link communication from the reader errors on the C1G2 protocol,Mitsugi et al.[16]present to a tag as the forward channel,and denote the up-link simulation results that bit errors significantly degrade the communication from a tag to the reader as the reverse channel. C1G2 performance.In [3].Buettner et al.examine the per- For successful reading of a passive tag with the backscatter formance of the C1G2 RFID system in a realistic setting. scheme,there are two thresholds to meet the physical require- They identify factors that degrade overall performance and ments.The first is the tag power(sensitivity)threshold,Ps.It reliability with a focus on the physical layer.They find that is the minimum received power necessary to turn on an RFID physical layer considerations have a significant impact on chip.The second is the reader sensitivity threshold,Ps.It is reader performance,and that this is exacerbated by a lack of the minimum level of the tag signal that the reader can detect integration between physical and MAC layers.In [5],Aroor and resolve.Thus it must satisfy P2>Ps for the tag to be et al.identify the state of the technical capability of passive powered up and resolve the received signal,and also P>Prs UHF RFID systems using a simple,empirical,experimental for the reader to detect and resolve the received signal. approach.They examine various read distances for free space, near metal and near water situations.In [4].Ramakrishnan B.Tag inventory and access et al.describe the first comprehensive benchmark suite for The MAC protocol for the C1G2 system is based on Slotted passive UHF RFID tags.In [17]Ren et al.performed extensive ALOHA,where each frame has a number of slots and each experiments on an industrial conveyor belt to determine the active tag will reply in a randomly selected slot per frame. effects of mobility on RFID reader performance.In [18] When a reader(interrogator)wishes to read a set of tags,it first Jeffery et al.conduct experiments in realistic settings and find powers up and transmits a continuous wave (CW)to energize that within each reader's detection range,there are two distinct the tags.It then initiates a series of frames,varying the number regions:major detection region and minor detection region. of slots in each frame to best accommodate the number of III.PRELIMINARY tags.After all tags are read,the reader powers down.We refer to an individual frame as a Ouery Round,and the series of A.Far-Field Propagation and Backscatter Principle Query Rounds between power down periods as a Ouery Cycle. Class-1 Generation-2(C1G2)RFID systems [19]as defined For each Ouery Round,the reader can optionally transmit a by EPCglobal are based on UHF frequencies.They use far- Select command which limits the number of active tags by field communication and the physical property of backscatter- providing a bit mask.Then a Query command is transmitted ing power [20].Far-field communication uses the electric radio which contains the uplink frequency and data encoding,the O waves,where the reader sends a continuous base signal that is parameter determining the number of slots for the following reflected back by the tag's antenna.A backscatter tag operates frame,and a Target parameter.When a tag receives a Query by modulating the electronics connected to the antenna so as command,it chooses a random number in the range(0,20-1), to control the reflection of electromagnetic energy.Suppose a where O is in the range (0,15),and the value is stored in the reader and a tag are separated by a distance of r in the free slot counter of the tag.If a tag stores a 0 in its slot counter,it space propagation scenario.The reader's antenna gain is Gr will immediately backscatter a 16 bit random number,denoted Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply

arbitration. The ALOHA protocol was first developed for ran￾dom access in packet radio networks. To improve efficiency for RFID systems, the slotted ALOHA is developed [1][2]. In [9], Schoute analyzes the performance of the dynamic frame-sized ALOHA. In [10] Floerkemeier presents a Bayesian strategy to dynamically determine frame size. In [11], Vogt uses the Markov process to model the read process and suggests a set of dynamic frame sizes in the read process. An estimate function is also proposed to estimate the tag quantity. In [6], Lee et al. adopt Vogt’s tag estimation method and derive the dynamic frame size for achieving maximum channel efficiency. They claim that if the frame size approximately equals the number of tags plus one, the maximum channel efficiency can be obtained. In [12], Murali et al. provide very fast and reliable estimation mechanisms for tag quantity in a more practical approach. To address the multiple-reading problem, Qian et al. propose the Lottery Frame scheme [13], a replicate-insensitive estimation protocol. In [14], Bo et al. consider the problem of identifying popular categories of RFID tags out of a large collection of tags. In [15], a fast missing tag detection protocol for RFID based inventory control applications was provided. The unreliability of the physical layer in RFID systems has a crucial impact on tag reading. To show the effect of errors on the C1G2 protocol, Mitsugi et al. [16] present simulation results that bit errors significantly degrade the C1G2 performance. In [3], Buettner et al. examine the per￾formance of the C1G2 RFID system in a realistic setting. They identify factors that degrade overall performance and reliability with a focus on the physical layer. They find that physical layer considerations have a significant impact on reader performance, and that this is exacerbated by a lack of integration between physical and MAC layers. In [5], Aroor et al. identify the state of the technical capability of passive UHF RFID systems using a simple, empirical, experimental approach. They examine various read distances for free space, near metal and near water situations. In [4], Ramakrishnan et al. describe the first comprehensive benchmark suite for passive UHF RFID tags. In [17] Ren et al. performed extensive experiments on an industrial conveyor belt to determine the effects of mobility on RFID reader performance. In [18] Jeffery et al. conduct experiments in realistic settings and find that within each reader’s detection range, there are two distinct regions: major detection region and minor detection region. III. PRELIMINARY A. Far-Field Propagation and Backscatter Principle Class-1 Generation-2 (C1G2) RFID systems [19] as defined by EPCglobal are based on UHF frequencies. They use far- field communication and the physical property of backscatter￾ing power [20]. Far-field communication uses the electric radio waves, where the reader sends a continuous base signal that is reflected back by the tag’s antenna. A backscatter tag operates by modulating the electronics connected to the antenna so as to control the reflection of electromagnetic energy. Suppose a reader and a tag are separated by a distance of r in the free space propagation scenario. The reader’s antenna gain is Gr and the tag’s antenna gain is Gt. The wave length is λ. Assume the transmitter power from the reader is P1 measured in watts. By considering power flux density, the power received at the tag is P2 = P1·Gr·Gt·λ2 (4π)2r2 . According to the radar principle, the amount of energy reflected by an object is dependent on the reflective area of the object. This area is referred to as the radar cross section (RCS). We use σ to denote the RCS, then the reflected power from the tag towards the reader is P3 = P1·Gr·σ (4π)2r2 . The power density yielded at the receiver of the reader is given by P4 = P1·G2 r·Gt·λ2·σ (4π)4r4 . According to the above analysis, we have the path loss as follows: P1 P2 = P3 P4 = 1 GrGt ( 4πr λ ) 2. (1) According to Eq.(1), we define the free space path loss over distance r as P Lf s(r)=( 4πr λ )2. Apparently the above free space propagation model is deterministic. However, this model rarely describes the actual propagation situation accurately. In realistic settings the propagation is probabilistic, because orientations of tags affect the backscatter efficiency, and phe￾nomenons such as absorption and multi-path fading further make the attenuation not accurately predicted. We denote the down-link communication from the reader to a tag as the forward channel, and denote the up-link communication from a tag to the reader as the reverse channel. For successful reading of a passive tag with the backscatter scheme, there are two thresholds to meet the physical require￾ments. The first is the tag power (sensitivity) threshold, Pts. It is the minimum received power necessary to turn on an RFID chip. The second is the reader sensitivity threshold, Prs. It is the minimum level of the tag signal that the reader can detect and resolve. Thus it must satisfy P2 > Pts for the tag to be powered up and resolve the received signal, and also P4 > Prs for the reader to detect and resolve the received signal. B. Tag inventory and access The MAC protocol for the C1G2 system is based on Slotted ALOHA, where each frame has a number of slots and each active tag will reply in a randomly selected slot per frame. When a reader (interrogator) wishes to read a set of tags, it first powers up and transmits a continuous wave (CW) to energize the tags. It then initiates a series of frames, varying the number of slots in each frame to best accommodate the number of tags. After all tags are read, the reader powers down. We refer to an individual frame as a Query Round, and the series of Query Rounds between power down periods as a Query Cycle. For each Query Round, the reader can optionally transmit a Select command which limits the number of active tags by providing a bit mask. Then a Query command is transmitted which contains the uplink frequency and data encoding, the Q parameter determining the number of slots for the following frame, and a Target parameter. When a tag receives a Query command, it chooses a random number in the range (0, 2Q−1), where Q is in the range (0,15), and the value is stored in the slot counter of the tag. If a tag stores a 0 in its slot counter, it will immediately backscatter a 16 bit random number, denoted 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

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. by RN16.Upon receiving RN16,the reader will echo RN/6 to finish reading all tags as small as possible.Assume that in an ACK command.If the tag successfully receives RN/6,it the average durations for empty/single/collision slots are all will backscatter its ID information (PC+EPC+CRC/6).Then nearly equal to At.Since the reader is responsible to set the a subsequent OueryRep command will be sent to the tag, frame size f for each Ouery Round,it needs to efficiently set a signaling the end of the slot and toggling an inventoried flag in series of frame sizes f1,f2,...,fm (0D between 10 15 5 0 each other.In this way,only one container is in the reading (a)Probability mass function range of the reader at any time.Assume the number of tags (b)Cumulative distributed function in a container is N.As the time interval for one container to stay within the effective reading range is limited to Fig.2.An example to explain the intuition of the objective. the RFID reader system needs to finish identifying all tags While a container is moving within the reader's range,its inside each container within this time interval.Note that due horizontal position is d(see Fig.1).For the ease of presenta- to random issues in the anti-collision scheme,e.g,the system tion,we respectively set the horizontal position at the entrance, may occasionally encounter much higher collisions than the the middle and the exit of the reader's effective range as0 expected situation,in realistic settings the reader can never and 2.Thus the distance between the tags in the container guarantee to finish identifying all tags in time,whatever the and the reader is r =vd2+h2.So when the container is speed of the conveyor is.Therefore the objective to design the moving on the conveyor,the propagation loss for both the RFID system is to make the expected duration for identifying forwarding channel and the reverse channel keeps changing all tags as short as possible,so that all tags can be identified as the distance r varies.Hence the probability varies for the in time with high possibility.Fig.2 illustrates the intuition tags to successfully receive and backscatter the signal to the of this objective.In Fig.2(a)we use Poisson distribution to reader,affecting the whole procedure for the tag inventory depict the duration distribution to finish identifying all N tags. and access.In order to solve the aforementioned optimization The horizontal axis k is the duration and the vertical axis problem,we need to investigate the probabilistic model for is the probability.We show three distributions with various RFID tag identification.Thus in the next two sections,we first mean durations A=1,4,10.In Fig.2(b)we depict the cor- propose a probabilistic model for RFID tag identification,then responding cumulative distribution functions.We observe that we accordingly propose an efficient tag identification scheme in order to finish identifying all tags within a fixed duration for identifying moving tags. k,the scheme with the smallest mean duration A =1 always has the highest probability to achieve that,while the scheme V.PROBABILISTIC MODEL FOR RFID TAG IDENTIFICATION with A =10 always has the lowest probability.Therefore, A.Probabilistic parameters for propagation in order to ensure all tags can be identified in time with high According to Section III-A,we know that the realistic possibility,a practical method is to make the expected duration propagation model is probabilistic,since the path loss and the Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply

by RN16. Upon receiving RN16, the reader will echo RN16 in an ACK command. If the tag successfully receives RN16, it will backscatter its ID information (PC+EPC+CRC16). Then a subsequent QueryRep command will be sent to the tag, signaling the end of the slot and toggling an inventoried flag in the tag to make it keep silent in the following rounds. If the ID is not successfully received by the reader, an NAK command is sent which resets the tag so as to keep the tag active in the next round. Upon receiving the QueryRep command, the remaining tags will decrement their slot counters, and respond with RN16 if their slot counters are set to 0. When the number of QueryReps is equal to 2Q, the current QueryRound ends. If there are still tags left unread, then the reader issues a QueryAdjust command to start a new Query Round, and all active tags which have received the first Query command can contend for slots in this frame. Note that, within each frame, tags may choose the same random number for the slot counter, which causes multiple tags to reply during a slot. Therefore within each frame there exist three kinds of slots: (1) the empty slot where no tags replies; (2) the single slot where only one tag replies; and (3) the collision slot where multiple tags reply. IV. PROBLEM FORMULATION Suppose a freight of containers is moving on a conveyor. The reader must read data from those tags inside the con￾tainers. Fig. 1 illustrates this scenario of reading moving tags. We suppose the conveyor has a constant moving speed v. The reader is fixed over the conveyor at a height of h, and it has an effective range of D on the horizon. The tag containers are placed along the conveyor with a distance of S ≥ D between each other. In this way, only one container is in the reading range of the reader at any time. Assume the number of tags in a container is N. As the time interval for one container to stay within the effective reading range is limited to D v , the RFID reader system needs to finish identifying all tags inside each container within this time interval. Note that due to random issues in the anti-collision scheme, e.g, the system may occasionally encounter much higher collisions than the expected situation, in realistic settings the reader can never guarantee to finish identifying all tags in time, whatever the speed of the conveyor is. Therefore the objective to design the RFID system is to make the expected duration for identifying all tags as short as possible, so that all tags can be identified in time with high possibility. Fig. 2 illustrates the intuition of this objective. In Fig. 2(a) we use Poisson distribution to depict the duration distribution to finish identifying all N tags. The horizontal axis k is the duration and the vertical axis is the probability. We show three distributions with various mean durations λ = 1, 4, 10. In Fig. 2(b) we depict the cor￾responding cumulative distribution functions. We observe that in order to finish identifying all tags within a fixed duration k, the scheme with the smallest mean duration λ = 1 always has the highest probability to achieve that, while the scheme with λ = 10 always has the lowest probability. Therefore, in order to ensure all tags can be identified in time with high possibility, a practical method is to make the expected duration to finish reading all tags as small as possible. Assume that the average durations for empty/single/collision slots are all nearly equal to Δt. Since the reader is responsible to set the frame size f for each Query Round, it needs to efficiently set a series of frame sizes f1, f2, ..., fm (0 <m< +∞) so that the expectation of m i=1 fi ·Δt is minimized. Since Δt is constant, this optimization problem is further reduced to minimizing the expectation of m i=1 fi, which is the total expected number of slots used to read all the tags. Fig. 1. Reading the moving tags on the conveyor. 0 5 10 15 20 0 0.1 0.2 0.3 0.4 k Probability lambda=1 lambda=4 lambda=10 0 5 10 15 20 0 0.2 0.4 0.6 0.8 1 k Probability lambda=1 lambda=4 lambda=10 (a) Probability mass function (b) Cumulative distributed function Fig. 2. An example to explain the intuition of the objective. While a container is moving within the reader’s range, its horizontal position is d (see Fig.1). For the ease of presenta￾tion, we respectively set the horizontal position at the entrance, the middle and the exit of the reader’s effective range as − D 2 , 0 and D 2 . Thus the distance between the tags in the container and the reader is r = √ d2 + h2. So when the container is moving on the conveyor, the propagation loss for both the forwarding channel and the reverse channel keeps changing as the distance r varies. Hence the probability varies for the tags to successfully receive and backscatter the signal to the reader, affecting the whole procedure for the tag inventory and access. In order to solve the aforementioned optimization problem, we need to investigate the probabilistic model for RFID tag identification. Thus in the next two sections, we first propose a probabilistic model for RFID tag identification, then we accordingly propose an efficient tag identification scheme for identifying moving tags. V. PROBABILISTIC MODEL FOR RFID TAG IDENTIFICATION A. Probabilistic parameters for propagation According to Section III-A, we know that the realistic propagation model is probabilistic, since the path loss and the 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.

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. backscatter efficiency are probabilistic.In order to depict the Theorem I:According to the probabilistic propagation RFID tag identification process under the probabilistic propa- model,the probability for a tag to successfully reply in the gation situation,assume that the distance between the reader frame with size f by monitoring the QueryRep messages is and the tag to be identified is r.We use pi(r)to denote the equal to pi(r),that is pe(f,r)=pi(r). probability for the tag to successfully receive the message from Proof:Since pa(t,x,r)denotes the probability for the the reader,and then use pt(r)to denote the probability for the tag to receive x OueryRep messages at the tth slot,and in reader to successfully receive the backscattered message from order to succeed to do it within the specified frame size f, the tag.Then by definition we have it should satisfy 1≤x≤t≤f.Therefore according to the definition for pe(f,r)in Eq.(4),pe(f,r)can be expressed in p(T)=Prob{P≥Ps} (2) the following equivalent form: p(r)=Prob{P4≥Prs P≥Pa} (3) p(f,r） B.Probabilistic model for tag identification According to Section III-B,considering one specified RFID Then,as we have tag,we can divide the tag inventory and access procedure into four phases:(1)Obtain frame size from the Query/QueryAdjust ∑pa(t,玉，r）=p(r)·∑Cgm(r)P-(1-p(r)-r message,(2)Monitor the QueryRep messages for selected slot, r=1 (3)Backscatter the RN/6 message,and(4)Backscatter the ID =P(T)·[P(r）+(1-P:(r)-1=P(r), message.Here we do not consider the optional Select message thus in the probabilistic model.In the following we respectively analyze the actual impact on the four phases due to the probabilistic propagation. p%f,r)=台 1)Obtain frame size from Query/QueryAdjust message: Assume before each Query Round,the number of tags left The theorem gets proved. unread is n.When the reader sends the Query/QueryAdjust The Ouery message actually acts as the role of the first message,the tag will detect and resolve this message with QueryRep message,especially when f =1 the unique Query probability pi(r).Thus n.pi(r)tags are able to select the message takes the role of the OueryRep message.Thus the slots inside the frame. first phase and the second phase are not independent to each 2)Monitor QueryRep messages for selected slot:For those other.However,as long as the frame size f is large enough, tags which have successfully selected the slot number ac- we can assume that the first phase and the second phase are cording to the frame size f,each tag counts down the slot independent to each other.In this situation,given the number counter slot according to the received QueryRep messages. of unread tags,n,the expected number of tags successfully Each OueryRep message is detected and resolved by the tag obtaining a slot inside the frame is with probability pi(r).When slot=0 the tag backscatters n'=n·p(r）·pg(f,r）=n·(p(r)2 the RN16 message to the reader.Due to the loss of QueryRep messages,the tag actually may have to wait for more slots Note that after successfully receiving the Ouery message after the exact slot it selects.In this situation suppose a tag tags randomly select the slots inside the frame with size f, has selected the zth slot(1x)slot is deferred to some extent over the original selected slot z.Since the original slot z is selected with uniform probability,then as pa(t,x,r）=(p(r)·C(p(r)F-1(1-p(r)-x indicated in Theorem I's proof,the probability for the tag ac- As t varies over the range [+oo,if tpa(t,z,r). slots,no,n1,ne,can be calculated as follows: t工 As each tag uniformly selects a slot from 1 to f,then the n0=f(1-)m, probability for it to successfully reply in the frame is n1=n'(1-3)-1 (5) ne f-no-n1. (4) We denote the above mentioned empty/single/collision 1 slot as original empty/single/collision slot,which means Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply

backscatter efficiency are probabilistic. In order to depict the RFID tag identification process under the probabilistic propa￾gation situation, assume that the distance between the reader and the tag to be identified is r. We use pi(r) to denote the probability for the tag to successfully receive the message from the reader, and then use pt(r) to denote the probability for the reader to successfully receive the backscattered message from the tag. Then by definition we have pi(r) = P rob{P2 ≥ Pts}, (2) pt(r) = P rob{P4 ≥ Prs|P2 ≥ Pts}. (3) B. Probabilistic model for tag identification According to Section III-B, considering one specified RFID tag, we can divide the tag inventory and access procedure into four phases:(1) Obtain frame size from the Query/QueryAdjust message, (2) Monitor the QueryRep messages for selected slot, (3) Backscatter the RN16 message, and (4) Backscatter the ID message. Here we do not consider the optional Select message in the probabilistic model. In the following we respectively analyze the actual impact on the four phases due to the probabilistic propagation. 1) Obtain frame size from Query/QueryAdjust message: Assume before each Query Round, the number of tags left unread is n. When the reader sends the Query/QueryAdjust message, the tag will detect and resolve this message with probability pi(r). Thus n · pi(r) tags are able to select the slots inside the frame. 2) Monitor QueryRep messages for selected slot: For those tags which have successfully selected the slot number ac￾cording to the frame size f, each tag counts down the slot counter slot according to the received QueryRep messages. Each QueryRep message is detected and resolved by the tag with probability pi(r). When slot = 0 the tag backscatters the RN16 message to the reader. Due to the loss of QueryRep messages, the tag actually may have to wait for more slots after the exact slot it selects. In this situation suppose a tag has selected the xth slot (1 ≤ x ≤ f) within the frame size f, the probability for it to detect x QueryRep messages at the actual tth (t ≥ x) slot is pα(t, x, r)=(pi(r)) · Cx−1 t−1 (pi(r))x−1(1 − pi(r))t−x. As t varies over the range [x, +∞], if t ≤ f, then the tag can reply inside the frame; otherwise, the tag cannot reply inside the frame. Therefore if a tag originally selects the xth slot, the probability for it to successfully reply in the frame is pβ(f, x, r) = f t=x pα(t, x, r). As each tag uniformly selects a slot from 1 to f, then the probability for it to successfully reply in the frame is pθ(f, r) = f x=1 1 f pβ(f, x, r) = 1 f f x=1 f t=x pα(t, x, r). (4) Theorem 1: According to the probabilistic propagation model, the probability for a tag to successfully reply in the frame with size f by monitoring the QueryRep messages is equal to pi(r), that is pθ(f, r) = pi(r). Proof: Since pα(t, x, r) denotes the probability for the tag to receive x QueryRep messages at the tth slot, and in order to succeed to do it within the specified frame size f, it should satisfy 1 ≤ x ≤ t ≤ f. Therefore according to the definition for pθ(f, r) in Eq. (4), pθ(f, r) can be expressed in the following equivalent form: pθ(f, r) = 1 f f t=1 t x=1 pα(t, x, r). Then, as we have t x=1 pα(t, x, r) = pi(r) · t x=1 Cx−1 t−1 (pi(r))x−1(1 − pi(r))t−x = pi(r) · [pi(r) + (1 − pi(r))]t−1 = pi(r), thus pθ(f, r) = 1 f f t=1 pi(r) = pi(r). The theorem gets proved. The Query message actually acts as the role of the first QueryRep message, especially when f = 1 the unique Query message takes the role of the QueryRep message. Thus the first phase and the second phase are not independent to each other. However, as long as the frame size f is large enough, we can assume that the first phase and the second phase are independent to each other. In this situation, given the number of unread tags, n, the expected number of tags successfully obtaining a slot inside the frame is n = n · pi(r) · pθ(f, r) = n · (pi(r))2. Note that after successfully receiving the Query message, tags randomly select the slots inside the frame with size f, using a uniform approach. Then due to the probabilistic loss of QueryRep messages, the actual slot t in which the tag replies is deferred to some extent over the original selected slot x. Since the original slot x is selected with uniform probability, then as indicated in Theorem 1’s proof, the probability for the tag ac￾tually replies in slot t is P(t) = t x=1 1 f · Pα(t, x, r) = pi(r) f . Since P(t) is the same for all slot t, it infers that the actual slot t in which the tag replies is uniformly distributed inside the frame. Therefore, if we do not consider the propagation loss for backscattering, then, according to the binomial distribution, the expected number of empty slots, single slots, and collision slots, n0, n1, nc, can be calculated as follows: ⎧ ⎪⎨ ⎪⎩ n0 = f · (1 − 1 f )n , n1 = n · (1 − 1 f )n −1, nc = f − n0 − n1. (5) We denote the above mentioned empty/single/collision slot as original empty/single/collision slot, which means 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.

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. no/one/multiple tag(s)select(s)this slot and is (are)ready to follows: backscatter the RN/6 message to the reader.Specifically,we n(n,r,f)=n0+1·(1-pt(r) define s-collision slot as the slot which is selected by s tags. +f·∑2P(s)pm(s,r, 3)Backscatter the RN16 message:If a tag has received (7) enough QueryRep messages for its selected slot,then it n(m,rf)=m1p(r)+f·∑2P(s)p2(s,r, backscatters the RN/6 message to the reader,and the reader n2(m,n,f)=f·∑2P(s)ps(s,r): is able to detect and resolve the backscattered message with 4)Backscatter the ID message:When a tag successfully probability p(r).According to the slotted Aloha protocol, transmits a RN16 message to the reader without collisions, due to the probabilistic loss of the RN/6 message,for some the reader will transmit a ACK message to the tag,and then original single slots it is possible for the reader unable to detect the tag will backscatter its ID message to the reader.The above the RN/6 messages,thus transferring those original single slots process is successfully completed with a probability of pi(r). into actual empty slots.For the original s-collision slots,s pt(r),otherwise the tag will keep active for the next round. tags try to send the RN/6 message simultaneously.Due to the Therefore the number of tags that successfully read within the probabilistic loss of the message,when all s messages are lost frame is n(n,T,f)·pi(r)·pt(r) with a probability of pi(s,r),it is possible that the reader is unable to detect any of the messages,thus transferring this C.Obtain the propagation and backscatter parameters slot into actual empty slot;similarly when s-1 messages In the above subsection,we have built a probabilistic model are lost with a probability of pa(s,r),it is possible for the for the RFID tag identification.Recall that we utilize two reader to detect only one of the messages,thus transferring parameters pi(r)and pt(r)to formalize the probabilistic this slot into actual single slot;otherwise,this slot remains model,thus obtaining these two important parameters is a as a collision slot with a probability of pa(s,r).The above prerequisite to the probabilistic model.However,it is rather probabilities,pi(s,r),p2(s,r),and pa(s,r),are calculated as difficult to directly compute these two parameters by using follows: realistic physical layer parameters obtained from sophisticated instruments [3].Here we claim that by using one reader and p1(s,r）=(1-p(r) one tag,it is enough to estimate pi(r)and pt(r)from the p2(s,r）=s·(1-p(r)-1·p(r following experiment results.We separate the reader and the (6) p3(s,T)=1-P1-P2 tag with a distance of r.First we set the frame size f to 1 =1-(1-p4(r)°-s·(1-p(r)s-1·p(r) for the reader,and let the reader issue m rounds to read the same tag and check the number of successful responses m. Suppose the actual numbers of empty slots,single slots and Thus we get the read ratio asr.Secondly we set collision slots are no,n,n.Fig.3 shows the translation the frame size f to a large enough value,say f=100,and relationship from original empty/singel/collision slots to actual also let the reader issue m2 rounds to read the same tag and empty/singel/collision slots. check the number of successful responses m2.Thus we get the read ratio as rtf(r)=m2. Translation Probability According to the probabilistic model,for the case when frame size f=1,the Ouery message is successfully detected Original Empty Slots 100% Actual Empty Slots and resolved by the tag with probability of pi(r),and the tag 1-pt successfully backscatters the RN/6 message with probability of pt(r).After that the reader successfully responds the ACK Original Single Slots -pt(r) Actual Single Slots message with probability of pi(r),and the tag successfully pi(s.r) backscatters the ID message with probability of pt(r).So P25,j rti(r)=(pi(r))2.(pt(r))2.For the case when frame size Original s-Collis on p3(s.r) Actual Collision Slot起 f is set to a large enough value,first the Query message is sots(5-1) successfully detected and resolved by the tag with probability of pi(r),then the tag monitors enough QueryRep messages Fig.3.Relationship for slot transformation for its selected slot with probability pe(f,r).It has been proved that pe(f,r)=pi(r).Then the tag successfully Suppose n'tags are able to successfully obtain a slot in the backscatters the RN/6 message with probability of pt(r).After frame of size f,then the proportion for the original s-collision that the reader successfully responds the ACK message with slots P(s)inside the frame is probability of pi(r),and the tag successfully backscatters the ID message with probability of p(r).Hence rtf(r)= (p((pa().Therefore we can derive that p(r P(s)=C· /(rt(1)3 and p(r).We can store the values of pa(r)and P(r)at various distance r.In our probabilistic model,for Thus given f,n'and pt(r),we can calculate no,n1,n as simplification of the problem we do not consider the impact Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply

no/one/multiple tag(s) select(s) this slot and is (are) ready to backscatter the RN16 message to the reader. Specifically, we define s-collision slot as the slot which is selected by s tags. 3) Backscatter the RN16 message: If a tag has received enough QueryRep messages for its selected slot, then it backscatters the RN16 message to the reader, and the reader is able to detect and resolve the backscattered message with probability pt(r). According to the slotted Aloha protocol, due to the probabilistic loss of the RN16 message, for some original single slots it is possible for the reader unable to detect the RN16 messages, thus transferring those original single slots into actual empty slots. For the original s-collision slots, s tags try to send the RN16 message simultaneously. Due to the probabilistic loss of the message, when all s messages are lost with a probability of p1(s, r), it is possible that the reader is unable to detect any of the messages, thus transferring this slot into actual empty slot; similarly when s − 1 messages are lost with a probability of p2(s, r), it is possible for the reader to detect only one of the messages, thus transferring this slot into actual single slot; otherwise, this slot remains as a collision slot with a probability of p3(s, r). The above probabilities, p1(s, r), p2(s, r), and p3(s, r), are calculated as follows: ⎧ ⎪⎪⎨ ⎪⎪⎩ p1(s, r) = (1 − pt(r))s p2(s, r) = s · (1 − pt(r))s−1 · pt(r) p3(s, r)=1 − p1 − p2 = 1 − (1 − pt(r))s − s · (1 − pt(r))s−1 · pt(r) (6) Suppose the actual numbers of empty slots, single slots and collision slots are n 0, n 1, n c. Fig. 3 shows the translation relationship from original empty/singel/collision slots to actual empty/singel/collision slots. Fig. 3. Relationship for slot transformation Suppose n tags are able to successfully obtain a slot in the frame of size f, then the proportion for the original s-collision slots P(s) inside the frame is P(s) = Cs n · ( 1 f ) s(1 − 1 f ) n −s. Thus given f,n and pt(r), we can calculate n 0, n 1, n c as follows: ⎧ ⎪⎪⎪⎨ ⎪⎪⎪⎩ n 0(n, r, f) = n0 + n1 · (1 − pt(r)) +f · n s=2 P(s) · p1(s, r), n 1(n, r, f) = n1 · pt(r) + f · n s=2 P(s) · p2(s, r), n c(n, r, f) = f · n s=2 P(s) · p3(s, r). (7) 4) Backscatter the ID message: When a tag successfully transmits a RN16 message to the reader without collisions, the reader will transmit a ACK message to the tag, and then the tag will backscatter its ID message to the reader. The above process is successfully completed with a probability of pi(r)· pt(r), otherwise the tag will keep active for the next round. Therefore the number of tags that successfully read within the frame is n 1(n, r, f) · pi(r) · pt(r). C. Obtain the propagation and backscatter parameters In the above subsection, we have built a probabilistic model for the RFID tag identification. Recall that we utilize two parameters pi(r) and pt(r) to formalize the probabilistic model, thus obtaining these two important parameters is a prerequisite to the probabilistic model. However, it is rather difficult to directly compute these two parameters by using realistic physical layer parameters obtained from sophisticated instruments [3]. Here we claim that by using one reader and one tag, it is enough to estimate pi(r) and pt(r) from the following experiment results. We separate the reader and the tag with a distance of r. First we set the frame size f to 1 for the reader, and let the reader issue m1 rounds to read the same tag and check the number of successful responses m 1. Thus we get the read ratio as rt1(r) = m 1 m1 . Secondly we set the frame size f to a large enough value, say f = 100, and also let the reader issue m2 rounds to read the same tag and check the number of successful responses m 2. Thus we get the read ratio as rtf (r) = m 2 m2 . According to the probabilistic model, for the case when frame size f = 1, the Query message is successfully detected and resolved by the tag with probability of pi(r), and the tag successfully backscatters the RN16 message with probability of pt(r). After that the reader successfully responds the ACK message with probability of pi(r), and the tag successfully backscatters the ID message with probability of pt(r). So rt1(r)=(pi(r))2 · (pt(r))2. For the case when frame size f is set to a large enough value, first the Query message is successfully detected and resolved by the tag with probability of pi(r), then the tag monitors enough QueryRep messages for its selected slot with probability pθ(f, r). It has been proved that pθ(f, r) = pi(r). Then the tag successfully backscatters the RN16 message with probability of pt(r). After that the reader successfully responds the ACK message with probability of pi(r), and the tag successfully backscatters the ID message with probability of pt(r). Hence rtf (r) = (pi(r))3 ·(pt(r))2. Therefore we can derive that pi(r) = rt(f) rt(1) and pt(r) = (rt(1))3 (rt(f))2 . We can store the values of pi(r) and pt(r) at various distance r. In our probabilistic model, for simplification of the problem we do not consider the impact 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.

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 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.

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]=mintono.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 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.

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 apply

Theorem 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.

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. 400 350 -Controlled conditio -Noisy condition 350 300 300 250 250 200 200 0.7 150 150 一DP -AD 100 0.6 050 1 2 3 00 20 304050 60 70 Distance The number of tags (a)Noisy conditions.(b)Controlled conditions. (a)pi(r)and pt(r) (b)Required number of slots for various strategies (c)Required number of slots for different propaga- to select frame sizes tion situations 90 250 80叶 Actual number of tags 025 70 -Estimated number of tags 02 60 0.15 50 150 40 30 % C=30 20 0.05 50 -C=50 10 0 10203040,50 607080 5 10 15 20 1.5 253 3.5 The number of tags Read rounds (d)Normalized throughput for various initial frame (e)Simulation results for tag size estimation. (f)Maximum number of tags which can be identi- sizes fied for various conveyor speeds. Fig.4.Simulation results exceeds nmaz(v),then conventionally the reader cannot finish [6]S.Lee,S.Joo,and C.Lee,"An enhanced dynamic framed slotted aloha identifying all the tags in time. algorithm for rfid tag identification,"in Proc.of MobiOuitous,2005. [7]J.Myung.W.Lee,and S.Jaideep."Adaptive binary splitting for efficient VIII.CONCLUSION rfid tag anti-collision,"IEEE Communications Letters,vol.10,no.3,pp 144-146.2006. In this paper we consider how to efficiently identify tags on [8]L.Pan and H.Wu,"Smart Trend-Traversal:A Low Delay and Energy the moving conveyor.Considering conditions like the path loss Tag Arbitration Protocol for Large RFID Systems,"in Proc.of INFO- and multi-path effect in realistic settings,we first propose a COM.mini-conference,2009. [9]F.Schoute,"Dynamic frame length aloha,"IEEE Transactions on probabilistic model for RFID tag identification.Based on this Communications,vol.31,no.4,pp.565-568,1983. model,we propose efficient solutions to identify moving RFID [10]C.Floerkemeier,"Bayesian transmission strategy for framed aloha based rfid protocols,"in Proc.of RFID,2007. tags,according to the fixed-path mobility on the conveyor. [11]H.Vogt."Efficient object identification with passive rfid tags,"in Proc. of Pervasive,2002. ACKNOWLEDGMENTS [12]M.Kodialam and T.Nandagopal,"Fast and reliable estimation schemes This project was supported in part by US National Science in rfid systems."in Proc.of MobiCom.2006. Foundation grants CNS-0721443,CNS-0831904,CAREER [13]C.Qian,H.-L.Ngan,and Y.Liu,"Cardinality estimation for large-scale rfid systems,"in Proc.of PerCom,2008. Award CNS-0747108,the China 973 project(2009CB320705. [14]B.Sheng.C.C.Tan,Q.Li,and W.Mao."Finding popular categoried 2006CB303000),the China NSF grant(60673154,60873026, for RFID tags,"in Proc.of ACM Mobihoc,2008. 90718031.60721002.60573106.60573132.60825205) [15]C.C.Tan,B.Sheng,and Q.Li,"How to monitor for missing RFID tags."in Proc.of IEEE ICDCS.2008. [16]Y.Kawakita and J.Mitsugi,"Anti-collision performance of gen2 air REFERENCES protocol in random error communication link,"in Proc.of SAINT-W. [1]Y.Maguire and R.Pappu,"An optimal g-algorithm for the iso 18000-6c 2006. rfid protocol,"IEEE Transactions on Automation Science and Engineer- [17]Z.Ren,C.C.Tan,D.Wang,and Q.Li,"Experimental study on mobile img,ol.6,n0.1,pp.16-24,2009. RFID performance,"in Proc.of WASA,2009. [2]B.Zhen,M.Kobayashi,and M.Shimuzu,"Framed aloha for multiple [18]S.R.Jeffery,M.Garofalakis,and M.J.Franklin."Adaptive cleaning rfid objects identification,"IEICE Transactions on Communications,vol. for rfid data streams,"in Proc.of VLDB,2006. E80-B,no.3,Pp.991-999,2005. [19]"Epcglobal.epc radio-frequency identity protocols class-1 generation-2 [3]M.Buettner and D.Wetherall,"An empirical study of uhf rfid perfor- uhf rfid protocol for communications at 860 mhz-960mhz version 1.2.0," mance,"in Proc.of MobiCom,2008. Tech.Rep.,2008. [4]K.M.Ramakrishnan and D.D.Deavours,"Performance benchmarks for [20]H.Lehpamer,RFID Design Principles.Artech House,Incorporate, passive uhf rfid tags,"in Proc.of the 13th Gl/ITG Conference on Mea- 2008. surement,Modeling,and Evaluation of Computer and Communication [21]W.Chen,"An accurate tag estimate method for improving the perfor- Sy3s1es,2006. mance of an rfid anticollision algorithm based on dynamic frame length [5]S.R.Aroor and D.D.Deavours,"Evaluation of the state of passive uhf aloha,"IEEE Transactions on Automation Science and Engineering, rfid:An experimental approach,"IEEE Systems Journal,vol.1,no.2. vol.6,no.1,Pp.9-15.2009. Pp.168-176,2007. Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply

0 1 2 3 4 5 6 0.5 0.6 0.7 0.8 0.9 1 Distance Propagation probability Controlled condition Noisy condition (a) pi(r) and pt(r) 10 20 30 40 50 60 70 0 50 100 150 200 250 300 350 400 The number of tags Required number of slots DP AD f=n f=32 (b) Required number of slots for various strategies to select frame sizes 1 2 0 50 100 150 200 250 300 350 (a)Noisy conditions.(b)Controlled conditions. Required number of slots (c) Required number of slots for different propaga￾tion situations 10 20 30 40 50 60 70 80 0 0.05 0.1 0.15 0.2 0.25 The number of tags Throughput C=10 C=30 C=50 (d) Normalized throughput for various initial frame sizes 5 10 15 20 0 10 20 30 40 50 60 70 80 90 Read rounds Number of tags Actual number of tags Estimated number of tags (e) Simulation results for tag size estimation. 1 1.5 2 2.5 3 3.5 4 0 50 100 150 200 250 Speed of the conveyor: v Maximum number of tags to be read (f) Maximum number of tags which can be identi- fied for various conveyor speeds. Fig. 4. Simulation results exceeds nmax(v), then conventionally the reader cannot finish identifying all the tags in time. VIII. CONCLUSION In this paper we consider how to efficiently identify tags on the moving conveyor. Considering conditions like the path loss and multi-path effect in realistic settings, we first propose a probabilistic model for RFID tag identification. Based on this model, we propose efficient solutions to identify moving RFID tags, according to the fixed-path mobility on the conveyor. ACKNOWLEDGMENTS This project was supported in part by US National Science Foundation grants CNS-0721443, CNS-0831904, CAREER Award CNS-0747108, the China 973 project (2009CB320705, 2006CB303000), the China NSF grant (60673154, 60873026, 90718031, 60721002, 60573106, 60573132, 60825205). REFERENCES [1] Y. Maguire and R. Pappu, “An optimal q-algorithm for the iso 18000-6c rfid protocol,” IEEE Transactions on Automation Science and Engineer￾ing, vol. 6, no. 1, pp. 16–24, 2009. [2] B. Zhen, M. Kobayashi, and M. Shimuzu, “Framed aloha for multiple rfid objects identification,” IEICE Transactions on Communications, vol. E80-B, no. 3, pp. 991–999, 2005. [3] M. Buettner and D. Wetherall, “An empirical study of uhf rfid perfor￾mance,” in Proc. of MobiCom, 2008. [4] K. M. Ramakrishnan and D. D. Deavours, “Performance benchmarks for passive uhf rfid tags,” in Proc. of the 13th GI/ITG Conference on Mea￾surement, Modeling, and Evaluation of Computer and Communication Systems, 2006. [5] S. R. Aroor and D. D. Deavours, “Evaluation of the state of passive uhf rfid: An experimental approach,” IEEE Systems Journal, vol. 1, no. 2, pp. 168–176, 2007. [6] S. Lee, S. Joo, and C. Lee, “An enhanced dynamic framed slotted aloha algorithm for rfid tag identification,” in Proc. of MobiQuitous, 2005. [7] J. Myung, W. Lee, and S. Jaideep, “Adaptive binary splitting for efficient rfid tag anti-collision,” IEEE Communications Letters, vol. 10, no. 3, pp. 144–146, 2006. [8] L. Pan and H. Wu, “Smart Trend-Traversal: A Low Delay and Energy Tag Arbitration Protocol for Large RFID Systems,” in Proc. of INFO￾COM, mini-conference, 2009. [9] F. Schoute, “Dynamic frame length aloha,” IEEE Transactions on Communications, vol. 31, no. 4, pp. 565–568, 1983. [10] C. Floerkemeier, “Bayesian transmission strategy for framed aloha based rfid protocols,” in Proc. of RFID, 2007. [11] H. Vogt, “Efficient object identification with passive rfid tags,” in Proc. of Pervasive, 2002. [12] M. Kodialam and T. Nandagopal, “Fast and reliable estimation schemes in rfid systems,” in Proc. of MobiCom, 2006. [13] C. Qian, H.-L. Ngan, and Y. Liu, “Cardinality estimation for large-scale rfid systems,” in Proc. of PerCom, 2008. [14] B. Sheng, C. C. Tan, Q. Li, and W. Mao, “Finding popular categoried for RFID tags,” in Proc. of ACM Mobihoc, 2008. [15] C. C. Tan, B. Sheng, and Q. Li, “How to monitor for missing RFID tags,” in Proc. of IEEE ICDCS, 2008. [16] Y. Kawakita and J. Mitsugi, “Anti-collision performance of gen2 air protocol in random error communication link,” in Proc. of SAINT-W, 2006. [17] Z. Ren, C. C. Tan, D. Wang, and Q. Li, “Experimental study on mobile RFID performance,” in Proc. of WASA, 2009. [18] S. R. Jeffery, M. Garofalakis, and M. J. Franklin, “Adaptive cleaning for rfid data streams,” in Proc. of VLDB, 2006. [19] “Epcglobal. epc radio-frequency identity protocols class-1 generation-2 uhf rfid protocol for communications at 860 mhz-960mhz version 1.2.0,” Tech. Rep., 2008. [20] H. Lehpamer, RFID Design Principles. Artech House, Incorporate, 2008. [21] W. Chen, “An accurate tag estimate method for improving the perfor￾mance of an rfid anticollision algorithm based on dynamic frame length aloha,” IEEE Transactions on Automation Science and Engineering, vol. 6, no. 1, pp. 9–15, 2009. 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