IEEE/ACM TRANSACTIONS ON NETWORKING 7 Φ0.45 0. 0.35 0 10 20 2 Time(ms) Fig.9:Baseband signals of acquiring an 8-bit BF across 3 tags.The bitmap totally contains 8 bits,each of which corresponds to an intercepted inventory.The three tags reply in the 1,2 and 5hinventory respectively,so the final BF equals [1,1,0,0,1,0,0,0]. D.Acquiring a Bloom Filter 0.35 Interceptod Invantory Ineegceeted Inventory So far.we have discussed how the TagMap reader deter- 0.3 mines if any tag outputs a given hash value.Now,we start to 0.29 acquire a whole BF by considering three cases progressively: 1)Case 1:Acquisition with a Single Hash:We firstly consider a simplified case,namely,acquiring a 2-bit BF using 01 0.1 a single hash function:h(t,r).Correspondingly,the bitmap size M=24.The definition of hash bitmap indicates that:a tag t is hashed into the mth bit of the bitmap if and only if 28 30 32 34 36 h四(t,r）=m for t∈T,where m=0,,M-1. Time(ms) Namely,the index of the bitmap actually implies the hash Fig.10:Acquiring an BF with 2 hashes.There are two intercepted value.We build a BF bit by bit,traversing the index from 0 inventories.The baseband signals fo each inventory contains two to M-1.When building the mth bit,we ask the question of Selects'signals before the Query signals. presence like this:is there any tag whose hash value is equal to m?To do so,the reader initiates an intercepted inventory reader initiates an intercepted inventory,which contains K with the Select command of S(r,l,m).If the answer is positive,the mth bit of the BF is set to'1';otherwise,0' Selects as follows: This procedure continues until M bits are all traversed. S(r1;I,m),S(r2,I,m),...,S(rk,l,m) (2) Fig.9 shows the baseband signals of acquiring an 8-bit BF Similarly,if any RN16 signal is detected after the Query,the across 3 tags.From the figure,we can observe 8 intercepted corresponding bit is set to'1'.Fig.10 shows the baseband sig- inventories.Zooming into any one of them,three distinct nals of two consecutive intercepted inventories when acquiring segments-Select,Query and RN16-can be observed, a BF with 2 hashes.From the figure,we can exactly observe exactly as same as a single intercepted inventory shown in two Select commands before the Query in an intercepted Fig.7. inventory. 2)Case 2:Acquisition with K Hashes:Secondly,we consider to acquire a 2-bit BF using K hash functions: 3)Case 3:Acquisition with Arbitrary Size:The first two h四(t,r1),.,h四(t,rK）.in this case,the mth bit is set to cases consider to generate BFs with size of M=2!bit. 'I'when any one tag is hashed into the bit by any one of these The size M is a key parameter that directly determines K hash functions.Correspondingly,the question of presence acquisition overhead,and thereby should be well optimized. turns to Lemma 2 implies the minimal(and optimal)size.Apparently, the minimal size of BF might not be exactly an exponent of {th(t,ri)=mll...Ilh(t,rK)=m)> 2.On the other hand,the hash values are stored in a binary format in the memory bank,so l must be an integer.As a for all t T.With regard to our hash function,the question result,the actual size M has to be set to 2 and I=[log2 M can be expressed as follows: suppose M is the optimal size,such that M>M and I is Problem 2.Is there any tag whose sub-bitstring E[r1,r1+ an integer.This setting is valid but might be extremely costly. I-1),...or E [rK,rK +I-1)in its MemBank3 is equal For example,suppose the optimal size M=257,we have to to m? set actual size M=2og22571=512,which is almost double than the optimal one. Since each range corresponds to a Select,answering the To enable an arbitrary size,we define the operation of above question requires K Selects.The result of multiple modulo to shrink the size,as used in other applications [46]. Select commands is a union of the selected tags:if a tag's Apparently M>M.Traversing the mth hash value where SL variable is asserted multiple times,then the final value remains asserted.The consequence is equivalent to combining m =0,...,M-1,the reader forces tags hashed into mth the sets of selected tags.This is exactly the answer to the bits to reply at the above question of presence.Therefore,for the mth bit,the h'(t,r）modi (3)IEEE/ACM TRANSACTIONS ON NETWORKING 7 0 5 10 15 20 25 30 Time(ms) 0.35 0.4 0.45 0.5 Amplitude 1 1 0 0 1 0 0 0 0 1 2 3 4 5 6 7 t3 t2 Query Select RN16 t1,t4 BF Index Fig. 9: Baseband signals of acquiring an 8-bit BF across 3 tags. The bitmap totally contains 8 bits, each of which corresponds to an intercepted inventory. The three tags reply in the 1 st , 2 nd and 5 th inventory respectively, so the final BF equals [1, 1, 0, 0, 1, 0, 0, 0]. D. Acquiring a Bloom Filter So far, we have discussed how the TagMap reader deter￾mines if any tag outputs a given hash value. Now, we start to acquire a whole BF by considering three cases progressively: 1) Case 1: Acquisition with a Single Hash: We firstly consider a simplified case, namely, acquiring a 2 l -bit BF using a single hash function: h (l) (t, r). Correspondingly, the bitmap size M = 2l . The definition of hash bitmap indicates that: a tag t is hashed into the mth bit of the bitmap if and only if h (l) (t, r) = m for t ∈ T, where m = 0, . . . , M − 1. Namely, the index of the bitmap actually implies the hash value. We build a BF bit by bit, traversing the index from 0 to M − 1. When building the mth bit, we ask the question of presence like this: is there any tag whose hash value is equal to m? To do so, the reader initiates an intercepted inventory with the Select command of S(r, l, m). If the answer is positive, the mth bit of the BF is set to ‘1’; otherwise, ‘0’. This procedure continues until M bits are all traversed. Fig. 9 shows the baseband signals of acquiring an 8-bit BF across 3 tags. From the figure, we can observe 8 intercepted inventories. Zooming into any one of them, three distinct segments - Select, Query and RN16 - can be observed, exactly as same as a single intercepted inventory shown in Fig. 7. 2) Case 2: Acquisition with K Hashes: Secondly, we consider to acquire a 2 l -bit BF using K hash functions: h (l) (t, r1), . . . , h(l) (t, rK). In this case, the mth bit is set to ‘1’ when any one tag is hashed into the bit by any one of these K hash functions. Correspondingly, the question of presence turns to   {t|h (l) (t, r1) = m|| . . . ||h (l) (t, rK) = m}    > 0 for all t ∈ T. With regard to our hash function, the question can be expressed as follows: Problem 2. Is there any tag whose sub-bitstring ∈ [r1, r1 + l − 1), . . . , or ∈ [rK, rK + l − 1) in its MemBank3 is equal to m? Since each range corresponds to a Select, answering the above question requires K Selects. The result of multiple Select commands is a union of the selected tags: if a tag’s SL variable is asserted multiple times, then the final value remains asserted. The consequence is equivalent to combining the sets of selected tags. This is exactly the answer to the above question of presence. Therefore, for the mth bit, the 26 28 30 32 34 36 Time (ms) 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 Amplitude Select Select RN16 Query Select Select Query RN16 Intercepted Inventory Intercepted Inventory Fig. 10: Acquiring an BF with 2 hashes. There are two intercepted inventories. The baseband signals fo each inventory contains two Selects’ signals before the Query signals. reader initiates an intercepted inventory, which contains K Selects as follows: S(r1, l, m), S(r2, l, m), . . . , S(rK, l, m) (2) Similarly, if any RN16 signal is detected after the Query, the corresponding bit is set to ‘1’. Fig. 10 shows the baseband sig￾nals of two consecutive intercepted inventories when acquiring a BF with 2 hashes. From the figure, we can exactly observe two Select commands before the Query in an intercepted inventory. 3) Case 3: Acquisition with Arbitrary Size: The first two cases consider to generate BFs with size of M = 2l bit. The size M is a key parameter that directly determines acquisition overhead, and thereby should be well optimized. Lemma 2 implies the minimal (and optimal) size. Apparently, the minimal size of BF might not be exactly an exponent of 2. On the other hand, the hash values are stored in a binary format in the memory bank, so l must be an integer. As a result, the actual size M has to be set to 2 l and l = dlog2 Mce suppose Mc is the optimal size, such that M ≥ Mc and l is an integer. This setting is valid but might be extremely costly. For example, suppose the optimal size Mc = 257, we have to set actual size M = 2dlog2 257e = 512, which is almost double than the optimal one. To enable an arbitrary size, we define the operation of modulo to shrink the size, as used in other applications [46]. Apparently M ≥ Mc. Traversing the mth hash value where m = 0, . . . , M − 1, the reader forces tags hashed into mth bits to reply at the h l (t, r) mod Mc (3)