Efficient Protocols for Rule Checking in RFID Systems Yafeng Yin,Lei Xie,Sanglu Lu,Daoxu Chen State Key Laboratory for Novel Software Technology,Nanjing University,China Email:yyf@dislab.nju.edu.cn,{Ixie,sanglu,cdx}@nju.edu.cn Abstract-With the rapid proliferation of RFID technologies, related to the tags'categories instead of the detail IDs.and RFID has been introduced to the applications like safety inspec- it is possible to quickly check the rules by exploring their tion and warehouse management.Conventionally a number of logical features.For example,if the alcohol is not detected in deployment rules are specified for these applications.This paper studies a practically important problem of rule checking over a the warehouse management,then the rule over the lighter and large set of RFID tags,i.e.,checking whether the specified rules the alcohol can be verified as satisfied immediately,no matter are satisfied according to the RFID tags within the monitoring whether the lighter exists.Besides.traditional slotted ALOHA- area.This rule checking function may need to be executed based solutions always try to reduce the collision slots,without frequently over a large number of tags and therefore should be made efficient in terms of execution time.Aiming to achieve sufficiently exploring the information from the collision slots. time efficiency,we propose two efficient protocols based on the In this paper,by effectively resolving the collision slots collision detection and the logical features of rules,respectively. and leveraging the rules'logical features for verification,we Simulation results indicate that our protocols achieve much better propose efficient rule checking protocols according to the performance than other solutions in terms of time efficiency. categories of tags,without the need of identifying tags one I.INTRODUCTION by one.While verifying all related rules in the applications, our protocols can dramatically reduce the overall execution With the rapid proliferation of RFID technologies,RFID time for rule checking. tags have been widely deployed into a variety of applications. We make the following contributions in this paper.(1)We In conventional applications,an RFID system typically con-study a practically important problem of rule checking over sists of one or several readers and a large number of tags. a large set of RFID tags,which is essential for a number Each tag is attached to a physical item and has a unique of RFID applications.(2)We propose an efficient protocol identification (ID)describing the item.The reader is used to for rule checking based on collision detection,which aims recognize the object by identifying its attached tag. at sufficiently exploring the information from the collision In recent years,RFID has been introduced to a number slots.Furthermore,we propose an enhanced protocol which of rule checking-based applications,e.g.,safety inspection leverages the rule's logical property to effectively simplify and warehouse management.In these applications,a set of the checking process.(3)To the best of our knowledge,this rules are specified over the deployment of the items (tags),is the first theoretical work to investigate the rule checking which vary from application to application.For example,in problem in RFID systems.While leveraging the physical and the warehouse management,the lighter and the alcohol should application layer's information,our solution conducts a cross- not be close to each other in consideration of safety,while the layer optimization to effectively achieve time efficiency. pillow core and pillowcase should be placed together,since II RELATED WORK they are matching products.In order to verify the rules in a specified area,we can reasonably adjust the reader's power to Previous research on RFID has focused on anti-collision a certain level.The objective is to check whether the rules are protocols,which can be categorized into tree-based [1][2] satisfied according to the detected information from tags in the and ALOHA-based ones [3][4].Tree-based protocols resolve scanning area.The checking function may need to be executed collisions by muting subsets of tags involved in a collision. frequently over a large number of tags and therefore should ALOHA-based protocols assign distinct transmission time slot be made efficient in terms of execution time.For example,in to each tag,and sequentially identify the tags.Most of the the airport,the security checking is frequently executed and existing work considers the collision slots unuseful and wastes each passenger cannot stand too much time.A straightforward the collision slots.However,the collision slot can be used to solution is to collect all the tag IDs from the scanning area, improve the RFID reading performance.In [5],the analog and then check the rules one by one based on the collected network coding is used to extract useful information from IDs.However,this approach is rather time-consuming due to collision slots to improve the reading throughput.Besides, the large number of tags deployed in the applications. Manchester coding technology can be used in RFID commu- Based on the above understanding,it is essential to pro- nications to detect the bit collision [6][7].In [8],Manchester vide a time-efficient solution for these rule checking-based coding is used to decode the tag identifier from the collision applications.We note that conventionally the rules are only bits with the known mask.In [9][10],Manchester coding is
Efficient Protocols for Rule Checking in RFID Systems Yafeng Yin, Lei Xie, Sanglu Lu, Daoxu Chen State Key Laboratory for Novel Software Technology, Nanjing University, China Email: yyf@dislab.nju.edu.cn, {lxie, sanglu, cdx}@nju.edu.cn Abstract—With the rapid proliferation of RFID technologies, RFID has been introduced to the applications like safety inspection and warehouse management. Conventionally a number of deployment rules are specified for these applications. This paper studies a practically important problem of rule checking over a large set of RFID tags, i.e., checking whether the specified rules are satisfied according to the RFID tags within the monitoring area. This rule checking function may need to be executed frequently over a large number of tags and therefore should be made efficient in terms of execution time. Aiming to achieve time efficiency, we propose two efficient protocols based on the collision detection and the logical features of rules, respectively. Simulation results indicate that our protocols achieve much better performance than other solutions in terms of time efficiency. I. INTRODUCTION With the rapid proliferation of RFID technologies, RFID tags have been widely deployed into a variety of applications. In conventional applications, an RFID system typically consists of one or several readers and a large number of tags. Each tag is attached to a physical item and has a unique identification (ID) describing the item. The reader is used to recognize the object by identifying its attached tag. In recent years, RFID has been introduced to a number of rule checking-based applications, e.g., safety inspection and warehouse management. In these applications, a set of rules are specified over the deployment of the items (tags), which vary from application to application. For example, in the warehouse management, the lighter and the alcohol should not be close to each other in consideration of safety, while the pillow core and pillowcase should be placed together, since they are matching products. In order to verify the rules in a specified area, we can reasonably adjust the reader’s power to a certain level. The objective is to check whether the rules are satisfied according to the detected information from tags in the scanning area. The checking function may need to be executed frequently over a large number of tags and therefore should be made efficient in terms of execution time. For example, in the airport, the security checking is frequently executed and each passenger cannot stand too much time. A straightforward solution is to collect all the tag IDs from the scanning area, and then check the rules one by one based on the collected IDs. However, this approach is rather time-consuming due to the large number of tags deployed in the applications. Based on the above understanding, it is essential to provide a time-efficient solution for these rule checking-based applications. We note that conventionally the rules are only related to the tags’ categories instead of the detail IDs, and it is possible to quickly check the rules by exploring their logical features. For example, if the alcohol is not detected in the warehouse management, then the rule over the lighter and the alcohol can be verified as satisfied immediately, no matter whether the lighter exists. Besides, traditional slotted ALOHAbased solutions always try to reduce the collision slots, without sufficiently exploring the information from the collision slots. In this paper, by effectively resolving the collision slots and leveraging the rules’ logical features for verification, we propose efficient rule checking protocols according to the categories of tags, without the need of identifying tags one by one. While verifying all related rules in the applications, our protocols can dramatically reduce the overall execution time for rule checking. We make the following contributions in this paper. (1) We study a practically important problem of rule checking over a large set of RFID tags, which is essential for a number of RFID applications. (2) We propose an efficient protocol for rule checking based on collision detection, which aims at sufficiently exploring the information from the collision slots. Furthermore, we propose an enhanced protocol which leverages the rule’s logical property to effectively simplify the checking process. (3) To the best of our knowledge, this is the first theoretical work to investigate the rule checking problem in RFID systems. While leveraging the physical and application layer’s information, our solution conducts a crosslayer optimization to effectively achieve time efficiency. II. RELATED WORK Previous research on RFID has focused on anti-collision protocols, which can be categorized into tree-based [1][2] and ALOHA-based ones [3][4]. Tree-based protocols resolve collisions by muting subsets of tags involved in a collision. ALOHA-based protocols assign distinct transmission time slot to each tag, and sequentially identify the tags. Most of the existing work considers the collision slots unuseful and wastes the collision slots. However, the collision slot can be used to improve the RFID reading performance. In [5], the analog network coding is used to extract useful information from collision slots to improve the reading throughput. Besides, Manchester coding technology can be used in RFID communications to detect the bit collision [6][7]. In [8], Manchester coding is used to decode the tag identifier from the collision bits with the known mask. In [9][10], Manchester coding is
used to extract the information from collision slots to enhance be used to accurately detect the bit collision [6][7][9].as the identification efficiency.Instead of identifying all RFID shown in Fig.1.When tagl and tag2 transmit IDs to the tags,Zheng et al.[11]propose a two-phase approximation reader simultaneously in a slot,the falling edge transition protocol for fast tag searching in large-scale RFID systems, and the rising edge transition cancel each other out,leading which significantly improves the searching efficiency. to no transition in a received bit,such as bit3 and bit6. Being different from the related work.our research focuses The corresponding bit is a collision bit.Therefore,when on verifying the categories of the rules.We aim to resolve the two tags both send '0'(or '1'),the reader is able to the collision slots and leverage the rules'logical features recover the bit as '0'(or '1').When a 0'and a '1'are for verification in the scanning area.In order to resolve transmitted simultaneously,the reader detects a collision bit the collision slots,we will use the bit collision detection x.We represent the above conclusion as follows,0+0 =0, technology based on Manchester coding. 1+11,0+1 =x (1+0=x).Furthermore,if there are III.PRELIMINARY more than two tags responding simultaneously in a slot,only A.Synchronization when all the tags transmit '0'(or '1'),the reader can recover the bit '0'(or '1').Otherwise,the reader detects a collision Before checking the rules,we should get the responses from tags.As a popular ID-collection protocol conforming bit x.We represent the conclusion as follows,0+...+0=0 to EPC-CIG2,frame slotted ALOHA protocol wastes the (all the tags send 0'),1+...+1 1 (all the tags send '1'), collision slot.which is considered to be useless.However.if 0+...+1 =x (some tags send 0'and some tags send '1' the tags'responses are synchronized in a slot,we can resolve to the reader).In order to decode the bits in a slot,current the collision slot to get the tags'categories.Furthermore,if experimental platforms like USRP can be used [15],which is able to achieve the bit-level identification (0.1.x). the bit-level synchronization is achieved,then each bit of the responses can be utilized to resolve the collision slot. Tag1: 10011111 In RFID systems,each tag communicates with the reader in a single hop way.The transmissions can be synchronized by the reader's signal [12].According to EPC-C1G2 standard 1011101 [13],the reader sends Ouery command to start an inventory round.Then each tag selects a slot to respond,the beginning of each slot is indicated by OueryRep or QueryAdjust mes- Data recei by the Reade sages.Therefore,the tags responding in the same slot can be 1 11 synchronized through OueryRep or QueryAdjust. In RFID systems,due to the limitation of the reader's Fig.1.Bit collision detection in Manchester code power,the effective scanning range is limited.For example, IV.PROBLEM FORMULATION the effective range of Alien 9611 antenna is limited to 5- In our problem,we assume that each tag has a category ID 6 meters.The time delay difference between tags caused to denote the tag's category and the category ID is the prefix by the difference of their distances to the antenna is less thanx0.02us.When a tag receives the reader's of tag ID.In order to efficiently get the category IDs,we will utilize the collision slots based on Manchester coding command,it'will respond in a very short time.When the rate from a tag to the reader is 53Kb/s,it takes 18.88us for the tag Without loss of generality,we assume that a feasible bit- level synchronization can be achieved,which can be used to to transmit one bit.The maximum time delay difference is less recover the category IDs from the mixed signal in a slot.In our than 0.02us,which can be neglected compared to 18.88us. Therefore,we consider that the tags responding in the same rule checking problem,we check the rules based on the tag's category ID.We use R =[R1,...,Ri,...,Rm}to represent slot are synchronized.Moreover,the tags has the probability to achieve bit-level synchronization,which is essential to recover the rules.The category IDs in the rules are formulated as the useful bits of the tags'responses from the mixed signal. C={C1,...,Ci,...,Cn}.In real application,there often exist some constraint rules in the categories.For example,orange As the tag's manufacturing technology is improved,we believe juice and apple juice both belong to fruit juice,it may be that a feasible bit-level synchronization can be achieved with enough to have any one of them in the warehouse.The type of more precise clock synchronization. the relationship is called OR.While pillow core and pillowcase B.Manchester Coding should be put together,their relationship's type is called AND In RFID systems,each tag encodes the backscattered data The lighter and the alcohol should not be close to each before sending it.In EPC-C1G2 standard,FMO coding and other for the sake of safety,their relationship's type is called Miller coding are used.However,the two codes are difficult EXCLUSIVE.Taking the actual situation into consideration, to be used for detecting bit collision.In this paper,we use we classify the rules into three basic types. Manchester coding to achieve bit collision detection.Manch- 1)OR:At least one category must exist.We represent the ester coding has been used in Type B of ISO 18000-6 [14].rule as Ri=CiVCk.We list two categories here.Actually, In Manchester code,a falling edge transition represents there can be more categories in a rule.The rule's Boolean 1,a rising edge transition represents 0.The transitions can value B(Ri)is false (B(Ri)=0)only when both Ci and Ck
used to extract the information from collision slots to enhance the identification efficiency. Instead of identifying all RFID tags, Zheng et al. [11] propose a two-phase approximation protocol for fast tag searching in large-scale RFID systems, which significantly improves the searching efficiency. Being different from the related work, our research focuses on verifying the categories of the rules. We aim to resolve the collision slots and leverage the rules’ logical features for verification in the scanning area. In order to resolve the collision slots, we will use the bit collision detection technology based on Manchester coding. III. PRELIMINARY A. Synchronization Before checking the rules, we should get the responses from tags. As a popular ID-collection protocol conforming to EPC-C1G2, frame slotted ALOHA protocol wastes the collision slot, which is considered to be useless. However, if the tags’ responses are synchronized in a slot, we can resolve the collision slot to get the tags’ categories. Furthermore, if the bit-level synchronization is achieved, then each bit of the responses can be utilized to resolve the collision slot. In RFID systems, each tag communicates with the reader in a single hop way. The transmissions can be synchronized by the reader’s signal [12]. According to EPC-C1G2 standard [13], the reader sends Query command to start an inventory round. Then each tag selects a slot to respond, the beginning of each slot is indicated by QueryRep or QueryAdjust messages. Therefore, the tags responding in the same slot can be synchronized through QueryRep or QueryAdjust. In RFID systems, due to the limitation of the reader’s power, the effective scanning range is limited. For example, the effective range of Alien 9611 antenna is limited to 5- 6 meters. The time delay difference between tags caused by the difference of their distances to the antenna is less than 6m 3×108m/s = 0.02μs. When a tag receives the reader’s command, it will respond in a very short time. When the rate from a tag to the reader is 53Kb/s, it takes 18.88μs for the tag to transmit one bit. The maximum time delay difference is less than 0.02μs, which can be neglected compared to 18.88μs. Therefore, we consider that the tags responding in the same slot are synchronized. Moreover, the tags has the probability to achieve bit-level synchronization, which is essential to recover the useful bits of the tags’ responses from the mixed signal. As the tag’s manufacturing technology is improved, we believe that a feasible bit-level synchronization can be achieved with more precise clock synchronization. B. Manchester Coding In RFID systems, each tag encodes the backscattered data before sending it. In EPC-C1G2 standard, FM0 coding and Miller coding are used. However, the two codes are difficult to be used for detecting bit collision. In this paper, we use Manchester coding to achieve bit collision detection. Manchester coding has been used in Type B of ISO 18000-6 [14]. In Manchester code, a falling edge transition represents 1, a rising edge transition represents 0. The transitions can be used to accurately detect the bit collision [6][7][9], as shown in Fig. 1. When tag1 and tag2 transmit IDs to the reader simultaneously in a slot, the falling edge transition and the rising edge transition cancel each other out, leading to no transition in a received bit, such as bit3 and bit6. The corresponding bit is a collision bit. Therefore, when the two tags both send ‘0’ (or ‘1’), the reader is able to recover the bit as ‘0’ (or ‘1’). When a ‘0’ and a ‘1’ are transmitted simultaneously, the reader detects a collision bit x. We represent the above conclusion as follows, 0+0=0, 1+1=1, 0+1= x (1+0= x). Furthermore, if there are more than two tags responding simultaneously in a slot, only when all the tags transmit ‘0’ (or ‘1’), the reader can recover the bit ‘0’ (or ‘1’). Otherwise, the reader detects a collision bit x. We represent the conclusion as follows, 0 + ... +0=0 (all the tags send ‘0’), 1 + ... +1=1 (all the tags send ‘1’), 0 + ... +1= x (some tags send ‘0’ and some tags send ‘1’ to the reader). In order to decode the bits in a slot, current experimental platforms like USRP can be used [15], which is able to achieve the bit-level identification (0, 1, x). 1 Data Received by the Reader 001 1111 1011 1011 10x1 1x11 Tag1: 10011111 Tag2: 10111011 + Fig. 1. Bit collision detection in Manchester code IV. PROBLEM FORMULATION In our problem, we assume that each tag has a category ID to denote the tag’s category and the category ID is the prefix of tag ID. In order to efficiently get the category IDs, we will utilize the collision slots based on Manchester coding. Without loss of generality, we assume that a feasible bitlevel synchronization can be achieved, which can be used to recover the category IDs from the mixed signal in a slot. In our rule checking problem, we check the rules based on the tag’s category ID. We use R = {R1, ..., Ri, ..., Rm} to represent the rules. The category IDs in the rules are formulated as C = {C1, ..., Cj , ..., Cn}. In real application, there often exist some constraint rules in the categories. For example, orange juice and apple juice both belong to fruit juice, it may be enough to have any one of them in the warehouse. The type of the relationship is called OR. While pillow core and pillowcase should be put together, their relationship’s type is called AND. The lighter and the alcohol should not be close to each other for the sake of safety, their relationship’s type is called EXCLUSIVE. Taking the actual situation into consideration, we classify the rules into three basic types. 1) OR: At least one category must exist. We represent the rule as Ri = Cj ∨ Ck. We list two categories here. Actually, there can be more categories in a rule. The rule’s Boolean value B(Ri) is false (B(Ri)=0) only when both Cj and Ck
are outside the scanning area,which are expressed as B(Ci)=obtains the related category IDs from the responses to check 0 and B(Ck)=0.Otherwise,B(Ri)is true (B(Ri)=1). the rules.In [11],a similar protocol CATS is proposed for 2)AND:All the categories must exist together.We rep- fast tag searching in large-scale RFID systems with multiple resent the rule as Ri CiA C&.The rule's Boolean value readers rather than a mobile reader used in our system. B(Ri)=1 only when both Ci and C&are in the scanning D.Analysis area,B(Ci)=1 and B(Ck)=1.Otherwise,B(Ri)=0. 3)EXCLUSIVE:The categories should not be put together. In the baseline protocols,ARCP collects the categories in We represent it as Ri=(CjA Ck).It is essentially the the reader's scanning area,which wastes time in collecting the same as the AND rule in consideration of logical relation. unrelated tag IDs.PRCP collects the categories in the rules, However,considering the actual situation in applications,we which wastes time in polling some nonexistent category IDs do not merge them.The rule's Boolean value B(Ri)=0 only specified by the rules.BRCP uses the Bloom filter to filter when B(Ci)=1 and B(Ck)=1.Otherwise,B(Ri)=1. unrelated categories,and gets the responses from tags like a However,if a rule is a hybrid rule,we can split it into virtual Bloom filter.However.the unit of the virtual Bloom subrules until each subrule belongs to one of the basic types. filter is a slot instead of a bit,which is rather time consuming, For example,a hybrid rule Ri=(CjA Ck)V(CuVC).We leading to the low efficiency of BRCP. get the subrules,CiA Ck.and Cu VCv.Then,B(Ri)can be VI.COLLISION DETECTION BASED RULE CHECKING obtained from B(CiA Ck)and B(Cu VC). PROTOCOL Due to the large number of tags and the large number A.Motivation of rules,traditional solutions are rather time consuming for Based on the above analysis,we propose a Collision de- collecting the tag IDs in the scanning area.Therefore,it tection based Rule Checking Protocol(CRCP).It focuses on is essential to propose a time-efficient solution for the rule resolving the collision slots based on Manchester code,which checking-based applications,which aims at minimizing the can be used for bit collision detection according to section III. execution time T for checking all the rules. In CRCP,if a categories [C1,C2,...,Ca}should select V.BASELINE PROTOCOLS the same slot to respond,the reader gets an a-collision slot. A.Frame Slotted ALOHA Based Rule Checking Protocol We use MM to represent the mixed signal of Mj. M;and M are Manchester code of d bits.M;is the short term The frame slotted ALOHA based Rule Checking Protocol of Ci to reduce transmission time.If a =2,M =100101, (ARCP)collects all the tag IDs in the scanning area and extracts the category IDs from them.In ARCP.the reader M=010111,henM=∑=14=100101+010111= first broadcasts a request message,which specifies the size of xx01x1.M is the expected code to be received by the reader. The reader decodes Mj from M by comparing the received the following frame.Then each tag individually and randomly selects one slot to transmit its ID.If only one tag replies in a code with the expected one.If the received code M is 010111, slot,the reader can successfully receive the tag ID.If multiple the reader can confirm that only C2 gives the response M2. Because the first bit in M is x,while the first bit in M,is 0. tags respond simultaneously,a collision occurs,the involved tags will be acknowledged to restart in the next frame.The It indicates that C is outside the scanning area,while C2 is in the area.After that,the reader uses the decoded category similar process repeats until no tags respond in the frame.Then IDs to check the rules. the reader extracts the category IDs and checks the rules. B.Polling Based Rule Checking Protocol 101011011010101 We call the categories in the rules as related categories. The Polling based Rule Checking Protocol(PRCP)checks the Mobile existence of related categories in the scanning area.In PRCP, Reader .h.icJ. h.(cs) the reader broadcasts a category ID and waits for the response. Expected Code M 011110 null xoxoxx When a tag's category ID is equal to the reader's request one, Received Code M. 011110 null xOxxx the tag will give a short response.Then,the reader gets a M, 100101 101010 nonempty slot.Otherwise,the reader gets an empty slot.The M 001111 reader sends out all the related category IDs one by one to M detect the existence of these category IDs.When the polling Ms0111i0 =】 a=4 process terminates,the reader determines each rule's Boolean value based on the tags'responses. Fig.2.Collision detection based rule checking protocol C.Bloom Filter Based Rule Checking Protocol B.Protocol Overview Bloom filter based Rule Checking Protocol (BRCP)uses the In CRCP,the reader sends the request in the form of Bloom filter to inform the related categories to give responses. Bloom filter,as shown in Fig.2.It selects k hash functions Each one of the related tags in the scanning area uses k hash h1,h2,...,hk and c category IDs C1,C2,...,Ce to construct functions to select k slots to give a short response.Then the the Bloom filter with length l.It maps each C;into k bits reader gets the tags'responses as a virtual Bloom filter and at positions h(Ci)mod I,h2(Ci)mod l,...,hk(Ci)mod I
are outside the scanning area, which are expressed as B(Cj ) = 0 and B(Ck)=0. Otherwise, B(Ri) is true (B(Ri)=1). 2) AND: All the categories must exist together. We represent the rule as Ri = Cj ∧ Ck. The rule’s Boolean value B(Ri)=1 only when both Cj and Ck are in the scanning area, B(Cj )=1 and B(Ck)=1. Otherwise, B(Ri)=0. 3) EXCLUSIVE: The categories should not be put together. We represent it as Ri = ¬(Cj ∧ Ck). It is essentially the same as the AND rule in consideration of logical relation. However, considering the actual situation in applications, we do not merge them. The rule’s Boolean value B(Ri)=0 only when B(Cj )=1 and B(Ck)=1. Otherwise, B(Ri)=1. However, if a rule is a hybrid rule, we can split it into subrules until each subrule belongs to one of the basic types. For example, a hybrid rule Ri = (Cj ∧ Ck) ∨ (Cu ∨ Cv). We get the subrules, Cj ∧ Ck and Cu ∨ Cv. Then, B(Ri) can be obtained from B(Cj ∧ Ck) and B(Cu ∨ Cv). Due to the large number of tags and the large number of rules, traditional solutions are rather time consuming for collecting the tag IDs in the scanning area. Therefore, it is essential to propose a time-efficient solution for the rule checking-based applications, which aims at minimizing the execution time T for checking all the rules. V. BASELINE PROTOCOLS A. Frame Slotted ALOHA Based Rule Checking Protocol The frame slotted ALOHA based Rule Checking Protocol (ARCP) collects all the tag IDs in the scanning area and extracts the category IDs from them. In ARCP, the reader first broadcasts a request message, which specifies the size of the following frame. Then each tag individually and randomly selects one slot to transmit its ID. If only one tag replies in a slot, the reader can successfully receive the tag ID. If multiple tags respond simultaneously, a collision occurs, the involved tags will be acknowledged to restart in the next frame. The similar process repeats until no tags respond in the frame. Then the reader extracts the category IDs and checks the rules. B. Polling Based Rule Checking Protocol We call the categories in the rules as related categories. The Polling based Rule Checking Protocol (PRCP) checks the existence of related categories in the scanning area. In PRCP, the reader broadcasts a category ID and waits for the response. When a tag’s category ID is equal to the reader’s request one, the tag will give a short response. Then, the reader gets a nonempty slot. Otherwise, the reader gets an empty slot. The reader sends out all the related category IDs one by one to detect the existence of these category IDs. When the polling process terminates, the reader determines each rule’s Boolean value based on the tags’ responses. C. Bloom Filter Based Rule Checking Protocol Bloom filter based Rule Checking Protocol (BRCP) uses the Bloom filter to inform the related categories to give responses. Each one of the related tags in the scanning area uses k hash functions to select k slots to give a short response. Then the reader gets the tags’ responses as a virtual Bloom filter and obtains the related category IDs from the responses to check the rules. In [11], a similar protocol CATS is proposed for fast tag searching in large-scale RFID systems with multiple readers rather than a mobile reader used in our system. D. Analysis In the baseline protocols, ARCP collects the categories in the reader’s scanning area, which wastes time in collecting the unrelated tag IDs. PRCP collects the categories in the rules, which wastes time in polling some nonexistent category IDs specified by the rules. BRCP uses the Bloom filter to filter unrelated categories, and gets the responses from tags like a virtual Bloom filter. However, the unit of the virtual Bloom filter is a slot instead of a bit, which is rather time consuming, leading to the low efficiency of BRCP. VI. COLLISION DETECTION BASED RULE CHECKING PROTOCOL A. Motivation Based on the above analysis, we propose a Collision detection based Rule Checking Protocol (CRCP). It focuses on resolving the collision slots based on Manchester code, which can be used for bit collision detection according to section III. In CRCP, if α categories {C1, C2,...,Cα} should select the same slot to respond, the reader gets an α – collision slot. We use M = α j=1 Mj to represent the mixed signal of Mj . Mj and M are Manchester code of d bits. Mj is the short term of Cj to reduce transmission time. If α = 2, M1 = 100101, M2 = 010111, then M = 2 j=1 Mj = 100101 + 010111 = xx01x1. M is the expected code to be received by the reader. The reader decodes Mj from M by comparing the received code with the expected one. If the received code Mr is 010111, the reader can confirm that only C2 gives the response M2. Because the first bit in M is x, while the first bit in Mr is 0. It indicates that C1 is outside the scanning area, while C2 is in the area. After that, the reader uses the decoded category IDs to check the rules. 011110 null x0xxxx . . . 100101 101010 001111 D 1 hr(c1),hr(c2), hr(c3),hr(c4) 110011 Received Code Mr Expected Code M xxxxxx null D 4 011110 M1 M2 M3 M4 1 1 0 1 0 1 1 0 1 1 0 1 Bloom filter Mobile Reader 0 1 0 1 C1 C2 C3 C4 C5 C9 hr(c5) M5 011110 Fig. 2. Collision detection based rule checking protocol B. Protocol Overview In CRCP, the reader sends the request in the form of Bloom filter, as shown in Fig. 2. It selects k hash functions h1, h2,...,hk and c category IDs C1, C2,...,Cc to construct the Bloom filter with length l. It maps each Cj into k bits at positions h1(Cj ) mod l, h2(Cj ) mod l, ..., hk(Cj ) mod l
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(C)mod 16(i [1,3],j[1,5])to construct Mi 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 with
and 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) 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 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
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 XxxXX 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 001111 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,a 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 pbo 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 Algorithm2.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 the
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 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 consideration 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
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 adjust
correlated 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 category 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
12 1216202428 0099 d (bit) 8 24 4 1500200025003000350040004500500 0 n scannng area Fig.3.Optimal values of a and d. Fig.4.Execution time under different length of Fig.5.Execution time under different number of category ID Ci. tags in scanning area. 500 10 0 100 250 300 Number of rles Fig.6.Execution time under different number of Fig.7.Number of verified category IDs under Fig.8.Accuracy under different number of rules. rules. different number of rules. the length of the Bloom filter and the number of hash functions [5]M.Zhang.T.Li,S.Chen,and B.Li,"Using analog network coding used in the Bloom filter to meet the requirement. to improve the RFID reading throughput."in IEEE ICDCS.2010.pp. 547C556. IX.CONCLUSION (6]H.Ning,Y.CongZ.-Q.Xu,T.Hong,J.-C.Zhao,and Y.Zhang,"Perfor- In this paper,we investigate the rule checking problem mance Evaluation of RFID Anti-Collision Algorithm with FPGA Imple- mentation."in 21st International Conference on Advanced Information in RFID systems.We present two efficient protocols,one Networking and Applications Workshops,May 2007. is CRCP,it improves the time efficiency by resolving the [7]M.Alotaibi,KS.Bialkowski,and A.Postula,"A Signal Strength Based collision slots.The other one is ECRCP,it combines the Tag Estimation Technique for RFID Systems,"in 2010 IEEE Internation- al Conference on RFID-Technology and Applications (RFID-TA),June collision detection and the rules'logical features to achieve the 2010. time efficiency.Based on the performance evaluation,CRCP [8]T.Lim,T.Li,and S.Yeo,"A cross-layer framework for privacy enhance- and ECRCP have better performance.Besides,the simulation ment in RFID systems,"Pervasive and Mobile Computing,Vol.4,no.6, pp.889-905,December 2008. results show that ECRCP outperforms all the other solutions. [9]L.Liu,Z.Xie,J.Xi,and S.Lai,"An Improved Anti-collision Algorithm ACKNOWLEDGEMENT in RFID System,"in Proc.of 2nd Interational Conference on Mobile Technology,Applications and Systems,pp.15-17,2005. This work is partially supported by the National Ba- [10]SS.Kim,YH.Kim,SJ.Lee,and KS.Ahn,"An Improved Anti Collision sic Research Program of China (973)under Grant No. Algorithm using Parity Bit in RFID System,"in Proc.of 7th IEEE Internation Symposium,pp.224-227.2008. 2009CB320705:the National Natural Science Foundation [11]Y.Zheng,and M.Li,"Fast Tag Searching Protocol for Large-Scale RFID of China under Grant No.61100196.61073028.61021062: Systems,"in 19th IEEE International Conference on Network Protocols (/CNP).October 2011. the JiangSu Natural Science Foundation under Grant No. [12]H.Yue,C.Zhang.M.Pan,Y.Fang,and S.Chen,"A Time-efficient BK2011559 Information Collection Protocol for Large-scale RFID Systems,"in Pro- REFERENCES ceedings IEEE INFOCOM,2012. [13]EPC Radio Frequency Identify Protocols Class-1 Generation-2 UHF [1]J.Myung.W.Lee,and S.Jaideep,"Adaptive binary splitting for efficient RFID Protocol for Communications at 860 MHz-916 MHz Version rfid tag anti-collision,"IEEE Communications Letters,vol.10.no.3.pp. 1.2.0 144-146.2006. [14]"Information Technology Automatic Identification And Data Capture [2]L.Pan and H.Wu,"Smart Trend-Traversal:A Low Delay and Energy Tag Techniques-Radio Frequency Identification For Item Management Air Arbitration Protocol for Large RFID Systems,"in Proc.of INFOCOM. Interface.Part 6.Parameters for Air interface communications at 860- mini-conference,2009. 960 MHZ,"ed:Standard ISO 18000-6.2003. [3]B.Sheng,C.C.Tan,Q.Li,and W.Mao,"Finding popular categoried [15]J.Wang,H.Hassanieh,D.Katabi,and P.Indyk,"Efficient and Reliable for RFID tags,"in Proc.of ACM Mobihoc,2008. Low-Power Backscatter Networks,"ACM S/GCOMM Computer Commu- [4]L.Xie,B.Sheng.C.C.Tan,H.Han,Q.Li and D.Chen,"Efficient tag nicarion Review,Vol.42.no.4,pp.61-72.October 2012. identification in mobile RFID systems,"in Proc.of INFOCOM,2010
0 4 8 12 16 20 24 28 32 0 4 8 12 16 20 24 28 32 0 10 20 30 40 ,7 d (bit) Execution time (sec) (,7=4 , d=7) Fig. 3. Optimal values of α¯ and d. 16 24 32 40 48 56 64 0 2 4 6 8 10 12 14 16 18 20 Length of category ID (bits) Execution Time (sec) ARCP PRCP BRCP CRCP ECRCP Fig. 4. Execution time under different length of category ID Cj . 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 0 5 10 15 20 25 30 Number of tags in scanning area Execution Time (sec) ARCP PRCP BRCP CRCP ECRCP Fig. 5. Execution time under different number of tags in scanning area. 50 100 150 200 250 300 350 400 450 500 0 5 10 15 20 25 30 Number of rules Execution Time (sec) ARCP PRCP BRCP CRCP ECRCP Fig. 6. Execution time under different number of rules. 50 100 150 200 250 300 0 500 1000 1500 2000 2500 Number of rules Number of category IDs verified in the protocol ARCP PRCP BRCP CRCP ECRCP Fig. 7. Number of verified category IDs under different number of rules. 50 100 150 200 250 300 0 10 20 30 40 50 60 70 80 90 100 Number of rules Accuracy of checking the rules (%) ARCP PRCP BRCP CRCP ECRCP Fig. 8. Accuracy under different number of rules. the length of the Bloom filter and the number of hash functions used in the Bloom filter to meet the requirement. IX. CONCLUSION In this paper, we investigate the rule checking problem in RFID systems. We present two efficient protocols, one is CRCP, it improves the time efficiency by resolving the collision slots. The other one is ECRCP, it combines the collision detection and the rules’ logical features to achieve the time efficiency. Based on the performance evaluation, CRCP and ECRCP have better performance. Besides, the simulation results show that ECRCP outperforms all the other solutions. ACKNOWLEDGEMENT This work is partially supported by the National Basic Research Program of China (973) under Grant No. 2009CB320705; the National Natural Science Foundation of China under Grant No. 61100196, 61073028, 61021062; the JiangSu Natural Science Foundation under Grant No. BK2011559. REFERENCES [1] J. Myung, W. Lee, and S. Jaideep, “Adaptive binary splitting for efficient rfid tag anti-collision,” IEEE Communications Letters, vol. 10, no. 3, pp. 144-146, 2006. [2] L. Pan and H. Wu, “Smart Trend-Traversal: A Low Delay and Energy Tag Arbitration Protocol for Large RFID Systems,” in Proc. of INFOCOM, mini-conference, 2009. [3] B. Sheng, C. C. Tan, Q. Li, and W. Mao, “Finding popular categoried for RFID tags,” in Proc. of ACM Mobihoc, 2008. [4] L. Xie, B. Sheng, C. C. Tan, H. Han, Q. Li and D. Chen, “Efficient tag identification in mobile RFID systems,” in Proc. of INFOCOM, 2010. [5] M. Zhang, T. Li, S. Chen, and B. Li, “Using analog network coding to improve the RFID reading throughput,” in IEEE ICDCS, 2010, pp. 547C556. [6] H. Ning, Y. CongZ.-Q. Xu, T. Hong, J.-C. Zhao, and Y. Zhang, “Performance Evaluation of RFID Anti-Collision Algorithm with FPGA Implementation,“ in 21st International Conference on Advanced Information Networking and Applications Workshops, May 2007. [7] M. Alotaibi, KS. Bialkowski, and A. Postula, “A Signal Strength Based Tag Estimation Technique for RFID Systems,“ in 2010 IEEE International Conference on RFID-Technology and Applications (RFID-TA), June 2010. [8] T. Lim, T. Li, and S. Yeo, “A cross-layer framework for privacy enhancement in RFID systems,“ Pervasive and Mobile Computing, Vol. 4, no. 6, pp. 889-905, December 2008. [9] L. Liu, Z. Xie, J. Xi, and S. Lai, “An Improved Anti-collision Algorithm in RFID System,” in Proc. of 2nd International Conference on Mobile Technology, Applications and Systems, pp. 15-17, 2005. [10] SS. Kim, YH. Kim, SJ. Lee, and KS. Ahn, “An Improved Anti Collision Algorithm using Parity Bit in RFID System,” in Proc. of 7th IEEE Internation Symposium, pp.224-227, 2008. [11] Y. Zheng, and M. Li, “Fast Tag Searching Protocol for Large-Scale RFID Systems,” in 19th IEEE International Conference on Network Protocols (ICNP), October 2011. [12] H. Yue, C. Zhang, M. Pan, Y. Fang, and S. Chen, “A Time-efficient Information Collection Protocol for Large-scale RFID Systems,” in Proceedings IEEE INFOCOM, 2012. [13] EPC Radio Frequency Identify Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz - 916 MHz Version 1.2.0. [14] “Information Technology Automatic Identification And Data Capture Techniques-Radio Frequency Identification For Item Management Air Interface. Part 6. Parameters for Air interface communications at 860- 960 MHZ,” ed: Standard ISO 18000-6, 2003. [15] J. Wang, H. Hassanieh, D. Katabi, and P. Indyk, “Efficient and Reliable Low-Power Backscatter Networks,” ACM SIGCOMM Computer Communication Review, Vol. 42, no. 4, pp.61-72, October 2012