based identification protocols.the reader detects whether any ReFERENcES tag-tag collision occurs and adaptively divides the tag set into [1]"Alien Technology",http://www.alientechnology.com small subsets until all tags are successfully identified.While [2]"CVX Research",http://evxr.com/cvx/ the RFID identification protocols can be directly borrowed to [3]"EPCglobal CIG2".http://www.epcglobalinc.org/standards/uhfe1g2 address the missing tag identification problem,the processing [4]“Ettus Research”,http:/lwww.ettus.com [5]"Gen 2 RFID Tools",https://www.cgran.org/wiki/Gen2 time increases with the number of tags and renders such [⑥“ei-Magic'”,http://users.ece.gatech.edu/justin/11magic/ approaches inefficient for monitoring large number of tags. [7]S.Boyd,"Convex Optimization".Cambridge University Press,2004. Many cardinality estimation protocols estimate the number [8]M.Buettner and D.Wetherall,"An Empirical Study of UHF RFID Performance",in ACM MobiCom,2008. of tags [15,20,32],which may serve as primary inputs for [9]E.Candes,J.Romberg,T.Tao,"Stable Signal Recovery from Incomplete missing tag identification.Such approaches,however,cannot and Inaccurate Measurements",Communications on Pure and Applied be directly borrowed to detect the missing tag events since Mathematics,vol.59,issue 9.pp.1207-1223,2006. they only provide a rough estimation of tag cardinality. [10]J.I.Capetanakis,"Tree algorithms for packet broadcast channels",IEEE Trans.on Information Theory,vol.25,issue 5,pp.505-515,1979. Recent works study the problem of tag monitoring and [11]P.-Y.Chen,W.-T.Chen.Y.-C.Tseng."Providing Group Tour Guide by identify the missing tags [28].In [22],Tan et al.present a RFIDs and Wireless Sensor Networks",IEEE Transcations on Wireless missing tag monitoring protocol which can detect the missing Communications,vol.8.issue 6,pp.3059-3067,2009. [12]D.Donoho,"Compressed sensing",IEEE Transactions on Information tag events when the number of missing tags exceeds a user- Theory,vol.52.issue4,pp.1289-1306.2006. defined threshold.In [16,Li et al.propose a missing tag [13]J.Gummeson,P.Zhang.D.Ganesan,"Flit:A Bulk Transmission identification protocol which can detect the missing tag events Protocol for RFID-Scale Sensors",in ACM MobiSys,2012. with certainty and identify the missing ones.Zhang et al.[28] [14]D.Guo,Y.Liu,X.Li,and P.Yang,"False Negative Problem of Counting Bloom Filter",IEEE Trans.on Knowledge and Data Engineering,vol. significantly reduce the missing tag identification time by more 22,issue5,Pp.651-664.2010. efficiently scheduling and utilizing multiple readers.Unlike the [15]H.Han,B.Sheng,C.C.Tan,Q.Li,W.Mao,and S.Lu,"Counting existing approaches which focus on upper layer information, RFID Tags Efficiently and Anonymously",in /EEE INFOCOM.2010. our approach effectively leverages the aggregated responses in [16]T.Li,S.Chen,and Y.Ling,"Identifying the Missing Tags in a Large RFID System",in ACM MobiHoc,2010. the physical layer to improve the monitoring efficiency. [17]C.Luo,F.Wu,J.Sun,C.W.Chen."Compressive Data Gathering for Many works study the problem of collecting data from com- Large-Scale Wireless Sensor Networks",in ACM MobiCom,2009. putational RFID tags integrated with various sensors.Yue et al. [18]L.M.Ni,Y.Liu,Y.C.Lau,and A.Patil,"LANDMARC:Indoor [25]present a data collection approach using the Bloom filter. Location Sensing Using Active RFID",ACM Wireless Networks,vol. 10,issue6,pPp.701-710,2004. Flit [13]improves the throughput of data transmission through [19]C.Qian,Y.Liu,H.-L.Ngan,and L.M.Ni,"ASAP:Scalable Identifi- a bulk transmission.BLINK [30]improves the link layer cation and Counting for Contactless RFID Systems",in /EEE /CDCS, performance with link quality measurement,mobility predic- 2010. tion,and rate adaptation for RFID communication.Buzz [23] [20]C.Qian.H.Ngan,and Y.Liu,"Cardinality Estimation for Large-scale RFID Systems",IEEE Trans.on Parallel and Distributed Systems,vol. presents an efficient and reliable data collection approach for 22,issue9,pp.1441-1454,2011. RFID systems leveraging physical layer information.Zanetti [21]L.G.Roberts,"Aloha Packet System with and without Slots and Capture et al.[26]study the problem of classifying different RFID "ACM SIGCOMM Computer Communication Review,vol.5.issue 2. pp.28-42,1975 tags using the physical layer fingerprints.Although targeting at [22]C.C.Tan,B.Sheng,and Q.Li."How to Monitor for Missing RFID totally different problems,the common rationale behind those Tags",in IEEE ICDCS,2008. works and our approach is that careful cross layer designs may [23]J.Wang,H.Hassanieh,D.Katabi,P.Indyk,"Efficient and Reliable Low-Power Backscatter Networks".in ACM SIGCOMM,2012 significantly improve the performance of RFID systems. 24]L.Yang,J.Han,Y.Qi,C.Wang,T.Gu,and Y.Liu,"Season:Shelving Interference and Joint Identification in Large-scale RFID Systems",in VII.CONCLUSION IEEE INFOCOM.2011. In this paper,we study the missing tag identification [25]H.Yue,C.Zhang,M.Pan,Y.Fang,S.Chen,"A Time-efficient Information Collection Protocol for Large-scale RFID Systems",in /EEE problem in large-scale RFID systems.We propose P-MTI to INFOCOM,2012. leverage physical layer information and substantially improve [26]D.Zanetti,B.Danev,S.Capkun,"Physical-layer Identification of UHF monitoring efficiency.We further present several optimization RFID Tags".in ACM MobiCom,2010. techniques to improve the performance.P-MTI leverages the [27]C.Zhang,Y.Zhang,Y.Fang,"A coverage inference protocol for wireless sensor networks",IEEE Transactions on Mobile Computing.vol.9.issue sparsity of missing tag events and reconstructs tag responses 6,pp.850-864,June2010. through compressive sensing.To validate its efficacy,we [28]R.Zhang.Y.Liu,Y.Zhang,and J.Sun,"Fast Identification of the implement a prototype system and extend the EPCglobal Gen- Missing Tags in a Large RFID System",in IEEE SECON,2011. 2 standard based on the GNURadio/USRP and WISP plat- [29]H.Zhang.J.Gummeson,B.Ransford,and K.Fu,"Moo:A batteryless computational RFID and sensing platform",Tech Report UMASS.2011. form.We do extensive evaluation of P-MTI with large-scale http://spqr.cs.umass.edu/moo/ simulations.The results demonstrate that P-MTI substantially [30]P.Zhang.J.Gummeson,D.Ganesan,"BLINK:A High Throughput outperforms the state-of-the-art schemes Link Layer for Backscatter Communication",in ACM MobiSys,2012. [31]Y.Zhang,L.T.Yang,and J.Chen "RFID and Sensor Networks:Archi- tectures,Protocols,Security and Integrations",Auerbach Publications, ACKNOWLEDGMENT 2010. We acknowledge the support from NTU Nanyang As- [32]Y.Zheng,M.Li,and C.Qian,"PET:Probabilistic Estimating Tree for Large-Scale RFID Estimation",in IEEE /CDCS,2011. sistant Professorship (NAP)grant M4080738.020,Microsoft [33]Y.Zheng and M.Li."Fast Tag Searching Protocol for Large-Scale RFID research grant FY12-RES-THEME-001,and NSFC grant No. Systems",in IEEE ICNP,2011. 61272456.based identification protocols, the reader detects whether any tag-tag collision occurs and adaptively divides the tag set into small subsets until all tags are successfully identified. While the RFID identification protocols can be directly borrowed to address the missing tag identification problem, the processing time increases with the number of tags and renders such approaches inefficient for monitoring large number of tags. Many cardinality estimation protocols estimate the number of tags [15, 20, 32], which may serve as primary inputs for missing tag identification. Such approaches, however, cannot be directly borrowed to detect the missing tag events since they only provide a rough estimation of tag cardinality. Recent works study the problem of tag monitoring and identify the missing tags [28]. In [22], Tan et al. present a missing tag monitoring protocol which can detect the missing tag events when the number of missing tags exceeds a user￾defined threshold. In [16], Li et al. propose a missing tag identification protocol which can detect the missing tag events with certainty and identify the missing ones. Zhang et al. [28] significantly reduce the missing tag identification time by more efficiently scheduling and utilizing multiple readers. Unlike the existing approaches which focus on upper layer information, our approach effectively leverages the aggregated responses in the physical layer to improve the monitoring efficiency. Many works study the problem of collecting data from com￾putational RFID tags integrated with various sensors. Yue et al. [25] present a data collection approach using the Bloom filter. Flit [13] improves the throughput of data transmission through a bulk transmission. BLINK [30] improves the link layer performance with link quality measurement, mobility predic￾tion, and rate adaptation for RFID communication. Buzz [23] presents an efficient and reliable data collection approach for RFID systems leveraging physical layer information. Zanetti et al. [26] study the problem of classifying different RFID tags using the physical layer fingerprints. Although targeting at totally different problems, the common rationale behind those works and our approach is that careful cross layer designs may significantly improve the performance of RFID systems. VII. CONCLUSION In this paper, we study the missing tag identification problem in large-scale RFID systems. We propose P-MTI to leverage physical layer information and substantially improve monitoring efficiency. We further present several optimization techniques to improve the performance. P-MTI leverages the sparsity of missing tag events and reconstructs tag responses through compressive sensing. To validate its efficacy, we implement a prototype system and extend the EPCglobal Gen- 2 standard based on the GNURadio/USRP and WISP plat￾form. We do extensive evaluation of P-MTI with large-scale simulations. The results demonstrate that P-MTI substantially outperforms the state-of-the-art schemes. ACKNOWLEDGMENT We acknowledge the support from NTU Nanyang As￾sistant Professorship (NAP) grant M4080738.020, Microsoft research grant FY12-RES-THEME-001, and NSFC grant No. 61272456. REFERENCES [1] “Alien Technology”, http://www.alientechnology.com [2] “CVX Research”, http://cvxr.com/cvx/ [3] “EPCglobal ClG2”, http://www.epcglobalinc.org/standards/uhfc1g2 [4] “Ettus Research”, http://www.ettus.com [5] “Gen 2 RFID Tools”, https://www.cgran.org/wiki/Gen2 [6] “`1-Magic”, http://users.ece.gatech.edu/ justin/l1magic/ [7] S. Boyd, “Convex Optimization”, Cambridge University Press, 2004. [8] M. Buettner and D. Wetherall, “An Empirical Study of UHF RFID Performance”, in ACM MobiCom, 2008. [9] E. Candes, J. Romberg, T. Tao, “Stable Signal Recovery from Incomplete ` and Inaccurate Measurements”, Communications on Pure and Applied Mathematics, vol. 59, issue 9. pp. 1207-1223, 2006. [10] J. I. Capetanakis, “Tree algorithms for packet broadcast channels”, IEEE Trans. on Information Theory, vol. 25, issue 5, pp. 505-515, 1979. [11] P.-Y. Chen, W.-T. Chen, Y.-C. Tseng, “Providing Group Tour Guide by RFIDs and Wireless Sensor Networks”, IEEE Transcations on Wireless Communications, vol. 8, issue 6, pp. 3059-3067, 2009. [12] D. Donoho, “Compressed sensing”, IEEE Transactions on Information Theory, vol. 52, issue 4, pp. 1289-1306, 2006. [13] J. Gummeson, P. Zhang, D. Ganesan, “Flit: A Bulk Transmission Protocol for RFID-Scale Sensors”, in ACM MobiSys, 2012. [14] D. Guo, Y. Liu, X. Li, and P. Yang, “False Negative Problem of Counting Bloom Filter”, IEEE Trans. on Knowledge and Data Engineering, vol. 22, issue 5, pp. 651-664, 2010. [15] H. Han, B. Sheng, C. C. Tan, Q. Li, W. Mao, and S. Lu, “Counting RFID Tags Efficiently and Anonymously”, in IEEE INFOCOM, 2010. [16] T. Li, S. Chen, and Y. Ling, “Identifying the Missing Tags in a Large RFID System”, in ACM MobiHoc, 2010. [17] C. Luo, F. Wu, J. Sun, C. W. Chen, “Compressive Data Gathering for Large-Scale Wireless Sensor Networks”, in ACM MobiCom, 2009. [18] L. M. Ni, Y. Liu, Y. C. Lau, and A. Patil, “LANDMARC: Indoor Location Sensing Using Active RFID”, ACM Wireless Networks, vol. 10, issue 6, pp. 701-710, 2004. [19] C. Qian, Y. Liu, H.-L. Ngan, and L. M. Ni, “ASAP: Scalable Identifi- cation and Counting for Contactless RFID Systems”, in IEEE ICDCS, 2010. [20] C. Qian, H. Ngan, and Y. Liu, “Cardinality Estimation for Large-scale RFID Systems”, IEEE Trans. on Parallel and Distributed Systems, vol. 22, issue 9, pp. 1441-1454, 2011. [21] L. G. Roberts, “Aloha Packet System with and without Slots and Capture ”, ACM SIGCOMM Computer Communication Review, vol. 5, issue 2, pp. 28-42, 1975. [22] C. C. Tan, B. Sheng, and Q. Li, “How to Monitor for Missing RFID Tags”, in IEEE ICDCS, 2008. [23] J. Wang, H. Hassanieh, D. Katabi, P. Indyk, “Efficient and Reliable Low-Power Backscatter Networks”, in ACM SIGCOMM, 2012. [24] L. Yang, J. Han, Y. Qi, C. Wang, T. Gu, and Y. Liu, “Season: Shelving Interference and Joint Identification in Large-scale RFID Systems”, in IEEE INFOCOM, 2011. [25] H. Yue, C. Zhang, M. Pan, Y. Fang, S. Chen, “A Time-efficient Information Collection Protocol for Large-scale RFID Systems”, in IEEE INFOCOM, 2012. [26] D. Zanetti, B. Danev, S. Capkun, “Physical-layer Identification of UHF ˇ RFID Tags”, in ACM MobiCom, 2010. [27] C. Zhang, Y. Zhang, Y. Fang, “A coverage inference protocol for wireless sensor networks”, IEEE Transactions on Mobile Computing, vol. 9, issue 6, pp. 850-864, June 2010. [28] R. Zhang, Y. Liu, Y. Zhang, and J. Sun, “Fast Identification of the Missing Tags in a Large RFID System”, in IEEE SECON, 2011. [29] H. Zhang, J. Gummeson, B. Ransford, and K. Fu, “Moo: A batteryless computational RFID and sensing platform”, Tech Report UMASS, 2011. http://spqr.cs.umass.edu/moo/ [30] P. Zhang, J. Gummeson, D. Ganesan, “BLINK: A High Throughput Link Layer for Backscatter Communication”, in ACM MobiSys, 2012. [31] Y. Zhang, L. T. Yang, and J. Chen “RFID and Sensor Networks: Archi￾tectures, Protocols, Security and Integrations”, Auerbach Publications, 2010. [32] Y. Zheng, M. Li, and C. Qian, “PET: Probabilistic Estimating Tree for Large-Scale RFID Estimation”, in IEEE ICDCS, 2011. [33] Y. Zheng and M. Li, “Fast Tag Searching Protocol for Large-Scale RFID Systems”, in IEEE ICNP, 2011