Mobile Netw Appl(2014)19:524-533 D0I10.1007/s11036-014-0524-9 Check out the Rules:Towards Time-Efficient Rule Checking over RFID Tags Yafeng Yin.Lei Xie.Sanglu Lu Daoxu Chen Published online:20 July 2014 Springer Science+Business Media New York 2014 Abstract With the rapid proliferation of RFID technolo-or several readers and a large number of tags.Each tag is gies,RFID has been introduced to the applications like attached to a physical item and has a unique identification safety inspection and warehouse management.Convention- (ID)describing the item.The reader recognizes the object ally a number of deployment rules are specified for these by identifying its attached tag. applications.This paper studies a practically important Recently,RFID has been introduced to a number of problem of rule checking over RFID tags,i.e.,checking rule checking-based applications,e.g.,safety inspection and whether the specified rules are satisfied according to the warehouse management.In these applications,a set of RFID tags within the monitoring area.This rule checking rules are specified over the deployment of the items(tags), function may need to be executed frequently over a large which vary from application to application.For example,in number of tags and therefore should be made efficient in the chemical laboratory,as shown in Fig.la,when some terms of execution time.Aiming to achieve time efficiency. chemicals (eg.metal material and corrosive solution)come we respectively propose two protocols,CRCP and ECRCP. together,the chemical reaction occurs,which may cause CRCP works based on collision detection.while ECRCP an accident.Therefore,these objects should not be placed combines the collision detection and the logical features together.In the warehouse management,the lighter and the of the rules.Simulation results indicate that our protocols alcohol should not be close to each other in consideration achieve much better performance than other solutions in of safety,while the pillow core and the pillowcase should terms of time efficiency. be placed together,since they are matching products,as shown in Fig.Ib.In order to check the rules over a spec- Keywords RFID.Rule checking.Algorithm design. ified area,the reader can reasonably adjust its power to a Time-efficient.Optimization certain level.The objective is to check whether the rules are satisfied according to the detected information from tags in the scanning area.The rule checking function may need 1 Introduction to be executed frequently over a large number of tags and therefore should be made efficient in terms of execution With the development of RFID technologies,RFID tags time.For example,the security checking in the airport,as have been widely deployed into a variety of applications. shown in Fig.1c.A straightforward solution is to collect Conventionally,an RFID system typically consists of one all the tag IDs,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 Y.Yin.L.Xie ()S.Lu.D.Chen State Key Laboratory for Novel Software Technology, applications. Nanjing University,Nanjing,China Based on the above understanding,it is essential to pro- e-mail:lxie@nju.edu.cn vide a time-efficient solution for these rule checking-based Y.Yin applications.We note that conventionally the rules are only e-mail:yyf@dislab.nju.edu.cn related to the tags'categories instead of the detail IDs,and S.Lu it is possible to quickly check the rules by exploring their e-mail:sanglu@nju.edu.cn logical features.For example,if the alcohol is not detected D.Chen in the warehouse management,then the rule over the lighter e-mail:cdx@nju.edu.cn and the alcohol can be verified as satisfied immediately,no ②SpringerDOI 10.1007/s11036-014-0524-9 Check out the Rules: Towards Time-Efficient Rule Checking over RFID Tags Yafeng Yin · Lei Xie · Sanglu Lu · Daoxu Chen © Springer Science+Business Media New York 2014 Abstract With the rapid proliferation of RFID technolo￾gies, RFID has been introduced to the applications like safety inspection and warehouse management. Convention￾ally a number of deployment rules are specified for these applications. This paper studies a practically important problem of rule checking over 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 respectively propose two protocols, CRCP and ECRCP. CRCP works based on collision detection, while ECRCP combines the collision detection and the logical features of the rules. Simulation results indicate that our protocols achieve much better performance than other solutions in terms of time efficiency. Keywords RFID · Rule checking · Algorithm design · Time-efficient · Optimization 1 Introduction With the development of RFID technologies, RFID tags have been widely deployed into a variety of applications. Conventionally, an RFID system typically consists of one Y. Yin · L. Xie () · S. Lu · D. Chen State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China e-mail: lxie@nju.edu.cn Y. Yin e-mail: yyf@dislab.nju.edu.cn S. Lu e-mail: sanglu@nju.edu.cn D. Chen e-mail: cdx@nju.edu.cn 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 recognizes the object by identifying its attached tag. Recently, 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 chemical laboratory, as shown in Fig. 1a, when some chemicals (eg. metal material and corrosive solution) come together, the chemical reaction occurs, which may cause an accident. Therefore, these objects should not be placed together. 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 the pillowcase should be placed together, since they are matching products, as shown in Fig. 1b. In order to check the rules over a spec￾ified area, the reader can reasonably adjust its 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 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. For example, the security checking in the airport, as shown in Fig. 1c. A straightforward solution is to collect all the tag IDs, 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 Published online: 20 July 2014 Mobile Netw Appl (2014) 19:524–533