RFID标签数目估算机制研究（参考文献）An Efficient Protocol for RFID Multigroup Threshold-based Classification

2013 Proceedings IEEE INFOCOM An Efficient Protocol for RFID Multigroup Threshold-based Classification Wen Luo Yan Oiao Shigang Chen Department of Computer Information Science Engineering,University of Florida Abstract-RFID technology has many applications such as different countries or manufacturers in a port.One challenge object tracking,automatic inventory control,and supply chain is to determine whether the number of tags in each group is management.They can be used to identify individual objects or above or below a prescribed threshold value.The threshold count the population of each type of objects in a deployment area,no matter whether the objects are passports,retail may be set high to identify the populous groups,it may be products,books or even humans.Most existing work adopts a set to a level that triggers certain actions such as replenishing "flat"RFID system model and performs functions of collecting the stocks,or even multiple thresholds can be used to classify tag IDs,estimating the number of tags,or detecting the groups based on the range of their population sizes.Solving missing tags.However,in practice,tags are often attached to this multigroup threshold-based classification problem gives objects of different groups,which may represent a different product type in a warehouse,a different book category in a us a basic tool to access a large population of numerous library,etc.An interesting problem,called multigroup threshold- groups. based classification,is to determine whether the number of Precise classification requires us to know the precise objects in each group is above or below a prescribed threshold number of tags in each group.Tag identification protocols value.Solving this problem is important for inventory tracking [4,[5,[6],[7],[8],[9],[10l,[11]can do that,,but it takes applications.If the number of groups is very large,it will be inefficient to measure the groups one at a time.The best them significant time to complete if the number of tags is very existing solution for multigroup threshold-based classification large.One way to improve efficiency is relaxing the problem is based on generic group testing,whose design is however from accurate classification to approximate classification [2]. geared towards detecting a small number of populous groups where the classification accuracy can be tuned to meet a Its performance degrades quickly when the number of groups above the threshold become large.In this paper,we propose a pre-defined requirement.We may use cardinality estimation new classification protocol based on logical bitmaps.It achieves protocols [4].[5].[12],[13].[14]to estimate the number high efficiency by measuring all groups in a mixed fashion. of tags in each group,and classify the group based on In the meantime,we show that the new method is able to the estimation.However,those protocols are efficient when perform threshold-based classification with an accuracy that estimating a small number of large groups,but they are not can be pre-set to any desirable level,allowing tradeoff between time efficiency and accuracy. efficient when estimating a large number of small groups, because their execution time for each group is largely I.INTRODUCTION indifferent in group size,as we will demonstrate shortly. In [2],Sheng et al.apply group testing to approximately Radio-frequency identification(RFID)has rich application detect popular groups.When the number of groups above in cyber-physical systems for object tracking,automatic the threshold is small,their performance is good.However, inventory control,and supply chain management [1].[2].the performance of the group-testing-based solution degrades [3].Practical RFID systems widely exist for automatic toll quickly (in terms of the execution time)when the number of payment,access control to parking garages,object tracking, groups above threshold becomes large. theft prevention,tracking and monitoring.An RFID system In this paper,we propose a new classification protocol typically consists of three components:readers,tags and the that is scalable to a large number of groups.Its design is middleware software.Small RFID tags,each with a unique drastically different from traditional approaches that measure ID,are attached to objects,allowing an RFID reader to the size of one group at a time.It measures the sizes of quickly access the properties of each individual object or all groups together at once in a mixed fashion.Yet,the collect statistical information about a large group of objects.new protocol is able to perform threshold-based classification Much of the existing work on RFID systems is to design with an accuracy that can be pre-set to any desirable level, tag identification protocols that read the IDs from tags [4].allowing tradeoff between time efficiency and accuracy.Our [5],[6],[7],[8],[9],[10],[11].Other work designs efficient main contributions are summarized as follows: protocols to estimate the number of tags in a large RFID 1.We design an iterative protocol for threshold-based system [4],[5],[12],[13],[14],detects missing tags [15],classification in a multi-group RFID system based on logical [16],[17],or collects useful information [18]. bitmaps that share time slots uniformly at random among all This paper investigates a different problem.In practice, groups during the process of measuring their populations. tags are often attached to objects belonging to different We use the maximum likelihood estimation method to groups,for instance,different brands of shoes in a large shoe extract per-group information from the shared slots.Such store,different titles of books in a bookstore,and goods from slot sharing greatly reduces the amount of time it takes to 978-1-4673-5946-7/13/$31.00©20131EEE 890

An Efficient Protocol for RFID Multigroup Threshold-based Classification Wen Luo Yan Qiao Shigang Chen Department of Computer & Information Science & Engineering, University of Florida Abstract—RFID technology has many applications such as object tracking, automatic inventory control, and supply chain management. They can be used to identify individual objects or count the population of each type of objects in a deployment area, no matter whether the objects are passports, retail products, books or even humans. Most existing work adopts a “flat” RFID system model and performs functions of collecting tag IDs, estimating the number of tags, or detecting the missing tags. However, in practice, tags are often attached to objects of different groups, which may represent a different product type in a warehouse, a different book category in a library, etc. An interesting problem, called multigroup threshold￾based classification, is to determine whether the number of objects in each group is above or below a prescribed threshold value. Solving this problem is important for inventory tracking applications. If the number of groups is very large, it will be inefficient to measure the groups one at a time. The best existing solution for multigroup threshold-based classification is based on generic group testing, whose design is however geared towards detecting a small number of populous groups. Its performance degrades quickly when the number of groups above the threshold become large. In this paper, we propose a new classification protocol based on logical bitmaps. It achieves high efficiency by measuring all groups in a mixed fashion. In the meantime, we show that the new method is able to perform threshold-based classification with an accuracy that can be pre-set to any desirable level, allowing tradeoff between time efficiency and accuracy. I. INTRODUCTION Radio-frequency identification (RFID) has rich application in cyber-physical systems for object tracking, automatic inventory control, and supply chain management [1], [2], [3]. Practical RFID systems widely exist for automatic toll payment, access control to parking garages, object tracking, theft prevention, tracking and monitoring. An RFID system typically consists of three components: readers, tags and the middleware software. Small RFID tags, each with a unique ID, are attached to objects, allowing an RFID reader to quickly access the properties of each individual object or collect statistical information about a large group of objects. Much of the existing work on RFID systems is to design tag identification protocols that read the IDs from tags [4], [5], [6], [7], [8], [9], [10], [11]. Other work designs efficient protocols to estimate the number of tags in a large RFID system [4], [5], [12], [13], [14], detects missing tags [15], [16], [17], or collects useful information [18]. This paper investigates a different problem. In practice, tags are often attached to objects belonging to different groups, for instance, different brands of shoes in a large shoe store, different titles of books in a bookstore, and goods from different countries or manufacturers in a port. One challenge is to determine whether the number of tags in each group is above or below a prescribed threshold value. The threshold may be set high to identify the populous groups, it may be set to a level that triggers certain actions such as replenishing the stocks, or even multiple thresholds can be used to classify groups based on the range of their population sizes. Solving this multigroup threshold-based classification problem gives us a basic tool to access a large population of numerous groups. Precise classification requires us to know the precise number of tags in each group. Tag identification protocols [4], [5], [6], [7], [8], [9], [10], [11] can do that, but it takes them significant time to complete if the number of tags is very large. One way to improve efficiency is relaxing the problem from accurate classification to approximate classification [2], where the classification accuracy can be tuned to meet a pre-defined requirement. We may use cardinality estimation protocols [4], [5], [12], [13], [14] to estimate the number of tags in each group, and classify the group based on the estimation. However, those protocols are efficient when estimating a small number of large groups, but they are not efficient when estimating a large number of small groups, because their execution time for each group is largely indifferent in group size, as we will demonstrate shortly. In [2], Sheng et al. apply group testing to approximately detect popular groups. When the number of groups above the threshold is small, their performance is good. However, the performance of the group-testing-based solution degrades quickly (in terms of the execution time) when the number of groups above threshold becomes large. In this paper, we propose a new classification protocol that is scalable to a large number of groups. Its design is drastically different from traditional approaches that measure the size of one group at a time. It measures the sizes of all groups together at once in a mixed fashion. Yet, the new protocol is able to perform threshold-based classification with an accuracy that can be pre-set to any desirable level, allowing tradeoff between time efficiency and accuracy. Our main contributions are summarized as follows: 1. We design an iterative protocol for threshold-based classification in a multi-group RFID system based on logical bitmaps that share time slots uniformly at random among all groups during the process of measuring their populations. We use the maximum likelihood estimation method to extract per-group information from the shared slots. Such slot sharing greatly reduces the amount of time it takes to 978-1-4673-5946-7/13/$31.00 ©2013 IEEE 2013 Proceedings IEEE INFOCOM 890

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 89

complete 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

2013 Proceedings IEEE INFOCOM 140 UPE broadcasts a polling request,followed by a slotted time EZB 120 frame during which tags respond.Receiving the request,each Enhanced FNEB EMLEA tag independently picks up a time slot to transmit its ID. 100 80 To address collision,the reader has to repeat this process 60 for a certain number of pollings before all tag IDs can be successfully received.The second category is tree-based [8], 30 [9],[10],[11].These protocols resolve collision by traversing 转教结衬 a binary tree with the IDs of the tags being the leaf nodes.The 0 10000 2000030000 4000050000 reader first broadcasts an ID prefix string.The tags whose Group size IDs match the string will respond.If collision happens,the reader will append an '0'or'1'to the prefix string and send Fig.1.The estimation time with respect to the group size for UPE,EZB. Enhanced FNEB and EMLEA.when a'=99%and B=1%. out the new string.This process repeats until only one tag responds.Applying to the problem in this paper,these two TABLE I NOTATIONS types of protocols do not work well for large-scale RFID systems due to their long identification time. Symbols Descriptions A probabilistic analytical model is proposed by Kodialam 1-a upper bound of false negative ratio and Nandagopal for anonymously estimating tag population B upper bound of false positive ratio [12].Their estimators are the Zero Estimator(ZE),Collision m bit length of logical bitmap Estimator (CE),and the Unified Probabilistic Estimator number of tags (UPE),which collect information from tags in a series of s number of above-threshold groups time frames and estimates the population of tags based on k actual number of tags in an arbitrary group the number of empty slots and/or the number of collision estimated number of tags in an arbitrary group slots.A follow-up work by the same authors proposes ri random number in the ith polling the Enhanced Zero-Based Estimator (EZB)[13],which is length of the time frame each polling an asymptotically unbiased estimator and makes estimation H() hash function whose range is 0,f-1 only based on the number of empty slots.Qian et al. mid a tag's member ID provide a replicate-insensitive estimation algorithm called the 9id a tag's group ID Lottery-Frame scheme (LoF)[14].The Enhanced First Non- a prescribed higher bound threshold value Empty slots Based Estimator(Enhanced FNEB)[20]can be a prescribed lower bound threshold value used to estimate tag population in both static and dynamic number of pollings environments by measuring the position of the first non- empty slot in each frame.Li et al.[21]study the estimation problem for large-scale RFID systems from the energy angle based on Maximum Likelihood Estimation (MLE). conditional probabilities as follows: They design several energy-efficient probabilistic algorithms Prob{group g is reported by the reader k≥h}≥a that iteratively refine a control parameter to optimize the (1) information carried in the transmissions from tags,such Prob[group g is reported by the readerk≤I}≤B that both the number and the size of the transmissions are We treat the report of a group with l or fewer tags as a minimized. false positive,and the non-report of a group with h or more B.Motivation tags as a false negative.Hence,the above objectives can also We first show the performance of some existing work be stated as bounding the false positive ratio by B and the false negative ratio by 1-a. through simulation.From the simulation results,we argue that these protocols are not time-efficient when they are III.PRELIMINARY applied to the multigroup threshold-based classification problem. A.Prior Work Figure 1 presents the execution time of four existing One possible solution for the multigroup threshold-based protocols [12].[13],[20],[21]with respect to the number classification problem is to use a reader to collect the of tags in a group;details about the simulation setting and actual tag IDs from tags,where each ID contains bits that parameters can be found in Section V-A.The protocols identify the group of the tag.For a reader to successfully are designed to estimate the size of a single group.To collect tag IDs in proximity,collision arbitration protocols perform multigroup threshold-based classification,they have must be considered so that replies from multiple tags to estimate one group at a time.Their estimation accuracy will not be garbled due to collision.In general,collision is specified by a confidence interval:The probability for the arbitration protocols can be classified into two categories.estimate to deviate from the true group size by B'percentage The first category is ALOHA-based [4].[5],[6].[7].In or more should not exceed a',where a'and B'are two pre- these protocols,communication is initialized when a reader specified system parameters.They are set to 99%and 1% 892

0 20 40 60 80 100 120 140 0 10000 20000 30000 40000 50000 Time in seconds Group size UPE EZB Enhanced FNEB EMLEA Fig. 1. The estimation time with respect to the group size for UPE, EZB, Enhanced FNEB and EMLEA, when α = 99% and β = 1%. TABLE I NOTATIONS Symbols Descriptions 1 − α upper bound of false negative ratio β upper bound of false positive ratio m bit length of logical bitmap n number of tags S number of above-threshold groups k actual number of tags in an arbitrary group kˆ estimated number of tags in an arbitrary group ri random number in the ith polling f length of the time frame each polling H(·) hash function whose range is [0, f − 1] mid a tag’s member ID gid a tag’s group ID h a prescribed higher bound threshold value l a prescribed lower bound threshold value w number of pollings conditional probabilities as follows: P rob{ group g is reported by the reader |k ≥ h} ≥ α P rob{ group g is reported by the reader |k ≤ l} ≤ β (1) We treat the report of a group with l or fewer tags as a false positive, and the non-report of a group with h or more tags as a false negative. Hence, the above objectives can also be stated as bounding the false positive ratio by β and the false negative ratio by 1 − α. III. PRELIMINARY A. Prior Work One possible solution for the multigroup threshold-based classification problem is to use a reader to collect the actual tag IDs from tags, where each ID contains bits that identify the group of the tag. For a reader to successfully collect tag IDs in proximity, collision arbitration protocols must be considered so that replies from multiple tags will not be garbled due to collision. In general, collision arbitration protocols can be classified into two categories. The first category is ALOHA-based [4], [5], [6], [7]. In these protocols, communication is initialized when a reader broadcasts a polling request, followed by a slotted time frame during which tags respond. Receiving the request, each tag independently picks up a time slot to transmit its ID. To address collision, the reader has to repeat this process for a certain number of pollings before all tag IDs can be successfully received. The second category is tree-based [8], [9], [10], [11]. These protocols resolve collision by traversing a binary tree with the IDs of the tags being the leaf nodes. The reader first broadcasts an ID prefix string. The tags whose IDs match the string will respond. If collision happens, the reader will append an ‘0’ or ‘1’ to the prefix string and send out the new string. This process repeats until only one tag responds. Applying to the problem in this paper, these two types of protocols do not work well for large-scale RFID systems due to their long identification time. A probabilistic analytical model is proposed by Kodialam and Nandagopal for anonymously estimating tag population [12] . Their estimators are the Zero Estimator (ZE), Collision Estimator (CE), and the Unified Probabilistic Estimator (UPE), which collect information from tags in a series of time frames and estimates the population of tags based on the number of empty slots and/or the number of collision slots. A follow-up work by the same authors proposes the Enhanced Zero-Based Estimator (EZB) [13], which is an asymptotically unbiased estimator and makes estimation only based on the number of empty slots. Qian et al. provide a replicate-insensitive estimation algorithm called the Lottery-Frame scheme (LoF) [14]. The Enhanced First Non￾Empty slots Based Estimator (Enhanced FNEB) [20] can be used to estimate tag population in both static and dynamic environments by measuring the position of the first non￾empty slot in each frame. Li et al. [21] study the estimation problem for large-scale RFID systems from the energy angle based on Maximum Likelihood Estimation (MLE). They design several energy-efficient probabilistic algorithms that iteratively refine a control parameter to optimize the information carried in the transmissions from tags, such that both the number and the size of the transmissions are minimized. B. Motivation We first show the performance of some existing work through simulation. From the simulation results, we argue that these protocols are not time-efficient when they are applied to the multigroup threshold-based classification problem. Figure 1 presents the execution time of four existing protocols [12], [13], [20], [21] with respect to the number of tags in a group; details about the simulation setting and parameters can be found in Section V-A. The protocols are designed to estimate the size of a single group. To perform multigroup threshold-based classification, they have to estimate one group at a time. Their estimation accuracy is specified by a confidence interval: The probability for the estimate to deviate from the true group size by β percentage or more should not exceed α , where α and β are two pre￾specified system parameters. They are set to 99% and 1% 2013 Proceedings IEEE INFOCOM 892

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 893

respectively 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

2013 Proceedings IEEE INFOCOM view,all slots are shared by all groups uniformly at random Clearly,for tags of group g,the indices of their (through independent hashing),which means the noise is selected slots in the frame can only be H(gid F(ri,0)), uniformly distributed in the whole time frame.Such uniform H(gid F(ri,1))....,H(gidF(ri,m-1)).These slots noise is measurable.To estimate the size of a group,we will or more precisely,the bits converted from these slots,form use the logical bitmap of that group.but subtract the noise the logical bitmap of g.denoted as LB(g). that other groups introduce into the bitmap. Note that the value of H(tid)mod m gives the index of To further improve performance,the reader repeats the the corresponding bit in the logical bitmap.For example,if above approach multiple times to gather multiple independent a tag selects the H(gidF(ri,H(tid)mod m))th slot to logical bitmaps for each group,and estimation based on transmit,the (H(tid)mod m)th bit in the logical bitmap multiple logical bitmaps reduces the variance of the result. will be set to '1'.Essentially,we embed the logical bitmaps of all in Bi. B.Overview Our threshold-based classification(TBC)protocol consists D.Report Phase of three phases:the parameter-precomputing phase,the frame phase,and the report phase.The parameter-precomputing After w pollings,the reader obtains w bitmaps,Bi, phase computes system parameters for optimal performance l≤i≤w.It sends the bitmaps to an offline data of the protocol.Using these parameters,the frame phase processing module.There,the logical bitmaps of each group makes w(1)polling requests,each of them followed by is extracted.For an arbitrary group g,we extract a logical a time frame,during which tags of all groups transmit in bitmap LB;(g)from B;as follows:Set the jth bit of LB;(g) to be the H(gid F(ri,j))th bit in Bi,i.e..LB;(g)i]= selected slots.The reader converts each time frame into a bitmap,from which logical bitmaps are extracted.Using B[H(gd⊕F(r,j)l,where1≤i≤wand0≤j≤m-l. these logical bitmaps,the report phase employs the Maximum Let z;be the number of zeros observed in LBi(g).Let Likelihood Estimation (MLE)method to report the above- n be the total number of tags in the system and k be the threshold groups. actual population of group g.Below we derive the formula There are three system parameters:1)w is the number of to compute an estimate k of the population. pollings (or time frames),2)f is the size of each time frame, Consider the ith polling in the frame phase and an arbitrary i.e.,the number of slots in a frame or the number of bits in bit b in LBi(g).A tag in group g has a probability of to the bitmap that the frame is converted to,and 3)m is the select this bit and set it to'1'because the tag only sets one of size of each logical bitmap.Clearly,m<f.The execution the m bits in the logical bitmap of g.Any tag in other groups time of TBC is dominated by the w time frames,which have has a probability of to set this bit to '1'due to dynamic wx f time slots in total.We want to find the optimal values slot sharing across the whole frame.Hence,the probability for w,f and m such that the constraints in (1)are met and for b to remain zero is the value of w x f is minimized. g=0-7--a (2) Before presenting the parameter-precomputing phase for how the optimal system parameters are computed,we will Hence,the likelihood function L;for us to observe z;bits first describe the frame phase and the report phase because of zeros in LBi(g)is deriving the formulas for optimal system parameters relies on the knowledge of how the frame phase works. =a--1- C.Frame Phase The frame phase is composed of w pollings,which are x0-1--1-m (3) performed in a similar way:In the ith polling(where 1 i<w),an RFID reader first broadcasts a request message, The likelihood function L for us to observe all zi values, including a random number ri and the system parameters, 1≤i≤w,in the w logical bitmaps is L=Π1La.That f and m.The request message also serves the purpose of 1s, synchronizing the clocks of all tags for starting a time frame of f slots right after the request. =Π[-子-1-r Consider an arbitrary tag t in an arbitrary group g.The tag computes a hash value H(gid F(ri,H(tid)mod m)) as the index of the time slot selected for its transmission, ×a-1-n-a-aym-] (4) where H()is a hash function whose range is [0,f-1], gid is the tag's group ID,tid is the tag's member ID,and We want to find an estimate k that maximizes L,namely, F(z,y)is a pseudo-random number function that takes two input parameters:z and y.F(r,y)uses x as the seed, =arg max (5) generates y random numbers,and outputs the yth number. k The transmission from all participating tags forms a bitmap Since the maximum is not affected by monotone Bi. transformations,we take the logarithm of both sides 894

view, all slots are shared by all groups uniformly at random (through independent hashing), which means the noise is uniformly distributed in the whole time frame. Such uniform noise is measurable. To estimate the size of a group, we will use the logical bitmap of that group, but subtract the noise that other groups introduce into the bitmap. To further improve performance, the reader repeats the above approach multiple times to gather multiple independent logical bitmaps for each group, and estimation based on multiple logical bitmaps reduces the variance of the result. B. Overview Our threshold-based classification (TBC) protocol consists of three phases: the parameter-precomputing phase, the frame phase, and the report phase. The parameter-precomputing phase computes system parameters for optimal performance of the protocol. Using these parameters, the frame phase makes w(≥ 1) polling requests, each of them followed by a time frame, during which tags of all groups transmit in selected slots. The reader converts each time frame into a bitmap, from which logical bitmaps are extracted. Using these logical bitmaps, the report phase employs the Maximum Likelihood Estimation (MLE) method to report the above￾threshold groups. There are three system parameters: 1) w is the number of pollings (or time frames), 2) f is the size of each time frame, i.e., the number of slots in a frame or the number of bits in the bitmap that the frame is converted to, and 3) m is the size of each logical bitmap. Clearly, m<f. The execution time of TBC is dominated by the w time frames, which have w × f time slots in total. We want to find the optimal values for w, f and m such that the constraints in (1) are met and the value of w × f is minimized. Before presenting the parameter-precomputing phase for how the optimal system parameters are computed, we will first describe the frame phase and the report phase because deriving the formulas for optimal system parameters relies on the knowledge of how the frame phase works. C. Frame Phase The frame phase is composed of w pollings, which are performed in a similar way: In the ith polling (where 1 ≤ i ≤ w), an RFID reader first broadcasts a request message, including a random number ri and the system parameters, f and m. The request message also serves the purpose of synchronizing the clocks of all tags for starting a time frame of f slots right after the request. Consider an arbitrary tag t in an arbitrary group g. The tag computes a hash value H(gid F(ri, H(tid) mod m)) as the index of the time slot selected for its transmission, where H(·) is a hash function whose range is [0, f − 1], gid is the tag’s group ID, tid is the tag’s member ID, and F(x, y) is a pseudo-random number function that takes two input parameters: x and y. F(x, y) uses x as the seed, generates y random numbers, and outputs the yth number. The transmission from all participating tags forms a bitmap Bi. Clearly, for tags of group g, the indices of their selected slots in the frame can only be H(gid F(ri, 0)), H(gid F(ri, 1)), ... , H(gid F(ri, m − 1)). These slots or more precisely, the bits converted from these slots, form the logical bitmap of g, denoted as LBi(g). Note that the value of H(tid) mod m gives the index of the corresponding bit in the logical bitmap. For example, if a tag selects the H(gid F(ri, H(tid) mod m))th slot to transmit, the (H(tid) mod m)th bit in the logical bitmap will be set to ‘1’. Essentially, we embed the logical bitmaps of all in Bi. D. Report Phase After w pollings, the reader obtains w bitmaps, Bi, 1 ≤ i ≤ w. It sends the bitmaps to an offline data processing module. There, the logical bitmaps of each group is extracted. For an arbitrary group g, we extract a logical bitmap LBi(g) from Bi as follows: Set the jth bit of LBi(g) to be the H(gid F(ri, j))th bit in Bi, i.e., LBi(g)[j] = Bi[H(gid F(ri, j))], where 1 ≤ i ≤ w and 0 ≤ j ≤ m−1. Let xi be the number of zeros observed in LBi(g). Let n be the total number of tags in the system and k be the actual population of group g. Below we derive the formula to compute an estimate ˆ k of the population. Consider the ith polling in the frame phase and an arbitrary bit b in LBi(g). A tag in group g has a probability of 1 m to select this bit and set it to ‘1’ because the tag only sets one of the m bits in the logical bitmap of g. Any tag in other groups has a probability of 1 f to set this bit to ‘1’ due to dynamic slot sharing across the whole frame. Hence, the probability for b to remain zero is q = (1 − 1 f ) n−k(1 − 1 m) k. (2) Hence, the likelihood function Li for us to observe xi bits of zeros in LBi(g) is Li = ((1 − 1 f ) n−k(1 − 1 m) k) xi × (1 − (1 − 1 f ) n−k(1 − 1 m) k) m−xi . (3) The likelihood function L for us to observe all xi values, 1 ≤ i ≤ w, in the w logical bitmaps is L = w i=1 Li. That is, L = w j=1  ((1 − 1 f ) n−k(1 − 1 m) k) xi × (1 − (1 − 1 f ) n−k(1 − 1 m) k) m−xi  . (4) We want to find an estimate ˆ k that maximizes L, namely, ˆ k = arg max{L} k . (5) Since the maximum is not affected by monotone transformations, we take the logarithm of both sides 2013 Proceedings IEEE INFOCOM 894

