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 11901H one uses k hash functions to select k slots to give a short M011110 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 Springerexpressed as B(Cj ) = 0 and B(Ck) = 0. Otherwise, B(Ri) is true (B(Ri) = 1). – AND: All the categories must exist together. We rep￾resent 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 essen￾tially the same as the AND rule in consideration of logical relation. However, considering the actual situa￾tion 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 checking￾based 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 cate￾gory 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 detec￾tion 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