Efficient Protocols for Rule Checking in RFID Systems Yafeng Yin,Lei Xie,Sanglu Lu,Daoxu Chen State Key Laboratory for Novel Software Technology,Nanjing University,China Email:yyf@dislab.nju.edu.cn,{Ixie,sanglu,cdx}@nju.edu.cn Abstract-With the rapid proliferation of RFID technologies, related to the tags'categories instead of the detail IDs,and RFID has been introduced to the applications like safety inspec- it is possible to quickly check the rules by exploring their tion and warehouse management.Conventionally a number of logical features.For example,if the alcohol is not detected in deployment rules are specified for these applications.This paper studies a practically important problem of rule checking over a the warehouse management,then the rule over the lighter and large set of RFID tags,i.e.,checking whether the specified rules the alcohol can be verified as satisfied immediately,no matter are satisfied according to the RFID tags within the monitoring whether the lighter exists.Besides,traditional slotted ALOHA- area.This rule checking function may need to be executed based solutions always try to reduce the collision slots,without frequently over a large number of tags and therefore should be made efficient in terms of execution time.Aiming to achieve sufficiently exploring the information from the collision slots. time efficiency,we propose two efficient protocols based on the In this paper,by effectively resolving the collision slots collision detection and the logical features of rules,respectively. and leveraging the rules'logical features for verification,we Simulation results indicate that our protocols achieve much better propose efficient rule checking protocols according to the performance than other solutions in terms of time efficiency. categories of tags,without the need of identifying tags one I.INTRODUCTION by one.While verifying all related rules in the applications, our protocols can dramatically reduce the overall execution With the rapid proliferation of RFID technologies,RFID time for rule checking. tags have been widely deployed into a variety of applications. We make the following contributions in this paper.(1)We In conventional applications,an RFID system typically con-study a practically important problem of rule checking over sists of one or several readers and a large number of tags. a large set of RFID tags,which is essential for a number Each tag is attached to a physical item and has a unique of RFID applications.(2)We propose an efficient protocol identification (ID)describing the item.The reader is used to for rule checking based on collision detection,which aims recognize the object by identifying its attached tag. at sufficiently exploring the information from the collision In recent years,RFID has been introduced to a number slots.Furthermore,we propose an enhanced protocol which of rule checking-based applications,e.g.,safety inspection leverages the rule's logical property to effectively simplify and warehouse management.In these applications,a set of the checking process.(3)To the best of our knowledge,this rules are specified over the deployment of the items (tags),is the first theoretical work to investigate the rule checking which vary from application to application.For example,in problem in RFID systems.While leveraging the physical and the warehouse management,the lighter and the alcohol should application layer's information,our solution conducts a cross- not be close to each other in consideration of safety,while the layer optimization to effectively achieve time efficiency. pillow core and pillowcase should be placed together,since II.RELATED WORK they are matching products.In order to verify the rules in a specified area,we can reasonably adjust the reader's power to Previous research on RFID has focused on anti-collision a certain level.The objective is to check whether the rules are protocols,which can be categorized into tree-based [1][2] satisfied according to the detected information from tags in the and ALOHA-based ones [3][4].Tree-based protocols resolve scanning area.The checking function may need to be executed collisions by muting subsets of tags involved in a collision. frequently over a large number of tags and therefore should ALOHA-based protocols assign distinct transmission time slot be made efficient in terms of execution time.For example,in to each tag,and sequentially identify the tags.Most of the the airport,the security checking is frequently executed and existing work considers the collision slots unuseful and wastes each passenger cannot stand too much time.A straightforward the collision slots.However,the collision slot can be used to solution is to collect all the tag IDs from the scanning area, improve the RFID reading performance.In [5],the analog and then check the rules one by one based on the collected network coding is used to extract useful information from IDs.However,this approach is rather time-consuming due to collision slots to improve the reading throughput.Besides, the large number of tags deployed in the applications. Manchester coding technology can be used in RFID commu- Based on the above understanding,it is essential to pro- nications to detect the bit collision [6][7].In [8],Manchester vide a time-efficient solution for these rule checking-based coding is used to decode the tag identifier from the collision applications.We note that conventionally the rules are only bits with the known mask.In [9][10].Manchester coding is 978-1-4673-5775-3/13/S31.00©2013IEEEEfficient Protocols for Rule Checking in RFID Systems Yafeng Yin, Lei Xie, Sanglu Lu, Daoxu Chen State Key Laboratory for Novel Software Technology, Nanjing University, China Email: yyf@dislab.nju.edu.cn, {lxie, sanglu, cdx}@nju.edu.cn Abstract—With the rapid proliferation of RFID technologies, RFID has been introduced to the applications like safety inspec￾tion and warehouse management. Conventionally a number of deployment rules are specified for these applications. This paper studies a practically important problem of rule checking over a large set of RFID tags, i.e., checking whether the specified rules are satisfied according to the RFID tags within the monitoring area. This rule checking function may need to be executed frequently over a large number of tags and therefore should be made efficient in terms of execution time. Aiming to achieve time efficiency, we propose two efficient protocols based on the collision detection and the logical features of rules, respectively. Simulation results indicate that our protocols achieve much better performance than other solutions in terms of time efficiency. I. INTRODUCTION With the rapid proliferation of RFID technologies, RFID tags have been widely deployed into a variety of applications. In conventional applications, an RFID system typically con￾sists of one or several readers and a large number of tags. Each tag is attached to a physical item and has a unique identification (ID) describing the item. The reader is used to recognize the object by identifying its attached tag. In recent years, RFID has been introduced to a number of rule checking-based applications, e.g., safety inspection and warehouse management. In these applications, a set of rules are specified over the deployment of the items (tags), which vary from application to application. For example, in the warehouse management, the lighter and the alcohol should not be close to each other in consideration of safety, while the pillow core and pillowcase should be placed together, since they are matching products. In order to verify the rules in a specified area, we can reasonably adjust the reader’s power to a certain level. The objective is to check whether the rules are satisfied according to the detected information from tags in the scanning area. The checking function may need to be executed frequently over a large number of tags and therefore should be made efficient in terms of execution time. For example, in the airport, the security checking is frequently executed and each passenger cannot stand too much time. A straightforward solution is to collect all the tag IDs from the scanning area, and then check the rules one by one based on the collected IDs. However, this approach is rather time-consuming due to the large number of tags deployed in the applications. Based on the above understanding, it is essential to pro￾vide a time-efficient solution for these rule checking-based applications. We note that conventionally the rules are only related to the tags’ categories instead of the detail IDs, and it is possible to quickly check the rules by exploring their logical features. For example, if the alcohol is not detected in the warehouse management, then the rule over the lighter and the alcohol can be verified as satisfied immediately, no matter whether the lighter exists. Besides, traditional slotted ALOHA￾based solutions always try to reduce the collision slots, without sufficiently exploring the information from the collision slots. In this paper, by effectively resolving the collision slots and leveraging the rules’ logical features for verification, we propose efficient rule checking protocols according to the categories of tags, without the need of identifying tags one by one. While verifying all related rules in the applications, our protocols can dramatically reduce the overall execution time for rule checking. We make the following contributions in this paper. (1) We study a practically important problem of rule checking over a large set of RFID tags, which is essential for a number of RFID applications. (2) We propose an efficient protocol for rule checking based on collision detection, which aims at sufficiently exploring the information from the collision slots. Furthermore, we propose an enhanced protocol which leverages the rule’s logical property to effectively simplify the checking process. (3) To the best of our knowledge, this is the first theoretical work to investigate the rule checking problem in RFID systems. While leveraging the physical and application layer’s information, our solution conducts a cross￾layer optimization to effectively achieve time efficiency. II. RELATED WORK Previous research on RFID has focused on anti-collision protocols, which can be categorized into tree-based [1][2] and ALOHA-based ones [3][4]. Tree-based protocols resolve collisions by muting subsets of tags involved in a collision. ALOHA-based protocols assign distinct transmission time slot to each tag, and sequentially identify the tags. Most of the existing work considers the collision slots unuseful and wastes the collision slots. However, the collision slot can be used to improve the RFID reading performance. In [5], the analog network coding is used to extract useful information from collision slots to improve the reading throughput. Besides, Manchester coding technology can be used in RFID commu￾nications to detect the bit collision [6][7]. In [8], Manchester coding is used to decode the tag identifier from the collision bits with the known mask. In [9][10], Manchester coding is 978-1-4673-5775-3/13/$31.00 ©2013 IEEE