RFID标签识别机制-冲突以及防冲突算法研究（参考文献）Using Analog Network Coding to Improve the RFID Reading Throughput

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 man￾agement in large warehouses, retail stores, hospitals, transporta￾tion 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 through￾put 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 error￾prone. 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 struc￾ture [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 proto￾cols, 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 trans￾mits 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 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

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 synchro￾nized 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 prob￾ability, 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 acknowl￾edgement. 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 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

not have to make advertisement in each slot.It may advertise at most once in the frame.In FCAT,each tag participates once every certain number of slots,and the tags will use the probabilistically in every slot of the frame. same report probability in those slots. Let Xi be the indicator random variable for the event that Third,after resolving a collision record,the reader learns the jth slot in the frame is empty.i.e.,X;=1 means the jth an extra ID and it broadcasts the ID in order to inform slot is empty and Xj=0 means it is not empty.Similarly.let the corresponding tag to stop participating in the protocol. Yi be the indicator random variable for the event that the jth However,instead of transmitting the whole ID (which is 96 slot is a singleton slot.Because each tag decides to transmit bits for GEN2 tags),the reader may transmit the slot index with probability pi in every slot in the frame,we have of the collision record.A tag stores the indices of the slots in which it has transmitted.If the tag receives a slot index Prob(Xj =1)=(1-pi)N,vje[1..f]. (6 that matches a stored one,it knows that the reader must have The expected value of no is collected its ID.A slot index can be much smaller than 96 bits.If we use 23-bit slot indices,more than 8 million slots are allowed.In our simulations,the number of slots required E(no)=(1-P)N=f(1-)4 (7) j=1 never exceeds2W」 The probability for the jth slot in the frame to be a singleton B.Using Frames is We propose the Framed Collision-Aware Tag identification protocol (FCAT),which improves SCAT by eliminating the Prof-1)-(N)p.(1-p)-1-Np(1-p)-1. inefficiency described in Section V-A.FCAT shares much (8) of the protocol details with SCAT.Below we will focus on describing their differences. The expected value of nI is In FCAT,time is divided into frames of size f.That is, each frame consists of f time slots.Each frame has an index, starting from zero.The index of the jth slot in the ith frame is En）)=∑Np1-p.)M-1=fN1-)M-1.9) i=l ix f+j.Before a frame begins,the RFID reader broadcasts Obviously,E(no)+E(n1)+E(ne)=f.Hence a pre-frame advertisement,including the frame index i and the report probability pi.Each slot of the frame consists of E(ne)=f-E(no)-E(n1) a report segment,during which the tags transmit their IDs, =f(1-(1-p)N-NP(1-p)N-1) and an acknowledgement segment,during which the reader (10) transmits either a positive acknowledgement or a negative =f1-(1-p)-1(1-p:+w) acknowledgement. The above equation can be rewritten as In any slot of the ith frame,each tag transmits its ID with probability pi.After receiving the signal in the report segment, N:= 1-2)-n1-%+ +1. (11) the reader performs the same operations as in SCAT,except n(1-p) that it does not transmit the IDs learned from resolving the At the end of the ith frame,the reader counts the value of collision records in the acknowledgement segment.Instead, ne.Substituting E(nc)by the instance value ne (obtained in it transmits the slot indices of the resolved collision records, the ith frame),the reader obtains an estimation of Ni by the which are shorter than the IDs themselves.If a tag receives a following formula: slot index that matches a slot in which it has transmitted its ID,it stops participating in FCAT.Certainly,if a tag receives 1-学)-n1-+w）+1. Ni= (12) a positive acknowledgement for its ID just transmitted in the In(1-Pi) report segment,it will also stop participating in FCAT. Next,we derive E(N;).To simplify the equations,let C1= C.Estimating the Number of Tags within FCAT Ca=+1,and function g(ne)=mn(1 In(1-Pi) Finally,we address the problem of how to learn the value of )We expand the right hand side of(12)by its Taylor series N.There exist efficient methods for estimating the number of about g=E(ne). tags.However,using them as a pre-step of FCAT incurs con- siderable overhead.In the following,we embed an estimation method within FCAT. )+(n-)+(nc-q)"(a) Consider an arbitrary frame with index i.Let no,ni and ne be the random variables for the numbers of empty,singleton ne"++C.(13) and collision slots,respectively.We can estimate the statistical Since q=E(nc).the mean of the second term in (13)is 0. relationship between these random variables and the number Therefore,we keep the first three terms when computing the Na of tags that are currently participating in the protocol. approximated value of E(Ni). Based on that relationship,we can estimate Ni from the measured values of no and ne.Our approach shares some similarity with [24].However,in [24],each tag transmits E()=C(+((ne)+Ca.(14) 552

not have to make advertisement in each slot. It may advertise once every certain number of slots, and the tags will use the same report probability in those slots. Third, after resolving a collision record, the reader learns an extra ID and it broadcasts the ID in order to inform the corresponding tag to stop participating in the protocol. However, instead of transmitting the whole ID (which is 96 bits for GEN2 tags), the reader may transmit the slot index of the collision record. A tag stores the indices of the slots in which it has transmitted. If the tag receives a slot index that matches a stored one, it knows that the reader must have collected its ID. A slot index can be much smaller than 96 bits. If we use 23-bit slot indices, more than 8 million slots are allowed. In our simulations, the number of slots required never exceeds 2N. B. Using Frames We propose the Framed Collision-Aware Tag identification protocol (FCAT), which improves SCAT by eliminating the inefficiency described in Section V-A. FCAT shares much of the protocol details with SCAT. Below we will focus on describing their differences. In FCAT, time is divided into frames of size f. That is, each frame consists of f time slots. Each frame has an index, starting from zero. The index of the jth slot in the ith frame is i × f + j. Before a frame begins, the RFID reader broadcasts a pre-frame advertisement, including the frame index i and the report probability pi. Each slot of the frame consists of a report segment, during which the tags transmit their IDs, and an acknowledgement segment, during which the reader transmits either a positive acknowledgement or a negative acknowledgement. In any slot of the ith frame, each tag transmits its ID with probability pi. After receiving the signal in the report segment, the reader performs the same operations as in SCAT, except that it does not transmit the IDs learned from resolving the collision records in the acknowledgement segment. Instead, it transmits the slot indices of the resolved collision records, which are shorter than the IDs themselves. If a tag receives a slot index that matches a slot in which it has transmitted its ID, it stops participating in FCAT. Certainly, if a tag receives a positive acknowledgement for its ID just transmitted in the report segment, it will also stop participating in FCAT. C. Estimating the Number of Tags within FCAT Finally, we address the problem of how to learn the value of N. There exist efficient methods for estimating the number of tags. However, using them as a pre-step of FCAT incurs con￾siderable overhead. In the following, we embed an estimation method within FCAT. Consider an arbitrary frame with index i. Let n0, n1 and nc be the random variables for the numbers of empty, singleton and collision slots, respectively. We can estimate the statistical relationship between these random variables and the number Ni of tags that are currently participating in the protocol. Based on that relationship, we can estimate Ni from the measured values of n0 and nc. Our approach shares some similarity with [24]. However, in [24], each tag transmits at most once in the frame. In FCAT, each tag participates probabilistically in every slot of the frame. Let Xj be the indicator random variable for the event that the jth slot in the frame is empty, i.e., Xj = 1 means the jth slot is empty and Xj = 0 means it is not empty. Similarly, let Yj be the indicator random variable for the event that the jth slot is a singleton slot. Because each tag decides to transmit with probability pi in every slot in the frame, we have P rob{Xj = 1} = (1 − pi) Ni , ∀j ∈ [1..f]. (6) The expected value of n0 is E(n0) = f j=1 (1 − pi) Ni = f(1 − pi) Ni . (7) The probability for the jth slot in the frame to be a singleton is P rob{Yj = 1} = Ni 1  pi(1 − pi) Ni−1 = Nipi(1 − pi) Ni−1. (8) The expected value of n1 is E(n1) = f i=1 Nipi(1 − pi) Ni−1 = fNipi(1 − pi) Ni−1. (9) Obviously, E(n0) + E(n1) + E(nc) = f. Hence E(nc) = f − E(n0) − E(n1) = f(1 − (1 − pi) Ni − Nipi(1 − pi) Ni−1) = f(1 − (1 − pi) Ni−1(1 − pi + ω)). (10) The above equation can be rewritten as Ni = ln(1 − E(nc) f ) − ln(1 − pi + ω) ln(1 − pi) + 1. (11) At the end of the ith frame, the reader counts the value of nc. Substituting E(nc) by the instance value nc (obtained in the ith frame), the reader obtains an estimation of Ni by the following formula: Nˆi = ln(1 − nc f ) − ln(1 − pi + ω) ln(1 − pi) + 1. (12) Next, we derive E(Nˆi). To simplify the equations, let C1 = 1 ln(1−pi) , C2 = −ln(1−pi+ω) ln(1−pi) +1, and function g(nc) = ln(1− nc f ). We expand the right hand side of (12) by its Taylor series about q = E(nc). Nˆi = C1  g(q)+(nc − q)g (q) + 1 2 (nc − q) 2g(q) + 1 6 (nc − q) 3g(q) + ... + C2. (13) Since q = E(nc), the mean of the second term in (13) is 0. Therefore, we keep the first three terms when computing the approximated value of E(Nˆi). E(Nˆi) C1  g(q) + 1 2 E((nc − q) 2)g(q)  + C2. (14) 552

0.02 0=2.213 simulations that the variance of such an estimator is larger 0.018 0=1.817… As shown in Fig.4,Ni is not a monotonic function with 0.016 0=1.414… respect to the number of singleton slots.Hence,we cannot 0.014 use n to estimate the value of Ni. 0.012 0.01 VI.SIMULATION RESULTS 0.008 In this section,we present simulation results to evaluate the 0.006 performance of our main protocol FCAT.We compare FCAT 00.511.522.533.54 with the existing work,including the Dynamic Framed Slotted number of tags (*10000) ALOHA (DFSA)[6].Enhanced Dynamic Framed Slotted ALOHA (EDFSA)[5],Adaptive Binary Splitting (ABS)[12] Fig.3. The relative bias of with respect to the number of tags. and Adaptive Query Splitting (AQS)[12].The first two are 30 ALOHA-based and the next two are tree-based. We use FCAT-A to denote the FCAT protocol in which k- 25 E(n0) collision slots withk≤入are resolvable,where入=2,3,4. 20 E(n1) E(nC）a The report probability p;is determined based on the formula 15 given in Section IV-C.Specifically,p;is set to be 1.414/Ni. 1.817/N;and 2.213/N;in FCAT-2.FCAT-3 and FCAT-4. respectively.Other values of p;are also investigated in Section VI-C.The frame size f is set to 30 time slots;the performance 0￥ of FCAT under different f values will also be studied.The 00.511.522.533.54 number of tags (*10000) parameters used in other protocols are selected based on their original papers whenever possible. Fig.4.The number of tags.N.is not a monotonic function in E(n). In the simulations,we set the time slot length based on the Parameters:pi 1.414/Ni and f=30. Philips I-Code specification [25].The transmission rate is 53 kbit/sec.Hence,it takes 18.88 us to transmit each bit.We We have E((ne-q)2)=V(ne)by definition and g"(q)= set the ID length to be 96 bits (including the 16 bits CRC i高(m te sp code),which takes 1812 us.The reader's acknowledgement consists of 20 bits,(including the CRC code),which takes we have 378 us.The waiting time before the report segment or the ac- e“-1-d knowledgement segment is 302 us to separate transmissions. E()≈N:- 2fm(1-p)(1+w) (15) Therefore,each slot is about 2.8 ms.The simulation results are the average outcome of 100 runs. Therefore. A.Reading Throughput Comparison Bias( 1+w-e“ (16) 2fNn(1-p)(1+w) We first compare the protocols in terms of the reading throughput,which is the average number of tag IDs that the Fig.3 shows the absolute value of Bias()with respect to RFID reader can collect in each second during the protocol the number of tags N:.The three lines show that the absolute execution time before all IDs are read.Table I shows the values of Bias()are 0.0082,0.011 and 0.014,for w= reading throughputs of the protocols when the number of 1.414,1.817 and 2.213,respectively.They are all very small. tags varies from 1,000 to 20,000.Due to collision resolution, Adding the number of tags whose IDs are already known, FCAT-2 achieves 51.1%~55.6%throughput improvement the reader has an estimation for the total number of tags over DFSA,54.8%~70.6%improvement over EDFSA, in the system,denoted as N.The variance of N*is the 59.6%62.9%improvement over ABS,64.1%~67.7% same as the variance of Ni.i.e.,V(N)=V(Ni).Because improvement over AQS. N:<N.V()<V().The value of V()is derived in As expected,FCAT-3 performs better than FCAT-2,and the appendix.It is approximately 0.0342,0.0287 or 0.0265, FCAT-4 performs better than FCAT-3.However,the improve- for w 1.414,1.817 and 2.213,respectively (i.e.,when ment of FCAT-4 over FCAT-3 is much smaller than that of 2-collision slots,3-collision slots or 4-collision slots are FCAT-3 over FCAT-2.FCAT-5(whose results are not shown in resolvable).This is the variance when only one instance of the table)performs only slightly better FCAT-4.For example, ne is used.It is small though not negligible.The RFID reader when N 10,000,its reading throughput is 270.9 tag IDs obtains one estimation after each frame.If it uses the average per second,which is slightly better than 265.1 of FCAT-4. as the estimation for N.then the variancewill This indicates a quickly shrinking margin of improvement as A increases and suggests that a large value of A is practically decrease in the square root of i and therefore diminish as unnecessary. the protocol executes frame after frame We also evaluate the reading time in terms of time slots. We can also design a similar estimator by using the number Table II shows the numbers of empty,singleton and collision of empty slots,no,based on (7).However,we find in our slots used to read 10,000 tags.We can see that fewer empty 553

0.006 0.008 0.01 0.012 0.014 0.016 0.018 0.02 0 0.5 1 1.5 2 2.5 3 3.5 4 bias number of tags (*10000) ω = 2.213 ω = 1.817 ω = 1.414 Fig. 3. The relative bias of Nˆi with respect to the number of tags. 0 5 10 15 20 25 30 0 0.5 1 1.5 2 2.5 3 3.5 4 number of tags (*10000) E(n0) E(n1) E(nc) Fig. 4. The number of tags, Ni, is not a monotonic function in E(n1). Parameters: pi = 1.414/Ni and f = 30. We have E((nc − q)2) = V (nc) by definition and g(q) = − 1 (q−f)2 since g(q) = ln(1 − q f ). The variance V (nc) is derived in the appendix. Applying (19) from the appendix, we have E(Nˆi) Ni − eω − 1 − ω 2f ln(1 − pi)(1 + ω) . (15) Therefore, Bias( Nˆi Ni ) = E( Nˆi Ni ) − 1 = 1 + ω − eω 2fNi ln(1 − pi)(1 + ω) . (16) Fig. 3 shows the absolute value of Bias( Nˆi Ni ) with respect to the number of tags Ni. The three lines show that the absolute values of Bias( Nˆi Ni ) are 0.0082, 0.011 and 0.014, for ω = 1.414, 1.817 and 2.213, respectively. They are all very small. Adding the number of tags whose IDs are already known, the reader has an estimation for the total number of tags in the system, denoted as Nˆ ∗ i . The variance of Nˆ ∗ i is the same as the variance of Nˆi, i.e., V (Nˆ ∗ i ) = V (Nˆi). Because Ni < N, V ( Nˆ ∗ i N ) < V ( Nˆi Ni ). The value of V ( Nˆi Ni ) is derived in the appendix. It is approximately 0.0342, 0.0287 or 0.0265, for ω = 1.414, 1.817 and 2.213, respectively (i.e., when 2-collision slots, 3-collision slots or 4-collision slots are resolvable). This is the variance when only one instance of nc is used. It is small though not negligible. The RFID reader obtains one estimation after each frame. If it uses the average i j=0 Nˆ ∗ j i as the estimation for N, then the variance will decrease in the square root of i and therefore diminish as the protocol executes frame after frame. We can also design a similar estimator by using the number of empty slots, n0, based on (7). However, we find in our simulations that the variance of such an estimator is larger. As shown in Fig. 4, Ni is not a monotonic function with respect to the number of singleton slots. Hence, we cannot use n1 to estimate the value of Ni. VI. SIMULATION RESULTS In this section, we present simulation results to evaluate the performance of our main protocol FCAT. We compare FCAT with the existing work, including the Dynamic Framed Slotted ALOHA (DFSA) [6], Enhanced Dynamic Framed Slotted ALOHA (EDFSA) [5], Adaptive Binary Splitting (ABS) [12] and Adaptive Query Splitting (AQS) [12]. The first two are ALOHA-based and the next two are tree-based. We use FCAT-λ to denote the FCAT protocol in which k￾collision slots with k ≤ λ are resolvable, where λ = 2, 3, 4. The report probability pi is determined based on the formula given in Section IV-C. Specifically, pi is set to be 1.414/Ni, 1.817/Ni and 2.213/Ni in FCAT-2, FCAT-3 and FCAT-4, respectively. Other values of pi are also investigated in Section VI-C. The frame size f is set to 30 time slots; the performance of FCAT under different f values will also be studied. The parameters used in other protocols are selected based on their original papers whenever possible. In the simulations, we set the time slot length based on the Philips I-Code specification [25]. The transmission rate is 53 kbit/sec. Hence, it takes 18.88 μs to transmit each bit. We set the ID length to be 96 bits (including the 16 bits CRC code), which takes 1812 μs. The reader’s acknowledgement consists of 20 bits, (including the CRC code), which takes 378 μs. The waiting time before the report segment or the ac￾knowledgement segment is 302 μs to separate transmissions. Therefore, each slot is about 2.8 ms. The simulation results are the average outcome of 100 runs. A. Reading Throughput Comparison We first compare the protocols in terms of the reading throughput, which is the average number of tag IDs that the RFID reader can collect in each second during the protocol execution time before all IDs are read. Table I shows the reading throughputs of the protocols when the number of tags varies from 1,000 to 20,000. Due to collision resolution, FCAT-2 achieves 51.1% ∼ 55.6% throughput improvement over DFSA, 54.8% ∼ 70.6% improvement over EDFSA, 59.6% ∼ 62.9% improvement over ABS, 64.1% ∼ 67.7% improvement over AQS. As expected, FCAT-3 performs better than FCAT-2, and FCAT-4 performs better than FCAT-3. However, the improve￾ment of FCAT-4 over FCAT-3 is much smaller than that of FCAT-3 over FCAT-2. FCAT-5 (whose results are not shown in the table) performs only slightly better FCAT-4. For example, when N = 10, 000, its reading throughput is 270.9 tag IDs per second, which is slightly better than 265.1 of FCAT-4. This indicates a quickly shrinking margin of improvement as λ increases and suggests that a large value of λ is practically unnecessary. We also evaluate the reading time in terms of time slots. Table II shows the numbers of empty, singleton and collision slots used to read 10,000 tags. We can see that fewer empty 553

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 554

TABLE 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

450 400 FCAT happens,the reader sends a new query with an indication of the collision.Each colliding tag draws a random binary 350 4A-44444444 300 number (i.e.0 or 1)and adds it to its counter.The set of 250 colliding tags is thus divided into two subsets:one is the set 200 of tags whose counters remain 0 and the other one is the set 150 of tags whose counters increase to 1.When collision happens, 100 all other tags that do not transmit also increase their counters 0 by one;otherwise,they decrease their counters by one.An 20406080100120140160180200 analysis shows that the maximal reading throughput of the frame size f binary-tree protocols is .T [27].The query-tree protocols [12],[13],[14]use the tag ID for splitting.A tag ID is a Fig.6.The reading throughput of FCAT is stabilized when f >10. unique bit string.Each query contains a prefix pi..p where i is the length of the prefix.Each tag,whose ID contains this [9],[10]and the tree-based protocols [12],[13],[14],[15], prefix,transmits its ID as a response.If multiple responses [161. collide,the reader will generate two new prefixes p1.P;0 and P1..P:l by attaching a bit 0 and 1,respectively.The set of In the ALOHA-based protocols,the reader broadcasts a colliding tags is divided into two subsets:one subset is the request and each tag randomly selects a time slot to report its ID.If exact one tag reports,the reader retrieves its tag group of tags whose IDs contain the prefix p..p:0 and the ID and this tag will remain silent for the rest of reading other subset is the group of tags whose IDs contain the prefix P1.P:1.A query-tree protocol can have quite different reading process.Simultaneous reports in a slot will lead to collision. throughputs determined by the tag ID distribution.It is shown Therefore,the ALOHA-based protocols try to maximize the probability that exact one tag reports in a slot.The ALOHA- that the maximal reading throughput is bounded by.ss for a set of uniformly distributed tag IDs [28]. based protocols differ in how the reader sends the request and how the tag selects a slot to report.In the slotted ALOHA [4]. VIII.CONCLUSION the reader sends out a contention probability at the beginning We believe this is the first paper that applies physical- of each slot and each unread tag with this probability to layer network coding to help boost the reading throughput reply with its ID.In the basic framed slotted ALOHA [5], of a large RFID system.We conclude that the physical-layer slots are grouped into frames with the same fixed frame network coding can indeed significantly improve the speed at size.Each unread tag picks up a random slot within each which a RFID reader collects information of the tags.The frame to report.It is possible that the number of tags far reason is that the information carried in many collision slots exceeds the number of slots in a frame so that the frame which was previously discarded,can be utilized almost as is full of collision.To overcome this problem,the dynamic effectively as the information carried in the singleton slots. framed slotted ALOHA (DFSA)[6]introduces frames with The current analog network coding method can improve the dynamic frame size.It is proved that the maximal reading reading throughput of a RFID system by 51.1%70.6%. throughput is achieved when the frame size is equal to the As the technologies of physical-layer network coding are number of unread tags [6].DFSA determines the size of the improved,the reading throughput can potentially be doubled. next frame by estimating the number of unread tags after REFeRENcES each frame.However,in practice,it may be impractical to set the frame size indefinitely high considering there exist [1]S.Katti,S.Gollakota,and D.Katabi,"Embracing Wireless Interference: Analog Network Coding,"In Proc.of ACM SIGCOMM,August 2007 a large number of tags [5].The enhanced dynamic framed [2]R.Das. "Global RFID Market Tops $5.5 Billion, slotted ALOHA [5]uses frames with limited frame size by http://www.comvertingmagazine.com/article/CA6653688.hmml,2009. [3]G.Zecca,P.Couderc.M.Banatre,and R.Beraldi,"Swarm Robot restricting the number of responding tags in a frame.The Synchronization Using RFID Tags,"In Proc.of IEEE PerCom,March maximal reading throughput of the ALOHA-based protocols 2009. is bounded by[11].In other words,for each slot,the [4]I.E.Telatar and R.G.Gallager,"Combining Queuing Theory and Information Theory for Multiaccess."IEEE Journal on Selected Areas probability of successfully reading a new tag is 36.8%. Communication,vol.13.no.6.pp.963-969,August 1995. In the tree-based protocols,the tag reading procedure can [) S.R.Lee,S.D.Joo.and C.W.Lee, “An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification,"/EEE be interpreted as a recursive splitting procedure.The general International Conference on Mobile and Ubiquitous Systems:Networks schema works as follows:In a slot,the reader sends a query and Services (MOBIOUITOUS),July 2005. [6]J.R.Cha and J.H.Kim,"Dynamic Framed Slotted ALOHA Algorithms with a certain condition and each tag that meets the condition Using Fast Tag Estimation Method for RFID Systems,"IEEE Consumer will respond.If a set of tags respond concurrently,the reader Communications and Networking Conference (CCNC),January 2006. split them into smaller subsets.The procedure repeats until [7]H.Vogt,"Efficient Object Identification with Passive RFID Tags,"In Proc.of International Conference on Pervasive Computing,April 2002. every subset only contains a single tag which can be identified [8 V.Sarangan,M.R.Devarapalli,and S.Radhakrishnan."A Framework by the reader.Different splitting criteria lead to different for Fast RFID Tag Reading in Static and Mobile Environments,"The In- ternational Journal of Computer and Telecommunications Networking, protocols.The binary-tree protocols [12],[15],[16]split a set vol.52,no.5,pp.1058-1073,2008. of tags using a random binary number.Specifically,each tag [9]Q.Peng,M.Zhang.and W.Wu,"Variant Enhanced Dynamic Frame has a counter initialized to 0.Upon receiving a query,each Slotted ALOHA Algorithm for Fast Object Identification in RFID System,"IEEE International Workshop on Anti-counterfeiting.Security. tag that has a counter value 0 will respond.Once collision Identification.April 2007. 555

0 50 100 150 200 250 300 350 400 450 20 40 60 80 100 120 140 160 180 200 reading throughput (tags/sec) frame size f FCAT-2 FCAT-3 FCAT-4 Fig. 6. The reading throughput of FCAT is stabilized when f ≥ 10. [9], [10] and the tree-based protocols [12], [13], [14], [15], [16]. In the ALOHA-based protocols, the reader broadcasts a request and each tag randomly selects a time slot to report its ID. If exact one tag reports, the reader retrieves its tag ID and this tag will remain silent for the rest of reading process. Simultaneous reports in a slot will lead to collision. Therefore, the ALOHA-based protocols try to maximize the probability that exact one tag reports in a slot. The ALOHA￾based protocols differ in how the reader sends the request and how the tag selects a slot to report. In the slotted ALOHA [4], the reader sends out a contention probability at the beginning of each slot and each unread tag with this probability to reply with its ID. In the basic framed slotted ALOHA [5], slots are grouped into frames with the same fixed frame size. Each unread tag picks up a random slot within each frame to report. It is possible that the number of tags far exceeds the number of slots in a frame so that the frame is full of collision. To overcome this problem, the dynamic framed slotted ALOHA (DFSA) [6] introduces frames with dynamic frame size. It is proved that the maximal reading throughput is achieved when the frame size is equal to the number of unread tags [6]. DFSA determines the size of the next frame by estimating the number of unread tags after each frame. However, in practice, it may be impractical to set the frame size indefinitely high considering there exist a large number of tags [5]. The enhanced dynamic framed slotted ALOHA [5] uses frames with limited frame size by restricting the number of responding tags in a frame. The maximal reading throughput of the ALOHA-based protocols is bounded by 1 eT [11]. In other words, for each slot, the probability of successfully reading a new tag is 36.8%. In the tree-based protocols, the tag reading procedure can be interpreted as a recursive splitting procedure. The general schema works as follows: In a slot, the reader sends a query with a certain condition and each tag that meets the condition will respond. If a set of tags respond concurrently, the reader split them into smaller subsets. The procedure repeats until every subset only contains a single tag which can be identified by the reader. Different splitting criteria lead to different protocols. The binary-tree protocols [12], [15], [16] split a set of tags using a random binary number. Specifically, each tag has a counter initialized to 0. Upon receiving a query, each tag that has a counter value 0 will respond. Once collision happens, the reader sends a new query with an indication of the collision. Each colliding tag draws a random binary number (i.e. 0 or 1) and adds it to its counter. The set of colliding tags is thus divided into two subsets: one is the set of tags whose counters remain 0 and the other one is the set of tags whose counters increase to 1. When collision happens, all other tags that do not transmit also increase their counters by one; otherwise, they decrease their counters by one. An analysis shows that the maximal reading throughput of the binary-tree protocols is 1 2.88T [27]. The query-tree protocols [12], [13], [14] use the tag ID for splitting. A tag ID is a unique bit string. Each query contains a prefix p1..pi where i is the length of the prefix. Each tag, whose ID contains this prefix, transmits its ID as a response. If multiple responses collide, the reader will generate two new prefixes p1..pi0 and p1..pi1 by attaching a bit 0 and 1, respectively. The set of colliding tags is divided into two subsets: one subset is the group of tags whose IDs contain the prefix p1..pi0 and the other subset is the group of tags whose IDs contain the prefix p1..pi1. A query-tree protocol can have quite different reading throughputs determined by the tag ID distribution. It is shown that the maximal reading throughput is bounded by 1 2.88T for a set of uniformly distributed tag IDs [28]. VIII. CONCLUSION We believe this is the first paper that applies physical￾layer network coding to help boost the reading throughput of a large RFID system. We conclude that the physical-layer network coding can indeed significantly improve the speed at which a RFID reader collects information of the tags. The reason is that the information carried in many collision slots, which was previously discarded, can be utilized almost as effectively as the information carried in the singleton slots. The current analog network coding method can improve the reading throughput of a RFID system by 51.1% ∼ 70.6%. As the technologies of physical-layer network coding are improved, the reading throughput can potentially be doubled. REFERENCES [1] S. Katti, S. Gollakota, and D. Katabi, “Embracing Wireless Interference: Analog Network Coding,” In Proc. of ACM SIGCOMM, August 2007. [2] R. Das, “Global RFID Market Tops $5.5 Billion,” http://www.convertingmagazine.com/article/CA6653688.html, 2009. [3] G. Zecca, P. Couderc, M. Banatre, and R. Beraldi, “Swarm Robot Synchronization Using RFID Tags,” In Proc. of IEEE PerCom, March 2009. [4] I. E. Telatar and R. G. Gallager, “Combining Queuing Theory and Information Theory for Multiaccess,” IEEE Journal on Selected Areas Communication, vol. 13, no. 6, pp. 963–969, August 1995. [5] S. R. Lee, S. D. Joo, and C. W. Lee, “An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification,” IEEE International Conference on Mobile and Ubiquitous Systems: Networks and Services (MOBIQUITOUS), July 2005. [6] J. R. Cha and J. H. Kim, “Dynamic Framed Slotted ALOHA Algorithms Using Fast Tag Estimation Method for RFID Systems,” IEEE Consumer Communications and Networking Conference (CCNC), January 2006. [7] H. Vogt, “Efficient Object Identification with Passive RFID Tags,” In Proc. of International Conference on Pervasive Computing, April 2002. [8] V. Sarangan, M. R. Devarapalli, and S. Radhakrishnan, “A Framework for Fast RFID Tag Reading in Static and Mobile Environments,” The In￾ternational Journal of Computer and Telecommunications Networking, vol. 52, no. 5, pp. 1058–1073, 2008. [9] Q. Peng, M. Zhang, and W. Wu, “Variant Enhanced Dynamic Frame Slotted ALOHA Algorithm for Fast Object Identification in RFID System,” IEEE International Workshop on Anti-counterfeiting, Security, Identification, April 2007. 555

[10]B.Zhen,M.Kobayashi,and M.Shimizu,"Framed ALOHA for Multiple random variable.Hence,we have RFID Object Identification,"IEICE Transactions on Communications March 2005. V(Z)=E(Z)-(E(Z1)2 [11]L.G.Roberts,"ALOHA Packet System with and without Slots and Capture,"ACM SIGCOMM Computer Communication Review,vol.5, =(1+NP)e-N(1-(1+Np)e-NP).(I8) n0.2,pp.2842,Apri1975. [12]J.Myung and W.Lee."Adaptive Splitting Protocols for RFID Tag Therefore, Collision Arbitration."In Proc.of ACM MobiHoc.May 2006. [13]N.Bhandari,A.Sahoo,and S.Iyer, ."Intelligent Query Tree (IQT) V(ne)=f(1+Np)e-Np(1-(1+Np)e-Np).(19) Protocol to Improve RFID Tag Read Efficiency,"IEEE International Conference on Information Technology (ICIT),December 2006. According to the central limit theorem,if f is large,ne [14]F.Zhou.C.Chen,D.Jin,C.Huang,and H.Min,"Evaluating and Opti- is approximately normally distributed.When foo,ne mizing Power Consumption of Anti-collision Protocols for Applications in RFID Systems,"In Proc.of ACM Interational Symposium on Low converges to the normal distribution, Power Electronics and Design (ISLPED),August 2004. [15]"Information technology automatic identification and data capture tech- ne B Norm(0,82) niques C radio frequency identification for item management air inter- face-part 6:parameters for air interface communications at 860-960 where 6 is E(ne)as given in (10).62 is V(ne)as given in MHz."Final Draft International Standard ISO 18000-6.November 2003. (19),andB means convergence in distribution. [16]S.A.Weis,S.E.Sarma.R.L.Rivest,and D.W.Engels, "Security and Privacy Aspects of Low-cost Radio Frequency Identification Sys- According to the 6-method [291,we have tems,"In Proc.of International Conference on Security in Pervasive Computing (SPC).March 2003. h(ne)B Norm(h(0),62 [h'(0)2) (20) [17]S.Zhang.S.Liew,and P.P.Lam,"Physical Layer Network Coding." In Proc.of ACM MobiCom.September 2006. for any function h(.)such that h'()exists and takes a non- [18]D.Shih,P.L.Sun,D.C.Yen,and S.M.Huang."Taxonomy and Survey zero value. of RFID Anti-collision Protocols,"Computer and Communications,vol. In Section V-C,the estimation formula is designed based 29no.11,pp.2150-2166.2006 [19]M.C.Azambuja,C.A.M.Marcon,and F.P.Hessel,"Survey on (10).which is copied below. of Standardized ISO 18000-6 RFID Anti-collision Protocols,"In Proc.of IEEE International Conference on Sensor Technologies and E(ne)=f(1-(1-p)Ns-Np(1-p)Na-1). Applications (SENSORCOMM),August 2008. 20]S.Pasupathy."Minimum Shift Keying:A Spectrally Efficient Modula- Let g(.)be the mapping function from N;to ne.The above tion."IEEE Communications Magazine,1979. equation can be rewritten as E(ne)=g(Ni).Fig.4 shows [21]J.Hamkins, "An Analytic Technique to Separate Cochannel FM Signals,"IEEE Transactions on Communications,vol.48,no.4,pp. that g(.)is a monotonic function,and hence it has a unique 543-546.Apri12000. inverse function,denoted as h(.). [22]E.Casini,R.D.Gaudenzi.and O.R.Herrero,"Contention Resolution According to Section V-C,Ni is computed from (10)by Diversity Slotted ALOHA (CRDSA):An Enhanced Random Access Schemefor Satellite Access Packet Networks,"IEEE Transactions on substituting E(ne)with the instance value of ne (obtained Wireless Communications.vol.6.no.4.pp.1408-1419.April 2007. after the ith frame). [23]S.Gollakota and D.Katabi (MIT),"ZigZag Decoding:Combating Hidden Temminals in Wireless Networks,"In Proc.of ACM SIGCOMM ne=f1-(1-ps)-Np(1-p)N-1) August 2008. [24]M.Kodialam and T.Nandagopal, "Fast and Rellable Estimation ≈f(1-e-N:p-Npe-Np). (21) Schemes in RFID Systems:"In Proc.of ACM MobiCom.September 2006. Clearly,ne =g(Ni)and Ni h(ne).Applying Ni= [25]Philips Semiconductors. "I-CODE Smart Label RFID Tags," h(nc)to (20),we have http://www.nxp.com/acrobat_download/other/identification/SL092030.pdf January 2004. :马Norm(h(0),d2(ej2). (22) [26]K.Finkenzeller,"RFID Handbook:Fundamentals and Applications in Contactless Smart Cards and Identification,"John Wiley Sons,2003 We know that h(g(N:))=N:.Differentiating both sides, [27]J.I.Capetenakis,"Tree Algorithms for Packet Broadcast Channels," IEEE Transactions on Information Theory,vol.25,no.5,pp.505-515 we have h'(g(Ni))g'(Ni)=1.Hence. 1979. 1 [28]C.Law,K.Lee,and K.Y.Siu,"Efficient Memoryless Protocol for Tag Identification,"In Prof.of International Workshop on Discrete kO)=N(Ene》=hgN》=g (23) Algaorithms and Methods for Mobile Computing and Communications Pp.75-84,August2000. Therefore,from(22),the variance of Ni is [29]G.Casella and R.L.Berger,"Statistical Inference,"2nd edition. Duxbury Press.2002. V(N)=62[h'(0)12= V(ne) g'(Na)2 APPENDIX.ESTIMATION VARIANCE,V() =+Npe-1+2Np+N32 (24) Consider an arbitrary frame with index i.Let Z;be the fN2P indicator random variable for the event that the jth slot in the frame is a collision slot.Since no slot is special,Zj,Vj E V(N (1+Np)ep-(1+2Np:+Np) (25) [1..f],follows the same distribution.They are independent fNap random variables.Because ne=we have Below we perform approximate computation to give a rough idea on how big this variance is.In SCAT or FCAT,Nip;=w, V(ne)=>v(Zj)=fV(Z1). where w is 1.414,1.817 or 2.213 for A 2,3 or 4. (17) respectively.Our simulations show that Ni reliably converges j=1 to Ni when i is large.Hence,we substitute Nip;with w in E(Zi)=1-(1-P)N-NP,(1-p)-1≈1-e-Np- (25),and the variance V()is 0.0342,0.0287 or 0.0265 Nipie-NP.E(Z)=E(Z1)because Z1 is an indicator respectively for different w values. 556

[10] B. Zhen, M. Kobayashi, and M. Shimizu, “Framed ALOHA for Multiple RFID Object Identification,” IEICE Transactions on Communications, March 2005. [11] L. G. Roberts, “ALOHA Packet System with and without Slots and Capture,” ACM SIGCOMM Computer Communication Review, vol. 5, no. 2, pp. 28–42, April 1975. [12] J. Myung and W. Lee, “Adaptive Splitting Protocols for RFID Tag Collision Arbitration,” In Proc. of ACM MobiHoc, May 2006. [13] N. Bhandari, A. Sahoo, and S. Iyer, “Intelligent Query Tree (IQT) Protocol to Improve RFID Tag Read Efficiency,” IEEE International Conference on Information Technology (ICIT), December 2006. [14] F. Zhou, C. Chen, D. Jin, C. Huang, and H. Min, “Evaluating and Opti￾mizing Power Consumption of Anti-collision Protocols for Applications in RFID Systems,” In Proc. of ACM International Symposium on Low Power Electronics and Design (ISLPED), August 2004. [15] “Information technology automatic identification and data capture tech￾niques C radio frequency identification for item management air inter￾face - part 6: parameters for air interface communications at 860-960 MHz,” Final Draft International Standard ISO 18000-6, November 2003. [16] S. A. Weis, S. E. Sarma, R. L. Rivest, and D. W. Engels, “Security and Privacy Aspects of Low-cost Radio Frequency Identification Sys￾tems,” In Proc. of International Conference on Security in Pervasive Computing (SPC), March 2003. [17] S. Zhang, S. Liew, and P. P. Lam, “Physical Layer Network Coding,” In Proc. of ACM MobiCom, September 2006. [18] D. Shih, P. L. Sun, D. C. Yen, and S. M. Huang, “Taxonomy and Survey of RFID Anti-collision Protocols,” Computer and Communications, vol. 29, no. 11, pp. 2150–2166, 2006. [19] M. C. Azambuja, C. A. M. Marcon, and F. P. Hessel, “Survey of Standardized ISO 18000-6 RFID Anti-collision Protocols,” In Proc. of IEEE International Conference on Sensor Technologies and Applications (SENSORCOMM), August 2008. [20] S. Pasupathy, “Minimum Shift Keying: A Spectrally Efficient Modula￾tion,” IEEE Communications Magazine, 1979. [21] J. Hamkins, “An Analytic Technique to Separate Cochannel FM Signals,” IEEE Transactions on Communications, vol. 48, no. 4, pp. 543–546, April 2000. [22] E. Casini, R. D. Gaudenzi, and O. R. Herrero, “Contention Resolution Diversity Slotted ALOHA (CRDSA): An Enhanced Random Access Schemefor Satellite Access Packet Networks,” IEEE Transactions on Wireless Communications, vol. 6, no. 4, pp. 1408–1419, April 2007. [23] S. Gollakota and D. Katabi (MIT), “ZigZag Decoding: Combating Hidden Terminals in Wireless Networks,” In Proc. of ACM SIGCOMM, August 2008. [24] M. Kodialam and T. Nandagopal, “Fast and Reliable Estimation Schemes in RFID Systems,” In Proc. of ACM MobiCom, September 2006. [25] Philips Semiconductors, “I-CODE Smart Label RFID Tags,” http://www.nxp.com/acrobat download/other/identification/SL092030.pdf, January 2004. [26] K. Finkenzeller, “RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification,” John Wiley & Sons, 2003. [27] J. I. Capetenakis, “Tree Algorithms for Packet Broadcast Channels,” IEEE Transactions on Information Theory, vol. 25, no. 5, pp. 505–515, 1979. [28] C. Law, K. Lee, and K. Y. Siu, “Efficient Memoryless Protocol for Tag Identification,” In Prof. of International Workshop on Discrete Algaorithms and Methods for Mobile Computing and Communications, pp. 75–84, August 2000. [29] G. Casella and R. L. Berger, “Statistical Inference,” 2nd edition, Duxbury Press, 2002. APPENDIX. ESTIMATION VARIANCE, V ( Nˆi Ni ) Consider an arbitrary frame with index i. Let Zj be the indicator random variable for the event that the jth slot in the frame is a collision slot. Since no slot is special, Zj , ∀j ∈ [1..f], follows the same distribution. They are independent random variables. Because nc = f j=1 Zj, we have V (nc) = f j=1 V (Zj ) = fV (Z1). (17) E(Z1)=1 − (1 − pi)Ni − Nipi(1 − pi)Ni−1 ≈ 1 − e−Nipi − Nipi · e−Nipi . E(Z2 1 ) = E(Z1) because Z1 is an indicator random variable. Hence, we have V (Z1) = E(Z2 1 ) − (E(Z1))2 = (1 + Nipi)e−Nipi (1 − (1 + Nipi)e−Nipi ). (18) Therefore, V (nc) = f(1 + Nipi)e−Nipi (1 − (1 + Nipi)e−Nipi ). (19) According to the central limit theorem, if f is large, nc is approximately normally distributed. When f → ∞, nc converges to the normal distribution, nc D → Norm(θ, δ2) where θ is E(nc) as given in (10), δ2 is V (nc) as given in (19), and D → means convergence in distribution. According to the δ-method [29], we have h(nc) D → Norm(h(θ), δ2 [h (θ)]2 ) (20) for any function h(.) such that h (θ) exists and takes a non￾zero value. In Section V-C, the estimation formula is designed based on (10), which is copied below. E(nc) = f(1 − (1 − pi) Ni − Nipi(1 − pi) Ni−1). Let g(.) be the mapping function from Ni to nc. The above equation can be rewritten as E(nc) = g(Ni). Fig. 4 shows that g(.) is a monotonic function, and hence it has a unique inverse function, denoted as h(.). According to Section V-C, Nˆi is computed from (10) by substituting E(nc) with the instance value of nc (obtained after the ith frame). nc = f(1 − (1 − pi) Nˆi − Nˆipi(1 − pi) Nˆi−1) ≈ f(1 − e−Nˆipi − Nˆipie−Nˆipi ). (21) Clearly, nc = g(Nˆi) and Nˆi = h(nc). Applying Nˆi = h(nc) to (20), we have Nˆi D → Norm(h(θ), δ2 [h (θ)]2 ). (22) We know that h(g(Ni)) = Ni. Differentiating both sides, we have h (g(Ni))g (Ni)=1. Hence, h (θ) = h (E(nc)) = h (g(Ni)) = 1 g (Ni) . (23) Therefore, from (22), the variance of Nˆi is V (Nˆi) = δ2 [h (θ)]2 = V (nc) [g (Ni)]2 = (1 + Nipi)eNipi − (1 + 2Nipi + N2 i p2 i ) fN2 i p4 i , (24) V ( Nˆi Ni ) = (1 + Nipi)eNipi − (1 + 2Nipi + N2 i p2 i ) fN4 i p4 i . (25) Below we perform approximate computation to give a rough idea on how big this variance is. In SCAT or FCAT, Nˆipi = ω, where ω is 1.414, 1.817 or 2.213 for λ = 2, 3 or 4, respectively. Our simulations show that Nˆi reliably converges to Ni when i is large. Hence, we substitute Nipi with ω in (25), and the variance V ( Nˆi Ni ) is 0.0342, 0.0287 or 0.0265 respectively for different ω values. 556