We briefly describe the method used by Katti et al.Readers III.TERMINOLOGY AND PROBLEM DEFINITION are referred to [1]for more details.The ANC protocol is A.Terminology designed based on MSK (Minimum Shift Keying)[20]and has been implemented using software defined radios.The signal During the execution of a time-slotted contention-based transmitted by Alice can be represented as protocol,if no tag transmits in a time slot,we call it an empty s[n]=Aseio,In] slot.If one tag transmits,it is called a singleton slot.If more than one tag transmits,it is a collision slot.In particular,if where A is the amplitude of the nth sample and 0[n]is its k tags transmit simultaneously,the slot is called a k-collision phase.Similarly,Bob's signal can be represented as slot,where k 2.In order to guard against channel error, s[n]=Bseio.Inl. each ID carries a CRC code.In a singleton slot,the RFID reader receives the ID signal from a single tag.It will verify If Alice and Bob transmit simultaneously,the router will the correctness of the received ID by checking the CRC code. receive the sum of the two signals,which can be represented as B.Resolvable Collision Slots yin]=h'Asei(o,]+Y)+h"B.ei(oin+"). An empty slot is easy to identify because no signal is where h'and h"are the channel attenuation and and received.The reader can distinguish a singleton slot from a are the phase shift.We rewrite it for simplicity as collision slot by first converting the signal into an ID and then yIn]=Aeioln]+Beioinl (1) verifying the correctness of the CRC code.For a collision slot,the reader records a mixed signal that combines the where A=h'As,B h"Ba,0[n]=0(n]+Y,and on]= individual signals of the tags that transmit simultaneously.In sn]+".Upon receiving the mixed signal from the router. later singleton slots,the reader will receive the individual ID Alice can resolve A and B from the following two energy signals from some of those tags.When the reader eventually equations [21],[1], receives the ID signals from all but one of those tags,we say the k-collision slot is resolvable if we can derive the ID signal μ=E2]=A2+B2 of the last tag by removing the (-1)ID signals from the 口=二∑P=4P+B2+4ABa mixed signal.The experimental study of Analogy Network Coding by Katti et al.in [1]has shown that 2-collision slots lyin]2>u are resolvable. where E.is the expectation and W is a sampling window size.In MSK,a bit '1'is represented as a phase difference of C.Problem Definition /2 over a time interval t,whereas a bit'0'is represented as The main problem we want to solve in this paper is how to a phase difference of-/2 over t.For example,if the phase optimally apply analog network coding to maximize the RFID difference between the (n+1)thsample and the nth sample. reading throughput.We design a collision-aware tag identifi- n+l-θn,isπ/2，then a bit“I"is transmitted..Since cation protocol and derive the optimal report probability (at Alice knows her own signal,from (1),she can estimate the which a tag transmits its ID in each slot)that maximizes the phase differences of Bob's signal,n+1]-on],which can number of singleton and 2-collision slots (from which IDs can be translated into the bit stream sent by Bob [1]. be extracted by ANC). The task of resolving the mixed signal in a collision slot in In [1],the authors state that ANC can be applied to resolve a RFID system is simpler than the same task in the wireless collision involving more than two signals.On one hand,as network shown in Fig.2.First,Alice knows the amplitude of we will demonstrate in Section VI,resolving 2-collision slots her signal when it is transmitted out,but she does not know the based on today's technology will already provide a practically amplitude of her signal when it reaches the router and mixed significant boost to the reading throughout.On the other with Bob's signal.When Alice received the amplified mixed hand,instead of restricting our work to 2-collision slots,we signal from the router,it becomes difficult for her to remove decide to generalize our protocol so that it can work with her own signal from the mixed one.In the RFID system, any future ANC method that resolves A-collision slots,where suppose the reader receives the mixed signal from t1 and t2 A(>2)is an input parameter.Such generalization sheds in one slot and the individual signal of t in another slot. light on the amount of throughput gain that can possibly Because the same signal of ti appears in the two slots,it be obtained through analog network coding.In particular, becomes easier to remove it from the mixed signal. the results in Section VI show that the reading throughput Second,it is very difficult to synchronize transmissions will be higher when A is larger (because more collision slots between wireless nodes,and thus the proposed ANC protocol become useful).However,the rate of throughput improvement has to introduce a complicated mechanism to relieve this diminishes quickly as A increases.Hence,it is not necessary problem,whereas transmissions in a RFID system can be to make A too large.In practice,we expect A to be a small synchronized by the reader's signal. number (such as 2,3 or 4). Given that the technology for collision resolution exists, Clearly,ANC and other physical-layer network coding the next question is how to optimally use it to maximize the methods can be applied in various different communication performance of a wireless system.This paper will answer the contexts,each of which has its unique technical challenges. question in the context of RFID systems. For example,collision resolution has been used in satellite 549We briefly describe the method used by Katti et al. Readers are referred to [1] for more details. The ANC protocol is designed based on MSK (Minimum Shift Keying) [20] and has been implemented using software defined radios. The signal transmitted by Alice can be represented as s[n] = Aseiθs[n] , where As is the amplitude of the nth sample and θs[n] is its phase. Similarly, Bob’s signal can be represented as s[n] = Bseiφs[n] . If Alice and Bob transmit simultaneously, the router will receive the sum of the two signals, which can be represented as y[n] = h Asei(θs[n]+γ ) + hBsei(φs[n]+γ) , where h and h are the channel attenuation and γ and γ are the phase shift. We rewrite it for simplicity as y[n] = Aeiθ[n] + Beiφ[n] , (1) where A = h As, B = hBs, θ[n] = θs[n] + γ , and φ[n] = φs[n] + γ. Upon receiving the mixed signal from the router, Alice can resolve A and B from the following two energy equations [21], [1], μ = E[|y[n]| 2] = A2 + B2, σ = 2 W |y[n]|2>μ |y[n]| 2 = A2 + B2 + 4AB/π, where E[.] is the expectation and W is a sampling window size. In MSK, a bit ‘1’ is represented as a phase difference of π/2 over a time interval t, whereas a bit ‘0’ is represented as a phase difference of −π/2 over t. For example, if the phase difference between the (n + 1)th sample and the nth sample, θ[n + 1] − θ[n], is π/2, then a bit “1” is transmitted. Since Alice knows her own signal, from (1), she can estimate the phase differences of Bob’s signal, φ[n + 1] − φ[n], which can be translated into the bit stream sent by Bob [1]. The task of resolving the mixed signal in a collision slot in a RFID system is simpler than the same task in the wireless network shown in Fig. 2. First, Alice knows the amplitude of her signal when it is transmitted out, but she does not know the amplitude of her signal when it reaches the router and mixed with Bob’s signal. When Alice received the amplified mixed signal from the router, it becomes difficult for her to remove her own signal from the mixed one. In the RFID system, suppose the reader receives the mixed signal from t1 and t2 in one slot and the individual signal of t1 in another slot. Because the same signal of t1 appears in the two slots, it becomes easier to remove it from the mixed signal. Second, it is very difficult to synchronize transmissions between wireless nodes, and thus the proposed ANC protocol has to introduce a complicated mechanism to relieve this problem, whereas transmissions in a RFID system can be synchronized by the reader’s signal. Given that the technology for collision resolution exists, the next question is how to optimally use it to maximize the performance of a wireless system. This paper will answer the question in the context of RFID systems. III. TERMINOLOGY AND PROBLEM DEFINITION A. Terminology During the execution of a time-slotted contention-based protocol, if no tag transmits in a time slot, we call it an empty slot. If one tag transmits, it is called a singleton slot. If more than one tag transmits, it is a collision slot. In particular, if k tags transmit simultaneously, the slot is called a k-collision slot, where k ≥ 2. In order to guard against channel error, each ID carries a CRC code. In a singleton slot, the RFID reader receives the ID signal from a single tag. It will verify the correctness of the received ID by checking the CRC code. B. Resolvable Collision Slots An empty slot is easy to identify because no signal is received. The reader can distinguish a singleton slot from a collision slot by first converting the signal into an ID and then verifying the correctness of the CRC code. For a collision slot, the reader records a mixed signal that combines the individual signals of the tags that transmit simultaneously. In later singleton slots, the reader will receive the individual ID signals from some of those tags. When the reader eventually receives the ID signals from all but one of those tags, we say the k-collision slot is resolvable if we can derive the ID signal of the last tag by removing the (k − 1) ID signals from the mixed signal. The experimental study of Analogy Network Coding by Katti et al. in [1] has shown that 2-collision slots are resolvable. C. Problem Definition The main problem we want to solve in this paper is how to optimally apply analog network coding to maximize the RFID reading throughput. We design a collision-aware tag identifi- cation protocol and derive the optimal report probability (at which a tag transmits its ID in each slot) that maximizes the number of singleton and 2-collision slots (from which IDs can be extracted by ANC). In [1], the authors state that ANC can be applied to resolve collision involving more than two signals. On one hand, as we will demonstrate in Section VI, resolving 2-collision slots based on today’s technology will already provide a practically significant boost to the reading throughout. On the other hand, instead of restricting our work to 2-collision slots, we decide to generalize our protocol so that it can work with any future ANC method that resolves λ-collision slots, where λ (≥ 2) is an input parameter. Such generalization sheds light on the amount of throughput gain that can possibly be obtained through analog network coding. In particular, the results in Section VI show that the reading throughput will be higher when λ is larger (because more collision slots become useful). However, the rate of throughput improvement diminishes quickly as λ increases. Hence, it is not necessary to make λ too large. In practice, we expect λ to be a small number (such as 2, 3 or 4). Clearly, ANC and other physical-layer network coding methods can be applied in various different communication contexts, each of which has its unique technical challenges. For example, collision resolution has been used in satellite 549