IEEE/ACM TRANSACTIONS ON NETWORKING 2 and the corresponding bits in the acquired BF are verified..TagMap reduces the acquisition overhead by 74.73%and One tag is considered to have been definitely moved out or 66.22%compared with commercial readers (e.g.,ImpinJ missing when a '0'is found;otherwise,it is assumed to be R420)and Tash [43]respectively.TagMap has a mean bit still present,although this assumption may be incorrect with error rate of less than 0.4% a low probability TagMap can accurately find out 97.1+0.4%of missing Yet,RFID-oriented protocols or applications that appeal to events within 2 seconds when 20%of tags are removed, BFs are actually NOT available to today's RFID systems, whereas a commercial reader requires more than 15 seconds because translating the idea of acquiring BFs across RFIDs to know these events. into a practical system faces three major challenges: Key Contributions.This work presents a system that can First,the primary challenge arises from the hardware con- acquire BFs across COTS RFID tags in the physical layer. straint.The core of BF is the on-tag hash functionality, Our design presents three key innovations.First,it emulates which allows each tag to select time slots according to on-tag hash and modulo functionality:second,it intercepts an the hash value of its EPC,making results predicable inventory to test if any tags are hashed into the corresponding exactly knowing which bits a desired tag is mapped into. bit;finally,this work also presents a prototype implementation Current pseudo-random generators of tags cannot meet the and reveals the utility of BFs in typical application scenarios. demand of predictability.One option is to supplement newly designed hash functions to tags [34]-[41].However,they II.MOTIVATION require new hardware (thousands of gate equivalents [42]) for RFID tags,making them significantly more expensive. In this section,we introduce the performance limitations of Second,transmitting and receiving presence signals is non- the current RFID systems firstly,and then present two typical compliant with today's RFID air protocols.These non- application scenarios that show the outperformance of Bloom standard operations would leave out the billions of RFIDs filter for RFID systems.Finally,we point out our advantages over thethe state-of-the-art solutions. already deployed in the today's world,some of which were even installed a decade ago. Third,our prior work named Tash [43]takes a step towards A.Performance Bottleneck in Current RFID Systems designing hash primitives in the application layer,which One of the key performance indicators for the RFID systems might be explored for our purpose.Unfortunately,applica-is the Individual Reading Rate (IRR).which is defined as tions have no control of the physical-layer inventory proce- the number of readings obtained from a particular tag per dure.Thus the application-layer Tash still requires the time- second.IRR highly depends on the efficiency of the anti- consuming anti-collision processing,without unleashing full collision protocol,which is used to avoid signal collisions efficiency potentials of embracing collisions that occur when multiple tags reply their ID simultaneously. In this work,we present TagMap,a practical solution that Today's commercial RFID systems adopt Q-Adaptive protocol, acquires BFs across commercial off-the-shelf (COTS)RFID which adjusts the frame adaptively.Specifically,The reader tags in the physical layer,enabling upper applications to boost divides time into several slots,which are further organized their performance by orders of magnitude.TagMap introduces into frames.As shown in Fig.2,the reader starts an inventory multiple innovations that enable it to deal with the above by broadcasting a select command for choosing a group of challenges.First,TagMap shifts the computation loads for tags to join in the incoming inventory (select all by default). hashing from tag side to the reader side by an emulated hash Then the command Query or QueryAdjust follows to start function.Specifically,it pre-stores the hash values of tags' a new frame,in which each unidentified tag randomly selects EPCs inside their memory banks.When running,it treats a a time slot to reply.The command QueryRep indicates a new portion of the pre-stored hash values as a new hash value. beginning of a slot.During a slot,the tag transmits a 22-bit Second,for each bit of a BF,TagMap reader initiates an short reply (called RN16)firstly for collision detection.Then, intercepted inventory,which forces all tags that are hashed either of the following two cases occurs on the reader side: into this bit to transmit their RN16 replies in the first single RN16 is successfully decoded,which indicates that only one slot.It regards a detected RN16 reply as the presence evidence tag was transmitting (i.e.,singleton slot).The reader then of a tag and skips the remaining anti-collision phase.Third, requests its 128-bit long reply (i.e.,PC EPC+CRC)by TagMap defines the Modulo operation,allowing to acquire issuing an ACK command. arbitrarily sized BFs. Otherwise,the situation indicates either a collision or non- Summary of Results.TagMap offers a new and interesting reply (i.e.,called collision slot and empty slot).In this case, tradeoff point on the spectrum between feasibility and effec- the reader proceeds to the next slot without requesting any tiveness.We implement a prototype of the TagMap reader by long reply.Thus,singleton slots are longer than other slots. using a USRP N210 and 1000 commercial UHF RFID tags In the end of each frame,if any collision slot is detected or any deployed in our office building.Our experiments reveal the long reply is corrupted,then the reader restarts a new frame following findings: using QueryAdjust for these tags.QueryAdjust is able TagMap is compatible with the EPCglobal Gen2 protocol to adjust the frame length based on the number of collisions and can serve 97.5%types of commercial tags in today's in the previous frame.This procedure terminates till all tags market,even some were deployed 13 years ago. are identified.IEEE/ACM TRANSACTIONS ON NETWORKING 2 and the corresponding bits in the acquired BF are verified. One tag is considered to have been definitely moved out or missing when a ‘0’ is found; otherwise, it is assumed to be still present, although this assumption may be incorrect with a low probability. Yet, RFID-oriented protocols or applications that appeal to BFs are actually NOT available to today’s RFID systems, because translating the idea of acquiring BFs across RFIDs into a practical system faces three major challenges: • First, the primary challenge arises from the hardware con￾straint. The core of BF is the on-tag hash functionality, which allows each tag to select time slots according to the hash value of its EPC, making results predicable - exactly knowing which bits a desired tag is mapped into. Current pseudo-random generators of tags cannot meet the demand of predictability. One option is to supplement newly designed hash functions to tags [34]–[41]. However, they require new hardware (thousands of gate equivalents [42]) for RFID tags, making them significantly more expensive. • Second, transmitting and receiving presence signals is non￾compliant with today’s RFID air protocols. These non￾standard operations would leave out the billions of RFIDs already deployed in the today’s world, some of which were even installed a decade ago. • Third, our prior work named Tash [43] takes a step towards designing hash primitives in the application layer, which might be explored for our purpose. Unfortunately, applica￾tions have no control of the physical-layer inventory proce￾dure. Thus the application-layer Tash still requires the time￾consuming anti-collision processing, without unleashing full efficiency potentials of embracing collisions. In this work, we present TagMap, a practical solution that acquires BFs across commercial off-the-shelf (COTS) RFID tags in the physical layer, enabling upper applications to boost their performance by orders of magnitude. TagMap introduces multiple innovations that enable it to deal with the above challenges. First, TagMap shifts the computation loads for hashing from tag side to the reader side by an emulated hash function. Specifically, it pre-stores the hash values of tags’ EPCs inside their memory banks. When running, it treats a portion of the pre-stored hash values as a new hash value. Second, for each bit of a BF, TagMap reader initiates an intercepted inventory, which forces all tags that are hashed into this bit to transmit their RN16 replies in the first single slot. It regards a detected RN16 reply as the presence evidence of a tag and skips the remaining anti-collision phase. Third, TagMap defines the Modulo operation, allowing to acquire arbitrarily sized BFs. Summary of Results. TagMap offers a new and interesting tradeoff point on the spectrum between feasibility and effec￾tiveness. We implement a prototype of the TagMap reader by using a USRP N210 and 1000 commercial UHF RFID tags deployed in our office building. Our experiments reveal the following findings: • TagMap is compatible with the EPCglobal Gen2 protocol and can serve 97.5% types of commercial tags in today’s market, even some were deployed 13 years ago. • TagMap reduces the acquisition overhead by 74.73% and 66.22% compared with commercial readers (e.g., ImpinJ R420) and Tash [43] respectively. TagMap has a mean bit error rate of less than 0.4%. • TagMap can accurately find out 97.1 ± 0.4% of missing events within 2 seconds when 20% of tags are removed, whereas a commercial reader requires more than 15 seconds to know these events. Key Contributions. This work presents a system that can acquire BFs across COTS RFID tags in the physical layer. Our design presents three key innovations. First, it emulates on-tag hash and modulo functionality; second, it intercepts an inventory to test if any tags are hashed into the corresponding bit; finally, this work also presents a prototype implementation and reveals the utility of BFs in typical application scenarios. II. MOTIVATION In this section, we introduce the performance limitations of the current RFID systems firstly, and then present two typical application scenarios that show the outperformance of Bloom filter for RFID systems. Finally, we point out our advantages over the the state-of-the-art solutions. A. Performance Bottleneck in Current RFID Systems One of the key performance indicators for the RFID systems is the Individual Reading Rate (IRR), which is defined as the number of readings obtained from a particular tag per second. IRR highly depends on the efficiency of the anti￾collision protocol, which is used to avoid signal collisions that occur when multiple tags reply their ID simultaneously. Today’s commercial RFID systems adopt Q-Adaptive protocol, which adjusts the frame adaptively. Specifically, The reader divides time into several slots, which are further organized into frames. As shown in Fig. 2, the reader starts an inventory by broadcasting a Select command for choosing a group of tags to join in the incoming inventory (select all by default). Then the command Query or QueryAdjust follows to start a new frame, in which each unidentified tag randomly selects a time slot to reply. The command QueryRep indicates a new beginning of a slot. During a slot, the tag transmits a 22-bit short reply (called RN16) firstly for collision detection. Then, either of the following two cases occurs on the reader side: • RN16 is successfully decoded, which indicates that only one tag was transmitting (i.e., singleton slot). The reader then requests its 128-bit long reply (i.e., PC + EPC+ CRC) by issuing an ACK command. • Otherwise, the situation indicates either a collision or non￾reply (i.e., called collision slot and empty slot). In this case, the reader proceeds to the next slot without requesting any long reply. Thus, singleton slots are longer than other slots. In the end of each frame, if any collision slot is detected or any long reply is corrupted, then the reader restarts a new frame using QueryAdjust for these tags. QueryAdjust is able to adjust the frame length based on the number of collisions in the previous frame. This procedure terminates till all tags are identified