and sets these bits to 1.When a tag receives the request,it C.Resolving the Collision Slot checks the corresponding k bits.Only all the bits are 1,it gives According to Algorithm 1.the critical problem of CRCP is response.See Fig.2 for an example of 3,I 16,the how to resolve the collision slots efficiently.In fact,decoding reader uses hi(Ci)mod 16(iE [1,3],j[1,5])to construct M;from M is like to solve the system of linear equations.In the Bloom filter.The tags in C1,C2,C3,C4,Cs pass the test an a-collision slot,a represents the number of variables in and give responses,while the tags in Co do not pass the test an equation,while the length of Manchester code d represents and keep silent.If a tag in C;should give response in the the number of equations.In order to simplify the procedure following frame with size f,it uses a hash function h to select of resolving the collision slot,we compare each bit in the a slot hr(Ci)mod f.Then,the tag sends d bits Manchester expected code M with the corresponding bit in received code code Mi.Here,Mi=h(Ci)mod (24),h is a hash function. Mr to decode Mi,as shown in Algorithm 2. Because the reader knows the related categories and the hash functions,it can get the mapping relation of C;and Mi. Algorithm 2:Resolving an a-collision slot When getting the responses,the reader checks whether each Input:d bits expected Manchester code M composed of bit in the slot can be recovered from the mixed signal.If [M,M2,...,M),corresponding category IDs the bits cannot be recovered,it means the number of tags responding in the slot is too large.Then the reader puts the C1,C2,...,Ca}.received Manchester code M corresponding category IDs into the new set C,which will be Boolean values of [Ci}are stored in [B(C)). verified later.If the bits can be recovered successfully,then the Initialization:B(Cj)=-1,j[1,a]. if M.=null then reader resolves the collision slots,as shown in Algorithm 1.In B(C1)=0,B(C2)=0,,B(Ca)=0. the frame received from tags,suppose that the reader is able Return. to get qi new category IDs Ci,Ci,...,Ck by decoding an a if a=1 then -collision slot.The reader decodes the collision slots one by |B(C)=1. one until it gets all the c related category IDs in the frame or LReturn. the frame terminates.Then,it repeats the similar process.At while i∈[l,ddo last,the reader verify the category IDs in C'using probability pr.The reader broadcasts an integer y =[pr x Y],Y is a M(间=10+∑11,0+m1=a. Use the known set {B(Ci)=0}to update large constant.Then the tag calculates the hash result h(ID) M(i),no,ni,a. mod Y,only if h(ID)mod Y<y,the tag gives response. if M(i)=x and M,(i)=0 then In this way,there will be only a few number of tags (eg.1)in for each Mi(i)=1 do B(Cj)=0. one category giving responses.Then,the reader can decode the if no 1 then category IDs.When all the related category IDs are verified, for each Mj(i)=0 do B(Cj)=1. the reader will check the rules based on section IV if M(i)=x and M(i)=1 then for each Mj(i)=0 do B(Cj)=0. if n 1 then Algorithm 1:CRCP:Reader Side for each Mj(i)=1 do B(Cj)=1. Input:m rules [R,R2,...,Rm},n related category IDs {C1,C2,....Cn},frame size f if M(i)=x and M(i)=x then z=0,q=0. if no 1 then while any related category is not verified do for each Mj(i)=0 do B(C)=1. Set g=0,and set c equal to the number of if n=1 then unverified related category IDs. for each Mj(i)=1 do B(Cj)=1. Send the request Bloom filter. In a new frame,wait for the tags'responses. Output:Verified category IDs.(CiB(Ci)-1).) for each slot i∈[1，f月amdq<cdo if Manchester code cannot be recovered then LPut these category IDs into set C. In Algorithm 2,null means an empty slot.M(i)mean- s the ith bit in the Manchester code M.M(i)and else Mi(i),M2(i),...,M(i)are defined in the same way.Based Decode the a-collision slot. on the description in section III,M(i)equals 0,1 or x.It Get gi new verified categories,g=g+gi. is produced as follows,.M)=∑eo0+∑1l.no and 2=2十q. mi respectively represent the number of Mi(i)(j [1,a]) if Cardinality of C=n-z then equivalent to 0 and 1 in the slot.Before the reader decodes the LVerify the tags in C using probability pr. category IDs in the ith bit,it will use the known set [B(C)} Check the rules according to the verified categories to update M(i).If B(C)=0,the reader removes Mi from Output:Checking result B(R1),B(R2),...,B(Rm). M and updates M(i),no.n1,a.If the expected bit M(i)=x, while the received bit Mr(i)=0,then the category Ci withand 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. 2 for an example of k = 3, l = 16, 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 do not pass the test and 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, the tag 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 IV. Algorithm 1: CRCP: Reader Side Input: m rules {R1, R2,...,Rm}, n related category IDs {C1, C2,...,Cn}, frame size f z = 0, q = 0. while any related category is not verified do Set q = 0, and set c equal to the number of unverified related category IDs. Send the request Bloom filter. In a new frame, wait for the tags’ responses. for each slot i ∈ [1, f] and q<c do if Manchester code cannot be recovered then Put these category IDs into set C . else Decode the α – collision slot. Get qi new verified categories, q = q + qi. z = z + q. if Cardinality of C = n − z then Verify the tags in C using probability pr. Check the rules according to the verified categories Output: Checking result B(R1), B(R2),...,B(Rm). C. 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. Algorithm 2: Resolving an α – collision slot Input: d bits expected Manchester code M composed of {M1, M2,...,Mα}, corresponding category IDs {C1, C2,...,Cα}, received Manchester code Mr, Boolean values of {Cj} are stored in {B(Cj )}. Initialization: B(Cj ) = −1, j ∈ [1, α]. if Mr = null then B(C1)=0, B(C2)=0,..., B(Cα)=0. Return. if α = 1 then B(C1)=1. Return. while i ∈ [1, d] do M(i) = n0 j=1 0 + n1 j=1 1, n0 + n1 = α. Use the known set {B(Cj )=0} to update M(i), n0, n1, α. if M(i) = x and Mr(i)=0 then for each Mj (i)=1 do B(Cj )=0. if n0 = 1 then for each Mj (i)=0 do B(Cj )=1. if M(i) = x and Mr(i)=1 then for each Mj (i)=0 do B(Cj )=0. if n1 = 1 then for each Mj (i)=1 do B(Cj )=1. if M(i) = x and Mr(i) = x then if n0 = 1 then for each Mj (i)=0 do B(Cj )=1. if n1 = 1 then for each Mj (i)=1 do B(Cj )=1. Output: Verified category IDs. ({Cj |B(Cj ) = −1}.) In Algorithm 2, null means an empty slot. M(i) mean￾s 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 III, 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 bit M(i) = x, while the received bit Mr(i)=0, then the category Cj with