2013 Proceedings IEEE INFOCOM respectively in our simulation.From the figure,we observe IV.AN EFFICIENT THRESHOLD-BASED CLASSIFICATION that the estimation time changes very little with respect to the PROTOCOL number of tags.For example,UPE takes about 20 seconds to This s estimate the tag population in the range from 500 to 50,000.If section presents an efficient Threshold-Based Classification (TBC)Protocol,which is a combination of there are two groups of 25,000 tags each,the total estimation time for the two groups will be 40 seconds.However,if dynamic slot sharing among groups and maximum likelihood estimation of group sizes. there are 100 groups of 500 tags each,the total estimation time will be 2,000 seconds!Hence,these protocols are not A.Dynamic Slot Sharing suitable when there are numerous small groups Let's begin with a single group and use a well known Sheng,Tan and Li studied how to reduce the execution approach [12]of estimating the group population for our time for identifying populous groups whose sizes are discussion:The RFID reader broadcasts a polling request, larger than a threshold [2].They start with a simple fast asking tags to respond in a subsequent time frame of f slots. threshold checking scheme (TCS),which approximately Upon receiving the request,each tag randomly selects a slot answers whether the number of involved tags exceeds a in the frame to transmit.Listening to the channel,the reader threshold with high probability.Based on TCS.they propose converts the time frame into a bitmap.Each bit corresponds two probabilistic protocols.The first one is based on generic to a slot,'0'for an empty slot and'1'for a non-empty slot. group testing(GT),and the second protocol is a combination The reader then counts the number of '0'bits.Intuitively. of group testing and divide-and-conquer.Simulations show when there are more tags transmitting,fewer slots will be left that their best protocol can significantly reduce the execution empty,which means fewer '0'bits.A functional relationship time for populous group discovery.However,it is also can be established between the number of tags in the group shown in the simulation results that their execution time is and the number of '0'bits in the bitmap [12],and we can approximately proportional to the number of groups above use this function to estimate the former from the latter.When the threshold.Hence,the performance of the protocol will there are multiple groups,we can repeat the above scheme, deteriorate if the number of groups above the threshold using a different time frame for each group. is large.In addition,the RFID reader must be able to Analysis has shown that '0'bits must account for a distinguish three types of slots:(1)empty slot,during which reasonable portion of the bitmap in order to ensure accuracy. no tag transmit;(2)singleton slot,during which only one tag Hence,to handle a large tag group,we should conservatively transmits,and(3)collision slot,during which more than one set the frame size to be large enough such that a reasonable tag transmits. number of '0'bits will remain after all tags pick their slots to transmit.But when there are a mix of large and small We follow two general design principles when designing groups,there is no one-frame-size-fit-all:A small frame size our time-efficient classification protocol.First,we want for all groups will not do well for large groups;a large to minimize the length of each time slot.Based on the frame size is good for large groups,but it is wasteful for parameters of the Philips I-Code specification [22].in order small groups.This is particularly true when the majority of to transmit a 96-bit ID from a tag to an RFID read,we need all groups are small but there are a few large ones.Can we a slot of 2.11 ms.However,if the reader is not interested in choose a different frame size for each group based on its IDs but wants to distinguish collision slots from singleton or population?No,because per-group population is not given empty slots [2],tags should transmit 10-bit long responses, but what we want to know. using slots of 0.491 ms each.Furthermore,if the reader One way to solve the above dilemma is to share all does not need to distinguish collision slots from singleton slots among all groups.To do so,we have to abandon the slots but only wants to know whether the slots are empty or traditional approach of one time frame per group [2],[12], not,tags can transmit one-bit short responses,using slots [13],[20],[21],and instead use a single time frame for all of 0.321 ms each to carry one bit information (channel groups-a new approach that measures the sizes of all busy or idle);this is the type of slots we will use in our groups together:Each group ID is pseudo-randomly hashed protocol design.Note that 0.302 ms idle time is included to a certain number of slots in the time frame.Each tag in in each slot to separate it from neighboring slots.Second,the group will probabilistically pick one of these slots to we want to minimize the number of slots.Figure 1 clearly transmit.Listening to the channel,the reader converts the shows that traditional approaches of measuring one group at time frame into a bitmap.For each group,it extracts the bits a time will not work well when there are a large number that the group ID is hashed to.Those bits form the logical of groups.We take a new design that is drastically different bitmap of the group,from which the group size is estimated. from traditional ones:measuring the groups all at once.This In this approach,each bit and the corresponding slot may design has an interesting feature that its execution time is be shared by more than one group.This sharing introduces largely insensitive to the number of groups if the total number noise;the logical bitmap of one group may carry some bits of tags is about the same.It makes our protocol particularly that are set to'1'not by transmissions of tags in this group, suitable for situations where there are a large number of small but by transmissions of tags from other groups that happen to or medium-sized groups be hashed to the same time slots.Fortunately,in a bird's-eye 893respectively in our simulation. From the figure, we observe that the estimation time changes very little with respect to the number of tags. For example, UPE takes about 20 seconds to estimate the tag population in the range from 500 to 50,000. If there are two groups of 25,000 tags each, the total estimation time for the two groups will be 40 seconds. However, if there are 100 groups of 500 tags each, the total estimation time will be 2,000 seconds! Hence, these protocols are not suitable when there are numerous small groups. Sheng, Tan and Li studied how to reduce the execution time for identifying populous groups whose sizes are larger than a threshold [2]. They start with a simple fast threshold checking scheme (TCS), which approximately answers whether the number of involved tags exceeds a threshold with high probability. Based on TCS, they propose two probabilistic protocols. The first one is based on generic group testing (GT), and the second protocol is a combination of group testing and divide-and-conquer. Simulations show that their best protocol can significantly reduce the execution time for populous group discovery. However, it is also shown in the simulation results that their execution time is approximately proportional to the number of groups above the threshold. Hence, the performance of the protocol will deteriorate if the number of groups above the threshold is large. In addition, the RFID reader must be able to distinguish three types of slots: (1) empty slot, during which no tag transmit; (2) singleton slot, during which only one tag transmits, and (3) collision slot, during which more than one tag transmits. We follow two general design principles when designing our time-efficient classification protocol. First, we want to minimize the length of each time slot. Based on the parameters of the Philips I-Code specification [22], in order to transmit a 96-bit ID from a tag to an RFID read, we need a slot of 2.11 ms. However, if the reader is not interested in IDs but wants to distinguish collision slots from singleton or empty slots [2], tags should transmit 10-bit long responses, using slots of 0.491 ms each. Furthermore, if the reader does not need to distinguish collision slots from singleton slots but only wants to know whether the slots are empty or not, tags can transmit one-bit short responses, using slots of 0.321 ms each to carry one bit information (channel busy or idle); this is the type of slots we will use in our protocol design. Note that 0.302 ms idle time is included in each slot to separate it from neighboring slots. Second, we want to minimize the number of slots. Figure 1 clearly shows that traditional approaches of measuring one group at a time will not work well when there are a large number of groups. We take a new design that is drastically different from traditional ones: measuring the groups all at once. This design has an interesting feature that its execution time is largely insensitive to the number of groups if the total number of tags is about the same. It makes our protocol particularly suitable for situations where there are a large number of small or medium-sized groups. IV. AN EFFICIENT THRESHOLD-BASED CLASSIFICATION PROTOCOL This section presents an efficient Threshold-Based Classification (TBC) Protocol, which is a combination of dynamic slot sharing among groups and maximum likelihood estimation of group sizes. A. Dynamic Slot Sharing Let’s begin with a single group and use a well known approach [12] of estimating the group population for our discussion: The RFID reader broadcasts a polling request, asking tags to respond in a subsequent time frame of f slots. Upon receiving the request, each tag randomly selects a slot in the frame to transmit. Listening to the channel, the reader converts the time frame into a bitmap. Each bit corresponds to a slot, ‘0’ for an empty slot and ‘1’ for a non-empty slot. The reader then counts the number of ‘0’ bits. Intuitively, when there are more tags transmitting, fewer slots will be left empty, which means fewer ‘0’ bits. A functional relationship can be established between the number of tags in the group and the number of ‘0’ bits in the bitmap [12], and we can use this function to estimate the former from the latter. When there are multiple groups, we can repeat the above scheme, using a different time frame for each group. Analysis has shown that ‘0’ bits must account for a reasonable portion of the bitmap in order to ensure accuracy. Hence, to handle a large tag group, we should conservatively set the frame size to be large enough such that a reasonable number of ‘0’ bits will remain after all tags pick their slots to transmit. But when there are a mix of large and small groups, there is no one-frame-size-fit-all: A small frame size for all groups will not do well for large groups; a large frame size is good for large groups, but it is wasteful for small groups. This is particularly true when the majority of all groups are small but there are a few large ones. Can we choose a different frame size for each group based on its population? No, because per-group population is not given but what we want to know. One way to solve the above dilemma is to share all slots among all groups. To do so, we have to abandon the traditional approach of one time frame per group [2], [12], [13], [20], [21], and instead use a single time frame for all groups — a new approach that measures the sizes of all groups together: Each group ID is pseudo-randomly hashed to a certain number of slots in the time frame. Each tag in the group will probabilistically pick one of these slots to transmit. Listening to the channel, the reader converts the time frame into a bitmap. For each group, it extracts the bits that the group ID is hashed to. Those bits form the logical bitmap of the group, from which the group size is estimated. In this approach, each bit and the corresponding slot may be shared by more than one group. This sharing introduces noise; the logical bitmap of one group may carry some bits that are set to ‘1’ not by transmissions of tags in this group, but by transmissions of tags from other groups that happen to be hashed to the same time slots. Fortunately, in a bird’s-eye 2013 Proceedings IEEE INFOCOM 893