IEEE/ACM TRANSACTIONS ON NETWORKING 13 0.07 [58]try to design the protocol to fast search tag or estimate 0.08 ase the cardinality.[56]introduce bloom filter into the RFID tag searching but doesn't implement on commercial RFID system. 05 Case3 是 Tash [43]first implement the bloom filter on commercial RFID system but only implement on the application layer and its effi- ciency is limited.This work first enables the bloom filter on the 0.02 physical layer of commercial RFID system and dramatically 0.0 improve the collecting speed.The others [6]-[13].[59]aim on recovering the collisions to improve the efficiency of inventory. 5 10 0 Missing Rate(%)】 Buzz [6]decodes tag collisions bit by bit.It assumes the linear combination of the static channel coefficients of reflecting Fig.18:Detection accuracy tags independent of coexisting tags.BiGroup [59]recovers 15%and 20%of tags are randomly taken away.We run 50 collisions without modifying COTS tags,but instead,changes experimental trials and plot the detection accuracy in Fig.18. the readers.However,these works either require modifying Case 1:Using a single hash function.From the figure,it is tags or work under specific conditions.Our work provides a seen that 0.79%+0.3%to 5.2%+1.2%missing tags are universal and fast inventory service on the commercial RFID falsely detected when the missing rate increases from 5% systems. to 20%.All results are lower than the predefined tolerance BF Applications:The traditional inventory interrogates all of 25%.None of the false negatives are reported since the the tags,which makes it time-inefficient.These works [16] nature of the Bloom filter yields zero false negative. [18]proposed continuous reading protocols that can incremen- Case 2:Using 3 hash functions.Lemma 2 suggests the tally collect tags in each step by using a BF.Sheng et al.[16] appropriate number of hash functions k=3.In this case,we preserved the tags collected in the previous round and collected use 3 hash functions to create a 212-bit BF so that more'I's only unknown tags.Thereafter,many follow-up studies [19]- can be found in the bitmap to prove the presence of tags. [33]investigated the issue of false positives resulting from the This is confirmed by our tests:the error rate is reduced to slots.TagMap provides a fundamental service to boost these 2.4%+0.5%even the missing rate equals 20%,removing work almost half (41.65%)false detections in Case 1. IX.CONCLUSION Case 3:Using modulo operation.We use the modulo This work provides a fundamental service to today's com- operation to reduce the bitmap length from 4096 bits to 2396 mercial RFID Gen2 tags,which is dispensable for prior Bloom bits.The accuracy for Case 3 is quite similar to that for Case filter-based applications.A key innovation of this work is 2 (e.g.,2.9%+0.4%vs.2.4%+0.5%given missing rate of the physical-layer acquisition approach,which is a significant 20%)because both adopt same number of hash functions. step in overcoming the performance bottleneck of current The about 0.5%difference derives from the fact that the RFID systems.Our work provides new exciting avenues for modulo operation disturbs the randomness of bitmap,i.e., exploration in RFID system and its applications. moving trail bits to head bits. Summary.Three acquisition overheads have been compared ACKNOWLEDGMENTS in Fig.16(b)(i.e.,the scenario when n=1000),which Lei Yang and Lei Xie are the co-corresponding author.The implies that TagMap and an ImpinJ reader takes 1.9s and 15s research is supported by NSFC for Young Scientists of China to acquire a BF or identify 1000 tags respectively.In other (NO.61972331),NSFC General Program (NO.61902331), words,TagMap can accurately find out 1-(2.9%+0.4%)= NSFC Key Program (NO.61932017)and UGC/ECS (NO. 97.1%+0.4%of missing events within 2 seconds,whereas a 25222917).Lei Xie's research is supported by the National commercial reader requires 15 seconds to know these events. Natural Science Foundation of China under Grant Nos. 61872174,61832008. VIII.RELATED WORK TagMap is related to previous work in three areas. REFERENCES Design of Hash Function:Feldhofer and Rechberger [42] [I]“RFID Forecasts. Players and Opportunities 2017. stated that current common hash functions (e.g.,MD5,SHA-1, 2017,” https://www.idtechex.com/research/reports/ etc),are not hardware friendly and are unsuitable for RFID rfid-forecasts-players-and-opportunities-2017-2027-000546.asp. tags,which possess a constrained computing capability.Such [2]D.M.Dobkin,The RF in RFID:UHF RFID in Practice.Newnes. 2012. difficulty has spurred considerable research [34]-[42].De- [3]J.Wang.L.Chang.O.Abari,and S.Keshav,"Are rfid sensing systems spite these optimized designs,the majority of them are still ready for the real world?"in Proc.of ACM MobiSys,2019.pp.366-377. presented in theory and none is available for COTS RFID [4]L.Yang.Y.Chen,X.-Y.Li,C.Xiao,M.Li,and Y.Liu,"Tagoram:real- tags.Our work explores hash functions by leveraging selective time tracking of mobile rfid tags to high precision using cots devices," in Proc.of ACM MobiCom,2014. reading to emulate equivalent hash functions. [5]D.-H.Shih.P.-L.Sun,D.C.Yen,and S.-M.Huang,"Taxonomy Design of Communication Protocols.Plenty of work focus and survey of rfid anti-collision protocols,"Computer communications, on designing communication protocols to improve the effi- vol.29,no.11,Pp.2150-2166,2006. [6]J.Wang.H.Hassanieh,D.Katabi,and P.Indyk,"Efficient and reliable ciency of inventory and tag detection.Some [22],[43],[55]- low-power backscatter networks,"in Proc.of ACM S/GCOMM.2012.IEEE/ACM TRANSACTIONS ON NETWORKING 13 5 10 15 20 Missing Rate(%) 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 Error Rate Case1 Case2 Case3 Fig. 18: Detection accuracy 15% and 20% of tags are randomly taken away. We run 50 experimental trials and plot the detection accuracy in Fig. 18. • Case 1: Using a single hash function. From the figure, it is seen that 0.79% ± 0.3% to 5.2% ± 1.2% missing tags are falsely detected when the missing rate increases from 5% to 20%. All results are lower than the predefined tolerance of 25%. None of the false negatives are reported since the nature of the Bloom filter yields zero false negative. • Case 2: Using 3 hash functions. Lemma 2 suggests the appropriate number of hash functions k = 3. In this case, we use 3 hash functions to create a 2 12-bit BF so that more ‘1’s can be found in the bitmap to prove the presence of tags. This is confirmed by our tests: the error rate is reduced to 2.4% ± 0.5% even the missing rate equals 20%, removing almost half (41.65%) false detections in Case 1. • Case 3: Using modulo operation. We use the modulo operation to reduce the bitmap length from 4096 bits to 2396 bits. The accuracy for Case 3 is quite similar to that for Case 2 (e.g., 2.9% ±0.4% vs. 2.4% ±0.5% given missing rate of 20%) because both adopt same number of hash functions. The about 0.5% difference derives from the fact that the modulo operation disturbs the randomness of bitmap, i.e., moving trail bits to head bits. Summary. Three acquisition overheads have been compared in Fig. 16(b) (i.e., the scenario when n = 1000), which implies that TagMap and an ImpinJ reader takes 1.9s and 15s to acquire a BF or identify 1000 tags respectively. In other words, TagMap can accurately find out 1 − (2.9% ± 0.4%) = 97.1% ± 0.4% of missing events within 2 seconds, whereas a commercial reader requires 15 seconds to know these events. VIII. RELATED WORK TagMap is related to previous work in three areas. Design of Hash Function: Feldhofer and Rechberger [42] stated that current common hash functions (e.g., MD5, SHA-1, etc), are not hardware friendly and are unsuitable for RFID tags, which possess a constrained computing capability. Such difficulty has spurred considerable research [34]–[42]. De￾spite these optimized designs, the majority of them are still presented in theory and none is available for COTS RFID tags. Our work explores hash functions by leveraging selective reading to emulate equivalent hash functions. Design of Communication Protocols. Plenty of work focus on designing communication protocols to improve the effi- ciency of inventory and tag detection. Some [22], [43], [55]– [58] try to design the protocol to fast search tag or estimate the cardinality. [56] introduce bloom filter into the RFID tag searching but doesn’t implement on commercial RFID system. Tash [43] first implement the bloom filter on commercial RFID system but only implement on the application layer and its effi- ciency is limited. This work first enables the bloom filter on the physical layer of commercial RFID system and dramatically improve the collecting speed. The others [6]–[13], [59] aim on recovering the collisions to improve the efficiency of inventory. Buzz [6] decodes tag collisions bit by bit. It assumes the linear combination of the static channel coefficients of reflecting tags independent of coexisting tags. BiGroup [59] recovers collisions without modifying COTS tags, but instead, changes the readers. However, these works either require modifying tags or work under specific conditions. Our work provides a universal and fast inventory service on the commercial RFID systems. BF Applications: The traditional inventory interrogates all the tags, which makes it time-inefficient. These works [16]– [18] proposed continuous reading protocols that can incremen￾tally collect tags in each step by using a BF. Sheng et al. [16] preserved the tags collected in the previous round and collected only unknown tags. Thereafter, many follow-up studies [19]– [33] investigated the issue of false positives resulting from the slots. TagMap provides a fundamental service to boost these work. IX. CONCLUSION This work provides a fundamental service to today’s com￾mercial RFID Gen2 tags, which is dispensable for prior Bloom filter-based applications. A key innovation of this work is the physical-layer acquisition approach, which is a significant step in overcoming the performance bottleneck of current RFID systems. Our work provides new exciting avenues for exploration in RFID system and its applications. ACKNOWLEDGMENTS Lei Yang and Lei Xie are the co-corresponding author. The research is supported by NSFC for Young Scientists of China (NO. 61972331), NSFC General Program (NO. 61902331), NSFC Key Program (NO. 61932017) and UGC/ECS (NO. 25222917). Lei Xie’s research is supported by the National Natural Science Foundation of China under Grant Nos. 61872174, 61832008. REFERENCES [1] “RFID Forecasts, Players and Opportunities 2017- 2017,” https://www.idtechex.com/research/reports/ rfid-forecasts-players-and-opportunities-2017-2027-000546.asp. [2] D. M. Dobkin, The RF in RFID: UHF RFID in Practice. Newnes, 2012. [3] J. Wang, L. Chang, O. Abari, and S. Keshav, “Are rfid sensing systems ready for the real world?” in Proc. of ACM MobiSys, 2019, pp. 366–377. [4] L. Yang, Y. Chen, X.-Y. Li, C. Xiao, M. Li, and Y. Liu, “Tagoram: real￾time tracking of mobile rfid tags to high precision using cots devices,” in Proc. of ACM MobiCom, 2014. [5] D.-H. Shih, P.-L. Sun, D. C. Yen, and S.-M. Huang, “Taxonomy and survey of rfid anti-collision protocols,” Computer communications, vol. 29, no. 11, pp. 2150–2166, 2006. [6] J. Wang, H. Hassanieh, D. Katabi, and P. Indyk, “Efficient and reliable low-power backscatter networks,” in Proc. of ACM SIGCOMM, 2012