RFID标签识别机制-冲突以及防冲突算法研究（参考文献）P-MTI - Physical-layer Missing Tag Identification via Compressive Sensing

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

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 sig￾nals 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 manda￾tory 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 } repre￾senting 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 phys￾ical 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 frame￾slotted 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 con￾duct 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 com￾ponents). 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, P￾MTI 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 mon￾itoring 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 aggre￾gated symbols, A is an M × N binary matrix, and x is an N￾entry 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 mathemat￾ically 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 <e, (7) monitoring N during a short monitoring interval,i.e.,N where the magnitude e is bounded by e,i.e.,llelle<e.The K>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 mon￾itoring 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 straight￾forward: 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 in￾corporates 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 K￾sparse 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 dy￾namics 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, P￾MTI 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 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￾sonably 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 con￾straints, 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 off￾the-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 recon￾struction 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 chan￾nel 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