ZOE:Fast Cardinality Estimation for Large-Scale RFID Systems Yuanging Zheng,Mo Li School of Computer Engineering,Nanyang Technological University,Singapore [yuanqing1,limo}@ntu.edu.sg Abstract-Estimating the RFID cardinality with accuracy Further improving the time efficiency of each estimation guarantee is an important task in large-scale RFID systems.This round will significantly benefit the entire cardinality estimation paper proposes a fast RFID cardinality estimation scheme.The process,meet the stringent time requirement of many realtime proposed Zero-One Estimator (ZOE)protocol rapidly converges to optimal parameter settings and achieves high estimation applications,and support larger scale of RFID systems.While efficiency.ZOE significantly improves the cardinality estimation pursuing the estimation efficiency at the optimum,we are efficiency,achieving 3x performance gain compared with existing also aiming at reducing the processing overhead of resource- protocols.Meanwhile,ZOE guarantees arbitrary accuracy re- constrained RFID tags.Most existing probabilistic approaches quirement without imposing computation and memory overhead at RFID tags.Due to the simplicity and robustness,the ZOE require generating large volume of random numbers or alter- protocol provides reliable cardinality estimation even over noisy natively pre-storing them at RFID tags,which leads to heavy channel.We implement a prototype system using the USRP computation and storage burden for RFID tags.We aim at software defined radio and Intel WISP RFID tags.We also shifting such processing overhead from resource-constrained evaluate the performance of ZOE with extensive simulations. RFID tags to the much more powerful RFID readers.Besides, The evaluation of ZOE shows encouraging results in terms of most existing works assume a reliable wireless channel be- estimation accuracy,time efficiency,as well as robustness. tween the RFID reader and tags,which is contradicting with the fact that the wireless channel is mostly error-prone. I.INTRODUCTION In this paper,we present Zero-One Estimator (ZOE):a Radio Frequency Identification (RFID)systems [9]have simple yet fast RFID cardinality estimation protocol with recently received significant interests from both industry and guaranteed accuracy requirement.ZOE first tunes the system academia.A large-scale RFID system usually consists of parameters and converges to optimal settings with a bisection multiple RFID readers and a huge amount of RFID tags [23]. search with small overhead.With the optimized parameter An RFID tag is capable of storing its unique ID as well as settings,ZOE estimates the RFID cardinality with only one some other information and wirelessly transmitting them back bit feedback from tags at each round providing extremely high to readers.By verifying the unique IDs of RFID tags attached estimation efficiency.Through simply XORing the original to physical objects,RFID readers are able to identify and random number stored at each RFID tag with a common itemize the objects.Due to small form factor and low cost of random number generated by RFID readers,ZOE shifts the RFID tags,RFID systems provide us a scalable and economic burden of generating randomness from lightweight tags to way for managing massive objects in a variety of applications relatively powerful readers.We further take the noisy wire- including inventory management [8,14,17,22,25],logistics less channel into consideration and propose Error Estimation (26,281,object tracking [15,181,etc. and Adjustment (EEA)algorithm to adjust estimation results Fast estimating the cardinality of RFID tags,accordingly according to the practical communication error rates. the number of labeled items,is of primary importance in We implement a prototype system using the Universal many applications,e.g.,estimating the number of conference Software Radio Peripheral (USRP)[4]in concert with the attendees with RFID badges.The estimated RFID cardinality Intel Wireless Identification and Sensing Platform (WISP) with guaranteed accuracy may also serve as primary inputs to [21].We implement the ZOE reader functionality with USRP upper-layer RFID protocols.For instance,Aloha-based RFID Software Defined Radio(SDR)that interrogates programmable identification protocols can achieve near-optimal performance WISP tags.The ZOE protocol only requires slight updates to if the frame size is set according to the number of tags the EPCglobal Class 1 Generation 2 (C1G2)standard.We In order to achieve efficient RFID cardinality estimation, also evaluate ZOE with extensive simulations to study its probabilistic estimation approaches have been proposed which performance in large-scale RFID systems. aim to estimate the approximate number of RFID tags.Some The rest of this paper is organized as follows.We first recent approaches achieve O(log n)estimation efficiency to briefly review the related work in Section II.In Section III, the number of RFID tags n [11,16].One most recent protocol, we introduce our system model and describe the problem of Probabilistic Estimation Tree (PET),achieves O(log log n) cardinality estimation.We give detailed description on ZOE time efficiency for each estimation round [271.Nevertheless. in Section IV.We present the implementation of ZOE in existing protocols require many independent estimation rounds Section V.We evaluate the performance of ZOE with extensive so as to achieve high accuracy on the estimation results. simulations in Section VI.Section VII concludes this paper.ZOE: Fast Cardinality Estimation for Large-Scale RFID Systems Yuanqing Zheng, Mo Li School of Computer Engineering, Nanyang Technological University, Singapore {yuanqing1, limo}@ntu.edu.sg Abstract—Estimating the RFID cardinality with accuracy guarantee is an important task in large-scale RFID systems. This paper proposes a fast RFID cardinality estimation scheme. The proposed Zero-One Estimator (ZOE) protocol rapidly converges to optimal parameter settings and achieves high estimation efficiency. ZOE significantly improves the cardinality estimation efficiency, achieving 3x performance gain compared with existing protocols. Meanwhile, ZOE guarantees arbitrary accuracy re￾quirement without imposing computation and memory overhead at RFID tags. Due to the simplicity and robustness, the ZOE protocol provides reliable cardinality estimation even over noisy channel. We implement a prototype system using the USRP software defined radio and Intel WISP RFID tags. We also evaluate the performance of ZOE with extensive simulations. The evaluation of ZOE shows encouraging results in terms of estimation accuracy, time efficiency, as well as robustness. I. INTRODUCTION Radio Frequency Identification (RFID) systems [9] have recently received significant interests from both industry and academia. A large-scale RFID system usually consists of multiple RFID readers and a huge amount of RFID tags [23]. An RFID tag is capable of storing its unique ID as well as some other information and wirelessly transmitting them back to readers. By verifying the unique IDs of RFID tags attached to physical objects, RFID readers are able to identify and itemize the objects. Due to small form factor and low cost of RFID tags, RFID systems provide us a scalable and economic way for managing massive objects in a variety of applications including inventory management [8, 14, 17, 22, 25], logistics [26, 28], object tracking [15, 18], etc. Fast estimating the cardinality of RFID tags, accordingly the number of labeled items, is of primary importance in many applications, e.g., estimating the number of conference attendees with RFID badges. The estimated RFID cardinality with guaranteed accuracy may also serve as primary inputs to upper-layer RFID protocols. For instance, Aloha-based RFID identification protocols can achieve near-optimal performance if the frame size is set according to the number of tags. In order to achieve efficient RFID cardinality estimation, probabilistic estimation approaches have been proposed which aim to estimate the approximate number of RFID tags. Some recent approaches achieve O(log n) estimation efficiency to the number of RFID tags n [11, 16]. One most recent protocol, Probabilistic Estimation Tree (PET), achieves O(log log n) time efficiency for each estimation round [27]. Nevertheless, existing protocols require many independent estimation rounds so as to achieve high accuracy on the estimation results. Further improving the time efficiency of each estimation round will significantly benefit the entire cardinality estimation process, meet the stringent time requirement of many realtime applications, and support larger scale of RFID systems. While pursuing the estimation efficiency at the optimum, we are also aiming at reducing the processing overhead of resource￾constrained RFID tags. Most existing probabilistic approaches require generating large volume of random numbers or alter￾natively pre-storing them at RFID tags, which leads to heavy computation and storage burden for RFID tags. We aim at shifting such processing overhead from resource-constrained RFID tags to the much more powerful RFID readers. Besides, most existing works assume a reliable wireless channel be￾tween the RFID reader and tags, which is contradicting with the fact that the wireless channel is mostly error-prone. In this paper, we present Zero-One Estimator (ZOE): a simple yet fast RFID cardinality estimation protocol with guaranteed accuracy requirement. ZOE first tunes the system parameters and converges to optimal settings with a bisection search with small overhead. With the optimized parameter settings, ZOE estimates the RFID cardinality with only one bit feedback from tags at each round providing extremely high estimation efficiency. Through simply XORing the original random number stored at each RFID tag with a common random number generated by RFID readers, ZOE shifts the burden of generating randomness from lightweight tags to relatively powerful readers. We further take the noisy wire￾less channel into consideration and propose Error Estimation and Adjustment (EEA) algorithm to adjust estimation results according to the practical communication error rates. We implement a prototype system using the Universal Software Radio Peripheral (USRP) [4] in concert with the Intel Wireless Identification and Sensing Platform (WISP) [21]. We implement the ZOE reader functionality with USRP Software Defined Radio (SDR) that interrogates programmable WISP tags. The ZOE protocol only requires slight updates to the EPCglobal Class 1 Generation 2 (C1G2) standard. We also evaluate ZOE with extensive simulations to study its performance in large-scale RFID systems. The rest of this paper is organized as follows. We first briefly review the related work in Section II. In Section III, we introduce our system model and describe the problem of cardinality estimation. We give detailed description on ZOE in Section IV. We present the implementation of ZOE in Section V. We evaluate the performance of ZOE with extensive simulations in Section VI. Section VII concludes this paper