Every Bit Counts-Fast and Scalable RFID Estimation Muhammad Shahzad and Alex X.Liu Department of Computer Science and Engineering Michigan State University East Lansing,Michigan,USA (shahzadm,alexliu@cse.msu.edu ABSTRACT 1.INTRODUCTION Radio Frequency Identification (RFID)systems have been 1.1 Motivation and Problem Statement widely deployed for various applications such as object track- ing,3D positioning,supply chain management,inventory RFID systems are widely used in various applications such control,and access control.This paper concerns the fun- as object tracking 12,3D positioning 19,indoor localiza- damental problem of estimating RFID tag population size, tion 13,supply chain management 9,inventory control, which is needed in many applications such as tag identifi- and access control [4,11]because the cost of commercial cation,warehouse monitoring,and privacy sensitive RFID RFID tags is negligible compared to the value of the prod- systems.In this paper,we propose a new scheme for es- ucts to which they are attached (e.g.,as low as 5 cents per timating tag population size called Average Run based Tag tag [15]).An RFID system consists of tags and readers. estimation (ART).The technique is based on the average A tag is a microchip with an antenna in a compact pack- run-length of ones in the bit string received using the stan- age that has limited computing power and communication dardized framed slotted Aloha protocol.ART is significantly range.There are two types of tags:(1)passive tags,which faster than prior schemes because its estimator has smaller are powered up by harvesting the radio frequency energy from readers (as they do not have their own power sources) variance compared to the variances of estimators of prior schemes.For example,given a required confidence interval and have communication range often less than 20 feet;(2) of 0.1%and a required reliability of 99.9%,ART is consis- active tags,which have their own power sources and have tently 7 times faster than the fastest existing schemes (UPE relatively longer communication range.A reader has a ded- and EZB)for any tag population size.Furthermore,ART's icated power source with significant computing power.It estimation time is observably independent of the tag popula- transmits a query to a set of tags and the tags respond over tion sizes.ART is easy to deploy because it neither requires a shared wireless medium. modification to tags nor to the communication protocol be- This paper concerns the fundamental problem of estimat- tween tags and readers.ART only needs to be implemented ing the size of a given tag population.This is needed in on readers as a software module.ART works with multiple many applications such as tag identification,privacy sensi- readers with overlapping regions. tive RFID systems,and warehouse monitoring.In tag iden- tification protocols,which read the ID stored in each tag, population size is estimated at the start to guide the iden- Categories and Subject Descriptors tification process.For example,for tag identification pro- C.2.1 [Computer-Communication Networks):Network tocols that are based on the framed slotted Aloha protocol Architecture and Design-Wireless communication;C.2.8 (standardized in EPCGlobal Class-1 Generation-2 (C1G2) [Mobile Computing]:Algorithm Design and Analysis RFID standard [3]and implemented in commercial RFID systems),tag estimation is often used to calculate the op- timal frame size [7].In privacy sensitive RFID systems, General Terms such as those used in parks for continuously monitoring the Algorithms,Design,Performance,Experimentation number of visitors in different areas of a park to plan the guided trips efficiently,readers may not have the permission to identify human individuals.In warehouses with RFID Keywords based monitoring systems,managers often need to perform RFID,Tags,Estimation a quick estimation of the number of products left in stock for various purposes such as the detection of employee theft Note that although tag population size can be accurately measured by tag identification,the speed will be too slow. Permission to make digital or hard copies of all or part of this work for We formally define the tag estimation problem as:given personal or classroom use is granted without fee provided that copies are a tag population of unknoun size t,a confidence interval not made or distributed for profit or commercial advantage and that copies B∈(0，l,and a required reliability a∈[0,1)，a set of read- bear this notice and the full citation on the first page.To copy otherwise,to ers needs to collaboratively compute the estimated number republish,to post on servers or to redistribute to lists,requires prior specific permission and/or a fee. of tags t so that Plt-tl<Bt>a.When the number of MobiCom'/2,August 22-26,2012,Istanbul,Turkey. readers is one,we call this problem single-reader estimation: Copyright2012ACM978-1-4503-1159-5/12/08.s15.00. otherwise,we call this problem multi-reader estimation. 365Every Bit Counts - Fast and Scalable RFID Estimation Muhammad Shahzad and Alex X. Liu Department of Computer Science and Engineering Michigan State University East Lansing, Michigan, USA {shahzadm, alexliu}@cse.msu.edu ABSTRACT Radio Frequency Identification (RFID) systems have been widely deployed for various applications such as object track￾ing, 3D positioning, supply chain management, inventory control, and access control. This paper concerns the fun￾damental problem of estimating RFID tag population size, which is needed in many applications such as tag identifi- cation, warehouse monitoring, and privacy sensitive RFID systems. In this paper, we propose a new scheme for es￾timating tag population size called Average Run based Tag estimation (ART). The technique is based on the average run-length of ones in the bit string received using the stan￾dardized framed slotted Aloha protocol. ART is significantly faster than prior schemes because its estimator has smaller variance compared to the variances of estimators of prior schemes. For example, given a required confidence interval of 0.1% and a required reliability of 99.9%, ART is consis￾tently 7 times faster than the fastest existing schemes (UPE and EZB) for any tag population size. Furthermore, ART’s estimation time is observably independent of the tag popula￾tion sizes. ART is easy to deploy because it neither requires modification to tags nor to the communication protocol be￾tween tags and readers. ART only needs to be implemented on readers as a software module. ART works with multiple readers with overlapping regions. Categories and Subject Descriptors C.2.1 [Computer-Communication Networks]: Network Architecture and Design – Wireless communication; C.2.8 [Mobile Computing]: Algorithm Design and Analysis General Terms Algorithms, Design, Performance, Experimentation Keywords RFID, Tags, Estimation Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. MobiCom’12, August 22–26, 2012, Istanbul, Turkey. Copyright 2012 ACM 978-1-4503-1159-5/12/08 ...$15.00. 1. INTRODUCTION 1.1 Motivation and Problem Statement RFID systems are widely used in various applications such as object tracking [12], 3D positioning [19], indoor localiza￾tion [13], supply chain management [9], inventory control, and access control [4, 11] because the cost of commercial RFID tags is negligible compared to the value of the prod￾ucts to which they are attached (e.g., as low as 5 cents per tag [15]). An RFID system consists of tags and readers. A tag is a microchip with an antenna in a compact pack￾age that has limited computing power and communication range. There are two types of tags: (1) passive tags, which are powered up by harvesting the radio frequency energy from readers (as they do not have their own power sources) and have communication range often less than 20 feet; (2) active tags, which have their own power sources and have relatively longer communication range. A reader has a ded￾icated power source with significant computing power. It transmits a query to a set of tags and the tags respond over a shared wireless medium. This paper concerns the fundamental problem of estimat￾ing the size of a given tag population. This is needed in many applications such as tag identification, privacy sensi￾tive RFID systems, and warehouse monitoring. In tag iden￾tification protocols, which read the ID stored in each tag, population size is estimated at the start to guide the iden￾tification process. For example, for tag identification pro￾tocols that are based on the framed slotted Aloha protocol (standardized in EPCGlobal Class-1 Generation-2 (C1G2) RFID standard [3] and implemented in commercial RFID systems), tag estimation is often used to calculate the op￾timal frame size [7]. In privacy sensitive RFID systems, such as those used in parks for continuously monitoring the number of visitors in different areas of a park to plan the guided trips efficiently, readers may not have the permission to identify human individuals. In warehouses with RFID￾based monitoring systems, managers often need to perform a quick estimation of the number of products left in stock for various purposes such as the detection of employee theft. Note that although tag population size can be accurately measured by tag identification, the speed will be too slow. We formally define the tag estimation problem as: given a tag population of unknown size t, a confidence interval β ∈ (0, 1], and a required reliability α ∈ [0, 1), a set of read￾ers needs to collaboratively compute the estimated number of tags t ˜ so that P |t ˜− t| ≤ βt ≥ α. When the number of readers is one, we call this problem single-reader estimation; otherwise, we call this problem multi-reader estimation. 365