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 Ckused 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 mes￾sages. 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. Manch￾ester 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 bit￾level 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