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