Mobile Netw Appl (2014)19:524-533 529 Table 1 An example for resolving a collision slot with Step 1 2 3 4 =4 Expected Mi set M1,M2,M3,M4 M1,M2,M3,M4 M1,M2,M3 M1,M2,M3 Expected code XXXXXX XXXXXX XX飞XXX XXXXXX Received code xOxxxx xOxxxx xOxxxx xOxxxx M 100101 100101 100101/ 100101 M2 101010 101010 101010 101010W M3 001111/ 001111 001111 001111 Ma 10011 1卫0011× B(Cj) B(C3)=1 B(C4)=0 B(C1)=1 B(C2)=1 the conclusion in the same way.The reader repeats the sim- feature.In this section,we propose an Enhanced Collision ilar process until it decodes all the a category IDs or it has detection based Rule Checking Protocol(ECRCP)in con- repeated d times. sideration of the rule's logical property.In fact,in the OR We give an example in Table 1,the expected Manchester rule,if any category exists,the rule's Boolean value is true. code M is composed of [M1,M2,M3,M4),the received In the AND rule,if any category is out of the scanning code Mr xOxxxx.M xxxxxx,M(1)=x =0+ area,the rule's Boolean value is false.In the EXCLUSIVE ∑=ll,only Ma(l)=0.Besides,.M)=M,(①)=x.r rule,if any category is out of the scanning area,the rule's indicates M3 must give the response.Therefore,B(C3)=1. Boolean value is true.In regard to a hybrid rule,it can be We can get B(C4)=0 in the same way.Then,the reader determined by its subrule's Boolean value in a similar way. removes C4 and updates the third bit in M.M(3)=0+1+ Therefore,when the reader gets a part of the category IDs,it 1 =x,no 1,n1 2,M is composed of (M1,M2,M3), can check the correlated rules.Then it only needs to check a=3.It repeats the similar process and gets B(C1)=1, the remaining categories in the unverified rules. B(C2)=1. 7.2 Protocol description 6.4 Performance analysis 7.2.I Estimating the tag size In CRCP,the reader uses k hash functions and c category IDs to construct the Bloom filter with length 1.If we require In CRCP,the reader sends the request message to tags that the false positive probability is less than e,we get the based on Bloom filter,while ignoring the effect of tag size. optimal value of as / -In(e).c ln(2)-ln(2) When the tag size in the scanning area is much smaller In each a-collision slot,the tag gives responses with d than the number of related categories,CRCP is rather time- bits.We use and pa represent the average value of a and consuming.Thus ECRCP uses the average run based tag pd,respectively.to denotes the waiting time between any estimation (ART)scheme [13]to estimate the tag size.If the two consecutive transmissions,and tbit denotes the time for ratio p of tag size to the number of related categories is less atag totransmitone bit.Withoutloss ofgenerality,weset to= than the threshold p*,the reader will use APCR to check 302us,tbir =18.88us,pe=.Besides,should be a small the rules.Otherwise,the reader uses the Bloom filter to number(such as 2,3,or 4)[3],considering the actual situ- inform the related categories to give responses and verifies ation.Therefore,a is limited to [1,4].We get the optimal the categories,as described in the following subsections. value of a is a*=4,the corresponding optimal value of d is d*=7.We set aa*,dd*,the frame size f== 7.2.2 Finding the popular category More detail information of performance analysis can be found in the conference version of this paper [18]. Based on Section 4,a related category may exist in serval rules.We use frequency fi to describe the number of times that Cj appears in different rules.If Cj appears in a differ- 7 Enhanced collision detection based rule checking ent rule,fj only adds one to its original value,no matter protocol how many times Ci appears in this rule.For example,in the rule Ri =(CiACk)V(Cj vCu),fj,fk,fu respectively add 7.1 Motivation one.Obviously,fi [1,m],m is the number of rules.If a category Ci has a larger value of fi,it means that the cate- CRCP mainly focuses on verifying all the related category gory affects more rules'Boolean values.ECRCP first finds IDs in the scanning area while ignoring the rule's logical the unverified popular category ID with the largest value SpringerTable 1 An example for resolving a collision slot with α = 4 Step 1 2 3 4 Expected Mj set M1,M2, M3,M4 M1,M2, M3,M4 M1,M2, M3 M1,M2, M3 Expected code xxxxxx xxxxxx xxxxxx xxxxxx Received code x0xxxx x0xxxx x0xxxx x0xxxx M1 100101 100101 100101 √ 100101 M2 101010 101010 101010 101010 √ M3 001111 √ 001111 001111 001111 M4 110011 110011 × B(Cj ) B(C3) = 1 B(C4) = 0 B(C1) = 1 B(C2) = 1 the conclusion in the same way. The reader repeats the sim￾ilar process until it decodes all the α category IDs or it has repeated d times. We give an example in Table 1, the expected Manchester code M is composed of {M1, M2, M3, M4}, the received code Mr = x0xxxx. M = xxxxxx, M(1) = x = 0 + 3 j=1 1, only M3(1) = 0. Besides, M(1) = Mr(1) = x. It indicates M3 must give the response. Therefore, B(C3) = 1. We can get B(C4) = 0 in the same way. Then, the reader removes C4 and updates the third bit in M. M(3) = 0 + 1 + 1 = x, n0 = 1, n1 = 2, M is composed of {M1, M2, M3}, α = 3. It repeats the similar process and gets B(C1) = 1, B(C2) = 1. 6.4 Performance analysis In CRCP, the reader uses k hash functions and c category IDs to construct the Bloom filter with length l. If we require that the false positive probability is less than , we get the optimal value of l as l = −ln()·c ln(2)·ln(2)  . In each α − collision slot, the tag gives responses with d bits. We use α¯ and p¯d represent the average value of α and pd , respectively. τ0 denotes the waiting time between any two consecutive transmissions, and τbit denotes the time for atagtotransmitonebit.Withoutlossofgenerality,weset τ0 = 302μs, τbit = 18.88μs, pc = 1 2 . Besides, α¯ should be a small number(such as 2, 3, or 4) [3], considering the actual situ￾ation. Therefore, α¯ is limited to [1, 4]. We get the optimal value of α¯ is α¯ ∗ = 4, the corresponding optimal value of d is d∗ = 7. We set α¯ = ¯α∗, d = d∗, the frame size f = c α¯ = c α¯ ∗ . More detail information of performance analysis can be found in the conference version of this paper [18]. 7 Enhanced collision detection based rule checking protocol 7.1 Motivation CRCP mainly focuses on verifying all the related category IDs in the scanning area while ignoring the rule’s logical feature. In this section, we propose an Enhanced Collision detection based Rule Checking Protocol (ECRCP) in con￾sideration of the rule’s logical property. In fact, in the OR rule, if any category exists, the rule’s Boolean value is true. In the AND rule, if any category is out of the scanning area, the rule’s Boolean value is false. In the EXCLUSIVE rule, if any category is out of the scanning area, the rule’s Boolean value is true. In regard to a hybrid rule, it can be determined by its subrule’s Boolean value in a similar way. Therefore, when the reader gets a part of the category IDs, it can check the correlated rules. Then it only needs to check the remaining categories in the unverified rules. 7.2 Protocol description 7.2.1 Estimating the tag size In CRCP, the reader sends the request message to tags based on Bloom filter, while ignoring the effect of tag size. When the tag size in the scanning area is much smaller than the number of related categories, CRCP is rather time￾consuming. Thus ECRCP uses the average run based tag estimation (ART) scheme [13] to estimate the tag size. If the ratio ρ of tag size to the number of related categories is less than the threshold ρ∗, the reader will use APCR to check the rules. Otherwise, the reader uses the Bloom filter to inform the related categories to give responses and verifies the categories, as described in the following subsections. 7.2.2 Finding the popular category Based on Section 4, a related category may exist in serval rules. We use frequency fj to describe the number of times that Cj appears in different rules. If Cj appears in a differ￾ent rule, fj only adds one to its original value, no matter how many times Cj appears in this rule. For example, in the rule Ri = (Cj ∧Ck )∨(Cj ∨Cu), fj , fk, fu respectively add one. Obviously, fj ∈ [1, m], m is the number of rules. If a category Cj has a larger value of fj , it means that the cate￾gory affects more rules’ Boolean values. ECRCP first finds the unverified popular category ID with the largest value Mobile Netw Appl (2014) 19:524–533 529