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