2013 Proceedings IEEE INFOCOM complete classification. of interest in this paper.The first type is called a tag-ID slot, 2.Given an accuracy requirement,we show analytically whose length is denoted as Tiag,during which a reader is how to compute optimal system parameters that minimize able to broadcast a 96-bit tag ID.The second type is called a the protocol execution time under the constraint of the short-response slot,whose length is denoted as Tshort,which requirement.Our estimation method based on logical bitmaps carries one-bit information:'0'for an empty slot when no tag ensures that false positive/false negative ratios are bounded, transmits.and '1'for an non-empty slot when one or more where false positive occurs when a below-threshold group is tags transmit a signal to make the channel busy. reported as above-threshold and false negative occurs when Significant asymmetry exists between readers and tags: an above-threshold group is not reported. Tags are supposed to be used in large quantities,and they 3.We comprehensively evaluate the proposed solution and must be cheap.The cost for a reader is less of a concern compare it with existing protocols.Our simulation results because its number in use is much fewer.Therefore,unlike match well with the analytical results,which demonstrate that tags,the reader is not limited in storage space,computation the new protocol performs far better in terms of execution power,or energy supply.If necessary,it can be connected to time than the best existing work. a powerful server for resources.With a high-quality antenna, The rest of the paper is organized as follows.Section II a reader is able to receive weak signals from tags.With low- presents the system model and defines the problem to be quality antennas,although tags can receive strong signals solved.Section III discusses the related work and gives the from the reader,they cannot receive each other's weak motivation for our solution.Section IV proposes our two- signals.They may not even sense whether the channel is phase protocol for the RFID threshold-based classification busy or idle,i.e.,whether another tag is transmitting.Nor can problem.Section V evaluates the new protocol through they sense if collision has occurred when two tags transmit simulations.Section VI draws the conclusion. simultaneously.Hence,a CSMA/CA-like MAC protocol [19] cannot be assumed in an RFID system.But the reader can II.PROBLEM DEFINITION AND SYSTEM MODEL detect whether the channel is idle or whether collision occurs A.System Model Such asymmetry points out a design principle that we should There are three types of RFID tags.Passive tags are follow:pushing the complexity to the reader while leaving most widely deployed today.They are cheap,but do the tags simple not have internal power sources.Passive tags rely on radio waves emitted from an RFID reader to power their circuit and transmit information back to the reader through B.Multigroup Threshold-based Classification Problem backscattering.They have short operational ranges,typically a few meters in an indoor environment.To cover a large Consider a big warehouse with tens of thousands of items area,arrays of RFID reader antennas must be installed.Semi- Each item is attached with an RFID tag for communication passive tags carry batteries to power their circuit,but still with an RFID reader.The items are divided into different rely on backscattering to transmit information.Active tags groups based on certain properties,which can be the use their own battery power to transmit,and consequently product sub-category,production date,or production place. do not need any energy supply from the reader.Active tags To support grouping,each tag ID should contain two operate at a much longer distance,making them particularly components:a group ID,which identifies the group the tag suitable for applications that cover a large area,where one belongs to,and a member ID,which identifies a specific tag or a few RFID readers are installed to access all tagged in the group.Clearly,all tags in a group must carry the same objects and perform management functions automatically. group ID,while tags in different groups carry different group With richer onboard resources,active tags are likely to gain IDs.We assume that the RFID reader knows the group IDs more popularity in the future,particularly when their prices in the system. drop over time as manufactural technologies are improved We define the population or size of a group as the and markets are expanded. number of tags in this group.As we have explained in Communication between readers and tags is time-slotted. the introduction,while it is possible to perform precise Readers send out a request,which is followed by a slotted multigroup classification at high cost,the focus of this paper time frame during which tags transmit in their selected is to study efficient solutions for approximate multigroup slots.The readers may take turns to transmit the request classification.We formally define the problem as follows: in order to avoid interference,or a more sophisticated Let h be the threshold and a be a large probability value. scheduling algorithm may be used to allow readers that do not We require that any group whose population exceeds h interfere to transmit simultaneously.When a tag transmits,should be reported with a probability of at least a.Let I as long as one reader receives the transmission correctly,be another integer parameter smaller than h and B be a the transmission will be successful.In our protocol design, small probability value.We also require that the probability we can logically treat all readers as one,which transmits of reporting any group with I or fewer tags should be no a request and then listens to the tags'responses.There are more than B.Let k:be the population of an arbitrary group different types of time slots [9],among which two types are g.Our performance objectives can be expressed in terms of 89complete classification. 2. Given an accuracy requirement, we show analytically how to compute optimal system parameters that minimize the protocol execution time under the constraint of the requirement. Our estimation method based on logical bitmaps ensures that false positive/false negative ratios are bounded, where false positive occurs when a below-threshold group is reported as above-threshold and false negative occurs when an above-threshold group is not reported. 3. We comprehensively evaluate the proposed solution and compare it with existing protocols. Our simulation results match well with the analytical results, which demonstrate that the new protocol performs far better in terms of execution time than the best existing work. The rest of the paper is organized as follows. Section II presents the system model and defines the problem to be solved. Section III discusses the related work and gives the motivation for our solution. Section IV proposes our two￾phase protocol for the RFID threshold-based classification problem. Section V evaluates the new protocol through simulations. Section VI draws the conclusion. II. PROBLEM DEFINITION AND SYSTEM MODEL A. System Model There are three types of RFID tags. Passive tags are most widely deployed today. They are cheap, but do not have internal power sources. Passive tags rely on radio waves emitted from an RFID reader to power their circuit and transmit information back to the reader through backscattering. They have short operational ranges, typically a few meters in an indoor environment. To cover a large area, arrays of RFID reader antennas must be installed. Semi￾passive tags carry batteries to power their circuit, but still rely on backscattering to transmit information. Active tags use their own battery power to transmit, and consequently do not need any energy supply from the reader. Active tags operate at a much longer distance, making them particularly suitable for applications that cover a large area, where one or a few RFID readers are installed to access all tagged objects and perform management functions automatically. With richer onboard resources, active tags are likely to gain more popularity in the future, particularly when their prices drop over time as manufactural technologies are improved and markets are expanded. Communication between readers and tags is time-slotted. Readers send out a request, which is followed by a slotted time frame during which tags transmit in their selected slots. The readers may take turns to transmit the request in order to avoid interference, or a more sophisticated scheduling algorithm may be used to allow readers that do not interfere to transmit simultaneously. When a tag transmits, as long as one reader receives the transmission correctly, the transmission will be successful. In our protocol design, we can logically treat all readers as one, which transmits a request and then listens to the tags’ responses. There are different types of time slots [9], among which two types are of interest in this paper. The first type is called a tag-ID slot, whose length is denoted as Ttag, during which a reader is able to broadcast a 96-bit tag ID. The second type is called a short-response slot, whose length is denoted as Tshort, which carries one-bit information: ‘0’ for an empty slot when no tag transmits, and ‘1’ for an non-empty slot when one or more tags transmit a signal to make the channel busy. Significant asymmetry exists between readers and tags: Tags are supposed to be used in large quantities, and they must be cheap. The cost for a reader is less of a concern because its number in use is much fewer. Therefore, unlike tags, the reader is not limited in storage space, computation power, or energy supply. If necessary, it can be connected to a powerful server for resources. With a high-quality antenna, a reader is able to receive weak signals from tags. With low￾quality antennas, although tags can receive strong signals from the reader, they cannot receive each other’s weak signals. They may not even sense whether the channel is busy or idle, i.e., whether another tag is transmitting. Nor can they sense if collision has occurred when two tags transmit simultaneously. Hence, a CSMA/CA-like MAC protocol [19] cannot be assumed in an RFID system. But the reader can detect whether the channel is idle or whether collision occurs. Such asymmetry points out a design principle that we should follow: pushing the complexity to the reader while leaving the tags simple. B. Multigroup Threshold-based Classification Problem Consider a big warehouse with tens of thousands of items. Each item is attached with an RFID tag for communication with an RFID reader. The items are divided into different groups based on certain properties, which can be the product sub-category, production date, or production place. To support grouping, each tag ID should contain two components: a group ID, which identifies the group the tag belongs to, and a member ID, which identifies a specific tag in the group. Clearly, all tags in a group must carry the same group ID, while tags in different groups carry different group IDs. We assume that the RFID reader knows the group IDs in the system. We define the population or size of a group as the number of tags in this group. As we have explained in the introduction, while it is possible to perform precise multigroup classification at high cost, the focus of this paper is to study efficient solutions for approximate multigroup classification. We formally define the problem as follows: Let h be the threshold and α be a large probability value. We require that any group whose population exceeds h should be reported with a probability of at least α. Let l be another integer parameter smaller than h and β be a small probability value. We also require that the probability of reporting any group with l or fewer tags should be no more than β. Let k be the population of an arbitrary group g. Our performance objectives can be expressed in terms of 2013 Proceedings IEEE INFOCOM 891