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 ②Springer
DOI 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 technologies, RFID has been introduced to the applications like safety inspection 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 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 specified 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 timeconsuming due to the large number of tags deployed in the applications. Based on the above understanding, it is essential to provide 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
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 Springer
Fig. 1 Rule-checking based applications matter whether the lighter exists. In regard to the tag identification 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 leveraging 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 checking 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. Furthermore, we propose an enhanced protocol which combines 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 physical 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 protocols [1] and ALOHA-based ones [2]. In ALOHA-based protocols, most of the existing work considers the collision 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], Manchester 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 identification 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’ logical features for rule checking. In order to resolve the collision 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 anticollision protocol for tag identification. In FSA, the reader first broadcasts the request message and specifies the following 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
526 Mobile Netw Appl (2014)19:524-533 a slot(singleton slot),the reader successfully receives the Tag1: tag ID and sends an acknowledgement to the tag.The tag 10011111 will keep silent in the rest of the session.If multiple tags respond in the same slot (collision slot),a collision occurs, Tag2: and the involved tags will be acknowledged to restart in the 10111011 next frame.The reader repeats the above process until no tags respond. Data received by the Reade 3.2 Synchronization Fig.2 Bit collision detection in Manchester code As a popular ID-collection protocol conforming to EPC- C1G2 standard,FSA discards the collision slot.However. if the tags'responses are synchronized in a slot,we can to no transition in a received bit,such as bit3 and bit6.The resolve the collision slot to get the tags'responses.Further- corresponding bit is a collision bit.If there are more than more,if the bit-level synchronization is achieved,then each two tags responding simultaneously in a slot,only all the bit of the responses can be utilized to resolve the collision tags transmit '0'(or '1'),the reader can recover the bit'0' slot. In RFID systems,each tag communicates with the reader (or '1').Otherwise,the reader detects a collision bit x.We in a single hop way.The transmissions can be synchronized represent the conclusion as follows,0+...+0=0(all by the reader's signal [14].According to EPC-C1G2 stan- the tags send '0'),1 +...+11 (all the tags send '1'), dard [15],the tags responding in the same slot can be syn- 0+...+1 =x (some tags send '0'and some tags send '1'). In order to decode the bits in a slot,current experimental chronized through QueryRep or QueryAdjust.Besides,the effective scanning range in the passive RFID system is lim- platforms like USRP can be used [17],which can achieve ited(eg.5-6meters).The time delay difference between tags the bit-level identification (0,1,x). caused by the difference of their distances to the antenna is less thanx0.02us.When a tag receives the 4 Problem formulation reader's command,it will respond in a very short time. When the rate from a tag to the reader is 53Kb/s,it takes We assume that each tag has a category ID to denote the 18.88us for the tag to transmit one bit.The maximum time tag's category and the category ID is the prefix of tag delay difference is less than 0.02us,which can be neglected ID.In order to efficiently get the category IDs,we will compared to 18.88us.In regard to the physical-layer sig- utilize the collision slots based on Manchester coding.With- nals,the signals from multiple tags exhibit small offsets, out loss of generality,we assume that a feasible bit-level which are sufficiently small for decoding [4].Therefore,we synchronization can be achieved,which can be used to consider that the tags responding in the same slot are syn- recover the category IDs from the mixed signal in a slot. chronized.Moreover,the tags has the probability to achieve In our problem,we check the rules based on the tag's cat- bit-level synchronization,which is essential to recover the egory ID.We use R =(R1.....Ri.....Rm}to represent useful bits of the tags'responses from the mixed signal.As the rules.The category IDs in the rules are formulated as the tag's manufacturing technology is improved,we believe C=(C1.....Cj,..Cn).In real application,there often that a feasible bit-level synchronization can be achieved exist some constraint rules in the categories.For example, with more precise clock synchronization. orange juice and apple juice both belong to fruit juice,it may be enough to have any one of them in the warehouse.The 3.3 Manchester coding type of the relationship is called OR.While pillow core and pillowcase should be put together,their relationship's type In RFID systems,each tag encodes the backscattered data is called AND.The lighter and the alcohol should not be before sending it.In this paper,we use Manchester coding to close to each other for the sake of safety,their relationship's achieve bit collision detection.Manchester coding has been used in Type B of ISO 18000-6[16]. type is called EXCLUSIVE.Taking the actual situation into In Manchester code,a falling edge transition represents consideration,we classify the rules into three basic types. 1,a rising edge transition represents 0.The transitions can OR:At least one category must exist.We represent the be used to accurately detect the bit collision [5,6,8],as rule as Ri =CiVCk.We list two categories here.Actu- shown in Fig.2.When tagl and tag2 transmit IDs to the ally,there can be more categories in a rule.The rule's reader simultaneously in a slot,the falling edge transition Boolean value B(Ri)is false (B(R;)=0)only when and the rising edge transition cancel each other out,leading both C;and C&are outside the scanning area,which are ②Springer
a slot (singleton slot), the reader successfully receives the tag ID and sends an acknowledgement to the tag. The tag will keep silent in the rest of the session. If multiple tags respond in the same slot (collision slot), a collision occurs, and the involved tags will be acknowledged to restart in the next frame. The reader repeats the above process until no tags respond. 3.2 Synchronization As a popular ID-collection protocol conforming to EPCC1G2 standard, FSA discards the collision slot. However, if the tags’ responses are synchronized in a slot, we can resolve the collision slot to get the tags’ responses. Furthermore, if the bit-level synchronization is achieved, then each bit of the responses can be utilized to resolve the collision slot. In RFID systems, each tag communicates with the reader in a single hop way. The transmissions can be synchronized by the reader’s signal [14]. According to EPC-C1G2 standard [15], the tags responding in the same slot can be synchronized through QueryRep or QueryAdjust. Besides, the effective scanning range in the passive RFID system is limited (eg. 5-6 meters). The time delay difference between tags caused by the difference of their distances to the antenna is less than 6m 3×108m/s = 0.02μs. When a tag receives the reader’s command, it will respond in a very short time. When the rate from a tag to the reader is 53Kb/s, it takes 18.88μs for the tag to transmit one bit. The maximum time delay difference is less than 0.02μs, which can be neglected compared to 18.88μs. In regard to the physical-layer signals, the signals from multiple tags exhibit small offsets, which are sufficiently small for decoding [4]. Therefore, we consider that the tags responding in the same slot are synchronized. Moreover, the tags has the probability to achieve bit-level synchronization, which is essential to recover the useful bits of the tags’ responses from the mixed signal. As the tag’s manufacturing technology is improved, we believe that a feasible bit-level synchronization can be achieved with more precise clock synchronization. 3.3 Manchester coding In RFID systems, each tag encodes the backscattered data before sending it. In this paper, we use Manchester coding to achieve bit collision detection. Manchester coding has been used in Type B of ISO 18000-6 [16]. In Manchester code, a falling edge transition represents 1, a rising edge transition represents 0. The transitions can be used to accurately detect the bit collision [5, 6, 8], as shown in Fig. 2. When tag1 and tag2 transmit IDs to the reader simultaneously in a slot, the falling edge transition and the rising edge transition cancel each other out, leading Fig. 2 Bit collision detection in Manchester code to no transition in a received bit, such as bit3 and bit6. The corresponding bit is a collision bit. If there are more than two tags responding simultaneously in a slot, only all the tags transmit ‘0’ (or ‘1’), the reader can recover the bit ‘0’ (or ‘1’). Otherwise, the reader detects a collision bit x. We represent the conclusion as follows, 0 + ... + 0 = 0 (all the tags send ‘0’), 1 + ... + 1 = 1 (all the tags send ‘1’), 0 + ... + 1 = x (some tags send ‘0’ and some tags send ‘1’). In order to decode the bits in a slot, current experimental platforms like USRP can be used [17], which can achieve the bit-level identification (0, 1, x). 4 Problem formulation We assume that each tag has a category ID to denote the tag’s category and the category ID is the prefix of tag ID. In order to efficiently get the category IDs, we will utilize the collision slots based on Manchester coding. Without loss of generality, we assume that a feasible bit-level synchronization can be achieved, which can be used to recover the category IDs from the mixed signal in a slot. In our problem, we check the rules based on the tag’s category ID. We use R = {R1, ..., Ri, ..., Rm} to represent the rules. The category IDs in the rules are formulated as C = {C1, ..., Cj , ..., Cn}. In real application, there often exist some constraint rules in the categories. For example, orange juice and apple juice both belong to fruit juice, it may be enough to have any one of them in the warehouse. The type of the relationship is called OR. While pillow core and pillowcase should be put together, their relationship’s type is called AND. The lighter and the alcohol should not be close to each other for the sake of safety, their relationship’s type is called EXCLUSIVE. Taking the actual situation into consideration, we classify the rules into three basic types. – OR: At least one category must exist. We represent the rule as Ri = Cj ∨Ck . We list two categories here. Actually, there can be more categories in a rule. The rule’s Boolean value B(Ri) is false (B(Ri) = 0) only when both Cj and Ck are outside the scanning area, which are 526 Mobile Netw Appl (2014) 19:524–533
Mobile Netw Appl (2014)19:524-533 527 expressed as B(Cj)=0 and B(Ck)=0.Otherwise, Bloom filter to check the rules.In [111,a similar protocol B(Ri)is true (B(Ri)=1). CATS is proposed for fast tag searching in large-scale RFID AND:All the categories must exist together.We rep- systems. resent the rule as Ri=CiA C&.The rule's Boolean value B(Ri)=1 only when both Ci and C&are in the scanning area,B(Ci)=1 and B(Ck)=1.Otherwise, 6 Collision detection based rule checking protocol B(R)=0. EXCLUSIVE:The categories should not be put together. 6.1 Motivation We represent it as Ri =(CjA Ck).It is essen- tially the same as the AND rule in consideration of Based on the above analysis,we propose a Collision detec- logical relation.However,considering the actual situa- tion based Rule Checking Protocol (CRCP).It focuses on tion in applications,we do not merge them.The rule's resolving the collision slots based on Manchester code, Boolean value B(Ri)=0 only when B(Cj)=1 and which can be used for bit collision detection according to B(Ck)=1.Otherwise,B(Ri)=1. Section 3. In CRCP,if a categories (C1,C2....,Ca}should select However,if a rule is a hybrid rule,we can split it into the same slot to respond,the reader gets an a-collision subrules until each subrule belongs to one of the basic types. slot.We use M=Mj to represent the mixed signal For example,a hybrid rule Ri=(CiA Ck)V(Cu VCu).We of Mj.Mi and M are Manchester code of d bits.Mi is get the subrules,CjA Cx and Cu VCv.Then,B(Ri)can be the short term of Ci to reduce transmission time.If a=2. obtained from B(CjA Ck)and B(Cu VC). M1=100101,M2=01011L,then M=∑=1M)= Due to the large number of tags and rules,it is essential 100101 +010111 xx01x1.M is the expected code to to propose a time-efficient solution for the rule checking- be received by the reader.The reader decodes M;from M based applications,which aims at minimizing the execution by comparing the received code with the expected one.If time T for checking all the rules. the received code M,is 010111,the reader can confirm that only C2 gives the response M2.Because the first bit in M is x.while the first bit in M,is 0.It indicates that CI is outside 5 Baseline protocols the scanning area,while C2 is in the area.After that,the reader uses the decoded category IDs to check the rules. 5.1 Frame slotted ALOHA based rule checking protocol (ARCP) 6.2 Protocol overview ARCP collects all the tag IDs in the scanning area,as In CRCP,the reader sends the request by Bloom filter.It described in Section 3.1.Then the reader extracts the cate- selects k hash functions h1,h2,...,hk and c category IDs gory IDs in the scanning area and checks the rules. C1,C2....,Ce to construct the Bloom filter with length 1, as shown in Fig.3.It maps each Ci into k bits at positions 5.2 Polling based rule checking protocol(PRCP) h(Cj)mod I,h2(Ci)mod 1,....hk(Ci)mod I and sets these bits to 1.When a tag receives the request,it checks We call the categories in the rules as related categories. the corresponding k bits.Only all the bits are 1,it gives PRCP checks the existence of related category IDs in the response.See Fig.3 for an example of k =3,I 16, scanning area by broadcasting them one by one.When a tag's category ID is equal to the reader's request one,it 92 will give a short response.The reader gets a nonempty slot. 1101o11o11o1oo3 Otherwise,it gets an empty slot.When the polling process terminates,the reader checks the rules based on the tags Mobile Reader responses. hdc:) h.(cal.h(ca Expected Code M 011110 null XxXXXX 5.3 Bloom filter based rule checking protocol(BRCP) Received Code M. 011110null x0xxxx M 100101 BRCP uses the Bloom filter to inform the related categories Mz 101010 M 001111 to respond.For the related tags in the scanning area,each Ma one uses k hash functions to select k slots to give a short M5011110 response.The reader gets the responses as a virtual Bloom a=1 a=4 filter and obtains the wanted category IDs from the virtual Fig.3 Collision detection based rule checking protocol Springer
expressed as B(Cj ) = 0 and B(Ck) = 0. Otherwise, B(Ri) is true (B(Ri) = 1). – AND: All the categories must exist together. We represent the rule as Ri = Cj ∧ Ck. The rule’s Boolean value B(Ri) = 1 only when both Cj and Ck are in the scanning area, B(Cj ) = 1 and B(Ck ) = 1. Otherwise, B(Ri) = 0. – EXCLUSIVE: The categories should not be put together. We represent it as Ri = ¬(Cj ∧ Ck). It is essentially the same as the AND rule in consideration of logical relation. However, considering the actual situation in applications, we do not merge them. The rule’s Boolean value B(Ri) = 0 only when B(Cj ) = 1 and B(Ck ) = 1. Otherwise, B(Ri) = 1. However, if a rule is a hybrid rule, we can split it into subrules until each subrule belongs to one of the basic types. For example, a hybrid rule Ri = (Cj ∧Ck)∨(Cu ∨Cv). We get the subrules, Cj ∧ Ck and Cu ∨ Cv. Then, B(Ri) can be obtained from B(Cj ∧ Ck ) and B(Cu ∨ Cv). Due to the large number of tags and rules, it is essential to propose a time-efficient solution for the rule checkingbased applications, which aims at minimizing the execution time T for checking all the rules. 5 Baseline protocols 5.1 Frame slotted ALOHA based rule checking protocol (ARCP) ARCP collects all the tag IDs in the scanning area , as described in Section 3.1. Then the reader extracts the category IDs in the scanning area and checks the rules. 5.2 Polling based rule checking protocol (PRCP) We call the categories in the rules as related categories. PRCP checks the existence of related category IDs in the scanning area by broadcasting them one by one. When a tag’s category ID is equal to the reader’s request one, it will give a short response. The reader gets a nonempty slot. Otherwise, it gets an empty slot. When the polling process terminates, the reader checks the rules based on the tags’ responses. 5.3 Bloom filter based rule checking protocol (BRCP) BRCP uses the Bloom filter to inform the related categories to respond. For the related tags in the scanning area, each one uses k hash functions to select k slots to give a short response. The reader gets the responses as a virtual Bloom filter and obtains the wanted category IDs from the virtual Bloom filter to check the rules. In [11], a similar protocol CATS is proposed for fast tag searching in large-scale RFID systems. 6 Collision detection based rule checking protocol 6.1 Motivation Based on the above analysis, we propose a Collision detection based Rule Checking Protocol (CRCP). It focuses on resolving the collision slots based on Manchester code, which can be used for bit collision detection according to Section 3. In CRCP, if α categories {C1, C2,...,Cα} should select the same slot to respond, the reader gets an α – collision slot. We use M = α j=1 Mj to represent the mixed signal of Mj . Mj and M are Manchester code of d bits. Mj is the short term of Cj to reduce transmission time. If α = 2, M1 = 100101, M2 = 010111, then M = 2 j=1 Mj = 100101 + 010111 = xx01x1. M is the expected code to be received by the reader. The reader decodes Mj from M by comparing the received code with the expected one. If the received code Mr is 010111, the reader can confirm that only C2 gives the response M2. Because the first bit in M is x, while the first bit in Mr is 0. It indicates that C1 is outside the scanning area, while C2 is in the area. After that, the reader uses the decoded category IDs to check the rules. 6.2 Protocol overview In CRCP, the reader sends the request by Bloom filter. It selects k hash functions h1, h2,...,hk and c category IDs C1, C2,...,Cc to construct the Bloom filter with length l, as shown in Fig. 3. It maps each Cj into k bits at positions h1(Cj ) mod l, h2(Cj ) mod l, ..., hk (Cj ) mod l and sets these bits to 1. When a tag receives the request, it checks the corresponding k bits. Only all the bits are 1, it gives response. See Fig. 3 for an example of k = 3, l = 16, Fig. 3 Collision detection based rule checking protocol Mobile Netw Appl (2014) 19:524–533 527
528 Mobile Netw Appl (2014)19:524-533 the reader uses hi(Cj)mod 16 (i [1,3],j [1,5])to Algorithm 1 CRCP:Reader Side construct the Bloom filter.The tags in C1,C2,C3,C4.Cs Input:m rules {R1,R2,...,Rm,n related category pass the test and give responses,while the tags in C9 keep IDs C1,C2,...,Cn,frame size f silent.If a tag in Ci should give response in the following 2=0,9=0. while any related category is not verified do frame with size f,it uses a hash function h to select a slot Set g=0,and set c equal to the number of h(Ci)mod f.Then,it sends d bits Manchester code Mj. unverified related category IDs. Send the request Bloom filter. Here,Mi=h(Ci)mod (2d),h is a hash function. In a new frame,wait for the tags'responses. Because the reader knows the related categories and the for each slot iE [1,f]and g<c do if Manchester code cannot be recovered then hash functions,it can get the mapping relation of Cj and L Put these category IDs into set Mi.When getting the responses,the reader checks whether else each bit in the slot can be recovered from the mixed sig- Decode the a-collision slot. Get di new verified categories,g=g+qi. nal.If the bits cannot be recovered.it means the number of 22+日. tags responding in the slot is too large.Then the reader puts if Cardinality of C=n-z then the corresponding category IDs into the new set C',which L Verify the tags in C using probability pr. will be verified later.If the bits can be recovered success- Check the rules according to the verified categories Output:Checking result B(R1),B(R2),...,B(Rm ) fully,then the reader resolves the collision slots,as shown in Algorithm 1.In the frame received from tags,suppose that the reader is able to get qi new category IDs Ci.Cj,....Ck bit M(i)=x,while the received bit Mr(i)=0,then by decoding an a-collision slot.The reader decodes the the category Cj with the corresponding bit equivalent to collision slots one by one until it gets all the c related cate- 1 is outside the scanning area,B(Ci)=0.Besides,if gory IDs in the frame or the frame terminates.Then,it no =1,the category Ci with corresponding bit equivalent repeats the similar process.At last,the reader verify the to 0 must in the scanning area,B(Cj)=1.If M(i)=x category IDs in C'using probability pr.The reader broad- and Mr(i)=1,we can get the conclusion in the same way. casts an integer y [pr x Y1,Y is a large constant.Then the tag calculates the hash result hr(ID)mod Y,only if However,if the expected bit M(i)=1 and the received bit Mr(i)=x,then the category Cj with cor- hr(ID)mod Yy,the tag gives response.In this way, responding bit equivalent to 0 gives response,B(Ci)=1. there will be only a few number of tags (eg.1)in one cate- gory giving responses.Then,the reader can decode the If M(i)=x=1+0 and M,(i)=x.we can get category IDs.When all the related category IDs are verified, the reader will check the rules based on Section 4. Algorithm 2 Resolving an a-collision slot 6.3 Resolving the collision slot Input:d bits expected Manchester code M composed of {M,M2,...,Ma,corresponding category IDs (C1,Ca,..C),received Manchester According to Algorithm 1,the critical problem of CRCP code Mr,Boolean values of fC,}are stored in B(C)} is how to resolve the collision slots efficiently.In fact, Initialization:B(C)=-l,j∈[1，a] decoding Mj from M is like to solve the system of linear if M,null then BC1)=0,B(C2)=0.,,,B(Ca)=0 equations.In an a-collision slot,o represents the number Return. of variables in an equation,while the length of Manchester if a=I then B(C)=1 code d represents the number of equations.In order to LReturn. simplify the procedure of resolving the collision slot,we while i 1,d do compare each bit in the expected code M with the corre- |M()=∑°10+∑11,0+1=a Use the known set {B(C;)=0}to update sponding bit in received code M,to decode Mi,as shown M(),o,n1,. if M(i)=x and Mr(i)=0 then in Algorithm 2. for each Mj(i)=1 do B(Cj)=0. In Algorithm 2,null means an empty slot.M(i) if no 1 then for each Mi(i)=0 do B(C;)=1. means the ith bit in the Manchester code M.M(i)and Mi(i),M2(i).....Ma(i)are defined in the same way. if M(i)=x and M,(i)=1 then for each M (i)=0 do B(C)=0. Based on the description in Section 3,M(i)equals 0,1 or x. if n=1 then It is produced as follows,M(i)=1.no and L for each Mj(i)=1 do B(C;)=1. nI respectively represent the number of Mj(i)(j[1,a]) if M(i)=x and M(i)=x then if no =1 then equivalent to 0 and 1 in the slot.Before the reader decodes Lfor each M;(i)=0 do B(C;)=1. the category IDs in the ith bit,it will use the known set if n=1 then [B(Ci)}to update M(i).If B(Ci)=0,the reader removes for each Mi(i)=1 do B(Ci)=1. Mj from M and updates M(i),no,n1.a.If the expected Output:Verified category IDs.(Ci B(Ci)-1.) ②Springer
the reader uses hi(Cj ) mod 16 (i ∈ [1, 3], j ∈ [1, 5]) to construct the Bloom filter. The tags in C1, C2, C3, C4, C5 pass the test and give responses, while the tags in C9 keep silent. If a tag in Cj should give response in the following frame with size f , it uses a hash function hr to select a slot hr(Cj ) mod f . Then, it sends d bits Manchester code Mj . Here, Mj = h(Cj ) mod (2d ), h is a hash function. Because the reader knows the related categories and the hash functions, it can get the mapping relation of Cj and Mj . When getting the responses, the reader checks whether each bit in the slot can be recovered from the mixed signal. If the bits cannot be recovered, it means the number of tags responding in the slot is too large. Then the reader puts the corresponding category IDs into the new set C , which will be verified later. If the bits can be recovered successfully, then the reader resolves the collision slots, as shown in Algorithm 1. In the frame received from tags, suppose that the reader is able to get qi new category IDs Ci, Cj ,...,Ck by decoding an α – collision slot. The reader decodes the collision slots one by one until it gets all the c related category IDs in the frame or the frame terminates. Then, it repeats the similar process. At last, the reader verify the category IDs in C using probability pr. The reader broadcasts an integer y = pr × Y, Y is a large constant. Then the tag calculates the hash result hr(ID) mod Y, only if hr(ID) mod Y ≤ y, the tag gives response. In this way, there will be only a few number of tags (eg. 1) in one category giving responses. Then, the reader can decode the category IDs. When all the related category IDs are verified, the reader will check the rules based on Section 4. 6.3 Resolving the collision slot According to Algorithm 1, the critical problem of CRCP is how to resolve the collision slots efficiently. In fact, decoding Mj from M is like to solve the system of linear equations. In an α – collision slot, α represents the number of variables in an equation, while the length of Manchester code d represents the number of equations. In order to simplify the procedure of resolving the collision slot, we compare each bit in the expected code M with the corresponding bit in received code Mr to decode Mj , as shown in Algorithm 2. In Algorithm 2, null means an empty slot. M(i) means the ith bit in the Manchester code M. Mr(i) and M1(i), M2(i), . . ., Mα(i) are defined in the same way. Based on the description in Section 3, M(i) equals 0 ,1 or x. It is produced as follows, M(i) = n0 j=0 0+n1 j=1 1. n0 and n1 respectively represent the number of Mj (i) (j ∈ [1, α]) equivalent to 0 and 1 in the slot. Before the reader decodes the category IDs in the ith bit, it will use the known set {B(Cj )} to update M(i). If B(Cj ) = 0, the reader removes Mj from M and updates M(i), n0, n1, α. If the expected Algorithm 1 CRCP: Reader Side bit M(i) = x, while the received bit Mr(i) = 0, then the category Cj with the corresponding bit equivalent to 1 is outside the scanning area, B(Cj ) = 0. Besides, if n0 = 1, the category Cj with corresponding bit equivalent to 0 must in the scanning area, B(Cj ) = 1. If M(i) = x and Mr(i) = 1, we can get the conclusion in the same way. However, if the expected bit M(i) = x = 0 + α−1 j=1 1 and the received bit Mr(i) = x, then the category Cj with corresponding bit equivalent to 0 gives response, B(Cj ) = 1. If M(i) = x = 1 + α−1 j=1 0 and Mr(i) = x, we can get Algorithm 2 Resolving an α – collision slot 528 Mobile Netw Appl (2014) 19:524–533