We expect A to be small.In the following,we consider A= remove the collision record Ri 2.3,or4.When入=2，(2)becomes 20 end for 21. end while 2 22. broadcast a positive acknowledgement and the IDs in I 三PaX= 23.els 24. add(i,si》）as a collision record =Np,-p)N-1+-卫1-p)N-2 broadcast a negative acknowledgement 2 E.Unresolvable Collision Slots and Channel Error ≥Ne-Mm+竖亚e-N (3) The reading process normally takes a short period of time 2 (minutes for tens of thousands of tags).During this time,we Let w=Nip;.Substituting Nipi by w in (3),we have expect the tags to be statically located.The MSK employed by ANC can tolerate a certain level of noise and channel Prob(X=对≈w+兰 e-w (4) variation.However,if the spontaneous noise is too large,a = collision slot may not be resolvable.The only impact is that To find the value of w that maximizes the above formula,we the slot is not useful,and the reader can still learn the IDs differentiate the right side and let it be zero from other slots.A tag will stop transmitting only after it receives positive confirmation from the reader.As long as d(u+号)e-w dw 5=(1-元)e-w=0 most 2-collision slots can be resolved,the proposed protocol (5) still achieves much higher reading throughput. Solving the above equation,we have w =1.414.Hence,the Channel error may corrupt the signal transmitted by a tag or optimal report probability is pi=1.414/Ni. the acknowledgement transmitted by the reader.This problem Following the same process,we derive that,when A=3. is common to all RFID reading protocols.The solution is also the optimal report probability is pi=1.817/N,and when common:The tag will keep transmitting its ID until it receives 入=4，it is p5=2.213/N. the positive confirmation from the reader.In this case.the Resolving the collision slots requires a sufficient number of reader may receive an ID more than once and the duplicates will be discarded. singleton slots.Otherwise,if all slots have collision,none of them will be resolved.Fortunately,when A is small (which The proposed protocol is not suitable for an environment should be the case as we have discussed in Section III-C and where the channel noise is so severe or the tags move so will further elaborate in Section VI-A),there are sufficient much and so fast during the reading operation that most singleton slots to resolve most collision slots.Our simulation collision slots are not resolvable.In this case,we should use results in Section VI-C show that the optimal report proba- a contention-based protocol without collision resolution.It is bilities obtained by exhaustive search match closely with the beyond the scope of this paper to investigate the noise level of each specific environment.Instead,we are more interested in above computed values. knowing what is the upper limit of throughput improvement D.Pseudo Code that ANC can bring (in an environment where most 2-collision slots are resolvable). The pseudo code for the operation of the RFID reader during the ith slot is given below.Let S be the set of newly V.FRAMED COLLISION-AWARE TAG IDENTIFICATION known IDs (together with their signals)that can be used to PROTOCOL (FCAT) resolve some of the collision records.Let I be the set of IDs In this section,we propose a framed version of the previous that are learned by resolving the collision records.Let R;be the collision record for slot j. protocol to improve its efficiency. Reader's Operation at Slot i A.Inefficiencies of SCAT 1.broadcast an advertisement (i,pi) SCAT utilizes the information carried in the collision slots. 2.record the signal si in the report segment 3.extract IDi from si However,it is not practically efficient due to a number of 4. if the channel is idle during the report segment then reasons. 5. broadcast a negative acknowledgement First,to calculate pi,the RFID reader has to know Ni. 6. else if CRC in IDi is verified to be correct then which in turn requires it to know N.It incurs considerable 7. S:=IDi,si) overhead to accurately estimate the number of tags in the 1=0 9. while S≠0do system as a pre-step to SCAT.We want to remove such a 10. remove an element (ID,s)from S pre-step and estimate N as a byproduct during the protocol 11 for each collision record R;do execution. 12. ifH(IDli)≤p防then Second,the advertisement segment of each slot represents 13. add s to the set of known individual signals in Rj significant overhead which is not always necessary.For con- 14 remove known signals from the mixed signal in R 15. extract ID'from the resulting signal s' secutive slots,the slot index changes from i to i+1 and the 16 if CRC in ID'is verified to be correct then report probability changes from w/Ni to w/N+1.where Ni 17 S:=S+(ID',s)} and N+1 at most differ by one.As the report probability 18 I:=I+D' changes little when Ni is reasonably large,the reader does 551We expect λ to be small. In the following, we consider λ = 2, 3, or 4. When λ = 2, (2) becomes 2 k=1 P rob{Xi = k} = Nipi(1 − pi) Ni−1 + Ni(Ni − 1) 2 p2 i (1 − pi) Ni−2 Nipie−Nipi + N2 i p2 i 2 e−Nipi . (3) Let ω = Nipi. Substituting Nipi by ω in (3), we have 2 k=1 P rob{Xi = k} (ω + ω2 2 )e−ω. (4) To find the value of ω that maximizes the above formula, we differentiate the right side and let it be zero. d(ω + ω2 2 )e−ω dω = (1 − ω2 2 )e−ω = 0. (5) Solving the above equation, we have ω = 1.414. Hence, the optimal report probability is pi = 1.414/Ni. Following the same process, we derive that, when λ = 3, the optimal report probability is pi = 1.817/Ni, and when λ = 4, it is pi = 2.213/Ni. Resolving the collision slots requires a sufficient number of singleton slots. Otherwise, if all slots have collision, none of them will be resolved. Fortunately, when λ is small (which should be the case as we have discussed in Section III-C and will further elaborate in Section VI-A), there are sufficient singleton slots to resolve most collision slots. Our simulation results in Section VI-C show that the optimal report proba￾bilities obtained by exhaustive search match closely with the above computed values. D. Pseudo Code The pseudo code for the operation of the RFID reader during the ith slot is given below. Let S be the set of newly known IDs (together with their signals) that can be used to resolve some of the collision records. Let I be the set of IDs that are learned by resolving the collision records. Let Rj be the collision record for slot j. Reader’s Operation at Slot i 1. broadcast an advertisement i, pi 2. record the signal si in the report segment 3. extract IDi from si 4. if the channel is idle during the report segment then 5. broadcast a negative acknowledgement 6. else if CRC in IDi is verified to be correct then 7. S := {IDi, si} 8. I := ∅ 9. while S = ∅ do 10. remove an element ID, s from S 11. for each collision record Rj do 12. if H(ID|j) ≤ pj then 13. add s to the set of known individual signals in Rj 14. remove known signals from the mixed signal in Rj 15. extract ID from the resulting signal s 16. if CRC in ID is verified to be correct then 17. S := S + {ID , s } 18. I := I + {ID } 19. remove the collision record Rj 20. end for 21. end while 22. broadcast a positive acknowledgement and the IDs in I 23. else 24. add i, si as a collision record 25. broadcast a negative acknowledgement E. Unresolvable Collision Slots and Channel Error The reading process normally takes a short period of time (minutes for tens of thousands of tags). During this time, we expect the tags to be statically located. The MSK employed by ANC can tolerate a certain level of noise and channel variation. However, if the spontaneous noise is too large, a collision slot may not be resolvable. The only impact is that the slot is not useful, and the reader can still learn the IDs from other slots. A tag will stop transmitting only after it receives positive confirmation from the reader. As long as most 2-collision slots can be resolved, the proposed protocol still achieves much higher reading throughput. Channel error may corrupt the signal transmitted by a tag or the acknowledgement transmitted by the reader. This problem is common to all RFID reading protocols. The solution is also common: The tag will keep transmitting its ID until it receives the positive confirmation from the reader. In this case, the reader may receive an ID more than once and the duplicates will be discarded. The proposed protocol is not suitable for an environment where the channel noise is so severe or the tags move so much and so fast during the reading operation that most collision slots are not resolvable. In this case, we should use a contention-based protocol without collision resolution. It is beyond the scope of this paper to investigate the noise level of each specific environment. Instead, we are more interested in knowing what is the upper limit of throughput improvement that ANC can bring (in an environment where most 2-collision slots are resolvable). V. FRAMED COLLISION-AWARE TAG IDENTIFICATION PROTOCOL (FCAT) In this section, we propose a framed version of the previous protocol to improve its efficiency. A. Inefficiencies of SCAT SCAT utilizes the information carried in the collision slots. However, it is not practically efficient due to a number of reasons. First, to calculate pi, the RFID reader has to know Ni, which in turn requires it to know N. It incurs considerable overhead to accurately estimate the number of tags in the system as a pre-step to SCAT. We want to remove such a pre-step and estimate N as a byproduct during the protocol execution. Second, the advertisement segment of each slot represents significant overhead which is not always necessary. For con￾secutive slots, the slot index changes from i to i + 1 and the report probability changes from ω/Ni to ω/Ni+1, where Ni and Ni+1 at most differ by one. As the report probability changes little when Ni is reasonably large, the reader does 551