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 P￾MTI 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 sched￾ule multiple readers and achieve interrogation among non￾overlapping readers in parallel, while IIP views multiple read￾ers 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-