Mobile Netw Appl (2014)19:524-533 525 (a)Chemical Laboratory (b)Warehouse Management (c)Security Checking Fig.1 Rule-checking based applications matter whether the lighter exists.In regard to the tag identifi- research shows that,analog network coding can be used to cation protocol,traditional slotted ALOHA-based solutions extract useful information from collision slots to improve always try to reduce the collision slots,without sufficiently the RFID reading throughput [3].In the collision slot,the exploring the information from the collision slots.In this the signals from multiple tags exhibit small offsets,which paper,by effectively resolving the collision slots and lever- are sufficiently small for decoding the collision slot [4]. aging the rules'logical features for verification,we propose Besides,Manchester coding technology can be used in efficient rule checking protocols based on the categories of RFID communications to detect the bit collision [5,6].In tags,without the need of identifying tags one by one.While [7].Manchester coding is used to decode the tag identifier verifying all related rules in the applications,our protocols from the collision bits with the known mask.In [8],Manch- can dramatically reduce the overall execution time for rule ester coding is used to extract the information from collision checking. slots to enhance the efficiency of identifying the tags. We make the following contributions in this paper. Instead of identifying all the tags,missing tag identifica- We study a practically important problem of rule check- tion only aims to find the missing tags [9,10].Opposite to ing over a large set of RFID tags,which is essential for a the purpose of finding missing tags,Zheng et al.propose a number of RFID applications,such as safety inspection, two-phase approximation protocol for fast tag searching in large-scale RFID systems [11].Rather than identifying the warehouse management,and so on. We propose a time-efficient protocol for rule checking tags,the RFID cardinality estimation protocols count the number of distinct tags [12,13].However,all the literature based on collision detection,which aims at sufficiently exploring the information from the collision slots.Fur- does not research the problem of rule checking over RFID tags thermore,we propose an enhanced protocol which com- Being different from the related work,our research bines the collision detection and the logical features of focuses on efficiently checking the rules based on the tags the rules.By leveraging the rule's logical property,the enhanced protocol can effectively simplify the checking categories.We resolve the collision slots to verify the tags' categories specified by the rules and leverage the rules'log- process. ical features for rule checking.In order to resolve the colli- To the best of our knowledge.this is the first theoretical work to investigate the rule checking problem in RFID sion slots,we will use the bit collision detection technology systems.While leveraging the information of the physi- based on Manchester coding. cal layer and the application layer,our solution conducts a cross-layer optimization to effectively achieve time 3 Preliminary efficiency. 3.1 Frame slotted ALOHA protocol 2 Related works Frame slotted ALOHA protocol (FSA)is a popular anti- collision protocol for tag identification.In FSA,the reader Previous research on RFID has focused on anti-collision first broadcasts the request message and specifies the fol- protocols,which can be categorized into tree-based pro- lowing frame size f.After receiving f,each tag selects tocols [1]and ALOHA-based ones [2].In ALOHA-based h(ID)mod f as its slot number.Here,h is a hash function, protocols,most of the existing work considers the colli- ID is tag ID.If no tag responds in a slot (empty slot),the sion slots unuseful and wastes the collision slots.Recent reader closes the slot immediately.If only one tag replies in SpringerFig. 1 Rule-checking based applications matter whether the lighter exists. In regard to the tag identifi￾cation protocol, 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 lever￾aging the rules’ logical features for verification, we propose efficient rule checking protocols based on 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. – We study a practically important problem of rule check￾ing over a large set of RFID tags, which is essential for a number of RFID applications, such as safety inspection, warehouse management, and so on. – We propose a time-efficient protocol for rule checking based on collision detection, which aims at sufficiently exploring the information from the collision slots. Fur￾thermore, we propose an enhanced protocol which com￾bines the collision detection and the logical features of the rules. By leveraging the rule’s logical property, the enhanced protocol can effectively simplify the checking process. – To the best of our knowledge, this is the first theoretical work to investigate the rule checking problem in RFID systems. While leveraging the information of the physi￾cal layer and the application layer, our solution conducts a cross-layer optimization to effectively achieve time efficiency. 2 Related works Previous research on RFID has focused on anti-collision protocols, which can be categorized into tree-based pro￾tocols [1] and ALOHA-based ones [2]. In ALOHA-based protocols, most of the existing work considers the colli￾sion slots unuseful and wastes the collision slots. Recent research shows that, analog network coding can be used to extract useful information from collision slots to improve the RFID reading throughput [3]. In the collision slot, the the signals from multiple tags exhibit small offsets, which are sufficiently small for decoding the collision slot [4]. Besides, Manchester coding technology can be used in RFID communications to detect the bit collision [5, 6]. In [7], Manchester coding is used to decode the tag identifier from the collision bits with the known mask. In [8], Manch￾ester coding is used to extract the information from collision slots to enhance the efficiency of identifying the tags. Instead of identifying all the tags, missing tag identifica￾tion only aims to find the missing tags [9, 10]. Opposite to the purpose of finding missing tags, Zheng et al. propose a two-phase approximation protocol for fast tag searching in large-scale RFID systems [11]. Rather than identifying the tags, the RFID cardinality estimation protocols count the number of distinct tags [12, 13]. However, all the literature does not research the problem of rule checking over RFID tags. Being different from the related work, our research focuses on efficiently checking the rules based on the tags’ categories. We resolve the collision slots to verify the tags’ categories specified by the rules and leverage the rules’ log￾ical features for rule checking. In order to resolve the colli￾sion slots, we will use the bit collision detection technology based on Manchester coding. 3 Preliminary 3.1 Frame slotted ALOHA protocol Frame slotted ALOHA protocol (FSA) is a popular anti￾collision protocol for tag identification. In FSA, the reader first broadcasts the request message and specifies the fol￾lowing frame size f . After receiving f , each tag selects h(ID) mod f as its slot number. Here, h is a hash function, ID is tag ID. If no tag responds in a slot (empty slot), the reader closes the slot immediately. If only one tag replies in Mobile Netw Appl (2014) 19:524–533 525