528 Mobile Netw Appl (2014)19:524-533 the reader uses hi(Cj)mod 16 (i [1,3],j [1,5])to Algorithm 1 CRCP:Reader Side construct the Bloom filter.The tags in C1,C2,C3,C4.Cs Input:m rules {R1,R2,...,Rm,n related category pass the test and give responses,while the tags in C9 keep IDs C1,C2,...,Cn,frame size f silent.If a tag in Ci should give response in the following 2=0,9=0. while any related category is not verified do frame with size f,it uses a hash function h to select a slot Set g=0,and set c equal to the number of h(Ci)mod f.Then,it sends d bits Manchester code Mj. unverified related category IDs. Send the request Bloom filter. Here,Mi=h(Ci)mod (2d),h is a hash function. In a new frame,wait for the tags'responses. Because the reader knows the related categories and the for each slot iE [1,f]and g<c do if Manchester code cannot be recovered then hash functions,it can get the mapping relation of Cj and L Put these category IDs into set Mi.When getting the responses,the reader checks whether else each bit in the slot can be recovered from the mixed sig- Decode the a-collision slot. Get di new verified categories,g=g+qi. nal.If the bits cannot be recovered.it means the number of 22+日. tags responding in the slot is too large.Then the reader puts if Cardinality of C=n-z then the corresponding category IDs into the new set C',which L Verify the tags in C using probability pr. will be verified later.If the bits can be recovered success- Check the rules according to the verified categories Output:Checking result B(R1),B(R2),...,B(Rm ) fully,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 bit M(i)=x,while the received bit Mr(i)=0,then by decoding an a-collision slot.The reader decodes the the category Cj with the corresponding bit equivalent to collision slots one by one until it gets all the c related cate- 1 is outside the scanning area,B(Ci)=0.Besides,if gory IDs in the frame or the frame terminates.Then,it no =1,the category Ci with corresponding bit equivalent repeats the similar process.At last,the reader verify the to 0 must in the scanning area,B(Cj)=1.If M(i)=x category IDs in C'using probability pr.The reader broad- and Mr(i)=1,we can get the conclusion in the same way. casts an integer y [pr x Y1,Y is a large constant.Then the tag calculates the hash result hr(ID)mod Y,only if However,if the expected bit M(i)=1 and the received bit Mr(i)=x,then the category Cj with cor- hr(ID)mod Yy,the tag gives response.In this way, responding bit equivalent to 0 gives response,B(Ci)=1. there will be only a few number of tags (eg.1)in one cate- gory giving responses.Then,the reader can decode the If M(i)=x=1+0 and M,(i)=x.we can get category IDs.When all the related category IDs are verified, the reader will check the rules based on Section 4. Algorithm 2 Resolving an a-collision slot 6.3 Resolving the collision slot Input:d bits expected Manchester code M composed of {M,M2,...,Ma,corresponding category IDs (C1,Ca,..C),received Manchester According to Algorithm 1,the critical problem of CRCP code Mr,Boolean values of fC,}are stored in B(C)} is how to resolve the collision slots efficiently.In fact, Initialization:B(C)=-l,j∈[1，a] decoding Mj from M is like to solve the system of linear if M,null then BC1)=0,B(C2)=0.,,,B(Ca)=0 equations.In an a-collision slot,o represents the number Return. of variables in an equation,while the length of Manchester if a=I then B(C)=1 code d represents the number of equations.In order to LReturn. simplify the procedure of resolving the collision slot,we while i 1,d do compare each bit in the expected code M with the corre- |M()=∑°10+∑11,0+1=a Use the known set {B(C;)=0}to update sponding bit in received code M,to decode Mi,as shown M(),o,n1,. if M(i)=x and Mr(i)=0 then in Algorithm 2. for each Mj(i)=1 do B(Cj)=0. In Algorithm 2,null means an empty slot.M(i) if no 1 then for each Mi(i)=0 do B(C;)=1. means the ith bit in the Manchester code M.M(i)and Mi(i),M2(i).....Ma(i)are defined in the same way. if M(i)=x and M,(i)=1 then for each M (i)=0 do B(C)=0. Based on the description in Section 3,M(i)equals 0,1 or x. if n=1 then It is produced as follows,M(i)=1.no and L for each Mj(i)=1 do B(C;)=1. nI respectively represent the number of Mj(i)(j[1,a]) if M(i)=x and M(i)=x then if no =1 then equivalent to 0 and 1 in the slot.Before the reader decodes Lfor each M;(i)=0 do B(C;)=1. the category IDs in the ith bit,it will use the known set if n=1 then [B(Ci)}to update M(i).If B(Ci)=0,the reader removes for each Mi(i)=1 do B(Ci)=1. Mj from M and updates M(i),no,n1.a.If the expected Output:Verified category IDs.(Ci B(Ci)-1.) ②Springerthe 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 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, it 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 sig￾nal. 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 success￾fully, 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 cate￾gory 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 broad￾casts 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 cate￾gory 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 4. 6.3 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 corre￾sponding bit in received code Mr to decode Mj , as shown in Algorithm 2. In Algorithm 2, null means an empty slot. M(i) means 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 3, 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 Algorithm 1 CRCP: Reader Side bit M(i) = x, while the received bit Mr(i) = 0, then the category Cj with the 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 cor￾responding 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 Algorithm 2 Resolving an α – collision slot 528 Mobile Netw Appl (2014) 19:524–533