2013 Proceedings IEEE INFOCOM of(4)月 That is, n)=a-月a1-月+kn(-》 -≥T +(m-z)1-1-子)”-*1-清 n(号) (6) (12) Differentiating both sides of the above equation,we have 空≤m片Pu- 兴-加”护 Let C=wm()T(1-)".Therefore.the probability for the reader to report a group is Prob(k T)= xaa-品-h- (7) Prob(∑1xi≤C): From (2),we know that zi follows the binomial After setting the right side to zero and simplifying it,we distribution with parameters m and (1-)(1-): have the following estimator, (之 Bind(m.(( (13) (8) Since a binomial distribution Bino(a,b)can be excellently 血（季 approximated by a normal distribution Norm(ab,ab(1-b)) when a is large enough (which is the case for m),(13)can In (7),m and f are given parameters whose values are be approximately written as pre-computed by the reader.The values of zi,1 T.where T is another system parameter that will be (17) determined in the next subsection based on the probabilistic performance objectives (1). The first performance objective in (1)can be translated E.Parameter-Precomputing Phase into Prob(k≥Tlk≥h)≥a,which is We first develop the constraints that the system parameters 、ae—2a 1 -(1-4)2 must satisfy in order to achieve the probabilistic performance (18) objectives.Based on the constraints,we determine the optimal values for the length m of logical bitmaps,the where k h.Since the left side of the inequality is an number w of pollings,the frame size f,and the parameter increasing function of k,we can replace the term k with h. T. Then,we have the first constraint for the system parameters. A group g whose estimated population is k will be reported C -(1-)2 if (19) k>T. (11) 895

