each communication round between an RFID reader and tags. The reader transmits an operation code (e.g.,Query,Write, Select,ACK etc.)indicating the expected operation of tags, the backscatter bit rate,and tag encoding schemes (e.g.,FMO or Miller)[2].Figure 4 shows the communication between a reader and a tag in the inventory communication round where the downlink uses pulse interval encoding at 40kHz and uplink uses Miller-4 encoding at 250kHz.The reader initiates the 20000 30000 communication by sending a Query command to the tag. Number of tags Number of tags When receiving a command,each tag responds according to (b)Standard deviation Fis.7.Performance of o with different numbers of estimating rounds. the operation code.As the operation code is Query in this case,the tag transmits a 16-bit random number(RN16)back to the reader and waits for ACK following the EPCglobal C1G2 in concert with the WISP RFID tags,we turn to the large- scale simulations to compare ZOE with the existing cardinality standard [2].Once the reader ACKs the RN16,the tag responds estimation schemes.This is for two reasons.First,partially due with the EPC code as depicted in Figure 4. to the complexity of existing cardinality estimation schemes We implement the ZOE protocol by following the con- ventional reader-initiated approach.We first add the Count (e.g.,FNEB,LoF,and PET),such approaches have not yet been successfully implemented on programmable RFID tags. command into the command set of the standard.To estimate Second,we want to compare the schemes in various complex the tag cardinality,the reader initiates counting procedure by settings,such as error-free and error-prone channel conditions, sending a Count command along with other parameters(0, RB,encoding scheme,etc).In the case that the operation and varying number of tags.Besides,programming,debug- code is Count,the tag computes R(id)=minfiHB(id) ging,and testing a large number of programmable RFID tags still remain challenging. RB][i]=0).If R(id)>0,the tag transmits a short response according to the encoding scheme,and keeps silent otherwise. VI.EVALUATION Figure 5 shows the communication between the reader and the We conduct extensive simulations under various scenarios tag in 4 counting rounds,where the operation code is Count to study the performance of the ZOE protocol.We first with 6=1,varying RB,and the Miller-4 encoding scheme. investigate the estimation accuracy and the corresponding In Figure 5,we can see that two short responses follow the processing cost of ZOE.We then compare ZOE with the first and the third Count commands at around 4ms and 7ms, most recent approaches FNEB,LoF,and PET in terms of the respectively;while no response follows the second and the time efficiency,as well as computation and memory overhead fourth Count commands.One may notice that thethe first at tags.We further investigate the estimation performance of Count command takes slightly longer time than the second different protocols over noisy channels. Count command.The reason is that RFID reader uses the pulse interval encoding scheme,in which bit-1 takes twice of A.Simulation setting and performance metrics the transmission time of bit-0.As the reader generates different We first focus on the ideal communication channel (i.e., RB for each Count command,the transmission time varies no transmission error occurs between RFID tags and RFID slightly across the commands in Figure 5. readers)and the reader is capable of correctly detecting the To send a short response,a tag simply transmits a single responses from tags.After that,we evaluate the robustness and tone (at 250kHz)which allows simple yet robust detection at reliability of the estimation protocols with unreliable channel readers.We first feed the signals into a bandpass filter with conditions.For all simulation instances,we repeat 300 runs center frequency of 250kHz to remove most background noise. and report the average if not explicitly specified otherwise. We use the standard moving window summation(with width The estimation accuracy is one of the most important of 64)to smoothen out any sudden changes due to noises metrics for an estimator.Consistent with existing works,we in the band.If the signal strength exceeds the mean plus use the same accuracy metric as studied in LoF and PET. three standard deviations (i.e..99.7%confidence level),we Accuracy E(f/n), say the channel is busy,and idle otherwise.Figure 6 shows where n denotes the estimation result and n refers to the actual the signal strength around the frequency band of 250kHz and number of tags.This metric evaluates the estimation accuracy moving window summation of the tag response following the and bias.An ideal estimator is expected to return an estimation first Count command approximately between 4.25ms and result close to the actual value.The closer it is to 1.the higher 4.5ms.We observe a big jump of moving window summation during the tag response period(4.25-4.5ms),while the sum is the estimation accuracy is. We use the standard deviation to measure the estimation small and flat when no tag response is transmitted (e.g.,after precision 4.6ms).As shown in Figure 6,when multiple tags respond simultaneously using on-off keying,the aggregated signal VE[(i-n)2], strength still provides valid indications of tag responses with where the operator E[.denotes the average of all runs.A high moving window summation. standard deviation indicates the estimation results spread out, Although ZOE can run in realtime on the USRP N210 whereas a low standard deviation means the estimation resultseach communication round between an RFID reader and tags. The reader transmits an operation code (e.g., Query, Write, Select, ACK etc.) indicating the expected operation of tags, the backscatter bit rate, and tag encoding schemes (e.g., FM0 or Miller) [2]. Figure 4 shows the communication between a reader and a tag in the inventory communication round where the downlink uses pulse interval encoding at 40kHz and uplink uses Miller-4 encoding at 250kHz. The reader initiates the communication by sending a Query command to the tag. When receiving a command, each tag responds according to the operation code. As the operation code is Query in this case, the tag transmits a 16-bit random number (RN16) back to the reader and waits for ACK following the EPCglobal C1G2 standard [2]. Once the reader ACKs the RN16, the tag responds with the EPC code as depicted in Figure 4. We implement the ZOE protocol by following the con￾ventional reader-initiated approach. We first add the Count command into the command set of the standard. To estimate the tag cardinality, the reader initiates counting procedure by sending a Count command along with other parameters (θ, RB, encoding scheme, etc). In the case that the operation code is Count, the tag computes R(id) = min{i|[HB(id) ⊕ RB][i] = 0}. If R(id) ≥ θ, the tag transmits a short response according to the encoding scheme, and keeps silent otherwise. Figure 5 shows the communication between the reader and the tag in 4 counting rounds, where the operation code is Count with θ = 1, varying RB, and the Miller-4 encoding scheme. In Figure 5, we can see that two short responses follow the first and the third Count commands at around 4ms and 7ms, respectively; while no response follows the second and the fourth Count commands. One may notice that the the first Count command takes slightly longer time than the second Count command. The reason is that RFID reader uses the pulse interval encoding scheme, in which bit-1 takes twice of the transmission time of bit-0. As the reader generates different RB for each Count command, the transmission time varies slightly across the commands in Figure 5. To send a short response, a tag simply transmits a single tone (at 250kHz) which allows simple yet robust detection at readers. We first feed the signals into a bandpass filter with center frequency of 250kHz to remove most background noise. We use the standard moving window summation (with width of 64) to smoothen out any sudden changes due to noises in the band. If the signal strength exceeds the mean plus three standard deviations (i.e., 99.7% confidence level), we say the channel is busy, and idle otherwise. Figure 6 shows the signal strength around the frequency band of 250kHz and moving window summation of the tag response following the first Count command approximately between 4.25ms and 4.5ms. We observe a big jump of moving window summation during the tag response period (4.25-4.5ms), while the sum is small and flat when no tag response is transmitted (e.g., after 4.6ms). As shown in Figure 6, when multiple tags respond simultaneously using on-off keying, the aggregated signal strength still provides valid indications of tag responses with moving window summation. Although ZOE can run in realtime on the USRP N210 1 1.1 1.2 850 10000 20000 30000 40000 50000 Accuracy Number of tags 8 rounds 16 rounds 32 rounds 64 rounds (a) Estimation accuracy 102 103 104 Standard deviation (lo 850 10000 20000 30000 40000 50000 g scale) Number of tags 8 rounds 16 rounds 32 rounds 64 rounds (b) Standard deviation Fig. 7. Performance of ZOE with different numbers of estimating rounds. in concert with the WISP RFID tags, we turn to the large￾scale simulations to compare ZOE with the existing cardinality estimation schemes. This is for two reasons. First, partially due to the complexity of existing cardinality estimation schemes (e.g., FNEB, LoF, and PET), such approaches have not yet been successfully implemented on programmable RFID tags. Second, we want to compare the schemes in various complex settings, such as error-free and error-prone channel conditions, and varying number of tags. Besides, programming, debug￾ging, and testing a large number of programmable RFID tags still remain challenging. VI. EVALUATION We conduct extensive simulations under various scenarios to study the performance of the ZOE protocol. We first investigate the estimation accuracy and the corresponding processing cost of ZOE. We then compare ZOE with the most recent approaches FNEB, LoF, and PET in terms of the time efficiency, as well as computation and memory overhead at tags. We further investigate the estimation performance of different protocols over noisy channels. A. Simulation setting and performance metrics We first focus on the ideal communication channel (i.e., no transmission error occurs between RFID tags and RFID readers) and the reader is capable of correctly detecting the responses from tags. After that, we evaluate the robustness and reliability of the estimation protocols with unreliable channel conditions. For all simulation instances, we repeat 300 runs and report the average if not explicitly specified otherwise. The estimation accuracy is one of the most important metrics for an estimator. Consistent with existing works, we use the same accuracy metric as studied in LoF and PET. Accuracy = E(ˆn/n), where nˆ denotes the estimation result and n refers to the actual number of tags. This metric evaluates the estimation accuracy and bias. An ideal estimator is expected to return an estimation result close to the actual value. The closer it is to 1, the higher the estimation accuracy is. We use the standard deviation to measure the estimation precision σ = p E[(ˆn − n) 2], where the operator E[.] denotes the average of all runs. A high standard deviation indicates the estimation results spread out, whereas a low standard deviation means the estimation results