900 IEEE TRANSACTIONS ON COMPUTERS,VOL.65,NO.3.MARCH 2016 experiments.Based on Fig.17a,both PID and EPIA can [10]W.Luo,S.Chen,T.Li,and Y.Qiao,"Probabilistic missing-tag achieve the requirement of coverage ratio (a=60%) detection and energy-time tradeoff in large-scale RFID systems," Besides,our solutions PID and EPIA have better perfor- in Proc.ACM MobiHoc,2012,pp.95-104. [11]X.Liu,K.Li,G.Min,Y.Shen,A.Liu,and W.Qu,"Completely mance than the baseline solution.When u=200,EPIA pinpointing the missing RFID tags in a time-efficient way,"IEEE reduces the execution time by 43 percent compared to Trans.Comput.,vol.64,no.1,pp.87-96,Jan.2015. [12]T.Li,S.Chen,and Y.Ling,"Efficient protocols for identifying the MaxPw,as shown in Fig.17b.Besides,PID and EPIA have missing tags in a large RFID system,"IEEE/ACM Trans.Netw., lower misreading ratios,as shown in Fig.17c.This is vol21,no.6,PP.1974-1987,Dec.2013, because PID and EPIA try to select the optimal power to [13]Y.Zheng and M.Li,"P-MTI:Physical-layer missing tag identifica- focus on the specified area,while avoiding identifying the tion via compressive sensing,"in Proc.IEEE INFOCOM,2013 pp.917-925. interference tags.The optimal power is usually larger than [14] X.Liu,K.Li,G.Min,Y.Shen,A.X.Liu,and W.Qu,"A multiple the minimum power and smaller than the maximum hashing approach to completeidentification of missing RFID tags," (default)power,as shown in 17d. IEEE Trans.Commn.,vol.62,no.3,pp.1046-1057,Mar.2014. [15]X.Liu,B.Xiao,S.Zhang,and K.Bu,"Unknown tag identification in large RFID systems:An efficient and complete solution,IEEE 11 CONCLUSION Trans.Parallel Distrib.Syst.,vol.26,no.6,pp.1775-1788,Jun.2015. [16]X.Liu,K.Li,G.Min,K.Lin,B.Xiao,Y.Shen,and W.Qu, In this paper,we investigate the problem of identifying the "Efficient unknown tag identification protocols in large-scale tags in the specified area.We conduct extensive experi- RFID systems,IEEE Trans.Parallel Distrib.Syst.,vol.25,no.12 ments on the commodity RFID system in real environments Pp.3145-3155,Dec.2014. [17 and present two efficient solutions,PID and PIA.They H.Yue,C.Zhang,M.Pan,Y.Fang,,and S.Chen,"Unknown-target information collection protocol in sensor-enabled RFID systems,' work in a similar way of picture-taking in an auto-focus IEEE/ACM Trans.Netw.,vol.22,no.4,pp.1164-1175,Aug.2014. camera.They first focus on the specified area and then iden- [18]Y.Zheng and M.Li,"Fast tag searching protocol for large-scale tify the target tags.Furthermore,we improve the proposed RFID systems,"in Proc.IEEE Int.Conf.Netw.Protocols,2011, solutions to make them work well in more complex envi- Pp.363-372. 19 Y.Qiao,S.Chen,T.Li,and S.Chen,"Energy-efficient polling pro- ronments.The realistic experiments show that our solutions tocols in RFID systems,"in Proc.12th ACM Int.Symp.Mobile Ad outperform the baseline solutions. Hoc Netw.Comput.,2011,pp.226-235. [20]H.Yue,C.Zhang,M.Pan,Y.Fang,and S.Chen,"A time-efficient information collection protocol for large-scale RFID systems,"in ACKNOWLEDGMENTS Proc.IEEE INFOCOM,2012,pp.2158-2166. [21]H.Han,B.Sheng,C.C.Tan,Q.Li,W.Mao,and S.Lu,"Counting This work is supported in part by National Natural Science RFID tags efficiently and anonymously,in Proc.IEEE INFOCOM, Foundation of China under Grant Nos.61472185,61100196, 2010,pp.1-9. 61373129,61321491,91218302;Key Project of Jiangsu [22]M.Kodialam and T.Nandagopal,"Fast and reliable estimation Research Program under Grant No.BE2013116;EU FP7 schemes in RFID systems,"in Proc.12th Annu.Int.Conf.Mobile Comput.Netw.,2006,pp.322-333. IRSES MobileCloud Project under Grant No.612212.This 231 C.Qian,H.Ngan,Y.Liu,and L.M.Ni,"Cardinality estimation for work is partially supported by Collaborative Innovation large-scale RFID systems,"IEEE Trans.Parallei Distrib.Syst., Center of Novel Software Technology and Industrialization. vol.22,no.9,PP.1441-1454,Sep.2011, 24】 Y.Zheng and M.Li,"Pet:Probabilistic estimating tree for large- Jie Wu is supported in part by US National Science scale RFID estimation,"IEEE Trans.Mobile Comput.,vol.11,no.11 Foundation grants NSF CCF 1301774,ECCS 1231461, Pp.1763-1774,Nov.2012. CNS 1156574,CNS 1065444,and ECCS 1128209.Lei Xie is [25] F.Schoute,"Dynamic frame length aloha,"IEEE Trans.Commun., the corresponding author. vol.31,no.4,Pp.565-568,Apr.1983. [26]W.Su,N.V.Aichazidis,and T.T.Ha,"Multiple RFID tags access algorithm,"IEEE Trans.Mobile Comput.,vol.9,no.2,pp.174-187, REFERENCES Feb.2010. [27]M.Buettner and D.Wetherall,"An emprical study of UHF RFID [1]J.Myung,W.Lee,and J.Srivastava,"Adaptive binary splitting for performance,"in Proc.14th ACM Int.Conf.Mobile Comput.Netw., efficient RFID tag anti-collision,"IEEE Conmmun.Left.,vol.10, 2008,PP.223-234 no.3,Pp.144-146,Mar.2006. [28]S.R.Arror and D.D.Deavours,"Evaluation of the state of passive [2 L.Pan and H.Wu,"Smart trend-traversal protocol for RFID tag UHF RFD:An experimental approach,"IEEE Syst.J.,vol.i,no.2, arbitration,"IEEE Trans.Wireless Commun.,vol.10,no.11, Pp.168-176,Dec.2007. PP.3565-3569,Nov.2011. 291 L.Xie,Q.Li,X.Chen,S.Lu,and D.Chen,"Continuous scanning [3 T.L.Porta,G.Maselli,and C.Petrioli,"Anti-collision protocols for with mobile reader in RFID systems:An experimental study,"in single-reader RFID systems:Temporal analysis and optimization," Proc.ACM 14th ACM Int.Symp.Mobile Ad Hoc Netw.Comput., IEEE Trans.Mobile Comput.,vol.10,no.2,pp.267-279,Feb.2011. 2013,pp.11-20. 4 M.Shahzad and A.Liu,"Probabilistic optimal tree hopping for [30]X.Xu,L.Gu,J.Wang,G.Xing,and S.Cheung,"Read more with RFID identification,"in Proc.ACM SIGMETRICS/Int.Conf.Mea- less:An adaptive approach to energy-efficient RFID systems,' surement Modeling Comput.Syst.,2014,pp.293-304. IEEE J.Sel.Areas Commun.,vol.29,no.8,pp.1684-1697,Sep.2011 [5 H.Vogt,"Efficient object identification with passive RFID tags,"in [31]Y.Yin,L.Xie,J.Wu,A.V.Vasilakos,and S.Lu,"Focus and shoot Proc.1st Int.Conf.Pervasive Comput.,2002,pp.98-113. Efficient identification over RFID tags in the specified area,"in [6 m,8 Proc.10th Int.Conf.Mobile Ubiquitous Syst.:Comput.,Netw.Services 2014,Pp.344-357 no.1,Pp.16-24,jan.2009. [32]S.Tang,J.Yuan,X.Li,G.Chen,Y.Liu,and J.Zhao,"RASPberry: (7 B.Zhen,M.Kobayashi,and M.Shimuzu,"Framed aloha for mul- A stable reader activation scheduling protocol in multi-reader tiple RFID objects identification,"IEICE Trans.Commun.,vol.E80- RFID systems,"in Proc.IEEE 17th Int.Conf.Netw.Protocols,2009 B,no.3.PP.991-999,Mar.2005. PP.304-313. 81 L.Xie,B.Sheng,C.Tan,H.Han,Q.Li,and D.Chen,"Efficient tag [33]L.Yang,J.Han,Y.Qi,C.Wang,T.Gu,and Y.Liu,"Season:Shelv- identification in mobile RFID systems,in Proc.IEEE INFOCOM, ing interference and joint identification in large-scale RFID sys- 2010,Pp.1-9. tems,"in Proc.IEEE INFOCOM,2011,pp.3092-3100. 9 C.Tan,B.Sheng,and Q.Li,"Efficient techniques for monitoring missing RFID tags,"IEEE Trans.Wireless Commun.,vol.9,no.6, PP.1882-1889,Jun.2010.experiments. Based on Fig. 17a, both PID and EPIA can achieve the requirement of coverage ratio (a ¼ 60%). Besides, our solutions PID and EPIA have better perfor￾mance than the baseline solution. When u ¼ 200, EPIA reduces the execution time by 43 percent compared to MaxPw, as shown in Fig. 17b. Besides, PID and EPIA have lower misreading ratios, as shown in Fig. 17c. This is because PID and EPIA try to select the optimal power to focus on the specified area, while avoiding identifying the interference tags. The optimal power is usually larger than the minimum power and smaller than the maximum (default) power, as shown in 17d. 11 CONCLUSION In this paper, we investigate the problem of identifying the tags in the specified area. We conduct extensive experi￾ments on the commodity RFID system in real environments and present two efficient solutions, PID and PIA. They work in a similar way of picture-taking in an auto-focus camera. They first focus on the specified area and then iden￾tify the target tags. Furthermore, we improve the proposed solutions to make them work well in more complex envi￾ronments. The realistic experiments show that our solutions outperform the baseline solutions. ACKNOWLEDGMENTS This work is supported in part by National Natural Science Foundation of China under Grant Nos. 61472185, 61100196, 61373129, 61321491, 91218302; Key Project of Jiangsu Research Program under Grant No. BE2013116; EU FP7 IRSES MobileCloud Project under Grant No. 612212. This work is partially supported by Collaborative Innovation Center of Novel Software Technology and Industrialization. Jie Wu is supported in part by US National Science Foundation grants NSF CCF 1301774, ECCS 1231461, CNS 1156574, CNS 1065444, and ECCS 1128209. Lei Xie is the corresponding author. REFERENCES [1] J. Myung, W. Lee, and J. Srivastava, “Adaptive binary splitting for efficient RFID tag anti-collision,” IEEE Commun. Lett., vol. 10, no. 3, pp. 144–146, Mar. 2006. [2] L. Pan and H. Wu, “Smart trend-traversal protocol for RFID tag arbitration,” IEEE Trans. Wireless Commun., vol. 10, no. 11, pp. 3565–3569, Nov. 2011. [3] T. L. Porta, G. Maselli, and C. Petrioli, “Anti-collision protocols for single-reader RFID systems: Temporal analysis and optimization,” IEEE Trans. Mobile Comput., vol. 10, no. 2, pp. 267–279, Feb. 2011. [4] M. Shahzad and A. Liu, “Probabilistic optimal tree hopping for RFID identification,” in Proc. ACM SIGMETRICS/Int. Conf. Mea￾surement Modeling Comput. Syst., 2014, pp. 293–304. [5] H. Vogt, “Efficient object identification with passive RFID tags,” in Proc. 1st Int. Conf. Pervasive Comput., 2002, pp. 98–113. [6] Y. Maguire and R. Pappu, “An optimal q-algorithm for the ISO 18000-6c RFID protocol,” IEEE Trans. Autom. Sci. Eng., vol. 6, no. 1, pp. 16–24, Jan. 2009. [7] B. Zhen, M. Kobayashi, and M. Shimuzu, “Framed aloha for mul￾tiple RFID objects identification,” IEICE Trans. Commun., vol. E80- B, no. 3, pp. 991–999, Mar. 2005. [8] L. Xie, B. Sheng, C. Tan, H. Han, Q. Li, and D. Chen, “Efficient tag identification in mobile RFID systems,” in Proc. IEEE INFOCOM, 2010, pp. 1–9. [9] C. Tan, B. Sheng, and Q. Li, “Efficient techniques for monitoring missing RFID tags,” IEEE Trans. Wireless Commun., vol. 9, no. 6, pp. 1882–1889, Jun. 2010. [10] W. Luo, S. Chen, T. Li, and Y. Qiao, “Probabilistic missing-tag detection and energy-time tradeoff in large-scale RFID systems,” in Proc. ACM MobiHoc, 2012, pp. 95–104. [11] X. Liu, K. Li, G. Min, Y. Shen, A. Liu, and W. Qu, “Completely pinpointing the missing RFID tags in a time-efficient way,” IEEE Trans. Comput., vol. 64, no. 1, pp. 87–96, Jan. 2015. [12] T. Li, S. Chen, and Y. Ling, “Efficient protocols for identifying the missing tags in a large RFID system,” IEEE/ACM Trans. Netw., vol. 21, no. 6, pp. 1974–1987, Dec. 2013. [13] Y. Zheng and M. Li, “P-MTI: Physical-layer missing tag identifica￾tion via compressive sensing,” in Proc. IEEE INFOCOM, 2013, pp. 917–925. [14] X. Liu, K. Li, G. Min, Y. Shen, A. X. Liu, and W. Qu, “A multiple hashing approach to complete identification of missing RFID tags,” IEEE Trans. Commun., vol. 62, no. 3, pp. 1046–1057, Mar. 2014. [15] X. Liu, B. Xiao, S. Zhang, and K. Bu, “Unknown tag identification in large RFID systems: An efficient and complete solution,” IEEE Trans. Parallel Distrib. Syst., vol. 26, no. 6, pp. 1775–1788, Jun. 2015. [16] X. Liu, K. Li, G. Min, K. Lin, B. Xiao, Y. Shen, and W. Qu, “Efficient unknown tag identification protocols in large-scale RFID systems,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 12, pp. 3145–3155, Dec. 2014. [17] H. Yue, C. Zhang, M. Pan, Y. Fang, , and S. Chen, “Unknown-target information collection protocol in sensor-enabled RFID systems,” IEEE/ACM Trans. Netw., vol. 22, no. 4, pp. 1164–1175, Aug. 2014. [18] Y. Zheng and M. Li, “Fast tag searching protocol for large-scale RFID systems,” in Proc. IEEE Int. Conf. Netw. Protocols, 2011, pp. 363–372. [19] Y. Qiao, S. Chen, T. Li, and S. Chen, “Energy-efficient polling pro￾tocols in RFID systems,” in Proc. 12th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 2011, pp. 226–235. [20] H. Yue, C. Zhang, M. Pan, Y. Fang, and S. Chen, “A time-efficient information collection protocol for large-scale RFID systems,” in Proc. IEEE INFOCOM, 2012, pp. 2158–2166. [21] H. Han, B. Sheng, C. C. Tan, Q. Li, W. Mao, and S. Lu, “Counting RFID tags efficiently and anonymously,” in Proc. IEEE INFOCOM, 2010, pp. 1–9. [22] M. Kodialam and T. Nandagopal, “Fast and reliable estimation schemes in RFID systems,” in Proc. 12th Annu. Int. Conf. Mobile Comput. Netw., 2006, pp. 322–333. [23] C. Qian, H. Ngan, Y. Liu, and L. M. Ni, “Cardinality estimation for large-scale RFID systems,” IEEE Trans. Parallel Distrib. Syst., vol. 22, no. 9, pp. 1441–1454, Sep. 2011. [24] Y. Zheng and M. Li, “Pet: Probabilistic estimating tree for large￾scale RFID estimation,” IEEE Trans. Mobile Comput., vol. 11, no. 11, pp. 1763–1774, Nov. 2012. [25] F. Schoute, “Dynamic frame length aloha,” IEEE Trans. Commun., vol. 31, no. 4, pp. 565–568, Apr. 1983. [26] W. Su, N. V. Alchazidis, and T. T. Ha, “Multiple RFID tags access algorithm,” IEEE Trans. Mobile Comput., vol. 9, no. 2, pp. 174–187, Feb. 2010. [27] M. Buettner and D. Wetherall, “An emprical study of UHF RFID performance,” in Proc. 14th ACM Int. Conf. Mobile Comput. Netw., 2008, pp. 223–234. [28] S. R. Arror and D. D. Deavours, “Evaluation of the state of passive UHF RFD: An experimental approach,” IEEE Syst. J., vol. 1, no. 2, pp. 168–176, Dec. 2007. [29] L. Xie, Q. Li, X. Chen, S. Lu, and D. Chen, “Continuous scanning with mobile reader in RFID systems: An experimental study,” in Proc. ACM 14th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 2013, pp. 11–20. [30] X. Xu, L. Gu, J. Wang, G. Xing, and S. Cheung, “Read more with less: An adaptive approach to energy-efficient RFID systems,” IEEE J. Sel. Areas Commun., vol. 29, no. 8, pp. 1684–1697, Sep. 2011. [31] Y. Yin, L. Xie, J. Wu, A. V. Vasilakos, and S. Lu, “Focus and shoot: Efficient identification over RFID tags in the specified area,” in Proc. 10th Int. Conf. Mobile Ubiquitous Syst.: Comput., Netw. Services, 2014, pp. 344–357. [32] S. Tang, J. Yuan, X. Li, G. Chen, Y. Liu, and J. Zhao, “RASPberry: A stable reader activation scheduling protocol in multi-reader RFID systems,” in Proc. IEEE 17th Int. Conf. Netw. Protocols, 2009, pp. 304–313. [33] L. Yang, J. Han, Y. Qi, C. Wang, T. Gu, and Y. Liu, “Season: Shelv￾ing interference and joint identification in large-scale RFID sys￾tems,” in Proc. IEEE INFOCOM, 2011, pp. 3092–3100. 900 IEEE TRANSACTIONS ON COMPUTERS, VOL. 65, NO. 3, MARCH 2016