P-MTI:Physical-layer Missing Tag Identification via Compressive Sensing Yuanging Zheng,Mo Li School of Computer Engineering,Nanyang Technological University,Singapore [yuanqing1,limo}@ntu.edu.sg Abstract-RFID systems are emerging platforms that support rely on upper layer information,rendering them less efficient a variety of pervasive applications.The problem of identifying for realtime monitoring. missing tag in RFID systems has attracted wide attention due to its practical importance.This paper presents P-MTI:a Physical- The compelling practical demands and the inadequacy of the layer Missing Tag Identification scheme which effectively makes status quo motivate the design of more efficient missing tag use of the lower layer information and dramatically improves identification schemes.In this paper,we present Physical-layer operational efficiency.Unlike conventional approaches,P-MTI Missing Tag Identification(P-MTI)which efficiently utilizes looks into the aggregated responses instead of focusing on the physical layer information of tag responses and thereby individual tag responses and extracts useful information from physical layer symbols.P-MTI leverages the sparsity of missing substantially improves the monitoring efficiency.Unlike con- tag events and reconstructs tag responses through compressive ventional approaches focusing on individual tag responses,we sensing.We implement P-MTI and prototype the system based on look into the aggregated signals from concurrent tag responses the USRP software defined radio and Intel WISP platform which which provides us much richer information. demonstrates the efficacy.We also evaluate the performance Say that we wish to identify K missing tags out of N, of P-MTI with extensive simulations and compare with previ- ous approaches under various scenarios.The evaluation shows where NK>0.We let each tag i transmit a sequence promising results of P-MTI in terms of identification accuracy, of M random bits A;concurrently with other tags.Each time efficiency,as well as robustness over noisy channels. tag i transmits one bit of A;at each time slot.The tags modulate the bits into physical layer symbols using simple I.INTRODUCTION on-off keying.In physical layer,the transmitted symbols from multiple tags will mix in the air and arrive at the reader as Radio Frequency Identification(RFID)systems are becom- PHY symbol superpositions.In the jth time slot the reader ing important platforms that enable ultra-low power ubiquitous receivesA().and thus after M time slots the computing [18,31].RFID tags harvest energy from high power received symbols at the reader y can be concisely represented RF signals of a nearby RFID reader.A tag can switch the asy=Ax,where M×V matrix A=[A1,A2,·,Aw]- reflection coefficients of its antenna to backscatter or absorb y denotes an M x 1 vector where each entry represents one the RF signals to send one-bit 0/1 information achieving ultra- of the M PHY symbol measurements.x denotes an N x 1 low power communication.Due to the small form factor and binary vector where the non-zero entries indicate presence low manufacturing costs of RFID tags,RFID systems make of tags while the zero entries imply the missing tags.For them ideal for massive object management in a variety of ease of presentation,here we omit channel coefficients.To applications [11,33]. compute x and figure out the K zero entries,generally we The problem of missing tag identification has attracted wide need M=N measurements.As a matter of fact,it suffices attention due to its practical importance [16,28].For example, for identifying the missing tags to know the differential of RFID tags can be attached to items as labels in a warehouse, two consecutive instances,xA =Xt-x-A,where K non- and RFID readers can monitor them for anti-theft purpose. zero entries in x indicate the missing tags.As the differential Such a problem of item-level monitoring also appears in of the two consecutive responses y=AxA,which can be applications of healthcare,logistics,military,etc.When the formulated as a standard compressive sensing problem [12]. number of tags is small,one may frequently identify all the we can efficiently recover x with only a substantially smaller tags and check if anyone is missing.When the number of tags number of measurements. scales up,tag-tag collisions become increasingly severe and We implement a prototype system and validate P-MTI render collision arbitration schemes highly inefficient. design based on the Universal Software Radio Peripheral Recently,many novel protocols have been proposed to (USRP)software defined radio with the Intel Wireless Iden- detect the missing tag events.Typically.those approaches tification and Sensing Platform(WISP)programmable RFID iterate over individual tag responses for identifying the missing tags.We also investigate our approach in large-scale settings tags.Due to the inherent nature of sequential look-up,conven-with extensive simulations compared with existing approaches tional approaches consume a substantial number of time slots [16,28].The experiment results show that the proposed P- that is linearly proportional to the total number N of tags. MTI scheme significantly improves the time efficiency.In Although many advances have been made,such approaches particular,P-MTI can effectively reduce the transmission time largely overlook the physical layer information and merely by approximately 65%over state-of-the-art approaches.TheP-MTI: Physical-layer Missing Tag Identification via Compressive Sensing Yuanqing Zheng, Mo Li School of Computer Engineering, Nanyang Technological University, Singapore {yuanqing1, limo}@ntu.edu.sg Abstract—RFID systems are emerging platforms that support a variety of pervasive applications. The problem of identifying missing tag in RFID systems has attracted wide attention due to its practical importance. This paper presents P-MTI: a Physical￾layer Missing Tag Identification scheme which effectively makes use of the lower layer information and dramatically improves operational efficiency. Unlike conventional approaches, P-MTI looks into the aggregated responses instead of focusing on individual tag responses and extracts useful information from physical layer symbols. P-MTI leverages the sparsity of missing tag events and reconstructs tag responses through compressive sensing. We implement P-MTI and prototype the system based on the USRP software defined radio and Intel WISP platform which demonstrates the efficacy. We also evaluate the performance of P-MTI with extensive simulations and compare with previ￾ous approaches under various scenarios. The evaluation shows promising results of P-MTI in terms of identification accuracy, time efficiency, as well as robustness over noisy channels. I. INTRODUCTION Radio Frequency Identification (RFID) systems are becom￾ing important platforms that enable ultra-low power ubiquitous computing [18, 31]. RFID tags harvest energy from high power RF signals of a nearby RFID reader. A tag can switch the reflection coefficients of its antenna to backscatter or absorb the RF signals to send one-bit 0/1 information achieving ultra￾low power communication. Due to the small form factor and low manufacturing costs of RFID tags, RFID systems make them ideal for massive object management in a variety of applications [11, 33]. The problem of missing tag identification has attracted wide attention due to its practical importance [16, 28]. For example, RFID tags can be attached to items as labels in a warehouse, and RFID readers can monitor them for anti-theft purpose. Such a problem of item-level monitoring also appears in applications of healthcare, logistics, military, etc. When the number of tags is small, one may frequently identify all the tags and check if anyone is missing. When the number of tags scales up, tag-tag collisions become increasingly severe and render collision arbitration schemes highly inefficient. Recently, many novel protocols have been proposed to detect the missing tag events. Typically, those approaches iterate over individual tag responses for identifying the missing tags. Due to the inherent nature of sequential look-up, conven￾tional approaches consume a substantial number of time slots that is linearly proportional to the total number N of tags. Although many advances have been made, such approaches largely overlook the physical layer information and merely rely on upper layer information, rendering them less efficient for realtime monitoring. The compelling practical demands and the inadequacy of the status quo motivate the design of more efficient missing tag identification schemes. In this paper, we present Physical-layer Missing Tag Identification (P-MTI) which efficiently utilizes the physical layer information of tag responses and thereby substantially improves the monitoring efficiency. Unlike con￾ventional approaches focusing on individual tag responses, we look into the aggregated signals from concurrent tag responses which provides us much richer information. Say that we wish to identify K missing tags out of N, where N  K ≥ 0. We let each tag i transmit a sequence of M random bits Ai concurrently with other tags. Each tag i transmits one bit of Ai at each time slot. The tags modulate the bits into physical layer symbols using simple on-off keying. In physical layer, the transmitted symbols from multiple tags will mix in the air and arrive at the reader as PHY symbol superpositions. In the jth time slot the reader receives yj = PN i=1 Ai(j), and thus after M time slots the received symbols at the reader y can be concisely represented as y = Ax, where M × N matrix A = [A1, A2, . . . , AN ]. y denotes an M × 1 vector where each entry represents one of the M PHY symbol measurements. x denotes an N × 1 binary vector where the non-zero entries indicate presence of tags while the zero entries imply the missing tags. For ease of presentation, here we omit channel coefficients. To compute x and figure out the K zero entries, generally we need M = N measurements. As a matter of fact, it suffices for identifying the missing tags to know the differential of two consecutive instances, x∆ = xt − xt−∆, where K non￾zero entries in x∆ indicate the missing tags. As the differential of the two consecutive responses y∆ = Ax∆, which can be formulated as a standard compressive sensing problem [12], we can efficiently recover x∆ with only a substantially smaller number of measurements. We implement a prototype system and validate P-MTI design based on the Universal Software Radio Peripheral (USRP) software defined radio with the Intel Wireless Iden￾tification and Sensing Platform (WISP) programmable RFID tags. We also investigate our approach in large-scale settings with extensive simulations compared with existing approaches [16, 28]. The experiment results show that the proposed P￾MTI scheme significantly improves the time efficiency. In particular, P-MTI can effectively reduce the transmission time by approximately 65% over state-of-the-art approaches. The