XIE ET AL.:EFFICIENT PROTOCOLS FOR COLLECTING HISTOGRAMS IN LARGE-SCALE RFID SYSTEMS 2423 TABLE 1 inter-cyde duration The Average Time Interval for Various Slots after QueryRep command after Query command empty slot 0.9ms 1.7ms singleton slot 4.1ms 5.1ms collision slot 1.3ms 2.2ms specified set of tags,conventionally,the reader should issue 100 200 60 multiple query cycles over the same set of tags and take the (a)The raw signal data for 5 continuous cycles average of the estimates.The inter-cycle overhead consists of the time between cycles when the reader is powered down,and the carrier time used to power the tags before beginning communication.According to the experiment results in [30],which are conducted in realistic settings, these times are 40 ms and 3 ms respectively,while the aver- age time interval per slot is 1~2 ms. We have further measured the time interval for various slots and the inter-cycle duration with the USRP N210 plat- form.In our experiments,we use the Alien-9900 reader and Alien-9611 linear antenna with a directional gain of 6 dB. The The RFID tags used are Alien 9640 general-purpose tags (b)The raw signal data for one frame which support the EPC C1G2 standards.We use Alien Fig.2.The captured raw signal data of the interrogation between the reader to continuously read 13 tags for 100 query cycles.We reader and the tag use USRP N210 as a sniffer to capture the physical signals. Fig.2 shows an example of the captured raw signal data of Query Cycle.Note that,within each frame,tags may choose the interrogation between the reader and the tag.According the same slot,which causes multiple tags to reply during a to the realistic experiment results in this setting,the average slot.Therefore,within each frame there exist three kinds of intervals for various slots are summarized in Table 1.It is slots:(1)the empty slot where no tag replies;(2)the single found that,in most cases,the slot is started with a QueryRep slot where only one tag replies;and (3)the collision slot command,then the average interval for empty slots is where multiple tags reply. 0.9 ms per slot,the average interval for singleton slots is 4.1 In regard to the tag ID,each tag has a unique 96-bit ID in ms per slot,and the average interval for collision slots is 1.3 its EPC memory,where the first s binary bits can be ms per slot;when a slot happens to be the first slot of a regarded as the category ID(1<s<96).According to the frame,the slot is started with a Query command,then the C1G2 standard,for each Query Cycle,the reader is able to average interval for empty slots is 1.7 ms per slot,the aver- select the tags in a specified category by sending a Select age interval for singleton is 5.1 ms per slot,and the average command with an s-bit mask in the category ID field.If mul- interval for collision slots is 2.2 ms per slot.By measuring tiple categories need to be selected,the reader can provide the time intervals between two adjacent query cycles,it is multiple bit masks in the Select command. found that the average interval for inter-cycle duration is 28.3 ms.Note that if the powered-down interval is not long 3.2 Basic Tag Identification versus enough,it is possible that some surrounding tags will main- the Estimation Scheme tain the former state for the inventoried flag with their local Assume that there are n tags in total,and that it takes s;slots residual power,which causes them to keep silent in the to uniquely identify n tags.It is known that for each query upcoming query cycle. round,when the frame size f is equal to the remaining Therefore,since the average inter-cycle duration(28.3 ms) number of tags,the proportion of singleton slots inside the is much larger than the average time interval of conventional frame is maximized;then,the efficiency is"=.Hence,the slots (empty slot:0.9 ms,singleton slot:4.1 ms,collision slot: essential number of slots is s(1).n=n.e. 1.3 ms),the inter-cycle duration must be taken into account when considering overall reading performance.It is obvious Therefore,assume that it takes se slots to estimate the tag that reading a large number of tags per cycle amortizes the size for each category with a certain accuracy.If we want cost of inter-cycle overhead,resulting in lower per tag read- the estimation scheme to achieve a better reading perfor- ing time,while for small tag sets the inter-cycle overhead is mance than the basic tag identification method,then we significant.It is essential to sufficiently reduce the inter-cycle need se.lesili,where le and li are the sizes of the bit overhead when we design a solution and set the correspond- strings transmitted during the estimation and identification ing parameters for RFID systems. phases,respectively. 3.3 The Impact of the Inter-Cycle Overhead 4 PROBLEM FORMULATION The MAC protocol for the C1G2 system is based on slotted Suppose there are a large number of tags in the effective ALOHA.In order to accurately estimate the size of a scanning area of the RFID reader,the RFID system conformsQuery Cycle. Note that, within each frame, tags may choose the same slot, which causes multiple tags to reply during a slot. Therefore, within each frame there exist three kinds of slots: (1) the empty slot where no tag replies; (2) the single slot where only one tag replies; and (3) the collision slot where multiple tags reply. In regard to the tag ID, each tag has a unique 96-bit ID in its EPC memory, where the first s binary bits can be regarded as the category ID (1 <s< 96). According to the C1G2 standard, for each Query Cycle, the reader is able to select the tags in a specified category by sending a Select command with an s-bit mask in the category ID field. If mul￾tiple categories need to be selected, the reader can provide multiple bit masks in the Select command. 3.2 Basic Tag Identification versus the Estimation Scheme Assume that there are n tags in total, and that it takes si slots to uniquely identify n tags. It is known that for each query round, when the frame size f is equal to the remaining number of tags, the proportion of singleton slots inside the frame is maximized; then, the efficiency is ns f ¼ 1 e . Hence, the essential number of slots is si ¼ Pþ1 i¼0 ð1 1 e Þ i  n ¼ n  e. Therefore, assume that it takes se slots to estimate the tag size for each category with a certain accuracy. If we want the estimation scheme to achieve a better reading perfor￾mance than the basic tag identification method, then we need se  le  si  li, where le and li are the sizes of the bit strings transmitted during the estimation and identification phases, respectively. 3.3 The Impact of the Inter-Cycle Overhead The MAC protocol for the C1G2 system is based on slotted ALOHA. In order to accurately estimate the size of a specified set of tags, conventionally, the reader should issue multiple query cycles over the same set of tags and take the average of the estimates. The inter-cycle overhead consists of the time between cycles when the reader is powered down, and the carrier time used to power the tags before beginning communication. According to the experiment results in [30], which are conducted in realistic settings, these times are 40 ms and 3 ms respectively, while the aver￾age time interval per slot is 1  2 ms. We have further measured the time interval for various slots and the inter-cycle duration with the USRP N210 plat￾form. In our experiments, we use the Alien-9900 reader and Alien-9611 linear antenna with a directional gain of 6 dB. The RFID tags used are Alien 9640 general-purpose tags which support the EPC C1G2 standards. We use Alien reader to continuously read 13 tags for 100 query cycles. We use USRP N210 as a sniffer to capture the physical signals. Fig. 2 shows an example of the captured raw signal data of the interrogation between the reader and the tag. According to the realistic experiment results in this setting, the average intervals for various slots are summarized in Table 1. It is found that, in most cases, the slot is started with a QueryRep command, then the average interval for empty slots is 0.9 ms per slot, the average interval for singleton slots is 4.1 ms per slot, and the average interval for collision slots is 1.3 ms per slot; when a slot happens to be the first slot of a frame, the slot is started with a Query command, then the average interval for empty slots is 1.7 ms per slot, the aver￾age interval for singleton is 5.1 ms per slot, and the average interval for collision slots is 2.2 ms per slot. By measuring the time intervals between two adjacent query cycles, it is found that the average interval for inter-cycle duration is 28.3 ms. Note that if the powered-down interval is not long enough, it is possible that some surrounding tags will main￾tain the former state for the inventoried flag with their local residual power, which causes them to keep silent in the upcoming query cycle. Therefore, since the average inter-cycle duration (28.3 ms) is much larger than the average time interval of conventional slots (empty slot: 0.9 ms, singleton slot: 4.1 ms, collision slot: 1.3 ms), the inter-cycle duration must be taken into account when considering overall reading performance. It is obvious that reading a large number of tags per cycle amortizes the cost of inter-cycle overhead, resulting in lower per tag read￾ing time, while for small tag sets the inter-cycle overhead is significant. It is essential to sufficiently reduce the inter-cycle overhead when we design a solution and set the correspond￾ing parameters for RFID systems. 4 PROBLEM FORMULATION Suppose there are a large number of tags in the effective scanning area of the RFID reader, the RFID system conforms Fig. 2. The captured raw signal data of the interrogation between the reader and the tag TABLE 1 The Average Time Interval for Various Slots after QueryRep command after Query command empty slot 0.9 ms 1.7 ms singleton slot 4.1 ms 5.1 ms collision slot 1.3 ms 2.2 ms XIE ET AL.: EFFICIENT PROTOCOLS FOR COLLECTING HISTOGRAMS IN LARGE-SCALE RFID SYSTEMS 2423