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. 5550 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