RFID标签数目估算机制研究（参考文献）Every Bit Counts - Fast and Scalable RFID Estimation

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-tla.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. 365

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 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

A tag estimation scheme should satisfy the following three some prior schemes require modification to tags and some requirements: demand unrealistic system parameters. For example.the scheme in [14 requires each tag to store thousands of hash 1.Reliability:The actual reliability should always be functions.which is not practical to implement on passive greater than or equal to the required reliability.The tags and is not compliant with the C1G2 standard.As reliability a given as input is called the required re- another example,the scheme in 6 uses increasingly large liability.The reliability that an estimation scheme frame sizes as population size increases (e.g.,the frame size achieves is called its actual reliability. required by the scheme in[6]is greater than half of tag popu- lation size),which soon exceeds the maximum limit allowed 2.Scalability:The estimation time needs to be scalable by the C1G2 Standard. to large population sizes because in many applications, the number of passive tags can be very large due to their low cost,easy disposability,and powerless oper- 2.RELATED WORK ation. The first tag estimation scheme,called Unified Proba- bilistic Estimator (UPE),was proposed by Kodialam and 3.Deployability:The estimation scheme needs to be com- Nandagopal in 2006 7.UPE uses the framed slotted Aloha pliant with the C1G2 standard and should not require protocol and makes estimation based on either the number of any changes to tags empty slots or that of collision slots in a frame.Besides this 1.2 Proposed Approach estimator having larger variance than ART,UPE requires the differentiation among empty,single,and collision slots, In this paper,we propose a new scheme called Aver- which takes significantly more time than differentiating be- age Run based Tag estimation(ART),which satisfies all of tween empty and non-empty slots.According to C1G2. the above three requirements.The communication protocol a reader requires 300us to detect an empty slot,1500us used by ART is the standardized framed slotted Aloha pro- to detect a collision,and 3000us to complete a successful tocol,in which a reader first broadcasts a value f to the tags read.In [8],Kodialam et al.proposed an improved framed in its vicinity where f represents the number of time slots slotted Aloha protocol based estimation scheme called En- present in a forthcoming frame.Then each tag randomly hanced Zero Based (EZB)estimator,which performs esti- picks a time slot in the frame and replies during that slot mation based on the total number of Os in a frame.While Thus,the reader gets a binary sequence of Os and Is by rep- UPE estimates population size in each round and averages resenting a slot with no tag replies as 0 and a slot with one the estimated sizes when all rounds are finished,EZB only or more tag replies as 1.The key idea of ART is to estimate records the total number of 0s in each frame and at the end tag population size based on the average run size of ls in of all rounds,EZB first averages the recorded values and the binary sequence.We show that the average run size of then uses it to do estimation. Is in a frame monotonously increases with the increase in the size of tag population.Thus,average run size of 1s is an In [14],Qian et al.proposed an estimation scheme called Lottery Frame (LoF).Compared to UPE and EZB,LoF is indicator of tag population size. faster;however,it is impractical to implement as it requires 1.3 Advantages of ART over Prior Art each tag to store a large number (i.e.,the number of bits in a tag ID times the number of frames,which can be in the scale ART is advantageous in terms of speed and deployability. of thousands)of unique hash functions.LoF needs to modify For speed,ART is faster than all prior schemes.For exam- both tags and the communication protocol between readers ple,given a confidence interval of 0.1%and the required reli- and tags,which makes it non-compliant with C1G2.Han et ability of 99.9%.ART is consistently 7 times faster than the al.proposed a tag estimation scheme called First Non Empty fastest existing schemes(i.e.,UPE [7]and EZB [8])for any Based (FNEB)estimator.which is based on the size of the tag population size.The reason behind ART being faster first run of 0s in a frame [6].FNEB is based on an unrealistic than prior schemes is that the new estimator that we pro- assumption that frame size can be arbitrarily large.Li et al pose in this paper,namely the average run size of Is,has sig- proposed an estimation scheme called Maximum Likelihood nificantly smaller variance compared to the estimators used Estimator(MLE)for active tags with the goal of minimizing in prior schemes (such as the total number of 0s 7,8 and power consumption of active tags [10].In [17],Shah and the location of the first 1 in the binary sequence 6),as we Wong proposed a multi-reader tag estimation scheme which analytically show in Section 4.2.An estimator with small is based on an unrealistic assumption that any tag covered variance is faster because the estimation process needs to be by multiple readers only replies to one reader. repeated fewer times to achieve the required reliability.The intuitive reason that our estimator has smaller variance than prior estimators is that our estimator uses more information 3.ART-SCHEME OVERVIEW available in the bit sequence.Furthermore,ART estimation time is observably independent of tag population sizes.In 3.1 Communication Protocol Overview contrast,as tag volume increases,the estimation time of ART uses the framed slotted Aloha protocol specified in some prior schemes (e.g.,FNEB 6)increases. C1G2 as its MAC layer communication protocol.In this pro For deployability,ART neither requires modification to tocol,the reader first tells tags the frame size f,which is typ- the tags nor to the communication protocol between tags ically no more than 512 slots for practical reasons16.and a and readers.ART only needs to be implemented on the random seed number R.Later in the paper,we will see how a reader side as a software module without any hardware mod- simple use of seed number R will make it straightforward to ifications.ART also does not demand any unpractical sys- extend our estimation scheme to use multiple readers with tem parameters beyond the C1G2 standard.In contrast overlapping regions.Each tag within the transmission range 366

A tag estimation scheme should satisfy the following three requirements: 1. Reliability: The actual reliability should always be greater than or equal to the required reliability. The reliability α given as input is called the required re￾liability. The reliability that an estimation scheme achieves is called its actual reliability. 2. Scalability: The estimation time needs to be scalable to large population sizes because in many applications, the number of passive tags can be very large due to their low cost, easy disposability, and powerless oper￾ation. 3. Deployability: The estimation scheme needs to be com￾pliant with the C1G2 standard and should not require any changes to tags. 1.2 Proposed Approach In this paper, we propose a new scheme called Aver￾age Run based Tag estimation (ART), which satisfies all of the above three requirements. The communication protocol used by ART is the standardized framed slotted Aloha pro￾tocol, in which a reader first broadcasts a value f to the tags in its vicinity where f represents the number of time slots present in a forthcoming frame. Then each tag randomly picks a time slot in the frame and replies during that slot. Thus, the reader gets a binary sequence of 0s and 1s by rep￾resenting a slot with no tag replies as 0 and a slot with one or more tag replies as 1. The key idea of ART is to estimate tag population size based on the average run size of 1s in the binary sequence. We show that the average run size of 1s in a frame monotonously increases with the increase in the size of tag population. Thus, average run size of 1s is an indicator of tag population size. 1.3 Advantages of ART over Prior Art ART is advantageous in terms of speed and deployability. For speed, ART is faster than all prior schemes. For exam￾ple, given a confidence interval of 0.1% and the required reli￾ability of 99.9%, ART is consistently 7 times faster than the fastest existing schemes (i.e., UPE [7] and EZB [8]) for any tag population size. The reason behind ART being faster than prior schemes is that the new estimator that we pro￾pose in this paper, namely the average run size of 1s, has sig￾nificantly smaller variance compared to the estimators used in prior schemes (such as the total number of 0s [7, 8] and the location of the first 1 in the binary sequence [6]), as we analytically show in Section 4.2. An estimator with small variance is faster because the estimation process needs to be repeated fewer times to achieve the required reliability. The intuitive reason that our estimator has smaller variance than prior estimators is that our estimator uses more information available in the bit sequence. Furthermore, ART estimation time is observably independent of tag population sizes. In contrast, as tag volume increases, the estimation time of some prior schemes (e.g., FNEB [6]) increases. For deployability, ART neither requires modification to the tags nor to the communication protocol between tags and readers. ART only needs to be implemented on the reader side as a software module without any hardware mod￾ifications. ART also does not demand any unpractical sys￾tem parameters beyond the C1G2 standard. In contrast, some prior schemes require modification to tags and some demand unrealistic system parameters. For example, the scheme in [14] requires each tag to store thousands of hash functions, which is not practical to implement on passive tags and is not compliant with the C1G2 standard. As another example, the scheme in [6] uses increasingly large frame sizes as population size increases (e.g., the frame size required by the scheme in [6] is greater than half of tag popu￾lation size), which soon exceeds the maximum limit allowed by the C1G2 Standard. 2. RELATED WORK The first tag estimation scheme, called Unified Proba￾bilistic Estimator (UPE), was proposed by Kodialam and Nandagopal in 2006 [7]. UPE uses the framed slotted Aloha protocol and makes estimation based on either the number of empty slots or that of collision slots in a frame. Besides this estimator having larger variance than ART, UPE requires the differentiation among empty, single, and collision slots, which takes significantly more time than differentiating be￾tween empty and non-empty slots. According to C1G2, a reader requires 300μs to detect an empty slot, 1500μs to detect a collision, and 3000μs to complete a successful read. In [8], Kodialam et al. proposed an improved framed slotted Aloha protocol based estimation scheme called En￾hanced Zero Based (EZB) estimator, which performs esti￾mation based on the total number of 0s in a frame. While UPE estimates population size in each round and averages the estimated sizes when all rounds are finished, EZB only records the total number of 0s in each frame and at the end of all rounds, EZB first averages the recorded values and then uses it to do estimation. In [14], Qian et al. proposed an estimation scheme called Lottery Frame (LoF). Compared to UPE and EZB, LoF is faster; however, it is impractical to implement as it requires each tag to store a large number (i.e., the number of bits in a tag ID times the number of frames, which can be in the scale of thousands) of unique hash functions. LoF needs to modify both tags and the communication protocol between readers and tags, which makes it non-compliant with C1G2. Han et al. proposed a tag estimation scheme called First Non Empty Based (FNEB) estimator, which is based on the size of the first run of 0s in a frame [6]. FNEB is based on an unrealistic assumption that frame size can be arbitrarily large. Li et al. proposed an estimation scheme called Maximum Likelihood Estimator (MLE) for active tags with the goal of minimizing power consumption of active tags [10]. In [17], Shah and Wong proposed a multi-reader tag estimation scheme which is based on an unrealistic assumption that any tag covered by multiple readers only replies to one reader. 3. ART — SCHEME OVERVIEW 3.1 Communication Protocol Overview ART uses the framed slotted Aloha protocol specified in C1G2 as its MAC layer communication protocol. In this pro￾tocol, the reader first tells tags the frame size f, which is typ￾ically no more than 512 slots for practical reasons [16], and a random seed number R. Later in the paper, we will see how a simple use of seed number R will make it straightforward to extend our estimation scheme to use multiple readers with overlapping regions. Each tag within the transmission range 366

of the reader then uses f,R,and its ID to select a slot in cation to tags,this probability is implemented by"virtually" the frame by evaluating a hash function h(f,R,ID)whose extending frame size 1/p times,i.e.,the reader announces a result is in 1,f following a uniform distribution.Each tag frame size of f/p but terminates the frame after the first f has a counter initialized with the slot number it chose to slots.According to C1G2.the reader can terminate a frame reply.After each slot.the reader first transmits an end of at any point.By adjusting p,ART is able to estimate tag slot signal and then each tag decrements its counter by one population of arbitrarily large sizes In any given slot,all the tags whose counters are equal to 1 respond to the reader.In essence,each tag picks a random 3.3 Formal Development:Overview and As- slot from 1 to f following a uniform distribution.If no tag sumptions replies in a slot,it is called an empty slot;if exactly one tag To formally develop an estimator,we first need to de- replies,it is called a singleton slot:and if two or more tags rive the equation for the expected value of average run size reply,it is called a collision slot. of Is as a function of frame size f,tag population size t, 3.2 Estimation Scheme Overview and persistence probability p.We then use the inverse of this function to get the estimated value t from the observed At the end of a frame,the reader obtains a sequence of 0s value of the average run size of Is.To achieve the required and Is by representing an empty slot with 0 and a singleton reliability and minimized estimation time,we optimize f,p, or collision slot with 1.In this binary sequence,a run is a and the number of rounds n so that the total number of slots subsequence where all bits in this subsequence are 0s (or 1s) (f+3)×n is minimized while satisfying P{lt-t≤Bt}≥a but the bits before and after the subsequence are 1s (or 0s), We add 3 to f because at the start of each frame,the reader if they exist.For example,frame 011100 has 3 runs:0.111. waits for about 1ms (3 empty slots)to let the tags get and 00. energized [3,16].We use f to denote f+3. ART uses the average run size of Is to estimate tag popu- To make the formal development tractable,we assume lation size.The intuition is that as tag population increases, that instead of picking a single slot to reply at the start the average run size of 1s increases(and that of Os decreases). of frame of size f,a tag independently decides to reply in We illustrate this intuition using the simulation results in each slot of the frame with probability 1/f regardless of Figure 1,which shows that the average run size of ls in- its decision about previous or forthcoming slots.Vogt first creases as tag population size increases from 0 to 160.The used this assumption for the analysis of framed slotted Aloha markers in this figure are the average of 100 runs.The lines protocol for RFID and justified its use by recognizing that above and below each marker show the standard deviation this problem belongs to a class of problems known as "occu- of the experiments.This figure shows that given a tag pop- pancy problems",which deals with the allocation of balls to ulation size and a frame size,there is a distinct expected urns 18.Ever since,the use of this assumption has been a value of the average run size of 1s.The expected value of norm in the formal analysis of all Aloha based RFID proto- the average run size of 1s is a monotonic function of the cols2,6-8,10.14.17,18,20. number of tags,which means that a unique inverse of this The implication of this assumption is that when a tag in- function exists.Thus,given the observed average run size dependently chooses a slot to reply,it can end up choosing of Is,using the inverse function,we can get the estimated more than one slots in the same frame or even not choosing value t of tag population size t.Similar to other tag esti- any at all,which is not in accordance with C1G2 standard mation schemes.ART also uses multiple frames obtained that requires a tag to pick exactly one slot in a frame.Note from multiple rounds of the framed slotted Aloha protocol that even with the independence assumption,the expected to reduce its estimation variance and therefore increase its number of slots that a tag chooses in a frame is still one estimation reliability.Using different seed values for different As we draw our estimate from a large number of frames to frames,in each frame,the same tag will choose a different achieve required reliability,we can expect to observe this ex- slot to respond. pected number.Therefore,the analysis with the assumption of independence is asymptotically the same as that with- 20 ×1 out the independence assumption.Bordenave et al.further 0 explained in detail why this independence assumption in an alyzing Aloha based protocols provides results just as accu- rate as if all the analysis was done without this assump- tion 1.Note that this independence assumption is made 10 only to make the formal development tractable.The simu- lations in Section 6 are based on the C1G2 standard where a tag chooses exactly one slot at the start of frame. 4.ART-ESTIMATION ALGORITHM 100 Next.we first focus on the single-reader version of ART.In Section 5.6,we present a method to extend ART to handle multiple-readers with overlapping regions.Table 1 lists the Figure 1:Average run size vs.t (f=16) symbols used in this paper. To scale to large tag population sizes,ART uses a persis- 4.1 Average Run Based Tag Estimation tence probability p by which a tag decides whether it should For ART.in each round of the Aloha protocol,we calcu- reply to the reader in a given frame.The persistence proba- late the average run size of b.For example,the average run bility was first introduced in 7.To avoid making any modifi- size of 1 in frame 01110011 (which has two runs of 1,i.e.. 367

of the reader then uses f, R, and its ID to select a slot in the frame by evaluating a hash function h(f, R, ID) whose result is in [1, f] following a uniform distribution. Each tag has a counter initialized with the slot number it chose to reply. After each slot, the reader first transmits an end of slot signal and then each tag decrements its counter by one. In any given slot, all the tags whose counters are equal to 1 respond to the reader. In essence, each tag picks a random slot from 1 to f following a uniform distribution. If no tag replies in a slot, it is called an empty slot; if exactly one tag replies, it is called a singleton slot; and if two or more tags reply, it is called a collision slot. 3.2 Estimation Scheme Overview At the end of a frame, the reader obtains a sequence of 0s and 1s by representing an empty slot with 0 and a singleton or collision slot with 1. In this binary sequence, a run is a subsequence where all bits in this subsequence are 0s (or 1s) but the bits before and after the subsequence are 1s (or 0s), if they exist. For example, frame 011100 has 3 runs: 0, 111, and 00. ART uses the average run size of 1s to estimate tag popu￾lation size. The intuition is that as tag population increases, the average run size of 1s increases (and that of 0s decreases). We illustrate this intuition using the simulation results in Figure 1, which shows that the average run size of 1s in￾creases as tag population size increases from 0 to 160. The markers in this figure are the average of 100 runs. The lines above and below each marker show the standard deviation of the experiments. This figure shows that given a tag pop￾ulation size and a frame size, there is a distinct expected value of the average run size of 1s. The expected value of the average run size of 1s is a monotonic function of the number of tags, which means that a unique inverse of this function exists. Thus, given the observed average run size of 1s, using the inverse function, we can get the estimated value t ˜ of tag population size t. Similar to other tag esti￾mation schemes, ART also uses multiple frames obtained from multiple rounds of the framed slotted Aloha protocol to reduce its estimation variance and therefore increase its estimation reliability. Using different seed values for different frames, in each frame, the same tag will choose a different slot to respond. 0 50 100 150 0 5 10 15 20 Number of tags t Average size of runs 1s 0s Figure 1: Average run size vs. t (f = 16) To scale to large tag population sizes, ART uses a persis￾tence probability p by which a tag decides whether it should reply to the reader in a given frame. The persistence proba￾bility was first introduced in [7]. To avoid making any modifi- cation to tags, this probability is implemented by “virtually” extending frame size 1/p times, i.e., the reader announces a frame size of f /p but terminates the frame after the first f slots. According to C1G2, the reader can terminate a frame at any point. By adjusting p, ART is able to estimate tag population of arbitrarily large sizes. 3.3 Formal Development: Overview and As￾sumptions To formally develop an estimator, we first need to de￾rive the equation for the expected value of average run size of 1s as a function of frame size f, tag population size t, and persistence probability p. We then use the inverse of this function to get the estimated value t ˜ from the observed value of the average run size of 1s. To achieve the required reliability and minimized estimation time, we optimize f, p, and the number of rounds n so that the total number of slots (f + 3)×n is minimized while satisfying P{|t ˜−t| ≤ βt} ≥ α. We add 3 to f because at the start of each frame, the reader waits for about 1ms (≈ 3 empty slots) to let the tags get energized [3, 16]. We use f to denote f + 3. To make the formal development tractable, we assume that instead of picking a single slot to reply at the start of frame of size f, a tag independently decides to reply in each slot of the frame with probability 1/f regardless of its decision about previous or forthcoming slots. Vogt first used this assumption for the analysis of framed slotted Aloha protocol for RFID and justified its use by recognizing that this problem belongs to a class of problems known as “occu￾pancy problems”, which deals with the allocation of balls to urns [18]. Ever since, the use of this assumption has been a norm in the formal analysis of all Aloha based RFID proto￾cols [2, 6–8, 10, 14, 17, 18, 20]. The implication of this assumption is that when a tag in￾dependently chooses a slot to reply, it can end up choosing more than one slots in the same frame or even not choosing any at all, which is not in accordance with C1G2 standard that requires a tag to pick exactly one slot in a frame. Note that even with the independence assumption, the expected number of slots that a tag chooses in a frame is still one. As we draw our estimate from a large number of frames to achieve required reliability, we can expect to observe this ex￾pected number. Therefore, the analysis with the assumption of independence is asymptotically the same as that with￾out the independence assumption. Bordenave et al. further explained in detail why this independence assumption in an￾alyzing Aloha based protocols provides results just as accu￾rate as if all the analysis was done without this assump￾tion [1]. Note that this independence assumption is made only to make the formal development tractable. The simu￾lations in Section 6 are based on the C1G2 standard where a tag chooses exactly one slot at the start of frame. 4. ART — ESTIMATION ALGORITHM Next, we first focus on the single-reader version of ART. In Section 5.6, we present a method to extend ART to handle multiple-readers with overlapping regions. Table 1 lists the symbols used in this paper. 4.1 Average Run Based Tag Estimation For ART, in each round of the Aloha protocol, we calcu￾late the average run size of b. For example, the average run size of 1 in frame 01110011 (which has two runs of 1, i.e., 367

Table 1:Symbols used in the paper THEOREM 1.Let St.i be the random variable representing Symbol Description the run size of b starting at location i in a frame of size f. actual tag population size Let a=f-i+1.The expectation and variance of Ssi are: t tm upper bound on of tags (2) tM maximum of tags that can be estimated s小=0- estimated of tags a required reliability Var(5)=B+2a+1g+2-g6)-ga+" (3) B required confidence interval (1-96)2 frame size fop optimal frame size PROOF.To calculate the expected value of S.i,we first j f+3 to include delay between two need its probability density function PiS.=s.The prob- consecutive frames ability that a run starting at location i will be of length s is n of rounds (i.e.,frames) the product of the probability that s consecutive slots are b nop optimal of rounds (i.e..frames) p persistence probability and s+ith slot is B,where 6=1-b.Thus, Pop optimal persistence probability i(1-g)ifsa b value of a slot:b=0 or b=1 、6 1-6 where 1≤i≤fand1≤s≤a.To derive the expected 96 probability that a slot is b value and variance of S.,we use the moment generating Sbi random variable for run size of b starting at i function: E. expected value Var(.) variance (r)=Eles1=∑e“PSt=sy Cove)】 covariance = Yi random variable for of b slots in frame element of sample space of Y random variable for of runs of b in frame =(ge')°+1-p)∑(ge') Ro 8=1 T element of sample space of R Xb random variable for average run size of b in Differentiating both side w.r.t.7,we get a frame a-1 4 expected value of Xo standard deviation ofo p'(r)=a(ge'）°+(1-go)ge')∑s(ge')-l o0】 $=1 number of ways in which y occurrences of b ξ{，y,r} and f-y occurrences of b can be arranged d (1-(qoe")a =alge'y°+1-gp)lge)ae可（1-9%er -1 in f slots while ensuring that the number of runs of b are r (1-96)(a-1)(g6e')a+1-a(g%e')°+qg%e alge")a+ (1-9%er)2 111 and 11)is (3+2)/2 =2.5.After n rounds,we obtain n average run sizes of b and then calculate the average of Evaluation of o'(r)at r =0 gives us Equation (2).To find these n values.This final value is then used as the expected Var(S.),we calculate E[S]by taking the second deriva- value of the average run size of b in a frame to estimate the tive of '(r)and setting T=0.Thus, tag population size The probability that a slot in a frame is b.where b=0 or ES,=6+96+2a-19+2-2a+1)g8+1 (1-96)2 1,can be calculated using Lemma 1. Evaluating E[S]-E2[S6.]gives Equation (3). LEMMA 1.Let t be the actual tag population size,f be the frame size,p be the persistence probability (i.e.,the proba- Let Xo be the random variable representing the average run bility that a tag participates in a frame),and go be the prob- size of b in a frame.Next,we calculate the expectation and ability that a slot in a frame is b.Thus: variance of Xo using the expectation and variance of Sa.i ∫(1-)fb=0 from Theorem 1.The expectation of Xo will be used to esti- 9s=1-(-)fb=1 (1) mate the tag population size and the variance of Xo will be used to calculate optimal values for f,p,and n.Let Yo be the random variable representing the number of times b oc- PROOF.The probability that a tag chooses a given slot in a frame is p/f.The probability that it does not choose that ead6 meo爱 slot is 1-2.The probability that none of the tags choose holds for any frame.Next,we first calculate E[Yo],Var(Y), that slot is (1-),which is the value of go.As the tags ER,Var(R),and Cov(Y,R)in Lemmas 2 and 3.Then choose the slots independently,g is the same for each slot of we use them to calculate E[Xo]and Var(X)in Theorem 2. the frame.The probability that a slot is chosen by at least Using Equation (14)in Theorem 2,replacing E[X]by the one tag is 1-go,which is the value of gi. average run size of b from n frames,we obtain an equation with only one variable t.Finally,we use Brent's method to Let S.be the random variable representing the run size obtain the numerical solution of this equation.The result of b starting at location i in a frame.If the i-th slot is not is the estimated tag population size.Since ART uses Xo to the starting point of a run,then S.=0.The expectation estimate the tag population size,we call Xo the estimator and variance of So.i can be calculated using Theorem 1. of ART. 368

Table 1: Symbols used in the paper Symbol Description t actual tag population size tm upper bound on # of tags tM maximum # of tags that can be estimated t ˜ estimated # of tags α required reliability β required confidence interval f frame size fop optimal frame size f f + 3 to include delay between two consecutive frames n # of rounds (i.e., frames) nop optimal # of rounds (i.e., frames) p persistence probability pop optimal persistence probability R random seed from reader h(f, R, ID) unform hash function in [1, f] b value of a slot: b = 0 or b = 1 b 1-b qb probability that a slot is b Sb,i random variable for run size of b starting at i E[.] expected value Var(.) variance Cov(.) covariance Yb random variable for # of b slots in frame y element of sample space of Yb Rb random variable for # of runs of b in frame r element of sample space of Rb Xb random variable for average run size of b in a frame μ{.} expected value of Xb σ{.} standard deviation of Xb ξ{f, y, r} number of ways in which y occurrences of b and f − y occurrences of b can be arranged in f slots while ensuring that the number of runs of b are r 111 and 11) is (3 + 2)/2=2.5. After n rounds, we obtain n average run sizes of b and then calculate the average of these n values. This final value is then used as the expected value of the average run size of b in a frame to estimate the tag population size. The probability that a slot in a frame is b, where b = 0 or 1, can be calculated using Lemma 1. Lemma 1. Let t be the actual tag population size, f be the frame size, p be the persistence probability ( i.e., the proba￾bility that a tag participates in a frame), and qb be the prob￾ability that a slot in a frame is b. Thus: qb =  (1 − p f ) t if b = 0 1 − (1 − p f ) t if b = 1 (1) Proof. The probability that a tag chooses a given slot in a frame is p/f. The probability that it does not choose that slot is 1 − p f . The probability that none of the tags choose that slot is (1 − p f ) t , which is the value of q0. As the tags choose the slots independently, qb is the same for each slot of the frame. The probability that a slot is chosen by at least one tag is 1 − q0, which is the value of q1. Let Sb,i be the random variable representing the run size of b starting at location i in a frame. If the i-th slot is not the starting point of a run, then Sb,i = 0. The expectation and variance of Sb,i can be calculated using Theorem 1. Theorem 1. Let Sb,i be the random variable representing the run size of b starting at location i in a frame of size f. Let a = f − i + 1. The expectation and variance of Sb,i are: E[Sb,i] = qb 1 − qb (1 − qa b ) (2) Var(Sb,i) = qb + (2a + 1)(qa+2 b − qa+1 b ) − q 2(a+1) b (1 − qb)2 (3) Proof. To calculate the expected value of Sb,i, we first need its probability density function P{Sb,i = s}. The prob￾ability that a run starting at location i will be of length s is the product of the probability that s consecutive slots are b and s + i th slot is b, where b = 1 − b. Thus, P{Sb,i = s} = ⎧ ⎨ ⎩ qs b (1 − qb) if sa where 1 ≤ i ≤ f and 1 ≤ s ≤ a. To derive the expected value and variance of Sb,i, we use the moment generating function: φ(τ ) = E[e τSb,i ] = a s=1 e τsP{Sb,i = s} = (qbe τ ) a + (1 − qb) a −1 s=1 (qbe τ ) s Differentiating both side w.r.t. τ , we get φ (τ )=a(qbe τ ) a + (1 − qb)(qbe τ ) a −1 s=1 s(qbe τ ) s−1 = a(qbe τ ) a + (1 − qb)(qbe τ ) d d(qbeτ ) 1 − (qbeτ ) a 1 − qbeτ − 1 = a(qbe τ ) a + (1 − qb) (a − 1)(qbeτ ) a+1 − a(qbeτ ) a + qbeτ (1 − qbeτ )2 Evaluation of φ (τ ) at τ = 0 gives us Equation (2). To find Var(Sb,i), we calculate E[S2 b,i] by taking the second deriva￾tive of φ (τ ) and setting τ = 0. Thus, E[S2 b,i] = qb + q2 b + (2a − 1)qa+2 b − (2a + 1)qa+1 b (1 − qb)2 Evaluating E[S2 b,i] − E2[Sb,i] gives Equation (3). Let Xb be the random variable representing the average run size of b in a frame. Next, we calculate the expectation and variance of Xb using the expectation and variance of Sb,i from Theorem 1. The expectation of Xb will be used to esti￾mate the tag population size and the variance of Xb will be used to calculate optimal values for f, p, and n. Let Yb be the random variable representing the number of times b oc￾curs in a frame and Rb be the random variable representing the number of runs of b in a frame. By definition, Xb = Yb Rb holds for any frame. Next, we first calculate E[Yb], Var(Yb), E[Rb], Var(Rb), and Cov(Yb, Rb) in Lemmas 2 and 3. Then, we use them to calculate E[Xb] and Var(Xb) in Theorem 2. Using Equation (14) in Theorem 2, replacing E[Xb] by the average run size of b from n frames, we obtain an equation with only one variable t. Finally, we use Brent’s method to obtain the numerical solution of this equation. The result is the estimated tag population size. Since ART uses Xb to estimate the tag population size, we call Xb the estimator of ART. 368

LEMMA 2.Let Yi be the random variable representing the Here we used the fact that the frame size is always greater mumber of times b occurs in a frame and Ro be the random than 1 during the estimation process whenever the informa- variable representing the number of runs of b in a frame. tion about runs is used.As I;~Bernoulli(o),its variance Given tag population size t,frame size f,and persistence is that of a bernoulli random variable given by probability p,we have: Var(Ii)=E[Ii](1-E[Ii]) (⑧) E[Yi]=fqb (4) Var(Y)=fqb(1-q6) (5) Note that Ii and I,are dependent on each other if and only if (iff)i=j-1 because Ij-1 and I;can not both be 1 in ER]=(9地+f(1-9B) (6) the same frame.Other than that,Vi Cov(Ij-1,Ij) 1=3 =-或+mú-)-*（色二 =qb(1-9B)+(f-1)g(1-9b){1-qB(1-9b)} 1-9%一 -2q6(1-6)-2(J-2)96(1-9%)2 =∫q地 =f(9%-4g6+6g-3q6)+(3q6-8q+5q6)▣ Each slot i of frame f has probability go of being b.So Y~Binom(f,go).Thus,Var(Yo)is simply the variance of LEMMA 3.Given tag population size t,frame size f,and a binomial distribution with parameters f and g: persistence probability p,we have: Var(Y)=fgo(1-gb) 「1 Cov(Y6,R)=yrq%(1-q)/-".{,,r} Let 72,...,Yf represent the sequence of binary random =0r=0 variables representing the value of each slot in a frame of size -E[Y]E[Ru] (9) f.Since each tag randomly and independently picks a slot in the frame,all i are identically distributed.Furthermore. where P=b}=go.Let Ii be the indicator random variable whose value is 1 if a run of b begins at Yi. ()[2)+2")+--] ifr>1∧0) (-)[2)+-g-] Thus. 5{f,,r}= ifr=1A01 0 otherwise we get PROOF.By definition,we have E=2=+2n1-)=n+-m》 Cov(Yi,R)=>yPYi=y.R.=r}-E[Yi]E[Rs] =2 y=0T=0 (10) As Ro is the sum of f identically distributed random vari- Here P=y,R=r}represents the probability that ex- ables,we use the general expression for the variance of the actly y out of f slots in the frame are b and at the same time sum of identically distributed random variables to obtain the number of runs of b is r.This probability is difficult to the variance of R. evaluate directly,but conditioning on Yo simplifies the task. P{Y=,B=r}=P{R=rY=}×P{=} Var(Rb)=Var(Ii) (11) As Y~Binom(f,)we have: a+2∑cowu. P=}= (12) j=2i< 369

