are outside the scanning area,which are expressed as B(Ci)=obtains the related category IDs from the responses to check 0 and B(Ck)=0.Otherwise,B(Ri)is true (B(Ri)=1). the rules.In [11],a similar protocol CATS is proposed for 2)AND:All the categories must exist together.We rep- fast tag searching in large-scale RFID systems with multiple resent the rule as Ri CiA C&.The rule's Boolean value readers rather than a mobile reader used in our system. B(Ri)=1 only when both Ci and C&are in the scanning D.Analysis area,B(Ci)=1 and B(Ck)=1.Otherwise,B(Ri)=0. 3)EXCLUSIVE:The categories should not be put together. In the baseline protocols,ARCP collects the categories in We represent it as Ri=(CjA Ck).It is essentially the the reader's scanning area,which wastes time in collecting the same as the AND rule in consideration of logical relation. unrelated tag IDs.PRCP collects the categories in the rules, However,considering the actual situation in applications,we which wastes time in polling some nonexistent category IDs do not merge them.The rule's Boolean value B(Ri)=0 only specified by the rules.BRCP uses the Bloom filter to filter when B(Ci)=1 and B(Ck)=1.Otherwise,B(Ri)=1. unrelated categories,and gets the responses from tags like a However,if a rule is a hybrid rule,we can split it into virtual Bloom filter.However.the unit of the virtual Bloom subrules until each subrule belongs to one of the basic types. filter is a slot instead of a bit,which is rather time consuming, For example,a hybrid rule Ri=(CjA Ck)V(CuVC).We leading to the low efficiency of BRCP. get the subrules,CiA Ck.and Cu VCv.Then,B(Ri)can be VI.COLLISION DETECTION BASED RULE CHECKING obtained from B(CiA Ck)and B(Cu VC). PROTOCOL Due to the large number of tags and the large number A.Motivation of rules,traditional solutions are rather time consuming for Based on the above analysis,we propose a Collision de- collecting the tag IDs in the scanning area.Therefore,it tection based Rule Checking Protocol(CRCP).It focuses on is essential to propose a time-efficient solution for the rule resolving the collision slots based on Manchester code,which checking-based applications,which aims at minimizing the can be used for bit collision detection according to section III. execution time T for checking all the rules. In CRCP,if a categories [C1,C2,...,Ca}should select V.BASELINE PROTOCOLS the same slot to respond,the reader gets an a-collision slot. A.Frame Slotted ALOHA Based Rule Checking Protocol We use MM to represent the mixed signal of Mj. M;and M are Manchester code of d bits.M;is the short term The frame slotted ALOHA based Rule Checking Protocol of Ci to reduce transmission time.If a =2,M =100101, (ARCP)collects all the tag IDs in the scanning area and extracts the category IDs from them.In ARCP.the reader M=010111,henM=∑=14=100101+010111= first broadcasts a request message,which specifies the size of xx01x1.M is the expected code to be received by the reader. The reader decodes Mj from M by comparing the received the following frame.Then each tag individually and randomly selects one slot to transmit its ID.If only one tag replies in a code with the expected one.If the received code M is 010111, slot,the reader can successfully receive the tag ID.If multiple 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. tags respond simultaneously,a collision occurs,the involved tags will be acknowledged to restart in the next frame.The It indicates that C is outside the scanning area,while C2 is in the area.After that,the reader uses the decoded category similar process repeats until no tags respond in the frame.Then IDs to check the rules. the reader extracts the category IDs and checks the rules. B.Polling Based Rule Checking Protocol 101011011010101 We call the categories in the rules as related categories. The Polling based Rule Checking Protocol(PRCP)checks the Mobile existence of related categories in the scanning area.In PRCP, Reader .h.icJ. h.(cs) the reader broadcasts a category ID and waits for the response. Expected Code M 011110 null xoxoxx When a tag's category ID is equal to the reader's request one, Received Code M. 011110 null xOxxx the tag will give a short response.Then,the reader gets a M, 100101 101010 nonempty slot.Otherwise,the reader gets an empty slot.The M 001111 reader sends out all the related category IDs one by one to M detect the existence of these category IDs.When the polling Ms0111i0 =】 a=4 process terminates,the reader determines each rule's Boolean value based on the tags'responses. Fig.2.Collision detection based rule checking protocol C.Bloom Filter Based Rule Checking Protocol B.Protocol Overview Bloom filter based Rule Checking Protocol (BRCP)uses the In CRCP,the reader sends the request in the form of Bloom filter to inform the related categories to give responses. Bloom filter,as shown in Fig.2.It selects k hash functions Each one of the related tags in the scanning area uses k hash h1,h2,...,hk and c category IDs C1,C2,...,Ce to construct functions to select k slots to give a short response.Then the the Bloom filter with length l.It maps each C;into k bits reader gets the tags'responses as a virtual Bloom filter and at positions h(Ci)mod I,h2(Ci)mod l,...,hk(Ci)mod Iare outside the scanning area, which are expressed as B(Cj ) = 0 and B(Ck)=0. Otherwise, B(Ri) is true (B(Ri)=1). 2) 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. 3) 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 the large number of rules, traditional solutions are rather time consuming for collecting the tag IDs in the scanning area. Therefore, 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. V. BASELINE PROTOCOLS A. Frame Slotted ALOHA Based Rule Checking Protocol The frame slotted ALOHA based Rule Checking Protocol (ARCP) collects all the tag IDs in the scanning area and extracts the category IDs from them. In ARCP, the reader first broadcasts a request message, which specifies the size of the following frame. Then each tag individually and randomly selects one slot to transmit its ID. If only one tag replies in a slot, the reader can successfully receive the tag ID. If multiple tags respond simultaneously, a collision occurs, the involved tags will be acknowledged to restart in the next frame. The similar process repeats until no tags respond in the frame. Then the reader extracts the category IDs and checks the rules. B. Polling Based Rule Checking Protocol We call the categories in the rules as related categories. The Polling based Rule Checking Protocol (PRCP) checks the existence of related categories in the scanning area. In PRCP, the reader broadcasts a category ID and waits for the response. When a tag’s category ID is equal to the reader’s request one, the tag will give a short response. Then, the reader gets a nonempty slot. Otherwise, the reader gets an empty slot. The reader sends out all the related category IDs one by one to detect the existence of these category IDs. When the polling process terminates, the reader determines each rule’s Boolean value based on the tags’ responses. C. Bloom Filter Based Rule Checking Protocol Bloom filter based Rule Checking Protocol (BRCP) uses the Bloom filter to inform the related categories to give responses. Each one of the related tags in the scanning area uses k hash functions to select k slots to give a short response. Then the reader gets the tags’ responses as a virtual Bloom filter and obtains the related category IDs from the responses to check the rules. In [11], a similar protocol CATS is proposed for fast tag searching in large-scale RFID systems with multiple readers rather than a mobile reader used in our system. D. Analysis In the baseline protocols, ARCP collects the categories in the reader’s scanning area, which wastes time in collecting the unrelated tag IDs. PRCP collects the categories in the rules, which wastes time in polling some nonexistent category IDs specified by the rules. BRCP uses the Bloom filter to filter unrelated categories, and gets the responses from tags like a virtual Bloom filter. However, the unit of the virtual Bloom filter is a slot instead of a bit, which is rather time consuming, leading to the low efficiency of BRCP. VI. COLLISION DETECTION BASED RULE CHECKING PROTOCOL A. Motivation Based on the above analysis, we propose a Collision de￾tection 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 III. 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. 011110 null x0xxxx . . . 100101 101010 001111 D 1 hr(c1),hr(c2), hr(c3),hr(c4) 110011 Received Code Mr Expected Code M xxxxxx null D 4 011110 M1 M2 M3 M4 1 1 0 1 0 1 1 0 1 1 0 1 Bloom filter Mobile Reader 0 1 0 1 C1 C2 C3 C4 C5 C9 hr(c5) M5 011110 Fig. 2. Collision detection based rule checking protocol B. Protocol Overview In CRCP, the reader sends the request in the form of Bloom filter, as shown in Fig. 2. It selects k hash functions h1, h2,...,hk and c category IDs C1, C2,...,Cc to construct the Bloom filter with length l. It maps each Cj into k bits at positions h1(Cj ) mod l, h2(Cj ) mod l, ..., hk(Cj ) mod l