reader is relatively a less concern because the reader's battery respond in those slots.Using the probabilistic counting meth- can be easily replaced or it may be powered by an external ods,the reader estimates the number of tags based on the source.To exploit this asymmetry,our new algorithms follows number of empty slots or the number of collision slots.Their a common framework that trades more energy cost at the reader best estimator is called the Unified Probabilistic Estimator for less cost at the tags.The reader will continuously refine and (UPE).A follow-up work by the same authors proposes the broadcast a control parameter called contention probability, Enhanced Zero-Based Estimator (EZB)[4],which makes its which optimizes the amount of information the reader can estimation based on the number of empty slots.The Lottery- extract from the transmissions by the tags.This in turn reduces Frame scheme (LoF)[5]by Qian et al.employs a geometric the number of transmissions by the tags that are necessary to distribution-based scheme to determine which slot in a time achieve a certain estimation accuracy. frame each tag will respond.It significantly reduces the esti- Second,we investigate statistical methods,including the mation time.However,every tag must respond during each of maximum likelihood estimation (MLE)and the average sum the time frames(their number ranges from tens to thousands), estimation (ASE)that are different from the probabilistic resulting in large energy cost when active tags use their own counting methods [8]used by [3].[4].Our estimation al- power to transmit.Also related is a novel security protocol gorithms optimize their performance by iteratively applying proposed by Tan et al.to monitor the missing RFID tags in MLE or ASE with continuously refined parameters.The new the presence of dishonest RFID readers [15]. algorithms not only require fewer transmissions by the tags None of the above estimators are designed with energy but also minimize the size of each transmission.The number conservation in mind.In the following,we will present our of transmissions made by the tags in our best algorithm is less energy efficient estimators. than one third of the number in the state-of-the-art algorithms. III.PROBLEM DEFINITION AND SYSTEM MODEL In terms of the total number of bits transmitted by the tags,it is more than an order of magnitude smaller. A.RFID Estimation Problem Third,we formally analyze the confidence intervals of the The problem is to design efficient algorithms to estimate the estimations made by the new algorithms and establish the number of RFID tags in a deployment area without actually termination conditions for any given accuracy requirement.We reading the ID of each tag.Let N be the actual number of tags perform extensive simulations to demonstrate that the measured and N be the estimate.The estimation accuracy is specified results match well with the analytical results and that the new by a confidence interval with two parameters:a probability algorithms perform far better in terms of energy saving than value a and an error bound B,both in the range of(0,1).The the best existing algorithms. requirement is that the probability forto fall in the interval The rest of the paper is organized as follows.Section 2 [1-B,1+B]is at least a,i.e., discusses the related work.Section 3 defines the problem to be solved and the system model.Sections 4-6 propose three new Prob(1-B)N≤N≤(1+3)N)≥a. solutions for the RFID estimation problem.Section 7 evaluates Our goal is to achieve the above estimation accuracy with the new algorithms through simulations.Section 8 draws the minimum energy overhead to the active tags. conclusion. B.System Model II.RELATED WORK The type of active RFID systems considered in this paper is Most existing work focuses on how to efficiently read the applicable to a large deployment area that are hundreds of feet IDs of the RFID tags.When queried by the RFID reader,the or more across.Passive tags are beyond the scope of this paper. tags will respond with their IDs.Since the communication If they were used,one would have to take the reader and move environment is wireless,inevitably collisions will happen when around the whole area,collecting tag information once every multiple tags choose the same slot.Collision arbitration pro- few feet.Active tags allow a RFID reader to collect information tocols mainly fall into two categories:framed ALOHA-based from one location.The tagged goods (such as apparel)may approach [9],[10],[11],[7]and tree-based approach [12],[13]. stack in piles,and there may be obstacles,such as racks filled [14],[6].In the former approach,the polling request carries with merchandize,between a tag and the reader.We expect the the frame length,and each tag individually chooses a slot in active tags are designed to transmit with significant power that the frame to transmit its ID.The process repeats until all the is high enough to ensure reliable information delivery in such tags successfully transmit their IDs to the reader.In the later a demanding environment.Hence,the energy cost due to the approach,the reader first sends out an ID prefix string.The tags'transmissions is the main concern in our algorithm design; tags whose IDs match the string will respond.If a collision it increases at least in the square of the maximum distance to be happens,the reader will append a'0'or'1'to the prefix string covered by the RFID system.Energy consumption that powers and send out the new string.This process repeats until only the tag's circuit for computing and receiving information is not one tag responds.Essentially the approach traverses a binary affected by long distance and obstacles.The energy consumed tree with the IDs of the tags being the leaf nodes. by the RFID reader is of less concern.We assume the reader Instead of identifying individual RFID tags,Kodialam and transmits at sufficiently high power. Nandagopal [3]study the problem of estimating the cardinality We use the following communication protocol between the of a tag set.In their approach,information from tags are reader and the tags.The reader first synchronizes the clocks collected by a RFID reader in a series of time frames.Each of the tags and then performs a sequence of pollings.In each frame consists of a number of slots,and tags probabilistically polling,the reader sends out a request,which is followed by areader is relatively a less concern because the reader’s battery can be easily replaced or it may be powered by an external source. To exploit this asymmetry, our new algorithms follows a common framework that trades more energy cost at the reader for less cost at the tags. The reader will continuously refine and broadcast a control parameter called contention probability, which optimizes the amount of information the reader can extract from the transmissions by the tags. This in turn reduces the number of transmissions by the tags that are necessary to achieve a certain estimation accuracy. Second, we investigate statistical methods, including the maximum likelihood estimation (MLE) and the average sum estimation (ASE) that are different from the probabilistic counting methods [8] used by [3], [4]. Our estimation al￾gorithms optimize their performance by iteratively applying MLE or ASE with continuously refined parameters. The new algorithms not only require fewer transmissions by the tags but also minimize the size of each transmission. The number of transmissions made by the tags in our best algorithm is less than one third of the number in the state-of-the-art algorithms. In terms of the total number of bits transmitted by the tags, it is more than an order of magnitude smaller. Third, we formally analyze the confidence intervals of the estimations made by the new algorithms and establish the termination conditions for any given accuracy requirement. We perform extensive simulations to demonstrate that the measured results match well with the analytical results and that the new algorithms perform far better in terms of energy saving than the best existing algorithms. The rest of the paper is organized as follows. Section 2 discusses the related work. Section 3 defines the problem to be solved and the system model. Sections 4-6 propose three new solutions for the RFID estimation problem. Section 7 evaluates the new algorithms through simulations. Section 8 draws the conclusion. II. RELATED WORK Most existing work focuses on how to efficiently read the IDs of the RFID tags. When queried by the RFID reader, the tags will respond with their IDs. Since the communication environment is wireless, inevitably collisions will happen when multiple tags choose the same slot. Collision arbitration pro￾tocols mainly fall into two categories: framed ALOHA-based approach [9], [10], [11], [7] and tree-based approach [12], [13], [14], [6]. In the former approach, the polling request carries the frame length, and each tag individually chooses a slot in the frame to transmit its ID. The process repeats until all the tags successfully transmit their IDs to the reader. In the later approach, the reader first sends out an ID prefix string. The tags whose IDs match the string will respond. If a collision happens, the reader will append a ‘0’ or ‘1’ to the prefix string and send out the new string. This process repeats until only one tag responds. Essentially the approach traverses a binary tree with the IDs of the tags being the leaf nodes. Instead of identifying individual RFID tags, Kodialam and Nandagopal [3] study the problem of estimating the cardinality of a tag set. In their approach, information from tags are collected by a RFID reader in a series of time frames. Each frame consists of a number of slots, and tags probabilistically respond in those slots. Using the probabilistic counting meth￾ods, the reader estimates the number of tags based on the number of empty slots or the number of collision slots. Their best estimator is called the Unified Probabilistic Estimator (UPE). A follow-up work by the same authors proposes the Enhanced Zero-Based Estimator (EZB) [4], which makes its estimation based on the number of empty slots. The Lottery￾Frame scheme (LoF) [5] by Qian et al. employs a geometric distribution-based scheme to determine which slot in a time frame each tag will respond. It significantly reduces the esti￾mation time. However, every tag must respond during each of the time frames (their number ranges from tens to thousands), resulting in large energy cost when active tags use their own power to transmit. Also related is a novel security protocol proposed by Tan et al. to monitor the missing RFID tags in the presence of dishonest RFID readers [15]. None of the above estimators are designed with energy conservation in mind. In the following, we will present our energy efficient estimators. III. PROBLEM DEFINITION AND SYSTEM MODEL A. RFID Estimation Problem The problem is to design efficient algorithms to estimate the number of RFID tags in a deployment area without actually reading the ID of each tag. Let N be the actual number of tags and Nˆ be the estimate. The estimation accuracy is specified by a confidence interval with two parameters: a probability value α and an error bound β, both in the range of (0, 1). The requirement is that the probability for N Nˆ to fall in the interval [1 − β, 1 + β] is at least α, i.e., P rob((1 − β)Nˆ ≤ N ≤ (1 + β)Nˆ) ≥ α. Our goal is to achieve the above estimation accuracy with minimum energy overhead to the active tags. B. System Model The type of active RFID systems considered in this paper is applicable to a large deployment area that are hundreds of feet or more across. Passive tags are beyond the scope of this paper. If they were used, one would have to take the reader and move around the whole area, collecting tag information once every few feet. Active tags allow a RFID reader to collect information from one location. The tagged goods (such as apparel) may stack in piles, and there may be obstacles, such as racks filled with merchandize, between a tag and the reader. We expect the active tags are designed to transmit with significant power that is high enough to ensure reliable information delivery in such a demanding environment. Hence, the energy cost due to the tags’ transmissions is the main concern in our algorithm design; it increases at least in the square of the maximum distance to be covered by the RFID system. Energy consumption that powers the tag’s circuit for computing and receiving information is not affected by long distance and obstacles. The energy consumed by the RFID reader is of less concern. We assume the reader transmits at sufficiently high power. We use the following communication protocol between the reader and the tags. The reader first synchronizes the clocks of the tags and then performs a sequence of pollings. In each polling, the reader sends out a request, which is followed by a