Query RN16 ACK EPC a号 Fig.3.Testbed:2 circular antennas are mounted to the USRP N210 software 4 10 defined radio.The USRP N210 is connected via GigE to a laptop which acts Time(ms) as an RFID reader.The reader interrogates WISP RFID tags. Fig.4. The communication between reader and tag in the inventory communication.The Query command is sent by the reader at around 4ms We assume that the error rate is time-invariant during the followed by the reply of RN16 from a tag.The ACK is sent at around 6ms short period of estimation process.We consider the false followed by the EPC code from the tag.The QueryRepeat is sent to query other tags. negative rate and false positive rate are both g for simplicity (i.e.,the chances of missing a tag response and triggering a 0.4 0.35 false detection are equally likely).One may easily extend it to the cases of asymmetric false positive/negative rates.We propose Error Estimation and Adjustment(EEA)algorithm to 0.15 0.1 adjust the estimation results according to error rates. 0.05 We denote by XEor the average value of m independent 6 10 observations with the error rate q.Then we have Time(ms) E(XEmor)=E(X-q(2X-1)) (7) Fig.5.The communication between reader and tag in the ZOE protocol. The first Count command is sent at around 4ms followed by a busy slot. According to (7),we compute E(X)with g as follows, The second Count command is followed by an empty slot. E()= E(XError)-q 1-2q We extend(3)and estimate the tag cardinality as follows, -2ne22} 011 (8) From (8).we find that the ideal channel condition is the 4.3 4.4 4.5 46 47 4.8 special case where g=0.When g=0.5,the communication Time(ms) Fig.6.The tag response detection using moving window summation of becomes totally random,i.e..the channel noise completely signal strength.When multiple tags respond simultaneously,the aggregated overwhelms the measurement.Nevertheless,we can success- signal strength increases fully compensate the communication error,if 0<g<0.5. 2)Reducing the overhead at RFID tags:In the basic only provide limited interfaces to developers.The combination algorithm,each tag needs to generate a random number at of the USRP and the WISP platform provides us full pro- each estimation round.Generating random numbers,however, grammability to both RFID reader and tags.We implement requires a fair amount of computation at the RFID tags. the ZOE reader using USRP N210 based on the GNURa- Existing approaches propose to preload random numbers into dio platform and the Gen2 RFID projects [3]to interrogate tags,which requires extra memory.At resource-constrained WISP RFID tags.The ZOE reader uses the USRP RFX900 RFID tags,either method in providing the randomness is far daughterboard which operates in the 900MHz band [4].We from satisfactory.Instead of using new random numbers at connect the daughterboard to Alien ALR-8696-C circular different estimating rounds,a 32-bit random number is stored polarized antennas with the antenna gain of 8.5dBic [1].The at each RFID tag during tag manufacturing and used for all typical power output of RFX900 daughterboard is only 23dBm estimation rounds.Many off-the-shelf methods are available (200mW).far less than 30dBm (1W)of commercial RFID reader.We connect the USRP N210 via Gigabit Ethernet to for manufacturers to preload the random numbers to tags [27].The backend server generates a uniformly distributed a laptop equipped with a qual-core 2.67GHz processor and random number at each estimation round and broadcasts it 2.9GB memory running Ubuntu 10.10.Figure 3 shows the to RFID tags.We denote the random number in the binary testbed. form as RB.Receiving the random number,each tag computes We implement the ZOE tag using the programmable WISP R(id)=mintiHB(id)RB][i]=0},where denotes tags based on the WISP4.1 hardware and firmware.The WISP the bitwise XOR operation,and participates in the estimation tag mainly consists of an RFID circuitry and an ultra-low round with R(id).Such a method only requires the tags power 16-bit MSP430 microcontroller.The RFID circuitry is to perform a lightweight bitwise XOR function.By this used to harvest power and backscatter radio signals.Current modification,we may expect nearly independent trials,and WISP firmware has partially implemented the EPCglobal the above analysis of the ZOE protocol still holds. C1G2 protocol [2.5].We extend the EPCglobal C1G2 protocol with the functionality of ZOE cardinality estimation.The V.IMPLEMENTATION implementation of the ZOE protocol only requires a slight We implement a prototype system to validate ZOE using extension to the EPCglobal C1G2 protocol. USRP SDR and WISP tags.Commercial RFID manufacturers In EPCglobal C1G2 standard [2].the RFID reader initiatesFig. 3. Testbed: 2 circular antennas are mounted to the USRP N210 software defined radio. The USRP N210 is connected via GigE to a laptop which acts as an RFID reader. The reader interrogates WISP RFID tags. We assume that the error rate is time-invariant during the short period of estimation process. We consider the false negative rate and false positive rate are both q for simplicity (i.e., the chances of missing a tag response and triggering a false detection are equally likely). One may easily extend it to the cases of asymmetric false positive/negative rates. We propose Error Estimation and Adjustment (EEA) algorithm to adjust the estimation results according to error rates. We denote by X¯ Error the average value of m independent observations with the error rate q. Then we have E(X¯ Error) = E(X¯ − q(2X¯ − 1)). (7) According to (7), we compute E(X¯) with q as follows, E(X¯) = E(X¯ Error) − q 1 − 2q . We extend (3) and estimate the tag cardinality as follows, nˆError = −2 θ ln(X¯ Error − q 1 − 2q ). (8) From (8), we find that the ideal channel condition is the special case where q = 0. When q = 0.5, the communication becomes totally random, i.e., the channel noise completely overwhelms the measurement. Nevertheless, we can success￾fully compensate the communication error, if 0 < q < 0.5. 2) Reducing the overhead at RFID tags: In the basic algorithm, each tag needs to generate a random number at each estimation round. Generating random numbers, however, requires a fair amount of computation at the RFID tags. Existing approaches propose to preload random numbers into tags, which requires extra memory. At resource-constrained RFID tags, either method in providing the randomness is far from satisfactory. Instead of using new random numbers at different estimating rounds, a 32-bit random number is stored at each RFID tag during tag manufacturing and used for all estimation rounds. Many off-the-shelf methods are available for manufacturers to preload the random numbers to tags [27]. The backend server generates a uniformly distributed random number at each estimation round and broadcasts it to RFID tags. We denote the random number in the binary form as RB. Receiving the random number, each tag computes R(id) = min{i|[HB(id) ⊕ RB][i] = 0}, where ⊕ denotes the bitwise XOR operation, and participates in the estimation round with R(id). Such a method only requires the tags to perform a lightweight bitwise XOR function. By this modification, we may expect nearly independent trials, and the above analysis of the ZOE protocol still holds. V. IMPLEMENTATION We implement a prototype system to validate ZOE using USRP SDR and WISP tags. Commercial RFID manufacturers 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0 2 4 6 8 10 Magnitude Time(ms) Query RN16 ACK EPC QueryRepeat Fig. 4. The communication between reader and tag in the inventory communication. The Query command is sent by the reader at around 4ms followed by the reply of RN16 from a tag. The ACK is sent at around 6ms followed by the EPC code from the tag. The QueryRepeat is sent to query other tags. 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0 2 4 6 8 10 Magnitude Time(ms) Busy slots Idle slots Fig. 5. The communication between reader and tag in the ZOE protocol. The first Count command is sent at around 4ms followed by a busy slot. The second Count command is followed by an empty slot. 0.004 0.012 0.02 0.028 4.2 4.3 4.4 4.5 4.6 4.7 4.8 Signal strength Time(ms) Single strength ( 1 tag ) Window sum ( 1 tag ) Window sum (2 tags) Window sum (4 tags) Fig. 6. The tag response detection using moving window summation of signal strength. When multiple tags respond simultaneously, the aggregated signal strength increases. only provide limited interfaces to developers. The combination of the USRP and the WISP platform provides us full pro￾grammability to both RFID reader and tags. We implement the ZOE reader using USRP N210 based on the GNURa￾dio platform and the Gen2 RFID projects [3] to interrogate WISP RFID tags. The ZOE reader uses the USRP RFX900 daughterboard which operates in the 900MHz band [4]. We connect the daughterboard to Alien ALR-8696-C circular polarized antennas with the antenna gain of 8.5dBic [1]. The typical power output of RFX900 daughterboard is only 23dBm (200mW), far less than 30dBm (1W) of commercial RFID reader. We connect the USRP N210 via Gigabit Ethernet to a laptop equipped with a qual-core 2.67GHz processor and 2.9GB memory running Ubuntu 10.10. Figure 3 shows the testbed. We implement the ZOE tag using the programmable WISP tags based on the WISP4.1 hardware and firmware. The WISP tag mainly consists of an RFID circuitry and an ultra-low power 16-bit MSP430 microcontroller. The RFID circuitry is used to harvest power and backscatter radio signals. Current WISP firmware has partially implemented the EPCglobal C1G2 protocol [2, 5]. We extend the EPCglobal C1G2 protocol with the functionality of ZOE cardinality estimation. The implementation of the ZOE protocol only requires a slight extension to the EPCglobal C1G2 protocol. In EPCglobal C1G2 standard [2], the RFID reader initiates