combat RFID signal collisions,especially the reader collision. Different from existing approaches,our scheduling protocol, They usually adopt an exclusive scheduling strategy to avoid named Season-II,just selects only one reader from neighboring reader collision [12]-[15].Namely,neighboring readers that readers to perform the interrogation and let the others passively share some contentious regions must be activated in sequence. collect data from contentious tags.Thus,neighboring readers For instance,Colorwave [13],one of the most popular anti- are able to collaborate with each other in the identification of reader-collision protocols,pre-schedules neighboring readers contentious tags,and save vast time consumed in scheduling. to work in different time slots.Those approaches may suffer Adopting joint identification,we find that the collaborative from two drawbacks,low throughput and large identification readers may face an emerging collision,termed as cross- delay.According to the well-known RFID standard ISO- range collision.We develop another anti-tag-collision protocol, 18000 [10].the average identification throughput of Framed Season-III,to combat the cross-range collision and achieve fast Slotted ALOHA protocols only archive 100 tags per second identification [11].The exclusive scheduling among readers will further The rest of this paper is organized as follows.We introduce degrade the throughput.For example,one of experiments preliminary knowledge about RFID systems and the system performed in a warehouse scenario indicates that the reader's model in Section II.We present the design of Season in Section throughput degrades to 52 tags per second on average due to III.In Section IV,we examine the performance of Season via the interferences among four neighboring readers,as shown preliminary implementation and extensive simulation based on in Section IV.As a result.it will spend almost half an hour real traces from a large-scale logistics system.At last,we to inventory 78,606 products.On the other hand,the identi- review related works in Section V and conclude this paper fication delay of tags is an import metric in real-time RFID in Section VI. applications,such as the theft detection 3,object tracking 4], etc.Our experimental results show that Colorwave requires six II.PRELIMINARIES exclusive rounds at least to schedule six mutually-interfered In this section,we first briefly review the three types of readers when identifying 1000 tags for each.In this case,the collisions in RFID systems mentioned in the previous section, maximum delay introduced to each tag is up to 63 seconds. and then introduce our system model. That means the moving speed of tags must be slower than 10cm per second in the readers'monitoring region where A.Tag Collision the range of the reader equals 3m.Such a speed cannot The most common collision in RFID systems is tag col- well support fast identification in real-time RFID applications lision,and it occurs when multiple tags in the interrogation which have a rigid time limit on the processing speed. region of a reader and transmit their IDs at the same time, By reconsidering the solution of reader-collision in another as shown in Fig.I(a).A popular anti-tag-collision algorithm perspective,we find that it is not necessary to constrain is Framed Slotted ALOHA (FSA)[9],[10],[26]-[28].The neighboring readers in a strictly sequential processing pattern design of our protocols is partially based on FSA.In FSA, for the purpose of anti-collision.Usually,the majority of tags the reader first divides a detecting procedure into several are non-contentious in common RFID applications.They can frames.Each frame contains f slots with equal length.At be concurrently identified by multiple readers because there is the beginning of one frame,the reader broadcasts the f to no reader collision in those tags.Hence,we propose to identify all tags and each tag randomly chooses a slot counter from tags in two phases.In the first phase,we simply allow multiple 0 to f-1.The reader then sequentially scans slots in the readers to identify the non-contentious tags simultaneously,frame with the 'query'command.In each slot,if a tag's slot while shelving the reader collisions.In this way,the identifi- counter equals zero,it will backscatter its ID immediately. cation throughput of non-contentious tags will be significantly Otherwise,the tag decreases its slot counter by one.From improved.In the second phase,we design efficient protocols the reader's perspective,there are three types of slots,'idle', to identify the contentious tags.We find that a reader,if it just 'single',and 'collided'slots.In idle slots,no tag responds, passively monitors,can facilitate the identification responses the reader continues to scan the next slot.In single slots,only from contentious tags that are interrogated by another reader. one tag replies,the reader can successfully receive the tag's This observation motivates us to enable collaboration among ID.The reader then sends an acknowledgement of success neighboring readers to enormously reduce the identification 'ACKS'to notify the tag to keep silent in the left identification delays of contentious tags. procedure.In collided slots,more than one tag responds such In this paper,we propose a novel scheme,Season,to that the reader cannot identify any tag.The reader then sends improve the efficiency for anti-collision based RFID identi- an acknowledgement of failure 'ACKF'to indicate these tags fication.The Season protocol works in two phases.In the to reply in the next frame.If there is any collided slot in the first phase,we propose the Season-I protocol in which all current frame,the reader renews a new frame until all tags are readers ignore the reader collisions and concurrently identify identified. non-contentious tags.Season-I extends the existing anti-tag- collision algorithms by adaptively tuning the size of frame B.Reader Collision to improve the throughput of identification.In the second This collision occurs at these tags located within the con- phase,neighboring readers jointly identify contentious tags. tentious regions covered by multiple readers.Engels [12]et al.combat RFID signal collisions, especially the reader collision. They usually adopt an exclusive scheduling strategy to avoid reader collision [12]–[15]. Namely, neighboring readers that share some contentious regions must be activated in sequence. For instance, Colorwave [13], one of the most popular anti￾reader-collision protocols, pre-schedules neighboring readers to work in different time slots. Those approaches may suffer from two drawbacks, low throughput and large identification delay. According to the well-known RFID standard ISO- 18000 [10], the average identification throughput of Framed Slotted ALOHA protocols only archive 100 tags per second [11]. The exclusive scheduling among readers will further degrade the throughput. For example, one of experiments performed in a warehouse scenario indicates that the reader’s throughput degrades to 52 tags per second on average due to the interferences among four neighboring readers, as shown in Section IV. As a result, it will spend almost half an hour to inventory 78,606 products. On the other hand, the identi- fication delay of tags is an import metric in real-time RFID applications, such as the theft detection [3], object tracking [4], etc. Our experimental results show that Colorwave requires six exclusive rounds at least to schedule six mutually-interfered readers when identifying 1000 tags for each. In this case, the maximum delay introduced to each tag is up to 63 seconds. That means the moving speed of tags must be slower than 10cm per second in the readers’ monitoring region where the range of the reader equals 3m. Such a speed cannot well support fast identification in real-time RFID applications which have a rigid time limit on the processing speed. By reconsidering the solution of reader-collision in another perspective, we find that it is not necessary to constrain neighboring readers in a strictly sequential processing pattern for the purpose of anti-collision. Usually, the majority of tags are non-contentious in common RFID applications. They can be concurrently identified by multiple readers because there is no reader collision in those tags. Hence, we propose to identify tags in two phases. In the first phase, we simply allow multiple readers to identify the non-contentious tags simultaneously, while shelving the reader collisions. In this way, the identifi- cation throughput of non-contentious tags will be significantly improved. In the second phase, we design efficient protocols to identify the contentious tags. We find that a reader, if it just passively monitors, can facilitate the identification responses from contentious tags that are interrogated by another reader. This observation motivates us to enable collaboration among neighboring readers to enormously reduce the identification delays of contentious tags. In this paper, we propose a novel scheme, Season, to improve the efficiency for anti-collision based RFID identi- fication. The Season protocol works in two phases. In the first phase, we propose the Season-I protocol in which all readers ignore the reader collisions and concurrently identify non-contentious tags. Season-I extends the existing anti-tag￾collision algorithms by adaptively tuning the size of frame to improve the throughput of identification. In the second phase, neighboring readers jointly identify contentious tags. Different from existing approaches, our scheduling protocol, named Season-II, just selects only one reader from neighboring readers to perform the interrogation and let the others passively collect data from contentious tags. Thus, neighboring readers are able to collaborate with each other in the identification of contentious tags, and save vast time consumed in scheduling. Adopting joint identification, we find that the collaborative readers may face an emerging collision, termed as cross￾range collision. We develop another anti-tag-collision protocol, Season-III, to combat the cross-range collision and achieve fast identification. The rest of this paper is organized as follows. We introduce preliminary knowledge about RFID systems and the system model in Section II. We present the design of Season in Section III. In Section IV, we examine the performance of Season via preliminary implementation and extensive simulation based on real traces from a large-scale logistics system. At last, we review related works in Section V and conclude this paper in Section VI. II. PRELIMINARIES In this section, we first briefly review the three types of collisions in RFID systems mentioned in the previous section, and then introduce our system model. A. Tag Collision The most common collision in RFID systems is tag col￾lision, and it occurs when multiple tags in the interrogation region of a reader and transmit their IDs at the same time, as shown in Fig. I(a). A popular anti-tag-collision algorithm is Framed Slotted ALOHA (FSA) [9], [10], [26]–[28]. The design of our protocols is partially based on FSA. In FSA, the reader first divides a detecting procedure into several frames. Each frame contains f slots with equal length. At the beginning of one frame, the reader broadcasts the f to all tags and each tag randomly chooses a slot counter from 0 to f − 1. The reader then sequentially scans slots in the frame with the ‘query’ command. In each slot, if a tag’s slot counter equals zero, it will backscatter its ID immediately. Otherwise, the tag decreases its slot counter by one. From the reader’s perspective, there are three types of slots, ‘idle’, ‘single’, and ‘collided’ slots. In idle slots, no tag responds, the reader continues to scan the next slot. In single slots, only one tag replies, the reader can successfully receive the tag’s ID. The reader then sends an acknowledgement of success ‘ACKS’ to notify the tag to keep silent in the left identification procedure. In collided slots, more than one tag responds such that the reader cannot identify any tag. The reader then sends an acknowledgement of failure ‘ACKF’ to indicate these tags to reply in the next frame. If there is any collided slot in the current frame, the reader renews a new frame until all tags are identified. B. Reader Collision This collision occurs at these tags located within the con￾tentious regions covered by multiple readers. Engels [12] et al