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 ofIEEE/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