Lemma 2. Let Yb be the random variable representing the number of times b occurs in a frame and Rb be the random variable representing the number of runs of b in a frame. Given tag population size t, frame size f, and persistence probability p, we have: E[Yb] = fqb (4) Var(Yb) = fqb(1 − qb) (5) E[Rb] = qb  qb + f(1 − qb)  (6) Var(Rb) = f(qb − 4q2 b + 6q3 b − 3q4 b ) + (3q2 b − 8q3 b + 5q4 b ) (7) Proof. The expected size of a run of b starting at loca￾tion i is E[Sb,i]. A run of b starting at location i means that the slot i − 1 is b. Thus, E[Yb] = E[Sb,1] + f i=2 E[Sb,i] × P slot i − 1 is b = qb 1 − qb (1 − qf b ) + f i=2 qb 1 − qb (1 − qf−i+1 b ) × (1 − qb) = qb 1 − qb (1 − qf b ) + qb (f − 1) − qf+1 b q−2 b − q −(f+1) b 1 − q−1 b  = fqb Each slot i of frame f has probability qb of being b. So Yb ∼ Binom(f, qb). Thus, Var(Yb) is simply the variance of a binomial distribution with parameters f and qb: Var(Yb) = fqb(1 − qb) Let γ1, γ2,..., γf represent the sequence of binary random variables representing the value of each slot in a frame of size f. Since each tag randomly and independently picks a slot in the frame, all γi are identically distributed. Furthermore, P {γi = b} = qb. Let Ii be the indicator random variable whose value is 1 if a run of b begins at γi. Ii =  1 if (γi = b, i = 1) ∨ (γi = b ∧ γi−1 = b, i > 1) 0 otherwise Thus, Rb =  f i=1 Ii Because E[Ii] =  P {γi = b} = qb if i = 1 P γi−1 = b, γi = b = qb(1 − qb) if i > 1 we get E[Rb] =  f i=1 E[Ii] = qb + f i=2 qb(1 − qb) = qb  qb + f(1 − qb)  As Rb is the sum of f identically distributed random vari￾ables, we use the general expression for the variance of the sum of identically distributed random variables to obtain the variance of Rb. Var(Rb) = Var( f i=1 Ii) =  f i=1 Var(Ii)+2 f j=2  ∀i 1 ∧ 0 <y<f ∧ r ≤ y ∧ r ≤ f − y − 1 y−1 r−1  2 f−y−1 r−1  + f−y−1 r  if r = 1 ∧ 0 <y<f ∧ r ≤ y ∧ r ≤ f − y − 1 1 if r = 1 ∧ y = f 1 if r = 0 ∧ y = 0 0 otherwise Proof. By definition, we have Cov(Yb, Rb) =  f y=0  f r=0 yrP {Yb = y, Rb = r} − E[Yb]E[Rb] (10) Here P {Yb = y, Rb = r} represents the probability that ex￾actly y out of f slots in the frame are b and at the same time the number of runs of b is r. This probability is difficult to evaluate directly, but conditioning on Yb simplifies the task. P {Yb = y, Rb = r} = P {Rb = r|Yb = y} × P {Yb = y} (11) As Yb ∼ Binom(f, qb), we have: P {Yb = y} =  f y  qy b (1 − qb) f−y (12) 369

