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