IV.INTUITION A.Basic Algorithm The previous research [12],[13],[17]takes advantage of Again,our algorithm is based on the idea of making obser- the framed-slotted ALOHA protocol to estimate the number vation on the first non-empty slot.However,if the number of of tags.The basic idea is based on the probability model we tags t is small,the position of the first reply may be located have described previously.The reader scans all the slots and at the end of the frame.Apparently,it is not efficient to use records the status of each slot:empty,singleton,or collision. the original send-and-reply protocol described in Section IIl. By examining the number of empty slots,collision slots,the In that protocol,a reader broadcasts f and R at the beginning reader can then estimate the number of tags. of a round,and waits for the first reply from tags.Therefore, This estimation method while powerful,has some limitations. when the first reply is toward the end of the round,the reader The main limitation is the large frame size,which translates to has to wait for the period of time almost equal to the frame a long protocol running time,when there exist a huge amount size. of tags.Suppose for a large tag population but the frame size is To resolve this issue to improve the query efficiency,we considerably small.All the tags'responses will be packed in a propose a new send-and-reply communication protocol among small number of slots,which means that the number of empty reader and tags.Compared to the original protocol,our new slots will become zero and number of collision slots will be protocol can identify the first non-empty slot in O(log2f)time equal to the frame size.To make estimation accurate,the frame slots instead of (f). size should be in proportion to the number of tags.Therefore, The new send-and-reply protocols for reader and tags are scanning the whole frame is inefficient when tag population is shown in Algorithm 1 and 2 respectively.In the protocols,the large.Furthermore,the performance is even worse in mobile reader sends an extra frame range r to all tags.Initially,the environment,where either RFID tag or reader can move.To reader splits the whole frame into two,and sets the first half count tags over a period of time,we have to use a very large frame as the candidate range,the second half frame as the frame size at the beginning,such that we can superimpose all alternative range.The reader always sends out its candidate the frames and guarantee that the number of empty slots is not range to the tags.Each tag evaluates h(f,R,id)and replies zero in the end [13]. immediately if the result is inside the range r.Otherwise,it To overcome the large frame size problem in the previous keeps silent without doing anything.Then the reader checks protocols,we propose a new idea based on a randomized the forthcoming slot.If the slot is empty,which indicates algorithm for counting.Suppose we have n random numbers there is no tag within the candidate range,the reader splits the uniformly and randomly chosen from (0.1).By examining the alternative range into two and picks the first half as the new smallest number,say x,we can estimate n.Intuitively,the candidate range,and the second half as the new alternative smaller z is,the larger n would be.If all the numbers are range.If the slot is not empty,which indicates there is at uniformly laid out,n should be approximated by 1/x.Of least one tag in the candidate range,the reader then splits the course,this estimation is very crude with a very large variance. candidate range into two,and sets the first half as the the new Fortunately,we can run the same process for a sufficiently large candidate range,and the second half as the new alternative number of times,the estimation will become more accurate. range.The above procedure is like a binary search tree as shown More details will be described later. in Fig.2.The reader keeps traversing from the root to the leaves Our scheme does not require the reader to scan the whole and records the path in each iteration.Finally,the reader can frame.Instead,the reader only needs to identify the first non- identify the first non-empty slot using the equation in line 16 empty slot,and uses the number of consecutive empty slots of Algorithm 1,where z;is a 0/1 bit indicating the state of the before that to estimate the number of tags.Again.the fewer ithiteration. the empty slots appear before the first non-empty slot,the more Fig.2 illustrates a simple example with frame size of 16. tags there are.In practice,certain number of iterations of such In the first iteration,the reader sends the frame size 16,search operations are performed,and the mean value is used to achieve an accurate estimation.For example,given, range [0,7],and a random seed to all tags.No tag replies,so the first slot is empty.Then the reader starts the second iteration {0|0|1} →X1=2 with a new range r=[8,11].At this time,at least one tag {1} +X2=0 replies,so the slot is "1".Repeating the same process twice, {0101010101010101011} →X3=9 the reader identifies the first non-empty slot to be 10. where Xi denotes the number of empty slots before the It is not difficult to find that if the number of tags is relatively first reply position in round i.From theoretical analysis and small to the frame size,our new send-and-reply protocol is extensive simulation,we find even though multiple iterations more efficient than the original protocol.Otherwise,the original are required for accuracy,the total time is still much shorter protocol is better.Therefore,we combine both of them to than the schemes in prior work. determine X.In the combined send-and-reply protocol,we define the number of waiting slots k.At every round,the V.ANONYMOUS ESTIMATING ALGORITHMS original protocol is tried first.Only when there is no reply In this section,we describe our novel RFID tag estimating within k slots,we turn to use our new protocol.So in the scheme,First Non-Empty slots Based (FNEB)estimator. worst case,only k+log2 f slots are required.IV. INTUITION The previous research [12], [13], [17] takes advantage of the framed-slotted ALOHA protocol to estimate the number of tags. The basic idea is based on the probability model we have described previously. The reader scans all the slots and records the status of each slot: empty, singleton, or collision. By examining the number of empty slots, collision slots, the reader can then estimate the number of tags. This estimation method while powerful, has some limitations. The main limitation is the large frame size, which translates to a long protocol running time, when there exist a huge amount of tags. Suppose for a large tag population but the frame size is considerably small. All the tags’ responses will be packed in a small number of slots, which means that the number of empty slots will become zero and number of collision slots will be equal to the frame size. To make estimation accurate, the frame size should be in proportion to the number of tags. Therefore, scanning the whole frame is inefficient when tag population is large. Furthermore, the performance is even worse in mobile environment, where either RFID tag or reader can move. To count tags over a period of time, we have to use a very large frame size at the beginning, such that we can superimpose all the frames and guarantee that the number of empty slots is not zero in the end [13]. To overcome the large frame size problem in the previous protocols, we propose a new idea based on a randomized algorithm for counting. Suppose we have n random numbers uniformly and randomly chosen from (0,1). By examining the smallest number, say x, we can estimate n. Intuitively, the smaller x is, the larger n would be. If all the numbers are uniformly laid out, n should be approximated by 1/x. Of course, this estimation is very crude with a very large variance. Fortunately, we can run the same process for a sufficiently large number of times, the estimation will become more accurate. More details will be described later. Our scheme does not require the reader to scan the whole frame. Instead, the reader only needs to identify the first non￾empty slot, and uses the number of consecutive empty slots before that to estimate the number of tags. Again, the fewer the empty slots appear before the first non-empty slot, the more tags there are. In practice, certain number of iterations of such operations are performed, and the mean value is used to achieve an accurate estimation. For example, given, { 0 | 0 | 1 } → X1 = 2 { 1 } → X2 = 0 { 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 } → X3 = 9 where Xi denotes the number of empty slots before the first reply position in round i. From theoretical analysis and extensive simulation, we find even though multiple iterations are required for accuracy, the total time is still much shorter than the schemes in prior work. V. ANONYMOUS ESTIMATING ALGORITHMS In this section, we describe our novel RFID tag estimating scheme, First Non-Empty slots Based (FNEB) estimator. A. Basic Algorithm Again, our algorithm is based on the idea of making obser￾vation on the first non-empty slot. However, if the number of tags t is small, the position of the first reply may be located at the end of the frame. Apparently, it is not efficient to use the original send-and-reply protocol described in Section III. In that protocol, a reader broadcasts f and R at the beginning of a round, and waits for the first reply from tags. Therefore, when the first reply is toward the end of the round, the reader has to wait for the period of time almost equal to the frame size. To resolve this issue to improve the query efficiency, we propose a new send-and-reply communication protocol among reader and tags. Compared to the original protocol, our new protocol can identify the first non-empty slot in O(log2f) time slots instead of O(f). The new send-and-reply protocols for reader and tags are shown in Algorithm 1 and 2 respectively. In the protocols, the reader sends an extra frame range r to all tags. Initially, the reader splits the whole frame into two, and sets the first half frame as the candidate range, the second half frame as the alternative range. The reader always sends out its candidate range to the tags. Each tag evaluates h(f, R, id) and replies immediately if the result is inside the range r. Otherwise, it keeps silent without doing anything. Then the reader checks the forthcoming slot. If the slot is empty, which indicates there is no tag within the candidate range, the reader splits the alternative range into two and picks the first half as the new candidate range, and the second half as the new alternative range. If the slot is not empty, which indicates there is at least one tag in the candidate range, the reader then splits the candidate range into two, and sets the first half as the the new candidate range, and the second half as the new alternative range. The above procedure is like a binary search tree as shown in Fig. 2. The reader keeps traversing from the root to the leaves and records the path in each iteration. Finally, the reader can identify the first non-empty slot using the equation in line 16 of Algorithm 1, where zi is a 0/1 bit indicating the state of the i th iteration. Fig. 2 illustrates a simple example with frame size of 16. In the first iteration, the reader sends the frame size 16, search range [0, 7], and a random seed to all tags. No tag replies, so the first slot is empty. Then the reader starts the second iteration with a new range r = [8, 11]. At this time, at least one tag replies, so the slot is “1”. Repeating the same process twice, the reader identifies the first non-empty slot to be 10. It is not difficult to find that if the number of tags is relatively small to the frame size, our new send-and-reply protocol is more efficient than the original protocol. Otherwise, the original protocol is better. Therefore, we combine both of them to determine X. In the combined send-and-reply protocol, we define the number of waiting slots k. At every round, the original protocol is tried first. Only when there is no reply within k slots, we turn to use our new protocol. So in the worst case, only k + log2 f slots are required