计算机科学与技术（参考文献）Acquiring Bloom Filters across Commercial RFIDs in Physical Layer

IEEE/ACM TRANSACTIONS ON NETWORKING Acquiring Bloom Filters across Commercial RFIDs in Physical Layer Zhenlin An,Student Member,IEEE,Qiongzheng Lin,Member.IEEE Lei Yang,Member.IEEE, Wei Lou,Member,IEEE and Lei Xie,Member;IEEE Abstract-Embedding Radio-Frequency IDentification (RFID) into everyday objects to construct ubiquitous networks has been hs(t1) 2(t2)ha(t2 h2(t2) a long-standing goal.However,a major problem that hinders the attainment of this goal is the current inefficient reading of RFID 10110100 tags.To address the issue,the research community introduces 5 6789101112 the technique of Bloom Filter (BF)to RFID systems.This work (a)Acquisition of a Bloom filter presents 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.The key idea is to treat all tags as if they were a single virtual sender,which hashes each tag into different Acquired BF: 010010 010 10 intercepted inventories.Our approach does not require hardware 123456789101112 nor firmware changes in commodity RFID tags allows for rapid,zero-cost deployment in existing RFID tags.We design and (b)Presence test with an acquired BF implement TagMap reader with commodity device (e.g.,USRP N210)platforms.Our comprehensive evaluation reveals that the Fig.1:Acquisition of a Bloom filter in an RFID system.(a) overhead of TagMap is 66.22%lower than the state-of-the-art Initially,the M-bit BF bitmap begins as an array of zeros.The reader solution,with a bit error rate of 0.4%. divides the acquisition procedure into M time slots corresponding to the M bits.Each tag in the set T=ft1,t2,...,tn}is hashed K Index Terms-RFID;Bloom Filter;Physical layer times using the hash functions of (h,h2,...,hk}into K slots, in each of which the tag yields a short presence signal to show its presence.The reader sets a bit to 1 if any signal is detected in the I.INTRODUCTION corresponding slot.(b)To check if a tag is present,hash it K times and check the corresponding bits in the acquired BF.For example. Today's largest and fastest growing market of the Internet the t2 cannot be on the spot,since a'0'is found at one of the bits; of Things(IoT)by unit sale comes from the Radio Frequency a new tag (e.g.,n+1)must arrive since unwanted '1'is found. IDentification (RFIDs)[1].In RFID systems,a device called the reader transmits a continuous high-power RF signal. Nearby tags can modulate the reader's signal by changing communication mechanisms (e.g.,CDMA or FDMA [14], the impedance match state of antenna to convey a message [15))are unsuitable due to their high energy demand.Worsely. of zeros and ones back to the reader.Such communication tags merely rely on the reader to schedule their medium access allows tags to work without batteries;they operate solely by with the framed-slotted ALOHA protocol because they cannot harvesting the energy from reader's RF signal [2]. "hear"from each other.These limitations force the reader to A fundamental operation in RFID systems is to scan and go through a time-consuming inventory procedure. read 96-bit or 128-bit Electronic Product Codes (EPCs,aka To address the issue,the research community introduces the ID)from tags,wherein time efficiency is a crucial performance metric,especially when dealing with large volumes of RFID technique of Bloom Filter (BF)to RFID systems [16]-[33]. tags.Many RFID-based applications like sensing [3]and Unlike previous anti-collision protocols that avoid collisions, these works embrace collisions as informative feedbacks.A localization [4]also highly rely on reading rates.The challenge is that tags can collide and cancel each other out,resulting Bloom filter is a space-(or time-)efficient probabilistic data structure that is used to represent a set.It can tell whether in wastage of bandwidth and an increase in the total delay. an element is a member of the set that it represents.Fig.I Many existing work made efforts to design more efficient anti-collision inventory protocols [5]-[13].However,the lack demonstrates how the reader acquires a BF across tags and how the acquired BF is utilized to test the presence of a tag. of traditional transceivers [2]prevents tags from utilizing a suitable channel to transmit additional bits per symbol The upper layer can employ the acquired BF to explore many and increasing the bandwidth efficiency.Other sophisticated notable applications.For example,consider a warehouse that stores a large number of high-valued commercial products Lei Yang and Lei Xie are the co-corresponding authors.Zhenlin An, or a military base that stocks a large number of guns and Qiongzheng Lin,Lei Yang and Wei Lou are with the Department of Comput- ammunition packages [16].How can a staff immediately ing,The Hong Kong Polytechnic University,Hong Kong SAR,China,e-mail: determine if anything is missing?The BF naturally fits the an,young,lin@tagsys.org,csweilou@comp.polyu.edu.hk.Lei Xie is with the State Key Laboratory for Novel Software Technology,Nanjing University demand of this application because it is an exact representation e-mail:Ixie@nju.edu.cn. of the current tag set.Specifically,all tags are hashed K times

IEEE/ACM TRANSACTIONS ON NETWORKING 1 Acquiring Bloom Filters across Commercial RFIDs in Physical Layer Zhenlin An, Student Member, IEEE, Qiongzheng Lin, Member, IEEE Lei Yang, Member, IEEE, Wei Lou, Member, IEEE and Lei Xie, Member, IEEE Abstract—Embedding Radio-Frequency IDentification (RFID) into everyday objects to construct ubiquitous networks has been a long-standing goal. However, a major problem that hinders the attainment of this goal is the current inefficient reading of RFID tags. To address the issue, the research community introduces the technique of Bloom Filter (BF) to RFID systems. This work presents 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. The key idea is to treat all tags as if they were a single virtual sender, which hashes each tag into different intercepted inventories. Our approach does not require hardware nor firmware changes in commodity RFID tags - allows for rapid, zero-cost deployment in existing RFID tags. We design and implement TagMap reader with commodity device (e.g., USRP N210) platforms. Our comprehensive evaluation reveals that the overhead of TagMap is 66.22% lower than the state-of-the-art solution, with a bit error rate of 0.4%. Index Terms—RFID; Bloom Filter; Physical layer I. INTRODUCTION Today’s largest and fastest growing market of the Internet of Things (IoT) by unit sale comes from the Radio Frequency IDentification (RFIDs) [1]. In RFID systems, a device called the reader transmits a continuous high-power RF signal. Nearby tags can modulate the reader’s signal by changing the impedance match state of antenna to convey a message of zeros and ones back to the reader. Such communication allows tags to work without batteries; they operate solely by harvesting the energy from reader’s RF signal [2]. A fundamental operation in RFID systems is to scan and read 96-bit or 128-bit Electronic Product Codes (EPCs, aka ID) from tags, wherein time efficiency is a crucial performance metric, especially when dealing with large volumes of RFID tags. Many RFID-based applications like sensing [3] and localization [4] also highly rely on reading rates. The challenge is that tags can collide and cancel each other out, resulting in wastage of bandwidth and an increase in the total delay. Many existing work made efforts to design more efficient anti-collision inventory protocols [5]–[13]. However, the lack of traditional transceivers [2] prevents tags from utilizing a suitable channel to transmit additional bits per symbol and increasing the bandwidth efficiency. Other sophisticated Lei Yang and Lei Xie are the co-corresponding authors. Zhenlin An, Qiongzheng Lin, Lei Yang and Wei Lou are with the Department of Comput￾ing, The Hong Kong Polytechnic University, Hong Kong SAR, China, e-mail: {an, young, lin}@tagsys.org, csweilou@comp.polyu.edu.hk. Lei Xie is with the State Key Laboratory for Novel Software Technology, Nanjing University, e-mail: lxie@nju.edu.cn. 0 1 0 0 1 0 1 1 0 1 0 0 t1 t2 ······ 1 2 3 4 5 6 7 8 9 10 11 12 Reader h1(t1) h2(t1) h3(t1) h2(t2) h2(t2) h3(t2) (a) Acquisition of a Bloom filter 0 1 0 0 1 0 0 1 0 1 0 1 t1 t2 ······ tn+1 1 2 3 4 5 6 7 8 9 10 11 12 Acquired BF: (b) Presence test with an acquired BF Fig. 1: Acquisition of a Bloom filter in an RFID system. (a) Initially, the M-bit BF bitmap begins as an array of zeros. The reader divides the acquisition procedure into M time slots corresponding to the M bits. Each tag in the set T = {t1, t2, . . . , tn} is hashed K times using the hash functions of {h1, h2, . . . , hK} into K slots, in each of which the tag yields a short presence signal to show its presence. The reader sets a bit to 1 if any signal is detected in the corresponding slot. (b) To check if a tag is present, hash it K times and check the corresponding bits in the acquired BF. For example, the t2 cannot be on the spot, since a ‘0’ is found at one of the bits; a new tag (e.g., tn+1) must arrive since unwanted ‘1’ is found. communication mechanisms (e.g., CDMA or FDMA [14], [15]) are unsuitable due to their high energy demand. Worsely, tags merely rely on the reader to schedule their medium access with the framed-slotted ALOHA protocol because they cannot “hear” from each other. These limitations force the reader to go through a time-consuming inventory procedure. To address the issue, the research community introduces the technique of Bloom Filter (BF) to RFID systems [16]–[33]. Unlike previous anti-collision protocols that avoid collisions, these works embrace collisions as informative feedbacks. A Bloom filter is a space- (or time-) efficient probabilistic data structure that is used to represent a set. It can tell whether an element is a member of the set that it represents. Fig. 1 demonstrates how the reader acquires a BF across tags and how the acquired BF is utilized to test the presence of a tag. The upper layer can employ the acquired BF to explore many notable applications. For example, consider a warehouse that stores a large number of high-valued commercial products or a military base that stocks a large number of guns and ammunition packages [16]. How can a staff immediately determine if anything is missing? The BF naturally fits the demand of this application because it is an exact representation of the current tag set. Specifically, all tags are hashed K times

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

