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.. 367of 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