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.The
P-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 Physicallayer 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 previous 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 becoming 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 ultralow 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, conventional 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 conventional 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 nonzero 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 Identification 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 PMTI 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
improvement stems from both the efficient use of lower layer 1234567891011 information and the compressive sensing based information reconstruction. The contributions of this paper are briefly summarized as 。。 follows:For the first time,(1)this paper presents the physical ☐empty▣singleton☐collision layer missing tag identification scheme,which makes extensive Fig.1. Frame-slotted Aloha:7 tags contend for 11 time slots. use of lower layer information in large-scale RFID systems; (2)exploiting the sparsity of missing tag events,the proposed B.Problem description scheme further improves missing tag identification efficiency Consider an RFID system N {n1,n2,...,nN}repre- with compressive sensing technique;(3)we consolidate our senting all the N tags covered by a reader,and K N design with a prototype system using the software-defined representing the set of missing tags.The reader has the access RFID reader and the programmable tags. to the IDs of the tags,among which K tags are missing.The problem of missing tag identification is to identify the K missing tags.The missing tag set may be empty meaning that II.SYSTEM MODEL AND PROBLEM DESCRIPTION all the tags in N are present.We denote by the cardinality of a set,and thus K=K and N=N.In this paper,we A.System model particularly focus on the cases where NK>0.If most tags are missing and only a small number of tags are present, We consider an RFID system consisting of three main one may directly identify the present tags. components:a large number of RFID tags attached to items To ensure realtime monitoring,we need to reduce the under monitoring,one or more RFID readers that monitor the processing time of missing tag identification and design a tags,and a backend server that coordinates the readers through scalable scheme to support thousands or even more tags. reliable links.Commercial RFID readers (e.g.,Alien ALR As each tag has to transmit at least one-bit information to 9900+[1])connect via RS232 or Gigabit Ethernet to PCs, announce its presence,prior work believes that at least N which allows high throughput and low latency communication. time slots are needed to monitor N tags [16].Generally,such We focus on the communication between one RFID reader and schemes sequentially look up individual tag responses and large number of tags rather than the backend server.We also only differentiate the empty/sington/collision slots,meaning study parallel interrogation of multiple readers [281. that only log2 3 bits of information can be extracted per slot. In this paper,we exclusively focus on the RFID system Moreover,each tag transmits multiple physical layer symbols operating in the 900MHz Ultra-High Frequency (UHF)band. to allow the reader to distinguish the different types of slots. An RFID reader transmits high power radio frequency sig- To improve monitoring efficiency,in this work we wish to nals to energize RFID tags and initiates the interrogation. make extensive use of physical layer symbols by extracting RFID tags backscatter or absorb the signals to communicate more amount of information.On the other hand.as the tags with the reader (i.e.,on-off keying)according to the reader are generally resource-constrained,we wish to make slight command.Due to the constraints of transmission power,the updates to the protocol stack at tags without introducing extra communication bandwidth is generally narrow and thus can be computation or communication overhead mathematically modeled using a single complex number [23]. Following existing works [16,23,28],we assume that the III.P-MTI DESIGN uplink communication from tags to readers is synchronized by We first explain the rationale of P-MTI design (Section the readers.As the uplink data rate is low,the synchronization III-A).We present a basic solution which leverages the phys- among the tags can generally be achieved in practice [23]. ical layer information for missing tag identification(Section Such a system model has been adopted in many RFID systems III-B).We then explore the sparsity of missing tag events and compliant with the de facto EPCglobal Gen-2 standard [3]. use compressive sensing technique to enhance the missing tag The EPCglobal Gen-2 standard [3]specifies several manda- identification efficiency (Section III-C).We combine several tory operations to regulate the RFID tags,while providing optimization methods to achieve higher overall performance fexibility for RFID manufacturers to implement value-added (Section III-D and Section III-E).We finally discuss additional features.Such an open framework motivates novel designs to design considerations (Section III-F). meet practical needs with available components (e.g.,random number generator [3],lightweight hash function,etc).We A.P-MTI rationale note that such routine components are widely implemented The conventional schemes generally exploit the frame- in current RFID tags. slotted Aloha protocol to identify the missing tags [16,28]. In this paper we do not consider the case of malfunctioning Figure I illustrates an instance where 7 tags contend for RFID tags.A malfunctioning tag may not respond to reader's 11 time slots.Say that one tag should have responded in interrogation even within the communication range (due to a singleton slot (e.g.,the 7th time slot)if present,but no many possible physical failures on the tag).As such,we treat response is received from the time slot.Then the reader may every unresponsive tag as a missing tag.The root case of such infer that the tag is missing.In such schemes,less information missing tag events is beyond the scope of this paper. can be extracted from empty and collision slots.As each tag
improvement stems from both the efficient use of lower layer information and the compressive sensing based information reconstruction. The contributions of this paper are briefly summarized as follows: For the first time, (1) this paper presents the physical layer missing tag identification scheme, which makes extensive use of lower layer information in large-scale RFID systems; (2) exploiting the sparsity of missing tag events, the proposed scheme further improves missing tag identification efficiency with compressive sensing technique; (3) we consolidate our design with a prototype system using the software-defined RFID reader and the programmable tags. II. SYSTEM MODEL AND PROBLEM DESCRIPTION A. System model We consider an RFID system consisting of three main components: a large number of RFID tags attached to items under monitoring, one or more RFID readers that monitor the tags, and a backend server that coordinates the readers through reliable links. Commercial RFID readers (e.g., Alien ALR 9900+ [1]) connect via RS232 or Gigabit Ethernet to PCs, which allows high throughput and low latency communication. We focus on the communication between one RFID reader and large number of tags rather than the backend server. We also study parallel interrogation of multiple readers [28]. In this paper, we exclusively focus on the RFID system operating in the 900MHz Ultra-High Frequency (UHF) band. An RFID reader transmits high power radio frequency signals to energize RFID tags and initiates the interrogation. RFID tags backscatter or absorb the signals to communicate with the reader (i.e., on-off keying) according to the reader command. Due to the constraints of transmission power, the communication bandwidth is generally narrow and thus can be mathematically modeled using a single complex number [23]. Following existing works [16, 23, 28], we assume that the uplink communication from tags to readers is synchronized by the readers. As the uplink data rate is low, the synchronization among the tags can generally be achieved in practice [23]. Such a system model has been adopted in many RFID systems compliant with the de facto EPCglobal Gen-2 standard [3]. The EPCglobal Gen-2 standard [3] specifies several mandatory operations to regulate the RFID tags, while providing flexibility for RFID manufacturers to implement value-added features. Such an open framework motivates novel designs to meet practical needs with available components (e.g., random number generator [3], lightweight hash function, etc). We note that such routine components are widely implemented in current RFID tags. In this paper we do not consider the case of malfunctioning RFID tags. A malfunctioning tag may not respond to reader’s interrogation even within the communication range (due to many possible physical failures on the tag). As such, we treat every unresponsive tag as a missing tag. The root case of such missing tag events is beyond the scope of this paper. LoF PET FNEB 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 ZOE 1 empty singleton collision Fig. 1. Frame-slotted Aloha: 7 tags contend for 11 time slots. B. Problem description Consider an RFID system N = {n1, n2, . . . , nN } representing all the N tags covered by a reader, and K ⊆ N representing the set of missing tags. The reader has the access to the IDs of the tags, among which K tags are missing. The problem of missing tag identification is to identify the K missing tags. The missing tag set may be empty meaning that all the tags in N are present. We denote by | · | the cardinality of a set, and thus K = |K| and N = |N|. In this paper, we particularly focus on the cases where N K ≥ 0. If most tags are missing and only a small number of tags are present, one may directly identify the present tags. To ensure realtime monitoring, we need to reduce the processing time of missing tag identification and design a scalable scheme to support thousands or even more tags. As each tag has to transmit at least one-bit information to announce its presence, prior work believes that at least N time slots are needed to monitor N tags [16]. Generally, such schemes sequentially look up individual tag responses and only differentiate the empty/sington/collision slots, meaning that only log2 3 bits of information can be extracted per slot. Moreover, each tag transmits multiple physical layer symbols to allow the reader to distinguish the different types of slots. To improve monitoring efficiency, in this work we wish to make extensive use of physical layer symbols by extracting more amount of information. On the other hand, as the tags are generally resource-constrained, we wish to make slight updates to the protocol stack at tags without introducing extra computation or communication overhead. III. P-MTI DESIGN We first explain the rationale of P-MTI design (Section III-A). We present a basic solution which leverages the physical layer information for missing tag identification (Section III-B). We then explore the sparsity of missing tag events and use compressive sensing technique to enhance the missing tag identification efficiency (Section III-C). We combine several optimization methods to achieve higher overall performance (Section III-D and Section III-E). We finally discuss additional design considerations (Section III-F). A. P-MTI rationale The conventional schemes generally exploit the frameslotted Aloha protocol to identify the missing tags [16, 28]. Figure 1 illustrates an instance where 7 tags contend for 11 time slots. Say that one tag should have responded in a singleton slot (e.g., the 7th time slot) if present, but no response is received from the time slot. Then the reader may infer that the tag is missing. In such schemes, less information can be extracted from empty and collision slots. As each tag
Signal from tag 1 (a) tag1 ●Ah tag2 ● A2h2 0.2 tag3 A3ha ∑Ah Signal from tao 2 05 (b) reader tag7●Azh Fig.3.Response signals from 7 tags mix in the air and aggregate at the Aggregated signals reader.If tag i is missing,then its contribution to the aggregated physical 05 layer symbols would be missing 4 0.2 leverage the differences of physical layer symbols to detect 50 100 150 200 250 300 350 40 and identify the missing tags.Departing from conventional Time(us) schemes which look at individual tag response at each slot,P- Fig.2.Received signals at RFID reader:(a)Signals from tag 1:(b)Signals from tag 2;(c)Aggregated signals from the two tags. MTI allows multiple tags to concurrently respond in each time slot which fundamentally improves the protocol efficiency. has to transmit at least one-bit information to announce its B.Physical layer missing tag identification:a basic solution presence,prior work believes that at least N time slots are In P-MTI,an RFID reader initiates the missing tag mon- needed to monitor N tags [16].Although many advances have itoring by broadcasting an operation code.When receiving been achieved in missing tag identification [16,28],existing the command,each tag generates random bits using a pseudo approaches largely overlook the PHY information and merely random number generator with its ID as the seed.The pseudo extract limited amount of information at upper layer. random bits of tag i is denoted as A;,an M x 1 bit vector.At To fundamentally improve the protocol efficiency,we con- each time slot,each tag backscatters radio frequency signals duct initial experiments to explore the physical layer of RFID if the random bit turns out to be 1,or keep silent otherwise. system using the USRP software defined radio and the WISP The physical layer symbols from N tags mix in the air and programmable tags.Section IV presents the implementation aggregate at the reader.We model the RFID communication and experiment settings in detail.A PHY symbol can be channel with a complex matrix HNxN.Then the aggregated represented as a complex number(amplitude and phase com- symbols at the reader can be represented as follows. ponents).As RFID backscatter communication uses on-off keying(a simple amplitude-shift keying scheme),at physical y=AHx. (1) layer an RFID reader decodes tag responses by measuring only amplitude and ignoring phase component [3].Figure 2(a) where y is an M x 1 complex vector representing the aggre- shows the magnitude of backscatter signals received at the gated symbols,A is an Mx N binary matrix,and x is an N- USRP reader when one WISP tag (tag 1)transmits a sequence entry binary vector with non-zero (zero)entries representing of pseudo random bits using on-off keying.Similarly,Figure presence (absence)of tags.As the backscatter communication 2(b)depicts the signals from tag 2.The magnitude of received is generally within a narrow wireless band [23],the wireless signal depends on the wireless channel attenuation.The reader channel between each tag and the reader can be mathemat- can decode tag 1 and tag 2 individually when no collision ically modeled with a complex number,incorporating both occurs.When both tags transmit at the same time (Figure signal attenuation and phase shift of wireless channel [23]. 2(c)),we find that the aggregated PHY symbols exhibit as Therefore,we assume H =diag(h1,h2,...,hN),where hi the superposition of the symbols from both tags.When more denotes the channel coefficient from tag i to the reader.Thus tags respond concurrently,the responsive signals from multiple Hx can be represented with an Nx 1 complex vector z,where tags similarly exhibit as a sum when they arrive at the reader. the ith entry zi=hixi [23].As x is binary vector,we have We propose to efficiently utilize the aggregated signals from zi=hi if xi=1,andzi=0 otherwise.Hence,Eg.(1)can concurrent tag responses (which were previously treated as be rewritten as follows, collision slots),and present P-MTI which makes extensive use of such physical layer information. y=Az. (2) The rationale behind P-MTI is that the missing tags reveal Since the reader has access to the tag IDs through database themselves by the absences of responses.Say that there are lookups,the reader can generate the pseudo random binary 7 tags (ie.,tag 1-7),and we let them send random matrix A using the same random number generator with the bits concurrently as in Figure 3.The responses from tags tags IDs as seeds.Therefore,we can compute z by solving mix in the air and aggregate at the reader.The reader will the linear equation Eg.(2)with the knowledge of y and A. receive physical layer symbols from all the 7 tags if none is The non-zero entry zi=hi is the channel coefficient between missing.If any tags are missing,the received symbols may tag i and the reader.A zero entry zj=hj=0 in z indicates differ from the expected ones.We denote the symbols of that the corresponding tag is missing.In such a way,P-MTI tag i as Ai,and denote the channel coefficient as hi.The not only identifies missing tags but also measures the channel aggregated physical layer responses received by the reader 7 coefficients H between present tags and the reader. can be represented asAhi.If tag k is missing.the To solve the linear equation Eq.(2),we generally need N aggregated responses becomeAhA We can thus measurements of physical layer symbols,since the unknown z
0.2 0.3 0.4 0.5 Signal from tag 1 0.2 0.3 0.4 0.5 Signal from tag 2 0.2 0.3 0.4 0.5 0 50 100 150 200 250 300 350 400 (a) (b) (c) Time(us) Magnitude Aggregated signals Fig. 2. Received signals at RFID reader: (a) Signals from tag 1; (b) Signals from tag 2; (c) Aggregated signals from the two tags. has to transmit at least one-bit information to announce its presence, prior work believes that at least N time slots are needed to monitor N tags [16]. Although many advances have been achieved in missing tag identification [16, 28], existing approaches largely overlook the PHY information and merely extract limited amount of information at upper layer. To fundamentally improve the protocol efficiency, we conduct initial experiments to explore the physical layer of RFID system using the USRP software defined radio and the WISP programmable tags. Section IV presents the implementation and experiment settings in detail. A PHY symbol can be represented as a complex number (amplitude and phase components). As RFID backscatter communication uses on-off keying (a simple amplitude-shift keying scheme), at physical layer an RFID reader decodes tag responses by measuring only amplitude and ignoring phase component [3]. Figure 2(a) shows the magnitude of backscatter signals received at the USRP reader when one WISP tag (tag 1) transmits a sequence of pseudo random bits using on-off keying. Similarly, Figure 2(b) depicts the signals from tag 2. The magnitude of received signal depends on the wireless channel attenuation. The reader can decode tag 1 and tag 2 individually when no collision occurs. When both tags transmit at the same time (Figure 2(c)), we find that the aggregated PHY symbols exhibit as the superposition of the symbols from both tags. When more tags respond concurrently, the responsive signals from multiple tags similarly exhibit as a sum when they arrive at the reader. We propose to efficiently utilize the aggregated signals from concurrent tag responses (which were previously treated as collision slots), and present P-MTI which makes extensive use of such physical layer information. The rationale behind P-MTI is that the missing tags reveal themselves by the absences of responses. Say that there are 7 tags (i.e., tag 1 – 7), and we let them send random bits concurrently as in Figure 3. The responses from tags mix in the air and aggregate at the reader. The reader will receive physical layer symbols from all the 7 tags if none is missing. If any tags are missing, the received symbols may differ from the expected ones. We denote the symbols of tag i as Ai , and denote the channel coefficient as hi . The aggregated physical layer responses received by the reader can be represented as P7 i=1 Aihi . If tag k is missing, the aggregated responses become P7 i=1 Aihi−Akhk. We can thus FNEB O(n) 1 2 3 4 5 6 7 8 9 10 11 ZOE id1 id2 idn ... id3 id4 OR P P P P P P ZOE id1 id2 idn OR P P P P id3 P id4 ... P node4 A1h1 node1 node2 node3 A3h3 A A4h4 2h2 A1h1 node1 node2 A2h2 A4h4 node4 node3 A3h3 ∑Aihi node A1h1 1 node2 A2h2 A4h4 node4 node3 A3h3 ∑Aihi station node A1h1 1 node2 A2h2 A7h7 node7 node3 A3h3 ∑Aihi station ... ... tag A1h1 1 tag2 A2h2 A7h7 tag7 tag3 A3h3 ∑Aihi reader ... ... Fig. 3. Response signals from 7 tags mix in the air and aggregate at the reader. If tag i is missing, then its contribution to the aggregated physical layer symbols would be missing. leverage the differences of physical layer symbols to detect and identify the missing tags. Departing from conventional schemes which look at individual tag response at each slot, PMTI allows multiple tags to concurrently respond in each time slot which fundamentally improves the protocol efficiency. B. Physical layer missing tag identification: a basic solution In P-MTI, an RFID reader initiates the missing tag monitoring by broadcasting an operation code. When receiving the command, each tag generates random bits using a pseudo random number generator with its ID as the seed. The pseudo random bits of tag i is denoted as Ai , an M ×1 bit vector. At each time slot, each tag backscatters radio frequency signals if the random bit turns out to be 1, or keep silent otherwise. The physical layer symbols from N tags mix in the air and aggregate at the reader. We model the RFID communication channel with a complex matrix HN×N . Then the aggregated symbols at the reader can be represented as follows. y = AHx, (1) where y is an M × 1 complex vector representing the aggregated symbols, A is an M × N binary matrix, and x is an Nentry binary vector with non-zero (zero) entries representing presence (absence) of tags. As the backscatter communication is generally within a narrow wireless band [23], the wireless channel between each tag and the reader can be mathematically modeled with a complex number, incorporating both signal attenuation and phase shift of wireless channel [23]. Therefore, we assume H = diag(h1, h2, . . . , hN ), where hi denotes the channel coefficient from tag i to the reader. Thus Hx can be represented with an N ×1 complex vector z, where the ith entry zi = hixi [23]. As x is binary vector, we have zi = hi if xi = 1, and zi = 0 otherwise. Hence, Eq.(1) can be rewritten as follows, y = Az. (2) Since the reader has access to the tag IDs through database lookups, the reader can generate the pseudo random binary matrix A using the same random number generator with the tags IDs as seeds. Therefore, we can compute z by solving the linear equation Eq.(2) with the knowledge of y and A. The non-zero entry zi = hi is the channel coefficient between tag i and the reader. A zero entry zj = hj = 0 in z indicates that the corresponding tag is missing. In such a way, P-MTI not only identifies missing tags but also measures the channel coefficients H between present tags and the reader. To solve the linear equation Eq.(2), we generally need N measurements of physical layer symbols, since the unknown z
is an N x 1 vector.As the reader does not need to distinguish Leveraging the differential of aggregated responses, empty/singleton/collision slots,the tags do not need to transmit we improve the performance of P-MTI from O(N)to multiple physical layer symbols in each time slot,which can O(K log(N/K)).The compressive sensing based information further reduce the transmission time. reconstruction allows us to extract the missing tag events directly from the differential of aggregated physical layer C.Compressive sensing based recovery symbols,thereby significantly reducing the required total time slots compared with the existing schemes.Besides,unlike We notice that P-MTI needs N measurements per mon- existing schemes which need multiple physical symbols per itoring operation.In practical scenarios,one may need to slot,P-MTI needs only one symbol per time slot.Therefore, frequently run the missing tag identification protocol to ensure the performance gain of such joint optimization is promising a timely report of missing tag events. As a matter of fact,it suffices to compute the differential D.Enhancement against noisy measurement of aggregated responses between two consecutive instances The above analysis ignores the noise in measurements. to achieve continuous monitoring.The rationale is straight- Wireless channel is mostly error-prone,subjected to various forward:if a response from a tag is detected while no factors,such as interference,quantization,etc [8.Channel dy- more response is detected later from the tag,then the tag is namics may also introduce noise to the measurements.Without probably missing.We therefore compute the differential of robustness enhancement against noise,a detection system may the aggregated responses between two consecutive instances result in unfavorable false alarms over noisy channels [14].In at time t andt-△，ya=yt-yt-△，and infer the dynamics the following,we enhance P-MTI's robustness against noise of the tags.According to Eg.(2),we have based on the theory of stable recovery [9].Incorporating the noise,Eq.(4)can be rewritten as follows. y△=yt-yt-△=Azt-Azt-△ (3) We refer the differential of z similarly by ZA =Zt-Zt-A. y△=Aza+e, (6) Then,from Eq.(③)，we have where e denotes the error due to noise.Then the optimization y△=AzA. (4) problem with relaxed constraints for recovery of z can be written as follows. Ideally,the zero entries in ZA imply that corresponding tags are present,while the non-zero entries indicate that the tags are missing.In practical RFID systems,the number of missing Minimize:ZAle tags K is typically much smaller than the number of tags under Subject to:AZA -yallea 0 [16,28].In other words,z is K-sparse,meaning that theory of stable recovery [9]tells us that the solution Z to the there are at most K non-zero entries in ZA [12].According convex optimization problem (7)is a good approximation of to the theory of compressive sensing,the K'-sparse vector zA ZA,and IZ-Zl2 ce where c denotes a small constant. can be accurately recovered with only M=O(K log(N/K)) In other words.a small error in y only slightly influences measurements,by solving the following convex optimization reconstruction of zA.In order to identify missing tags,P- problem [12]. MTI only needs to distinguish the zero and non-zero entries in zA.The noise may disturb zA and render the zero entries Minimize:ZAlle in zA non-zero (yet remaining small),affacting the detection Subject to:AZA=yA, (5) accuracy.As the error is well bounded by the noise in practice, where denotes (norm.l) if the noise is small we can use a threshold a to accurately classify the contaminated signals with high probabilities.In Intuitively,the objective function of minimizingle in- particular,we define the detection function f(zA:)for tag i corporates the fact that zA is sparse,while the constraint as follows function is self-explanatory.Therefore,we can refer to convex optimization solvers (e.g.,CVX [2],E1-Magic [6])to compute Present,if ilez<0 ZA.In our implementation,we use the CVX solver [2]based f(z△i)= (8) Absent, otherwise. on the interior-point algorithm [7].It has been reported that M =3K4K N measurements suffice to recover the If the magnitude of zAi is smaller than 6,then tag i is K'-sparse vector [17].We set the number of measurements present;otherwise,we say tag i is absent.When the channel as M=CKMax log(N)in practice,where KMax represents condition dramatically deteriorates,the RFID reader cannot the estimated maximum number of missing tags and C is a always accurately identify the missing tags.In such scenarios, constant.Our experiment results show that M measurements the reader may use the basic P-MTI to identify the missing of physical layer symbols are sufficient to reconstruct the K-tags,and monitor the channel H.If the channel becomes sparse vector of zA.When the number of missing tags exceeds reasonably good and stable,P-MTI can switch back to monitor KMax,our approach can identify at least KMax missing tags,the differential and identify the missing tags.The reader which allows P-MTI to effectively adjust Kmax(Section V). may also increase transmission power to increase the signal
is an N ×1 vector. As the reader does not need to distinguish empty/singleton/collision slots, the tags do not need to transmit multiple physical layer symbols in each time slot, which can further reduce the transmission time. C. Compressive sensing based recovery We notice that P-MTI needs N measurements per monitoring operation. In practical scenarios, one may need to frequently run the missing tag identification protocol to ensure a timely report of missing tag events. As a matter of fact, it suffices to compute the differential of aggregated responses between two consecutive instances to achieve continuous monitoring. The rationale is straightforward: if a response from a tag is detected while no more response is detected later from the tag, then the tag is probably missing. We therefore compute the differential of the aggregated responses between two consecutive instances at time t and t − ∆, y∆ = yt − yt−∆, and infer the dynamics of the tags. According to Eq.(2), we have y∆ = yt − yt−∆ = Azt − Azt−∆. (3) We refer the differential of z similarly by z∆ = zt − zt−∆. Then, from Eq.(3), we have y∆ = Az∆. (4) Ideally, the zero entries in z∆ imply that corresponding tags are present, while the non-zero entries indicate that the tags are missing. In practical RFID systems, the number of missing tags K is typically much smaller than the number of tags under monitoring N during a short monitoring interval, i.e., N K ≥ 0 [16, 28]. In other words, z∆ is K-sparse, meaning that there are at most K non-zero entries in z∆ [12]. According to the theory of compressive sensing, the K-sparse vector z∆ can be accurately recovered with only M = O(K log(N/K)) measurements, by solving the following convex optimization problem [12]. Minimize: kz∆k`1 Subject to: Az∆ = y∆, (5) where k · k`p denotes `p-norm, i.e., kxk`p , ( Pi=N i=1 |xi | p ) 1/p . Intuitively, the objective function of minimizing kz∆k`1 incorporates the fact that z∆ is sparse, while the constraint function is self-explanatory. Therefore, we can refer to convex optimization solvers (e.g., CVX [2], `1-Magic [6]) to compute z∆. In our implementation, we use the CVX solver [2] based on the interior-point algorithm [7]. It has been reported that M = 3K ∼ 4K N measurements suffice to recover the K-sparse vector [17]. We set the number of measurements as M = CKMax log(N) in practice, where KMax represents the estimated maximum number of missing tags and C is a constant. Our experiment results show that M measurements of physical layer symbols are sufficient to reconstruct the Ksparse vector of z∆. When the number of missing tags exceeds KMax, our approach can identify at least KMax missing tags, which allows P-MTI to effectively adjust KMax (Section V). Leveraging the differential of aggregated responses, we improve the performance of P-MTI from O(N) to O(K log(N/K)). The compressive sensing based information reconstruction allows us to extract the missing tag events directly from the differential of aggregated physical layer symbols, thereby significantly reducing the required total time slots compared with the existing schemes. Besides, unlike existing schemes which need multiple physical symbols per slot, P-MTI needs only one symbol per time slot. Therefore, the performance gain of such joint optimization is promising. D. Enhancement against noisy measurement The above analysis ignores the noise in measurements. Wireless channel is mostly error-prone, subjected to various factors, such as interference, quantization, etc [8]. Channel dynamics may also introduce noise to the measurements. Without robustness enhancement against noise, a detection system may result in unfavorable false alarms over noisy channels [14]. In the following, we enhance P-MTI’s robustness against noise based on the theory of stable recovery [9]. Incorporating the noise, Eq.(4) can be rewritten as follows. y∆ = Az∆ + e, (6) where e denotes the error due to noise. Then the optimization problem with relaxed constraints for recovery of z can be written as follows. Minimize: kz∆k`1 Subject to: kAz∆ − y∆k`2 ≤ , (7) where the magnitude e is bounded by , i.e., kek`2 ≤ . The theory of stable recovery [9] tells us that the solution ˆz∆ to the convex optimization problem (7) is a good approximation of z∆, and kz∆ − ˆz∆k2 ≤ c where c denotes a small constant. In other words, a small error in y∆ only slightly influences reconstruction of z∆. In order to identify missing tags, PMTI only needs to distinguish the zero and non-zero entries in z∆. The noise may disturb z∆ and render the zero entries in z∆ non-zero (yet remaining small), affacting the detection accuracy. As the error is well bounded by the noise in practice, if the noise is small we can use a threshold θ to accurately classify the contaminated signals with high probabilities. In particular, we define the detection function f(z∆i) for tag i as follows. f(z∆i) = ( Present, if kz∆ik`2 < θ Absent, otherwise. (8) If the magnitude of z∆i is smaller than θ, then tag i is present; otherwise, we say tag i is absent. When the channel condition dramatically deteriorates, the RFID reader cannot always accurately identify the missing tags. In such scenarios, the reader may use the basic P-MTI to identify the missing tags, and monitor the channel H. If the channel becomes reasonably good and stable, P-MTI can switch back to monitor the differential and identify the missing tags. The reader may also increase transmission power to increase the signal
strength of backscatter responses,reduce data rates to enhance robustness against noise,and notify coexisting wireless devices to mitigate interferences.Although our approach cannot mag- ically fight against strong channel variation (due to intentional inference,fast tag mobility,dramatic environment dynamics, etc.),P-MTI is experimentally proven to be robust in rea- Fig.4.Testbed:2 circular antennas are mounted to USRP N210.The USRP sonably good channel conditions (Section V)and stationary N210 is connected via GigE to a laptop which acts as an RFID reader. environment settings (Section IV). E.Multiple readers Multiple readers are normally deployed to ensure a full coverage of a large monitoring area [28]due to power con- straints,interrogation environment,etc.For instance,current Fig.5.A WISP tag. RFID readers can only power up the passive RFID tags within approximately 10m.We denote the number of RFID only perform lightweight routine computation tasks required readers as L which is generally constrained by the deployment by the EPCglobal Gen-2 standard [3],and the computational budget.With more RFID readers,the number of tags in each overhead is negligible. monitoring area can be reduced,which mitigates the tag-tag 3)Channel dynamics:In practice,wireless channels contention and collision in the area.Besides,the RFID readers change over time.P-MTI naturally embraces the channel with non-overlapping coverage can interrogate tags in parallel dynamics.First,the compressive sensing based signal recon- without the reader-reader interference. struction is robust to channel noise.P-MTI takes measurement Recent works propose to efficiently schedule multiple RFID noise (due to channel dynamics,interference,quantization, readers to improve the performance [28].P-MTI is able to etc.)into consideration and enhance its robustness based on adopt similar coordination strategies to achieve the parallel the theory of stable recovery (Section III-D).Second,the interrogation of multiple readers.We note that a tag can be detection function f(zi)obviates the need of accurate chan- in the overlapped coverage of multiple RFID readers.As the nel measurements.In stationary environment settings (e.g., readers with overlapped coverage can easily be scheduled medicine store,military basis,etc),the channel variation is into different time slots by the server,the tags will only talk small.If channel condition changes dramatically during a to one reader at a time.Therefore,each RFID reader with short period,P-MTI may draw a false detection result.One non-overlapping coverage area can interrogate the tags in its possible solution is to do extra measurements to ensure the coverage.Each RFID reader reports all the missing tags as detection results.For instance,the RFID reader may query the well as the present tags in its coverage to the backend server. potential missing tags to respond immediately.If no response The server claims a missing tag event only when a tag is is sent back from the tag,then the reader can confidently absent in all the monitoring area of the RFID readers.Such conclude its absence.Tag mobility also introduces channel a simple data processing task can be easily handled by the dynamics.While P-MTI primarily focus on monitoring static backend server with powerful computation capability. goods (e.g.,in inventory management),our scheme inherently tolerates low mobility scenarios where the channel dynamics F.Discussion are within the stability range as discussed in Section III. 1)Communication cost:The RFID reader needs to initiate Following the existing approaches [16,23],we focus on the the missing tag identification process by sending a command wireless channels without the intentional interference from as well as communication parameters (e.g.,data rate,encoding adversaries.P-MTI may benefit from a wise channel selection scheme.etc).Such an initialization is typically in orders scheme (e.g.,BLINK [30])to ensure the channel quality as of ms.As the RFID readers are normally connected with well. backend server via high speed links,the communication cost between readers and backend server is also small compared IV.IMPLEMENTATION with that of the backscatter communication.The backscatter Although the EPCglobal Gen-2 standard specifies many communication from tags to reader involves the transmission operations of tags and readers,the practical implementation time of O(K log(N/K))physical layer symbols. is left to the manufacturers'choices.Production RFID readers 2)Computational complexity:The computation time of (e.g.,Alien ALR 9900+RFID reader [1])only provide limited compressive sensing based decoding performed at the backend interfaces and do not expose physical layer information to server turns out to be the major contributor to the overall users.To explore the lower layer information,we build a computation overhead.In our implementation,we use the off- prototype missing tag identification system based on the USRP the-shelf CVX solver [2]to decode the aggregated responses software defined radio and the programmable WISP tags. and identify the missing tags,which involves computation time Figure 4 shows the testbed.In particular,we implement a of O(N3).Our implementation using commodity PCs can prototype software defined RFID reader using USRP N210 easily cope with the computation tasks in sub-second time with based on the GNURadio toolkit and Gen2 RFID project [5]. thousands of tags.In P-MTI,both RFID reader and RFID tag One USRP RFX900 daughterboard operating in the 900MHz
strength of backscatter responses, reduce data rates to enhance robustness against noise, and notify coexisting wireless devices to mitigate interferences. Although our approach cannot magically fight against strong channel variation (due to intentional inference, fast tag mobility, dramatic environment dynamics, etc.), P-MTI is experimentally proven to be robust in reasonably good channel conditions (Section V) and stationary environment settings (Section IV). E. Multiple readers Multiple readers are normally deployed to ensure a full coverage of a large monitoring area [28] due to power constraints, interrogation environment, etc. For instance, current RFID readers can only power up the passive RFID tags within approximately 10m. We denote the number of RFID readers as L which is generally constrained by the deployment budget. With more RFID readers, the number of tags in each monitoring area can be reduced, which mitigates the tag-tag contention and collision in the area. Besides, the RFID readers with non-overlapping coverage can interrogate tags in parallel without the reader-reader interference. Recent works propose to efficiently schedule multiple RFID readers to improve the performance [28]. P-MTI is able to adopt similar coordination strategies to achieve the parallel interrogation of multiple readers. We note that a tag can be in the overlapped coverage of multiple RFID readers. As the readers with overlapped coverage can easily be scheduled into different time slots by the server, the tags will only talk to one reader at a time. Therefore, each RFID reader with non-overlapping coverage area can interrogate the tags in its coverage. Each RFID reader reports all the missing tags as well as the present tags in its coverage to the backend server. The server claims a missing tag event only when a tag is absent in all the monitoring area of the RFID readers. Such a simple data processing task can be easily handled by the backend server with powerful computation capability. F. Discussion 1) Communication cost: The RFID reader needs to initiate the missing tag identification process by sending a command as well as communication parameters (e.g., data rate, encoding scheme, etc). Such an initialization is typically in orders of ms. As the RFID readers are normally connected with backend server via high speed links, the communication cost between readers and backend server is also small compared with that of the backscatter communication. The backscatter communication from tags to reader involves the transmission time of O(K log(N/K)) physical layer symbols. 2) Computational complexity: The computation time of compressive sensing based decoding performed at the backend server turns out to be the major contributor to the overall computation overhead. In our implementation, we use the offthe-shelf CVX solver [2] to decode the aggregated responses and identify the missing tags, which involves computation time of O(N3 ). Our implementation using commodity PCs can easily cope with the computation tasks in sub-second time with thousands of tags. In P-MTI, both RFID reader and RFID tag Fig. 4. Testbed: 2 circular antennas are mounted to USRP N210. The USRP N210 is connected via GigE to a laptop which acts as an RFID reader. Fig. 5. A WISP tag. only perform lightweight routine computation tasks required by the EPCglobal Gen-2 standard [3], and the computational overhead is negligible. 3) Channel dynamics: In practice, wireless channels change over time. P-MTI naturally embraces the channel dynamics. First, the compressive sensing based signal reconstruction is robust to channel noise. P-MTI takes measurement noise (due to channel dynamics, interference, quantization, etc.) into consideration and enhance its robustness based on the theory of stable recovery (Section III-D). Second, the detection function f(z∆i) obviates the need of accurate channel measurements. In stationary environment settings (e.g., medicine store, military basis, etc), the channel variation is small. If channel condition changes dramatically during a short period, P-MTI may draw a false detection result. One possible solution is to do extra measurements to ensure the detection results. For instance, the RFID reader may query the potential missing tags to respond immediately. If no response is sent back from the tag, then the reader can confidently conclude its absence. Tag mobility also introduces channel dynamics. While P-MTI primarily focus on monitoring static goods (e.g., in inventory management), our scheme inherently tolerates low mobility scenarios where the channel dynamics are within the stability range as discussed in Section III. Following the existing approaches [16, 23], we focus on the wireless channels without the intentional interference from adversaries. P-MTI may benefit from a wise channel selection scheme (e.g., BLINK [30]) to ensure the channel quality as well. IV. IMPLEMENTATION Although the EPCglobal Gen-2 standard specifies many operations of tags and readers, the practical implementation is left to the manufacturers’ choices. Production RFID readers (e.g., Alien ALR 9900+ RFID reader [1]) only provide limited interfaces and do not expose physical layer information to users. To explore the lower layer information, we build a prototype missing tag identification system based on the USRP software defined radio and the programmable WISP tags. Figure 4 shows the testbed. In particular, we implement a prototype software defined RFID reader using USRP N210 based on the GNURadio toolkit and Gen2 RFID project [5]. One USRP RFX900 daughterboard operating in the 900MHz
0.4 0.35 tag1-+ 8g2" 3 ag 3- 0.8 0.6 0.2 0 0.15 0.1 0.2 0.2 0.05 +++4+++++++ 4+4++ 0 10 20 30 40 0 0.2 0.4 0.6 0.8 1 12 Time(ms) Measurements Initial synchronization offset(us) F5g.6. MTI process.1)the reader transmits Fig.7. Received signal strength from 3 tags. Fig.8.Initial offsets among WISP tags. continuous waves:2)the reader broadcasts the MTI command;3)When receiving MTI,each tag responds. First measurement(5 tags) a routine named MTI.Figure 6 plots the magnitude of received signals at RFID reader during the MTI process.The RFID reader initiates the monitoring by transmitting continuous Second measurement (4 tags) waves to power up the tags.The reader then broadcasts the operation code of MTI.When receiving the MTI command, each tag sends the pseudo random bits using on-off keying as Differential of two measurement specified in P-MTI.The aggregated responses from tags are received and decoded at the reader.The reader terminates the monitoring by simply stopping the radio frequency waves. 0 50 100150200250300 350 400 Time(us) A.Backscatter signals Fig.9.Received signals at RFID reader:(a)Aggregated signals from 5 tags; (b)Aggregated signals from 4 tags:(c)Differential of the two measurements. The differential of aggregated responses based approach requires that the wireless channel remains relatively stable UHF band [4]is connected to the USRP N210 as the frontend. during consecutive measurements.We let 3 WISP tags transmit We connect the daughterboard to Alien ALR-8696-C circular random bits and measure the received signal strength at the polarized antennas with 8.5dBic antenna gain [1].The USRP USRP reader in the office environment.Each tag transmits a N210 is connected via Gigabit Ethernet to a laptop equipped packet of 32 symbols per second.The RFID reader measures with one qual-core 2.67GHz processor and 2.9GB memory the average signal strength of the 32 symbols.We conduct running Ubuntu 10.10. 40 measurements for each tag,and show the strength of We implement RFID tags with the WISP programmable tags backscatter signals from 3 tags in Figure 7.We find that (Figure 5)based on the WISP4.1 hardware and firmware.Each the received backscatter signals remain quite stable during the WISP tag mainly consists of an antenna circuitry and an ultra- measurements of 40 seconds.As shown in Figure 2,the signal low power 16-bit MSP430 microcontroller.The circuitry is strength remains even more stable within the transmission of used to harvest energy from the radio frequency signals and one packet which is much shorter. backscatter the signals for communication.A capacitor stores the harvested transient energy and supplies power for compu- B.Backscatter synchronization tation and communication.The EPCglobal Gen-2 protocol [3] Passive RFID tags work on harvested energy from radio has been partially implemented in the WISP firmware,which frequency signals of reader.As the interrogation environment has most of the necessary components to implement P-MTI. varies,the energy harvest rate differs from tags to tags. We extend the firmware to let the tags work in concert with the Therefore,some tags may wake up earlier than other tags, software defined RFID reader to achieve the functionality of which introduces response offsets.We set a conservative missing tag identification.The programming overhead is small period of transmitting continuous waves to power the tags and the extension only requires slight updates to the EPCglobal before broadcasting the MTI command.The tags transmit Gen-2 standard.Constrained by transmission power of USRP signals concurrently after receiving the MTI command.Ideally, with 200mW and limited number of available WISP tags,cur- the signals from multiple tags would arrive at the reader at rently we can only perform experiments in small-scale static the same time.In practice,however,the signals exhibit small settings.Yet we believe P-MTI can be easily implemented in offsets.Figure 8 shows the CDF of offsets among 7WISP large-scale production RFID systems. tags.According to our experiments on WISP RFID tags,the The EPCglobal Gen-2 standard specifies a set of routine offsets are within 1.4us with the 90th percentile of 0.75us. operations (e.g.,Query,Write,Select,ACK,etc).We ex-When the data rate is 40kbps,a 1.4us offset counts for 5.6% tend the EPCglobal Gen-2 following the conventional reader- of bit width(25us)which is sufficiently small for decoding.A initiated approach by adding the missing tag identification recent independent work [23]reports similar synchronization
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0 2 4 6 8 10 12 Magnitude Time(ms) Continuous wave MTI Response Fig. 6. MTI process. 1) the reader transmits continuous waves; 2) the reader broadcasts the MTI command; 3) When receiving MTI, each tag responds. 0 0.2 0.4 0.6 0 10 20 30 40 Received signal strength Measurements tag 1 tag 2 tag 3 Fig. 7. Received signal strength from 3 tags. 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 CDF Initial synchronization offset (us) Offset Fig. 8. Initial offsets among WISP tags. 0 0.1 0.2 0.3 0.4 0.5 0.6 First measurement (5 tags) 0 0.1 0.2 0.3 0.4 0.5 0.6 Second measurement (4 tags) 0 0.1 0.2 0.3 0.4 0.5 0.6 0 50 100 150 200 250 300 350 400 (a) (b) (c) Time(us) Magnitude Differential of two measurements Missing tag Fig. 9. Received signals at RFID reader: (a) Aggregated signals from 5 tags; (b) Aggregated signals from 4 tags; (c) Differential of the two measurements. UHF band [4] is connected to the USRP N210 as the frontend. We connect the daughterboard to Alien ALR-8696-C circular polarized antennas with 8.5dBic antenna gain [1]. The USRP N210 is connected via Gigabit Ethernet to a laptop equipped with one qual-core 2.67GHz processor and 2.9GB memory running Ubuntu 10.10. We implement RFID tags with the WISP programmable tags (Figure 5) based on the WISP4.1 hardware and firmware. Each WISP tag mainly consists of an antenna circuitry and an ultralow power 16-bit MSP430 microcontroller. The circuitry is used to harvest energy from the radio frequency signals and backscatter the signals for communication. A capacitor stores the harvested transient energy and supplies power for computation and communication. The EPCglobal Gen-2 protocol [3] has been partially implemented in the WISP firmware, which has most of the necessary components to implement P-MTI. We extend the firmware to let the tags work in concert with the software defined RFID reader to achieve the functionality of missing tag identification. The programming overhead is small and the extension only requires slight updates to the EPCglobal Gen-2 standard. Constrained by transmission power of USRP with 200mW and limited number of available WISP tags, currently we can only perform experiments in small-scale static settings. Yet we believe P-MTI can be easily implemented in large-scale production RFID systems. The EPCglobal Gen-2 standard specifies a set of routine operations (e.g., Query, Write, Select, ACK, etc). We extend the EPCglobal Gen-2 following the conventional readerinitiated approach by adding the missing tag identification routine named MTI. Figure 6 plots the magnitude of received signals at RFID reader during the MTI process. The RFID reader initiates the monitoring by transmitting continuous waves to power up the tags. The reader then broadcasts the operation code of MTI. When receiving the MTI command, each tag sends the pseudo random bits using on-off keying as specified in P-MTI. The aggregated responses from tags are received and decoded at the reader. The reader terminates the monitoring by simply stopping the radio frequency waves. A. Backscatter signals The differential of aggregated responses based approach requires that the wireless channel remains relatively stable during consecutive measurements. We let 3 WISP tags transmit random bits and measure the received signal strength at the USRP reader in the office environment. Each tag transmits a packet of 32 symbols per second. The RFID reader measures the average signal strength of the 32 symbols. We conduct 40 measurements for each tag, and show the strength of backscatter signals from 3 tags in Figure 7. We find that the received backscatter signals remain quite stable during the measurements of 40 seconds. As shown in Figure 2, the signal strength remains even more stable within the transmission of one packet which is much shorter. B. Backscatter synchronization Passive RFID tags work on harvested energy from radio frequency signals of reader. As the interrogation environment varies, the energy harvest rate differs from tags to tags. Therefore, some tags may wake up earlier than other tags, which introduces response offsets. We set a conservative period of transmitting continuous waves to power the tags before broadcasting the MTI command. The tags transmit signals concurrently after receiving the MTI command. Ideally, the signals from multiple tags would arrive at the reader at the same time. In practice, however, the signals exhibit small offsets. Figure 8 shows the CDF of offsets among 7 WISP tags. According to our experiments on WISP RFID tags, the offsets are within 1.4µs with the 90th percentile of 0.75µs. When the data rate is 40kbps, a 1.4µs offset counts for 5.6% of bit width (25µs) which is sufficiently small for decoding. A recent independent work [23] reports similar synchronization
Missed 0.7 0.75 0 05 0.25 0.25 SNR-20dB C=3 SNR=17dB -X C=4 SNR=14dB-- 0 5 11 14 17 20 23 26 29 33 5 10 15 20 25 30 10 15 20 30 35 4 SNR(dB) Number of missing tags Number of missing tags F5g.10. Missing tag identification accuracy Fig.11.Missing tag identification accuracy with Fig.12.Identified and missed tags with dif- across different channel conditions. different number of missing tags. ferent number of missing tags,SNR=17dB,and KMax=20. accuracy on the Moo RFID tag [29]which is developed based B.P-MTI investigation on the WISP project. C.Identifying missing WISP tag Wireless communication is error-prone in practice,and thus whether P-MTI can accurately identify missing tags in the We prototype a missing tag identification system where a presence of channel noise is worth investigating.We simulate software defined RFID reader monitors 5 WISP tags.Figure 1000 tags uniformly distributed in the coverage of each RFID 9(a)depicts the received signals at the reader when all the 5 reader,among which 20 tags are missing.We specify the WISP tags are present in the first measurement instance.We number of measurements M =CKMax log(N),where N intentionally take away one tag to emulate a missing tag event. 1000 and KMax =20 with different C.We randomly select Figure 9(b)plots the received signals from the 4 remaining the missing tags for simulation.Figure 10 plots the average tags.Figure 9(c)plots the differential of the two measure- accuracy of identifying the missing tags across different signal ments,and the signals when only the missing tag responds. to noise ratio(SNR).As expected,when SNR is very low,P- We note that the magnitude of received signal strength is MTI cannot always identify the missing tags.At moderate and influenced by the wireless channel as well as the automatic high SNRs (e.g.,17-32dB),P-MTI achieves high accuracy.In again control of RFID reader.Although the magnitude of particular,with the SNR>17dB,the identification accuracies received signal differs due to channel attenuation and gain are consistently higher than 98%when C 3.P-MTI control,we see that the differential exhibits similar patterns can further improve the accuracy with extra measurements with the signals when only the missing tag responds.With (i.e.,with larger C)according to the application requirement. the knowledge of the differential signals,we can accurately Generally,with more measurements P-MTI can achieve higher identify the missing tag by solving the convex optimization accuracy at the cost of extra communication and computation problem (7).For clarity,here we only present the instance overhead in the presence of noise.According to Figure 10, when only one tag is missing.In the experiments when more we find that the marginal accuracy improvement diminishes than one tag are missing,we find that P-MTI can accurately with the increased number of measurements.For instance,the identify them as well accuracy with C=4 is only slightly higher than that with V.EVALUATION C =3.We thus set C=3 to balance the accuracy and overhead in practice In the following,we turn to large-scale simulations to eval- uate our missing tag identification scheme.We first analyze Another parameter that P-MTI needs to specify is the the proposed P-MTI.We then compare P-MTI with state-of- estimated maximum number of missing tags.The number of the-art protocols IIP [16]and Protocol-3 [28]. missing tags can sometimes exceed the estimated maximum number.We investigate identification accuracy of P-MTI with A.Simulation setup and performance metrics different number of missing tags which may exceed the We build a custom simulator based on CVX solver [2]and estimated maximum number of KMax=20,under noisy channel run the simulations on MATLAB.For P-MTI,we study the conditions (i.e.,SNR=14,17,and 20dB).Figure 11 plots the various scenarios with different number of tags and readers and average accuracy of identifying the missing tags when the wireless channel conditions.For fair comparison,we adopt the number of missing tags varies from 5 to 40.According to the same system parameters used in benchmark protocols [16,28]. results,we see that when the number of missing tags is smaller In particular,the transmission time of a short response is than KMax (i.e.,<20),P-MTI can accurately identify the specified as ts =0.8ms and the transmission time of a 96- missing tags.When the number of missing tags exceeds KMax, bit tag ID is specified as ttag =2.4ms,which gives an ap- the accuracy decreases.Therefore,the RFID reader needs to proximate bitrate of 40kbps.We focus on the communication adjust KMax to ensure that no more than KMax tags would be time between RFID readers and tags,and ignore the negligible missing.Figure 12 plots in detail the missing tag identification processing time on backend server.All results are obtained by results with different number of missing tags,SNR=17dB,and averaging over 100 runs if not specified otherwise. KMax=20.Although P-MTI may fail to identify some tags
0 0.25 0.5 0.75 1 5 8 11 14 17 20 23 26 29 32 Accuracy SNR(dB) C=1 C=2 C=3 C=4 Fig. 10. Missing tag identification accuracy across different channel conditions. 0 0.25 0.5 0.75 1 5 10 15 20 25 30 35 40 Accuracy Number of missing tags SNR=20dB SNR=17dB SNR=14dB Fig. 11. Missing tag identification accuracy with different number of missing tags. 0 20 40 5 10 15 20 25 30 35 40 Number of tags Number of missing tags Identified Missed Fig. 12. Identified and missed tags with different number of missing tags, SNR=17dB, and KMax=20. accuracy on the Moo RFID tag [29] which is developed based on the WISP project. C. Identifying missing WISP tag We prototype a missing tag identification system where a software defined RFID reader monitors 5 WISP tags. Figure 9(a) depicts the received signals at the reader when all the 5 WISP tags are present in the first measurement instance. We intentionally take away one tag to emulate a missing tag event. Figure 9(b) plots the received signals from the 4 remaining tags. Figure 9(c) plots the differential of the two measurements, and the signals when only the missing tag responds. We note that the magnitude of received signal strength is influenced by the wireless channel as well as the automatic again control of RFID reader. Although the magnitude of received signal differs due to channel attenuation and gain control, we see that the differential exhibits similar patterns with the signals when only the missing tag responds. With the knowledge of the differential signals, we can accurately identify the missing tag by solving the convex optimization problem (7). For clarity, here we only present the instance when only one tag is missing. In the experiments when more than one tag are missing, we find that P-MTI can accurately identify them as well. V. EVALUATION In the following, we turn to large-scale simulations to evaluate our missing tag identification scheme. We first analyze the proposed P-MTI. We then compare P-MTI with state-ofthe-art protocols IIP [16] and Protocol-3 [28]. A. Simulation setup and performance metrics We build a custom simulator based on CVX solver [2] and run the simulations on MATLAB. For P-MTI, we study the various scenarios with different number of tags and readers and wireless channel conditions. For fair comparison, we adopt the same system parameters used in benchmark protocols [16, 28]. In particular, the transmission time of a short response is specified as ts = 0.8ms and the transmission time of a 96- bit tag ID is specified as ttag = 2.4ms, which gives an approximate bitrate of 40kbps. We focus on the communication time between RFID readers and tags, and ignore the negligible processing time on backend server. All results are obtained by averaging over 100 runs if not specified otherwise. B. P-MTI investigation Wireless communication is error-prone in practice, and thus whether P-MTI can accurately identify missing tags in the presence of channel noise is worth investigating. We simulate 1000 tags uniformly distributed in the coverage of each RFID reader, among which 20 tags are missing. We specify the number of measurements M = CKMax log(N), where N = 1000 and KMax = 20 with different C. We randomly select the missing tags for simulation. Figure 10 plots the average accuracy of identifying the missing tags across different signal to noise ratio (SNR). As expected, when SNR is very low, PMTI cannot always identify the missing tags. At moderate and high SNRs (e.g., 17-32dB), P-MTI achieves high accuracy. In particular, with the SNR≥17dB, the identification accuracies are consistently higher than 98% when C ≥ 3. P-MTI can further improve the accuracy with extra measurements (i.e., with larger C) according to the application requirement. Generally, with more measurements P-MTI can achieve higher accuracy at the cost of extra communication and computation overhead in the presence of noise. According to Figure 10, we find that the marginal accuracy improvement diminishes with the increased number of measurements. For instance, the accuracy with C = 4 is only slightly higher than that with C = 3. We thus set C = 3 to balance the accuracy and overhead in practice. Another parameter that P-MTI needs to specify is the estimated maximum number of missing tags. The number of missing tags can sometimes exceed the estimated maximum number. We investigate identification accuracy of P-MTI with different number of missing tags which may exceed the estimated maximum number of KMax=20, under noisy channel conditions (i.e., SNR=14, 17, and 20dB). Figure 11 plots the average accuracy of identifying the missing tags when the number of missing tags varies from 5 to 40. According to the results, we see that when the number of missing tags is smaller than KMax (i.e., <20), P-MTI can accurately identify the missing tags. When the number of missing tags exceeds KMax, the accuracy decreases. Therefore, the RFID reader needs to adjust KMax to ensure that no more than KMax tags would be missing. Figure 12 plots in detail the missing tag identification results with different number of missing tags, SNR=17dB, and KMax=20. Although P-MTI may fail to identify some tags
Protocol3 16 14 P-MT1100%) 10 ptive 泉2米：米米米米为 米 一米.米米米米 10002000300040005000600070008000900010000 10 20304050607080 90100 0 10 20 30 40 50 Number of tags Number of readers Missing tag ratio(%) Fig.13.Single reader case:Transmission time Fig.14. Multiple reader case:Transmission Fig.15.Transmission time of Protocol-3 and P- of IIP.Protocol-3.P-MTI (KMax =0.2N).and time of Protocol-3.P-MTI (KMax =0.2N).and MTI with/without a priori knowledge of missing P-MTI (KMax N)with different number of P-MTI (KMax N)with different number of tag ratio. tags. readers. when the number of missing tags exceeds KMax,the number of Multiple readers.We compare the performance of P-MTI successfully identified missing tags would become very close with Protocol-3 in the scenarios of multiple RFID readers. to or even exceed KMax.When the number of missing tags We simulate 50,000 tags with varied number of readers. exceeds 20.however,the number of successfully identified We use the same RFID network topology for P-MTI and ones becomes larger than 20.In such cases,the reader can Protocol-3 and investigate the transmission time.As shown adaptively increase KMax to ensure that KMax is larger than in Figure 14,with more readers both P-MTI and Protocol- the number of missing ones.A larger KMax can correct the 3 can effectively reduce the overall transmission time by error due to underestimation of missing tags at the cost of dividing the tags into smaller subsets and interrogating them the increased communication overhead.We show that even in in parallel.Nevertheless,the increased number of readers the most conservative setting (i.e,KMax =N),P-MTI still requires extra deployment costs.Thus it is yet significant to achieves much higher processing efficiency compared with further improve the communication efficiency.According to existing protocols in the following. our experiment results,P-MTI can significantly reduce the transmission time compared with Protocol-3,with/without the C.Performance comparison knowledge of missing tag ratio.In particular,P-MTI with We compare P-MTI with the most recent protocols IIP [16] conservative parameter setting only takes about 33%of the and Protocol-3 [28].We adopt the same system parameters transmission time of Protocol-3. used in [16,28].As IIP and Protocol-3 do not target at Number of missing tags.We compare the transmission noisy channels,we do not simulate channel errors in the time of P-MTI with Protocol-3 with different ratio of missing comparison study.For completeness,P-MTI however uses tags.We simulate 50,000 tags in the coverage of 50 RFID conservative parameter settings (e.g.,M 3KMax log(N)) readers.Figure 15 plots the transmission time with different which would favor the benchmark protocols.As in IIP and missing tag ratios varied from 0%to 50%,which covers Protocol-3.we mainly investigate the transmission time of the typical missing tag events in practical applications.The backscatter responses from tags to readers,and ignore the adaptive P-MTI adaptively increases KMax when the number negligible communication overhead(e.g.,transmission time of of missing tags becomes close to or exceeds KMax.The initialization,reader to server transmission,etc). conservative P-MTI conservatively sets KMax=0.5N.From Single reader.We note that Protocol-3 and P-MTI sched- Figure 15,we find that the transmission time of adaptive ule multiple readers and achieve interrogation among non- P-MTI increases linearly with the missing tag ratio,while overlapping readers in parallel,while IIP views multiple read- the transmission time of conservative P-MTI remains almost ers as a single logical reader and does not benefit from parallel constant.We also find that the transmission time of both interrogation.Therefore,we first study the single reader case adaptive and conservative P-MTI is much smaller than that and compare IIP,Protocol-3,and P-MTI.Figure 13 compares of Protocol-3 across different missing tag ratios the transmission time of IIP,Protocol-3,P-MTI (with KMax 0.2N),and P-MTI (with KMax =N).According to the results, VI.RELATED WORK we find that P-MTI with conservative parameter settings can Many works study the problem of RFID identification reduce the transmission time by approximately 65%compared which aims at identifying the tags through collision arbitration with IIP and Protocol-3.With more realistic parameter settings [19,24].The RFID identification protocols can be generally of KMax =0.2N,P-MTI achieves even higher efficiency.The classified into two categories:Aloha-based [21]and tree-based performance gain of P-MTI stems from the efficient use of [10]protocols.In Aloha-based identification protocols,each physical layer information and the compressive sensing based tag randomly selects a time slot to transmit its ID.If a time slot information reconstruction.With the knowledge of maximum is selected by only one tag,then the tag can be successfully number of missing tags,P-MTI can achieve higher efficiency identified.If more than one tag select a time slot,then the rather than using the conservative parameter settings tags cannot be identified due to tag-tag collisions.In tree-
0 2 4 6 8 10 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Transmission time(s) Number of tags IIP Protocol-3 P-MTI( 20% ) P-MTI(100%) Fig. 13. Single reader case: Transmission time of IIP, Protocol-3, P-MTI (KMax = 0.2N), and P-MTI (KMax = N) with different number of tags. 0 2 4 6 8 10 12 14 16 10 20 30 40 50 60 70 80 90 100 Transmission time(s) Number of readers Protocol-3 P-MTI( 20% ) P-MTI(100%) Fig. 14. Multiple reader case: Transmission time of Protocol-3, P-MTI (KMax = 0.2N), and P-MTI (KMax = N) with different number of readers. 0 1 2 3 4 0 10 20 30 40 50 Transmission time(s) Missing tag ratio(%) Protocol-3 Conservative P-MTI Adaptive P-MTI Fig. 15. Transmission time of Protocol-3 and PMTI with/without a priori knowledge of missing tag ratio. when the number of missing tags exceeds KMax, the number of successfully identified missing tags would become very close to or even exceed KMax. When the number of missing tags exceeds 20, however, the number of successfully identified ones becomes larger than 20. In such cases, the reader can adaptively increase KMax to ensure that KMax is larger than the number of missing ones. A larger KMax can correct the error due to underestimation of missing tags at the cost of the increased communication overhead. We show that even in the most conservative setting (i.e, KMax = N), P-MTI still achieves much higher processing efficiency compared with existing protocols in the following. C. Performance comparison We compare P-MTI with the most recent protocols IIP [16] and Protocol-3 [28]. We adopt the same system parameters used in [16, 28]. As IIP and Protocol-3 do not target at noisy channels, we do not simulate channel errors in the comparison study. For completeness, P-MTI however uses conservative parameter settings (e.g., M = 3KMax log(N)) which would favor the benchmark protocols. As in IIP and Protocol-3, we mainly investigate the transmission time of backscatter responses from tags to readers, and ignore the negligible communication overhead (e.g., transmission time of initialization, reader to server transmission, etc). Single reader. We note that Protocol-3 and P-MTI schedule multiple readers and achieve interrogation among nonoverlapping readers in parallel, while IIP views multiple readers as a single logical reader and does not benefit from parallel interrogation. Therefore, we first study the single reader case and compare IIP, Protocol-3, and P-MTI. Figure 13 compares the transmission time of IIP, Protocol-3, P-MTI (with KMax = 0.2N), and P-MTI (with KMax = N). According to the results, we find that P-MTI with conservative parameter settings can reduce the transmission time by approximately 65% compared with IIP and Protocol-3. With more realistic parameter settings of KMax = 0.2N, P-MTI achieves even higher efficiency. The performance gain of P-MTI stems from the efficient use of physical layer information and the compressive sensing based information reconstruction. With the knowledge of maximum number of missing tags, P-MTI can achieve higher efficiency rather than using the conservative parameter settings. Multiple readers. We compare the performance of P-MTI with Protocol-3 in the scenarios of multiple RFID readers. We simulate 50,000 tags with varied number of readers. We use the same RFID network topology for P-MTI and Protocol-3 and investigate the transmission time. As shown in Figure 14, with more readers both P-MTI and Protocol- 3 can effectively reduce the overall transmission time by dividing the tags into smaller subsets and interrogating them in parallel. Nevertheless, the increased number of readers requires extra deployment costs. Thus it is yet significant to further improve the communication efficiency. According to our experiment results, P-MTI can significantly reduce the transmission time compared with Protocol-3, with/without the knowledge of missing tag ratio. In particular, P-MTI with conservative parameter setting only takes about 33% of the transmission time of Protocol-3. Number of missing tags. We compare the transmission time of P-MTI with Protocol-3 with different ratio of missing tags. We simulate 50,000 tags in the coverage of 50 RFID readers. Figure 15 plots the transmission time with different missing tag ratios varied from 0% to 50%, which covers the typical missing tag events in practical applications. The adaptive P-MTI adaptively increases KMax when the number of missing tags becomes close to or exceeds KMax. The conservative P-MTI conservatively sets KMax = 0.5N. From Figure 15, we find that the transmission time of adaptive P-MTI increases linearly with the missing tag ratio, while the transmission time of conservative P-MTI remains almost constant. We also find that the transmission time of both adaptive and conservative P-MTI is much smaller than that of Protocol-3 across different missing tag ratios. VI. RELATED WORK Many works study the problem of RFID identification which aims at identifying the tags through collision arbitration [19, 24]. The RFID identification protocols can be generally classified into two categories: Aloha-based [21] and tree-based [10] protocols. In Aloha-based identification protocols, each tag randomly selects a time slot to transmit its ID. If a time slot is selected by only one tag, then the tag can be successfully identified. If more than one tag select a time slot, then the tags cannot be identified due to tag-tag collisions. In tree-
based identification protocols.the reader detects whether any ReFERENcES tag-tag collision occurs and adaptively divides the tag set into [1]"Alien Technology",http://www.alientechnology.com small subsets until all tags are successfully identified.While [2]"CVX Research",http://evxr.com/cvx/ the RFID identification protocols can be directly borrowed to [3]"EPCglobal CIG2".http://www.epcglobalinc.org/standards/uhfe1g2 address the missing tag identification problem,the processing [4]“Ettus Research”,http:/lwww.ettus.com [5]"Gen 2 RFID Tools",https://www.cgran.org/wiki/Gen2 time increases with the number of tags and renders such [⑥“ei-Magic'”,http://users.ece.gatech.edu/justin/11magic/ approaches inefficient for monitoring large number of tags. [7]S.Boyd,"Convex Optimization".Cambridge University Press,2004. Many cardinality estimation protocols estimate the number [8]M.Buettner and D.Wetherall,"An Empirical Study of UHF RFID Performance",in ACM MobiCom,2008. of tags [15,20,32],which may serve as primary inputs for [9]E.Candes,J.Romberg,T.Tao,"Stable Signal Recovery from Incomplete missing tag identification.Such approaches,however,cannot and Inaccurate Measurements",Communications on Pure and Applied be directly borrowed to detect the missing tag events since Mathematics,vol.59,issue 9.pp.1207-1223,2006. they only provide a rough estimation of tag cardinality. [10]J.I.Capetanakis,"Tree algorithms for packet broadcast channels",IEEE Trans.on Information Theory,vol.25,issue 5,pp.505-515,1979. Recent works study the problem of tag monitoring and [11]P.-Y.Chen,W.-T.Chen.Y.-C.Tseng."Providing Group Tour Guide by identify the missing tags [28].In [22],Tan et al.present a RFIDs and Wireless Sensor Networks",IEEE Transcations on Wireless missing tag monitoring protocol which can detect the missing Communications,vol.8.issue 6,pp.3059-3067,2009. [12]D.Donoho,"Compressed sensing",IEEE Transactions on Information tag events when the number of missing tags exceeds a user- Theory,vol.52.issue4,pp.1289-1306.2006. defined threshold.In [16,Li et al.propose a missing tag [13]J.Gummeson,P.Zhang.D.Ganesan,"Flit:A Bulk Transmission identification protocol which can detect the missing tag events Protocol for RFID-Scale Sensors",in ACM MobiSys,2012. with certainty and identify the missing ones.Zhang et al.[28] [14]D.Guo,Y.Liu,X.Li,and P.Yang,"False Negative Problem of Counting Bloom Filter",IEEE Trans.on Knowledge and Data Engineering,vol. significantly reduce the missing tag identification time by more 22,issue5,Pp.651-664.2010. efficiently scheduling and utilizing multiple readers.Unlike the [15]H.Han,B.Sheng,C.C.Tan,Q.Li,W.Mao,and S.Lu,"Counting existing approaches which focus on upper layer information, RFID Tags Efficiently and Anonymously",in /EEE INFOCOM.2010. our approach effectively leverages the aggregated responses in [16]T.Li,S.Chen,and Y.Ling,"Identifying the Missing Tags in a Large RFID System",in ACM MobiHoc,2010. the physical layer to improve the monitoring efficiency. [17]C.Luo,F.Wu,J.Sun,C.W.Chen."Compressive Data Gathering for Many works study the problem of collecting data from com- Large-Scale Wireless Sensor Networks",in ACM MobiCom,2009. putational RFID tags integrated with various sensors.Yue et al. [18]L.M.Ni,Y.Liu,Y.C.Lau,and A.Patil,"LANDMARC:Indoor [25]present a data collection approach using the Bloom filter. Location Sensing Using Active RFID",ACM Wireless Networks,vol. 10,issue6,pPp.701-710,2004. Flit [13]improves the throughput of data transmission through [19]C.Qian,Y.Liu,H.-L.Ngan,and L.M.Ni,"ASAP:Scalable Identifi- a bulk transmission.BLINK [30]improves the link layer cation and Counting for Contactless RFID Systems",in /EEE /CDCS, performance with link quality measurement,mobility predic- 2010. tion,and rate adaptation for RFID communication.Buzz [23] [20]C.Qian.H.Ngan,and Y.Liu,"Cardinality Estimation for Large-scale RFID Systems",IEEE Trans.on Parallel and Distributed Systems,vol. presents an efficient and reliable data collection approach for 22,issue9,pp.1441-1454,2011. RFID systems leveraging physical layer information.Zanetti [21]L.G.Roberts,"Aloha Packet System with and without Slots and Capture et al.[26]study the problem of classifying different RFID "ACM SIGCOMM Computer Communication Review,vol.5.issue 2. pp.28-42,1975 tags using the physical layer fingerprints.Although targeting at [22]C.C.Tan,B.Sheng,and Q.Li."How to Monitor for Missing RFID totally different problems,the common rationale behind those Tags",in IEEE ICDCS,2008. works and our approach is that careful cross layer designs may [23]J.Wang,H.Hassanieh,D.Katabi,P.Indyk,"Efficient and Reliable Low-Power Backscatter Networks".in ACM SIGCOMM,2012 significantly improve the performance of RFID systems. 24]L.Yang,J.Han,Y.Qi,C.Wang,T.Gu,and Y.Liu,"Season:Shelving Interference and Joint Identification in Large-scale RFID Systems",in VII.CONCLUSION IEEE INFOCOM.2011. In this paper,we study the missing tag identification [25]H.Yue,C.Zhang,M.Pan,Y.Fang,S.Chen,"A Time-efficient Information Collection Protocol for Large-scale RFID Systems",in /EEE problem in large-scale RFID systems.We propose P-MTI to INFOCOM,2012. leverage physical layer information and substantially improve [26]D.Zanetti,B.Danev,S.Capkun,"Physical-layer Identification of UHF monitoring efficiency.We further present several optimization RFID Tags".in ACM MobiCom,2010. techniques to improve the performance.P-MTI leverages the [27]C.Zhang,Y.Zhang,Y.Fang,"A coverage inference protocol for wireless sensor networks",IEEE Transactions on Mobile Computing.vol.9.issue sparsity of missing tag events and reconstructs tag responses 6,pp.850-864,June2010. through compressive sensing.To validate its efficacy,we [28]R.Zhang.Y.Liu,Y.Zhang,and J.Sun,"Fast Identification of the implement a prototype system and extend the EPCglobal Gen- Missing Tags in a Large RFID System",in IEEE SECON,2011. 2 standard based on the GNURadio/USRP and WISP plat- [29]H.Zhang.J.Gummeson,B.Ransford,and K.Fu,"Moo:A batteryless computational RFID and sensing platform",Tech Report UMASS.2011. form.We do extensive evaluation of P-MTI with large-scale http://spqr.cs.umass.edu/moo/ simulations.The results demonstrate that P-MTI substantially [30]P.Zhang.J.Gummeson,D.Ganesan,"BLINK:A High Throughput outperforms the state-of-the-art schemes Link Layer for Backscatter Communication",in ACM MobiSys,2012. [31]Y.Zhang,L.T.Yang,and J.Chen "RFID and Sensor Networks:Archi- tectures,Protocols,Security and Integrations",Auerbach Publications, ACKNOWLEDGMENT 2010. We acknowledge the support from NTU Nanyang As- [32]Y.Zheng,M.Li,and C.Qian,"PET:Probabilistic Estimating Tree for Large-Scale RFID Estimation",in IEEE /CDCS,2011. sistant Professorship (NAP)grant M4080738.020,Microsoft [33]Y.Zheng and M.Li."Fast Tag Searching Protocol for Large-Scale RFID research grant FY12-RES-THEME-001,and NSFC grant No. Systems",in IEEE ICNP,2011. 61272456
based identification protocols, the reader detects whether any tag-tag collision occurs and adaptively divides the tag set into small subsets until all tags are successfully identified. While the RFID identification protocols can be directly borrowed to address the missing tag identification problem, the processing time increases with the number of tags and renders such approaches inefficient for monitoring large number of tags. Many cardinality estimation protocols estimate the number of tags [15, 20, 32], which may serve as primary inputs for missing tag identification. Such approaches, however, cannot be directly borrowed to detect the missing tag events since they only provide a rough estimation of tag cardinality. Recent works study the problem of tag monitoring and identify the missing tags [28]. In [22], Tan et al. present a missing tag monitoring protocol which can detect the missing tag events when the number of missing tags exceeds a userdefined threshold. In [16], Li et al. propose a missing tag identification protocol which can detect the missing tag events with certainty and identify the missing ones. Zhang et al. [28] significantly reduce the missing tag identification time by more efficiently scheduling and utilizing multiple readers. Unlike the existing approaches which focus on upper layer information, our approach effectively leverages the aggregated responses in the physical layer to improve the monitoring efficiency. Many works study the problem of collecting data from computational RFID tags integrated with various sensors. Yue et al. [25] present a data collection approach using the Bloom filter. Flit [13] improves the throughput of data transmission through a bulk transmission. BLINK [30] improves the link layer performance with link quality measurement, mobility prediction, and rate adaptation for RFID communication. Buzz [23] presents an efficient and reliable data collection approach for RFID systems leveraging physical layer information. Zanetti et al. [26] study the problem of classifying different RFID tags using the physical layer fingerprints. Although targeting at totally different problems, the common rationale behind those works and our approach is that careful cross layer designs may significantly improve the performance of RFID systems. VII. CONCLUSION In this paper, we study the missing tag identification problem in large-scale RFID systems. We propose P-MTI to leverage physical layer information and substantially improve monitoring efficiency. We further present several optimization techniques to improve the performance. P-MTI leverages the sparsity of missing tag events and reconstructs tag responses through compressive sensing. To validate its efficacy, we implement a prototype system and extend the EPCglobal Gen- 2 standard based on the GNURadio/USRP and WISP platform. We do extensive evaluation of P-MTI with large-scale simulations. The results demonstrate that P-MTI substantially outperforms the state-of-the-art schemes. ACKNOWLEDGMENT We acknowledge the support from NTU Nanyang Assistant Professorship (NAP) grant M4080738.020, Microsoft research grant FY12-RES-THEME-001, and NSFC grant No. 61272456. REFERENCES [1] “Alien Technology”, http://www.alientechnology.com [2] “CVX Research”, http://cvxr.com/cvx/ [3] “EPCglobal ClG2”, http://www.epcglobalinc.org/standards/uhfc1g2 [4] “Ettus Research”, http://www.ettus.com [5] “Gen 2 RFID Tools”, https://www.cgran.org/wiki/Gen2 [6] “`1-Magic”, http://users.ece.gatech.edu/ justin/l1magic/ [7] S. Boyd, “Convex Optimization”, Cambridge University Press, 2004. [8] M. Buettner and D. Wetherall, “An Empirical Study of UHF RFID Performance”, in ACM MobiCom, 2008. [9] E. Candes, J. Romberg, T. Tao, “Stable Signal Recovery from Incomplete ` and Inaccurate Measurements”, Communications on Pure and Applied Mathematics, vol. 59, issue 9. pp. 1207-1223, 2006. [10] J. I. Capetanakis, “Tree algorithms for packet broadcast channels”, IEEE Trans. on Information Theory, vol. 25, issue 5, pp. 505-515, 1979. [11] P.-Y. Chen, W.-T. Chen, Y.-C. Tseng, “Providing Group Tour Guide by RFIDs and Wireless Sensor Networks”, IEEE Transcations on Wireless Communications, vol. 8, issue 6, pp. 3059-3067, 2009. [12] D. Donoho, “Compressed sensing”, IEEE Transactions on Information Theory, vol. 52, issue 4, pp. 1289-1306, 2006. [13] J. Gummeson, P. Zhang, D. Ganesan, “Flit: A Bulk Transmission Protocol for RFID-Scale Sensors”, in ACM MobiSys, 2012. [14] D. Guo, Y. Liu, X. Li, and P. Yang, “False Negative Problem of Counting Bloom Filter”, IEEE Trans. on Knowledge and Data Engineering, vol. 22, issue 5, pp. 651-664, 2010. [15] H. Han, B. Sheng, C. C. Tan, Q. Li, W. Mao, and S. Lu, “Counting RFID Tags Efficiently and Anonymously”, in IEEE INFOCOM, 2010. [16] T. Li, S. Chen, and Y. Ling, “Identifying the Missing Tags in a Large RFID System”, in ACM MobiHoc, 2010. [17] C. Luo, F. Wu, J. Sun, C. W. Chen, “Compressive Data Gathering for Large-Scale Wireless Sensor Networks”, in ACM MobiCom, 2009. [18] L. M. Ni, Y. Liu, Y. C. Lau, and A. Patil, “LANDMARC: Indoor Location Sensing Using Active RFID”, ACM Wireless Networks, vol. 10, issue 6, pp. 701-710, 2004. [19] C. Qian, Y. Liu, H.-L. Ngan, and L. M. Ni, “ASAP: Scalable Identifi- cation and Counting for Contactless RFID Systems”, in IEEE ICDCS, 2010. [20] C. Qian, H. Ngan, and Y. Liu, “Cardinality Estimation for Large-scale RFID Systems”, IEEE Trans. on Parallel and Distributed Systems, vol. 22, issue 9, pp. 1441-1454, 2011. [21] L. G. Roberts, “Aloha Packet System with and without Slots and Capture ”, ACM SIGCOMM Computer Communication Review, vol. 5, issue 2, pp. 28-42, 1975. [22] C. C. Tan, B. Sheng, and Q. Li, “How to Monitor for Missing RFID Tags”, in IEEE ICDCS, 2008. [23] J. Wang, H. Hassanieh, D. Katabi, P. Indyk, “Efficient and Reliable Low-Power Backscatter Networks”, in ACM SIGCOMM, 2012. [24] L. Yang, J. Han, Y. Qi, C. Wang, T. Gu, and Y. Liu, “Season: Shelving Interference and Joint Identification in Large-scale RFID Systems”, in IEEE INFOCOM, 2011. [25] H. Yue, C. Zhang, M. Pan, Y. Fang, S. Chen, “A Time-efficient Information Collection Protocol for Large-scale RFID Systems”, in IEEE INFOCOM, 2012. [26] D. Zanetti, B. Danev, S. Capkun, “Physical-layer Identification of UHF ˇ RFID Tags”, in ACM MobiCom, 2010. [27] C. Zhang, Y. Zhang, Y. Fang, “A coverage inference protocol for wireless sensor networks”, IEEE Transactions on Mobile Computing, vol. 9, issue 6, pp. 850-864, June 2010. [28] R. Zhang, Y. Liu, Y. Zhang, and J. Sun, “Fast Identification of the Missing Tags in a Large RFID System”, in IEEE SECON, 2011. [29] H. Zhang, J. Gummeson, B. Ransford, and K. Fu, “Moo: A batteryless computational RFID and sensing platform”, Tech Report UMASS, 2011. http://spqr.cs.umass.edu/moo/ [30] P. Zhang, J. Gummeson, D. Ganesan, “BLINK: A High Throughput Link Layer for Backscatter Communication”, in ACM MobiSys, 2012. [31] Y. Zhang, L. T. Yang, and J. Chen “RFID and Sensor Networks: Architectures, Protocols, Security and Integrations”, Auerbach Publications, 2010. [32] Y. Zheng, M. Li, and C. Qian, “PET: Probabilistic Estimating Tree for Large-Scale RFID Estimation”, in IEEE ICDCS, 2011. [33] Y. Zheng and M. Li, “Fast Tag Searching Protocol for Large-Scale RFID Systems”, in IEEE ICNP, 2011