2010 International Conference on Distributed Computing Systems Using Analog Network Coding to Improve the RFID Reading Throughput Ming Zhang Tao Li Shigang Chen Bo Li Department of Computer Information Science Engineering University of Florida,Gainesville,FL 32611,USA Abstract-RFID promises to revolutionize the inventory man- reading throughput,which is the average number of unique agement in large warehouses,retail stores,hospitals,transporta- tag IDs that the reader can collect in a second.The current tion systems,etc.Periodically reading the IDs of the tags is an protocols have reached the physical throughput limit that can important function to guard against administration error,vendor fraud and employee theft.Given the low-speed communication be achieved based on their design methods.In the time-slotted channel in which a RFID system operates,the reading through- ALOHA-based protocols [4].[5].[6].[7].[8].[9],[10].a tag put is one of the most important performance metrics.The transmits its ID in each time slot (or some slot in a frame) current protocols have reached the physical throughput limit that with a certain probability p until the receipt of its ID is can possibly be achieved based on their design methods.To break acknowledged by the RFID reader.The reading throughput that limit,we have to apply fundamentally different approaches. This paper investigates how much throughput improvement the is fundamentally limited by the probabilistic collision that analog network coding [1]can bring when it is integrated into occurs in ALOHA-based networks.The optimal throughput the RFID protocols.The idea is to extract useful information is.where e is the natural constant and T is the length of from collision slots when multiple tags transmit their IDs a time slot [11].It is achieved when p is chosen such that simultaneously.Traditionally,those slots are discarded.With the probability for exactly one tag transmitting in each slot analog network coding,we show that a collision slot is almost as useful as a non-collision slot in which exactly one tag transmits. is 36.8%.The other major class is the tree-based protocols. We propose the framed collision-aware tag identification protocol which organize the reading process in a binary tree struc- that optimally applies analog network coding to maximize the ture [12],[131.[14]and improve the reading throughput by reading throughput,which is 51.1%~70.6%higher than the balancing the tree [12],[15],[16].Analytical and simulation best existing protocols results have shown that the best performance of the tree-based protocols is comparable to the best of the ALOHA-based I.INTRODUCTION protocols. The barcode system brings numerous benefits for the retail To break the fundamental limit of the ALOHA-based proto- stores.It speeds up the checkout process,makes the price cols,we have to resort to fundamentally different approaches change easier,and allows quick access for the properties In this paper,we apply the recently-proposed analog network of each merchandize item.It also has serious limitation.A coding scheme [1]to RFID systems and investigate how barcode can only be read in close range.Suppose an inventory significantly it can improve the reading throughput. management policy requires periodical reading of all items What limits the throughput of the ALOHA-based protocols? in order to guard against administration error,vendor fraud Radio collision,which happens when more than one tag trans- and employee theft.One will have to use a portable laser mits in a slot.The conventional wisdom is that collision slots scanner and manually read the barcodes one after another, do not carry useful information and therefore those slots are which is tedious and error-prone.RFID tags,which can be wasted.That is however not true.Recent research shows that, read wirelessly,provide an ideal solution to this problem [2]. by embracing the interference of wireless communication, [3].Each tag carries a unique identification number (ID),and physical-layer network coding can significantly improve the a RFID reader can retrieve the ID of a tag even when there network throughput [17].In particular,the analog network are obstacles between them.Although the passive tags are coding scheme [1]has been experimentally implemented. most popular,they are not suitable for automated inventory However,its usefulness has only been demonstrated under management in a large area because they can only be read in a “toy”examples.. few meters.In order to read all tags,we have to either deploy The contributions in this paper are two-fold:First,we numerous readers,each covering a small area,or manually optimally integrate analog network coding into the RFID move a reader around,which is again inefficient and error- system to maximize the reading throughput by making some prone.This paper considers the battery-powered active (or collision slots almost as useful as non-collision slots (in which semi-passive)tags that can be read in a long distance and only one tag transmits).The difference is that the former allow have more software/hardware resources than the passive tags. the RFID reader to learn new tag IDs after some time,while The communication between the RFID reader and the the latter let the reader learn new IDs right away.Second,we tags is operated in a low-speed channel.Yet the number of demonstrate the practical value of the analog network coding tags in a large RFID system is expected to be very large. research by providing an interesting application scenario. Therefore,one of the most critical performance metrics is the Technically,we design the first collision-aware tag identifi- IEEE 1063-69272010 547 Φcomputer U.S.Government Work Not Protected by U.S.Copyright society D0I10.1109/ICDCS.2010.48
Using Analog Network Coding to Improve the RFID Reading Throughput Ming Zhang Tao Li Shigang Chen Bo Li Department of Computer & Information Science & Engineering University of Florida, Gainesville, FL 32611, USA Abstract—RFID promises to revolutionize the inventory management in large warehouses, retail stores, hospitals, transportation systems, etc. Periodically reading the IDs of the tags is an important function to guard against administration error, vendor fraud and employee theft. Given the low-speed communication channel in which a RFID system operates, the reading throughput is one of the most important performance metrics. The current protocols have reached the physical throughput limit that can possibly be achieved based on their design methods. To break that limit, we have to apply fundamentally different approaches. This paper investigates how much throughput improvement the analog network coding [1] can bring when it is integrated into the RFID protocols. The idea is to extract useful information from collision slots when multiple tags transmit their IDs simultaneously. Traditionally, those slots are discarded. With analog network coding, we show that a collision slot is almost as useful as a non-collision slot in which exactly one tag transmits. We propose the framed collision-aware tag identification protocol that optimally applies analog network coding to maximize the reading throughput, which is 51.1% ∼ 70.6% higher than the best existing protocols. I. INTRODUCTION The barcode system brings numerous benefits for the retail stores. It speeds up the checkout process, makes the price change easier, and allows quick access for the properties of each merchandize item. It also has serious limitation. A barcode can only be read in close range. Suppose an inventory management policy requires periodical reading of all items in order to guard against administration error, vendor fraud and employee theft. One will have to use a portable laser scanner and manually read the barcodes one after another, which is tedious and error-prone. RFID tags, which can be read wirelessly, provide an ideal solution to this problem [2], [3]. Each tag carries a unique identification number (ID), and a RFID reader can retrieve the ID of a tag even when there are obstacles between them. Although the passive tags are most popular, they are not suitable for automated inventory management in a large area because they can only be read in a few meters. In order to read all tags, we have to either deploy numerous readers, each covering a small area, or manually move a reader around, which is again inefficient and errorprone. This paper considers the battery-powered active (or semi-passive) tags that can be read in a long distance and have more software/hardware resources than the passive tags. The communication between the RFID reader and the tags is operated in a low-speed channel. Yet the number of tags in a large RFID system is expected to be very large. Therefore, one of the most critical performance metrics is the reading throughput, which is the average number of unique tag IDs that the reader can collect in a second. The current protocols have reached the physical throughput limit that can be achieved based on their design methods. In the time-slotted ALOHA-based protocols [4], [5], [6], [7], [8], [9], [10], a tag transmits its ID in each time slot (or some slot in a frame) with a certain probability p until the receipt of its ID is acknowledged by the RFID reader. The reading throughput is fundamentally limited by the probabilistic collision that occurs in ALOHA-based networks. The optimal throughput is 1 eT , where e is the natural constant and T is the length of a time slot [11]. It is achieved when p is chosen such that the probability for exactly one tag transmitting in each slot is 36.8%. The other major class is the tree-based protocols, which organize the reading process in a binary tree structure [12], [13], [14] and improve the reading throughput by balancing the tree [12], [15], [16]. Analytical and simulation results have shown that the best performance of the tree-based protocols is comparable to the best of the ALOHA-based protocols. To break the fundamental limit of the ALOHA-based protocols, we have to resort to fundamentally different approaches. In this paper, we apply the recently-proposed analog network coding scheme [1] to RFID systems and investigate how significantly it can improve the reading throughput. What limits the throughput of the ALOHA-based protocols? Radio collision, which happens when more than one tag transmits in a slot. The conventional wisdom is that collision slots do not carry useful information and therefore those slots are wasted. That is however not true. Recent research shows that, by embracing the interference of wireless communication, physical-layer network coding can significantly improve the network throughput [17]. In particular, the analog network coding scheme [1] has been experimentally implemented. However, its usefulness has only been demonstrated under “toy” examples. The contributions in this paper are two-fold: First, we optimally integrate analog network coding into the RFID system to maximize the reading throughput by making some collision slots almost as useful as non-collision slots (in which only one tag transmits). The difference is that the former allow the RFID reader to learn new tag IDs after some time, while the latter let the reader learn new IDs right away. Second, we demonstrate the practical value of the analog network coding research by providing an interesting application scenario. Technically, we design the first collision-aware tag identifi- 2010 International Conference on Distributed Computing Systems 1063-6927 2010 U.S. Government Work Not Protected by U.S. Copyright DOI 10.1109/ICDCS.2010.48 547
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. 548
cation protocol that establishes the engineering and theoretical foundation for integrating analog network coding into the process of tag reading. We derive the optimal system parameters 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 overhead. 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 collisionavoidance methods such as FDMA or CDMA require sophisticated 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 simultaneously 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
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 549
We 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
access networks,where each terminal transmits a single packet slots,it sets pi=1 for one slot and if it still finds an empty twice at two randomly-selected time slots in each MAC frame slot,it knows that the IDs of all tags have been collected. [22].The throughput upper bound can be predicted if the number of packets per slot is known (which requires the B.Collision Resolution knowledge of the number of transmitting terminals).In our When the CRC received in the report segment is verified to context,we do not derive a throughput upper bound for a be correct,the reader learns the ID of a tag from the current given set of system parameters.Instead,we determine the slot i.Knowing the ID,the RFID reader can easily figure out best system parameter that optimizes the throughput.We do the previous slots in which this tag has transmitted.For an not assume the knowledge for the number of tags that is arbitrary collision record with slot index j,the tag must have participating in the protocol.In fact,this number changes over transmitted if H(Dlj)≤lp:×2」.If that is the case,the time because after a tag successfully delivers its ID to the reader removes the signal received in the current slot from reader,it will stop transmitting.A tag may transmit for one, the mixed signal in the collision record,treats the result as two or more times at any time slots during the reading process. if it was the ID signal of a single tag,and extracts the CRC Moreover,because the number of participating tags changes, code.If the CRC code is verified to be correct,the collision the optimal system parameter also changes over time. record is resolved and the reader learns an additional tag ID. IV.SLOTTED COLLISION-AWARE TAG IDENTIFICATION The signal for that ID can be used to resolve other collision records in a similar process as described above. PROTOCOL Resolving the collision slots incurs computation overhead. In this section,we propose the Slotted Collision-Aware Tag Hence,we expect the reader to be computationally capable or identification protocol (SCAT).In the next section,we will connected to a powerful computing device.It is worth noting optimize the protocol for less overhead. that the RFID system works in a low speed channel (53 Kbps A.Protocol Description for the Philips I-Code system),while the original ANC [1] SCAT is a time-slotted protocol.The time slots are synchro- and the follow-up work [23]are designed for 11 Mbps or higher throughput channels,which is far more demanding, nized by the reader's signal.Each time slot consists of three yet experimentally-demonstrated feasible. segments:the advertisement segment,the report segment,and the acknowledgement segment. C.Determining the Optimal Value for Pi In the advertisement segment,the RFID reader sends out a We want to determine the optimal report probability pi for slot index i and a report probabiliry pi,where i begins from each slot such that the number of slots for collecting the IDs zero and increases by one after each slot. of all tags is minimized.Consider an arbitrary time slot with In the report segment,each tag decides to transmit its ID with probability pi.To actually broadcast the report prob- index i.When there is only one tag transmitting,the RFID ability,the reader may send out an l-bit integer pix 2] reader will learn the ID of the tag.If there are two tags transmitting,the reader will not learn any ID now but will instead of a real number pi.A tag computes a hash function H(IDli)whose range is [0.2).IfH(Dli)≤p:×2」，the learn one ID later when the other ID is known (such that the collision record of this slot can be resolved).Similarly,when tag transmits its ID】 k tags transmit in this slot for k≤入，the reader will learn For an empty slot,the reader transmits a negative acknowl- edgement.For a collision slot,the reader will not be able one ID from the collision record when the other (k-1)IDs are known.Essentially,a singleton slot or a k-collision slot to tell how many tags have transmitted simultaneously in the report segment.It will record the mixed signal and transmit will allow the reader to learn one ID now or later.Hence,we a negative acknowledgement.The mixed signal and the slot shall choose the value of pi that maximizes the probability index form a collision record.Over time the reader will collect for one,two,.,or A tags to transmit in the current slot. Let N be the number of tags in the system.Its value can a group of such records.The operation for a singleton slot is more complicated.The reader learns the ID of a tag in the be estimated to an arbitrary accuracy [24]in a pre-step of report segment.Using this ID,it tries to resolve some collision SCAT.This pre-step will be removed in the next section. Before slot i,the reader may have successfully collected and records to learn more tag IDs (see the next subsection).It then transmits a positive acknowledgement,together with the IDs acknowledged a number ni of tag IDs,and those tags will that are learned from the resolution of the previous collision no longer participate in the protocol of SCAT.Let N be the number of tags that the reader has not identified yet before records. When the tag that transmits in the report segment receives slot i.Since ni is known to the reader,Ni is also known. the positive acknowledgement,it will stop participating in the As each tag decides to transmit with probability pi,the SCAT protocol as its ID has been successfully delivered to number of tags that transmit will be a random variable X;that follows the binomial distribution.The probability for Xi=k. the reader.Similarly,when a tag that transmitted its ID at an earlier slot but has not received a positive acknowledgement k∈[0Nis(）·p(1-ps)Ne-k.Our objective is to yet receives its own ID in the acknowledgement segment,it maximize the probability of Xi [0..A,which is will stop participating in SCAT. The SCAT protocol stops when no tag transmits any more. When the reader finds a certain number of consecutive empty =-（）-w四 550
access networks, where each terminal transmits a single packet twice at two randomly-selected time slots in each MAC frame [22]. The throughput upper bound can be predicted if the number of packets per slot is known (which requires the knowledge of the number of transmitting terminals). In our context, we do not derive a throughput upper bound for a given set of system parameters. Instead, we determine the best system parameter that optimizes the throughput. We do not assume the knowledge for the number of tags that is participating in the protocol. In fact, this number changes over time because after a tag successfully delivers its ID to the reader, it will stop transmitting. A tag may transmit for one, two or more times at any time slots during the reading process. Moreover, because the number of participating tags changes, the optimal system parameter also changes over time. IV. SLOTTED COLLISION-AWARE TAG IDENTIFICATION PROTOCOL In this section, we propose the Slotted Collision-Aware Tag identification protocol (SCAT). In the next section, we will optimize the protocol for less overhead. A. Protocol Description SCAT is a time-slotted protocol. The time slots are synchronized by the reader’s signal. Each time slot consists of three segments: the advertisement segment, the report segment, and the acknowledgement segment. In the advertisement segment, the RFID reader sends out a slot index i and a report probability pi, where i begins from zero and increases by one after each slot. In the report segment, each tag decides to transmit its ID with probability pi. To actually broadcast the report probability, the reader may send out an l-bit integer pi × 2l instead of a real number pi. A tag computes a hash function H(ID|i) whose range is [0..2l ). If H(ID|i) ≤ pi × 2l , the tag transmits its ID. For an empty slot, the reader transmits a negative acknowledgement. For a collision slot, the reader will not be able to tell how many tags have transmitted simultaneously in the report segment. It will record the mixed signal and transmit a negative acknowledgement. The mixed signal and the slot index form a collision record. Over time the reader will collect a group of such records. The operation for a singleton slot is more complicated. The reader learns the ID of a tag in the report segment. Using this ID, it tries to resolve some collision records to learn more tag IDs (see the next subsection). It then transmits a positive acknowledgement, together with the IDs that are learned from the resolution of the previous collision records. When the tag that transmits in the report segment receives the positive acknowledgement, it will stop participating in the SCAT protocol as its ID has been successfully delivered to the reader. Similarly, when a tag that transmitted its ID at an earlier slot but has not received a positive acknowledgement yet receives its own ID in the acknowledgement segment, it will stop participating in SCAT. The SCAT protocol stops when no tag transmits any more. When the reader finds a certain number of consecutive empty slots, it sets pi = 1 for one slot and if it still finds an empty slot, it knows that the IDs of all tags have been collected. B. Collision Resolution When the CRC received in the report segment is verified to be correct, the reader learns the ID of a tag from the current slot i. Knowing the ID, the RFID reader can easily figure out the previous slots in which this tag has transmitted. For an arbitrary collision record with slot index j, the tag must have transmitted if H(ID|j) ≤ pi × 2l . If that is the case, the reader removes the signal received in the current slot from the mixed signal in the collision record, treats the result as if it was the ID signal of a single tag, and extracts the CRC code. If the CRC code is verified to be correct, the collision record is resolved and the reader learns an additional tag ID. The signal for that ID can be used to resolve other collision records in a similar process as described above. Resolving the collision slots incurs computation overhead. Hence, we expect the reader to be computationally capable or connected to a powerful computing device. It is worth noting that the RFID system works in a low speed channel (53 Kbps for the Philips I-Code system), while the original ANC [1] and the follow-up work [23] are designed for 11 Mbps or higher throughput channels, which is far more demanding, yet experimentally-demonstrated feasible. C. Determining the Optimal Value for pi We want to determine the optimal report probability pi for each slot such that the number of slots for collecting the IDs of all tags is minimized. Consider an arbitrary time slot with index i. When there is only one tag transmitting, the RFID reader will learn the ID of the tag. If there are two tags transmitting, the reader will not learn any ID now but will learn one ID later when the other ID is known (such that the collision record of this slot can be resolved). Similarly, when k tags transmit in this slot for k ≤ λ, the reader will learn one ID from the collision record when the other (k − 1) IDs are known. Essentially, a singleton slot or a k-collision slot will allow the reader to learn one ID now or later. Hence, we shall choose the value of pi that maximizes the probability for one, two, ..., or λ tags to transmit in the current slot. Let N be the number of tags in the system. Its value can be estimated to an arbitrary accuracy [24] in a pre-step of SCAT. This pre-step will be removed in the next section. Before slot i, the reader may have successfully collected and acknowledged a number ni of tag IDs, and those tags will no longer participate in the protocol of SCAT. Let Ni be the number of tags that the reader has not identified yet before slot i. Since ni is known to the reader, Ni is also known. As each tag decides to transmit with probability pi, the number of tags that transmit will be a random variable Xi that follows the binomial distribution. The probability for Xi = k, ∀k ∈ [0..Ni] is Ni k · pk i (1 − pi)Ni−k. Our objective is to maximize the probability of Xi ∈ [0..λ], which is λ k=1 P rob{Xi = k} = λ k=1 Ni k · pk i (1 − pi) Ni−k. (2) 550
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 551
We 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 probabilities 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 consecutive 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