IEEE/ACM TRANSACTIONS ON NETWORKING 9 03 high accuracy is required,the traditional per-tag collection 02 should be used. 0.2 G=1.0 2)The tolerance is the leading factor that affects the per- =0.13 0.15 formance of TagMap.Particularly,when the s>0.13, 0.1 TagMap performs always better than the Q-Adaptive re- 0.0 gardless of how many tags participate.By contrast,the 200300 0mte6igstmo00o0 5000 number of tags has a relatively limited impact on the performance than the tolerance.For example,TagMap is Fig.12:The overhead ratio of TagMap to Q-Adaptive.The performance of TagMap is better than Q-Adaptive when the radio still better than Q-Adaptive with a very small number G<1.0.Particularly,TagMap is always better than Q-Adaptive of tags (e.g.,n<100)when s>0.13.On the other regardless of how many tags participate when the tolerance>0.13. hand,the overhead ratio is linearly reduced approximately as the number of tags increases,namely,the earnings of clarity,we assume they are approximately equal;(2)the length TagMap are higher in handling a large number of tags, of an EPC is 96 bits but its transmission involves a 22-bit when remaining the tolerance unchanged. preamble and a 16-bit CRC;(3)the guard intervals between In summary,the use of Bloom filter with TagMap has the commands and replies are ignored because they are extremely applicable limits.The performance might be worse than col- small compared with the intervals of data transmissions;(4) lecting tags one by one when pursuing a higher accuracy.In the lengths of some commands with variable fields (like this situation,we advise to automatically switch the system Select and Query)are estimated using the average. back to the traditional mode Approximately,it takes about 25us for the transmission of each bit.The delay (i.e.,TDelay)in commercial readers VI.SYSTEM IMPLEMENTATION (e.g..ImpinJ R420)is around 30 ms based on our empirical A.TagMap Reader measurements.Substituting the above parameters into Egn.5 and Eqn.6 respectively,the two precise cost formulas are We implement a prototype of TagMap reader by using finally updated as follows: a USRP N210 software defined radio equipped with SBX daughterboard [51]and two directional antennas.The imple- C0Adpe(n)=(3000+(37+22+25+134)·25)·n mentation is based on [52]and integrates TagMap's design +(37+25)·(ne In n-n).25 into the EPC Gen2 protocol.We release the source code of =8450n+1550(ne1nn-n) TagMap [53].The architecture of the TagMap reader is shown CTaMap(n,e)=「1.44n1og2(1/e)1(「0.99811og2(1/e)1·91+37+22)·25 in Fig.13. =「1.44n1og2(1/e)1(f0.99811og2(1/e)1·91+59)·25 Architecture.The TagMap reader consists of the follow- To quantify how n and s affect the performance of TagMap,we ing components:USRP Source,Gate,Tag Decoder,Reader define the overhead ratio of TagMap to Q-Adaptive,denoted Encoder and USRP Sink. by G(n,)as follows: USRP Source:The first block is to acquire samples from G(n,e）=CgMp(m,e) the USRP hardware.In our experiment,the ADC is set to Co-Ad山ptie(n)】 (6) 2MS/s,resulting in 50 samples for each tag bit. = [1.44n1og2(1/e)1(f0.99811og2(1/e)1·91+59)·25 8450n+1550(ne In n-n) Gate:The reader always provides continuous signals to tags,thus is full duplex (i.e.,transmitting and receiving Apparently,TagMap performs better than Q-Adaptive only simultaneously).This block is used to track the Query and when and only when the G(n,s)<1.0;otherwise,the best Ack commands,and trigger the processing of tags'replies solution is to collect all tags one by one with the Q-Adaptive. Tag Decoder:This block is to detect tags'RN16 reply sig- Fig.12 shows the results of the overhead ratio as functions nals like preamble correlation,synchronization and channel of a variable number of tags (i.e.,100 <n 10000)and a estimation. variable tolerance (i.e.,0<<1).From the figure,we have Reader Encoder:This block is to implement the reader the two important findings: commands.Depending on the output of the tag decoder 1)TagMap performs better than Q-Adaptive in the white block,the reader create the next commands.Although this area where the smallest tolerance is set to 0.07.This work only requires the commands of Select and Query, suggests that the tolerance cannot be too small.This result we implement all other Gen2 commands (i.e.,QueryRep, is reasonable because the philosophy behind Bloom filter QueryAdust,Ack),as well as the Q-adaptive algorithm. is to save the procedure in time or space at the cost of USRP Sink:This block is to propagate the reader command accuracy [46].It is suitable for the application scenarios to the USRP hardware.We set the UHD gain of USRP to 20 which can tolerate a relatively higher false positive rate dB at a frequency during 902~928 MHz.We utilize a RF In our scenario like the detection of missing tags,the amplifier to increase the transmitting power to 30 dBm.The system would acquire the Bloom filter repeatedly.Even ADC rate is configured to 2 MS/s. using a relatively higher tolerance (e.g.,=0.25),the Transmission.The EPC Gen2 requires a reader to contin- tag can be identified within two rounds with an extremely uously generate a high-power CW.Two links are involved. high probability (e.g.,1-0.25 *0.25 =0.9375).Thus,The first link is data transmission from reader-tag,which the tolerance of 0.25 is acceptable.However,when a is often called downlink transmission.The second link is theIEEE/ACM TRANSACTIONS ON NETWORKING 9 100 200 300 500 1000 2000 3000 5000 10000 Number of tags (n) 0.05 0.1 0.15 0.2 0.25 0.3 Tolerance ( ) 0 0.5 1 1.5 2 2.5 3 3.5 G=0.5 G=1.0 " =0.13 " =0.07 Fig. 12: The overhead ratio of TagMap to Q-Adaptive. The performance of TagMap is better than Q-Adaptive when the radio G < 1.0. Particularly, TagMap is always better than Q-Adaptive regardless of how many tags participate when the tolerance > 0.13. clarity, we assume they are approximately equal; (2) the length of an EPC is 96 bits but its transmission involves a 22-bit preamble and a 16-bit CRC; (3) the guard intervals between commands and replies are ignored because they are extremely small compared with the intervals of data transmissions; (4) the lengths of some commands with variable fields (like Select and Query) are estimated using the average. Approximately, it takes about 25µs for the transmission of each bit. The delay (i.e., TDelay) in commercial readers (e.g., ImpinJ R420) is around 30 ms based on our empirical measurements. Substituting the above parameters into Eqn. 5 and Eqn. 6 respectively, the two precise cost formulas are finally updated as follows: CQ-Adaptive(n) = (3000 + (37 + 22 + 25 + 134) · 25) · n + (37 + 25) · (ne ln n − n) · 25 = 8450n + 1550(ne ln n − n) CTagMap(n, ε) = d1.44n log2 (1/ε)e (d0.9981 log2 (1/ε)e · 91 + 37 + 22) · 25 = d1.44n log2 (1/ε)e (d0.9981 log2 (1/ε)e · 91 + 59) · 25 To quantify how n and ε affect the performance of TagMap, we define the overhead ratio of TagMap to Q-Adaptive, denoted by G(n, ε), as follows: G(n, ε) = CTagMap(n, ε) CQ-Adaptive(n) = d1.44n log2 (1/ε)e (d0.9981 log2 (1/ε)e · 91 + 59) · 25 8450n + 1550(ne ln n − n) (6) Apparently, TagMap performs better than Q-Adaptive only when and only when the G(n, ε) < 1.0; otherwise, the best solution is to collect all tags one by one with the Q-Adaptive. Fig. 12 shows the results of the overhead ratio as functions of a variable number of tags (i.e., 100 ≤ n ≤ 10000) and a variable tolerance (i.e., 0 < ε < 1). From the figure, we have the two important findings: 1) TagMap performs better than Q-Adaptive in the white area where the smallest tolerance is set to 0.07. This suggests that the tolerance cannot be too small. This result is reasonable because the philosophy behind Bloom filter is to save the procedure in time or space at the cost of accuracy [46]. It is suitable for the application scenarios which can tolerate a relatively higher false positive rate. In our scenario like the detection of missing tags, the system would acquire the Bloom filter repeatedly. Even using a relatively higher tolerance (e.g., ε = 0.25), the tag can be identified within two rounds with an extremely high probability (e.g., 1 − 0.25 ∗ 0.25 = 0.9375). Thus, the tolerance of 0.25 is acceptable. However, when a high accuracy is required, the traditional per-tag collection should be used. 2) The tolerance is the leading factor that affects the per￾formance of TagMap. Particularly, when the ε > 0.13, TagMap performs always better than the Q-Adaptive re￾gardless of how many tags participate. By contrast, the number of tags has a relatively limited impact on the performance than the tolerance. For example, TagMap is still better than Q-Adaptive with a very small number of tags (e.g., n < 100) when ε > 0.13. On the other hand, the overhead ratio is linearly reduced approximately as the number of tags increases, namely, the earnings of TagMap are higher in handling a large number of tags, when remaining the tolerance unchanged. In summary, the use of Bloom filter with TagMap has the applicable limits. The performance might be worse than col￾lecting tags one by one when pursuing a higher accuracy. In this situation, we advise to automatically switch the system back to the traditional mode . VI. SYSTEM IMPLEMENTATION A. TagMap Reader We implement a prototype of TagMap reader by using a USRP N210 software defined radio equipped with SBX daughterboard [51] and two directional antennas. The imple￾mentation is based on [52] and integrates TagMap’s design into the EPC Gen2 protocol. We release the source code of TagMap [53]. The architecture of the TagMap reader is shown in Fig. 13. Architecture. The TagMap reader consists of the follow￾ing components: USRP Source, Gate, Tag Decoder, Reader Encoder and USRP Sink. • USRP Source: The first block is to acquire samples from the USRP hardware. In our experiment, the ADC is set to 2MS/s, resulting in 50 samples for each tag bit. • Gate: The reader always provides continuous signals to tags, thus is full duplex (i.e., transmitting and receiving simultaneously). This block is used to track the Query and Ack commands, and trigger the processing of tags’ replies. • Tag Decoder: This block is to detect tags’ RN16 reply sig￾nals like preamble correlation, synchronization and channel estimation. • Reader Encoder: This block is to implement the reader commands. Depending on the output of the tag decoder block, the reader create the next commands. Although this work only requires the commands of Select and Query, we implement all other Gen2 commands (i.e., QueryRep, QueryAdust, Ack), as well as the Q-adaptive algorithm. • USRP Sink: This block is to propagate the reader command to the USRP hardware. We set the UHD gain of USRP to 20 dB at a frequency during 902 ∼ 928 MHz. We utilize a RF amplifier to increase the transmitting power to 30 dBm.The ADC rate is configured to 2 MS/s. Transmission. The EPC Gen2 requires a reader to contin￾uously generate a high-power CW. Two links are involved. The first link is data transmission from reader → tag, which is often called downlink transmission. The second link is the