IEEE/ACM TRANSACTIONS ON NETWORKING Reader Tag 1 PCEPC+CRC Tag 2 RN16 RN16 PC+EPC+CRC Singleton slot Collide slot Empty slot Singleton slot Fig.2:Gen2 inventory procedure.The reader starts an inventory procedure with a Select command,which selects a group of tags to join.Each inventory is composed of many frames,which are initiated by either a Query or QueryAdjust command.Further,the reader divides a frame into many time slots with QueryRep.Tags (e.g.,tag 1 and tag 2)randomly selects a time slot to reply.In particular,a short reply called RN16 must be transmitted for collision avoidance before the transmission of a long reply. 0=2 tags'EPCs to maintain a fresh record.With the help of BFs, we can design an incremental scanning algorithm.Initially, the reader collects all tags'EPCs.In the following inventory rounds,the reader quickly acquires a BF from these tags only. With the BF,we can check if all the bits that a known tag is hashed into in the acquired BF are set to'1'-a negative result implies that the test tag is gone (or missing);or check if new 'I's emerge-a positive result implies the presence of one or Number of Tags more new tags.Then,we can dynamically adjust the tag set Fig.3:Individual reading rate.The reading rate decreases as the by removing left tags and/or adding new tags.Note that the number of tags increases rapidly. new tags can be selectively read as shown in [45]. BF-Aware Missing Detection.We consider a warehouse Empirical Study.In our prior work [44],we practically that stores a large number of high-valued commercial products measure the reading rates of the ImpinJ R420 reader across or a military base that stocks a large number of guns and 1~40 Alien tags,with various frequencies (920~926MHz), ammunition packages [16].We assume that each object is including 16 channels.We try 7 settings of Q in the ex- attached with an RFID tag.To detect missing objects that may periments where Q is the length of the first frame.For have been stolen from the warehouse in a timely manner,an each setting,we repeat the experiment 50 times and report RFID reader must periodically scan all of the present RFID the average value.The Fig.3 shows the results.For the tags to maintain a fresh record.It is reasonable to assume sake of comparison,we also presents the theoretical rate of all EPCs are known ahead of time;otherwise,we cannot tell optimized ALOHA protocol.Clearly,we wish each tag can which tag is missing.BF naturally fits such needs because it is be scanned as many times as possible per second.The study an exact representation of the current tag set [19]-[33],[43]. suggests that the reading rate rapidly decreases by 80%above We can check if all the bits that a test tag is hashed into in when the number of tags is more than 30,compared with the acquired BF are set to 1.A negative result implies that the the single-tag scenario.This finding shows that the channel test tag is missing. competitions among tags seriously and significantly degrades Utilizing BF is time-efficient for two main aspects at least. the time efficiency in practice.Meanwhile,we would observe First,collisions are now allowable and informative,which that the current anti-collision algorithm,i.e.,Q-adaptive,is imply the presence of the corresponding hashed tags.This re- already a good algorithm approaching the optimal solution. moves the time-consuming process of dealing with collisions. Thus,current system leaves very limited space to improve the Second,each tag only requires to transmit a few bits (e.g., efficiency by designing better anti-collision protocols under 16-bit RN16 in our design)to show its presence instead of a the rigorous hardware constraint.This is mainly because the whole 144-bit long reply,saving transmission time by orders tag is battery-free and powerless to support sophisticated anti- of magnitude for each time slot. collision algorithms. C.Comparison with our Prior Work B.BF-Aware Application Scenario Why and how would the BF boost the performance of an This work enhances our prior design [43],which emulates RFID system?To further derive our design,we show two a group of hash primitives in the application layer.However, our solution is more efficient and practical prior to [43]at typical usage scenarios of BF as follows. least in two aspects. BF-Aware Continuous Scanning.We use the asset man- agement as a typical example,which requires an RFID reader Practicality:As an application-layer emulation technique, to periodically and continuously scan all of the present RFID Tash highly depends on a Gen2 command,i.e.,Truncate, which forces tags to transmit truncated EPCs.These in- IThis figure is from our prior work [44]. complete EPCs are viewed as the presence evidence of

