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 tagimprovement 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