IEEE/ACM TRANSACTIONS ON NETWORKING Tags 2 4 5 6 Time(s) USRP Reade Fig.15:Ten-second reading trace pinJ Reade because ImpinJ reader's anti-collision processing uses a ran- Antenna domized algorithm (an ALOHA variant),while our approach is a deterministic algorithm(discuss later). Fig.14:Experimental scenario.Total 1,000 tags are densely deployed in a small area. B.Acquisition Overhead VII.EVALUATION We are interested in evaluating the acquisition overhead as Our experiments are performed in our office lounge.A total function of tag number (i.e.,n).The overhead is defined as of 1000 tags are densely attached to plastic panels1.The office the time consumed in acquiring tags or a data structure like section has a size of 3x 3x 2.5m3,as shown in Fig.14.Many BF for representing them. sofas and tables are in the lounge.To fully cover numerous TagMap overhead across three cases.Although BF is a tags,we use a 12 dBi large antenna.The transmitting power randomized data structure,the acquisition overhead is deter- is fixed at 30 dBm.The USRP reader is connected to a 64-bit ministic.The overhead depends on the bitmap size M and MacBook with 2.8GHz Intel Core i7 for running GNURadio. the number of hashes K.Let Ts,To and TRN denote the Test Suite.We begin with a group of microbenchmark ex- time consumed on transmitting the Select,Query and periments to provide insights into the performance of TagMap RN16.As shown in Fig.4,each intercepted inventory takes with comparison with commercial readers.All EPCs are stored K.(T's+T1)+To+T2+TRN+T3 where T1,T2 and T3 are the in database and known to upper applications.This assumption constant spaces specified in Gen2.Thus,the total overhead C is reasonable and necessary because identifying if a tag is is given by missing or under tracking without any prior knowledge of its C=M(K.(Ts+T)+TQ+T2+TRN +T3) existence is impossible.The tolerance of BF is set to 0.25 by default. Thus,as long as two parameters are certain,the acquisition Baselines.To be fair to TagMap,we only focus on overhead of BF is a constant.This is why the tag is always practical techniques without considering previous simulation- regularly identified by TagMap reader in Fig.15.Next,we driven evaluation.We compare TagMap against two baseline measure the overhead with respect to the three cases discussed schemes:a commercial reader (i.e.,ImpinJ reader)[48]and in Sec.IV-D.The results are shown in Fig.16(a)and under- Tash [43].As the commercial reader collects all tags in the stood as follows: range,its inventory results are used as the ground truth. In the first case,the minimal size M=[n/In2]when keeping K=1 (see Lemma 2)without using modulo.It seems that the overhead should be linearly proportional to A.Reading Rate n,i.e.,C[n/In2].Actually,the figure shows that the To better understand how TagMap reader improves the overhead increases step by step.This is because the hash value reading rate,Fig.15 shows a 10-second reading trace of a is represented in a binary form,we have to set the actual size tag.We totally deploy 140 tags in the surveillance region and M =2floga m =2floga(n/In 2)1,making C2floga(n/In2)1. randomly select one tag to show it reading trace.These tags are We can exactly observe the turning points appearing at n= inventoried by an ImpinJ and a TagMap reader respectively. [2ln21,「41n21,「8n21,…=..,89,178,355,719,. In the figure,the red (higher)and gray (lower)bars indicate The second case considers using multiple hash func- the tag is identified by the ImpinJ and TagMap reader re- tion to lower the false positives.The Lemmas suggest spectively.We can visually observe that the tag is much more that M=「nlog2e·log2(1/0.3)l=[2.5 n]and K= frequently identified by TagMap reader than the ImpinJ reader. [ln 2l0g2(e)log2(1/0.25)1=2.Thus,the actual size In particular,TagMap reader achieves a mean reading rate of M -2floga(2.5n)1.Similar to the first case,many steps 16Hz,outperforming ImpinJ(i.e.,0.8Hz)by 18x higher.Such are observed when n=[2/2.5l,「4/2.51，「8/2.5l,·= outperformance is achieved because TagMap reader removes ...,103,205,410,820,....Compared with the first case,this the time-consuming processing for anti-collision.In addition, case consumes about double time.These the extra time is it can be seen that the tag is identified in a random manner by consumed on two Selects in each bit-driven intercepted the ImpinJ reader but regularly by the TagMap reader.This is inventory. The third case adopts modulo to fit the optimal size. IThe deployment mode (like grid)does not affect the performance as long Since this case adopts the same settings as that of the second as each tag can be identified. case (i.e.,M=2nloga(2.5n)1 and K=2).the turning pointsIEEE/ACM TRANSACTIONS ON NETWORKING 11 USRP Reader ImpinJ Reader Antenna Tags Antenna Fig. 14: Experimental scenario. Total 1, 000 tags are densely deployed in a small area. VII. EVALUATION Our experiments are performed in our office lounge. A total of 1000 tags are densely attached to plastic panels 1 . The office section has a size of 3×3×2.5m3 , as shown in Fig. 14. Many sofas and tables are in the lounge. To fully cover numerous tags, we use a 12 dBi large antenna. The transmitting power is fixed at 30 dBm. The USRP reader is connected to a 64-bit MacBook with 2.8GHz Intel Core i7 for running GNURadio. Test Suite. We begin with a group of microbenchmark ex￾periments to provide insights into the performance of TagMap with comparison with commercial readers. All EPCs are stored in database and known to upper applications. This assumption is reasonable and necessary because identifying if a tag is missing or under tracking without any prior knowledge of its existence is impossible. The tolerance of BF is set to 0.25 by default. Baselines. To be fair to TagMap, we only focus on practical techniques without considering previous simulation￾driven evaluation. We compare TagMap against two baseline schemes: a commercial reader (i.e., ImpinJ reader) [48] and Tash [43]. As the commercial reader collects all tags in the range, its inventory results are used as the ground truth. A. Reading Rate To better understand how TagMap reader improves the reading rate, Fig. 15 shows a 10-second reading trace of a tag. We totally deploy 140 tags in the surveillance region and randomly select one tag to show it reading trace. These tags are inventoried by an ImpinJ and a TagMap reader respectively. In the figure, the red (higher) and gray (lower) bars indicate the tag is identified by the ImpinJ and TagMap reader re￾spectively. We can visually observe that the tag is much more frequently identified by TagMap reader than the ImpinJ reader. In particular, TagMap reader achieves a mean reading rate of 16Hz, outperforming ImpinJ (i.e., 0.8Hz) by 18× higher. Such outperformance is achieved because TagMap reader removes the time-consuming processing for anti-collision. In addition, it can be seen that the tag is identified in a random manner by the ImpinJ reader but regularly by the TagMap reader. This is 1The deployment mode (like grid) does not affect the performance as long as each tag can be identified. TagMap ImpinJ 0 1 2 3 4 5 6 7 8 9 10 Time(s) Fig. 15: Ten-second reading trace because ImpinJ reader’s anti-collision processing uses a ran￾domized algorithm (an ALOHA variant), while our approach is a deterministic algorithm (discuss later). B. Acquisition Overhead We are interested in evaluating the acquisition overhead as function of tag number (i.e., n). The overhead is defined as the time consumed in acquiring tags or a data structure like BF for representing them. TagMap overhead across three cases. Although BF is a randomized data structure, the acquisition overhead is deter￾ministic. The overhead depends on the bitmap size M and the number of hashes K. Let TS, TQ and TRN denote the time consumed on transmitting the Select, Query and RN16. As shown in Fig. 4, each intercepted inventory takes K ·(TS +τ1)+TQ +τ2+TRN +τ3 where τ1, τ2 and τ3 are the constant spaces specified in Gen2. Thus, the total overhead C is given by C = M (K · (TS + τ1) + TQ + τ2 + TRN + τ3) Thus, as long as two parameters are certain, the acquisition overhead of BF is a constant. This is why the tag is always regularly identified by TagMap reader in Fig. 15. Next, we measure the overhead with respect to the three cases discussed in Sec.IV-D. The results are shown in Fig. 16(a) and under￾stood as follows: • In the first case, the minimal size Mc = dn/ ln 2e when keeping K = 1 (see Lemma 2) without using modulo. It seems that the overhead should be linearly proportional to n, i.e., C ∼ dn/ ln 2e. Actually, the figure shows that the overhead increases step by step. This is because the hash value is represented in a binary form, we have to set the actual size M = 2dlog2 Mce = 2dlog2 (n/ ln 2)e , making C ∼ 2 dlog2 (n/ ln 2)e . We can exactly observe the turning points appearing at n = d2 ln 2e, d4 ln 2e, d8 ln 2e, · · · = . . . , 89, 178, 355, 719, . . . . • The second case considers using multiple hash func￾tion to lower the false positives. The Lemmas suggest that Mc = dn log2 e · log2 (1/0.3)e = d2.5ne and K = dln 2 log2 (e) log2 (1/0.25)e = 2. Thus, the actual size M = 2dlog2 (2.5n)e . Similar to the first case, many steps are observed when n = d2/2.5e, d4/2.5e, d8/2.5e, · · · = . . . , 103, 205, 410, 820, . . . . Compared with the first case, this case consumes about double time. These the extra time is consumed on two Selects in each bit-driven intercepted inventory. • The third case adopts modulo to fit the optimal size. Since this case adopts the same settings as that of the second case (i.e., M = 2dlog2 (2.5n)e and K = 2), the turning points