IEEE/ACM TRANSACTIONS ON NETWORKING 3 Reader Select Query RN16 ACK PC+EPC+CRC QueryRep RN16 Tag 1 1st slot (Collision) 2nd slot (Empty reply) 1st slot (Successful reply) 1st frame Tag 2 RN16 PC+EPC+CRC 2nd slot (Successful reply) QueryAdjust QueryRep 2nd frame Filtering ACK RN16 Collide slot Empty slot Singleton slot Singleton slot Fig. 2: Gen2 inventory procedure. The reader starts an inventory procedure with a Select command, which selects a group of tags to join. Each inventory is composed of many frames, which are initiated by either a Query or QueryAdjust command. Further, the reader divides a frame into many time slots with QueryRep. Tags (e.g., tag 1 and tag 2) randomly selects a time slot to reply. In particular, a short reply called RN16 must be transmitted for collision avoidance before the transmission of a long reply. 0 5 10 15 20 25 30 35 40 Number of Tags(#) 10 15 20 25 30 35 40 45 50 55 Reading Rate(Hz) Theory Q=0 Q=1 Q=2 Q=3 Q=4 Q=5 Q=0 Q=1 Q=5 Q=2 Q=4 Q=3 Theory 84% drop Fig. 3: Individual reading rate. The reading rate decreases as the number of tags increases rapidly.1 Empirical Study. In our prior work [44], we practically measure the reading rates of the ImpinJ R420 reader across 1 ∼ 40 Alien tags, with various frequencies (920 ∼ 926MHz), including 16 channels. We try 7 settings of Q in the ex￾periments where Q is the length of the first frame. For each setting, we repeat the experiment 50 times and report the average value. The Fig. 3 shows the results. For the sake of comparison, we also presents the theoretical rate of optimized ALOHA protocol. Clearly, we wish each tag can be scanned as many times as possible per second. The study suggests that the reading rate rapidly decreases by 80% above when the number of tags is more than 30, compared with the single-tag scenario. This finding shows that the channel competitions among tags seriously and significantly degrades the time efficiency in practice. Meanwhile, we would observe that the current anti-collision algorithm, i.e., Q-adaptive, is already a good algorithm approaching the optimal solution. Thus, current system leaves very limited space to improve the efficiency by designing better anti-collision protocols under the rigorous hardware constraint. This is mainly because the tag is battery-free and powerless to support sophisticated anti￾collision algorithms. B. BF-Aware Application Scenario Why and how would the BF boost the performance of an RFID system? To further derive our design, we show two typical usage scenarios of BF as follows. BF-Aware Continuous Scanning. We use the asset man￾agement as a typical example, which requires an RFID reader to periodically and continuously scan all of the present RFID 1This figure is from our prior work [44]. tags’ EPCs to maintain a fresh record. With the help of BFs, we can design an incremental scanning algorithm. Initially, the reader collects all tags’ EPCs. In the following inventory rounds, the reader quickly acquires a BF from these tags only. With the BF, we can check if all the bits that a known tag is hashed into in the acquired BF are set to ‘1’ - a negative result implies that the test tag is gone (or missing); or check if new ‘1’s emerge - a positive result implies the presence of one or more new tags. Then, we can dynamically adjust the tag set by removing left tags and/or adding new tags. Note that the new tags can be selectively read as shown in [45]. BF-Aware Missing Detection. We consider a warehouse that stores a large number of high-valued commercial products or a military base that stocks a large number of guns and ammunition packages [16]. We assume that each object is attached with an RFID tag. To detect missing objects that may have been stolen from the warehouse in a timely manner, an RFID reader must periodically scan all of the present RFID tags to maintain a fresh record. It is reasonable to assume all EPCs are known ahead of time; otherwise, we cannot tell which tag is missing. BF naturally fits such needs because it is an exact representation of the current tag set [19]–[33], [43]. We can check if all the bits that a test tag is hashed into in the acquired BF are set to 1. A negative result implies that the test tag is missing. Utilizing BF is time-efficient for two main aspects at least. First, collisions are now allowable and informative, which imply the presence of the corresponding hashed tags. This re￾moves the time-consuming process of dealing with collisions. Second, each tag only requires to transmit a few bits (e.g., 16-bit RN16 in our design) to show its presence instead of a whole 144-bit long reply, saving transmission time by orders of magnitude for each time slot. C. Comparison with our Prior Work This work enhances our prior design [43], which emulates a group of hash primitives in the application layer. However, our solution is more efficient and practical prior to [43] at least in two aspects. • Practicality: As an application-layer emulation technique, Tash highly depends on a Gen2 command, i.e., Truncate, which forces tags to transmit truncated EPCs. These in￾complete EPCs are viewed as the presence evidence of

IEEE/ACM TRANSACTIONS ON NETWORKING tags.Unfortunately,to our best knowledge and investigation, we have not found any Truncate-available tags on the elect market.Actually,this issue has been claimed in [43].This is also the reason that the performance of Tash [43]related to this command is evaluated with simulations,instead of real tags.On the contrary,our solution uses RN16 reply as presence evidence.As a fundamental reply,the RN16 reply 0 100100 is completely serviceable in today's Gen2 tags. M Efficiency:The anti-collision processing is actually un- Fig.4:Acquisition solution.To acquire an M-bit BF,TagMap avoidable in Tash,because there is no way to control the reader initiates M intercepted inventories,each of which contains inventory procedure in the application layer.No relevant K Selects,one Query and a time window for RN16 reply. APIs are provided by commercial readers so far.Our ap- B.Solution Sketch proach intercepts an inventory in the physical layer to skip the anti-collision processing. The features and usage of the Bloom filter have been widely In short.TagMap is highly advantageous due to its physical- studied in various fields [46].They are not our focus in this layer performance boost and full compatibility with COTS work.Instead,we more concern about the way to acquire a tags. BF across RFID tags,which must be tightly integrated with the standard EPCglobal Gen2 RFID air protocol [47],making billions of tags serviceable.The whole solution consists of two III.OVERVIEW phases as follows: In offline phase,we compute the hash value of each tag's Although we present our acquisition approach with the EPC and store it inside the tag's non-volatile memory bank EPCglobal Gen2 air interface protocol,which has been for future use.The storing can be accomplished by using adopted globally,our approach also works with other similar the standard Gen2 command of Write.This phase is only protocols,such as ISO18000-6C.In this section,we firstly initiated once.For example,it is initiated when the user formulate the Bloom filter and then sketch the overall solution. writes EPCs to tags. In online phase,the reader acquires a BF bit by bit.The TagMap reader initiates an intercepted inventory for each A.Formulation of Bloom Filter bit.The inventory is used to answer the question of presence A BF represents a set T={t1,t2,...,tn}with n tags.It is that if any tag is hashed into the corresponding bit.If answer described by an array of M bits,which are initially set to 0. is positive,the bit is set to one;otherwise,it is set to zero. We can use K hash functions,(hi,h2,...,hk}to map each Fig.4 shows the acquisition procedure from a high-level. tag in the universe to a number within the range {1,...,M). To acquire an M-bit BF,the reader initiates M intercepted For each tag t ET,the bits of (h(t),...,hk(t)}are set to inventories,each of which corresponds to a bit in the BF.In 1.A bit can be set to 1 multiple times (e.g.,collisions),but each inventory,the reader broadcasts K Select commands its value remains 1.To check if a tag t is in T,we check if and one Query command;the tags matching the hash rules all bits of (h(t),...,hk(t)}are set to 1.If not,then t is not are forced to transmit their RN16 replies in the first slot.In in the tag set.If all bits are set to 1,we assume that t is in the end of the intercepted inventory,the reader determines the T,although this assumption may be wrong with sufficiently value of the corresponding bit. low probability,namely,yielding a false positive.The false positive rate depends on parameter selection:using many hash IV.ACQUISITION OF BLOOM FILTER functions equates to a high probability of finding'0'bits for In this section,we introduce the technical details of each tag that is not in the set;using a few hash functions increases the fraction of'0'bits in the map.Here,we present TagMap. two useful Lemmas as follows: A.TagMap in a Nutshell Lemma 1.Given a tolerance (i.e.,upper bound of false positive rate，以BF length M≥[nlog2e·log2(1/e)l= The subsequent sections progressively introduce the acqui- [1.44nlog2(1/e)1: sition approach by discussing the following issues: Emulating hash function.Commercially available tags at Lemma 2.The false negative rate is minimized when present do not support hash functions.Thus,our first task is the number of hash functions K [In2.(M/n)]= to emulate a hash function that works as if it was embedded 「0.99811og2(1/e)17 on each tag. Their proofs are similar in nature to the standard analysis Answering the question of presence.With the emulated hash of the Bloom filter as shown in [46].The number of tags n is functions,a TagMap reader initiates an intercepted inventory assumed to be known already.It can be discovered through a to suggest whether any tag that can output a given hash value preliminary inventory or stored in backend. is present or not

IEEE/ACM TRANSACTIONS ON NETWORKING 4 tags. Unfortunately, to our best knowledge and investigation, we have not found any Truncate-available tags on the market. Actually, this issue has been claimed in [43]. This is also the reason that the performance of Tash [43] related to this command is evaluated with simulations, instead of real tags. On the contrary, our solution uses RN16 reply as presence evidence. As a fundamental reply, the RN16 reply is completely serviceable in today’s Gen2 tags. • Efficiency: The anti-collision processing is actually un￾avoidable in Tash, because there is no way to control the inventory procedure in the application layer. No relevant APIs are provided by commercial readers so far. Our ap￾proach intercepts an inventory in the physical layer to skip the anti-collision processing. In short, TagMap is highly advantageous due to its physical￾layer performance boost and full compatibility with COTS tags. III. OVERVIEW Although we present our acquisition approach with the EPCglobal Gen2 air interface protocol, which has been adopted globally, our approach also works with other similar protocols, such as ISO18000-6C. In this section, we firstly formulate the Bloom filter and then sketch the overall solution. A. Formulation of Bloom Filter A BF represents a set T = {t1, t2, . . . , tn} with n tags. It is described by an array of M bits, which are initially set to 0. We can use K hash functions, {h1, h2, . . . , hK} to map each tag in the universe to a number within the range {1, . . . , M}. For each tag t ∈ T, the bits of {h1(t), . . . , hK(t)} are set to 1. A bit can be set to 1 multiple times (e.g., collisions), but its value remains 1. To check if a tag t is in T, we check if all bits of {h1(t), . . . , hK(t)} are set to 1. If not, then t is not in the tag set. If all bits are set to 1, we assume that t is in T, although this assumption may be wrong with sufficiently low probability, namely, yielding a false positive. The false positive rate depends on parameter selection: using many hash functions equates to a high probability of finding ‘0’ bits for each tag that is not in the set; using a few hash functions increases the fraction of ‘0’ bits in the map. Here, we present two useful Lemmas as follows: Lemma 1. Given a tolerance ε (i.e., upper bound of false positive rate), BF length M ≥ dn log2 e · log2 (1/ε)e = d1.44n log2 (1/ε)e. Lemma 2. The false negative rate is minimized when the number of hash functions K = dln 2 · (M/n)e = d0.9981 log2 (1/ε)e. Their proofs are similar in nature to the standard analysis of the Bloom filter as shown in [46]. The number of tags n is assumed to be known already. It can be discovered through a preliminary inventory or stored in backend. Intercepted Inventory ··· Intercepted Inventory Select ··· Select Query ⌧2 RN16 ⌧3 K ⌧1 ⌧1 0 1 0 1 0 1 0 0 Intercepted Inventory ··· M BF bitmap: Fig. 4: Acquisition solution. To acquire an M-bit BF, TagMap reader initiates M intercepted inventories, each of which contains K Selects, one Query and a time window for RN16 reply. B. Solution Sketch The features and usage of the Bloom filter have been widely studied in various fields [46]. They are not our focus in this work. Instead, we more concern about the way to acquire a BF across RFID tags, which must be tightly integrated with the standard EPCglobal Gen2 RFID air protocol [47], making billions of tags serviceable. The whole solution consists of two phases as follows: • In offline phase, we compute the hash value of each tag’s EPC and store it inside the tag’s non-volatile memory bank for future use. The storing can be accomplished by using the standard Gen2 command of Write. This phase is only initiated once. For example, it is initiated when the user writes EPCs to tags. • In online phase, the reader acquires a BF bit by bit. The TagMap reader initiates an intercepted inventory for each bit. The inventory is used to answer the question of presence that if any tag is hashed into the corresponding bit. If answer is positive, the bit is set to one; otherwise, it is set to zero. Fig. 4 shows the acquisition procedure from a high-level. To acquire an M-bit BF, the reader initiates M intercepted inventories, each of which corresponds to a bit in the BF. In each inventory, the reader broadcasts K Select commands and one Query command; the tags matching the hash rules are forced to transmit their RN16 replies in the first slot. In the end of the intercepted inventory, the reader determines the value of the corresponding bit. IV. ACQUISITION OF BLOOM FILTER In this section, we introduce the technical details of TagMap. A. TagMap in a Nutshell The subsequent sections progressively introduce the acqui￾sition approach by discussing the following issues: • Emulating hash function. Commercially available tags at present do not support hash functions. Thus, our first task is to emulate a hash function that works as if it was embedded on each tag. • Answering the question of presence. With the emulated hash functions, a TagMap reader initiates an intercepted inventory to suggest whether any tag that can output a given hash value is present or not

IEEE/ACM TRANSACTIONS ON NETWORKING r=5l=4 10102 Reade Tag Memory Model 11110100 Tags HemBank1:1010111011010010 01011100 Pointer s 011111009 1=4 01001000 MemBank3: 0111010101000110H() ak=10 01110110 Ot MemBank3 r=5 、bitmask S(4,3.1102） 100 11101100 Fig.6:Illustration of selective reading in Gen2 protocol.7 tags Fig.5:Illustration of a hash function.The figure shows a tag's two are covered by a reader.The reader initiates a Select command memory banks:MemBank1 and MemBank3,which store the tag's S(4,3,1102).As a result,tags of t2,ts,ts and t6 (highlighted in EPC t and the real hash value H(t)respectively.Given an input of red)are only selected to join in the incoming inventory because their r=5 and I=4,the output of h(4)(t,5)equals 10102,which exactly MemBank3s'sub-bitstring (highlighted in red)within 4,7)equals is the sub-bitstring of H(t)within 5,9)bits stored in MemBank3. 1102.Other tags do not meet the condition and remain silent. Acquiring a Bloom filter.Finally,we show how the reader ]as国ac builds a whole BF bit by bit through a series of intercepted P.RN1R inventories in three cases 7.2 Select Query Next,we introduce these issues with details. B.Emulating Hash Functions A hash function,denoted by h((t,r),outputs an I-bit hash 0. value when given a tag's EPC t and a random number r.It takes three inputs:(1)an l-bit tag's EPC number t;(2)an l,-bit random number r;and (3)the bit length of the hash value l.Formally, 10 121416 18 Time (ms) h四(t,r）:{0,1}×{0,1→{0,1} 1) Fig.7:Baseband signals of an intercepted inventory.The inventory where l is also called the dimension of the hash function.The contains a Select,a Query and an RN16 reply.T,T2 and Ts are output is randomly distributed in [0,2).Following a common key timing parameters,which are specified in the Gen2 protocol. The reader detects the presence of RN16 reply to determine if any practice,we create K hash functions by shuffling the output tag responds. using K different random numbers.The kth hash function is denoted byh(t,k).The superscript l is sometimes omitted, quality of randomness at each bit.If the upper application such as h(t,rk),hk(t)or hk,for clarity unless it should be needs a stronger randomness,one could store a truly ran- noted. dom bitstring in the MemBank3 rather than the real hash Memory Banks.Before introducing the hash design,we value,meanwhile save the mapping between the EPC and the need to introduce some background about the memory bank bitstrings in database for future query.In addition,to avoid of tag.The Gen2 air protocol specifies a simple tag memory the dependence of K hash values,one can tactfully choose model:each tag contains four types of non-volatile memory r1,...,rK such that [ri,r1+1)n...n[rk,rK +1)= blocks(called memory banks).The first three banks are used Secondly,The computation of H(t)is performed in a host to store the password,EPC number and TID number.The last computer rather than on tags,so its workload is almost memory bank(MemBank3)is reserved for user-defined data.neglected.Storing H(t)is also performed once until the tag's Fig.5 demonstrates the first and the third memory bank.The EPC is changed,which is unlikely to happen often in practice. Read or write commands are used to read or write data Although writing data into memory bank usually takes a longer from or into these banks respectively. time than reading them,the writing is performed in offline Hash Function.Initially,we compute the real hash value phase thereby its workload is not counted into the acquisition (denoted by H(t))of a tag's EPC by using SHA-1 for tag t, overhead.Thirdly,A possible concern is if today's RFID tags and then store H(t)in the tag's MemBank3 for future use. in the market can serve our design in terms of the operability Note both operations are performed once in the offline phase. of MemBank3.We investigate 40 tag chips from ImpinJ [48]. We define a tag's sub-bitstring within [r,+l)in MemBank3 Alien [49]and NXP [50],whose total market share exceeds as its 1-bit hash value challenged by the random number r. 80%[1].The investigation result suggests that TagMap is In other words,our hash value h((t,r)is a portion of H(t) completely compatible with the EPCglobal Gen2 air protocol stored in MemBank3.Fig.5 demonstrates the relation between and can serve 97.5%types of tags,except those that are read- the real hash value and our hash value,where the tag's 4-bit only(More details refer to Sec.VI.). hash value h(4)(t,5)=10102(the ()2 means a value in binary format.).Clearly,our design does not require a tag to equip a real hash function or gets its chip involved. C.Answering the Question of Presence Discussion.Evidently,h((t,r)is random and its random- A simple way to obtain a tag's hash value is to Read ness is derived from H(t).which is supposed to have good the corresponding sub-bitstring from its MemBank3.However

IEEE/ACM TRANSACTIONS ON NETWORKING 5 Tag Memory Model 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 H(t) MemBank1: 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 0 t MemBank3: 10102 1 0 1 0 l = 4 bitmask r = 5 r = 5,l = 4 Fig. 5: Illustration of a hash function. The figure shows a tag’s two memory banks: MemBank1 and MemBank3, which store the tag’s EPC t and the real hash value H(t) respectively. Given an input of r = 5 and l = 4, the output of h (4)(t, 5) equals 10102, which exactly is the sub-bitstring of H(t) within [5, 9) bits stored in MemBank3. • Acquiring a Bloom filter. Finally, we show how the reader builds a whole BF bit by bit through a series of intercepted inventories in three cases. Next, we introduce these issues with details. B. Emulating Hash Functions A hash function, denoted by h (l) (t, r), outputs an l-bit hash value when given a tag’s EPC t and a random number r. It takes three inputs: (1) an lt-bit tag’s EPC number t; (2) an lr-bit random number r; and (3) the bit length of the hash value l. Formally, h (l) (t, r) : {0, 1} lt × {0, 1} lr → {0, 1} l (1) where l is also called the dimension of the hash function. The output is randomly distributed in [0, 2 l ). Following a common practice, we create K hash functions by shuffling the output using K different random numbers. The k th hash function is denoted by h (l) k (t, rk). The superscript l is sometimes omitted, such as h(t, rk), hk(t) or hk, for clarity unless it should be noted. Memory Banks. Before introducing the hash design, we need to introduce some background about the memory bank of tag. The Gen2 air protocol specifies a simple tag memory model: each tag contains four types of non-volatile memory blocks (called memory banks). The first three banks are used to store the password, EPC number and TID number. The last memory bank (MemBank3) is reserved for user-defined data. Fig. 5 demonstrates the first and the third memory bank. The Read or Write commands are used to read or write data from or into these banks respectively. Hash Function. Initially, we compute the real hash value (denoted by H(t)) of a tag’s EPC by using SHA-1 for tag t, and then store H(t) in the tag’s MemBank3 for future use. Note both operations are performed once in the offline phase. We define a tag’s sub-bitstring within [r, r +l) in MemBank3 as its l-bit hash value challenged by the random number r. In other words, our hash value h (l) (t, r) is a portion of H(t) stored in MemBank3. Fig. 5 demonstrates the relation between the real hash value and our hash value, where the tag’s 4-bit hash value h (4)(t, 5) = 10102 (the (·)2 means a value in binary format.). Clearly, our design does not require a tag to equip a real hash function or gets its chip involved. Discussion. Evidently, h (l) (t, r) is random and its random￾ness is derived from H(t), which is supposed to have good MemBank3 Reader Tags Select 0 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 Select t1 t2 t3 t4 t5 t6 t7 Pointer =4 Length =3 Mask = 1102 S(4, 3, 1102) Reader Select Query RN16 Time Fig. 6: Illustration of selective reading in Gen2 protocol. 7 tags are covered by a reader. The reader initiates a Select command S(4, 3, 1102). As a result, tags of t2, t3, t5 and t6 (highlighted in red) are only selected to join in the incoming inventory because their MemBank3s’ sub-bitstring (highlighted in red) within [4, 7) equals 1102. Other tags do not meet the condition and remain silent. 0 2 4 6 8 10 12 14 16 18 Time (ms) 0 0.2 0.4 0.6 0.8 1 1.2 Amplitude (v) Intercepted inventory Select Query RN16 Preamble ⌧1 ⌧2 ⌧3 READER TAG P RN16 Select Query Select Time slot Fig. 7: Baseband signals of an intercepted inventory. The inventory contains a Select, a Query and an RN16 reply. τ1, τ2 and τ3 are key timing parameters, which are specified in the Gen2 protocol. The reader detects the presence of RN16 reply to determine if any tag responds. quality of randomness at each bit. If the upper application needs a stronger randomness, one could store a truly ran￾dom bitstring in the MemBank3 rather than the real hash value, meanwhile save the mapping between the EPC and the bitstrings in database for future query. In addition, to avoid the dependence of K hash values, one can tactfully choose r1, . . . , rK such that [r1, r1 + l) ∩ · · · ∩ [rK, rK + l) = ∅. Secondly, The computation of H(t) is performed in a host computer rather than on tags, so its workload is almost neglected. Storing H(t) is also performed once until the tag’s EPC is changed, which is unlikely to happen often in practice. Although writing data into memory bank usually takes a longer time than reading them, the writing is performed in offline phase thereby its workload is not counted into the acquisition overhead. Thirdly, A possible concern is if today’s RFID tags in the market can serve our design in terms of the operability of MemBank3. We investigate 40 tag chips from ImpinJ [48], Alien [49] and NXP [50], whose total market share exceeds 80% [1]. The investigation result suggests that TagMap is completely compatible with the EPCglobal Gen2 air protocol and can serve 97.5% types of tags, except those that are read￾only(More details refer to Sec.VI.). C. Answering the Question of Presence A simple way to obtain a tag’s hash value is to Read the corresponding sub-bitstring from its MemBank3. However

IEEE/ACM TRANSACTIONS ON NETWORKING 1.0g where the mask will be compared with .0i SamplesOffset 1.0 These fields are combined to compose a selection rule.We formally denote the rule as follows: Length S(卫，t,m) Pointer Mask which implies that only tags whose MemBank3s'sub-bitstring p,p+1)is equal to m will be selected.Fig.6 shows an (a)RN16 example in which four tags are selected to join in the inventory. Note that multiple Selects are allowable (discussed later). ■Acucired-Desired Intercepted Inventory.The function of selective reading offers an opportunity to select the tags based on a mask.If the reader broadcasts the following Select, S(r,l,v) then only the tags whose sub-bitstring [r,r+1)in its 500 550 600 650700 750 800 850 MemBank3 is equal to v,are selected to participate in the Samples# incoming inventory.Interestingly,the set of selected tags (b)Preamble exactly fit the question of presence!To know if its cardinality is greater than zero,we let the reader afterwards broadcast Fig.8:Baseband signals of RN16 reply.(a)shows the signals of a RN16 reply.which is composed of a 5-bit preamble and 16 a Query command to start a single-slot frame,by setting random bits.(b)shows zoomed-in preamble and its comparison with the field of frame length to 1.All selected tags are forced to the desired template. reply in the following slot immediately.As aforementioned, a tag must transmit an RN16 reply firstly before sending its EPC reply.Our trick here is that the RN16 reply is regarded keep in mind that our ultimate goal is to acquire a BF across all as the presence evidence of a tag.which has the given hash tags instead of their hash values.Here,we consider a question, value.As long as the reader detects any RN16 reply signal, named question of presence,that is,is there any tag which the answer to the question of presence is negative.Finally, can output a wanted hash value?Formally,given the input the reader ignores the request of long reply even if a single pair(r,l)and the hash value v,we determine if tag responds and terminates the inventory procedure.We call the above procedure intercepted inventory.The inventory is {h四(t,r）=>0 "intercepted"because an intact inventory is supposed to ACK for all t E T,where denotes the cardinality of a set.Since the tag's RN16 reply and request the long reply subsequently our hash value is a portion of the real one stored in a tag's (see Fig.2).In contrast to the entire inventory,the interval MemBank3,the question can be converted to a new form: of an intercept inventory is kept constant regardless of how many tags participate the procedure.Fig.7 shows the baseband Problem 1.Is there any tag whose sub-bistring Er,r+l)signals of an intercepted inventory acquired by USRP N210. in its MemBank3 is equal to v? Detecting Presence Signals.Each 22-bit RN16 reply con- Selective Reading.Any inventory procedure must be started tains a 6-bit preamble and 16 random bits.The reader can with a Select command.Gen2 protocol specifies that detect an RN16 reply by correlating its preamble template each tag maintains a flag variable SL.The reader can use with the received signals.Considering that the 16-bit random the Select command to turn the SL flags of tags into signals are independent of the preamble,their correlation is asserted (i.e.,true)or deasserted (i.e.,false).Only the nearly zero except when the preamble is perfectly aligned with asserted tags will respond to a Query (or QueryAdjust) the beginning of an RN16.One or multiple spikes appearing at command,participating the inventory.The Select command the correlation result indicate the presence of one or multiple is composed of 8 fields.For simplicity,we only introduce the tags possessing the given hash value.Fig.8(a)shows an four fields,which will be employed in our design:MemBank, example of RN16 reply sent from a single tag.Fig.8(b)zooms Pointer,Length and Mask. into its preamble compared with the template.It is worth Mask:it is a specific bitstring that should match the content noting that the final received signal is a combination of the of a specific position in a MemBank. line-of-sight propagation,the repetitive proportions from other none-ling-of-sight paths,and the leakage of the continuous Length:it defines the length of the mask in bits wave from the reader.The signals arrive at the receiver MemBank:it specifies which memory bank the mask will different phase values due to the diversity of the propagation be compared with.We consider MemBank3 only by default distances.As a result,they might add up constructively or in our scenario. destructively.In the second case,the received signal might be Pointer:it specifies the starting position in the MemBank weaker than the power of reader continuous wave

IEEE/ACM TRANSACTIONS ON NETWORKING 6 500 1000 1500 2000 2500 Samples# 0.98 0.985 0.99 0.995 1 1.005 1.01 1.015 1.02 Amplitude Samples Offset =1 (a) RN16 500 550 600 650 700 750 800 850 Samples# -2 -1 0 1 2 Amplitude Acuqired Desired (b) Preamble Fig. 8: Baseband signals of RN16 reply. (a) shows the signals of a RN16 reply, which is composed of a 5-bit preamble and 16 random bits. (b) shows zoomed-in preamble and its comparison with the desired template. keep in mind that our ultimate goal is to acquire a BF across all tags instead of their hash values. Here, we consider a question, named question of presence, that is, is there any tag which can output a wanted hash value? Formally, given the input pair (r, l) and the hash value v, we determine if   {t|h (l) (t, r) = v}    > 0 for all t ∈ T, where | · | denotes the cardinality of a set. Since our hash value is a portion of the real one stored in a tag’s MemBank3, the question can be converted to a new form: Problem 1. Is there any tag whose sub-bistring ∈ [r, r + l) in its MemBank3 is equal to v? Selective Reading. Any inventory procedure must be started with a Select command. Gen2 protocol specifies that each tag maintains a flag variable SL. The reader can use the Select command to turn the SL flags of tags into asserted (i.e., true) or deasserted (i.e., false). Only the asserted tags will respond to a Query (or QueryAdjust) command, participating the inventory. The Select command is composed of 8 fields. For simplicity, we only introduce the four fields, which will be employed in our design: MemBank, Pointer, Length and Mask. • Mask: it is a specific bitstring that should match the content of a specific position in a MemBank. • Length: it defines the length of the mask in bits. • MemBank: it specifies which memory bank the mask will be compared with. We consider MemBank3 only by default in our scenario. • Pointer: it specifies the starting position in the MemBank where the mask will be compared with. These fields are combined to compose a selection rule. We formally denote the rule as follows: S( p |{z} Pointer , Length z}|{ l , m|{z} Mask ) which implies that only tags whose MemBank3s’ sub-bitstring ∈ [p, p + l) is equal to m will be selected. Fig. 6 shows an example in which four tags are selected to join in the inventory. Note that multiple Selects are allowable (discussed later). Intercepted Inventory. The function of selective reading offers an opportunity to select the tags based on a mask. If the reader broadcasts the following Select, S(r, l, v) , then only the tags whose sub-bitstring ∈ [r, r + l) in its MemBank3 is equal to v, are selected to participate in the incoming inventory. Interestingly, the set of selected tags exactly fit the question of presence! To know if its cardinality is greater than zero, we let the reader afterwards broadcast a Query command to start a single-slot frame, by setting the field of frame length to 1. All selected tags are forced to reply in the following slot immediately. As aforementioned, a tag must transmit an RN16 reply firstly before sending its EPC reply. Our trick here is that the RN16 reply is regarded as the presence evidence of a tag, which has the given hash value. As long as the reader detects any RN16 reply signal, the answer to the question of presence is negative. Finally, the reader ignores the request of long reply even if a single tag responds and terminates the inventory procedure. We call the above procedure intercepted inventory. The inventory is “intercepted” because an intact inventory is supposed to ACK the tag’s RN16 reply and request the long reply subsequently (see Fig. 2). In contrast to the entire inventory, the interval of an intercept inventory is kept constant regardless of how many tags participate the procedure. Fig. 7 shows the baseband signals of an intercepted inventory acquired by USRP N210. Detecting Presence Signals. Each 22-bit RN16 reply con￾tains a 6-bit preamble and 16 random bits. The reader can detect an RN16 reply by correlating its preamble template with the received signals. Considering that the 16-bit random signals are independent of the preamble, their correlation is nearly zero except when the preamble is perfectly aligned with the beginning of an RN16. One or multiple spikes appearing at the correlation result indicate the presence of one or multiple tags possessing the given hash value. Fig. 8(a) shows an example of RN16 reply sent from a single tag. Fig. 8(b) zooms into its preamble compared with the template. It is worth noting that the final received signal is a combination of the line-of-sight propagation, the repetitive proportions from other none-ling-of-sight paths, and the leakage of the continuous wave from the reader. The signals arrive at the receiver different phase values due to the diversity of the propagation distances. As a result, they might add up constructively or destructively. In the second case, the received signal might be weaker than the power of reader continuous wave

IEEE/ACM TRANSACTIONS ON NETWORKING 7 Φ0.45 0. 0.35 0 10 20 2 Time(ms) Fig.9:Baseband signals of acquiring an 8-bit BF across 3 tags.The bitmap totally contains 8 bits,each of which corresponds to an intercepted inventory.The three tags reply in the 1,2 and 5hinventory respectively,so the final BF equals [1,1,0,0,1,0,0,0]. D.Acquiring a Bloom Filter 0.35 Interceptod Invantory Ineegceeted Inventory So far.we have discussed how the TagMap reader deter- 0.3 mines if any tag outputs a given hash value.Now,we start to 0.29 acquire a whole BF by considering three cases progressively: 1)Case 1:Acquisition with a Single Hash:We firstly consider a simplified case,namely,acquiring a 2-bit BF using 01 0.1 a single hash function:h(t,r).Correspondingly,the bitmap size M=24.The definition of hash bitmap indicates that:a tag t is hashed into the mth bit of the bitmap if and only if 28 30 32 34 36 h四(t,r）=m for t∈T,where m=0,,M-1. Time(ms) Namely,the index of the bitmap actually implies the hash Fig.10:Acquiring an BF with 2 hashes.There are two intercepted value.We build a BF bit by bit,traversing the index from 0 inventories.The baseband signals fo each inventory contains two to M-1.When building the mth bit,we ask the question of Selects'signals before the Query signals. presence like this:is there any tag whose hash value is equal to m?To do so,the reader initiates an intercepted inventory reader initiates an intercepted inventory,which contains K with the Select command of S(r,l,m).If the answer is positive,the mth bit of the BF is set to'1';otherwise,0' Selects as follows: This procedure continues until M bits are all traversed. S(r1;I,m),S(r2,I,m),...,S(rk,l,m) (2) Fig.9 shows the baseband signals of acquiring an 8-bit BF Similarly,if any RN16 signal is detected after the Query,the across 3 tags.From the figure,we can observe 8 intercepted corresponding bit is set to'1'.Fig.10 shows the baseband sig- inventories.Zooming into any one of them,three distinct nals of two consecutive intercepted inventories when acquiring segments-Select,Query and RN16-can be observed, a BF with 2 hashes.From the figure,we can exactly observe exactly as same as a single intercepted inventory shown in two Select commands before the Query in an intercepted Fig.7. inventory. 2)Case 2:Acquisition with K Hashes:Secondly,we consider to acquire a 2-bit BF using K hash functions: 3)Case 3:Acquisition with Arbitrary Size:The first two h四(t,r1),.,h四(t,rK）.in this case,the mth bit is set to cases consider to generate BFs with size of M=2!bit. 'I'when any one tag is hashed into the bit by any one of these The size M is a key parameter that directly determines K hash functions.Correspondingly,the question of presence acquisition overhead,and thereby should be well optimized. turns to Lemma 2 implies the minimal(and optimal)size.Apparently, the minimal size of BF might not be exactly an exponent of {th(t,ri)=mll...Ilh(t,rK)=m)> 2.On the other hand,the hash values are stored in a binary format in the memory bank,so l must be an integer.As a for all t T.With regard to our hash function,the question result,the actual size M has to be set to 2 and I=[log2 M can be expressed as follows: suppose M is the optimal size,such that M>M and I is Problem 2.Is there any tag whose sub-bitstring E[r1,r1+ an integer.This setting is valid but might be extremely costly. I-1),...or E [rK,rK +I-1)in its MemBank3 is equal For example,suppose the optimal size M=257,we have to to m? set actual size M=2og22571=512,which is almost double than the optimal one. Since each range corresponds to a Select,answering the To enable an arbitrary size,we define the operation of above question requires K Selects.The result of multiple modulo to shrink the size,as used in other applications [46]. Select commands is a union of the selected tags:if a tag's Apparently M>M.Traversing the mth hash value where SL variable is asserted multiple times,then the final value remains asserted.The consequence is equivalent to combining m =0,...,M-1,the reader forces tags hashed into mth the sets of selected tags.This is exactly the answer to the bits to reply at the above question of presence.Therefore,for the mth bit,the h'(t,r）modi (3)

IEEE/ACM TRANSACTIONS ON NETWORKING 7 0 5 10 15 20 25 30 Time(ms) 0.35 0.4 0.45 0.5 Amplitude 1 1 0 0 1 0 0 0 0 1 2 3 4 5 6 7 t3 t2 Query Select RN16 t1,t4 BF Index Fig. 9: Baseband signals of acquiring an 8-bit BF across 3 tags. The bitmap totally contains 8 bits, each of which corresponds to an intercepted inventory. The three tags reply in the 1 st , 2 nd and 5 th inventory respectively, so the final BF equals [1, 1, 0, 0, 1, 0, 0, 0]. D. Acquiring a Bloom Filter So far, we have discussed how the TagMap reader deter￾mines if any tag outputs a given hash value. Now, we start to acquire a whole BF by considering three cases progressively: 1) Case 1: Acquisition with a Single Hash: We firstly consider a simplified case, namely, acquiring a 2 l -bit BF using a single hash function: h (l) (t, r). Correspondingly, the bitmap size M = 2l . The definition of hash bitmap indicates that: a tag t is hashed into the mth bit of the bitmap if and only if h (l) (t, r) = m for t ∈ T, where m = 0, . . . , M − 1. Namely, the index of the bitmap actually implies the hash value. We build a BF bit by bit, traversing the index from 0 to M − 1. When building the mth bit, we ask the question of presence like this: is there any tag whose hash value is equal to m? To do so, the reader initiates an intercepted inventory with the Select command of S(r, l, m). If the answer is positive, the mth bit of the BF is set to ‘1’; otherwise, ‘0’. This procedure continues until M bits are all traversed. Fig. 9 shows the baseband signals of acquiring an 8-bit BF across 3 tags. From the figure, we can observe 8 intercepted inventories. Zooming into any one of them, three distinct segments - Select, Query and RN16 - can be observed, exactly as same as a single intercepted inventory shown in Fig. 7. 2) Case 2: Acquisition with K Hashes: Secondly, we consider to acquire a 2 l -bit BF using K hash functions: h (l) (t, r1), . . . , h(l) (t, rK). In this case, the mth bit is set to ‘1’ when any one tag is hashed into the bit by any one of these K hash functions. Correspondingly, the question of presence turns to   {t|h (l) (t, r1) = m|| . . . ||h (l) (t, rK) = m}    > 0 for all t ∈ T. With regard to our hash function, the question can be expressed as follows: Problem 2. Is there any tag whose sub-bitstring ∈ [r1, r1 + l − 1), . . . , or ∈ [rK, rK + l − 1) in its MemBank3 is equal to m? Since each range corresponds to a Select, answering the above question requires K Selects. The result of multiple Select commands is a union of the selected tags: if a tag’s SL variable is asserted multiple times, then the final value remains asserted. The consequence is equivalent to combining the sets of selected tags. This is exactly the answer to the above question of presence. Therefore, for the mth bit, the 26 28 30 32 34 36 Time (ms) 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 Amplitude Select Select RN16 Query Select Select Query RN16 Intercepted Inventory Intercepted Inventory Fig. 10: Acquiring an BF with 2 hashes. There are two intercepted inventories. The baseband signals fo each inventory contains two Selects’ signals before the Query signals. reader initiates an intercepted inventory, which contains K Selects as follows: S(r1, l, m), S(r2, l, m), . . . , S(rK, l, m) (2) Similarly, if any RN16 signal is detected after the Query, the corresponding bit is set to ‘1’. Fig. 10 shows the baseband sig￾nals of two consecutive intercepted inventories when acquiring a BF with 2 hashes. From the figure, we can exactly observe two Select commands before the Query in an intercepted inventory. 3) Case 3: Acquisition with Arbitrary Size: The first two cases consider to generate BFs with size of M = 2l bit. The size M is a key parameter that directly determines acquisition overhead, and thereby should be well optimized. Lemma 2 implies the minimal (and optimal) size. Apparently, the minimal size of BF might not be exactly an exponent of 2. On the other hand, the hash values are stored in a binary format in the memory bank, so l must be an integer. As a result, the actual size M has to be set to 2 l and l = dlog2 Mce suppose Mc is the optimal size, such that M ≥ Mc and l is an integer. This setting is valid but might be extremely costly. For example, suppose the optimal size Mc = 257, we have to set actual size M = 2dlog2 257e = 512, which is almost double than the optimal one. To enable an arbitrary size, we define the operation of modulo to shrink the size, as used in other applications [46]. Apparently M ≥ Mc. Traversing the mth hash value where m = 0, . . . , M − 1, the reader forces tags hashed into mth bits to reply at the h l (t, r) mod Mc (3)

IEEE/ACM TRANSACTIONS ON NETWORKING 8 M bits is identified.Thus,the whole procedure totally contains n Mbits Truncated bits frames,n long slots,and ne ln(n)-n short slots.As shown in Fig.2,a long time slot in which only a single tag intends 5 6 15 to transmit is EPC.is reserved for the transmissions of a 101004 -Moving forward QueryAdjust,an RN16,an ACK,and an EPC:a short time 1112131415， slot in which no tags respond or multiple tags'signals are collided,is reserved for the transmissions of a QueryAdjust Fig.11:The design of modulo.Suppose the optimal size of the and an RN16.Thus,the totally time overhead taken by Q- BF is 11,the reader builds 2=16 bit BF and moves the last Adaptive,denoted by Co-Adaptive,can be computed as follows: 5 bits to align with the first five. Co-Adaptive nTL+(ne ln n-n)T's +nTDelay TL TQuery TRN16 TAck TEPC (4) -th intercepted inventory.In other words,if a tag is supposed Ts=TQueryAdjust TRN16 to be hashed into the bit greater than or equal to M,then the tag is moved to reply at (m mod M)th bit-inventory.As where TL and Ts are the sizes of a long time slot and a short illustrated in Fig.11,the modulo moves the replies at the time slot respectively.According to our prior study [45],the bits equal to or greater than M ahead to align with the first commercial readers require to reserve Tpelay seconds in the bits.Correspondingly,the question of presence turns to: beginning of each frame for some pre-arranged tasks,such as synchronization,clearing tag states,adjustment of frame Problem 3.Is there any tag whose sub-bitstring E[r1,r1+). length,etc.Since n frames are required,the total extra time ...or E [rk,rK+l)in its MemBank3 is equal to m,m+M, consumption is nTDely.The other time symbols Txxx denotes m+2i,.,orm+l岩」？ the time consumed on the corresponding reader commands or Therefore,for the mth bit,the reader initiates an intercepted the tag reply.For example,Touery denotes the time cost for inventory,which contains multiple Selects as follows: transmitting a reader command of Query.Finally,the total overhead taken by the Q-Adaptive is given by S(r1,l;m),S(r2;1,m),...:S(rk:l,m) CQ-Adaptive(n)=n(TDelay TQuery +TRNI6+TAck TErc) +(neln n-n)(TQueryAdjust +TRN16) S(r1,l,m+[ Cleary,the overhead is only related to the total number of tags It is worthing noting the modulo operation would increase (i.e.,n)in the scanning field. the number of tags hashed into the head bits,breaking the randomness of BF.If the upper-layer application requires a B.Overhead Analysis on TagMap strong randomness,a good way is to move truncated bit (i.e., Unlike the Q-Adaptive,all time slots in TagMap are equal indexes >M)forward to a random index less than M while the reader labels the mapping between the tags and bits so the in size.The collection procedure totally contains M slots,each of which is reserved for the transmissions of K Selects,a application can predicate the hashing. Query and an RN16.Thus,the total time overhead taken by TagMap.denoted by CTagMap.can be computed as follows: V.ANALYSIS In this section,we give a comprehensive theoretical analysis CragMap M(K Tselect +TQuery TRN16) on the performance of TagMap compared with the traditional M=「nlog2e·log2(1/e)1≈[1.44nlog2(1/e)l (5) Q-Adaptive protocol K=ln2·(log2e·log2(1/e)l≈「0.99811og2(1/e)l Substituting M and K into CragMap,the above equation can A.Overhead Analysis on O-Adaptive Protocol be overwritten as follows: As aforementioned,the current mainstream RFID readers CTagMap(n,e)=[1.44nlog2(1/e)1([0.998110g2(1/e)1.Tselect use the Q-Adaptive protocol to collect all tags'EPCs.The +TQuery TRN16) Q-Adaptive is a variant of framed slotted ALOAH (FSA) Apart from the number of tags,the overhead of TagMap is protocol.Unlike the traditional FSA,it attempts to adjust the also related to the tolerance (i.e.,E). frame length adaptively to maintain a high probability that a tag is successfully identified in a frame.We have already given the theoretical analysis of Q-Adaptive in our prior work [45]. C.Overhead Comparison For clarity,we directly present the result as below. According to Gen2,we have the following estimated pa- rameter settings: Lemma 3.The protocol of Q-Adaptive requires about neln(n)time slots to collect n tags'EPCs in an optimal Tselect =91 bits,TQuery =37 bits,TQueryAdjust =15 bits condition. TRN16 =22 bits,TAck 25 bits,TEPC 134 bits The proof of the above lemma can be referred to our prior It is worth noting that:(1)the bit rates in the uplink (Tag- work [45].Specifically,keeping the optimal frame length,Reader)and downlink (Reader-Tag)are not exactly same. the protocol must start a new frame anytime when a tag Both are determined by the user settings.For the sake of

IEEE/ACM TRANSACTIONS ON NETWORKING 8 0 1 0 0 1 0 0 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 0 1 0 11 12 13 14 1 0 1 0 0 11 12 13 14 15 0 15 Moving forward Truncated bits M bits M c bits Fig. 11: The design of modulo. Suppose the optimal size of the BF is 11, the reader builds 2 dlog2 11e = 16 bit BF and moves the last 5 bits to align with the first five. -th intercepted inventory. In other words, if a tag is supposed to be hashed into the bit greater than or equal to Mc, then the tag is moved to reply at (m mod M) th bit-inventory. As illustrated in Fig. 11, the modulo moves the replies at the bits equal to or greater than Mc ahead to align with the first bits. Correspondingly, the question of presence turns to: Problem 3. Is there any tag whose sub-bitstring ∈ [r1, r1+l), . . . , or ∈ [rK, rK +l) in its MemBank3 is equal to m, m+Mc, m + 2Mc, . . . , or m + b M MccMc? Therefore, for the mth bit, the reader initiates an intercepted inventory, which contains multiple Selects as follows: S(r1, l, m), S(r2, l, m), . . . , S(rK, l, m) . . . . . . S(r1, l, m + b M Mc cMc), S(r2, l, m + b M Mc cMc), . . . , S(rK, l, m + b M Mc cMc) It is worthing noting the modulo operation would increase the number of tags hashed into the head bits, breaking the randomness of BF. If the upper-layer application requires a strong randomness, a good way is to move truncated bit (i.e., indexes ≥ Mc) forward to a random index less than Mc while the reader labels the mapping between the tags and bits so the application can predicate the hashing. V. ANALYSIS In this section, we give a comprehensive theoretical analysis on the performance of TagMap compared with the traditional Q-Adaptive protocol. A. Overhead Analysis on Q-Adaptive Protocol As aforementioned, the current mainstream RFID readers use the Q-Adaptive protocol to collect all tags’ EPCs. The Q-Adaptive is a variant of framed slotted ALOAH (FSA) protocol. Unlike the traditional FSA, it attempts to adjust the frame length adaptively to maintain a high probability that a tag is successfully identified in a frame. We have already given the theoretical analysis of Q-Adaptive in our prior work [45]. For clarity, we directly present the result as below. Lemma 3. The protocol of Q-Adaptive requires about ne ln(n) time slots to collect n tags’ EPCs in an optimal condition. The proof of the above lemma can be referred to our prior work [45]. Specifically, keeping the optimal frame length, the protocol must start a new frame anytime when a tag is identified. Thus, the whole procedure totally contains n frames, n long slots, and ne ln(n) − n short slots. As shown in Fig. 2, a long time slot in which only a single tag intends to transmit is EPC, is reserved for the transmissions of a QueryAdjust, an RN16, an ACK, and an EPC; a short time slot in which no tags respond or multiple tags’ signals are collided, is reserved for the transmissions of a QueryAdjust and an RN16. Thus, the totally time overhead taken by Q￾Adaptive, denoted by CQ-Adaptive, can be computed as follows:    CQ-Adaptive = nTL + (ne ln n − n)TS + nTDelay TL = TQuery + TRN16 + TAck + TEPC TS = TQueryAdjust + TRN16 (4) where TL and TS are the sizes of a long time slot and a short time slot respectively. According to our prior study [45], the commercial readers require to reserve TDelay seconds in the beginning of each frame for some pre-arranged tasks, such as synchronization, clearing tag states, adjustment of frame length, etc. Since n frames are required, the total extra time consumption is nTDelay. The other time symbols TXXX denotes the time consumed on the corresponding reader commands or the tag reply. For example, TQuery denotes the time cost for transmitting a reader command of Query. Finally, the total overhead taken by the Q-Adaptive is given by CQ-Adaptive(n) = n(TDelay + TQuery + TRN16 + TAck + TEPC) + (ne ln n − n)(TQueryAdjust + TRN16) Cleary, the overhead is only related to the total number of tags (i.e., n) in the scanning field. B. Overhead Analysis on TagMap Unlike the Q-Adaptive, all time slots in TagMap are equal in size. The collection procedure totally contains M slots, each of which is reserved for the transmissions of K Selects, a Query and an RN16. Thus, the total time overhead taken by TagMap, denoted by CTagMap, can be computed as follows:    CTagMap = M(K · TSelect + TQuery + TRN16) M = dn log2 e · log2 (1/ε)e ≈ d1.44n log2 (1/ε)e K = dln 2 · (log2 e · log2 (1/ε))e ≈ d0.9981 log2 (1/ε)e (5) Substituting M and K into CTagMap, the above equation can be overwritten as follows: CTagMap(n, ε) = d1.44n log2 (1/ε)e(d0.9981 log2 (1/ε)e · TSelect + TQuery + TRN16) Apart from the number of tags, the overhead of TagMap is also related to the tolerance (i.e., ε). C. Overhead Comparison According to Gen2, we have the following estimated pa￾rameter settings: TSelect = 91 bits, TQuery = 37 bits, TQueryAdjust = 15 bits TRN16 = 22 bits, TAck = 25 bits, TEPC = 134 bits It is worth noting that: (1) the bit rates in the uplink (Tag→ Reader) and downlink (Reader→Tag) are not exactly same. Both are determined by the user settings. For the sake of

IEEE/ACM TRANSACTIONS ON NETWORKING 9 03 high accuracy is required,the traditional per-tag collection 02 should be used. 0.2 G=1.0 2)The tolerance is the leading factor that affects the per- =0.13 0.15 formance of TagMap.Particularly,when the s>0.13, 0.1 TagMap performs always better than the Q-Adaptive re- 0.0 gardless of how many tags participate.By contrast,the 200300 0mte6igstmo00o0 5000 number of tags has a relatively limited impact on the performance than the tolerance.For example,TagMap is Fig.12:The overhead ratio of TagMap to Q-Adaptive.The performance of TagMap is better than Q-Adaptive when the radio still better than Q-Adaptive with a very small number G0.13.On the other regardless of how many tags participate when the tolerance>0.13. hand,the overhead ratio is linearly reduced approximately as the number of tags increases,namely,the earnings of clarity,we assume they are approximately equal;(2)the length TagMap are higher in handling a large number of tags, of an EPC is 96 bits but its transmission involves a 22-bit when remaining the tolerance unchanged. preamble and a 16-bit CRC;(3)the guard intervals between In summary,the use of Bloom filter with TagMap has the commands and replies are ignored because they are extremely applicable limits.The performance might be worse than col- small compared with the intervals of data transmissions;(4) lecting tags one by one when pursuing a higher accuracy.In the lengths of some commands with variable fields (like this situation,we advise to automatically switch the system Select and Query)are estimated using the average. back to the traditional mode Approximately,it takes about 25us for the transmission of each bit.The delay (i.e.,TDelay)in commercial readers VI.SYSTEM IMPLEMENTATION (e.g..ImpinJ R420)is around 30 ms based on our empirical A.TagMap Reader measurements.Substituting the above parameters into Egn.5 and Eqn.6 respectively,the two precise cost formulas are We implement a prototype of TagMap reader by using finally updated as follows: a USRP N210 software defined radio equipped with SBX daughterboard [51]and two directional antennas.The imple- C0Adpe(n)=(3000+(37+22+25+134)·25)·n mentation is based on [52]and integrates TagMap's design +(37+25)·(ne In n-n).25 into the EPC Gen2 protocol.We release the source code of =8450n+1550(ne1nn-n) TagMap [53].The architecture of the TagMap reader is shown CTaMap(n,e)=「1.44n1og2(1/e)1(「0.99811og2(1/e)1·91+37+22)·25 in Fig.13. =「1.44n1og2(1/e)1(f0.99811og2(1/e)1·91+59)·25 Architecture.The TagMap reader consists of the follow- To quantify how n and s affect the performance of TagMap,we ing components:USRP Source,Gate,Tag Decoder,Reader define the overhead ratio of TagMap to Q-Adaptive,denoted Encoder and USRP Sink. by G(n,)as follows: USRP Source:The first block is to acquire samples from G(n,e）=CgMp(m,e) the USRP hardware.In our experiment,the ADC is set to Co-Ad山ptie(n)】 (6) 2MS/s,resulting in 50 samples for each tag bit. = [1.44n1og2(1/e)1(f0.99811og2(1/e)1·91+59)·25 8450n+1550(ne In n-n) Gate:The reader always provides continuous signals to tags,thus is full duplex (i.e.,transmitting and receiving Apparently,TagMap performs better than Q-Adaptive only simultaneously).This block is used to track the Query and when and only when the G(n,s)<1.0;otherwise,the best Ack commands,and trigger the processing of tags'replies solution is to collect all tags one by one with the Q-Adaptive. Tag Decoder:This block is to detect tags'RN16 reply sig- Fig.12 shows the results of the overhead ratio as functions nals like preamble correlation,synchronization and channel of a variable number of tags (i.e.,100 <n 10000)and a estimation. variable tolerance (i.e.,0<<1).From the figure,we have Reader Encoder:This block is to implement the reader the two important findings: commands.Depending on the output of the tag decoder 1)TagMap performs better than Q-Adaptive in the white block,the reader create the next commands.Although this area where the smallest tolerance is set to 0.07.This work only requires the commands of Select and Query, suggests that the tolerance cannot be too small.This result we implement all other Gen2 commands (i.e.,QueryRep, is reasonable because the philosophy behind Bloom filter QueryAdust,Ack),as well as the Q-adaptive algorithm. is to save the procedure in time or space at the cost of USRP Sink:This block is to propagate the reader command accuracy [46].It is suitable for the application scenarios to the USRP hardware.We set the UHD gain of USRP to 20 which can tolerate a relatively higher false positive rate dB at a frequency during 902~928 MHz.We utilize a RF In our scenario like the detection of missing tags,the amplifier to increase the transmitting power to 30 dBm.The system would acquire the Bloom filter repeatedly.Even ADC rate is configured to 2 MS/s. using a relatively higher tolerance (e.g.,=0.25),the Transmission.The EPC Gen2 requires a reader to contin- tag can be identified within two rounds with an extremely uously generate a high-power CW.Two links are involved. high probability (e.g.,1-0.25 *0.25 =0.9375).Thus,The first link is data transmission from reader-tag,which the tolerance of 0.25 is acceptable.However,when a is often called downlink transmission.The second link is the

IEEE/ACM TRANSACTIONS ON NETWORKING 9 100 200 300 500 1000 2000 3000 5000 10000 Number of tags (n) 0.05 0.1 0.15 0.2 0.25 0.3 Tolerance ( ) 0 0.5 1 1.5 2 2.5 3 3.5 G=0.5 G=1.0 " =0.13 " =0.07 Fig. 12: The overhead ratio of TagMap to Q-Adaptive. The performance of TagMap is better than Q-Adaptive when the radio G 0.13. clarity, we assume they are approximately equal; (2) the length of an EPC is 96 bits but its transmission involves a 22-bit preamble and a 16-bit CRC; (3) the guard intervals between commands and replies are ignored because they are extremely small compared with the intervals of data transmissions; (4) the lengths of some commands with variable fields (like Select and Query) are estimated using the average. Approximately, it takes about 25µs for the transmission of each bit. The delay (i.e., TDelay) in commercial readers (e.g., ImpinJ R420) is around 30 ms based on our empirical measurements. Substituting the above parameters into Eqn. 5 and Eqn. 6 respectively, the two precise cost formulas are finally updated as follows: CQ-Adaptive(n) = (3000 + (37 + 22 + 25 + 134) · 25) · n + (37 + 25) · (ne ln n − n) · 25 = 8450n + 1550(ne ln n − n) CTagMap(n, ε) = d1.44n log2 (1/ε)e (d0.9981 log2 (1/ε)e · 91 + 37 + 22) · 25 = d1.44n log2 (1/ε)e (d0.9981 log2 (1/ε)e · 91 + 59) · 25 To quantify how n and ε affect the performance of TagMap, we define the overhead ratio of TagMap to Q-Adaptive, denoted by G(n, ε), as follows: G(n, ε) = CTagMap(n, ε) CQ-Adaptive(n) = d1.44n log2 (1/ε)e (d0.9981 log2 (1/ε)e · 91 + 59) · 25 8450n + 1550(ne ln n − n) (6) Apparently, TagMap performs better than Q-Adaptive only when and only when the G(n, ε) 0.13, TagMap performs always better than the Q-Adaptive re￾gardless of how many tags participate. By contrast, the number of tags has a relatively limited impact on the performance than the tolerance. For example, TagMap is still better than Q-Adaptive with a very small number of tags (e.g., n 0.13. On the other hand, the overhead ratio is linearly reduced approximately as the number of tags increases, namely, the earnings of TagMap are higher in handling a large number of tags, when remaining the tolerance unchanged. In summary, the use of Bloom filter with TagMap has the applicable limits. The performance might be worse than col￾lecting tags one by one when pursuing a higher accuracy. In this situation, we advise to automatically switch the system back to the traditional mode . VI. SYSTEM IMPLEMENTATION A. TagMap Reader We implement a prototype of TagMap reader by using a USRP N210 software defined radio equipped with SBX daughterboard [51] and two directional antennas. The imple￾mentation is based on [52] and integrates TagMap’s design into the EPC Gen2 protocol. We release the source code of TagMap [53]. The architecture of the TagMap reader is shown in Fig. 13. Architecture. The TagMap reader consists of the follow￾ing components: USRP Source, Gate, Tag Decoder, Reader Encoder and USRP Sink. • USRP Source: The first block is to acquire samples from the USRP hardware. In our experiment, the ADC is set to 2MS/s, resulting in 50 samples for each tag bit. • Gate: The reader always provides continuous signals to tags, thus is full duplex (i.e., transmitting and receiving simultaneously). This block is used to track the Query and Ack commands, and trigger the processing of tags’ replies. • Tag Decoder: This block is to detect tags’ RN16 reply sig￾nals like preamble correlation, synchronization and channel estimation. • Reader Encoder: This block is to implement the reader commands. Depending on the output of the tag decoder block, the reader create the next commands. Although this work only requires the commands of Select and Query, we implement all other Gen2 commands (i.e., QueryRep, QueryAdust, Ack), as well as the Q-adaptive algorithm. • USRP Sink: This block is to propagate the reader command to the USRP hardware. We set the UHD gain of USRP to 20 dB at a frequency during 902 ∼ 928 MHz. We utilize a RF amplifier to increase the transmitting power to 30 dBm.The ADC rate is configured to 2 MS/s. Transmission. The EPC Gen2 requires a reader to contin￾uously generate a high-power CW. Two links are involved. The first link is data transmission from reader → tag, which is often called downlink transmission. The second link is the

IEEE/ACM TRANSACTIONS ON NETWORKING 10 TABLE I:Summary of Gen2-compatible Tags Approach Function ImpinJ Monza series Alien ALN series NXP Tash r D E QT X-2K X-8K R6 9662 961097269820 9715 9716 U7xm 12C DNA MI (bits) 128 496 128 128 128/96 96 128 96-480 128 128 128 128 448 160 224 M3 (hits 32 1285122176 8192 512 512 128 128 128 128 2.0483.328 3.072 W/S/Q/R Truncate + + (1)'*'denotes this function is essential to Tash or TagMap;(2)''or'x'denote that this function is available or unavailable on tag:(3)W/S/Q/R denotes the commands of Write,Select,Query and RN16 respectively.(4)Ml and M3 denote memory bank 1(EPC memory)and memory bank 3(user defined memory). Applications bits,but the de facto standard remains 128 bits.In particular, the Monza serials of tags from ImpinJ were firstly release in2005[54]. All query related commands such as Select,Query and Gate Tag Reade RN16 are serviceable by all of the investigated tags.The Encoder Truncate is dispensable to Tash.Our real tests suggest that no Truncate-supportable tags in the market are Fig.13:TagMap reader architecture.The reader allows upper-layer application to provide a JSON-like configuration file and outputs the available currently,even though this is a mandatory function acquired BF in result file in the Gen2 protocol.This confines the effectiveness of Tash [43]in reality.However,TagMap leverages RN16 as opposite,which is called as uplink transmission.Both links presence signals and does not rely on this function.Thus, modulate data by OOK (i.e.,changing the amplitudes of the TagMap is universally applicable to today's commercial CW),but involve different channel coding methods. tags. Downlink (reader-tag):A reader encodes the data bits In summary,TagMap is perfectly compatible with the Gen2 using Pulse-Interval Encoding (PIE)for the downlink.The protocol and serves almost all of today's commercial tags even PIE coding has three user-defined parameters:Tari,Pw those released 13 years ago. (Pulse Width)and x.The Tari is the reference interval for the downlink signaling.Pw indicates the time duration C.Application Program Interface of the lower edge,which can be set to a value between For the sake of simplicity,the TagMap reader interacts 0.265Tari and 0.625Tari but is capped at 2us.The with upper applications through the file system.Applications duration of the bit '1'is x-us longer than that of bit 0' write parameters of each intercepted inventory into a JSON- and X must be between 0.5Tari and Tari.The downlink formatted setting file Code 1.In particular,the codes between rate varies between 27Kbps and 128Kbps with respect to the line 4 ~13 define two Select commands with different parameter choice.In our test,for the max-throughout,we pointers(i.e.,the random numbers).The reader encoder begins set above three parameters to 6.25us0.3Ti(1.87)to schedule the intercepted inventory based on the settingfile and 0.5Tari (3.125us). every time when it detects a change of the file.Majority of Uplink (tagreader):A tag uses either FMO or Miller signal processing is performed in GNURadio host computer. coding [47],both of which are highly similar to PIE.We The reader outputs decoded BFs into a "result"file,from omit their coding details because tags cannot be controlled which the upper applications can obtain the bitmap and meta in our design. data (time stamp,etc). 2{//Settings of an intercepted inventory B.Serviceability of Commercial Tags 3 "Select":【{ We investigate mainstream RFID tags in today's market "MEMBANK"[1,1],//MemBank3 in terms of their serviceability to the Gen2 commands that "P0 INTER":[0,0,0,0,0,0,1,1], "LENGTH":[0,0,0,0,0,0,1,1], TagMap and Tash require.For commercial interests,readers "MASK":[1,0,1] and tags are usually designed separately and produced by different manufactures.The Gen2 protocol is the glue that "MEMBANK"[1,1], adheres the two actors.We use our USRP reader to test 40 10 "P0 INTER":[0,0,0,0,1,0,0,1], 11 types of tag chips from ImpinJ [48].Alien [49]and NXP [50], "LENGTH":[0,0,0,0,0,0,1,1], "MASK":[1,0,1] which occupy majority of today's RFID market [1].Due to the 13 H. limited space,we only list the results of 15 basic models in "Query": Table.I as example,and will release the entire white paper on "SEL":[1,1],//Query all selected tags our website soon(for anonymity).We have the observations: 16 "SESSION":[0,0],//Inventory session "Q":[0,0,0,1]//set frame length to 1 Both TagMap and Tash require MemBank3 to store hash 18 values.The investigation suggests that 39/40=97.5%types 19 of tags serve to write to and read from their MemBank3. 20 The exception is ImpinJ Monza R6,which is read only.The Code 1:Program interface memory size of MemBank3 fluctuates around 32~3,328

IEEE/ACM TRANSACTIONS ON NETWORKING 10 TABLE I: Summary of Gen2-compatible Tags Approach Function ImpinJ Monza series Alien ALN series NXP Tash Ours D E QT X-2K X-8K R6 9662 9610 9726 9820 9715 9716 U7xm I2C DNA ? ? M1 (bits) 128 496 128 128 128/96 96 128 96-480 128 128 128 128 448 160 224 ? ? M3 (bits) 32 128 512 2176 8192 × 512 512 128 128 128 128 2,048 3,328 3,072 ? ? W/S/Q/R X X X X X × X X X X X X X X X ? – Truncate × × × × × × × × × × × × × × × (1) ‘?’ denotes this function is essential to Tash or TagMap; (2) ‘X’ or ‘×’ denote that this function is available or unavailable on tag; (3) W/S/Q/R denotes the commands of Write, Select, Query and RN16 respectively. (4) M1 and M3 denote memory bank 1 (EPC memory) and memory bank 3 (user defined memory). Host USRP Source Matched Filter Gate USRP Sink Tag Decoder Reader Encoder BF Configure Applications Fig. 13: TagMap reader architecture. The reader allows upper-layer application to provide a JSON-like configuration file and outputs the acquired BF in result file. opposite, which is called as uplink transmission. Both links modulate data by OOK (i.e., changing the amplitudes of the CW), but involve different channel coding methods. • Downlink (reader → tag): A reader encodes the data bits using Pulse-Interval Encoding (PIE) for the downlink. The PIE coding has three user-defined parameters: Tari, PW (Pulse Width) and X. The Tari is the reference interval for the downlink signaling. PW indicates the time duration of the lower edge, which can be set to a value between 0.265Tari and 0.625Tari but is capped at 2µs. The duration of the bit ‘1’ is X-µs longer than that of bit ‘0’ and X must be between 0.5Tari and Tari. The downlink rate varies between 27Kbps and 128Kbps with respect to the parameter choice. In our test, for the max-throughout, we set above three parameters to 6.25µs, 0.3Tari (1.875µs) and 0.5Tari (3.125µs). • Uplink (tag → reader): A tag uses either FM0 or Miller coding [47], both of which are highly similar to PIE. We omit their coding details because tags cannot be controlled in our design. B. Serviceability of Commercial Tags We investigate mainstream RFID tags in today’s market in terms of their serviceability to the Gen2 commands that TagMap and Tash require. For commercial interests, readers and tags are usually designed separately and produced by different manufactures. The Gen2 protocol is the glue that adheres the two actors. We use our USRP reader to test 40 types of tag chips from ImpinJ [48], Alien [49] and NXP [50], which occupy majority of today’s RFID market [1]. Due to the limited space, we only list the results of 15 basic models in Table. I as example, and will release the entire white paper on our website soon (for anonymity). We have the observations: • Both TagMap and Tash require MemBank3 to store hash values. The investigation suggests that 39/40 = 97.5% types of tags serve to write to and read from their MemBank3. The exception is ImpinJ Monza R6, which is read only. The memory size of MemBank3 fluctuates around 32 ∼ 3, 328 bits, but the de facto standard remains 128 bits. In particular, the Monza serials of tags from ImpinJ were firstly release in 2005 [54]. • All query related commands such as Select, Query and RN16 are serviceable by all of the investigated tags. The Truncate is dispensable to Tash. Our real tests suggest that no Truncate-supportable tags in the market are available currently, even though this is a mandatory function in the Gen2 protocol. This confines the effectiveness of Tash [43] in reality. However, TagMap leverages RN16 as presence signals and does not rely on this function. Thus, TagMap is universally applicable to today’s commercial tags. In summary, TagMap is perfectly compatible with the Gen2 protocol and serves almost all of today’s commercial tags even those released 13 years ago. C. Application Program Interface For the sake of simplicity, the TagMap reader interacts with upper applications through the file system. Applications write parameters of each intercepted inventory into a JSON￾formatted setting file Code 1. In particular, the codes between line 4 ∼ 13 define two Select commands with different pointers (i.e., the random numbers). The reader encoder begins to schedule the intercepted inventory based on the setting file, every time when it detects a change of the file. Majority of signal processing is performed in GNURadio host computer. The reader outputs decoded BFs into a “result” file, from which the upper applications can obtain the bitmap and meta data (time stamp, etc). 1.... 2 {//Settings of an intercepted inventory 3 "Select": [{ 4 "MEMBANK":[1, 1], //MemBank3 5 "POINTER":[0, 0, 0, 0, 0, 0, 1, 1], 6 "LENGTH":[0, 0, 0, 0, 0, 0, 1, 1], 7 "MASK":[1, 0, 1] 8 },{ 9 "MEMBANK":[1, 1], 10 "POINTER":[0, 0, 0, 0, 1, 0, 0, 1], 11 "LENGTH":[0, 0, 0, 0, 0, 0, 1, 1], 12 "MASK":[1, 0, 1] 13 }], 14 "Query": { 15 "SEL":[1,1],//Query all selected tags 16 "SESSION":[0,0],//Inventory session 17 "Q":[0,0,0,1] //Set frame length to 1 18 } 19 } 20... Code 1: Program interface