Journal of Computer Science and Technology ›› 2020, Vol. 35 ›› Issue (5): 1099-1114.doi: 10.1007/s11390-020-9828-3

Special Issue: Computer Networks and Distributed Computing

• Computer Networks and Distributed Computing • Previous Articles     Next Articles

Minimum Time Extrema Estimation for Large-Scale Radio-Frequency Identification Systems

Xiao-Jun Zhu1,2, Member, CCF, IEEE, Li-Jie Xu2, Xiao-Bing Wu3, and Bing Chen1, Senior Member, CCF        

  1. 1 College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China;
    2 Jiangsu Key Laboratory of Big Data Security and Intelligent Processing, Nanjing University of Posts and Telecommunications, Nanjing 210049, China;
    3 Wireless Research Centre, University of Canterbury, Christchurch 8041, New Zealand
  • Received:2019-07-09 Revised:2020-03-14 Online:2020-09-20 Published:2020-09-30
  • Supported by:
    The research is supported by the National Natural Science Foundation of China under Grant Nos. 61972199, 61672283, 61502232, and 61502251, the Jiangsu Key Laboratory of Big Data Security & Intelligent Processing, Nanjing University of Posts and Telecommunications under Grant No. BDSIP1907, China Postdoctoral Science Foundation under Grant No. 2016M601859, and the Post-Doctoral Fund of Jiangsu Province of China under Grant No. 1701047A.

We consider the extrema estimation problem in large-scale radio-frequency identification (RFID) systems, where there are thousands of tags and each tag contains a finite value. The objective is to design an extrema estimation protocol with the minimum execution time. Because the standard binary search protocol wastes much time due to interframe overhead, we propose a parameterized protocol and treat the number of slots in a frame as an unknown parameter. We formulate the problem and show how to find the best parameter to minimize the worst-case execution time. Finally, we propose two rules to further reduce the execution time. The first is to find and remove redundant frames. The second is to concatenate a frame from minimum value estimation with a frame from maximum value estimation to reduce the total number of frames. Simulations show that, in a typical scenario, the proposed protocol reduces execution time by 79% compared with the standard binary search protocol.

Key words: radio-frequency identification (RFID) system; maximum value estimation; minimum value estimation; time efficient protocol;

[1] Smith J R. History of the WISP program. In Wirelessly Powered Sensor Networks and Computational RFID, Smith J R (ed.), Springer-Verlag, 2013, pp.13-29.
[2] Qian C, Liu Y, Ngan H, Ni L M. Asap:Scalable identification and counting for contactless RFID systems. In Proc. the 30th Int. Conf. Distributed Computing Systems, June 2010, pp.52-61.
[3] Pan L, Wu H. Smart trend-traversal:A low delay and energy tag arbitration protocol for large RFID systems. In Proc. the 28th IEEE Int. Conf. Computer Communications, April 2009, pp.2571-2575.
[4] Shahzad M, Liu A X. Probabilistic optimal tree hopping for RFID identification. In Proc. ACM SIGMETRICS/Int. Conf. Measurement and Modeling of Computer Systems, June 2013, pp.293-304.
[5] Hou Y, Zheng Y. PHY assisted tree-based RFID identification. In Proc. IEEE Int. Conf. Computer Communications, May 2017.
[6] Mustafa H, Zhu X, Li Q, Chen G. Efficient median estimation for large-scale sensor RFID systems. Int. Journal of Sensor Networks, 2012, 12(3):171-183.
[7] Xie L, Han H, Li Q, Wu J, Lu S. Efficient protocols for collecting histograms in large-scale RFID systems. IEEE Trans. Parallel and Distributed Systems, 2015, 26(9):2421-2433.
[8] Zhong H, Zhu X, Chen B, Shen S. Estimating the extrema of large-scale RFID systems. In Proc. the 24th IEEE Int. Conf. Parallel and Distributed Systems, December 2018, pp.886-893.
[9] Zheng Y, Li M. Towards more efficient cardinality estimation for large-scale RFID systems. IEEE/ACM Trans. Networking, 2014, 22(6):1886-1896.
[10] Zhou Z, Chen B, Yu H. Understanding RFID counting protocols. IEEE/ACM Trans. Networking, 2016, 24(1):312-327.
[11] Shahzad M, Liu X. Fast and accurate estimation of RFID tags. IEEE/ACM Trans. Networking, 2015, 23(1):241-254.
[12] Liu X, Li K, Liu X, Guo S, Shahzad M, Wang L, Wu J. Multi-category RFID estimation. IEEE/ACM Trans. Networking, 2017, 25(1):264-277.
[13] Liu X, Li K, Guo S, Liu X, Li P, Wang K, Wu J. Top-k queries for categorized RFID systems. IEEE/ACM Trans. Networking, 2017, 25(5):2587-2600.
[14] Wang Y, Liu J, Wang X, Zhu F, Chen L. Missing tag identification in open RFID systems. In Proc. the 2017 IEEE Int. Conf. Communications, May 2017.
[15] Zhu F, Xiao B, Liu J, Wang B, Pan Q, Chen L. Exploring tag distribution in multi-reader RFID systems. IEEE Trans. Mobile Computing, 2017, 16(5):1300-1314.
[16] Cho S, Kim K, Hong S. Effective object identification and association by varying coverage through RFID power control. Journal of Computer Science and Technology, 2014, 29(1):4-20.
[17] Xie L, Wang C, Bu Y, Sun J, Cai Q, Wu J, Lu S. TaggedAR:An RFID-based approach for recognition of multiple tagged objects in augmented reality systems. IEEE Trans. Mobile Computing, 2019, 18(5):1188-1202.
[18] Xiao F, Wang Z, Ye N, Wang R, Li X. One more tag enables fine-grained RFID localization and tracking. IEEE/ACM Trans. Networking, 2018, 26(1):161-174.
[19] Buettner M, Wetherall D. An empirical study of UHF RFID performance. In Proc. the 14th Annual Int. Conf. Mobile Computing and Networking, August 2008, pp.223-234.
[20] Zhu X, Wu X, Chen G. Refining hop-count for localisation in wireless sensor networks. Int. Journal of Sensor Networks, 2012, 12(4):232-243.
No related articles found!
Full text



[1] Zhou Di;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] C.Y.Chung; H.R.Hwa;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[4] Pan Qijing;. A Routing Algorithm with Candidate Shortest Path[J]. , 1986, 1(3): 33 -52 .
[5] Wang Jianchao; Wei Daozheng;. An Effective Test Generation Algorithm for Combinational Circuits[J]. , 1986, 1(4): 1 -16 .
[6] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[7] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[8] Zheng Guoliang; Li Hui;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[9] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[10] Huang Xuedong; Cai Lianhong; Fang Ditang; Chi Bianjin; Zhou Li; Jiang Li;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved