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.48Using 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