of (4): ln(L) = w i=1  xi((n − k) ln(1 − 1 f ) + k ln(1 − 1 m)) + (m − xi) ln(1 − (1 − 1 f ) n−k(1 − 1 m) k)) . (6) Differentiating both sides of the above equation, we have ∂ lnL ∂k = w i=1  ( xi − m(1 − 1 f )n−k(1 − 1 m)k 1 − (1 − 1 f )n−k(1 − 1 m )k ) × (ln(1 − 1 m) − ln(1 − 1 f )) . (7) After setting the right side to zero and simplifying it, we have the following estimator, ˆ k = ln( w i=1 xi mw(1− 1 f )n ) ln( 1− 1 m 1− 1 f ) . (8) In (7), m and f are given parameters whose values are pre-computed by the reader. The values of xi, 1 ≤ i ≤ m, are obtained from LBi(g). The total number n of tags can be estimated from the bitmaps, Bi, 1 ≤ i ≤ w. Let Xi be the number of zeros in Bi. The probability for each tag to set a bit in Bi to ‘1’ is 1 f . The probability for each bit to remain zero is approximately (1 − 1 f )n. The likelihood function for us to observe Xi zeros in Bi, 1 ≤ i ≤ w, is L = w i=1 (1 − 1 f ) nXi (1 − (1 − 1 f ) n) f−Xi (9) Using the maximum likelihood estimation, we take the logarithm of both sides, differentiate it, and then let the right side be zero. We have w i=1 Xi − wf(1 − 1 f ) n = 0 n = ln w i=1 Xi wf ln(1 − 1 f ) , (10) where Xi, 1 ≤ i ≤ w, are obtained from Bi. For each group g, after we estimate its population ˆ k based on (8), we report the group (as an above-threshold group) if ˆ k ≥ T , where T is another system parameter that will be determined in the next subsection based on the probabilistic performance objectives (1). E. Parameter-Precomputing Phase We first develop the constraints that the system parameters must satisfy in order to achieve the probabilistic performance objectives. Based on the constraints, we determine the optimal values for the length m of logical bitmaps, the number w of pollings, the frame size f, and the parameter T . A group g whose estimated population is ˆ k will be reported if ˆ k ≥ T. (11) That is, ln( w i=1 xi mw(1− 1 f )n ) ln( 1− 1 m 1− 1 f ) ≥ T w i=1 xi ≤ wm( 1 − 1 m 1 − 1 f ) T (1 − 1 f ) n. (12) Let C = wm( 1− 1 m 1− 1 f )T (1 − 1 f )n. Therefore, the probability for the reader to report a group is P rob(ˆ k ≥ T ) = P rob( w i=1 xi ≤ C). From (2), we know that xi follows the binomial distribution with parameters m and (1 − 1 f )n−k(1 − 1 m )k: xi ∼ Bino(m,(1 − 1 f ) n−k(1 − 1 m) k). (13) Since a binomial distribution Bino(a, b) can be excellently approximated by a normal distribution Norm(ab, ab(1 − b)) when a is large enough (which is the case for m), (13) can be approximately written as xi ∼ Norm(m(1 − 1 f ) n−k(1 − 1 m) k, m(1 − 1 f ) n−k(1 − 1 m) k(1 − (1 − 1 f ) n−k(1 − 1 m) k)). (14) According to (14), we know w i=1 xi ∼ Norm(mw(1 − 1 f ) n−k(1 − 1 m) k, mw(1 − 1 f ) n−k(1 − 1 m) k(1 − (1 − 1 f ) n−k(1 − 1 m) k)). (15) Let μ = mw(1 − 1 f )n−k(1 − 1 m )k and σ2 = mw(1 − 1 f )n−k(1 − 1 m )k(1 − (1 − 1 f )n−k(1 − 1 m)k), then we have P rob( w i=1 xi = j) = 1 √ 2πσ2 e −(j−μ)2 2σ2 (16) Thus, P rob(ˆ k ≥ T ) = P ro( w i=1 xi ≤ C) =  C j=0 1 √ 2πσ2 e −(j−μ)2 2σ2 (17) The first performance objective in (1) can be translated into P rob(ˆ k ≥ T |k ≥ h) ≥ α, which is  C j=0 1 √ 2πσ2 e −(j−μ)2 2σ2 ≥ α (18) where k ≥ h. Since the left side of the inequality is an increasing function of k, we can replace the term k with h. Then, we have the first constraint for the system parameters.  C j=0 1 √2πσ12 e −(j−μ1)2 2σ12 ≥ α, (19) 2013 Proceedings IEEE INFOCOM 895

