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 ②Springera 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 EPC￾C1G2 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. Further￾more, 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 stan￾dard [15], the tags responding in the same slot can be syn￾chronized through QueryRep or QueryAdjust. Besides, the effective scanning range in the passive RFID system is lim￾ited (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 sig￾nals, 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 syn￾chronized. 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. With￾out 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 cat￾egory 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. Actu￾ally, 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