Now we calculate P{=ry=y}i.e.,the probability of ing expansion of the Taylor series of g(Y,R): having r runs of b in a frame of size f given that y out of f slots are b.As tags choose the slots independently,each g6,)=ga,)+[6-0)器+(-)2】 0g occurrence with r runs having y slots of b is equally likely. Therefore,we determine the total number of ways,denoted +2(Y%-0A)(B-02) 82g by gff,y,r},in which y occurrences of b and f-y occur- OYioR rences of b can be arranged such that the number of runs of b is r.We treat this as an ordered partition problem.First, +(B-2)22g】 aR +0G-1) we separate all the y occurrences of b from the frame and make r partitions of these y occurrences.Then,we create appropriate number of partitions of f-y occurrences of 6 Taking the expectation of both sides,we get such that between consecutive partitions of b,the partitions 8g of b can be interleaved.For r partitions of b,there are 4 E[g(Ya,R6】≈ 21 Var(Y) possible partitions of b. +2Co06,)8品 8g 1.The frame starts with b and ends with b,implying that +Var(Ro) +g(01,02)】 (16) there arer-1 partitions of b,each interleaved between adjacent partitions of b. Evaluating the partial derivatives of g as required in Equa- tion (16),we get 2.The frame starts with b and ends with b,implying that there are r partitions of b. 8g(Yu,R) =0 ayp 3.The frame starts with b and ends with b,implying that there are r partitions of b. 82g(Yi,R) 1 8Y%8R6 ￥==一 Rb=82 4.The frame starts with b and ends with b,implying that 82g(Yi,Ru) there are r+1 partitions of b. a We can make r partitions of y occurrences of b in ( ways and r partitions of f-y occurrences of in ( Putting these values in Equation (16)and using 01=E[Y] and 02 E[R],we get Equation (14). ways.Similarly,we can make r+1 partitions of f-y occur- The variance can be calculated as follows: rences of B in (1)ways and r-1 partitions ofof f-y occurrences of in (ways.The equation ofy Var(g(6,R)=E[{g(%,R)-E[g(,)J}](17) in the lemma statement follows from this discussion.The to- tal number of ways in which y zeros can be arranged among Considering that E[g(Y,R)]is being squared in the expres- f slots is ()Thus,we get sion above,we use first order Taylor series expansion to get the value of E[g(Yo,R)]and substitute it in Equation (17). P{=r%==U (13) ( ,=E[s-器+风-器】 +g(01,02)+0G1) Substituting values from Equations (12)and (13)in (11) and (10)results in Equation (9). =[o鼎+o]+9a,+oU=9e.) THEOREM 2.Given tag population size t,frame size f, Substituting the value of Elg(Y,Ro)]and using the first and persistence probability p,we have: order Taylor series expansion of g(Yo,R)in (17),we get E[X]= EY Cov(Y.R)E[Yo]Var(R) ERu] ES Ru (14) E2R Var(a(6A=Ec-8器+(-器月 +00-1) dg og Var(X)= Var(Y) E2YolVar(R) 2E[Yo]Cov(Y R)+ER] ≈Var(Ya)( E2R]E3[Ru] +2Cov(Yo.Rw)aYR +Var(Ro)( 0g2 (15) (18) PROOF.Let g(R)==The Taylor series ex- Evaluating the partial derivatives of g as required in the pansion of g around (01,02)is given by: equation above,we get 9,-6-品+（风-品] 81 Og(Yi,R) 1 ∂Y6 Y6=81 h=2 ÷02 1=0 Og(Y,R) 01 g6,R)}￥=a: aR ==一房 R6=2 R=a2 According to Bienayme-Chebyshev inequality,we have Putting these values in Equation(18)and using 01=E[Y] 01 E[Yo]and 02 E[R].Therefore,we get the follow- and 02=E[R],we get Equation(15). 370

Now we calculate P {Rb = r|Yb = y} i.e., the probability of having r runs of b in a frame of size f given that y out of f slots are b. As tags choose the slots independently, each occurrence with r runs having y slots of b is equally likely. Therefore, we determine the total number of ways, denoted by ξ {f, y, r}, in which y occurrences of b and f − y occur￾rences of b can be arranged such that the number of runs of b is r. We treat this as an ordered partition problem. First, we separate all the y occurrences of b from the frame and make r partitions of these y occurrences. Then, we create appropriate number of partitions of f − y occurrences of b such that between consecutive partitions of b, the partitions of b can be interleaved. For r partitions of b, there are 4 possible partitions of b. 1. The frame starts with b and ends with b, implying that there are r−1 partitions of b, each interleaved between adjacent partitions of b. 2. The frame starts with b and ends with b, implying that there are r partitions of b. 3. The frame starts with b and ends with b, implying that there are r partitions of b. 4. The frame starts with b and ends with b, implying that there are r + 1 partitions of b. We can make r partitions of y occurrences of b in y−1 r−1  ways and r partitions of f − y occurrences of b in f−y−1 r−1  ways. Similarly, we can make r + 1 partitions of f −y occur￾rences of b in f−y−1 r  ways and r − 1 partitions of of f − y occurrences of b in f−y−1 r−2  ways. The equation of ξ {f, y, r} in the lemma statement follows from this discussion. The to￾tal number of ways in which y zeros can be arranged among f slots is f y  . Thus, we get P {Rb = r|Yb = y} = ξ {f, y, r} f y  (13) Substituting values from Equations (12) and (13) in (11) and (10) results in Equation (9). Theorem 2. Given tag population size t, frame size f, and persistence probability p, we have: E[Xb] = E[Yb] E[Rb] − Cov(Yb, Rb) E2[Rb] + E[Yb] E3[Rb] Var(Rb) (14) Var(Xb) = Var(Yb) E2[Rb] − 2E[Yb] E3[Rb] Cov(Yb, Rb) + E2[Yb] E4[Rb] Var(Rb) (15) Proof. Let g(Yb, Rb) = Xb = Yb Rb . The Taylor series ex￾pansion of g around (θ1, θ2) is given by: g(Yb, Rb) = ∞ j=0  1 j! (Yb − θ1) ∂ ∂Y b + (Rb − θ2) ∂ ∂R b j × g(Y b , R b)  Y b =a1 R b=a2 According to Bienaym´e-Chebyshev inequality, we have θ1 = E[Yb] and θ2 = E[Rb]. Therefore, we get the follow￾ing expansion of the Taylor series of g(Yb, Rb): g(Yb, Rb) = g(θ1, θ2) + (Yb − θ1) ∂g ∂Yb + (Rb − θ2) ∂g ∂Rb  + 1 2 (Yb − θ1) 2 ∂2g ∂Y 2 b + 2(Yb − θ1)(Rb − θ2) ∂2g ∂Yb∂Rb + (Rb − θ2) 2 ∂2g ∂R2 b  + O(j −1 ) Taking the expectation of both sides, we get E[g(Yb, Rb)] ≈ 1 2 Var(Yb) ∂2g ∂Y 2 b + 2Cov(Yb, Rb) ∂2g ∂Yb∂Rb +Var(Rb) ∂2g ∂R2 b  + g(θ1, θ2) (16) Evaluating the partial derivatives of g as required in Equa￾tion (16), we get ∂2g(Yb, Rb) ∂Y 2 b   Yb=θ1 Rb=θ2 = 0 ∂2g(Yb, Rb) ∂Yb∂Rb   Yb=θ1 Rb=θ2 = − 1 θ2 2 ∂2g(Yb, Rb) ∂R2 b   Yb=θ1 Rb=θ2 = 2 θ1 θ3 1 Putting these values in Equation (16) and using θ1 = E[Yb] and θ2 = E[Rb], we get Equation (14). The variance can be calculated as follows: Var g(Yb, Rb)  = Eg(Yb, Rb) − E[g(Yb, Rb)]2 (17) Considering that E[g(Yb, Rb)] is being squared in the expres￾sion above, we use first order Taylor series expansion to get the value of E[g(Yb, Rb)] and substitute it in Equation (17). E[g(Yb, Rb)] = E (Yb − θ1) ∂g ∂Yb + (Rb − θ2) ∂g ∂Rb  +g(θ1, θ2) + O(j −1 ) = (0) ∂g ∂Yb + (0) ∂g ∂Rb  + g(θ1, θ2) + O(j −1 ) ≈ g(θ1, θ2) Substituting the value of E[g(Yb, Rb)] and using the first order Taylor series expansion of g(Yb, Rb) in (17), we get Var g(Yb, Rb)  = E(Yb − θ1) ∂g ∂Yb + (Rb − θ2) ∂g ∂Rb 2 +O(j −1 ) ≈ Var(Yb)( ∂g ∂Yb ) 2 + 2Cov(Yb, Rb) ∂g ∂Yb ∂g ∂Rb + Var(Rb)( ∂g ∂Rb ) 2 (18) Evaluating the partial derivatives of g as required in the equation above, we get ∂g(Yb, Rb) ∂Yb   Yb=θ1 Rb=θ2 = 1 θ2 ∂g(Yb, Rb) ∂Rb   Yb=θ1 Rb=θ2 = −θ1 θ2 2 Putting these values in Equation (18) and using θ1 = E[Yb] and θ2 = E[Rb], we get Equation (15). 370

-ART -ART →Size of first run of0s ·Simulations Simulations Avg.run size of 0s -Total 0s 101 …Total1s 10 8 +Runs of 1s Runs of 0s -Avg.run size of 1s 10 Number of tag 100 150 umber oftagst 100 150 10 Number of tag Figure 2:Variances of ART estima-Figure 3:Expectation of ART esti-Figure 4:Variance of different esti- tor mator mators vs.t Figure 2 contains a line plotting the variance of xI using are calculated as follows.The variance of the total num- Equation (15),where f=16 and p=1.This figure also con- ber of 0s and 1s can be calculated using Equation (5).The tains many dots where each dot represents the variance of Xi variance of the size of the first run can be calculated using that we obtained through 100 times of simulation for each Equation (3)by setting i =1.The variance of the number tag population size.This figure shows that for the variance of runs of Os and that of Is can be calculated using Equation of X1,simulation results match with the variance calculated (7).We emphasize that plots in Figure 4 are not based on from Equation (15).Figure 3 contains a line plotting the experimental results,instead,they are based on analytical expectation of XI using Equation (14),where f 16 and formulas. p 1,and many dots where each dot represents the av- erage value of Xi that we obtained through 100 times of 4.3 Unbounded Tag Population Size simulation for each tag population.This figure shows that For fixed values of required reliability o,frame size f,and the expected value calculated from Equation(14)tracks the persistence probability p,Theorem 3 calculates the upper simulation results very well. bound tu on the number of tags that ART can estimate; that is,for tag population sizes larger than tM,all the slots 4.2 Analytical Comparison of Estimators in each frame are expected to be 1 and thus ART cannot Although both Xo and Xi can be used to estimate the make an estimate because the tag population size can be tag population size,we choose Xi for ART because the tag infinitely large population size estimation calculated from Xi has smaller variance compared to Xo as we show below.It is worth not- THEOREM 3.For given required reliability a E 0,1), ing that Xo and Xi are not equivalent estimators.The av- frame size f>1,persistence probability p>0,the mari- erage run size of 0s cannot be inferred from the average run mum number of tags tM that ART can estimate is: size of 1s,and vice versa.For example,1100011 and 1100110 log{1-(1-a)7} have the same average run size of 1s,but they have different tM= average run size of 0s.Fundamentally,Xo and Xi are not 1og{1-} equivalent estimators because for any slot,the probability of PROOF.ART fails if and only if all the slots are 1.To it being 0(which means no tag chooses this slot)and that of achieve the required reliability a,the failure probability of it being 1(which means one or more tags choose this slot) ART P{Yi=f)=qf has to be less than 1-a.Using the are different. value of gi calculated in Lemma 1.we have Next,we show that the ART estimator.namely the aver- age run size of 1s,has less variance than many other framed P===-（-)门 <1-a slotted Aloha based estimators,namely (1)the size of the first run of 0s(used by FNEB [6]),(2)the average run size of Thus,by taking the log,we have 0s,(3)the total number of 0s(used by UPE [7]and EZB [8]), (4)the total number of 1s,(5)the total number of runs of 1og1-1-a)}<og1-f} 0s,and (6)the total number of runs of 1s.The higher the variance of an estimator is,the more number of rounds n are As log{1-号}<0，dividing both sides by log{1-号} needed to improve reliability,and more rounds means more changes the direction of inequality and results in: estimation time.Figure 4 shows the analytical plots of the variances of the ART estimator and the above 6 other esti- t< mators with frame size f=16 versus tag population sizes. osL-1-a边}=tw口 1og{1-号} This figure shows that the variance of ART estimator is sig- mificantly lower than all other estimators.Runs of 1s and From this theorem,we observe that as p/f-0 we have runs of 0s have smaller variance compared to ART for very t-oo.Figure 5 shows the plot of ta for increasing val- small tag population sizes.This observation,however,is in- ues of p and 4 different values of f with required reliability significant because both these quantities are non-monotonic a=99%.In theory,for any given required reliability a,we functions of tag population size and therefore,cannot be can increase the estimation scope of ART to any value by used alone for estimation.The variances of these estimators decreasing the value of p/f.In practice,however,p/f has 371

