IEEE/ACM TRANSACTIONS ON NETWORKING tags.Unfortunately,to our best knowledge and investigation, we have not found any Truncate-available tags on the elect market.Actually,this issue has been claimed in [43].This is also the reason that the performance of Tash [43]related to this command is evaluated with simulations,instead of real tags.On the contrary,our solution uses RN16 reply as presence evidence.As a fundamental reply,the RN16 reply 0 100100 is completely serviceable in today's Gen2 tags. M Efficiency:The anti-collision processing is actually un- Fig.4:Acquisition solution.To acquire an M-bit BF,TagMap avoidable in Tash,because there is no way to control the reader initiates M intercepted inventories,each of which contains inventory procedure in the application layer.No relevant K Selects,one Query and a time window for RN16 reply. APIs are provided by commercial readers so far.Our ap- B.Solution Sketch proach intercepts an inventory in the physical layer to skip the anti-collision processing. The features and usage of the Bloom filter have been widely In short.TagMap is highly advantageous due to its physical- studied in various fields [46].They are not our focus in this layer performance boost and full compatibility with COTS work.Instead,we more concern about the way to acquire a tags. BF across RFID tags,which must be tightly integrated with the standard EPCglobal Gen2 RFID air protocol [47],making billions of tags serviceable.The whole solution consists of two III.OVERVIEW phases as follows: In offline phase,we compute the hash value of each tag's Although we present our acquisition approach with the EPC and store it inside the tag's non-volatile memory bank EPCglobal Gen2 air interface protocol,which has been for future use.The storing can be accomplished by using adopted globally,our approach also works with other similar the standard Gen2 command of Write.This phase is only protocols,such as ISO18000-6C.In this section,we firstly initiated once.For example,it is initiated when the user formulate the Bloom filter and then sketch the overall solution. writes EPCs to tags. In online phase,the reader acquires a BF bit by bit.The TagMap reader initiates an intercepted inventory for each A.Formulation of Bloom Filter bit.The inventory is used to answer the question of presence A BF represents a set T={t1,t2,...,tn}with n tags.It is that if any tag is hashed into the corresponding bit.If answer described by an array of M bits,which are initially set to 0. is positive,the bit is set to one;otherwise,it is set to zero. We can use K hash functions,(hi,h2,...,hk}to map each Fig.4 shows the acquisition procedure from a high-level. tag in the universe to a number within the range {1,...,M). To acquire an M-bit BF,the reader initiates M intercepted For each tag t ET,the bits of (h(t),...,hk(t)}are set to inventories,each of which corresponds to a bit in the BF.In 1.A bit can be set to 1 multiple times (e.g.,collisions),but each inventory,the reader broadcasts K Select commands its value remains 1.To check if a tag t is in T,we check if and one Query command;the tags matching the hash rules all bits of (h(t),...,hk(t)}are set to 1.If not,then t is not are forced to transmit their RN16 replies in the first slot.In in the tag set.If all bits are set to 1,we assume that t is in the end of the intercepted inventory,the reader determines the T,although this assumption may be wrong with sufficiently value of the corresponding bit. low probability,namely,yielding a false positive.The false positive rate depends on parameter selection:using many hash IV.ACQUISITION OF BLOOM FILTER functions equates to a high probability of finding'0'bits for In this section,we introduce the technical details of each tag that is not in the set;using a few hash functions increases the fraction of'0'bits in the map.Here,we present TagMap. two useful Lemmas as follows: A.TagMap in a Nutshell Lemma 1.Given a tolerance (i.e.,upper bound of false positive rate，以BF length M≥[nlog2e·log2(1/e)l= The subsequent sections progressively introduce the acqui- [1.44nlog2(1/e)1: sition approach by discussing the following issues: Emulating hash function.Commercially available tags at Lemma 2.The false negative rate is minimized when present do not support hash functions.Thus,our first task is the number of hash functions K [In2.(M/n)]= to emulate a hash function that works as if it was embedded 「0.99811og2(1/e)17 on each tag. Their proofs are similar in nature to the standard analysis Answering the question of presence.With the emulated hash of the Bloom filter as shown in [46].The number of tags n is functions,a TagMap reader initiates an intercepted inventory assumed to be known already.It can be discovered through a to suggest whether any tag that can output a given hash value preliminary inventory or stored in backend. is present or not.IEEE/ACM TRANSACTIONS ON NETWORKING 4 tags. Unfortunately, to our best knowledge and investigation, we have not found any Truncate-available tags on the market. Actually, this issue has been claimed in [43]. This is also the reason that the performance of Tash [43] related to this command is evaluated with simulations, instead of real tags. On the contrary, our solution uses RN16 reply as presence evidence. As a fundamental reply, the RN16 reply is completely serviceable in today’s Gen2 tags. • Efficiency: The anti-collision processing is actually un￾avoidable in Tash, because there is no way to control the inventory procedure in the application layer. No relevant APIs are provided by commercial readers so far. Our ap￾proach intercepts an inventory in the physical layer to skip the anti-collision processing. In short, TagMap is highly advantageous due to its physical￾layer performance boost and full compatibility with COTS tags. III. OVERVIEW Although we present our acquisition approach with the EPCglobal Gen2 air interface protocol, which has been adopted globally, our approach also works with other similar protocols, such as ISO18000-6C. In this section, we firstly formulate the Bloom filter and then sketch the overall solution. A. Formulation of Bloom Filter A BF represents a set T = {t1, t2, . . . , tn} with n tags. It is described by an array of M bits, which are initially set to 0. We can use K hash functions, {h1, h2, . . . , hK} to map each tag in the universe to a number within the range {1, . . . , M}. For each tag t ∈ T, the bits of {h1(t), . . . , hK(t)} are set to 1. A bit can be set to 1 multiple times (e.g., collisions), but its value remains 1. To check if a tag t is in T, we check if all bits of {h1(t), . . . , hK(t)} are set to 1. If not, then t is not in the tag set. If all bits are set to 1, we assume that t is in T, although this assumption may be wrong with sufficiently low probability, namely, yielding a false positive. The false positive rate depends on parameter selection: using many hash functions equates to a high probability of finding ‘0’ bits for each tag that is not in the set; using a few hash functions increases the fraction of ‘0’ bits in the map. Here, we present two useful Lemmas as follows: Lemma 1. Given a tolerance ε (i.e., upper bound of false positive rate), BF length M ≥ dn log2 e · log2 (1/ε)e = d1.44n log2 (1/ε)e. Lemma 2. The false negative rate is minimized when the number of hash functions K = dln 2 · (M/n)e = d0.9981 log2 (1/ε)e. Their proofs are similar in nature to the standard analysis of the Bloom filter as shown in [46]. The number of tags n is assumed to be known already. It can be discovered through a preliminary inventory or stored in backend. Intercepted Inventory ··· Intercepted Inventory Select ··· Select Query ⌧2 RN16 ⌧3 K ⌧1 ⌧1 0 1 0 1 0 1 0 0 Intercepted Inventory ··· M BF bitmap: Fig. 4: Acquisition solution. To acquire an M-bit BF, TagMap reader initiates M intercepted inventories, each of which contains K Selects, one Query and a time window for RN16 reply. B. Solution Sketch The features and usage of the Bloom filter have been widely studied in various fields [46]. They are not our focus in this work. Instead, we more concern about the way to acquire a BF across RFID tags, which must be tightly integrated with the standard EPCglobal Gen2 RFID air protocol [47], making billions of tags serviceable. The whole solution consists of two phases as follows: • In offline phase, we compute the hash value of each tag’s EPC and store it inside the tag’s non-volatile memory bank for future use. The storing can be accomplished by using the standard Gen2 command of Write. This phase is only initiated once. For example, it is initiated when the user writes EPCs to tags. • In online phase, the reader acquires a BF bit by bit. The TagMap reader initiates an intercepted inventory for each bit. The inventory is used to answer the question of presence that if any tag is hashed into the corresponding bit. If answer is positive, the bit is set to one; otherwise, it is set to zero. Fig. 4 shows the acquisition procedure from a high-level. To acquire an M-bit BF, the reader initiates M intercepted inventories, each of which corresponds to a bit in the BF. In each inventory, the reader broadcasts K Select commands and one Query command; the tags matching the hash rules are forced to transmit their RN16 replies in the first slot. In the end of the intercepted inventory, the reader determines the value of the corresponding bit. IV. ACQUISITION OF BLOOM FILTER In this section, we introduce the technical details of TagMap. A. TagMap in a Nutshell The subsequent sections progressively introduce the acqui￾sition approach by discussing the following issues: • Emulating hash function. Commercially available tags at present do not support hash functions. Thus, our first task is to emulate a hash function that works as if it was embedded on each tag. • Answering the question of presence. With the emulated hash functions, a TagMap reader initiates an intercepted inventory to suggest whether any tag that can output a given hash value is present or not