Season:Shelving Interference and Joint Identification in Large-scale RFID Systems Lei Yang*,Jinsong Han*,Yong Qi*,Cheng Wangs,Tao Gu,Yunhao Liut Department of Computer Science and Technology,Xi'an Jiaotong University,China f TNLIST,School of Software,Tsinghua University,China Department of Computer Science and Engineering,HKUST,Hong Kong 3 Tongji University University of Southern Denmark Abstract-Prior work on anti-collision for Radio Frequency IDentification (RFID)systems usually schedule adjacent readers to exclusively interrogate tags for avoiding reader collisions. Although such a pattern can effectively deal with collisions, the lack of readers'collaboration wastes numerous time on the scheduling process and dramatically degrades the throughput of identification.Even worse,the tags within the overlapped (a) b】 (c) interrogation regions of adjacent readers (termed as contentious tags),even if the number of such tags is very small,introduce Fig.1. Collisions in RFID systems.(a)Tag collision:(b)Reader collision; a significant delay to the identification process.In this paper, (c)Reader-Tag collision we propose a new strategy for collision resolution.First,we shelve the collisions and identify the tags that do not involve reader collisions.Second,we perform a joint identification,in this situation,the signals coming from multiple tags may inter- which adjacent readers collaboratively identify the contentious fere with each other and prevent the reader from resolving any tags.In particular,we find that neighboring readers can cause tag's ID.We call the first collision as"tag collision",as shown a new type of collisions,cross-tag-collision,which may impede the joint identification.We propose a protocol stack,named in Fig.I(a).The second type of collision occurs in a multi- Season,to undertake the tasks in two phases and solve the cross- reader environment,as illustrated in Fig.I(b).In this example, tag-collision.We conduct extensive simulations and preliminary reader r and r2 share an overlapped interrogation region (In implementation to demonstrate the efficiency of our scheme. this paper,we define such a region as 'contentious region', The results show that our scheme can achieve above 6 times the tags within contentious regions as 'contentious tags',and improvement on the identification throughput in a large-scale dense reader environment. other tags as 'non-contentious tags').If there are some tags in Index Terms-RFID,Tag Collision,Reader Collision,Season this region,they cannot resolve the commands from r or r2 when two readers concurrently broadcast their commands.We I.INTRODUCTION call this type of collisions as 'reader collision'.The third type of collision is termed as reader-tag collision,which occurs Radio Frequency Identification systems have been deployed when one reader is in another reader's interrogation region.as in a variety of application domains,such as logistic and supply shown in Figure I(c),reader r is located in r2's interrogation chain management [1],access control [2],theft detection [3]. region.Tag ti's response will be 'drowned'by the commands and tracking [4]-[8],etc.An RFID system typically consists from reader r2,and resulting ri is unable to receive tI's ID. of a large number of readers and tags.RFID tags are attached Clearly,avoiding collisions is a crucial task in RFID to products and targeted to enable the identification of those systems,especially when readers are densely deployed.The objects.Tags usually have no energy and can only be activated algorithms to resolve the aforementioned collisions are known when they are within the electromagnetic field of a reader. as anti-tag-collision,anti-reader-collision,and anti-reader-tag The reader interrogates the tags and collects their IDs via collision algorithm,respectively.As a cost-effective and RF signals,without the need of keeping in sight or touch. source-limited device,the RFID tag cannot afford the relative- In contrast to the conventional barcode system,RFID systems ly complicated anti-collision algorithms adopted in traditional have many advantages,such as non-optical proximity,long wireless networks.such as CSMA.CDMA.FDMA,etc. transmission range,and quick identification.Therefore,the Existing RFID anti-collision algorithms mainly employ Time promising RFID technology is expected to be widely used Dividing Multiple Accesses (TDMA),which allows tags and in the near feature. readers to send signals in different time slots.For example The signal collision is one of the most challenging issues Framed Slotted ALOHA (FSA)[9],[10],[26]-[28],which is when implementing the RFID technology.There are three a dominant anti-tag-collision protocol,requires tags to respond types of RFID signal collisions.The first type of collision in randomly chosen time slot. occurs when more than one tag responds simultaneously.In Unfortunately,existing anti-collision works are inefficient toSeason: Shelving Interference and Joint Identification in Large-scale RFID Systems Lei Yang∗ , Jinsong Han∗ , Yong Qi∗ , Cheng Wang§ , Tao Gu¶ , Yunhao Liu†‡ ∗ Department of Computer Science and Technology, Xi’an Jiaotong University, China † TNLIST, School of Software, Tsinghua University, China ‡ Department of Computer Science and Engineering, HKUST, Hong Kong § Tongji University ¶ University of Southern Denmark Abstract—Prior work on anti-collision for Radio Frequency IDentification (RFID) systems usually schedule adjacent readers to exclusively interrogate tags for avoiding reader collisions. Although such a pattern can effectively deal with collisions, the lack of readers’ collaboration wastes numerous time on the scheduling process and dramatically degrades the throughput of identification. Even worse, the tags within the overlapped interrogation regions of adjacent readers (termed as contentious tags), even if the number of such tags is very small, introduce a significant delay to the identification process. In this paper, we propose a new strategy for collision resolution. First, we shelve the collisions and identify the tags that do not involve reader collisions. Second, we perform a joint identification, in which adjacent readers collaboratively identify the contentious tags. In particular, we find that neighboring readers can cause a new type of collisions, cross-tag-collision, which may impede the joint identification. We propose a protocol stack, named Season, to undertake the tasks in two phases and solve the cross￾tag-collision. We conduct extensive simulations and preliminary implementation to demonstrate the efficiency of our scheme. The results show that our scheme can achieve above 6 times improvement on the identification throughput in a large-scale dense reader environment. Index Terms—RFID, Tag Collision, Reader Collision, Season I. INTRODUCTION Radio Frequency Identification systems have been deployed in a variety of application domains, such as logistic and supply chain management [1], access control [2], theft detection [3], and tracking [4]–[8], etc. An RFID system typically consists of a large number of readers and tags. RFID tags are attached to products and targeted to enable the identification of those objects. Tags usually have no energy and can only be activated when they are within the electromagnetic field of a reader. The reader interrogates the tags and collects their IDs via RF signals, without the need of keeping in sight or touch. In contrast to the conventional barcode system, RFID systems have many advantages, such as non-optical proximity, long transmission range, and quick identification. Therefore, the promising RFID technology is expected to be widely used in the near feature. The signal collision is one of the most challenging issues when implementing the RFID technology. There are three types of RFID signal collisions. The first type of collision occurs when more than one tag responds simultaneously. In t2 t3 t1 r1 r1 r2 t1 r1 r2 t1 (a) (b) (c) Fig. 1. Collisions in RFID systems. (a) Tag collision; (b) Reader collision; (c) Reader-Tag collision. this situation, the signals coming from multiple tags may inter￾fere with each other and prevent the reader from resolving any tag’s ID. We call the first collision as “tag collision”, as shown in Fig. I(a). The second type of collision occurs in a multi￾reader environment, as illustrated in Fig. I(b). In this example, reader r1 and r2 share an overlapped interrogation region (In this paper, we define such a region as ‘contentious region’, the tags within contentious regions as ‘contentious tags’, and other tags as ‘non-contentious tags’). If there are some tags in this region, they cannot resolve the commands from r1 or r2 when two readers concurrently broadcast their commands. We call this type of collisions as ‘reader collision’. The third type of collision is termed as reader-tag collision, which occurs when one reader is in another reader’s interrogation region, as shown in Figure I(c), reader r1 is located in r2’s interrogation region. Tag t1’s response will be ‘drowned’ by the commands from reader r2, and resulting r1 is unable to receive t1’s ID. Clearly, avoiding collisions is a crucial task in RFID systems, especially when readers are densely deployed. The algorithms to resolve the aforementioned collisions are known as anti-tag-collision, anti-reader-collision, and anti-reader-tag collision algorithm, respectively. As a cost-effective and source-limited device, the RFID tag cannot afford the relative￾ly complicated anti-collision algorithms adopted in traditional wireless networks, such as CSMA, CDMA, FDMA, etc. Existing RFID anti-collision algorithms mainly employ Time Dividing Multiple Accesses (TDMA), which allows tags and readers to send signals in different time slots. For example, Framed Slotted ALOHA (FSA) [9], [10], [26]–[28] , which is a dominant anti-tag-collision protocol, requires tags to respond in randomly chosen time slot. Unfortunately, existing anti-collision works are inefficient to