cation protocol that establishes the engineering and theoretical T T2 T3 T2 T4 T2 foundation for integrating analog network coding into the 1T3 T process of tag reading.We derive the optimal system param- (A)Contention-based protocol eters for improving the reading throughput.We also reduce the protocol overhead through a framed structure and an T3 embedded estimator for the number of tags that are currently T T3 participating in the protocol.The proposed protocol is able to efficiently utilize the information carried in collision slots and (B)Collision-resolution protocol thus break the fundamental limit of ALOHA-based protocols that do not use analog network coding.Our work answers two Fig.1. This example shows that a collision-resolution protocol may reduce the number of time slots used to identify four tags from 11 time slots to 6 important questions:How to optimally apply analog network time slots coding for RFID reading?How much throughput gain can analog network coding bring?The simulation results show that the reading throughput can be improved by 51.1%~70.6% when using today's analog network coding method and the Alice Bob throughput can be much higher if the coding method is improved in the future. The rest of the paper is organized as follows.Section II Fig.2.Alice-Bob example for Analog Network Coding. presents the motivation of our work.Section III gives the problem definition.Section IV proposes a collision-aware tag identification protocol and derives the optimal system 36.8%of the time slots will be idle and 26.4%of the slots will have collision. parameters.Section V improves the protocol for less over- head.Section VI presents the simulation results.Section VII Can we do better than We observe that the reading discusses the related work.Section VIII draws the conclusion. throughput can be improved if we make good use of the collision slots.Suppose the reader receives a mixed signal II.BACKGROUND in a collision slot when both tag ti and tag t2 transmit their IDs.In a later slot,if the reader receives the individual signal A.Motivation for the ID of tag t1,it can remove this signal from the mixed Consider a RFID system with a large number of active signal and recover the individual signal for the ID of tag t2. (or semi-active)tags deployed in a region.We assume that Consider the example in Fig.1,where four tags transmit the RFID reader and the tags transmit with sufficient power their IDs to the reader.In Fig.I (a),when a contention-based such that they can communicate over a long distance.The protocol is used,it takes 11 slots for the reader to collect all problem is for the reader to collect the IDs of all tags within four IDs.In Fig.1 (b),when a collision-resolution protocol the communication range.If the communication range cannot is used to resolve collision,only 6 slots are necessary.In cover the whole deployment region,the reader may have to particular,when the reader receives the signal from t in the perform the reading process at several locations and remove third slot,it removes this signal from the mixed signal received the duplicate IDs when some tags are covered by multiple in the first slot and recovers the ID of t.Similarly,when it readings.In this paper,we focus on the reading operation receives the signal from t3 in the sixth slot,it also learns the at a single location,Our goal is to optimize the reading ID of t2 from the fourth slot throughput,which is the average number of tag IDs that the reader is able to collect in each second. B.Analog Network Coding (ANC) During the reading process,multiple tags may transmit Can we remove an individual signal from a mixed signal to their IDs simultaneously,causing collision.Some collision- recover the other constituent signal?This question has recently avoidance methods such as FDMA or CDMA require so- been brought up in the context of physical-layer networking phisticated scheduling methods to minimize bandwidth waste code.Significant progress has been made in both theory and due to idle sub-channels or unused codes [18].The overhead implementation [1],[17]. for sophisticated scheduling can be too costly for a RFID Katti et al.implemented the Analog Network Coding system where each tag only needs to deliver one piece of (ANC)and demonstrated its effectiveness in the Alice-Bob information (i.e.,its ID)to the reader.Hence,contention-based network shown in Fig.2.Traditionally,four timeslots are time-slotted protocols have become the industrial standards needed for Alice and Bob to exchange a pair of messages: [19]1. Alice sends a message to the router and the router forwards In a contention-based protocol,each tag transmits its ID in it to Bob,and vice versa.However,by using ANC,only two a time slot with a report probability p that is tuned to reduce timeslots are necessary:Alice and Bob transmit simultane- collision.A tag stops when it receives the acknowledgement ously to the router.Instead of dropping the mixed signal,the from the reader that its ID has been successfully received. router simply amplifies and broadcasts it to both Alice and It can be shown that the optimal reading throughput is Bob.Alice subtracts her own signal from the mixed signal theoretically bounded bywhere e is the natural constant and decodes Bob's message.Similarly,Bob can extract Alice's and T is the length of a time slot [11].In such a protocol, message. 548cation protocol that establishes the engineering and theoretical foundation for integrating analog network coding into the process of tag reading. We derive the optimal system param￾eters for improving the reading throughput. We also reduce the protocol overhead through a framed structure and an embedded estimator for the number of tags that are currently participating in the protocol. The proposed protocol is able to efficiently utilize the information carried in collision slots and thus break the fundamental limit of ALOHA-based protocols that do not use analog network coding. Our work answers two important questions: How to optimally apply analog network coding for RFID reading? How much throughput gain can analog network coding bring? The simulation results show that the reading throughput can be improved by 51.1% ∼ 70.6% when using today’s analog network coding method and the throughput can be much higher if the coding method is improved in the future. The rest of the paper is organized as follows. Section II presents the motivation of our work. Section III gives the problem definition. Section IV proposes a collision-aware tag identification protocol and derives the optimal system parameters. Section V improves the protocol for less over￾head. Section VI presents the simulation results. Section VII discusses the related work. Section VIII draws the conclusion. II. BACKGROUND A. Motivation Consider a RFID system with a large number of active (or semi-active) tags deployed in a region. We assume that the RFID reader and the tags transmit with sufficient power such that they can communicate over a long distance. The problem is for the reader to collect the IDs of all tags within the communication range. If the communication range cannot cover the whole deployment region, the reader may have to perform the reading process at several locations and remove the duplicate IDs when some tags are covered by multiple readings. In this paper, we focus on the reading operation at a single location, Our goal is to optimize the reading throughput, which is the average number of tag IDs that the reader is able to collect in each second. During the reading process, multiple tags may transmit their IDs simultaneously, causing collision. Some collision￾avoidance methods such as FDMA or CDMA require so￾phisticated scheduling methods to minimize bandwidth waste due to idle sub-channels or unused codes [18]. The overhead for sophisticated scheduling can be too costly for a RFID system where each tag only needs to deliver one piece of information (i.e., its ID) to the reader. Hence, contention-based time-slotted protocols have become the industrial standards [19]. In a contention-based protocol, each tag transmits its ID in a time slot with a report probability p that is tuned to reduce collision. A tag stops when it receives the acknowledgement from the reader that its ID has been successfully received. It can be shown that the optimal reading throughput is theoretically bounded by 1 eT , where e is the natural constant and T is the length of a time slot [11]. In such a protocol, Fig. 1. This example shows that a collision-resolution protocol may reduce the number of time slots used to identify four tags from 11 time slots to 6 time slots. Fig. 2. Alice-Bob example for Analog Network Coding. 36.8% of the time slots will be idle and 26.4% of the slots will have collision. Can we do better than 1 eT ? We observe that the reading throughput can be improved if we make good use of the collision slots. Suppose the reader receives a mixed signal in a collision slot when both tag t1 and tag t2 transmit their IDs. In a later slot, if the reader receives the individual signal for the ID of tag t1, it can remove this signal from the mixed signal and recover the individual signal for the ID of tag t2. Consider the example in Fig. 1, where four tags transmit their IDs to the reader. In Fig. 1 (a), when a contention-based protocol is used, it takes 11 slots for the reader to collect all four IDs. In Fig. 1 (b), when a collision-resolution protocol is used to resolve collision, only 6 slots are necessary. In particular, when the reader receives the signal from t1 in the third slot, it removes this signal from the mixed signal received in the first slot and recovers the ID of t4. Similarly, when it receives the signal from t3 in the sixth slot, it also learns the ID of t2 from the fourth slot. B. Analog Network Coding (ANC) Can we remove an individual signal from a mixed signal to recover the other constituent signal? This question has recently been brought up in the context of physical-layer networking code. Significant progress has been made in both theory and implementation [1], [17]. Katti et al. implemented the Analog Network Coding (ANC) and demonstrated its effectiveness in the Alice-Bob network shown in Fig. 2. Traditionally, four timeslots are needed for Alice and Bob to exchange a pair of messages: Alice sends a message to the router and the router forwards it to Bob, and vice versa. However, by using ANC, only two timeslots are necessary: Alice and Bob transmit simultane￾ously to the router. Instead of dropping the mixed signal, the router simply amplifies and broadcasts it to both Alice and Bob. Alice subtracts her own signal from the mixed signal and decodes Bob’s message. Similarly, Bob can extract Alice’s message. 548