approach,the framed-slotted ALOHA (FSA)protocol,which B.System Model is an extension of the pure ALOHA protocol [21],is widely used in RFID standards.Built on that,adaptive FSA protocols, The MAC protocol for our RFID system is based on the where frame size is adaptively adjusted,are explored in [15], adaptive framed-slotted ALOHA model.To read a set of tags,a [22-[241. reader first powers up and transmits continuous wave (CW)to Recent research work [12],[13],[17],[25]is the closest to energize tags.Each tag waits for the reader's command before this paper.A probabilistic analytical model for anonymously replying.This is known as the Reader Talks First mode. estimating tag population is first proposed in [12].The main The communication between the reader and tags is composed idea is to use the framed-slotted ALOHA protocol and monitor of multiple frames.Each frame is partitioned into slots.Here, the number of empty and collision slots to count tags.However, we refer to an individual frame as a round.The reader will first the drawbacks of the estimators in [12]are that all the tags broadcast a begin round command containing the frame size f must be readable by the reader in a single probe and that the in the forthcoming round,and a random seed R.The frame size reader must know approximately the magnitude of the number is the number of slots available for tags to choose in a round of tags to be estimated.Due to these constraints,an Enhanced Each tag picks a slot,and this slot determines when a tag will Zero-Based (EZB)estimator is presented in [13].By tuning reply.An RFID tag uses a hash function h(),f,R,and its ID the parameters for multiple iterations,the number of tags can to pick a slot in the current round,ie.,h(f,R,id)[0,f-1]. be estimated with high accuracy,even when the tag population We assume that the outputs of the hash function have a uniform varies a lot.The key improvement in our work over [12]and random distribution such that the tag has the equal probability [13]is that our scheme does not scan the entire frame,which to select any slot within the round given a seed and ID. drastically reduces time cost.Finally,another novel estimator Each RFID tag has a slot counter which will decrease each for the same problem is proposed in [25]with more focus on time the reader indicates that the current slot has ended.The tag the multiple-reader scenario.However,the scheme requires a will only reply when its slot counter reaches zero.When all the special geometric distribution hash function,which might not slots in the frame have been accounted for,the reader sends an be available in the off-the-shelf RFID systems. end round command to terminate this round.We assume that the reader can issue an end round command to terminate a III.PROBLEM DEFINITION AND SYSTEM MODEL round at any time without waiting for the frame to end.The A.Problem Definition procedure is illustrated in Fig.1.We call this the original send- and-reply protocol. TABLE I NOTATIONS Begin round End slot End round command ommand Symbols Descriptions command Confidence interval Reader <f,R> Error probability t Number of distinct tags Tag#1 #1 Upper bound of the number of tags Tag#2 #2 t Estimation of the number of tags Random variable for the number of continuous empty Tag#3 #3 slots before the first non-empty slot in a frame Frame size (the number of slots in a frame) R Random seed Tag#t e Load factor t/f Empty Slot 无 Number of waiting slots Collision Slot m Number of rounds (frames) -round a】 Hash function TO Theoretical time cost (in number of slots)in a round Fig.1.Collection sequence of passive RFID systems using the adaptive FSA m Number of sets of tags Since every RFID tag chooses its own slot individually,there Given an RFID reader and a set of tags,we want to quickly will be instances where no tag picks a particular slot.We term and accurately estimate the number of distinct RFID tags in this as an empty slot.A slot that has only been chosen by the set without identifying each tag individually.Our algorithms one tag is known as a singleton slot.A slot that is chosen by allow a user to specify his desired accuracy using two variables, more than one tag is called a collision slot.We refer to both a confidence interval e and an error probability 6.Lower values singleton slot and collision slot as non-empty slot in this paper. of e and o result in a more accurate estimation.Our algorithms After collecting all replies,the reader can generate a bitstring. return an estimation t of the actual number of tags t,such such as that Pr[lf-t<et]>1-6.For example,if the set has 5000 RFID tags,and given e=5%and 6=1%,the desired {·1110|11110|11·}, estimator should output the number within [4750,5250]with probability greater than 99%.Table I summarizes the notations where 0 indicates an empty slot,and 1 represents a non-empty used. slot.approach, the framed-slotted ALOHA (FSA) protocol, which is an extension of the pure ALOHA protocol [21], is widely used in RFID standards. Built on that, adaptive FSA protocols, where frame size is adaptively adjusted, are explored in [15], [22]–[24]. Recent research work [12], [13], [17], [25] is the closest to this paper. A probabilistic analytical model for anonymously estimating tag population is first proposed in [12]. The main idea is to use the framed-slotted ALOHA protocol and monitor the number of empty and collision slots to count tags. However, the drawbacks of the estimators in [12] are that all the tags must be readable by the reader in a single probe and that the reader must know approximately the magnitude of the number of tags to be estimated. Due to these constraints, an Enhanced Zero-Based (EZB) estimator is presented in [13]. By tuning the parameters for multiple iterations, the number of tags can be estimated with high accuracy, even when the tag population varies a lot. The key improvement in our work over [12] and [13] is that our scheme does not scan the entire frame, which drastically reduces time cost. Finally, another novel estimator for the same problem is proposed in [25] with more focus on the multiple-reader scenario. However, the scheme requires a special geometric distribution hash function, which might not be available in the off-the-shelf RFID systems. III. PROBLEM DEFINITION AND SYSTEM MODEL A. Problem Definition TABLE I NOTATIONS Symbols Descriptions ǫ Confidence interval δ Error probability t Number of distinct tags tmax Upper bound of the number of tags t˜ Estimation of the number of tags X Random variable for the number of continuous empty slots before the first non-empty slot in a frame f Frame size (the number of slots in a frame) R Random seed ρ Load factor t/f k Number of waiting slots n Number of rounds (frames) h(·) Hash function T(·) Theoretical time cost (in number of slots) in a round m Number of sets of tags Given an RFID reader and a set of tags, we want to quickly and accurately estimate the number of distinct RFID tags in the set without identifying each tag individually. Our algorithms allow a user to specify his desired accuracy using two variables, a confidence interval ǫ and an error probability δ. Lower values of ǫ and δ result in a more accurate estimation. Our algorithms return an estimation t˜ of the actual number of tags t, such that P r[|t˜ − t| ≤ ǫt] ≥ 1 − δ. For example, if the set has 5000 RFID tags, and given ǫ = 5% and δ = 1%, the desired estimator should output the number within [4750, 5250] with probability greater than 99%. Table I summarizes the notations used. B. System Model The MAC protocol for our RFID system is based on the adaptive framed-slotted ALOHA model. To read a set of tags, a reader first powers up and transmits continuous wave (CW) to energize tags. Each tag waits for the reader’s command before replying. This is known as the Reader Talks First mode. The communication between the reader and tags is composed of multiple frames. Each frame is partitioned into slots. Here, we refer to an individual frame as a round. The reader will first broadcast a begin round command containing the frame size f in the forthcoming round, and a random seed R. The frame size is the number of slots available for tags to choose in a round. Each tag picks a slot, and this slot determines when a tag will reply. An RFID tag uses a hash function h(·), f, R, and its ID to pick a slot in the current round, i.e., h(f, R, id) → [0, f −1]. We assume that the outputs of the hash function have a uniform random distribution such that the tag has the equal probability to select any slot within the round given a seed and ID. Each RFID tag has a slot counter which will decrease each time the reader indicates that the current slot has ended. The tag will only reply when its slot counter reaches zero. When all the slots in the frame have been accounted for, the reader sends an end round command to terminate this round. We assume that the reader can issue an end round command to terminate a round at any time without waiting for the frame to end. The procedure is illustrated in Fig. 1. We call this the original send￾and-reply protocol. #1 #2 #3 #t Begin round command End slot command End round command Reader ... <f, R> Tag#1 Tag#2 Tag#3 Tag#t Singleton Slot Collision Slot Empty Slot ... st 1 round ... Fig. 1. Collection sequence of passive RFID systems using the adaptive FSA Since every RFID tag chooses its own slot individually, there will be instances where no tag picks a particular slot. We term this as an empty slot. A slot that has only been chosen by one tag is known as a singleton slot. A slot that is chosen by more than one tag is called a collision slot. We refer to both singleton slot and collision slot as non-empty slot in this paper. After collecting all replies, the reader can generate a bitstring, such as { · · · | 1 | 0 | 1 | 1 | 0 | 1 | · · · }, where 0 indicates an empty slot, and 1 represents a non-empty slot