IEEE/ACM TRANSACTIONS ON NETWORKING 1.0g where the mask will be compared with .0i SamplesOffset 1.0 These fields are combined to compose a selection rule.We formally denote the rule as follows: Length S(卫，t,m) Pointer Mask which implies that only tags whose MemBank3s'sub-bitstring p,p+1)is equal to m will be selected.Fig.6 shows an (a)RN16 example in which four tags are selected to join in the inventory. Note that multiple Selects are allowable (discussed later). ■Acucired-Desired Intercepted Inventory.The function of selective reading offers an opportunity to select the tags based on a mask.If the reader broadcasts the following Select, S(r,l,v) then only the tags whose sub-bitstring [r,r+1)in its 500 550 600 650700 750 800 850 MemBank3 is equal to v,are selected to participate in the Samples# incoming inventory.Interestingly,the set of selected tags (b)Preamble exactly fit the question of presence!To know if its cardinality is greater than zero,we let the reader afterwards broadcast Fig.8:Baseband signals of RN16 reply.(a)shows the signals of a RN16 reply.which is composed of a 5-bit preamble and 16 a Query command to start a single-slot frame,by setting random bits.(b)shows zoomed-in preamble and its comparison with the field of frame length to 1.All selected tags are forced to the desired template. reply in the following slot immediately.As aforementioned, a tag must transmit an RN16 reply firstly before sending its EPC reply.Our trick here is that the RN16 reply is regarded keep in mind that our ultimate goal is to acquire a BF across all as the presence evidence of a tag.which has the given hash tags instead of their hash values.Here,we consider a question, value.As long as the reader detects any RN16 reply signal, named question of presence,that is,is there any tag which the answer to the question of presence is negative.Finally, can output a wanted hash value?Formally,given the input the reader ignores the request of long reply even if a single pair(r,l)and the hash value v,we determine if tag responds and terminates the inventory procedure.We call the above procedure intercepted inventory.The inventory is {h四(t,r）=>0 "intercepted"because an intact inventory is supposed to ACK for all t E T,where denotes the cardinality of a set.Since the tag's RN16 reply and request the long reply subsequently our hash value is a portion of the real one stored in a tag's (see Fig.2).In contrast to the entire inventory,the interval MemBank3,the question can be converted to a new form: of an intercept inventory is kept constant regardless of how many tags participate the procedure.Fig.7 shows the baseband Problem 1.Is there any tag whose sub-bistring Er,r+l)signals of an intercepted inventory acquired by USRP N210. in its MemBank3 is equal to v? Detecting Presence Signals.Each 22-bit RN16 reply con- Selective Reading.Any inventory procedure must be started tains a 6-bit preamble and 16 random bits.The reader can with a Select command.Gen2 protocol specifies that detect an RN16 reply by correlating its preamble template each tag maintains a flag variable SL.The reader can use with the received signals.Considering that the 16-bit random the Select command to turn the SL flags of tags into signals are independent of the preamble,their correlation is asserted (i.e.,true)or deasserted (i.e.,false).Only the nearly zero except when the preamble is perfectly aligned with asserted tags will respond to a Query (or QueryAdjust) the beginning of an RN16.One or multiple spikes appearing at command,participating the inventory.The Select command the correlation result indicate the presence of one or multiple is composed of 8 fields.For simplicity,we only introduce the tags possessing the given hash value.Fig.8(a)shows an four fields,which will be employed in our design:MemBank, example of RN16 reply sent from a single tag.Fig.8(b)zooms Pointer,Length and Mask. into its preamble compared with the template.It is worth Mask:it is a specific bitstring that should match the content noting that the final received signal is a combination of the of a specific position in a MemBank. line-of-sight propagation,the repetitive proportions from other none-ling-of-sight paths,and the leakage of the continuous Length:it defines the length of the mask in bits wave from the reader.The signals arrive at the receiver MemBank:it specifies which memory bank the mask will different phase values due to the diversity of the propagation be compared with.We consider MemBank3 only by default distances.As a result,they might add up constructively or in our scenario. destructively.In the second case,the received signal might be Pointer:it specifies the starting position in the MemBank weaker than the power of reader continuous wave.IEEE/ACM TRANSACTIONS ON NETWORKING 6 500 1000 1500 2000 2500 Samples# 0.98 0.985 0.99 0.995 1 1.005 1.01 1.015 1.02 Amplitude Samples Offset =1 (a) RN16 500 550 600 650 700 750 800 850 Samples# -2 -1 0 1 2 Amplitude Acuqired Desired (b) Preamble Fig. 8: Baseband signals of RN16 reply. (a) shows the signals of a RN16 reply, which is composed of a 5-bit preamble and 16 random bits. (b) shows zoomed-in preamble and its comparison with the desired template. keep in mind that our ultimate goal is to acquire a BF across all tags instead of their hash values. Here, we consider a question, named question of presence, that is, is there any tag which can output a wanted hash value? Formally, given the input pair (r, l) and the hash value v, we determine if   {t|h (l) (t, r) = v}    > 0 for all t ∈ T, where | · | denotes the cardinality of a set. Since our hash value is a portion of the real one stored in a tag’s MemBank3, the question can be converted to a new form: Problem 1. Is there any tag whose sub-bistring ∈ [r, r + l) in its MemBank3 is equal to v? Selective Reading. Any inventory procedure must be started with a Select command. Gen2 protocol specifies that each tag maintains a flag variable SL. The reader can use the Select command to turn the SL flags of tags into asserted (i.e., true) or deasserted (i.e., false). Only the asserted tags will respond to a Query (or QueryAdjust) command, participating the inventory. The Select command is composed of 8 fields. For simplicity, we only introduce the four fields, which will be employed in our design: MemBank, Pointer, Length and Mask. • Mask: it is a specific bitstring that should match the content of a specific position in a MemBank. • Length: it defines the length of the mask in bits. • MemBank: it specifies which memory bank the mask will be compared with. We consider MemBank3 only by default in our scenario. • Pointer: it specifies the starting position in the MemBank where the mask will be compared with. These fields are combined to compose a selection rule. We formally denote the rule as follows: S( p |{z} Pointer , Length z}|{ l , m|{z} Mask ) which implies that only tags whose MemBank3s’ sub-bitstring ∈ [p, p + l) is equal to m will be selected. Fig. 6 shows an example in which four tags are selected to join in the inventory. Note that multiple Selects are allowable (discussed later). Intercepted Inventory. The function of selective reading offers an opportunity to select the tags based on a mask. If the reader broadcasts the following Select, S(r, l, v) , then only the tags whose sub-bitstring ∈ [r, r + l) in its MemBank3 is equal to v, are selected to participate in the incoming inventory. Interestingly, the set of selected tags exactly fit the question of presence! To know if its cardinality is greater than zero, we let the reader afterwards broadcast a Query command to start a single-slot frame, by setting the field of frame length to 1. All selected tags are forced to reply in the following slot immediately. As aforementioned, a tag must transmit an RN16 reply firstly before sending its EPC reply. Our trick here is that the RN16 reply is regarded as the presence evidence of a tag, which has the given hash value. As long as the reader detects any RN16 reply signal, the answer to the question of presence is negative. Finally, the reader ignores the request of long reply even if a single tag responds and terminates the inventory procedure. We call the above procedure intercepted inventory. The inventory is “intercepted” because an intact inventory is supposed to ACK the tag’s RN16 reply and request the long reply subsequently (see Fig. 2). In contrast to the entire inventory, the interval of an intercept inventory is kept constant regardless of how many tags participate the procedure. Fig. 7 shows the baseband signals of an intercepted inventory acquired by USRP N210. Detecting Presence Signals. Each 22-bit RN16 reply con￾tains a 6-bit preamble and 16 random bits. The reader can detect an RN16 reply by correlating its preamble template with the received signals. Considering that the 16-bit random signals are independent of the preamble, their correlation is nearly zero except when the preamble is perfectly aligned with the beginning of an RN16. One or multiple spikes appearing at the correlation result indicate the presence of one or multiple tags possessing the given hash value. Fig. 8(a) shows an example of RN16 reply sent from a single tag. Fig. 8(b) zooms into its preamble compared with the template. It is worth noting that the final received signal is a combination of the line-of-sight propagation, the repetitive proportions from other none-ling-of-sight paths, and the leakage of the continuous wave from the reader. The signals arrive at the receiver different phase values due to the diversity of the propagation distances. As a result, they might add up constructively or destructively. In the second case, the received signal might be weaker than the power of reader continuous wave