530 Mobile Netw Appl (2014)19:524-533 of fi from the unverified rules.If several categories have At this time,all the unverified rules are selected.The reader the same values of fi,the reader randomly chooses one of verifies CI and C6 like CRCP.If the reader gets B(C1)=1. them as the popular category.Then,it updates the frequency B(C6)=0,it can immediately conclude that B(R1)=1, of each unverified related category in the remaining rules B(R4)=1.After that,the reader only needs to verify the by eliminating the selected rules,which contain the popular undetermined categories C3,C4.Cs in the unverified rules category,as shown in Algorithm 3. R2,R3,while ignoring other categories.Obviously,ECRCP Algorithm 3 ECRCP:Reader Side only needs to verify a part of the related categories instead of all of them. Input:m rules (R,R2:....Rm},Boolean values of {Ri}is {B(Ri)},frequency of (Ci}is (f, popular category set is {C). Estimate the tag size N in the interrogation region 8 Performance evaluation if N<p*x m then Use ARCP to check the rules. L Return. Initialize f}by setting f=0. We evaluate the performance of our proposed protocols by while any rule is not yet checked do comparing them with the baseline protocols.We use the Checked rules are defined as original selected rules,C=. overall execution time as the performance metric. while any unchecked rule is not yet selected do for each unselected rule ri do if Ci is unverified and C;erists in R 8.1 Experiment setting then fj=fi+1. Select the popular category C:with the We use the following parameters [14]to configure the simu- largest value of fi. ifC=then f防三f: lation:tag ID is 96 bits long.It takes 37.76us for the if C*0 andf<f;then Break. reader to transmit one bit.Any two consecutive transmis- AddC;into{C◆}，the rules containing C L are selected. sions are separated by a waiting time to =302us.It takes Call Algorithm 1 to verify the categories in (C*}. 18.88us for a tag to transmit one bit.If the tag transmits Check the undetermined rules based on the d bits to the reader,the transmission time of the slot is verified category IDs. Output:B(R),B(R2),...,B(Rm). (302+18.88 xd)us.It needs 32lus for the reader to detect an empty slot.In PRCP and BRCP,the tag can transmit one-bit information to announce its presence.The slot is about 321us.The number of tags in the interrogation region 7.2.3 Checking the rules (three-dimensional physical space)is set to 5000 at most. Unless otherwise specified,we set the length of category When the reader first selects the popular category ID C. ID to 32bits,the number of tags to 3000 and the number of it adds C into the set [C*).Then,it updates fi of each rules to 300 by default.The false positive probability is set unverified category Ci in the unchecked rules.The reader to 1 x 10-4.Under the same simulation setting,we average selects the new popular category,which has the same fre- the results over 100 trials. quency with thethe former popular category,adding it into (C*).It repeats the above process until no category can be 8.2 Optimal values of a and d added into [C*).The reader uses [C*)to produce the Bloom filter,as shown in Algorithm 3.When the reader gets the Based on Fig.4,when approaches to 4 and d approaches responses from the tags,it will resolve the category IDs like to 7,the execution time decreases.When a is too small (a CRCP.Then.it checks the correlated rules.After that.the reader will only check the remaining related categories in the unverified rules.It repeats the similar process until all the rules are checked. In order to describe the process well,we provide an example.We assume that R =C1V C2.R2 CIA C3, R3 =(C4A Cs)V(C4AC6),R4=-(C6AC7).Firstly,the 20 reader gets fi=2,f2=1,f3 =1,f4=1,f5 =1,f6=2, 10 f7=1.CI and C6 have the largest frequency value.It ran- domly selects Ci as the popular category,[C*)=(C1).The value of frequency in [C*)is f*=fi =2.Then,it updates 3222420 fj of each unverified category in the remaining unselected d (bit)128 rules (R3,R4),f4 =1,fs =1,f6 =2,f7=1.Obviously, 0048121620242832 C6 is the popular category and f6=f.[C*)=(C1,C6]. Fig.4 Optimal values of a and d ②Springerof fj from the unverified rules. If several categories have the same values of fj , the reader randomly chooses one of them as the popular category. Then, it updates the frequency of each unverified related category in the remaining rules by eliminating the selected rules, which contain the popular category, as shown in Algorithm 3. Algorithm 3 ECRCP: Reader Side 7.2.3 Checking the rules When the reader first selects the popular category ID C∗ j , it adds C∗ j into the set {C∗}. Then, it updates fj of each unverified category Cj in the unchecked rules. The reader selects the new popular category, which has the same fre￾quency with the the former popular category, adding it into {C∗}. It repeats the above process until no category can be added into {C∗}. The reader uses {C∗} to produce the Bloom filter, as shown in Algorithm 3. When the reader gets the responses from the tags, it will resolve the category IDs like CRCP. Then, it checks the correlated rules. After that, the reader will only check the remaining related categories in the unverified rules. It repeats the similar process until all the rules are checked. In order to describe the process well, we provide an example. We assume that R1 = C1 ∨ C2, R2 = C1 ∧ C3, R3 = (C4 ∧ C5) ∨ (C4 ∧ C6), R4 = ¬(C6 ∧ C7). Firstly, the reader gets f1 = 2, f2 = 1, f3 = 1, f4 = 1, f5 = 1, f6 = 2, f7 = 1. C1 and C6 have the largest frequency value. It ran￾domly selects C1 as the popular category, {C∗}={C1}. The value of frequency in {C∗} is f ∗ j = f1 = 2. Then, it updates fj of each unverified category in the remaining unselected rules {R3, R4}, f4 = 1, f5 = 1, f6 = 2, f7 = 1. Obviously, C6 is the popular category and f6 = f ∗ j , {C∗}={C1, C6}. At this time, all the unverified rules are selected. The reader verifies C1 and C6 like CRCP. If the reader gets B(C1) = 1, B(C6) = 0, it can immediately conclude that B(R1) = 1, B(R4) = 1. After that, the reader only needs to verify the undetermined categories C3, C4, C5 in the unverified rules R2, R3, while ignoring other categories. Obviously, ECRCP only needs to verify a part of the related categories instead of all of them. 8 Performance evaluation We evaluate the performance of our proposed protocols by comparing them with the baseline protocols. We use the overall execution time as the performance metric. 8.1 Experiment setting We use the following parameters [14] to configure the simu￾lation: tag ID is 96 bits long. It takes 37.76μs for the reader to transmit one bit. Any two consecutive transmis￾sions are separated by a waiting time τ0 = 302μ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. It needs 321μs for the reader to detect an empty slot. In PRCP and BRCP, the tag can transmit one-bit information to announce its presence. The slot is about 321μs. The number of tags in the interrogation region (three-dimensional physical space) is set to 5000 at most. 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. 8.2 Optimal values of α¯ and d Based on Fig. 4, when α¯ approaches to 4 and d approaches to 7, the execution time decreases. When α¯ is too small (α¯ = Fig. 4 Optimal values of α¯ and d 530 Mobile Netw Appl (2014) 19:524–533