TABLE I TABLE III READING THROUGHPUT COMPARISON WHEN N VARIES FROM 1.000 TO TAG IDS RESOLVED FROM COLLISION SLOTS 20.000 N FCAT-2 FCAT-3 FCAT-4 FCAT-2 FCAT-3 FCAT-4 DFSA EDFSA ABS AQS 1000 423 600 707 1000 197.7 234.8 238.8 130.8 115.9 123.9 117.9 5000 2102 3008 3561 2000 199.5 237.2 257.5 131.8 21.5 123.7 119.4 10000 4139 5945 7065 3000 200.2 239.7 261.4 132.1 I22.9 123.8 120.4 15000 6062 8819 10482 4000 201.0 240.1 262.1 132.8 124.8 123.9 120.5 20000 7905 11507 13656 5000 201.3 240.4 262.3 130.1 126.1 123.8 120.8 6000 201.3 2415 263.7 132.4 126.3 123.6 120.9 300 7000 201.3 241.2 264.9 131.1 126.4 123.8 121.1 8000 201.4 241.8 265.1 131.9 127.1 123.6 121.1 250 9000 201.2 241.5 265.4 131.0 127.8 123.7 121.1 200 10000 201.3 241.8 265.1 131.4 127.8 123.9 121.2 % 11000 201.7 241.5 266.0 130.0 127.6 123.9 121.1 100 12000 200.8 241.8 265.9 130.3 126.8 123.8 121.2 FCAT-2 123.8 50 13000 201.0 241.7 265.9 129.2 127.3 121.2 FCAT-4 14000 200.4 241.3 266.2 130.9 127.6 123.5 121.3 0.5 1.5 22.5 15000 200.8 241.2 266.0 131.7 127.7 124.2 121.3 16000 200.9 241.8 265.9 131.3 128.2 123.8 121.3 17000 200.2 241.3 265.5 130.5 128.1 124.1 121.3 Fig.5.FCAT reading throughput with respect to w. 18000 199.7 240.7 265.9 130.0 128.2 123.6 121.3 19000 199.1 240.9 266.4 129.2 128.2 123.7 121.3 20000 199.1 241.3 266.1 129.1 128.6 123.9 121.3 set too small,the reading throughput decreases because many TABLE II slots are empty and thus wasted.Ifw is set too large,it also EMPTY,SINGLETON AND COLLISION TIME SLOTS WHEN N=10000 hurts the performance because there are too many collision slots and too many tags collide in those slots,making them FCAT-2 FCAT-3 FCAT-4 DFSA EDFSA ABS AOS unresolvable. empty 4189 2257 1345 10076 10705 4410 4737 By trying all possible values of w,we can use simulation to singleton 5861 4055 2935 10000 10000 10000 10000 find the true optimal w(and the corresponding optimal report collision 7016 7497 8050 7208 7234 14409 14735 probability)that maximizes the reading throughput.As shown total 17066 13809 12330 27284 27939 2881929472 in Table IV,the optimal value of w observed in the simulation matches closely with the value computed in Section IV-C,i.e., 1.414when入=2.1.817when入=3.and2.2l3when入=4 slots are wasted in FCAT than in all other compared protocols Also shown in the same table,the reading throughput achieved FCAT also uses much fewer singleton slots to collect all tag IDs because FCAT can extract tag information from the by FCAT using the computed reporting probability is almost the same as the maximum-achievable throughput under the collision slots,while other protocols have to read tags solely in the singleton slots.FCAT-4 has more collision slots than optimal reporting probability obtained by simulation through exhaustive search. FCAT-2.The reason is that FCAT-4 can utilize a collision slot in which up to four tags collide,and hence FCAT-4 encourages D.Impact of Frame Size more tags to transmit simultaneously. Fig.6 shows the impact of the frame size f in a system B.Effectiveness of Collision Resolution with 10,000 tags.We can see that the reading throughput is In Table III,we show the number of tag IDs that are stabilized when f≥l0. resolved from the collision slots.FCAT-2 obtains about 40% of tag IDs from the collision slots.The percentage is above VII.RELATED WORK 57%for FCAT-3 and above 68%for FCAT-4.For example, All existing contention-based tag reading protocols are when there are 10,000 tags in the system,FCAT-2 will read called anti-collision protocols because they treat collision as more than 4.000 of them from the collision slots,which are waste and try to avoid it [26].Most of these protocols fall into ignored by the previous protocols. two classes:the ALOHA-based protocols [4].[5].[6].[7].[8]. C.Report Probability The report probability p;is calculated as w/Ni.Ni is the TABLE IV number of tags participating in slot i and the method in THE COMPUTED VALUE OF w MATCHES CLOSELY WITH THE OPTIMAL Section V-C is used to estimate N;after each frame.The VALUE OF w OBTAINED BY SIMULATION. optimal value of w is set in Section IV-C.We use simulation to A Optimal w Maximum Throughput computed w FCAT Throughput confirm our analytical result and demonstrate how the value of 2 1.42 202.1 1.41 201.3 w affects the performance of FCAT.Fig.5 shows the reading 1.90 241.9 1.82 241.8 throughput with respect to w when there are 10000 tags.If w is 4 2.12 266.2 2.21 265.1 554TABLE I READING THROUGHPUT COMPARISON WHEN N VARIES FROM 1,000 TO 20,000 N FCAT-2 FCAT-3 FCAT-4 DFSA EDFSA ABS AQS 1000 197.7 234.8 238.8 130.8 115.9 123.9 117.9 2000 199.5 237.2 257.5 131.8 121.5 123.7 119.4 3000 200.2 239.7 261.4 132.1 122.9 123.8 120.4 4000 201.0 240.1 262.1 132.8 124.8 123.9 120.5 5000 201.3 240.4 262.3 130.1 126.1 123.8 120.8 6000 201.3 241.5 263.7 132.4 126.3 123.6 120.9 7000 201.3 241.2 264.9 131.1 126.4 123.8 121.1 8000 201.4 241.8 265.1 131.9 127.1 123.6 121.1 9000 201.2 241.5 265.4 131.0 127.8 123.7 121.1 10000 201.3 241.8 265.1 131.4 127.8 123.9 121.2 11000 201.7 241.5 266.0 130.0 127.6 123.9 121.1 12000 200.8 241.8 265.9 130.3 126.8 123.8 121.2 13000 201.0 241.7 265.9 129.2 127.3 123.8 121.2 14000 200.4 241.3 266.2 130.9 127.6 123.5 121.3 15000 200.8 241.2 266.0 131.7 127.7 124.2 121.3 16000 200.9 241.8 265.9 131.3 128.2 123.8 121.3 17000 200.2 241.3 265.5 130.5 128.1 124.1 121.3 18000 199.7 240.7 265.9 130.0 128.2 123.6 121.3 19000 199.1 240.9 266.4 129.2 128.2 123.7 121.3 20000 199.1 241.3 266.1 129.1 128.6 123.9 121.3 TABLE II EMPTY, SINGLETON AND COLLISION TIME SLOTS WHEN N = 10000 FCAT-2 FCAT-3 FCAT-4 DFSA EDFSA ABS AQS empty 4189 2257 1345 10076 10705 4410 4737 singleton 5861 4055 2935 10000 10000 10000 10000 collision 7016 7497 8050 7208 7234 14409 14735 total 17066 13809 12330 27284 27939 28819 29472 slots are wasted in FCAT than in all other compared protocols. FCAT also uses much fewer singleton slots to collect all tag IDs because FCAT can extract tag information from the collision slots, while other protocols have to read tags solely in the singleton slots. FCAT-4 has more collision slots than FCAT-2. The reason is that FCAT-4 can utilize a collision slot in which up to four tags collide, and hence FCAT-4 encourages more tags to transmit simultaneously. B. Effectiveness of Collision Resolution In Table III, we show the number of tag IDs that are resolved from the collision slots. FCAT-2 obtains about 40% of tag IDs from the collision slots. The percentage is above 57% for FCAT-3 and above 68% for FCAT-4. For example, when there are 10,000 tags in the system, FCAT-2 will read more than 4,000 of them from the collision slots, which are ignored by the previous protocols. C. Report Probability The report probability pi is calculated as ω/Ni. Ni is the number of tags participating in slot i and the method in Section V-C is used to estimate Ni after each frame. The optimal value of ω is set in Section IV-C. We use simulation to confirm our analytical result and demonstrate how the value of ω affects the performance of FCAT. Fig. 5 shows the reading throughput with respect to ω when there are 10000 tags. If ω is TABLE III TAG IDS RESOLVED FROM COLLISION SLOTS N FCAT-2 FCAT-3 FCAT-4 1000 423 600 707 5000 2102 3008 3561 10000 4139 5945 7065 15000 6062 8819 10482 20000 7905 11507 13656 0 50 100 150 200 250 300 0 0.5 1 1.5 2 2.5 3 reading throughput (tags/sec) ω FCAT-2 FCAT-3 FCAT-4 Fig. 5. FCAT reading throughput with respect to ω. set too small, the reading throughput decreases because many slots are empty and thus wasted. If ω is set too large, it also hurts the performance because there are too many collision slots and too many tags collide in those slots, making them unresolvable. By trying all possible values of ω, we can use simulation to find the true optimal ω (and the corresponding optimal report probability) that maximizes the reading throughput. As shown in Table IV, the optimal value of ω observed in the simulation matches closely with the value computed in Section IV-C, i.e., 1.414 when λ = 2, 1.817 when λ = 3, and 2.213 when λ = 4. Also shown in the same table, the reading throughput achieved by FCAT using the computed reporting probability is almost the same as the maximum-achievable throughput under the optimal reporting probability obtained by simulation through exhaustive search. D. Impact of Frame Size Fig. 6 shows the impact of the frame size f in a system with 10,000 tags. We can see that the reading throughput is stabilized when f ≥ 10. VII. RELATED WORK All existing contention-based tag reading protocols are called anti-collision protocols because they treat collision as waste and try to avoid it [26]. Most of these protocols fall into two classes: the ALOHA-based protocols [4], [5], [6], [7], [8], TABLE IV THE COMPUTED VALUE OF ω MATCHES CLOSELY WITH THE OPTIMAL VALUE OF ω OBTAINED BY SIMULATION. λ Optimal ω Maximum Throughput computed ω FCAT Throughput 2 1.42 202.1 1.41 201.3 3 1.90 241.9 1.82 241.8 4 2.12 266.2 2.21 265.1 554