the corresponding bit equivalent to 1 is outside the scanning no E [2,a-1],M;can be decoded when the received bit area,B(Ci)=0.Besides,if no =1,the category Ci with is null or 1.It indicates that the received bit is only produced corresponding bit equivalent to 0 must in the scanning area. by s bits which equal to 1,s E[0,n].The process is like a B(Cj)=1.If M(i)=x and M(i)=1,we can get the Bernoulli process,the probability is ().p.(1-pe)(-) conclusion in the same way.However,if the expected bit s[0,n].Therefore,the probability that the received bit M(间=x=0+∑g=1 and the received bitM,()=x,is null or1 is P(mult/n=∑o()·p2·(1-pe)a- then the category Ci with corresponding bit equivalent to 0 Meanwhile,the conditional probability that the current bit gives response,B(C)=1.If M(i)=x1+and equals 0,while n bits equal to 1 in the other a-1 bits M,()=X,we can get the conclusion in the same'Wway.The is P(eon）)=pwo·(（l)·p·p81-n).Therefore,he reader repeats the similar process until it decodes all the a probability of getting Mj is p(n2)=P(con)P(nuu/1). category IDs or it has repeated d times. If no =a,Mi can be decoded only when the received bit is We give an example in table I,the expected Manchester null,the probability is p(no=)=p8o(1-Pe).Then,we can code M is composed of [M,M2,M3,M4},the received code M =x0xxxx.M xxxxxx,M(1)=x=0+=1.only obtain that Pbito P(no=1)+P(n2+P(no=a) Moreover,we can get pbiti in the same way.Obviously, M3(1)=0.Besides,M(1)=M.(1)=x.It indicates M3 Pbit1=Pbito.Therefore,pbit =2 x pbito P(a). must give the response.Therefore,B(C3)=1.We can get The probability that a category ID Ci can be decoded in B(C)=0 in the same way.Then,the reader removes Ca and a slot is pa =1-(1-pbit)d,d is the length of M.The updates the third bit in M.M(3)=0+1+1 =x,no =1,time duration of a frame istf =(Tit.d+To).f.To denotes n1 =2,M is composed of {M,M2,M3},a=3.It repeats the waiting time between any two consecutive transmissions, the similar process and gets B(C1)=1,B(C2)=1. and Toit denotes the time for a tag to transmit one bit.We TABLE I estimate the response time tres for all the category IDs as AN EXAMPLE FOR RESOLVING A COLLISION SLOT WITH a=4 re where a and pa represent the apa Step 2 average value of a and pa,respectively.We should minimize Expected 1,M2, 1,M2. M1,2, M1,M2, tres and it is achieved by maximizing the following function Mi set M3,M4 Ms,M4 Ms Ms Expected XXXXXX XXXXXX XXXXXX XXXXXX code T(a,d) aa=a·1-(1-P(a) (1) Received X0xxXX XOxxxx x0xxXX x0xXxX Tbit·d+To Tbit·d+To code In order to decode the category IDs,a d.Then we can M 100I0I 100101 100I01V 100101 M2 101010 101010 101010 101010W get the optimal values of a and d in the limited search space M3 001111V 001111T 001111 001111 through enumeration.Without loss of generality,we set To= MA 110011 110011× 302us,Tbit 18.88us,pe =Besides,a should be a small B(Ci) B(C3)=1B(C4)=0 BC1)=1 B(C2)=1 number(such as 2,3,or 4)[5],considering the actual situation. D.Performance Analysis Therefore,is limited to [1,4].We get the optimal value of a is a*=4,the corresponding optimal value of d is d*=7. In CRCP,the reader uses k hash functions and c category IDs to construct the Bloom filter with length l.We use po We set a=a*,d=d*,the frame size f=景=÷ If a e1,4,the reader has a high probability for decoding to represent the probability of any bit equivalent to 0,po (1-)ke-ke/.Therefore,the false positive probability Cj.However,if the number of tags is large,the mixed signal of the Bloom filter is pf(l,k,c)=(1-po)(1-e-ke/l)k may be irresolvable.In this case,the reader verifies the categories using pr,which is a random number in (0,1).It In order to minimize pf(l,k,c),the optimal value of k is set repeats the process until all the related categories are verified. ask=(a2)(伯，If we requirep(,k,d)≤e,the value of I should satisfy We set I- VII.ENHANCED COLLISION DETECTION BASED RULE -In(E)-c n②n(② CHECKING PROTOCOL In the frame received from tags,we respectively use poo A.Motivation and poi to represent the probability that a bit in a category ID CRCP mainly focuses on verifying all the related category equivalent to 0 and 1,po =poi =Each category responds IDs in the scanning area while ignoring the rule's logical with probability pe.We use pbit to represent the probability feature.In this section,we propose an Enhanced Collision that a Manchester code M;can be decoded by a bit M;(i)of detection based Rule Checking Protocol(ECRCP)in consid- Mi.If the bit used for decoding M;is 0,the probability that eration of the rule's logical property.In fact,in the OR rule, Mj can be decoded is pbito.pbit is defined in the same way, if any category exists,the rule's Boolean value is true.In the Pbit Pbito Pbit1.When a 1,pbit 1.If a 1,we can AND rule,if any category is out of the scanning area,the calculate pbit by pbito and pbiti as follows. rule's Boolean value is false.In the EXCLUSIVE rule,if any In regard to pbito,the bit used for decoding Mi is 0.Based category is out of the scanning area,the rule's Boolean value on Algorithm 2.the ith expected bit M(i)+is true.In regard to a hybrid rule,it can be determined by 1.If no =1.Mj can always be decoded.The its subrule's Boolean value in a similar way.Therefore,when probability of this situation is P()pup).If the reader gets a part of the category IDs,it can check thethe 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 the conclusion in the same way. The reader repeats the similar process until it decodes all the α category IDs or it has repeated d times. We give an example in table I, 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. TABLE I 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 D. Performance Analysis In CRCP, the reader uses k hash functions and c category IDs to construct the Bloom filter with length l. We use p0 to represent the probability of any bit equivalent to 0, p0 = (1 − 1 l )kc ≈ e−kc/l. Therefore, the false positive probability of the Bloom filter is pf (l, k, c) = (1 − p0)k ≈ (1 − e−kc/l)k. In order to minimize pf (l, k, c), the optimal value of k is set as k∗ = (ln2) l c  . If we require pf (l, k, c) ≤ , the value of l should satisfy l ≥ −ln()·c ln(2)·ln(2) . We set l =  −ln()·c ln(2)·ln(2) . In the frame received from tags, we respectively use pb0 and pb1 to represent the probability that a bit in a category ID equivalent to 0 and 1, pb0 = pb1 = 1 2 . Each category responds with probability pc. We use pbit to represent the probability that a Manchester code Mj can be decoded by a bit Mj (i) of Mj . If the bit used for decoding Mj is 0, the probability that Mj can be decoded is pbit0. pbit1 is defined in the same way, pbit = pbit0 + pbit1. When α = 1, pbit = 1. If α > 1, we can calculate pbit by pbit0 and pbit1 as follows. In regard to pbit0, the bit used for decoding Mj is 0. Based on Algorithm 2, the ith expected bit M(i) = n0 j=1 0 + n1 j=1 1. If n0 = 1, Mj can always be decoded. The probability of this situation is p(n0=1) = pb0 · p (α−1) b1 . If n0 ∈ [2, α − 1], Mj can be decoded when the received bit is null or 1. It indicates that the received bit is only produced by s bits which equal to 1, s ∈ [0, n1]. The process is like a Bernoulli process, the probability is n1 s  · ps c · (1 − pc)(α−s) , s ∈ [0, n1]. Therefore, the probability that the received bit is null or 1 is p(null/1) = n1 s=0 n1 s  · ps c · (1 − pc)(α−s) . Meanwhile, the conditional probability that the current bit equals 0, while n1 bits equal to 1 in the other α − 1 bits is p(con) = pb0 · α−1 n1  · pn1 b1 · p (α−1−n1) b0 . Therefore, the probability of getting Mj is p(n0∈[2,α−1]) = p(con) · p(null/1). If n0 = α, Mj can be decoded only when the received bit is null, the probability is p(n0=α) = pα b0 ·(1−pc)α. Then, we can obtain that pbit0 = p(n0=1) + α−1 n0=2 p(n0∈[2,α−1]) + p(n0=α). Moreover, we can get pbit1 in the same way. Obviously, pbit1 = pbit0. Therefore, pbit = 2 × pbit0 = P(α). The probability that a category ID Cj can be decoded in a slot is pd = 1 − (1 − pbit)d, d is the length of Mj . The time duration of a frame is tf = (τbit · d + τ0) · f, τ0 denotes the waiting time between any two consecutive transmissions, and τbit denotes the time for a tag to transmit one bit. We estimate the response time tres for all the category IDs as tres ≈ n f·α¯·p¯d ·tf = (τbit·d+τ0)n α¯·p¯d , where α¯ and p¯d represent the average value of α and pd, respectively. We should minimize tres and it is achieved by maximizing the following function T(¯α, d) α¯ · p¯d τbit · d + τ0 = α¯ · 1 −  1 − P(¯α) d τbit · d + τ0 . (1) In order to decode the category IDs, α¯ ≤ d. Then we can get the optimal values of α¯ and d in the limited search space through enumeration. Without loss of generality, we set τ0 = 302μs, τbit = 18.88μs, pc = 1 2 . Besides, α¯ should be a small number(such as 2, 3, or 4) [5], considering the actual situation. 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 α¯∗ . If α¯ ∈ [1, 4], the reader has a high probability for decoding Cj . However, if the number of tags is large, the mixed signal may be irresolvable. In this case, the reader verifies the categories using pr, which is a random number in (0, 1). It repeats the process until all the related categories are verified. VII. ENHANCED COLLISION DETECTION BASED RULE CHECKING PROTOCOL A. 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 consid￾eration 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