VII.SIMULATION RESULT B.Total Number of Bits Transmitted In this section,we evaluate the performance of MLEA, The second simulation evaluates the energy cost of the algorithms.As mentioned before,one bit is enough to separate ASEA and EMLEA by simulations.We compare the proposed algorithms with the state-of-the-art algorithms in the related empty/non-empty slot.Hence,the response of MLEA,ASEA, work.They are the Unified Probabilistic Estimator (UPE) EMLEA and EZB is one bit long.A response in UPE-M is 10 [3]and the Enhanced Zero-Based (ZEB)estimator [4].The bits long [3].We compare the total number of bits transmitted original UPE,denoted as UPE-O,is very energy-inefficient by all tags before each algorithm terminates.Fig.5 show because its contention probability begins from 100%and thus the simulation results with respect to N when a =95% all tags will respond.We modify it (denoted as UPE-M)to and B =3%,6%and 9%.For example,when a =95%, begin from a small initial contention probability We B=3%,and N =20,000,the ratio between the number run each simulation 100 times and average the outcomes. of bits transmitted by UPE-M (EZB)and that by our best In the initialization phase of our protocols,let Nmaz estimator EMLEA is 32.8(53.6).It should be noted that the number of bits transmitted is not an accurate measurement of 1.000.000 and C=2.The frame size in ASEA and EMLEA is 10 slots.The parameters for UPE and ZEB are picked based the energy cost because it ignores the energy spent to power up the radio and synchronize with the reader.However,combining on the original papers whenever possible.All algorithms except the number of bits and the number of transmissions (in the for UPE need only to identify empty and non-empty slots.UPE has to identify empty,singleton and collision slots.To set a previous subsection)still gives a good idea on how energy- efficient each algorithm is. non-empty slot apart from an empty slot,a tag only needs to respond a short bit string to make the channel busy.However, C.Estimation Time to set a singleton slot apart from a collision slot,many more bits (10 used by UPE)are necessary [19].For example,CRC The third simulation compares the time it takes for each algorithm to complete the estimation of N.Based on the may be used to detect collision. specification of the Philips I-Code system [16],after the The energy cost of an algorithm depends on (1)the num- ber of responses that all tags transmit before the algorithm required waiting times (e.g.,gap between transmissions)are included,it can be calculated that a reader needs 0.4ms to terminates and(2)the size of each response.We use 'S'to detect an empty slot,0.8ms to detect a collision or a singleton mean that the response is a short bit string(in the empty/non- slot,and 1ms to broadcast a polling request.Hence,MLEA, empty case),and 'L'to mean a long bit string (in the ASEA,EMLEA and EZB requires a slot length of 0.4ms, empty/singleton/collision case). while UPE-M requires a slot length of 0.8ms.Recall that We do not include the simulation results for LoF [5]because its energy cost is much higher than others.Its number of the contention probability takes the form ofwhere is responses transmitted by the tags is kN,where k is the number a known constant.Thus the reader transmits N instead of the of frames used in the estimation process. actual probability value in the polling requests.If we assume Nmax is no more than a million,then 20 bits for Ni are sufficient.MLEA has a fixed frame size of one slot.ASEA and A.Number of Responses EMLEA have a fixed frame size of 10 slots.EZB and UPE- The first simulation studies the number of responses in each M also have pre-determined frame sizes.Let a =95%and algorithm with respect to N,a and B.Table I shows the 3=5%.Fig.(6)shows the estimation times of the algorithms number of responses with respect to N when a =90%and with respect to the number of tags in the deployment.The B=5%.The proposed algorithms require fewer responses times grow very slowly as the number of tags increase,which than UPE and EZB.As predicted,UPE-O is energy-inefficient; suggests the algorithms all scale well.UPE-M takes the least UPE-M works much better.The best algorithm is EMLEA amount of time,only 1.1 seconds,to estimate 20,000 tags, whose number of responses is about one third of what UPE- while the other algorithms take between 3.4 to 7.7 seconds. EMLEA takes 5.3 seconds.Even though the new algorithms M requires and one fiftieth of what EZB when N is 20.000. Moveover,each response in UPE is much longer. take longer to complete,their estimation time is still small.We Tables II-III show similar comparison for different a values believe the extra time needed can be well justified for the large energy saving. Tables IV-VI show the comparison under different B values when a =99%.We omit the results for UPE-O(which are VIII.CONCLUSIONS much worse than the numbers of UPE-M)to keep the table width within a column.In all cases,the number of responses This paper proposes three new probabilistic algorithms for increases when a increases or B decreases,and except for EZB. estimating the number of RFID tags in a region.We believe the number does not vary much with respect to N,meaning the algorithms are the first of its kind that targets at prolonging that all algorithms except for EZB achieve good scalability the lifetime of the active RFIDs.Their energy cost is far less The ratio between the numbers for different algorithms appear than the state-of-the-art algorithms in the related work. to be quite stable under different parameter settings REFERENCES [1]R.Hollinger and J.Davis, "National Retail Security Survey," 2The fisher information [18]is a way of measuring the amount of informa- hup://diogenesllc.com/NRSS_2001.pdf.2001 tion that an observable random variable carries about an unknown parameter [2]R.Want,"An Introduction to RFID Technology,"Proc.IEEE PerCom, 6 upon which the likelihood function of 6,L()=f(x;)depends. Jan2006.VII. SIMULATION RESULT In this section, we evaluate the performance of MLEA, ASEA and EMLEA by simulations. We compare the proposed algorithms with the state-of-the-art algorithms in the related work. They are the Unified Probabilistic Estimator (UPE) [3] and the Enhanced Zero-Based (ZEB) estimator [4]. The original UPE, denoted as UPE-O, is very energy-inefficient because its contention probability begins from 100% and thus all tags will respond. We modify it (denoted as UPE-M) to begin from a small initial contention probability 1 Nmax . We run each simulation 100 times and average the outcomes. In the initialization phase of our protocols, let Nmax = 1, 000, 000 and C = 2. The frame size in ASEA and EMLEA is 10 slots. The parameters for UPE and ZEB are picked based on the original papers whenever possible. All algorithms except for UPE need only to identify empty and non-empty slots. UPE has to identify empty, singleton and collision slots. To set a non-empty slot apart from an empty slot, a tag only needs to respond a short bit string to make the channel busy. However, to set a singleton slot apart from a collision slot, many more bits (10 used by UPE) are necessary [19]. For example, CRC may be used to detect collision. The energy cost of an algorithm depends on (1) the num￾ber of responses that all tags transmit before the algorithm terminates and (2) the size of each response. We use ‘S’ to mean that the response is a short bit string (in the empty/non￾empty case), and ‘L’ to mean a long bit string (in the empty/singleton/collision case). We do not include the simulation results for LoF [5] because its energy cost is much higher than others. Its number of responses transmitted by the tags is kN, where k is the number of frames used in the estimation process. A. Number of Responses The first simulation studies the number of responses in each algorithm with respect to N, α and β. Table I shows the number of responses with respect to N when α = 90% and β = 5%. The proposed algorithms require fewer responses than UPE and EZB. As predicted, UPE-O is energy-inefficient; UPE-M works much better. The best algorithm is EMLEA, whose number of responses is about one third of what UPE￾M requires and one fiftieth of what EZB when N is 20,000. Moveover, each response in UPE is much longer. Tables II-III show similar comparison for different α values. Tables IV-VI show the comparison under different β values when α = 99%. We omit the results for UPE-O (which are much worse than the numbers of UPE-M) to keep the table width within a column. In all cases, the number of responses increases when α increases or β decreases, and except for EZB, the number does not vary much with respect to N, meaning that all algorithms except for EZB achieve good scalability. The ratio between the numbers for different algorithms appear to be quite stable under different parameter settings. 2The fisher information [18] is a way of measuring the amount of informa￾tion that an observable random variable x carries about an unknown parameter θ upon which the likelihood function of θ, L(θ) = f(x; θ), depends. B. Total Number of Bits Transmitted The second simulation evaluates the energy cost of the algorithms. As mentioned before, one bit is enough to separate empty/non-empty slot. Hence, the response of MLEA, ASEA, EMLEA and EZB is one bit long. A response in UPE-M is 10 bits long [3]. We compare the total number of bits transmitted by all tags before each algorithm terminates. Fig. 5 show the simulation results with respect to N when α = 95% and β = 3%, 6% and 9%. For example, when α = 95%, β = 3%, and N = 20, 000, the ratio between the number of bits transmitted by UPE-M (EZB) and that by our best estimator EMLEA is 32.8 (53.6). It should be noted that the number of bits transmitted is not an accurate measurement of the energy cost because it ignores the energy spent to power up the radio and synchronize with the reader. However, combining the number of bits and the number of transmissions (in the previous subsection) still gives a good idea on how energy￾efficient each algorithm is. C. Estimation Time The third simulation compares the time it takes for each algorithm to complete the estimation of N. Based on the specification of the Philips I-Code system [16], after the required waiting times (e.g., gap between transmissions) are included, it can be calculated that a reader needs 0.4ms to detect an empty slot, 0.8ms to detect a collision or a singleton slot, and 1ms to broadcast a polling request. Hence, MLEA, ASEA, EMLEA and EZB requires a slot length of 0.4ms, while UPE-M requires a slot length of 0.8ms. Recall that the contention probability takes the form of ω Nˆi , where ω is a known constant. Thus the reader transmits Nˆ i instead of the actual probability value in the polling requests. If we assume Nmax is no more than a million, then 20 bits for Nˆ i are sufficient. MLEA has a fixed frame size of one slot. ASEA and EMLEA have a fixed frame size of 10 slots. EZB and UPE￾M also have pre-determined frame sizes. Let α = 95% and β = 5%. Fig. (6) shows the estimation times of the algorithms with respect to the number of tags in the deployment. The times grow very slowly as the number of tags increase, which suggests the algorithms all scale well. UPE-M takes the least amount of time, only 1.1 seconds, to estimate 20,000 tags, while the other algorithms take between 3.4 to 7.7 seconds. EMLEA takes 5.3 seconds. Even though the new algorithms take longer to complete, their estimation time is still small. We believe the extra time needed can be well justified for the large energy saving. VIII. CONCLUSIONS This paper proposes three new probabilistic algorithms for estimating the number of RFID tags in a region. We believe the algorithms are the first of its kind that targets at prolonging the lifetime of the active RFIDs. Their energy cost is far less than the state-of-the-art algorithms in the related work. REFERENCES [1] R. Hollinger and J. Davis, “National Retail Security Survey,” http://diogenesllc.com/NRSS 2001.pdf, 2001. [2] R. Want, “An Introduction to RFID Technology,” Proc. IEEE PerCom, Jan 2006