0 50 100 150 0 5 10 15 20 25 30 Number of tags t Variance ART Simulations Figure 2: Variances of ART estima￾tor 0 50 100 150 0 5 10 15 Number of tags t Average Run Size ART Simulations Figure 3: Expectation of ART esti￾mator 101 102 100 102 Number of tags t Variance Size of first run of 0s Avg. run size of 0s Total 0s Total 1s Runs of 1s Runs of 0s Avg. run size of 1s Figure 4: Variance of different esti￾mators vs. t Figure 2 contains a line plotting the variance of X1 using Equation (15), where f = 16 and p = 1. This figure also con￾tains many dots where each dot represents the variance of X1 that we obtained through 100 times of simulation for each tag population size. This figure shows that for the variance of X1, simulation results match with the variance calculated from Equation (15). Figure 3 contains a line plotting the expectation of X1 using Equation (14), where f = 16 and p = 1, and many dots where each dot represents the av￾erage value of X1 that we obtained through 100 times of simulation for each tag population. This figure shows that the expected value calculated from Equation (14) tracks the simulation results very well. 4.2 Analytical Comparison of Estimators Although both X0 and X1 can be used to estimate the tag population size, we choose X1 for ART because the tag population size estimation calculated from X1 has smaller variance compared to X0 as we show below. It is worth not￾ing that X0 and X1 are not equivalent estimators. The av￾erage run size of 0s cannot be inferred from the average run size of 1s, and vice versa. For example, 1100011 and 1100110 have the same average run size of 1s, but they have different average run size of 0s. Fundamentally, X0 and X1 are not equivalent estimators because for any slot, the probability of it being 0 (which means no tag chooses this slot) and that of it being 1 (which means one or more tags choose this slot) are different. Next, we show that the ART estimator, namely the aver￾age run size of 1s, has less variance than many other framed slotted Aloha based estimators, namely (1) the size of the first run of 0s (used by FNEB [6]), (2) the average run size of 0s, (3) the total number of 0s (used by UPE [7] and EZB [8]), (4) the total number of 1s, (5) the total number of runs of 0s, and (6) the total number of runs of 1s. The higher the variance of an estimator is, the more number of rounds n are needed to improve reliability, and more rounds means more estimation time. Figure 4 shows the analytical plots of the variances of the ART estimator and the above 6 other esti￾mators with frame size f = 16 versus tag population sizes. This figure shows that the variance of ART estimator is sig￾nificantly lower than all other estimators. Runs of 1s and runs of 0s have smaller variance compared to ART for very small tag population sizes. This observation, however, is in￾significant because both these quantities are non-monotonic functions of tag population size and therefore, cannot be used alone for estimation. The variances of these estimators are calculated as follows. The variance of the total num￾ber of 0s and 1s can be calculated using Equation (5). The variance of the size of the first run can be calculated using Equation (3) by setting i = 1. The variance of the number of runs of 0s and that of 1s can be calculated using Equation (7). We emphasize that plots in Figure 4 are not based on experimental results, instead, they are based on analytical formulas. 4.3 Unbounded Tag Population Size For fixed values of required reliability α, frame size f, and persistence probability p, Theorem 3 calculates the upper bound tM on the number of tags that ART can estimate; that is, for tag population sizes larger than tM, all the slots in each frame are expected to be 1 and thus ART cannot make an estimate because the tag population size can be infinitely large. Theorem 3. For given required reliability α ∈ [0, 1), frame size f > 1, persistence probability p > 0, the maxi￾mum number of tags tM that ART can estimate is: tM = log 1 − (1 − α) 1 f log 1 − p f Proof. ART fails if and only if all the slots are 1. To achieve the required reliability α, the failure probability of ART P {Y1 = f} = qf 1 has to be less than 1 − α. Using the value of q1 calculated in Lemma 1, we have P {Y1 = f} = qf 1 = 1 − 1 − p f tf < 1 − α Thus, by taking the log, we have log 1 − (1 − α) 1 f  < tlog 1 − p f  As log 1 − p f  < 0, dividing both sides by log 1 − p f  changes the direction of inequality and results in: t < log 1 − (1 − α) 1 f log 1 − p f = tM From this theorem, we observe that as p/f → 0 we have tM → ∞. Figure 5 shows the plot of tM for increasing val￾ues of p and 4 different values of f with required reliability α = 99%. In theory, for any given required reliability α, we can increase the estimation scope of ART to any value by decreasing the value of p/f. In practice, however, p/f has 371

