Mobile Netw Appl(2014)19:524-533 D0I10.1007/s11036-014-0524-9 Check out the Rules:Towards Time-Efficient Rule Checking over RFID Tags Yafeng Yin.Lei Xie.Sanglu Lu Daoxu Chen Published online:20 July 2014 Springer Science+Business Media New York 2014 Abstract With the rapid proliferation of RFID technolo-or several readers and a large number of tags.Each tag is gies,RFID has been introduced to the applications like attached to a physical item and has a unique identification safety inspection and warehouse management.Convention- (ID)describing the item.The reader recognizes the object ally a number of deployment rules are specified for these by identifying its attached tag. applications.This paper studies a practically important Recently,RFID has been introduced to a number of problem of rule checking over RFID tags,i.e.,checking rule checking-based applications,e.g.,safety inspection and whether the specified rules are satisfied according to the warehouse management.In these applications,a set of RFID tags within the monitoring area.This rule checking rules are specified over the deployment of the items(tags), function may need to be executed frequently over a large which vary from application to application.For example,in number of tags and therefore should be made efficient in the chemical laboratory,as shown in Fig.la,when some terms of execution time.Aiming to achieve time efficiency. chemicals (eg.metal material and corrosive solution)come we respectively propose two protocols,CRCP and ECRCP. together,the chemical reaction occurs,which may cause CRCP works based on collision detection.while ECRCP an accident.Therefore,these objects should not be placed combines the collision detection and the logical features together.In the warehouse management,the lighter and the of the rules.Simulation results indicate that our protocols alcohol should not be close to each other in consideration achieve much better performance than other solutions in of safety,while the pillow core and the pillowcase should terms of time efficiency. be placed together,since they are matching products,as shown in Fig.Ib.In order to check the rules over a spec- Keywords RFID.Rule checking.Algorithm design. ified area,the reader can reasonably adjust its power to a Time-efficient.Optimization certain level.The objective is to check whether the rules are satisfied according to the detected information from tags in the scanning area.The rule checking function may need 1 Introduction to be executed frequently over a large number of tags and therefore should be made efficient in terms of execution With the development of RFID technologies,RFID tags time.For example,the security checking in the airport,as have been widely deployed into a variety of applications. shown in Fig.1c.A straightforward solution is to collect Conventionally,an RFID system typically consists of one all the tag IDs,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 Y.Yin.L.Xie ()S.Lu.D.Chen State Key Laboratory for Novel Software Technology, applications. Nanjing University,Nanjing,China Based on the above understanding,it is essential to pro- e-mail:lxie@nju.edu.cn vide a time-efficient solution for these rule checking-based Y.Yin applications.We note that conventionally the rules are only e-mail:yyf@dislab.nju.edu.cn related to the tags'categories instead of the detail IDs,and S.Lu it is possible to quickly check the rules by exploring their e-mail:sanglu@nju.edu.cn logical features.For example,if the alcohol is not detected D.Chen in the warehouse management,then the rule over the lighter e-mail:cdx@nju.edu.cn and the alcohol can be verified as satisfied immediately,no ②Springer
DOI 10.1007/s11036-014-0524-9 Check out the Rules: Towards Time-Efficient Rule Checking over RFID Tags Yafeng Yin · Lei Xie · Sanglu Lu · Daoxu Chen © Springer Science+Business Media New York 2014 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 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 respectively propose two protocols, CRCP and ECRCP. CRCP works based on collision detection, while ECRCP combines the collision detection and the logical features of the rules. Simulation results indicate that our protocols achieve much better performance than other solutions in terms of time efficiency. Keywords RFID · Rule checking · Algorithm design · Time-efficient · Optimization 1 Introduction With the development of RFID technologies, RFID tags have been widely deployed into a variety of applications. Conventionally, an RFID system typically consists of one Y. Yin · L. Xie () · S. Lu · D. Chen State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China e-mail: lxie@nju.edu.cn Y. Yin e-mail: yyf@dislab.nju.edu.cn S. Lu e-mail: sanglu@nju.edu.cn D. Chen e-mail: cdx@nju.edu.cn 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 recognizes the object by identifying its attached tag. Recently, 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 chemical laboratory, as shown in Fig. 1a, when some chemicals (eg. metal material and corrosive solution) come together, the chemical reaction occurs, which may cause an accident. Therefore, these objects should not be placed together. 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 the pillowcase should be placed together, since they are matching products, as shown in Fig. 1b. In order to check the rules over a specified area, the reader can reasonably adjust its 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 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. For example, the security checking in the airport, as shown in Fig. 1c. A straightforward solution is to collect all the tag IDs, and then check the rules one by one based on the collected IDs. However, this approach is rather timeconsuming 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 Published online: 20 July 2014 Mobile Netw Appl (2014) 19:524–533
Mobile Netw Appl (2014)19:524-533 525 (a)Chemical Laboratory (b)Warehouse Management (c)Security Checking Fig.1 Rule-checking based applications matter whether the lighter exists.In regard to the tag identifi- research shows that,analog network coding can be used to cation protocol,traditional slotted ALOHA-based solutions extract useful information from collision slots to improve always try to reduce the collision slots,without sufficiently the RFID reading throughput [3].In the collision slot,the exploring the information from the collision slots.In this the signals from multiple tags exhibit small offsets,which paper,by effectively resolving the collision slots and lever- are sufficiently small for decoding the collision slot [4]. aging the rules'logical features for verification,we propose Besides,Manchester coding technology can be used in efficient rule checking protocols based on the categories of RFID communications to detect the bit collision [5,6].In tags,without the need of identifying tags one by one.While [7].Manchester coding is used to decode the tag identifier verifying all related rules in the applications,our protocols from the collision bits with the known mask.In [8],Manch- can dramatically reduce the overall execution time for rule ester coding is used to extract the information from collision checking. slots to enhance the efficiency of identifying the tags. We make the following contributions in this paper. Instead of identifying all the tags,missing tag identifica- We study a practically important problem of rule check- tion only aims to find the missing tags [9,10].Opposite to ing over a large set of RFID tags,which is essential for a the purpose of finding missing tags,Zheng et al.propose a number of RFID applications,such as safety inspection, two-phase approximation protocol for fast tag searching in large-scale RFID systems [11].Rather than identifying the warehouse management,and so on. We propose a time-efficient protocol for rule checking tags,the RFID cardinality estimation protocols count the number of distinct tags [12,13].However,all the literature based on collision detection,which aims at sufficiently exploring the information from the collision slots.Fur- does not research the problem of rule checking over RFID tags thermore,we propose an enhanced protocol which com- Being different from the related work,our research bines the collision detection and the logical features of focuses on efficiently checking the rules based on the tags the rules.By leveraging the rule's logical property,the enhanced protocol can effectively simplify the checking categories.We resolve the collision slots to verify the tags' categories specified by the rules and leverage the rules'log- process. ical features for rule checking.In order to resolve the colli- To the best of our knowledge.this is the first theoretical work to investigate the rule checking problem in RFID sion slots,we will use the bit collision detection technology systems.While leveraging the information of the physi- based on Manchester coding. cal layer and the application layer,our solution conducts a cross-layer optimization to effectively achieve time 3 Preliminary efficiency. 3.1 Frame slotted ALOHA protocol 2 Related works Frame slotted ALOHA protocol (FSA)is a popular anti- collision protocol for tag identification.In FSA,the reader Previous research on RFID has focused on anti-collision first broadcasts the request message and specifies the fol- protocols,which can be categorized into tree-based pro- lowing frame size f.After receiving f,each tag selects tocols [1]and ALOHA-based ones [2].In ALOHA-based h(ID)mod f as its slot number.Here,h is a hash function, protocols,most of the existing work considers the colli- ID is tag ID.If no tag responds in a slot (empty slot),the sion slots unuseful and wastes the collision slots.Recent reader closes the slot immediately.If only one tag replies in Springer
Fig. 1 Rule-checking based applications matter whether the lighter exists. In regard to the tag identification protocol, traditional slotted ALOHA-based 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 based on 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. – 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, such as safety inspection, warehouse management, and so on. – We propose a time-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 combines the collision detection and the logical features of the rules. By leveraging the rule’s logical property, the enhanced protocol can effectively simplify the checking process. – To the best of our knowledge, this is the first theoretical work to investigate the rule checking problem in RFID systems. While leveraging the information of the physical layer and the application layer, our solution conducts a cross-layer optimization to effectively achieve time efficiency. 2 Related works Previous research on RFID has focused on anti-collision protocols, which can be categorized into tree-based protocols [1] and ALOHA-based ones [2]. In ALOHA-based protocols, most of the existing work considers the collision slots unuseful and wastes the collision slots. Recent research shows that, analog network coding can be used to extract useful information from collision slots to improve the RFID reading throughput [3]. In the collision slot, the the signals from multiple tags exhibit small offsets, which are sufficiently small for decoding the collision slot [4]. Besides, Manchester coding technology can be used in RFID communications to detect the bit collision [5, 6]. In [7], Manchester coding is used to decode the tag identifier from the collision bits with the known mask. In [8], Manchester coding is used to extract the information from collision slots to enhance the efficiency of identifying the tags. Instead of identifying all the tags, missing tag identification only aims to find the missing tags [9, 10]. Opposite to the purpose of finding missing tags, Zheng et al. propose a two-phase approximation protocol for fast tag searching in large-scale RFID systems [11]. Rather than identifying the tags, the RFID cardinality estimation protocols count the number of distinct tags [12, 13]. However, all the literature does not research the problem of rule checking over RFID tags. Being different from the related work, our research focuses on efficiently checking the rules based on the tags’ categories. We resolve the collision slots to verify the tags’ categories specified by the rules and leverage the rules’ logical features for rule checking. In order to resolve the collision slots, we will use the bit collision detection technology based on Manchester coding. 3 Preliminary 3.1 Frame slotted ALOHA protocol Frame slotted ALOHA protocol (FSA) is a popular anticollision protocol for tag identification. In FSA, the reader first broadcasts the request message and specifies the following frame size f . After receiving f , each tag selects h(ID) mod f as its slot number. Here, h is a hash function, ID is tag ID. If no tag responds in a slot (empty slot), the reader closes the slot immediately. If only one tag replies in Mobile Netw Appl (2014) 19:524–533 525
526 Mobile Netw Appl (2014)19:524-533 a slot(singleton slot),the reader successfully receives the Tag1: tag ID and sends an acknowledgement to the tag.The tag 10011111 will keep silent in the rest of the session.If multiple tags respond in the same slot (collision slot),a collision occurs, Tag2: and the involved tags will be acknowledged to restart in the 10111011 next frame.The reader repeats the above process until no tags respond. Data received by the Reade 3.2 Synchronization Fig.2 Bit collision detection in Manchester code As a popular ID-collection protocol conforming to EPC- C1G2 standard,FSA discards the collision slot.However. if the tags'responses are synchronized in a slot,we can to no transition in a received bit,such as bit3 and bit6.The resolve the collision slot to get the tags'responses.Further- corresponding bit is a collision bit.If there are more than more,if the bit-level synchronization is achieved,then each two tags responding simultaneously in a slot,only all the bit of the responses can be utilized to resolve the collision tags transmit '0'(or '1'),the reader can recover the bit'0' slot. In RFID systems,each tag communicates with the reader (or '1').Otherwise,the reader detects a collision bit x.We in a single hop way.The transmissions can be synchronized represent the conclusion as follows,0+...+0=0(all by the reader's signal [14].According to EPC-C1G2 stan- the tags send '0'),1 +...+11 (all the tags send '1'), dard [15],the tags responding in the same slot can be syn- 0+...+1 =x (some tags send '0'and some tags send '1'). In order to decode the bits in a slot,current experimental chronized through QueryRep or QueryAdjust.Besides,the effective scanning range in the passive RFID system is lim- platforms like USRP can be used [17],which can achieve ited(eg.5-6meters).The time delay difference between tags the bit-level identification (0,1,x). caused by the difference of their distances to the antenna is less thanx0.02us.When a tag receives the 4 Problem formulation 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 We assume that each tag has a category ID to denote the 18.88us for the tag to transmit one bit.The maximum time tag's category and the category ID is the prefix of tag delay difference is less than 0.02us,which can be neglected ID.In order to efficiently get the category IDs,we will compared to 18.88us.In regard to the physical-layer sig- utilize the collision slots based on Manchester coding.With- nals,the signals from multiple tags exhibit small offsets, out loss of generality,we assume that a feasible bit-level which are sufficiently small for decoding [4].Therefore,we synchronization can be achieved,which can be used to consider that the tags responding in the same slot are syn- recover the category IDs from the mixed signal in a slot. chronized.Moreover,the tags has the probability to achieve In our problem,we check the rules based on the tag's cat- bit-level synchronization,which is essential to recover the egory ID.We use R =(R1.....Ri.....Rm}to represent useful bits of the tags'responses from the mixed signal.As the rules.The category IDs in the rules are formulated as the tag's manufacturing technology is improved,we believe C=(C1.....Cj,..Cn).In real application,there often that a feasible bit-level synchronization can be achieved exist some constraint rules in the categories.For example, with more precise clock synchronization. orange juice and apple juice both belong to fruit juice,it may be enough to have any one of them in the warehouse.The 3.3 Manchester coding type of the relationship is called OR.While pillow core and pillowcase should be put together,their relationship's type In RFID systems,each tag encodes the backscattered data is called AND.The lighter and the alcohol should not be before sending it.In this paper,we use Manchester coding to close to each other for the sake of safety,their relationship's achieve bit collision detection.Manchester coding has been used in Type B of ISO 18000-6[16]. type is called EXCLUSIVE.Taking the actual situation into In Manchester code,a falling edge transition represents consideration,we classify the rules into three basic types. 1,a rising edge transition represents 0.The transitions can OR:At least one category must exist.We represent the be used to accurately detect the bit collision [5,6,8],as rule as Ri =CiVCk.We list two categories here.Actu- shown in Fig.2.When tagl and tag2 transmit IDs to the ally,there can be more categories in a rule.The rule's reader simultaneously in a slot,the falling edge transition Boolean value B(Ri)is false (B(R;)=0)only when and the rising edge transition cancel each other out,leading both C;and C&are outside the scanning area,which are ②Springer
a slot (singleton slot), the reader successfully receives the tag ID and sends an acknowledgement to the tag. The tag will keep silent in the rest of the session. If multiple tags respond in the same slot (collision slot), a collision occurs, and the involved tags will be acknowledged to restart in the next frame. The reader repeats the above process until no tags respond. 3.2 Synchronization As a popular ID-collection protocol conforming to EPCC1G2 standard, FSA discards the collision slot. However, if the tags’ responses are synchronized in a slot, we can resolve the collision slot to get the tags’ responses. 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 [14]. According to EPC-C1G2 standard [15], the tags responding in the same slot can be synchronized through QueryRep or QueryAdjust. Besides, the effective scanning range in the passive RFID system is limited (eg. 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. In regard to the physical-layer signals, the signals from multiple tags exhibit small offsets, which are sufficiently small for decoding [4]. 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. 3.3 Manchester coding In RFID systems, each tag encodes the backscattered data before sending it. In this paper, we use Manchester coding to achieve bit collision detection. Manchester coding has been used in Type B of ISO 18000-6 [16]. 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 [5, 6, 8], as shown in Fig. 2. 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 Fig. 2 Bit collision detection in Manchester code to no transition in a received bit, such as bit3 and bit6. The corresponding bit is a collision bit. If there are more than two tags responding simultaneously in a slot, only 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’). In order to decode the bits in a slot, current experimental platforms like USRP can be used [17], which can achieve the bit-level identification (0, 1, x). 4 Problem formulation 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 bit-level synchronization can be achieved, which can be used to recover the category IDs from the mixed signal in a slot. In our 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. – 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 526 Mobile Netw Appl (2014) 19:524–533
Mobile Netw Appl (2014)19:524-533 527 expressed as B(Cj)=0 and B(Ck)=0.Otherwise, Bloom filter to check the rules.In [111,a similar protocol B(Ri)is true (B(Ri)=1). CATS is proposed for fast tag searching in large-scale RFID AND:All the categories must exist together.We rep- systems. resent the rule as Ri=CiA C&.The rule's Boolean value B(Ri)=1 only when both Ci and C&are in the scanning area,B(Ci)=1 and B(Ck)=1.Otherwise, 6 Collision detection based rule checking protocol B(R)=0. EXCLUSIVE:The categories should not be put together. 6.1 Motivation We represent it as Ri =(CjA Ck).It is essen- tially the same as the AND rule in consideration of Based on the above analysis,we propose a Collision detec- logical relation.However,considering the actual situa- tion based Rule Checking Protocol (CRCP).It focuses on tion in applications,we do not merge them.The rule's resolving the collision slots based on Manchester code, Boolean value B(Ri)=0 only when B(Cj)=1 and which can be used for bit collision detection according to B(Ck)=1.Otherwise,B(Ri)=1. Section 3. In CRCP,if a categories (C1,C2....,Ca}should select However,if a rule is a hybrid rule,we can split it into the same slot to respond,the reader gets an a-collision subrules until each subrule belongs to one of the basic types. slot.We use M=Mj to represent the mixed signal For example,a hybrid rule Ri=(CiA Ck)V(Cu VCu).We of Mj.Mi and M are Manchester code of d bits.Mi is get the subrules,CjA Cx and Cu VCv.Then,B(Ri)can be the short term of Ci to reduce transmission time.If a=2. obtained from B(CjA Ck)and B(Cu VC). M1=100101,M2=01011L,then M=∑=1M)= Due to the large number of tags and rules,it is essential 100101 +010111 xx01x1.M is the expected code to to propose a time-efficient solution for the rule checking- be received by the reader.The reader decodes M;from M based applications,which aims at minimizing the execution by comparing the received code with the expected one.If time T for checking all the rules. the received code M,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 M,is 0.It indicates that CI is outside 5 Baseline protocols the scanning area,while C2 is in the area.After that,the reader uses the decoded category IDs to check the rules. 5.1 Frame slotted ALOHA based rule checking protocol (ARCP) 6.2 Protocol overview ARCP collects all the tag IDs in the scanning area,as In CRCP,the reader sends the request by Bloom filter.It described in Section 3.1.Then the reader extracts the cate- selects k hash functions h1,h2,...,hk and c category IDs gory IDs in the scanning area and checks the rules. C1,C2....,Ce to construct the Bloom filter with length 1, as shown in Fig.3.It maps each Ci into k bits at positions 5.2 Polling based rule checking protocol(PRCP) h(Cj)mod I,h2(Ci)mod 1,....hk(Ci)mod I and sets these bits to 1.When a tag receives the request,it checks We call the categories in the rules as related categories. the corresponding k bits.Only all the bits are 1,it gives PRCP checks the existence of related category IDs in the response.See Fig.3 for an example of k =3,I 16, scanning area by broadcasting them one by one.When a tag's category ID is equal to the reader's request one,it 92 will give a short response.The reader gets a nonempty slot. 1101o11o11o1oo3 Otherwise,it gets an empty slot.When the polling process terminates,the reader checks the rules based on the tags Mobile Reader responses. hdc:) h.(cal.h(ca Expected Code M 011110 null XxXXXX 5.3 Bloom filter based rule checking protocol(BRCP) Received Code M. 011110null x0xxxx M 100101 BRCP uses the Bloom filter to inform the related categories Mz 101010 M 001111 to respond.For the related tags in the scanning area,each Ma one uses k hash functions to select k slots to give a short M5011110 response.The reader gets the responses as a virtual Bloom a=1 a=4 filter and obtains the wanted category IDs from the virtual Fig.3 Collision detection based rule checking protocol Springer
expressed as B(Cj ) = 0 and B(Ck) = 0. Otherwise, B(Ri) is true (B(Ri) = 1). – 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. – 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 rules, it is essential to propose a time-efficient solution for the rule checkingbased applications, which aims at minimizing the execution time T for checking all the rules. 5 Baseline protocols 5.1 Frame slotted ALOHA based rule checking protocol (ARCP) ARCP collects all the tag IDs in the scanning area , as described in Section 3.1. Then the reader extracts the category IDs in the scanning area and checks the rules. 5.2 Polling based rule checking protocol (PRCP) We call the categories in the rules as related categories. PRCP checks the existence of related category IDs in the scanning area by broadcasting them one by one. When a tag’s category ID is equal to the reader’s request one, it will give a short response. The reader gets a nonempty slot. Otherwise, it gets an empty slot. When the polling process terminates, the reader checks the rules based on the tags’ responses. 5.3 Bloom filter based rule checking protocol (BRCP) BRCP uses the Bloom filter to inform the related categories to respond. For the related tags in the scanning area, each one uses k hash functions to select k slots to give a short response. The reader gets the responses as a virtual Bloom filter and obtains the wanted category IDs from the virtual Bloom filter to check the rules. In [11], a similar protocol CATS is proposed for fast tag searching in large-scale RFID systems. 6 Collision detection based rule checking protocol 6.1 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 3. 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. 6.2 Protocol overview In CRCP, the reader sends the request by Bloom filter. It selects k hash functions h1, h2,...,hk and c category IDs C1, C2,...,Cc to construct the Bloom filter with length l, as shown in Fig. 3. 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 checks the corresponding k bits. Only all the bits are 1, it gives response. See Fig. 3 for an example of k = 3, l = 16, Fig. 3 Collision detection based rule checking protocol Mobile Netw Appl (2014) 19:524–533 527
528 Mobile Netw Appl (2014)19:524-533 the reader uses hi(Cj)mod 16 (i [1,3],j [1,5])to Algorithm 1 CRCP:Reader Side construct the Bloom filter.The tags in C1,C2,C3,C4.Cs Input:m rules {R1,R2,...,Rm,n related category pass the test and give responses,while the tags in C9 keep IDs C1,C2,...,Cn,frame size f silent.If a tag in Ci should give response in the following 2=0,9=0. while any related category is not verified do frame with size f,it uses a hash function h to select a slot Set g=0,and set c equal to the number of h(Ci)mod f.Then,it sends d bits Manchester code Mj. unverified related category IDs. Send the request Bloom filter. Here,Mi=h(Ci)mod (2d),h is a hash function. In a new frame,wait for the tags'responses. Because the reader knows the related categories and the for each slot iE [1,f]and g<c do if Manchester code cannot be recovered then hash functions,it can get the mapping relation of Cj and L Put these category IDs into set Mi.When getting the responses,the reader checks whether else each bit in the slot can be recovered from the mixed sig- Decode the a-collision slot. Get di new verified categories,g=g+qi. nal.If the bits cannot be recovered.it means the number of 22+日. tags responding in the slot is too large.Then the reader puts if Cardinality of C=n-z then the corresponding category IDs into the new set C',which L Verify the tags in C using probability pr. will be verified later.If the bits can be recovered success- Check the rules according to the verified categories Output:Checking result B(R1),B(R2),...,B(Rm ) fully,then the reader resolves the collision slots,as shown in Algorithm 1.In the frame received from tags,suppose that the reader is able to get qi new category IDs Ci.Cj,....Ck bit M(i)=x,while the received bit Mr(i)=0,then by decoding an a-collision slot.The reader decodes the the category Cj with the corresponding bit equivalent to collision slots one by one until it gets all the c related cate- 1 is outside the scanning area,B(Ci)=0.Besides,if gory IDs in the frame or the frame terminates.Then,it no =1,the category Ci with corresponding bit equivalent repeats the similar process.At last,the reader verify the to 0 must in the scanning area,B(Cj)=1.If M(i)=x category IDs in C'using probability pr.The reader broad- and Mr(i)=1,we can get the conclusion in the same way. casts an integer y [pr x Y1,Y is a large constant.Then the tag calculates the hash result hr(ID)mod Y,only if However,if the expected bit M(i)=1 and the received bit Mr(i)=x,then the category Cj with cor- hr(ID)mod Yy,the tag gives response.In this way, responding bit equivalent to 0 gives response,B(Ci)=1. there will be only a few number of tags (eg.1)in one cate- gory giving responses.Then,the reader can decode the If M(i)=x=1+0 and M,(i)=x.we can get category IDs.When all the related category IDs are verified, the reader will check the rules based on Section 4. Algorithm 2 Resolving an a-collision slot 6.3 Resolving the collision slot Input:d bits expected Manchester code M composed of {M,M2,...,Ma,corresponding category IDs (C1,Ca,..C),received Manchester According to Algorithm 1,the critical problem of CRCP code Mr,Boolean values of fC,}are stored in B(C)} is how to resolve the collision slots efficiently.In fact, Initialization:B(C)=-l,j∈[1，a] decoding Mj from M is like to solve the system of linear if M,null then BC1)=0,B(C2)=0.,,,B(Ca)=0 equations.In an a-collision slot,o represents the number Return. of variables in an equation,while the length of Manchester if a=I then B(C)=1 code d represents the number of equations.In order to LReturn. simplify the procedure of resolving the collision slot,we while i 1,d do compare each bit in the expected code M with the corre- |M()=∑°10+∑11,0+1=a Use the known set {B(C;)=0}to update sponding bit in received code M,to decode Mi,as shown M(),o,n1,. if M(i)=x and Mr(i)=0 then in Algorithm 2. for each Mj(i)=1 do B(Cj)=0. In Algorithm 2,null means an empty slot.M(i) if no 1 then for each Mi(i)=0 do B(C;)=1. means the ith bit in the Manchester code M.M(i)and Mi(i),M2(i).....Ma(i)are defined in the same way. if M(i)=x and M,(i)=1 then for each M (i)=0 do B(C)=0. Based on the description in Section 3,M(i)equals 0,1 or x. if n=1 then It is produced as follows,M(i)=1.no and L for each Mj(i)=1 do B(C;)=1. nI respectively represent the number of Mj(i)(j[1,a]) if M(i)=x and M(i)=x then if no =1 then equivalent to 0 and 1 in the slot.Before the reader decodes Lfor each M;(i)=0 do B(C;)=1. the category IDs in the ith bit,it will use the known set if n=1 then [B(Ci)}to update M(i).If B(Ci)=0,the reader removes for each Mi(i)=1 do B(Ci)=1. Mj from M and updates M(i),no,n1.a.If the expected Output:Verified category IDs.(Ci B(Ci)-1.) ②Springer
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 keep silent. If a tag in Cj should give response in the following frame with size f , it uses a hash function hr to select a slot hr(Cj ) mod f . Then, it sends d bits Manchester code Mj . Here, Mj = h(Cj ) mod (2d ), h is a hash function. Because the reader knows the related categories and the hash functions, it can get the mapping relation of Cj and Mj . When getting the responses, the reader checks whether each bit in the slot can be recovered from the mixed 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 4. 6.3 Resolving the collision slot According to Algorithm 1, the critical problem of CRCP is how to resolve the collision slots efficiently. In fact, decoding Mj from M is like to solve the system of linear equations. In an α – collision slot, α represents the number of variables in an equation, while the length of Manchester code d represents the number of equations. In order to simplify the procedure of resolving the collision slot, we compare each bit in the expected code M with the corresponding bit in received code Mr to decode Mj , as shown in Algorithm 2. In Algorithm 2, null means an empty slot. M(i) means the ith bit in the Manchester code M. Mr(i) and M1(i), M2(i), . . ., Mα(i) are defined in the same way. Based on the description in Section 3, M(i) equals 0 ,1 or x. It is produced as follows, M(i) = n0 j=0 0+n1 j=1 1. n0 and n1 respectively represent the number of Mj (i) (j ∈ [1, α]) equivalent to 0 and 1 in the slot. Before the reader decodes the category IDs in the ith bit, it will use the known set {B(Cj )} to update M(i). If B(Cj ) = 0, the reader removes Mj from M and updates M(i), n0, n1, α. If the expected Algorithm 1 CRCP: Reader Side bit M(i) = x, while the received bit Mr(i) = 0, then the category Cj with the corresponding bit equivalent to 1 is outside the scanning area, B(Cj ) = 0. Besides, if n0 = 1, the category Cj with corresponding bit equivalent to 0 must in the scanning area, B(Cj ) = 1. If M(i) = x and Mr(i) = 1, we can get the conclusion in the same way. However, if the expected bit M(i) = x = 0 + α−1 j=1 1 and the received bit Mr(i) = x, then the category Cj with 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 Algorithm 2 Resolving an α – collision slot 528 Mobile Netw Appl (2014) 19:524–533
Mobile Netw Appl (2014)19:524-533 529 Table 1 An example for resolving a collision slot with Step 1 2 3 4 =4 Expected Mi set M1,M2,M3,M4 M1,M2,M3,M4 M1,M2,M3 M1,M2,M3 Expected code XXXXXX XXXXXX XX飞XXX XXXXXX Received code xOxxxx xOxxxx xOxxxx xOxxxx M 100101 100101 100101/ 100101 M2 101010 101010 101010 101010W M3 001111/ 001111 001111 001111 Ma 10011 1卫0011× B(Cj) B(C3)=1 B(C4)=0 B(C1)=1 B(C2)=1 the conclusion in the same way.The reader repeats the sim- feature.In this section,we propose an Enhanced Collision ilar process until it decodes all the a category IDs or it has detection based Rule Checking Protocol(ECRCP)in con- repeated d times. sideration of the rule's logical property.In fact,in the OR We give an example in Table 1,the expected Manchester rule,if any category exists,the rule's Boolean value is true. code M is composed of [M1,M2,M3,M4),the received In the AND rule,if any category is out of the scanning code Mr xOxxxx.M xxxxxx,M(1)=x =0+ area,the rule's Boolean value is false.In the EXCLUSIVE ∑=ll,only Ma(l)=0.Besides,.M)=M,(①)=x.r rule,if any category is out of the scanning area,the rule's indicates M3 must give the response.Therefore,B(C3)=1. Boolean value is true.In regard to a hybrid rule,it can be We can get B(C4)=0 in the same way.Then,the reader determined by its subrule's Boolean value in a similar way. removes C4 and updates the third bit in M.M(3)=0+1+ Therefore,when the reader gets a part of the category IDs,it 1 =x,no 1,n1 2,M is composed of (M1,M2,M3), can check the correlated rules.Then it only needs to check a=3.It repeats the similar process and gets B(C1)=1, the remaining categories in the unverified rules. B(C2)=1. 7.2 Protocol description 6.4 Performance analysis 7.2.I Estimating the tag size In CRCP,the reader uses k hash functions and c category IDs to construct the Bloom filter with length 1.If we require In CRCP,the reader sends the request message to tags that the false positive probability is less than e,we get the based on Bloom filter,while ignoring the effect of tag size. optimal value of as / -In(e).c ln(2)-ln(2) When the tag size in the scanning area is much smaller In each a-collision slot,the tag gives responses with d than the number of related categories,CRCP is rather time- bits.We use and pa represent the average value of a and consuming.Thus ECRCP uses the average run based tag pd,respectively.to denotes the waiting time between any estimation (ART)scheme [13]to estimate the tag size.If the two consecutive transmissions,and tbit denotes the time for ratio p of tag size to the number of related categories is less atag totransmitone bit.Withoutloss ofgenerality,weset to= than the threshold p*,the reader will use APCR to check 302us,tbir =18.88us,pe=.Besides,should be a small the rules.Otherwise,the reader uses the Bloom filter to number(such as 2,3,or 4)[3],considering the actual situ- inform the related categories to give responses and verifies ation.Therefore,a is limited to [1,4].We get the optimal the categories,as described in the following subsections. value of a is a*=4,the corresponding optimal value of d is d*=7.We set aa*,dd*,the frame size f== 7.2.2 Finding the popular category More detail information of performance analysis can be found in the conference version of this paper [18]. Based on Section 4,a related category may exist in serval rules.We use frequency fi to describe the number of times that Cj appears in different rules.If Cj appears in a differ- 7 Enhanced collision detection based rule checking ent rule,fj only adds one to its original value,no matter protocol how many times Ci appears in this rule.For example,in the rule Ri =(CiACk)V(Cj vCu),fj,fk,fu respectively add 7.1 Motivation one.Obviously,fi [1,m],m is the number of rules.If a category Ci has a larger value of fi,it means that the cate- CRCP mainly focuses on verifying all the related category gory affects more rules'Boolean values.ECRCP first finds IDs in the scanning area while ignoring the rule's logical the unverified popular category ID with the largest value Springer
Table 1 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 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 1, 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. 6.4 Performance analysis In CRCP, the reader uses k hash functions and c category IDs to construct the Bloom filter with length l. If we require that the false positive probability is less than , we get the optimal value of l as l = −ln()·c ln(2)·ln(2) . In each α − collision slot, the tag gives responses with d bits. We use α¯ and p¯d represent the average value of α and pd , respectively. τ0 denotes the waiting time between any two consecutive transmissions, and τbit denotes the time for atagtotransmitonebit.Withoutlossofgenerality,weset τ0 = 302μs, τbit = 18.88μs, pc = 1 2 . Besides, α¯ should be a small number(such as 2, 3, or 4) [3], 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 α¯ ∗ . More detail information of performance analysis can be found in the conference version of this paper [18]. 7 Enhanced collision detection based rule checking protocol 7.1 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 categories in the unverified rules. 7.2 Protocol description 7.2.1 Estimating the tag size In CRCP, the reader sends the request message to tags based on Bloom filter, while ignoring the effect of tag size. When the tag size in the scanning area is much smaller than the number of related categories, CRCP is rather timeconsuming. Thus ECRCP uses the average run based tag estimation (ART) scheme [13] to estimate the tag size. If the ratio ρ of tag size to the number of related categories is less than the threshold ρ∗, the reader will use APCR to check the rules. Otherwise, the reader uses the Bloom filter to inform the related categories to give responses and verifies the categories, as described in the following subsections. 7.2.2 Finding the popular category Based on Section 4, a related category may exist in serval rules. We use frequency fj to describe the number of times that Cj appears in different rules. If Cj appears in a different rule, fj only adds one to its original value, no matter how many times Cj appears in this rule. For example, in the rule Ri = (Cj ∧Ck )∨(Cj ∨Cu), fj , fk, fu respectively add one. Obviously, fj ∈ [1, m], m is the number of rules. If a category Cj has a larger value of fj , it means that the category affects more rules’ Boolean values. ECRCP first finds the unverified popular category ID with the largest value Mobile Netw Appl (2014) 19:524–533 529
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 ②Springer
of 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 frequency 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 randomly 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 simulation: tag ID is 96 bits long. 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. 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
Mobile Netw Appl (2014)19:524-533 531 18, 16 十一ARCP PRCP 14 ARCP ·PRCP BRCP CRCP 20 ECRCP RCH 10 -ECRCP-No Estimation 8 6 0.050.10.15020.250.30.350.4 500100015002000250030003500400045005000 Ratio Number of tags in scanning area Fig.5 Execution time under different value of ratios Fig.7 Execution time under different number of tags in scanning area 2.3).the kinds of category IDs in the slot are small and 8.4 Execution time comparison collision slots cannot be fully utilized.If a is too large,the collision slots are difficult to be decoded.which wastes a lot Figures 6.7 and 8 shows the execution time,CRCP and of time.Therefore,the optimal values of a and d are =4 ECRCP have better performances,and ECRCP achieves the and d=7,which are not relevant to the length of category highest time efficiency.In Fig.6,when the length of Cj is ID,the number of rules or tags,and are used in the following 64 bits,the execution time of ECRCP is about 0.5 seconds, experiments. which is 3 of the time required by ARCP.The perfor- mance of ECRCP is unrelated to the length of category ID. 8.3 Threshold value o* In Fig.7.when the number of tags is 5000.the execution time of ECRCP is about 0.5 seconds,which is 1.8 of the Figure 5 shows the execution time of each protocol while time required by ARCP.The number of tags has no effect varying the ratio of p.ECRCP-No estimation means that on ECRCP,because ECRCP focuses on the categories in the ECRCP does not estimate the tag size and works in the way rules instead of those in the scanning area.In Fig.8,when described in Section 7.2.2.In Fig.5,when p<0.25,ARCP the number of rules is 500,the execution time of ECRCP is achieves the best performance.This is because the tag size about 0.8 seconds,which is 3.1 of the time required by in the scanning area is much smaller than the number of BRCP.This is because ECRCP not only resolves the col- related categories.In regard to p,it is not relevant to the lision slot but also leverages the rule's logical feature.In length of category ID,the number of rules or tags.It only Fig.9.when the number of rules is 50.ECRCP only verifies concentrates on the ratio of tag size to the number of related 21 of the related category IDs. categories.Therefore,we set the threshold of the ratio to Figures 10 and 11 provide some fine-grained analysis p*=0.25.In our proposed ECRCP,if p<p*,ECRCP about the efficiency of the protocols.Figure 10 illustrates works as ARCP to check the rules.Otherwise,it works in the utilization ratio of the responses slots.CRCP and the way described in Section 7.2.2. ECRCP have higher utilization ratio of responses slots than the baseline ones,because CRCP and ECRCP resolve the 20 30 ·ARCP 16 PRCP 一ARCP 25 14 BRCP -PRCP ·CRCP 12 BRCP 20 一ECRCP CRCP ⊙一ECRCP aw!L 15 10 ǚ 16 2432404856 64 50100150200250300350400450500 Length of Categoy ID(bits) Number of rules Fig.6 Execution time under different length of C Fig.8 Execution time under different number of rules Springer
Fig. 5 Execution time under different value of ratios 2, 3), the kinds of category IDs in the slot are small and collision slots cannot be fully utilized. If α¯ is too large, the collision slots are difficult to be decoded, which wastes a lot of time. 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. 8.3 Threshold value ρ∗ Figure 5 shows the execution time of each protocol while varying the ratio of ρ. ECRCP-No estimation means that ECRCP does not estimate the tag size and works in the way described in Section 7.2.2. In Fig. 5, when ρ ≤ 0.25, ARCP achieves the best performance. This is because the tag size in the scanning area is much smaller than the number of related categories. In regard to ρ, it is not relevant to the length of category ID, the number of rules or tags. It only concentrates on the ratio of tag size to the number of related categories. Therefore, we set the threshold of the ratio to ρ∗ = 0.25. In our proposed ECRCP, if ρ ≤ ρ∗, ECRCP works as ARCP to check the rules. Otherwise, it works in the way described in Section 7.2.2. Fig. 6 Execution time under different length of Cj Fig. 7 Execution time under different number of tags in scanning area 8.4 Execution time comparison Figures 6, 7 and 8 shows the execution time, CRCP and ECRCP have better performances, and ECRCP achieves the highest time efficiency. In Fig. 6, when the length of Cj is 64 bits, the execution time of ECRCP is about 0.5 seconds, which is 3 % of the time required by ARCP. The performance of ECRCP is unrelated to the length of category ID. In Fig. 7, when the number of tags is 5000, the execution time of ECRCP is about 0.5 seconds, which is 1.8 % 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. 8, when the number of rules is 500, the execution time of ECRCP is about 0.8 seconds, which is 3.1 % 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. 9, when the number of rules is 50, ECRCP only verifies 21 % of the related category IDs. Figures 10 and 11 provide some fine-grained analysis about the efficiency of the protocols. Figure 10 illustrates the utilization ratio of the responses slots. CRCP and ECRCP have higher utilization ratio of responses slots than the baseline ones, because CRCP and ECRCP resolve the Fig. 8 Execution time under different number of rules Mobile Netw Appl (2014) 19:524–533 531
532 Mobile Netw Appl (2014)19:524-533 2500 9 ARCP PRCP 8 2000 BRCR CRCP ECRC 500 5 1000 4 3 500 50 100150200250300 ARCP PRCP BRCP CRCPECRCP Number of rules Protocols Fig.9 Number of verified category IDs under different number of rules Fig.11 Average Number of verified category IDs used to check a rule collision slots to get more category IDs.Besides,Fig.11 properly adjust the length of the Bloom filter and the num- shows that ECRCP only needs about 1.7 verified related ber of hash functions used in the Bloom filter to meet the categories to check a rule on average,which is only 21 of requirement. that needed in RRCP,BRCP,CRCP.This is because RCRCP verifies the most popular categories,which affect more rules'Boolean values.ECRP only verifies part of the related 9 Discussion categories,which is consistent with Fig.9.Therefore,it achieves the best performance. Bit-level collision detection is important to CRCP and ECRCP.While considering the realistic environments, 8.5 Accuracy of checking all the rules detecting a collision bit can be affected by the capture effect. channel error,etc. Figure 12 illustrates the accuracies of checking all the rules. Capture Effect:When tagl sends bit'0'and tag2 sends The accuracies of ARCP and PRCP are higher than those bit'1'simultaneously,the expected mixed result is a of BRCP,CRCP and ECRCP.Because BRCP,CRCP and collision bit x.However,if the signal strength of tagl is ECRCP use the Bloom filter,which has the probability of much more strong than that of tag2,the reader is likely false positive.It can result in decoding the category IDs to get bit'0',capture effect occurs.At this time,CRCP wrongly,leading to wrong result of the correlated rule. and ECRCP may consider that tag2 is missing,leading However,the accuracy of 96%can be achieved by CRCP to an error. and ECRCP,which is high enough in many applications. Aiming to relieve capture effect,we can check the Furthermore,the accuracy of 98 can be achieved by rules in a mobile way to change the distance between ECRCP.When the number of rules is 300,the accuracy of the tags and the antenna,which affects the tag's signal ECRCP is 99.5 %If a higher accuracy is needed,we can strength.If a tag can be detected at least one time,then the reader considers that it exists.Moreover,in our pro- posed protocols CRCP and ECRCP,there may be more 5 4.5 PRCP 10 4553 2 1 0.5 ARCP PRCP BRCP CRCPECRCP 50 100 150 200 250 300 Protocols Number of rules Fig.10 Average Number of category IDs verified in a response slot Fig.12 Accuracy under different number of rules ②Springer
Fig. 9 Number of verified category IDs under different number of rules collision slots to get more category IDs. Besides, Fig. 11 shows that ECRCP only needs about 1.7 verified related categories to check a rule on average, which is only 21 % of that needed in RRCP, BRCP, CRCP. This is because RCRCP verifies the most popular categories, which affect more rules’ Boolean values. ECRP only verifies part of the related categories, which is consistent with Fig. 9. Therefore, it achieves the best performance. 8.5 Accuracy of checking all the rules Figure 12 illustrates the accuracies of checking all the rules. The accuracies of ARCP and PRCP are higher than those of BRCP, CRCP and ECRCP. Because BRCP, CRCP and ECRCP use the Bloom filter, which has the probability of false positive. It can result in decoding the category IDs wrongly, leading to wrong result of the correlated 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 Fig. 10 Average Number of category IDs verified in a response slot Fig. 11 Average Number of verified category IDs used to check a rule properly adjust the length of the Bloom filter and the number of hash functions used in the Bloom filter to meet the requirement. 9 Discussion Bit-level collision detection is important to CRCP and ECRCP. While considering the realistic environments, detecting a collision bit can be affected by the capture effect, channel error, etc. – Capture Effect: When tag1 sends bit ’0’ and tag2 sends bit ’1’ simultaneously, the expected mixed result is a collision bit x. However, if the signal strength of tag1 is much more strong than that of tag2, the reader is likely to get bit ’0’, capture effect occurs. At this time, CRCP and ECRCP may consider that tag2 is missing, leading to an error. Aiming to relieve capture effect, we can check the rules in a mobile way to change the distance between the tags and the antenna, which affects the tag’s signal strength. If a tag can be detected at least one time, then the reader considers that it exists. Moreover, in our proposed protocols CRCP and ECRCP, there may be more Fig. 12 Accuracy under different number of rules 532 Mobile Netw Appl (2014) 19:524–533
Mobile Netw Appl (2014)19:524-533 533 than one tag in category i giving response in a slot.It 2.Xie L,Sheng B,Tan CC,Han H,Li Q,Chen D (2010)Effi- will further reduce the capture effect,because the exis- cient tag identification in mobile RFID systems.In:Proceedings tence of a category is more easily to be detected than of INFOCOM.San Diego,pp 1001-1009 3.Zhang M,Li T,Chen S,Li B(2010)Using analog network cod- the existence of a tag. ing to improve the RFID reading throughput.In:Proceedings of Channel Error:Channel error may corrupt the sig- ICDCS.Genova,pp 547-556 nal transmitted by a tag.The problem is common to 4.Zheng Y,Li M(2013)P-MTI:physical-layer missing tag identi- all RFID reading protocols.Therefore,the RFID tag fication via compressive sensing.In:Proceedings of INFOCOM. usually keeps transmitting its ID until it receives the Turin,pp 917-925 5.Alotaibi M.Bialkowski KS.Postula A (2010)A signal strength acknowledgement from the reader.In our proposed pro- based tag estimation technique for RFID systems.In:2010 IEEE tocols CRCP and ECRCP,only the bits of a slot can be international conference on RFID-technology and applications recovered from the signal,the reader will resolve the (RFID-TA).Guangzhou,pp 251-256 6.Ning H,Cong Y,Xu ZQ,Hong T,Zhao JC,Zhang Y(2007)Per- collision slot,as shown in Algorithm 1.Otherwise,the formance evaluation of RFID anti-collision algorithm with FPGA tags mapping to this slot will reply in the next frame,in implementation.In:21st international conference on advanced order to reduce the effect of channel error. information networking and applications workshops (AINAW). Niagara Falls,pp 153-158 While considering the issues like capture effect,chan- 7.Lim T,Li T.Yeo S(2008)A cross-layer framework for privacy nel error,etc,there may be some potential inaccuracy of enhancement in RFID systems.Pervasive Mob Comput 4(6):889- our protocols CRCP and ECRCP.However,by adopting 905 8.Liu L,Xie Z,Xi J,Lai S (2005)An improved anti-collision the techniques described above,our protocols can work algorithm in RFID system.In:Proceedings of 2nd interna- efficiently and reduce the effect caused by realistic envi- tional conference on mobile technology,applications and systems. ronments in a degree.In future,we will provide more Guangzhou improvements to CRCP and ECRCP,in order to solve the 9.Tan CC,Sheng B,Li Q(2008)How to monitor for missing RFID tags.In:Proceedings of ICDCS.Beijing,pp 295-302 problems better. 10.Luo W,Chen S,Li T,Qiao Y (2012)Probabilistic missing- tag detection and energy-time tradeoff in large-scale RFID sys- tems. In:Proceedings of MobiHoc.South Carolina,pp 95- 104 10 Conclusion 11.Zheng Y,Li M(2011)Fast tag searching protocol for large-scale RFID systems.In:19th IEEE international conference on network In this paper,we investigate the rule checking problem in protocols (ICNP).Vancouver,pp 363-372 RFID systems.We present two efficient protocols,CRCP 12.Kodialam M,Nandagopal T(2006)Fast and reliable estimation and ECRCP.CRCP resolves the collision slots.while schemes in RFID systems.In:Proceedings of the 12th annual international conference on mobile computing and networking ECRCP further combines the collision detection and the (MobiCom).Los Angeles,pp 322-333 rules'logical features to achieve time efficiency.Simu- 13. Shahzad M,Liu AX(2012)Every bit counts fast and scalable lation results show that CRCP and ECRCP have better RFID estimation.In:Proceedings of the 18th annual international performance than the baseline protocols.Besides,ECRCP conference on mobile computing and networking (MobiCom). Istanbul,pp 365-376 outperforms all the other solutions. 14.Yue H,Zhang C,Pan M,Fang Y,Chen S (2012)A time- efficient information collection protocol for large-scale RFID Acknowledgments This work is supported in part by National Systems.In:Proceedings of IEEE INFOCOM.Orlando,pp 2158- Natural Science Foundation of China under Grant No.61100196, 2166 61321491.91218302:JiangSu Natural Science Foundation under 15.EPC radio frequency identify protocols class-1 generation-2 UHF Grant No.BK2011559:Key Project of JiangSu Research Program RFID protocol for communications at 860 MHz-916 MHz under Grant No.BE2013116:EU FP7 IRSES MobileCloud Project Version 1.2.0 under Grant No.612212. 16.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-960MHZ,ed:Standard IS018000-6,(2003) 17.Wang J,Hassanieh H,Katabi D,Indyk P(2012)Efficient and reli- References able low-power backscatter networks.ACM SIGCOMM Comput Commun Rev 42(4):61-72 1.Pan L.Wu H(2009)Smart trend-traversal:a low delay and energy 18.Yin Y,Xie L,Lu S,Chen D(2013)Efficient Protocols for Rule tag arbitration protocol for large RFID systems.In:Proceedings Checking in RFID Systems.In:Proceedings of IEEE ICCCN. of INFOCOM,mini-conference.Rio de Janeiro,pp 2571-2575 Nassau,pp 1-7 Springer
than one tag in category i giving response in a slot. It will further reduce the capture effect, because the existence of a category is more easily to be detected than the existence of a tag. – Channel Error: Channel error may corrupt the signal transmitted by a tag. The problem is common to all RFID reading protocols. Therefore, the RFID tag usually keeps transmitting its ID until it receives the acknowledgement from the reader. In our proposed protocols CRCP and ECRCP, only the bits of a slot can be recovered from the signal, the reader will resolve the collision slot, as shown in Algorithm 1. Otherwise, the tags mapping to this slot will reply in the next frame, in order to reduce the effect of channel error. While considering the issues like capture effect, channel error, etc, there may be some potential inaccuracy of our protocols CRCP and ECRCP. However, by adopting the techniques described above, our protocols can work efficiently and reduce the effect caused by realistic environments in a degree. In future, we will provide more improvements to CRCP and ECRCP, in order to solve the problems better. 10 Conclusion In this paper, we investigate the rule checking problem in RFID systems. We present two efficient protocols, CRCP and ECRCP. CRCP resolves the collision slots, while ECRCP further combines the collision detection and the rules’ logical features to achieve time efficiency. Simulation results show that CRCP and ECRCP have better performance than the baseline protocols. Besides, ECRCP outperforms all the other solutions. Acknowledgments This work is supported in part by National Natural Science Foundation of China under Grant No. 61100196, 61321491, 91218302; JiangSu Natural Science Foundation under Grant No. BK2011559; Key Project of JiangSu Research Program under Grant No. BE2013116; EU FP7 IRSES MobileCloud Project under Grant No. 612212. References 1. Pan L, Wu H (2009) Smart trend-traversal: a low delay and energy tag arbitration protocol for large RFID systems. In: Proceedings of INFOCOM, mini-conference. Rio de Janeiro, pp 2571–2575 2. Xie L, Sheng B, Tan CC, Han H, Li Q, Chen D (2010) Efficient tag identification in mobile RFID systems. In: Proceedings of INFOCOM. San Diego, pp 1001–1009 3. Zhang M, Li T, Chen S, Li B (2010) Using analog network coding to improve the RFID reading throughput. In: Proceedings of ICDCS. Genova, pp 547–556 4. Zheng Y, Li M (2013) P-MTI: physical-layer missing tag identification via compressive sensing. In: Proceedings of INFOCOM. Turin, pp 917–925 5. Alotaibi M, Bialkowski KS, Postula A (2010) A signal strength based tag estimation technique for RFID systems. In: 2010 IEEE international conference on RFID-technology and applications (RFID-TA). Guangzhou, pp 251–256 6. Ning H, Cong Y, Xu ZQ, Hong T, Zhao JC, Zhang Y (2007) Performance evaluation of RFID anti-collision algorithm with FPGA implementation. In: 21st international conference on advanced information networking and applications workshops (AINAW). Niagara Falls, pp 153–158 7. Lim T, Li T, Yeo S (2008) A cross-layer framework for privacy enhancement in RFID systems. Pervasive Mob Comput 4(6):889– 905 8. Liu L, Xie Z, Xi J, Lai S (2005) An improved anti-collision algorithm in RFID system. In: Proceedings of 2nd international conference on mobile technology, applications and systems. Guangzhou 9. Tan CC, Sheng B, Li Q (2008) How to monitor for missing RFID tags. In: Proceedings of ICDCS. Beijing, pp 295–302 10. Luo W, Chen S, Li T, Qiao Y (2012) Probabilistic missingtag detection and energy-time tradeoff in large-scale RFID systems. In: Proceedings of MobiHoc. South Carolina, pp 95– 104 11. Zheng Y, Li M (2011) Fast tag searching protocol for large-scale RFID systems. In: 19th IEEE international conference on network protocols (ICNP). Vancouver, pp 363–372 12. Kodialam M, Nandagopal T (2006) Fast and reliable estimation schemes in RFID systems. In: Proceedings of the 12th annual international conference on mobile computing and networking (MobiCom). Los Angeles, pp 322–333 13. Shahzad M, Liu AX (2012) Every bit counts - fast and scalable RFID estimation. In: Proceedings of the 18th annual international conference on mobile computing and networking (MobiCom). Istanbul, pp 365–376 14. Yue H, Zhang C, Pan M, Fang Y, Chen S (2012) A timeefficient information collection protocol for large-scale RFID Systems. In: Proceedings of IEEE INFOCOM. Orlando, pp 2158– 2166 15. EPC radio frequency identify protocols class-1 generation-2 UHF RFID protocol for communications at 860 MHz - 916 MHz Version 1.2.0 16. 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) 17. Wang J, Hassanieh H, Katabi D, Indyk P (2012) Efficient and reliable low-power backscatter networks. ACM SIGCOMM Comput Commun Rev 42(4):61–72 18. Yin Y, Xie L, Lu S, Chen D (2013) Efficient Protocols for Rule Checking in RFID Systems. In: Proceedings of IEEE ICCCN. Nassau, pp 1–7 Mobile Netw Appl (2014) 19:524–533 533