correlated rules.Then it only needs to check the remaining interrogation region(three-dimensional physical space)is set categories in the rules which have not been verified. to 5000 at most.Based on the above limitation,the tag IDs and the rules are generated randomly.Unless otherwise specified, Algorithm 3:ECRCP:Reader Side we set the length of category ID to 32bits,the number of Input:m rules {R1,R2,...,Rm},{B(Ri)}is used for tags to 3000 and the number of rules to 300 by default.The storing the Boolean values of [Ri. false positive probability is set to 1x 10-4.Under the same while any rule is not yet checked do simulation setting,we average the results over 100 trials. for each Rule Ri do B.Optimal Values of and d if Rule Ri is not yet checked then LSelect an undetermined category ID in Ri We first investigate the optimal values of a and d in CRCP. The execution time under different values of a and d is Start a new Ouery based on the selected category IDs. illustrated in Fig.3.When approaches to 4 and d approaches Call Algorithm 1 to verify these category IDs. to 7,the execution time decreases.When =4.5,6.7. Check the undetermined rules based on the verified the protocol has the good performance.However,only when category IDs. =4 and d=7,the execution time gets the minimum value. Output:B(R1),B(R2),...,B(Rm). When a is too small (=2,3),the kinds of category IDs in the slot are small and collision slots cannot be fully utilized. B.Protocol Description On the contrary,if a is too large(a >8),the collision slots In ECRCP,the reader successively selects the related cat- are difficult to be decoded.which wastes a lot of time.When egory IDs from different rules to produce the Bloom filter, approximates to 4 (=5,6,7),the kinds of category IDs in which aims at determining more rules'Boolean values with a slot are appropriate.However,there may be more than one the verified category IDs,as shown in Algorithm 3.It selects tag in a category,the number of tags responding in the same one undetermined category ID from each rule not yet verified slot can be large,causing the collision slot to be irresolvable. and resolves the category IDs like CRCP.Then,the reader The problem becomes more serious with the increase of a. checks the rules based on the verified category IDs instead of Therefore,the optimal values of a and d are =4 and d=7, entering the next Query Cycle.After that,it will only check which are not relevant to the length of category ID,the number the categories in the rules with unknown Boolean values.It of rules or tags,and are used in the following experiments. repeats the similar process until all the rules are checked. C.Execution Time Comparison In order to describe the process more clearly,we provide Fig.4.5.6 shows the execution time,CRCP and ECRCP an example here.We assume that R1=C1 VC2 VC3,R2=have better performances,and ECRCP achieves the highest C4 A Cs,R3=(C6 A C7).The reader checks C1,C4,C6 time efficiency.In Fig.4,when the length of Cj is 64 bits, first and gets B(C1)=1,B(C4)=1 and B(C6)=0.It can the execution time of ECRCP is about 0.6 seconds,which conclude that B(R1)=1,B(R3)=1.Then,it only needs to is 3.4%of the time required by ARCP.The performance of check the unknown category ID Cs in R2 while ignoring C2, ECRCP is unrelated to the length of category ID.In Fig.5, C3,C7.Therefore,ECRCP is more efficient than CRCP. when the number of tags is 5000,the execution time of ECRCP VIII.PERFORMANCE EVALUATION is about 0.6 seconds,which is 2.1%of the time required by ARCP.The number of tags has no effect on ECRCP,because In this section,we evaluate the performance of our two effi- ECRCP focuses on the categories in the rules instead of those cient protocols by comparing them with the baseline protocols. in the scanning area.In Fig.6,when the number of rules We use the overall execution time as the performance metric. is 500,the execution time of ECRCP is about 0.9 seconds, A.Experiment Setting which is 3.5%of the time required by BRCP.This is because We use the following parameters [12]to configure the ECRCP not only resolves the collision slot but also leverages simulation:each tag ID is 96 bits.The rate from the reader to the rule's logical feature.In Fig.7,when the number of rules tags is 26.5Kb/s,it takes 37.76us for the reader to transmit is 50,ECRCP only verifies 24%of the related category IDs. one bit.Any two consecutive transmissions are separated by D.Accuracy of checking all the rules a waiting time To 302us.If the category ID is 32 bits Fig.8 illustrates the accuracies of checking all the rules. long,it takes 1510us for the reader to transmit it with a The accuracies of ARCP and PRCP are higher than those of time interval included.The rate from a tag to the reader is BRCP,CRCP and ECRCP.This is because that BRCP,CRCP 53Kb/s,it takes 18.88us for a tag to transmit one bit.If and ECRCP use the Bloom filter,which has the probability of the tag transmits d bits to the reader,the transmission time false positive,which can result in decoding the category IDs of the slot is (302+18.88 x d)us.In regard to an empty wrongly,leading to wrong result of the corresponding rule. slot,it needs 321us for the reader to detect it.In PRCP and However,the accuracy of 96%can be achieved by CRCP BRCP,the tag can transmit one-bit information to the reader to and ECRCP,which is high enough in many applications. announce its presence.The slot is about 321us.In regard to the Furthermore,the accuracy of 98%can be achieved by ECRCP. number of tags in the scanning area,considering the limited When the number of rules is 300,the accuracy of ECRCP is effective scanning range (eg.5-6m),the number of tags in the 99.5%.If a higher accuracy is needed,we can properly adjustcorrelated rules. Then it only needs to check the remaining categories in the rules which have not been verified. Algorithm 3: ECRCP: Reader Side Input: m rules {R1, R2,...,Rm}, {B(Ri)} is used for storing the Boolean values of {Ri}. while any rule is not yet checked do for each Rule Ri do if Rule Ri is not yet checked then Select an undetermined category ID in Ri. Start a new Query based on the selected category IDs. Call Algorithm 1 to verify these category IDs. Check the undetermined rules based on the verified category IDs. Output: B(R1), B(R2),...,B(Rm). B. Protocol Description In ECRCP, the reader successively selects the related cat￾egory IDs from different rules to produce the Bloom filter, which aims at determining more rules’ Boolean values with the verified category IDs, as shown in Algorithm 3. It selects one undetermined category ID from each rule not yet verified and resolves the category IDs like CRCP. Then, the reader checks the rules based on the verified category IDs instead of entering the next Query Cycle. After that, it will only check the categories in the rules with unknown Boolean values. It repeats the similar process until all the rules are checked. In order to describe the process more clearly, we provide an example here. We assume that R1 = C1 ∨ C2 ∨ C3, R2 = C4 ∧ C5, R3 = ¬(C6 ∧ C7). The reader checks C1, C4, C6 first and gets B(C1)=1, B(C4)=1 and B(C6)=0. It can conclude that B(R1)=1, B(R3)=1. Then, it only needs to check the unknown category ID C5 in R2 while ignoring C2, C3, C7. Therefore, ECRCP is more efficient than CRCP. VIII. PERFORMANCE EVALUATION In this section, we evaluate the performance of our two effi- cient protocols by comparing them with the baseline protocols. We use the overall execution time as the performance metric. A. Experiment Setting We use the following parameters [12] to configure the simulation: each tag ID is 96 bits. The rate from the reader to tags is 26.5Kb/s, it takes 37.76μs for the reader to transmit one bit. Any two consecutive transmissions are separated by a waiting time τ0 = 302μs. If the category ID is 32 bits long, it takes 1510μs for the reader to transmit it with a time interval included. The rate from a tag to the reader is 53Kb/s, it takes 18.88μs for a tag to transmit one bit. If the tag transmits d bits to the reader, the transmission time of the slot is (302 + 18.88 × d)μs. In regard to an empty slot, it needs 321μs for the reader to detect it. In PRCP and BRCP, the tag can transmit one-bit information to the reader to announce its presence. The slot is about 321μs. In regard to the number of tags in the scanning area, considering the limited effective scanning range (eg. 5-6m), the number of tags in the interrogation region (three-dimensional physical space) is set to 5000 at most. Based on the above limitation, the tag IDs and the rules are generated randomly. Unless otherwise specified, we set the length of category ID to 32bits, the number of tags to 3000 and the number of rules to 300 by default. The false positive probability is set to 1 × 10−4. Under the same simulation setting, we average the results over 100 trials. B. Optimal Values of α¯ and d We first investigate the optimal values of α¯ and d in CRCP. The execution time under different values of α¯ and d is illustrated in Fig. 3. When α¯ approaches to 4 and d approaches to 7, the execution time decreases. When α¯ = 4, 5, 6, 7, the protocol has the good performance. However, only when α¯ = 4 and d = 7, the execution time gets the minimum value. When α¯ is too small (α¯ = 2, 3), the kinds of category IDs in the slot are small and collision slots cannot be fully utilized. On the contrary, if α¯ is too large(α¯ ≥ 8), the collision slots are difficult to be decoded, which wastes a lot of time. When α¯ approximates to 4 (α¯ = 5, 6, 7), the kinds of category IDs in a slot are appropriate. However, there may be more than one tag in a category, the number of tags responding in the same slot can be large, causing the collision slot to be irresolvable. The problem becomes more serious with the increase of α¯. Therefore, the optimal values of α¯ and d are α¯ = 4 and d = 7, which are not relevant to the length of category ID, the number of rules or tags, and are used in the following experiments. C. Execution Time Comparison Fig. 4, 5, 6 shows the execution time, CRCP and ECRCP have better performances, and ECRCP achieves the highest time efficiency. In Fig. 4, when the length of Cj is 64 bits, the execution time of ECRCP is about 0.6 seconds, which is 3.4% of the time required by ARCP. The performance of ECRCP is unrelated to the length of category ID. In Fig. 5, when the number of tags is 5000, the execution time of ECRCP is about 0.6 seconds, which is 2.1% of the time required by ARCP. The number of tags has no effect on ECRCP, because ECRCP focuses on the categories in the rules instead of those in the scanning area. In Fig. 6, when the number of rules is 500, the execution time of ECRCP is about 0.9 seconds, which is 3.5% of the time required by BRCP. This is because ECRCP not only resolves the collision slot but also leverages the rule’s logical feature. In Fig. 7, when the number of rules is 50, ECRCP only verifies 24% of the related category IDs. D. Accuracy of checking all the rules Fig. 8 illustrates the accuracies of checking all the rules. The accuracies of ARCP and PRCP are higher than those of BRCP, CRCP and ECRCP. This is because that BRCP, CRCP and ECRCP use the Bloom filter, which has the probability of false positive, which can result in decoding the category IDs wrongly, leading to wrong result of the corresponding rule. However, the accuracy of 96% can be achieved by CRCP and ECRCP, which is high enough in many applications. Furthermore, the accuracy of 98% can be achieved by ECRCP. When the number of rules is 300, the accuracy of ECRCP is 99.5%. If a higher accuracy is needed, we can properly adjust