-f=200 0.4 800 15000 .f=100 .f=50 0.3 f=10 700 0 10000 0.2 7600 5000 500 0.2 0.4 0.6 0. 0.2 0.4 0.6 0.8 400 0.8 10 20 30 40 50 Persistence probability p Persistence probabilty p Frame size f Figure 5:tM vs.p and f Figure 6:Eq.(19)as func.of p Figure7:(f+3)×nvs.f a minimum value of 1/232 due to the 32-bit limitation of P{1-Bt≤{X}≤(1+B)} the hash functions used by passive tags as specified in the C1G2 standard.Recall that in ART,the reader announces =Pμ{1-B)≤X1≤4{(1+B)〉=a(21) a virtual frame size of f/p(although terminates the frame after the first f slots)and each tag uses the result of a hash Based on the fact that the variance of a random variable function h to select a slot in the range [1,f/p).The number is reduced by n times if the same experiment is repeated of bits to encode the hash function result is specified to be n times,by running n rounds and getting n frames,the 32 in the C1G2 standard.Thus,the maximum value of f/p variance of Xi becomes and the standard deviation of is 232.Therefore,the maximum number of tags that ART Xi becomes Let Zdenote Thus,(21)becomes can estimate based on the C1G2 standard is: aft/vn l1og{1-(1-a)7} 1og{1-2应} L-8-μ&≤Z≤+80-世 ot ait Q Here tcic is large enough for all practical applications. (22 For example,with f =512 and a 90%,tMcic2 is By the central limit theorem,Z approximates a standard 2.3221e+10,which is over 23 billion;with f 512 and normal random variable.The area under the standard nor- =99%,tcc is 2.0254e+10,which is over 20 billion. mal curve gives the success probability,which is the required reliability in our context.As our confidence interval require 5.ART-PARAMETER OPTIMIZATION ment is symmetric on both the upper and lower sides of the population size,we can represent the required reliability a To minimize estimation time while achieving required re- in terms of a constant k as follows: liability,next,we optimize the three ART parameters:frame size f,persistence probability p,and number of rounds n. P{-k≤Z≤k}=a (23) 5.1 Optimizing Persistence Probability p From Equations (22)and (23),we get Theorem 4 gives the condition that p needs to satisfy so that the actual reliability is equal to its lower bound,which 4{但-B4-世=-k, 4{但+B)-4=K is the required reliability a.We first prove this theorem and 碧 then show how to calculate the optimal value for p. (24) As the absolute values of the right hand size (R.H.S.)of both THEOREM 4.Given confidence interval B,tag population equations above are k,we get size t,and frame size f,denoting EX]by uith,the optimal persistence probability pop satisfies the following equation. 2μ{母-4{(1-)t}-μ{(1+B)t)=0▣ (25) 2μ{t-μ{(1-B)号-μ{(1+3)}=0(19) Next,we show how to calculate the optimal value for p PROOF.To find the optimal value pop for p,we first find using Theorem 4,which shows that pop only depends on the conditions that pop needs to satisfy so that the actual confidence interval B,tag population size t,and frame size reliability Pt-t<Bt is equal to its lower bound,which f.For now,we first assume that we know an upper bound is the required reliability a. on the tag population size denoted by tm.Later we give a method to obtain tm automatically.Second,we assume that P{(1-B)t≤t≤(1+B)t}=a (20 we know the optimal frame size fop.Later we give a method to calculate fop.Replacing t by tm and f by fop,left hand Denoting the observed average value of Xi from the n frames side (L.H.S)of Equation (19)in Theorem 4 becomes a well by X1.E[Xi]by uft),and Var(X1)by o2{t),we have t behaved function of p as shown in Figure 6.The numerical X1).Using [X1}to substitute i in (20),we get solution of this equation gives the optimal value pop. 372

0 0.2 0.4 0.6 0.8 1 0 5000 10000 15000 Persistence probability p Maximum number of tags tM f=200 f=100 f=50 f=10 Figure 5: tM vs. p and f 0 0.2 0.4 0.6 0.8 1 −0.1 0 0.1 0.2 0.3 0.4 Persistence probabilty p Function value Figure 6: Eq. (19) as func. of p 10 20 30 40 50 400 500 600 700 800 Frame size f (f + 3) × n Figure 7: (f + 3) × n vs. f a minimum value of 1/232 due to the 32-bit limitation of the hash functions used by passive tags as specified in the C1G2 standard. Recall that in ART, the reader announces a virtual frame size of f /p (although terminates the frame after the first f slots) and each tag uses the result of a hash function h to select a slot in the range [1, f /p]. The number of bits to encode the hash function result is specified to be 32 in the C1G2 standard. Thus, the maximum value of f /p is 232. Therefore, the maximum number of tags that ART can estimate based on the C1G2 standard is: tMC1G2 = log 1 − (1 − α) 1 f log 1 − 1 232 Here tMC1G2 is large enough for all practical applications. For example, with f = 512 and α = 90%, tMC1G2 is 2.3221e+10, which is over 23 billion; with f = 512 and α = 99%, tMC1G2 is 2.0254e+10, which is over 20 billion. 5. ART — PARAMETER OPTIMIZATION To minimize estimation time while achieving required re￾liability, next, we optimize the three ART parameters: frame size f, persistence probability p, and number of rounds n. 5.1 Optimizing Persistence Probability p Theorem 4 gives the condition that p needs to satisfy so that the actual reliability is equal to its lower bound, which is the required reliability α. We first prove this theorem and then show how to calculate the optimal value for p. Theorem 4. Given confidence interval β, tag population size t, and frame size f, denoting E[X1] by μ {t}, the optimal persistence probability pop satisfies the following equation. 2μ {t} − μ {(1 − β)t} − μ {(1 + β)t} = 0 (19) Proof. To find the optimal value pop for p, we first find the conditions that pop needs to satisfy so that the actual reliability P |t ˜− t| ≤ βt is equal to its lower bound, which is the required reliability α. P (1 − β)t ≤ t ˜≤ (1 + β)t = α (20) Denoting the observed average value of X1 from the n frames by X˜1, E[X1] by μ {t}, and Var(X1) by σ2 {t}, we have t ˜= μ−1{X˜1}. Using μ−1{X˜1} to substitute t ˜ in (20), we get P  (1 − β)t ≤ μ−1 {X˜1} ≤ (1 + β)t  = P  μ {(1 − β)t} ≤ X˜1 ≤ μ {(1 + β)t}  = α (21) Based on the fact that the variance of a random variable is reduced by n times if the same experiment is repeated n times, by running n rounds and getting n frames, the variance of X1 becomes σ2{t} n and the standard deviation of X1 becomes σ{t} √n . Let Z denote X˜1−μ{t} σ{t}/ √n . Thus, (21) becomes P  μ {(1 − β)t} − μ {t} σ{t} √n ≤ Z ≤ μ {(1 + β)t} − μ {t} σ{t} √n  = α (22) By the central limit theorem, Z approximates a standard normal random variable. The area under the standard nor￾mal curve gives the success probability, which is the required reliability in our context. As our confidence interval require￾ment is symmetric on both the upper and lower sides of the population size, we can represent the required reliability α in terms of a constant k as follows: P {−k ≤ Z ≤ k} = α (23) From Equations (22) and (23), we get μ {(1 − β)t} − μ {t} σ{t} √n = −k, μ {(1 + β)t} − μ {t} σ{t} √n = k (24) As the absolute values of the right hand size (R.H.S.) of both equations above are k, we get 2μ {t} − μ {(1 − β)t} − μ {(1 + β)t} = 0 (25) Next, we show how to calculate the optimal value for p using Theorem 4, which shows that pop only depends on confidence interval β, tag population size t, and frame size f. For now, we first assume that we know an upper bound on the tag population size denoted by tm. Later we give a method to obtain tm automatically. Second, we assume that we know the optimal frame size fop. Later we give a method to calculate fop. Replacing t by tm and f by fop, left hand side (L.H.S) of Equation (19) in Theorem 4 becomes a well behaved function of p as shown in Figure 6. The numerical solution of this equation gives the optimal value pop. 372

5.2 Minimizing Number of Rounds n f arbitrarily small,theoretically,it will still be possible to Using optimal persistence probability pop,the two equa- obtain the estimate accurately:however.in this case.n can tions in(24)hold.From them,we get be prohibitively large making it practically impossible to obtain the estimate as per the accuracy requirements. kafty 2 -kot =n= μ{1+)}-μ{t} μ{(1-B)}-μ{ 5.4 Observably Constant Estimation Time (26) Let be the cumulative distribution function of a standard There are three inputs to ART:confidence interval B,re- normal distribution and erf{.}be the standard error func- quired reliability a,and a population of t tags where t is un- tion,we get known.The total estimation time of ART is(fop+3)x nop, P{-k≤Z≤k}=Φ()-(-)=erf which from our experiments we observe to be dependent (27) only on B and a,i.e.,(fop+3)x nop is constant with re spect to (w.r.t.)t.Because (fop+3)x nop is highly com- From Equations(23)and(27),we get plex due to complex components such as Cov(Y,R)as ex- k=v2 erf a} (28) pressed in Equation (9),we have not yet formally proven that (fop +3)x nop is independent of t,although we hy- From Equations(26)and(28),we get pothesize that this is mathematically true.Intuitively,the 2erf1{a×a{t2 =n= (-V2erf-1{a}×o{t larger t is,the smaller pop is.Although t plays an important role in computing pop,nop,and fop individually,in formula 、μ{(1+)}-μ{t μ{(1-)t母-μ{t母 (fop+3)x nop the impact of t gets canceled out.From Equa- (29) tions(29)and(31),we observe that the value of nop depends Based on this equation,with B,a,p Pop,t=tm,and upon a,B,u,a and value of fop depends upon B,u,a.Here f fop,we can calculate the minimal value nop for n. (fop+3)x nop is independent of t because a and B are given values and u and o are functions of gi,if g is independent of 5.3 Optimizing Frame Size f t.Indeed gi is intuitively independent of t because g 1/t Our goal of optimizing ART parameters,namely p,n,and and pop obtained from Equation(19)decreases as the value f,is to minimize the total estimation time,which is(f+3)x of tm increases,as shown in Figure 8.A constant value of nop.Because B,a,and tm are known and pop is a function gi means that the probability of any slot in a frame being of f,nop is essentially a function of f.Thus,(f+3)x nop non-empty is the same,which in turn implies that average is a function of f.Next,we show how to find the optimal run size in a frame will also be the same regardless of t.Fig- frame size fop so that (f+3)x nop is minimized. ure 9 plots the value of g w.r.t.t using Equations(19)and Function (f+3)x nop is a convex function of f as seen (1).We observe that the value of gi stays perfectly constant from Figure 7.This means that an optimal frame size fop w.r.t.t.Figure 10 shows that the total estimation time of exists and can be obtained by differentiating (f+3)x nop ART stays constant w.r.t.t for given B and a. with respect to f as shown in the following equation: 5.5 Obtaining Population Upper Bound ti 哥+)×n,}=0 (30) So far we have assumed the knowledge of an upper bound tm on tag population size t.In some applications,tm is read- ily available.For example,the number of TVs in a TV ware- As both expressions for n given in Equation(29)have the house can be reasonably estimated by the warehouse size same value when p =pop:either of them can be used to and minimum TV size.However,this may not be available calculate the value of nop.By substituting nop in Equation for some applications where the tag population size changes (30)by the L.H.S of the nop expression in Equation(29),we in large magnitude.We next present a fast scheme to ob- get tain tm based on Flajolet and Martin's probabilistic count- 4+}--b+ ing algorithm used in databases 5.Before running ART the reader uses this scheme to obtain tm.In this scheme, -27[u+a_g the reader keeps issuing single-slot frames,where the persis- (31 tence probability p follows a geometric distribution starting fromp=1 (i.e.,p=zr in the i-th frame),until the reader whereandare obtained through the differen- gets an empty slot.Suppose the empty slot occurred in the 3 i-th frame,then tm =1.2897 x 2i-2 is an upper bound on tiation of expressions for EX and Var(X)in Equations t[5,14 (14)and (15),respectively. To obtain of fop from Equation(31),we need the value of 5.6 ART with Multiple Readers Pop,while to obtain the value of pop from Equation(19),we We next discuss how to obtain tm and t using multiple need the value of fop.Therefore,we have two simultaneous readers whose covered regions may overlap.To obtain tm equations,(19)and (31),with two unknowns,fop and Pop. using multiple readers,we can let each reader obtain the t These equations can be numerically solved simultaneously value on its own and then sum them up as the final overall using Levenberg-Marquardt Algorithm to obtain the values tm because of two reasons.First,our requirement on tm is of fop and pop. only a rough upper bound estimate.Second,deployment of Note that the estimation scheme will still work if we do multiple readers in practice often requires site surveys to en- not use f =fop,but in that case the value of n will be sure minimal overlapping between readers.To use multiple such that the (f+3)x n will not be minimum.If we make readers to obtain t more precisely,we adapt the approach 373

5.2 Minimizing Number of Rounds n Using optimal persistence probability pop, the two equa￾tions in (24) hold. From them, we get  kσ {t} μ {(1 + β)t} − μ {t} 2 = n =  −kσ {t} μ {(1 − β)t} − μ {t} 2 (26) Let Φ be the cumulative distribution function of a standard normal distribution and erf {.} be the standard error func￾tion, we get P {−k ≤ Z ≤ k} = Φ(k) − Φ(−k) = erf  k √2  (27) From Equations (23) and (27), we get k = √ 2 erf−1 {α} (28) From Equations (26) and (28), we get √2 erf−1 {α} × σ {t} μ {(1 + β)t} − μ {t} 2 =n= − √2 erf−1 {α} × σ {t} μ {(1 − β)t} − μ {t} 2 (29) Based on this equation, with β, α, p = pop, t = tm, and f = fop, we can calculate the minimal value nop for n. 5.3 Optimizing Frame Size f Our goal of optimizing ART parameters, namely p, n, and f, is to minimize the total estimation time, which is (f +3)× nop. Because β, α, and tm are known and pop is a function of f, nop is essentially a function of f. Thus, (f + 3) × nop is a function of f. Next, we show how to find the optimal frame size fop so that (f + 3) × nop is minimized. Function (f + 3) × nop is a convex function of f as seen from Figure 7. This means that an optimal frame size fop exists and can be obtained by differentiating (f + 3) × nop with respect to f as shown in the following equation: d df (f + 3) × nop = 0 (30) As both expressions for n given in Equation (29) have the same value when p = pop, either of them can be used to calculate the value of nop. By substituting nop in Equation (30) by the L.H.S of the nop expression in Equation (29), we get μ (1 + β)tm − μ tm  σ tm + 2f ∂σ tm ∂f  −2fσ tm ∂μ (1 + β)tm ∂f − ∂μ tm ∂f  = 0 (31) where ∂μ . ∂f and ∂σ . ∂f are obtained through the differen￾tiation of expressions for E[Xb] and Var(Xb) in Equations (14) and (15), respectively. To obtain of fop from Equation (31), we need the value of pop, while to obtain the value of pop from Equation (19), we need the value of fop. Therefore, we have two simultaneous equations, (19) and (31), with two unknowns, fop and pop. These equations can be numerically solved simultaneously using Levenberg-Marquardt Algorithm to obtain the values of fop and pop. Note that the estimation scheme will still work if we do not use f = fop, but in that case the value of n will be such that the (f + 3) × n will not be minimum. If we make f arbitrarily small, theoretically, it will still be possible to obtain the estimate accurately; however, in this case, n can be prohibitively large making it practically impossible to obtain the estimate as per the accuracy requirements. 5.4 Observably Constant Estimation Time There are three inputs to ART: confidence interval β, re￾quired reliability α, and a population of t tags where t is un￾known. The total estimation time of ART is (fop + 3) × nop, which from our experiments we observe to be dependent only on β and α, i.e., (fop + 3) × nop is constant with re￾spect to (w.r.t.) t. Because (fop + 3) × nop is highly com￾plex due to complex components such as Cov(Yb, Rb) as ex￾pressed in Equation (9), we have not yet formally proven that (fop + 3) × nop is independent of t, although we hy￾pothesize that this is mathematically true. Intuitively, the larger t is, the smaller pop is. Although t plays an important role in computing pop, nop, and fop individually, in formula (fop+3)×nop the impact of t gets canceled out. From Equa￾tions (29) and (31), we observe that the value of nop depends upon α, β, μ, σ and value of fop depends upon β, μ, σ. Here (fop + 3)×nop is independent of t because α and β are given values and μ and σ are functions of q1, if q1 is independent of t. Indeed q1 is intuitively independent of t because q1 ∝ 1/t and pop obtained from Equation (19) decreases as the value of tm increases, as shown in Figure 8. A constant value of q1 means that the probability of any slot in a frame being non-empty is the same, which in turn implies that average run size in a frame will also be the same regardless of t. Fig￾ure 9 plots the value of q1 w.r.t. t using Equations (19) and (1). We observe that the value of q1 stays perfectly constant w.r.t. t. Figure 10 shows that the total estimation time of ART stays constant w.r.t. t for given β and α. 5.5 Obtaining Population Upper Bound tm So far we have assumed the knowledge of an upper bound tm on tag population size t. In some applications, tm is read￾ily available. For example, the number of TVs in a TV ware￾house can be reasonably estimated by the warehouse size and minimum TV size. However, this may not be available for some applications where the tag population size changes in large magnitude. We next present a fast scheme to ob￾tain tm based on Flajolet and Martin’s probabilistic count￾ing algorithm used in databases [5]. Before running ART, the reader uses this scheme to obtain tm. In this scheme, the reader keeps issuing single-slot frames, where the persis￾tence probability p follows a geometric distribution starting from p =1(i.e., p = 1 2i−1 in the i-th frame), until the reader gets an empty slot. Suppose the empty slot occurred in the i-th frame, then tm = 1.2897 × 2i−2 is an upper bound on t [5, 14]. 5.6 ART with Multiple Readers We next discuss how to obtain tm and t ˜ using multiple readers whose covered regions may overlap. To obtain tm using multiple readers, we can let each reader obtain the tm value on its own and then sum them up as the final overall tm because of two reasons. First, our requirement on tm is only a rough upper bound estimate. Second, deployment of multiple readers in practice often requires site surveys to en￾sure minimal overlapping between readers. To use multiple readers to obtain t ˜ more precisely, we adapt the approach 373

0.9175 420 -B=1% B=5% 10 -B=10% 418 0.917 B=25 10 416 .414 0.9165 0 412 0.910 410 10 10 10 104 10 x10 x10 Figure 8:Pop vs.tm Figure 9:q1 vs.tm Figure 10:(fop+3)xnopvs.tm proposed by Kodialam et al.in [8],which uses a central con- 6. PERFORMANCE EVALUATION troller for all readers.ART parameters B,a,tm,fop,Pop,and We numerically evaluated in Matlab our ART scheme as nop have the same value across all readers.When a reader well as four prior RFID estimation schemes:UPE 7.EZB transmits seed Ri in its i-th frame,it does not generate Ri on 8,FNEB 6],and MLE 10.We did not evaluate the other its own,rather it uses the i-th seed Ri issued by the central estimation scheme LoF [14]because it is non-compliant with controller.That is,each reader generates the same sequence C1G2.In terms of implementation complexity,the number of nop seeds.In the i-th frames from different readers,be- of lines of code required to implement ART were almost the cause all readers use the same seed Ri,the slot number that same as all four prior protocols.To ensure compliance with a given tag chooses is the same (i.e.,h(f,Ri,ID))in the the C1G2 standard,in all our simulations,each tag picks up frame of each reader covering this tag.Once a reader has exactly one slot at the start of frame as soon as the reader completed its frame,it sends the frame to the central con- broadcasts the frame size. troller.The controller applies the logical OR on all the i-th Next,we first conduct a side-by-side comparison on esti- frames from all readers,and gets the same i-th frame as if mation time between ART and the four prior schemes.Then. using a single reader.ART uses the nop frames computed by we conduct experiments to show that ART indeed achieves logical OR to estimate the population size. the required reliability 5.7 ART-Pseudocode 6.1 Estimation Time Algorithm 1 shows the pseudocode of ART The results in Figures 11,12,and 13 show that the esti- mation time of ART is significantly smaller than all prior Algorithm 1:EstimateRFIDTagPopulation(a,B,nr) schemes.Note that in Figures 12 and 13,the plots for FNEB Input:(1)Required reliability a are out of the range of the vertical axes,and the plots of UPE (2)Required confidence interval B and EZB are almost overlapping. (3)Number of readers nr Output:Estimated tag population size f We make three main observations from Figures 11 (a) 1tm :=GetMaximumTags(nr) (b),and (c),which show the estimation time needed by each 2 Solve (19)and (31)to get fop and pop. scheme with population sizes of up to one million tags for 3 Evaluate k using (28). different configurations of a and confidence interval B.First. 4 Evaluate nop by using a,B,k,fop:Pop:and tm in (29). s for i:=1 to nop do we observe that ART is faster than all four prior schemes in Provide all readers with fop/pop and a random seed Ri. all these configurations.For a=99.9%and B=0.1%,ART 7 Run Aloha on readers and gather all readers'frames. is 7 times faster than the fastest prior estimation schemes Perform slot wise OR on all frames to obtain one frame. which are UPE 7 and EZB 8.For a =99%and B=1% Obtain X1(i),the average run size of 1s in this frame. ART is 1.96 times faster than UPE and EZB.For a=95% 10文avg←∑2文1()/mop and B=5%.ART is 1.68 times faster than UPE and EZB 11 Use E[X]:=and solve (14)to obtain an estimate i of t. Second.we observe that ART,UPE.EZB,and MLE per- 12 return t form estimation in constant time,which attributes to the use 13 GetMaximumTags(n,) 14 f:=1 of persistence probabilities.Third,we observe that FNEB 16 for j:=1 to nr do whose estimator is the size of the first run of 0s,is the slow- 16 i=1 est.This concurs with our analytical analysis in Figure 4. 17 P=1 where we show that FNEB has the largest variance.The 18 repeat Provide reader j with f/p and a random seed Ri larger the variance of an estimator,the more the rounds 0 Run Aloha on reader j and get the response. of execution needed to achieve the required reliability,and 21 if slot is not empty then therefore the longer the estimation time. p4+1=p4/2 28 i:=i+1 We make three main observations from Figures 12(a), 24 until slot is empty (b),and (c),which show the estimation time for 5000 tags 26 tm,=1.2897×2-2 required by each scheme with the required reliability a vary- 26 tm=∑r1tmd ing from 90%to 99.9%for different configurations of confi- 27 return tm dence interval B.First,we observe that ART is faster than all four prior estimation schemes in all these configurations Second,the difference between the estimation time of ART 374

0 2 4 6 8 10 x 105 10−4 10−3 10−2 10−1 100 t m pop Figure 8: pop vs. tm 2 4 6 8 10 x 105 0.916 0.9165 0.917 0.9175 t m q1 β = 1% β = 5% β = 10% β = 25% Figure 9: q1 vs. tm 102 103 104 105 106 410 412 414 416 418 420 t m (fop+ 3) × nop Figure 10: (fop+3)×nopvs.tm proposed by Kodialam et al. in [8], which uses a central con￾troller for all readers. ART parameters β, α, tm, fop, pop, and nop have the same value across all readers. When a reader transmits seed Ri in its i-th frame, it does not generate Ri on its own, rather it uses the i-th seed Ri issued by the central controller. That is, each reader generates the same sequence of nop seeds. In the i-th frames from different readers, be￾cause all readers use the same seed Ri, the slot number that a given tag chooses is the same (i.e., h(f,Ri,ID)) in the frame of each reader covering this tag. Once a reader has completed its frame, it sends the frame to the central con￾troller. The controller applies the logical OR on all the i-th frames from all readers, and gets the same i-th frame as if using a single reader. ART uses the nop frames computed by logical OR to estimate the population size. 5.7 ART - Pseudocode Algorithm 1 shows the pseudocode of ART. Algorithm 1: EstimateRFIDTagPopulation(α, β, nr) Input: (1) Required reliability α (2) Required confidence interval β (3) Number of readers nr Output: Estimated tag population size t ˜ 1 tm := GetMaximumTags(nr) 2 Solve (19) and (31) to get fop and pop. 3 Evaluate k using (28). 4 Evaluate nop by using α, β, k, fop, pop, and tm in (29). 5 for i := 1 to nop do 6 Provide all readers with fop/pop and a random seed Ri. 7 Run Aloha on readers and gather all readers’ frames. 8 Perform slot wise OR on all frames to obtain one frame. 9 Obtain X˜1(i), the average run size of 1s in this frame. 10 X˜avg ← nop i=1 X˜1(i)/nop 11 Use E[X1] := X˜avg and solve (14) to obtain an estimate t ˜ of t. 12 return t ˜ 13 GetMaximumTags(nr) 14 f := 1 15 for j := 1 to nr do 16 i := 1 17 pi := 1 18 repeat 19 Provide reader j with f/pi and a random seed Ri. 20 Run Aloha on reader j and get the response. 21 if slot is not empty then 22 pi+1 := pi/2 23 i := i + 1 24 until slot is empty 25 tm,j := 1.2897 × 2i−2 26 tm := nr j=1 tm,j 27 return tm 6. PERFORMANCE EVALUATION We numerically evaluated in Matlab our ART scheme as well as four prior RFID estimation schemes: UPE [7], EZB [8], FNEB [6], and MLE [10]. We did not evaluate the other estimation scheme LoF [14] because it is non-compliant with C1G2. In terms of implementation complexity, the number of lines of code required to implement ART were almost the same as all four prior protocols. To ensure compliance with the C1G2 standard, in all our simulations, each tag picks up exactly one slot at the start of frame as soon as the reader broadcasts the frame size. Next, we first conduct a side-by-side comparison on esti￾mation time between ART and the four prior schemes. Then, we conduct experiments to show that ART indeed achieves the required reliability. 6.1 Estimation Time The results in Figures 11, 12, and 13 show that the esti￾mation time of ART is significantly smaller than all prior schemes. Note that in Figures 12 and 13, the plots for FNEB are out of the range of the vertical axes, and the plots of UPE and EZB are almost overlapping. We make three main observations from Figures 11 (a), (b), and (c), which show the estimation time needed by each scheme with population sizes of up to one million tags for different configurations of α and confidence interval β. First, we observe that ART is faster than all four prior schemes in all these configurations. For α = 99.9% and β = 0.1%, ART is 7 times faster than the fastest prior estimation schemes, which are UPE [7] and EZB [8]. For α = 99% and β = 1%, ART is 1.96 times faster than UPE and EZB. For α = 95% and β = 5%, ART is 1.68 times faster than UPE and EZB. Second, we observe that ART, UPE, EZB, and MLE per￾form estimation in constant time, which attributes to the use of persistence probabilities. Third, we observe that FNEB, whose estimator is the size of the first run of 0s, is the slow￾est. This concurs with our analytical analysis in Figure 4, where we show that FNEB has the largest variance. The larger the variance of an estimator, the more the rounds of execution needed to achieve the required reliability, and therefore the longer the estimation time. We make three main observations from Figures 12 (a), (b), and (c), which show the estimation time for 5000 tags required by each scheme with the required reliability α vary￾ing from 90% to 99.9% for different configurations of confi- dence interval β. First, we observe that ART is faster than all four prior estimation schemes in all these configurations. Second, the difference between the estimation time of ART 374