2013 Proceedings IEEE INFOCOM where ui mw(1-)n-h(1-)h and 012 u(1-(1- identifies populous groups whose sizes are larger than a )-(1-品)) threshold. Similarly,the second performance objective in (1)can be Our simulation setting is based on the Philips I-Code translated into the following constraint, specification [22].Any two consecutive transmissions(from a reader to tags or from a tag to the reader)are separated by a 1 e ≤B, (20) waiting time of 0.302 ms.According to the specification,the transmission rate from a tag to the reader is different from the transmission rate from the reader to a tag.The rate from where u2=mw(1-)-(1-)and 22=u2(1-(1-a tag to the reader is 53 Kb/sec;it takes 0.018 ms for a tag )m-(1-a). to transmit one bit.The length of a slot is calculated as the Our goal is to find optimal system parameters that sum of a waiting time and the time for the tag to transmit minimize the execution time required by TBC,i.e.,w x f, a certain number of bits.Since the type of slots used by subject to the above two constraints. TBC and Enhanced FNEB,Tshort,contains only one bit,the slot length is 0.321 ms.The type of slots used by UPE and GT needs to detect collision and contains 10 bits.Their slot Minimize w×f, 21) length is Tiong=0.49ms.Comparing with the time used by C 1 tags to transmit to the reader,the time used by the reader to subject to 211 0V2m京 transmit to the tags are negligible in all four protocols. In our simulation,n =500,000,the range of group sizes 1 -(1-42)2 is (0.500].h =250,and the value of l varies.There 2022 0V2m02 are 2,000 groups,and the number z of above-threshold(h) groups may vary in simulation,but its default value is 1 C =mw(- 1,000.First,we randomly choose the sizes for the above- 1- threshold groups from[250,500].After that,we distribute the remaining M tags into the below-threshold groups.For the 1=mw(1 n-h(1-二)》 first below-threshold group,we generate a random number between 1 and min49.tobe its population,which 2=1-1-m-1-) is denoted as s1.For the second below-threshold group,we select a random value between I and min{49,as 2=m(1- --》 its population,which is denoted as s2.Similarly,we assign a random value between 1 and min(249,)as the 2=1-1--1- population for the third below-threshold group.This process m is repeated for all remaining below-threshold groups.If there The parameters h,l,a and B are given by the performance are still tags left unassigned,we assign them arbitrarily to objectives (1).To solve the above constrained optimization below-threshold groups as long as their sizes are below 250. problem,we need to determine the optimal values of the For each simulation,TBC will compute the optimal value remaining four system parameters w,f,m and T,such that of w x f (together with the optimal system parameters). w x f is minimized.Since all these parameters are bounded Once w x f is determined,the execution time is known, integers,we may find the optimal set of parameters by which is Tshort x w x f plus the time for broadcasting exhaustive search,which occurs offline before the TBC polling requests.GT will also compute its optimal system protocol is executed.The computation process includes four parameters,including the time frame size f,the number R loops to enumerate all possible discrete values for the four of rounds,and the number W of shuffled groups W.The parameters. execution time required by GT is Tiong×f×W×R.UPE and Enhanced FNEB work under the settings based on their V.NUMERICAL RESULTS original papers.Their execution times are the sum of the A.Setting times for measuring the populations of individual groups. We evaluate the performance of TBC and compare it B.Execution time required in terms of a,B and I/h with the existing work,including the Unified Probabilistic We compare TBC,GT,UPE and Enhanced FNEB in terms Estimator(UPE)[12],the Enhanced First Non-Empty slots of execution time.Tables II-IV show our simulation results Based Estimator (Enhanced FNEB)[20],and the Group under different values of l/h,a and B. Testing(GT)[2].UPE and Enhanced FNEB are designed for Table II shows the execution time required when a =99% RFID population estimation,not for satisfying the probability and B=1%.From the table,we can see that TBC has a much performance objectives in(1).However,the estimation results smaller execution time than GT,UPE and Enhanced FNEB. from these two estimators can be used for classification by GT takes 1'14"when I =0.1h,which is 3.09 times of TBC. reporting those groups whose estimated sizes are above a UPE and Enhanced FNEB consume an order of magnitude threshold.GT is the most related work.It probabilistically or more time than GT and TBC. 896

where μ1 = mw(1− 1 f )n−h(1− 1 m )h and σ1 2 = μ1(1−(1− 1 f )n−h(1 − 1 m )h). Similarly, the second performance objective in (1) can be translated into the following constraint,  C j=0 1 √2πσ22 e −(j−μ2)2 2σ22 ≤ β, (20) where μ2 = mw(1 − 1 f )n−l (1 − 1 m )l and σ2 2 = μ2(1 − (1 − 1 f )n−l (1 − 1 m )l ). Our goal is to find optimal system parameters that minimize the execution time required by TBC, i.e., w × f, subject to the above two constraints. Minimize w × f, (21) subject to  C j=0 1 √2πσ12 e −(j−μ1)2 2σ12 ≥ α  C j=0 1 √2πσ22 e −(j−μ2)2 2σ22 ≤ β C = mw( 1 − 1 m 1 − 1 f ) T (1 − 1 f ) n μ1 = mw(1 − 1 f ) n−h(1 − 1 m) h σ1 2 = μ1(1 − (1 − 1 f ) n−h(1 − 1 m) h) μ2 = mw(1 − 1 f ) n−l (1 − 1 m) l σ2 2 = μ2(1 − (1 − 1 f ) n−l (1 − 1 m) l ). The parameters h, l, α and β are given by the performance objectives (1). To solve the above constrained optimization problem, we need to determine the optimal values of the remaining four system parameters w, f, m and T , such that w × f is minimized. Since all these parameters are bounded integers, we may find the optimal set of parameters by exhaustive search, which occurs offline before the TBC protocol is executed. The computation process includes four loops to enumerate all possible discrete values for the four parameters. V. NUMERICAL RESULTS A. Setting We evaluate the performance of TBC and compare it with the existing work, including the Unified Probabilistic Estimator (UPE) [12], the Enhanced First Non-Empty slots Based Estimator (Enhanced FNEB) [20], and the Group Testing (GT) [2]. UPE and Enhanced FNEB are designed for RFID population estimation, not for satisfying the probability performance objectives in (1). However, the estimation results from these two estimators can be used for classification by reporting those groups whose estimated sizes are above a threshold. GT is the most related work. It probabilistically identifies populous groups whose sizes are larger than a threshold. Our simulation setting is based on the Philips I-Code specification [22]. Any two consecutive transmissions (from a reader to tags or from a tag to the reader) are separated by a waiting time of 0.302 ms. According to the specification, the transmission rate from a tag to the reader is different from the transmission rate from the reader to a tag. The rate from a tag to the reader is 53 Kb/sec; it takes 0.018 ms for a tag to transmit one bit. The length of a slot is calculated as the sum of a waiting time and the time for the tag to transmit a certain number of bits. Since the type of slots used by TBC and Enhanced FNEB, Tshort, contains only one bit, the slot length is 0.321 ms. The type of slots used by UPE and GT needs to detect collision and contains 10 bits. Their slot length is Tlong = 0.49ms. Comparing with the time used by tags to transmit to the reader, the time used by the reader to transmit to the tags are negligible in all four protocols. In our simulation, n = 500, 000, the range of group sizes is (0, 500], h = 250, and the value of l varies. There are 2,000 groups, and the number x of above-threshold(h) groups may vary in simulation, but its default value is 1,000. First, we randomly choose the sizes for the above￾threshold groups from [250, 500]. After that, we distribute the remaining M tags into the below-threshold groups. For the first below-threshold group, we generate a random number between 1 and min{249, M 2000−x } to be its population, which is denoted as s1. For the second below-threshold group, we select a random value between 1 and min{249, M−s1 1999−x } as its population, which is denoted as s2. Similarly, we assign a random value between 1 and min{249, M−s1−s2 1998−x } as the population for the third below-threshold group. This process is repeated for all remaining below-threshold groups. If there are still tags left unassigned, we assign them arbitrarily to below-threshold groups as long as their sizes are below 250. For each simulation, TBC will compute the optimal value of w × f (together with the optimal system parameters). Once w × f is determined, the execution time is known, which is Tshort × w × f plus the time for broadcasting polling requests. GT will also compute its optimal system parameters, including the time frame size f, the number R of rounds, and the number W of shuffled groups W. The execution time required by GT is Tlong × f × W × R. UPE and Enhanced FNEB work under the settings based on their original papers. Their execution times are the sum of the times for measuring the populations of individual groups. B. Execution time required in terms of α, β and l/h We compare TBC, GT, UPE and Enhanced FNEB in terms of execution time. Tables II – IV show our simulation results under different values of l/h, α and β. Table II shows the execution time required when α = 99% and β = 1%. From the table, we can see that TBC has a much smaller execution time than GT, UPE and Enhanced FNEB. GT takes 1 14 when l = 0.1h, which is 3.09 times of TBC. UPE and Enhanced FNEB consume an order of magnitude or more time than GT and TBC. 2013 Proceedings IEEE INFOCOM 896

2013 Proceedings IEEE INFOCOM TABLE II 250 TBC ESTIMATION TIME COMPARISON WHEN O =99%AND B=1% 200 GT…… Estimation Time in minutes(/),seconds(/) 150 TBC GT UPE Enhanced FNEB 1=0.1h 1'14" 349" 556'50" 336'36" 100 1=0.3h1'42" 426" 55650" 33636" 50 1=0.5h3'05 615" 55650 33636 l=0.7h 4'51" 912" 55650" 33636" 1002003004005006007008009001000 l=0.9h 621" 11'58" 55650" 33636" Number of above-threshold groups S TABLE III Fig.2.Execution time with respect to the number of groups S which are ESTIMATION TIME COMPARISON WHEN =95%AND 8=5% supposed to be reported when a =99%,B =1%and I =0.1h.The total number of tags n is fixed to be 500,000 at each point. Estimation Time in minutes(/),seconds(/) TBC GT UPE Enhanced FNEB GT uses a simple,fast threshold checking scheme (TCS) l=0.1h 447 1'55" 17'31M 1027" to probabilistically identify populous groups with size larger l=0.3h 1'6" 2'9" 1731" 1027" than a threshold.However,TCS incurs a large variance in 1=0.5h 1'47" 257" 55650" 33636" its estimated result.To satisfy a high accuracy requirement, l=0.7h 2394 411" 55650% 33636" a large number of TCS executions are required,which =0.9h 4'4" 6'36" 556W50" 33636" lengthens execution time.In addition,GT has to identify whether a slot is empty,singleton or collision,resulting in TABLE IV longer slots.It is not efficient to invoke UPE and Enhanced ESTIMATION TIME COMPARISON WHEN =90%AND B=10% FNEB to estimate the size of each group one at a time.In Estimation Time in minutes(/),seconds(/) addition,UPE requires tags to transmit 10-bit responses to TBC GT UPE Enhanced FNEB distinguish singleton slots from collision slots.TBC estimate =0.1h 38 1'33" 10/37M 75m all group sizes together and share slots among all groups.It =0.3h 52' 1'51" 1037 75" only needs to know whether each slot is empty or not.Hence, l=0.5h 1'17" 2'18" 55650" 336'36" its execution time is the shortest. =0.7h 36 55650" 33636" In Table II,when l/h becomes larger,both TBC and 1'56 =0.9h 2'504 4'55" 556Y50 336'36" GT need more time to classify the above-threshold groups. This is because a larger ratio of l/h means a higher accuracy requirement for above-threshold classification.The performance gain by TBC over GT shrinks as l/h increases, 250 but remains significant.For example,when I=0.1h,the TBC 200 GT execution time required by GT is 3.09 times that of TBC. When I=0.9h,the time by GT becomes 1.9 times that of 150 TBC. Tables III and IV compare the execution time of the four 100 protocols when a=95%,B=5%,and a =90%,B=10%, 50 respectively.These two tables show that TBC outperforms other protocols under different parameter settings.When 0 1002003004005006007008009001000 comparing with Table II,we see that given the same values Number of above-threshold groups S of h and l,the execution times of all protocols are reduced when a decreases or B increases. Fig.3.Execution time with respect to the number of groups S which are supposed to be reported when a =99%,B=1%and I =0.1h.The total C.Execution time required in terms of the number of above- number of tags n for all the groups increases along with S. threshold groups In the previous comparison,the number of above-threshold viewed as a constant even when the number of groups is groups is set at the default value 1,000.We further compare different.Such an observation agrees with (21),which does TBC and GT by varying the number of above-threshold not include S in its formulation.In Fig.3,we allow the total groups,denoted as S.Let a=99%and B=1%.In Fig.2.number of tags to change.Each below-threshold group takes we keep n 500,000 and vary the the number of above- a random population in the range of(0,250)and each above- threshold groups from 100 to 1,000.As we see in the figure, threshold group takes a random population in the range of TBC outperforms GT,and the execution time of TBC is 250,500.From the figure,we observe that the classification insensitive to S.As long as the total number of tags in the times of TBC and GT are approximately proportional to the system is the same,the execution time can be approximately number of above-threshold groups.However,the line of GT 897

0 50 100 150 200 250 100 200 300 400 500 600 700 800 900 1000 Time in seconds Number of above-threshold groups S TBC GT Fig. 2. Execution time with respect to the number of groups S which are supposed to be reported when α = 99%, β = 1% and l = 0.1h. The total number of tags n is fixed to be 500,000 at each point. GT uses a simple, fast threshold checking scheme (TCS) to probabilistically identify populous groups with size larger than a threshold. However, TCS incurs a large variance in its estimated result. To satisfy a high accuracy requirement, a large number of TCS executions are required, which lengthens execution time. In addition, GT has to identify whether a slot is empty, singleton or collision, resulting in longer slots. It is not efficient to invoke UPE and Enhanced FNEB to estimate the size of each group one at a time. In addition, UPE requires tags to transmit 10-bit responses to distinguish singleton slots from collision slots. TBC estimate all group sizes together and share slots among all groups. It only needs to know whether each slot is empty or not. Hence, its execution time is the shortest. In Table II, when l/h becomes larger, both TBC and GT need more time to classify the above-threshold groups. This is because a larger ratio of l/h means a higher accuracy requirement for above-threshold classification. The performance gain by TBC over GT shrinks as l/h increases, but remains significant. For example, when l = 0.1h, the execution time required by GT is 3.09 times that of TBC. When l = 0.9h, the time by GT becomes 1.9 times that of TBC. Tables III and IV compare the execution time of the four protocols when α = 95%, β = 5%, and α = 90%, β = 10%, respectively. These two tables show that TBC outperforms other protocols under different parameter settings. When comparing with Table II, we see that given the same values of h and l, the execution times of all protocols are reduced when α decreases or β increases. C. Execution time required in terms of the number of above￾threshold groups In the previous comparison, the number of above-threshold groups is set at the default value 1,000. We further compare TBC and GT by varying the number of above-threshold groups, denoted as S. Let α = 99% and β = 1%. In Fig. 2, we keep n = 500, 000 and vary the the number of above￾threshold groups from 100 to 1,000. As we see in the figure, TBC outperforms GT, and the execution time of TBC is insensitive to S. As long as the total number of tags in the system is the same, the execution time can be approximately TABLE II ESTIMATION TIME COMPARISON WHEN α = 99% AND β = 1% Estimation Time in minutes(), seconds() TBC GT UPE Enhanced FNEB l = 0.1h 1 14 3 49 556 50 336 36 l = 0.3h 1 42 4 26 556 50 336 36 l = 0.5h 3 05 615 55650 33636 l = 0.7h 4 51 9 12 556 50 336 36 l = 0.9h 6 21 11 58 55650 33636 TABLE III ESTIMATION TIME COMPARISON WHEN α = 95% AND β = 5% Estimation Time in minutes(), seconds() TBC GT UPE Enhanced FNEB l = 0.1h 44 1 55 17 31 10 27 l = 0.3h 16 2 9 17 31 1027 l = 0.5h 1 47 2 57 556 50 336 36 l = 0.7h 239 411 55650 33636 l = 0.9h 4 4 6 36 556 50 336 36 TABLE IV ESTIMATION TIME COMPARISON WHEN α = 90% AND β = 10% Estimation Time in minutes(), seconds() TBC GT UPE Enhanced FNEB l = 0.1h 38 133 10 37 7 5 l = 0.3h 52 1 51 10 37 7 5 l = 0.5h 1 17 218 55650 33636 l = 0.7h 1 56 3 6 556 50 336 36 l = 0.9h 250 455 55650 33636 0 50 100 150 200 250 100 200 300 400 500 600 700 800 900 1000 Time in seconds Number of above-threshold groups S TBC GT Fig. 3. Execution time with respect to the number of groups S which are supposed to be reported when α = 99%, β = 1% and l = 0.1h. The total number of tags n for all the groups increases along with S. viewed as a constant even when the number of groups is different. Such an observation agrees with (21), which does not include S in its formulation. In Fig. 3, we allow the total number of tags to change. Each below-threshold group takes a random population in the range of (0, 250) and each above￾threshold group takes a random population in the range of [250, 500]. From the figure, we observe that the classification times of TBC and GT are approximately proportional to the number of above-threshold groups. However, the line of GT 2013 Proceedings IEEE INFOCOM 897

2013 Proceedings IEEE INFOCOM 300 [6]J.Cha and J.Kim,"Novel Anti-collision Algorithms for Fast Object nl0k Identification in RFID System,"Proc.IEEE ICPADS,2005. n=50k 250 n=100k [7]D.Klair,K.Chin,and R.Raad,"On the Energy Consumption of Pure 200 n=200k and Slotted Aloha based RFID Anti-Collision Protocols."Computer 0一440k==== Communications,2008. 150 n=500k [8]D.Hush and C.Wood,"Analysis of Tree Algorithm for RFID Arbitration,"Proc.of IEEE ISIT.1998. u I 100 [9]J.Myung and W.Lee,"An adaptive memoryless tag anti-collision 50 protocol for RFID networks,"Proc.IEEE ICC,2005. [10]H.Choi,J.Cha,and J.Kim,"Fast Wireless Anti-collision Algorithm 0 in Ubiquitous ID System,"Proc.IEEE VTC,Sep 2004. 0.1 0.20.30.40.50.6 [11]V.Namboodiri and L.Gao,"Energy-Aware Tag Anti-Collision h Protocols for RFID Systems,"Proc.of IEEE PerCom,2007. [12]M.Kodialam and T.Nandagopal,"Fast and Reliable Estimation Fig.4.Execution time with respect to the value of l/h when o =99%, Schemes in RFID Systems,"Proc.of ACM MOBICOM,Los Angeles. B=1% 2006. [13]M.Kodialam,T.Nandagopal,and W.Lau."Anonymous Tracking using RFID tags,”Poc.g寸IEEE INFOCOM,2007. has a larger slope than that of TBC. [14]C.Qian.H.Ngan,and Y.Liu,"Cardinality Estimation for Large-scale RFID Systems,"Proc.of IEEE PerCom,2008. D.Execution time required in terms of the total tag number [15]S.Chen T.Li and Y.Ling,"Identifying the Missing Tags in a Large RFID System."Proc.of ACM Mobihoc.2010. Finally,we evaluate the performance of TBC under [16]B.Sheng.Q.Li,and W.Mao,"Efficient Continuous Scanning in RFID different numbers of tags.The results are shown in Fig.4. Systems,"Proc.of IEEE INFOCOM,March 2010. [17]C.Tan,B.Sheng,and Q.Li,"How to Monitor for Missing RFID where a =99%,B=1%,I/h varies from 0.1 to 0.6,and n Tags."Proc.of IEEE ICDCS.June 2008. varies from 10k to 500k.Each value of n corresponds to a [18]S.Chen,M.Zhang.and B.Xiao."Efficient Information Collection Protocols for Sensor-augmented RFID Networks,"Proc.of IEEE curve in the figure.The execution time of TBC increases as n INFOCOM.April 2011. increases,which is expected.For all values of n,we observe [19]B.Bianchi,L.Fratta,and M.Oliveri,"Performance Evaluation and that the execution time of TBC increases as I/h increases, Enhancement of the CSMA/CA MAC Protocol for 802.11 Wireless confirming the results in Tables II-IV LANs,"Personal,Indoor and Mobile Radio Communications.IEEE International Symposium on.vol.2,pp.392-396.1996. [20]H.Han,B.Sheng.Chiu C.Tan,Q.Li,W.Mao,and S.Lu,"Counting VI.CONCLUSION RFID Tags Efficiently and Anonymously,"Proc.IEEE INFOCOM, March 2010. This paper proposes a new solution for multigroup [21]T.Li,S.Wu,S.Chen,and M.Yang,"Energy Efficient Algorithms for threshold-based classification in a large RFID system.While the RFID Estimation Problem."Proc.IEEE INFOCOM,March 2010. much of the prior work focuses on estimating the total [22]Philips Semiconductors, "I-CODE Smart Label RFID Tags," http://www.nxp.com/acrobat_download/other/identification/SL092030.pdf. number of tags in a system,it is inefficient to apply those Jan2004. solutions to sequentially estimate the size of each tag group and see if it is above a threshold.In this paper,we propose a new protocol based on logical bitmaps that allow the sizes of all groups to be estimated together for classification. Slot sharing is exploited to reduce the execution time.The new method is able to perform tag-group classification with any pre-set accuracy.Our protocol can be configured for tradeoff between time efficiency and accuracy.We evaluate the proposed solution and compare it with existing protocols through simulations,which demonstrate that the new protocol performs better in terms of execution time than the best existing work. VII.ACKNOWLEDGEMENT This work was supported in part by the National Science Foundation under grant CNS-1115548. REFERENCES [1]L.Ni,Y.Liu,and Y.C.Lau,"Landmarc:Indoor Location Sensing using Active RFID,"Proc.of IEEE PerCom,2003. [2]B.Sheng.Chiu C.Tan,Q.Li.and W.Mao. “Finding Popular Categories for RFID Tags,"Proc.ACM MOBIHOC,May 2008. [3]Q.Yao,Y.Qi,J.Han,J.Zhao,X.Li,and Y.Liu,"Randomizing RFID Private Authentication,"Proc.of IEEE PerCom,2009. [4]H.Vogt,"Efficient Object Identification with Passive RFID Tags," Proc.of IEEE PerCom.2002. [5]J.Zhai and G.N.Wang."An Anti-Collision Algorithm Using Two- functioned Estimation for RFID Tags,"Proc.of /CCSA,2005. 898

0 50 100 150 200 250 300 0.1 0.2 0.3 0.4 0.5 0.6 Time in seconds l/h n=10k n=50k n=100k n=200k n=400k n=500k Fig. 4. Execution time with respect to the value of l/h when α = 99%, β = 1% has a larger slope than that of TBC. D. Execution time required in terms of the total tag number Finally, we evaluate the performance of TBC under different numbers of tags. The results are shown in Fig. 4, where α = 99%, β = 1%, l/h varies from 0.1 to 0.6, and n varies from 10k to 500k. Each value of n corresponds to a curve in the figure. The execution time of TBC increases as n increases, which is expected. For all values of n, we observe that the execution time of TBC increases as l/h increases, confirming the results in Tables II-IV. VI. CONCLUSION This paper proposes a new solution for multigroup threshold-based classification in a large RFID system. While much of the prior work focuses on estimating the total number of tags in a system, it is inefficient to apply those solutions to sequentially estimate the size of each tag group and see if it is above a threshold. In this paper, we propose a new protocol based on logical bitmaps that allow the sizes of all groups to be estimated together for classification. Slot sharing is exploited to reduce the execution time. The new method is able to perform tag-group classification with any pre-set accuracy. Our protocol can be configured for tradeoff between time efficiency and accuracy. We evaluate the proposed solution and compare it with existing protocols through simulations, which demonstrate that the new protocol performs better in terms of execution time than the best existing work. VII. ACKNOWLEDGEMENT This work was supported in part by the National Science Foundation under grant CNS-1115548. REFERENCES [1] L. Ni, Y. Liu, and Y. C. Lau, “Landmarc: Indoor Location Sensing using Active RFID,” Proc. of IEEE PerCom, 2003. [2] B. Sheng, Chiu C. Tan, Q. Li, and W. Mao, “Finding Popular Categories for RFID Tags,” Proc. ACM MOBIHOC, May 2008. [3] Q. Yao, Y. Qi, J. Han, J. Zhao, X. Li, and Y. Liu, “Randomizing RFID Private Authentication,” Proc. of IEEE PerCom, 2009. [4] H. Vogt, “Efficient Object Identification with Passive RFID Tags,” Proc. of IEEE PerCom, 2002. [5] J. Zhai and G. N. Wang, “An Anti-Collision Algorithm Using Two￾functioned Estimation for RFID Tags,” Proc. of ICCSA, 2005. [6] J. Cha and J. Kim, “Novel Anti-collision Algorithms for Fast Object Identification in RFID System,” Proc. IEEE ICPADS, 2005. [7] D. Klair, K. Chin, and R. Raad, “On the Energy Consumption of Pure and Slotted Aloha based RFID Anti-Collision Protocols,” Computer Communications, 2008. [8] D. Hush and C. Wood, “Analysis of Tree Algorithm for RFID Arbitration,” Proc. of IEEE ISIT, 1998. [9] J. Myung and W. Lee, “An adaptive memoryless tag anti-collision protocol for RFID networks,” Proc. IEEE ICC, 2005. [10] H. Choi, J. Cha, and J. Kim, “Fast Wireless Anti-collision Algorithm in Ubiquitous ID System,” Proc. IEEE VTC, Sep 2004. [11] V. Namboodiri and L. Gao, “Energy-Aware Tag Anti-Collision Protocols for RFID Systems,” Proc. of IEEE PerCom, 2007. [12] M. Kodialam and T. Nandagopal, “Fast and Reliable Estimation Schemes in RFID Systems,” Proc. of ACM MOBICOM, Los Angeles, 2006. [13] M. Kodialam, T. Nandagopal, and W. Lau, “Anonymous Tracking using RFID tags,” Proc. of IEEE INFOCOM, 2007. [14] C. Qian, H. Ngan, and Y. Liu, “Cardinality Estimation for Large-scale RFID Systems,” Proc. of IEEE PerCom, 2008. [15] S. Chen T. Li and Y. Ling, “Identifying the Missing Tags in a Large RFID System,” Proc. of ACM Mobihoc, 2010. [16] B. Sheng, Q. Li, and W. Mao, “Efficient Continuous Scanning in RFID Systems,” Proc. of IEEE INFOCOM, March 2010. [17] C. Tan, B. Sheng, and Q. Li, “How to Monitor for Missing RFID Tags,” Proc. of IEEE ICDCS, June 2008. [18] S. Chen, M. Zhang, and B. Xiao, “Efficient Information Collection Protocols for Sensor-augmented RFID Networks,” Proc. of IEEE INFOCOM, April 2011. [19] B. Bianchi, L. Fratta, and M. Oliveri, “Performance Evaluation and Enhancement of the CSMA/CA MAC Protocol for 802.11 Wireless LANs,” Personal, Indoor and Mobile Radio Communications, IEEE International Symposium on, vol. 2, pp. 392–396, 1996. [20] H. Han, B. Sheng, Chiu C. Tan, Q. Li, W. Mao, and S. Lu, “Counting RFID Tags Efficiently and Anonymously,” Proc. IEEE INFOCOM, March 2010. [21] T. Li, S. Wu, S. Chen, and M. Yang, “Energy Efficient Algorithms for the RFID Estimation Problem,” Proc. IEEE INFOCOM, March 2010. [22] Philips Semiconductors, “I-CODE Smart Label RFID Tags,” http://www.nxp.com/acrobat download/other/identification/SL092030.pdf, Jan 2004. 2013 Proceedings IEEE INFOCOM 898