find that when two readers attempt to communicate with those overlapped regions between ri and its neighboring readers. tags at the same time,the signals cannot be correctly resolved On the contrary,the tags in T=Ur,er()(Ti\T;),where and considered as environment noises by the tags.Meanwhile. Ti Ti={tt E Ti&t g Til,are non-contentious tags of each reader is unaware of the existence of interference from reader ri.They are only covered by reader ri. other readers.Therefore,those tags fail to be identified by any We use undirect graph G =(R,E)to denote RCG. reader.To resolve the signal interference,existing approaches Reader ri and rj.where ri,rj E R,are adjacent in G if convert the potential reader collision to an undirected graph, their corresponding nodes are connected by an edge,i.e., named as Reader Conflict Graph (RCG).In RCG,a node (ri,rj)EE.The degree d(ri)of reader ri is the number represents an individual RFID reader and an edge represents a of edges connected to ri in RCG.The maximum degree of collision constraint:if two nodes are connected with an edge graph G is defined as A(G)=maxrerd(r).We assume the in RCG,the related readers will collide if they transmit the readers can be well synchronized through a global clock and command at the same time. some synchronization protocols [16]. Note that the edge does not represent the communication between readers but only the potential reader collision.Indeed. III.SEASON all readers in the network are often linked through LAN.The In this section,we first present three important observations existing approaches,e.g.,Colorwave [13],utilize the graph that motivate our design.We then present the design of Season coloring algorithm to solve reader collisions.Those solutions and describe the three protocols we propose. thereby are similar to finding the smallest number of total colors for coloring the RCG such that any two adjacent vertices A.Observations are in different colors.Indeed,a color is corresponding to We observe three intuitive but important facts in practice: a periodic reservation for collision-free transmissions.The Observation 1:Majority of tags are non-contentious due signal interference can be addressed by well arranging neigh- to the well advanced deployment of readers.If we allow boring readers to send commands exclusively.However,as the readers concurrently interrogate non-contentious tags,we we discussed before,the exclusive scheduling incurs a poor can improve the identification throughput.Hence,a key throughput of identification. step of improving the identification throughput is to enable the concurrency for neighboring readers in identifying non- C.Reader-Tag Collision contentious tags.This observation motivates us to handle the To resolve reader-tag collision,EPCglobal Gen II stan- non-contentious and contentious tags separately. dards [9]specify two separated frequencies for the reader's Observation 2:The minor contentious tags indeed cause query and tag's response,respectively,if readers are densely the major delay during the identification.Sometimes,only one deployed.In fact,we can boil down reader-tag collisions contentious tag may incur large delay.As shown in Fig.2(a), to reader collisions as long as we synchronize all readers' there is one contentious tag in the contentious region between behaviors.For example,if we schedule (r1,r2 )in sequence, ri and r2,while no tag is in the contentious region between we can only consider the other two types of collisions. rI and ra.However,both reader ri and r3 are not aware of this situation since they have no knowledge about the locations D.System Model of tags.These two readers have to be activated exclusively if In our model,we use slotted channel as the communication utilizing prior works [12]-[14].Therefore,we seek to design model between readers and tags.The transmissions happen new identification pattern for contentious tags. within predefined and equally spaced intervals,termed as slots. Observation 3:The signals from the contentious tags can The reader guarantees the slot synchronization via energizing be received by the readers that cover these tags.For instance, probe/request.Obviously,the time required to identify tags is the responding signal generated by the contentious tag t will proportional to the number of tags.All readers are connected be received by two neighboring reader ri and r2,as shown by wired or wireless networks which enable them to commu- in Fig.2(b).If we can deliberately arrange one reader to nication with each other at high speed. interrogate the contentious tags while its neighboring readers Consider a set of readers R={r1,...,rm}are deployed passively listen to the responses from these tags,the system is at a region.An identification procedure is the procedure to able to retrieve the data from the contentious tag even there is identify all the tags within the region at a time.In this paper, a potential reader collisions in RCG.Unfortunately,existing we use the terms 'collect a tag','collect data from a tag',and approaches do not facilitate this feature. 'identify a tag'interchangeably.For simplicity,we assume a unit disk model for the interrogation region of a reader.Note B.Overview that our scheme is not constrained by this assumption.We Motivated from the above observations,we split an identi- denote Ti=[t1,...,tn}as the tag set.The tags in Ti are fication procedure in two phases.In Phase-I,the system iden- located in the interrogation region of reader ri.T=UreRTi tifies all non-contentious tags.We term this phase as Shelv- denotes the set of all tags.The neighboring reader set of r; ing Interference.In Phase-II,neighboring readers jointly and is denoted as I(ri).The tags in Te=Ur,er(r)(TinTj) collaboratively identify contentious tags.We call this phase are the contentious tags of reader ri.They are located in the as Joint Identification.Hence,we propose our anti-collisionfind that when two readers attempt to communicate with those tags at the same time, the signals cannot be correctly resolved and considered as environment noises by the tags. Meanwhile, each reader is unaware of the existence of interference from other readers. Therefore, those tags fail to be identified by any reader. To resolve the signal interference, existing approaches convert the potential reader collision to an undirected graph, named as Reader Conflict Graph (RCG). In RCG, a node represents an individual RFID reader and an edge represents a collision constraint: if two nodes are connected with an edge in RCG, the related readers will collide if they transmit the command at the same time. Note that the edge does not represent the communication between readers but only the potential reader collision. Indeed, all readers in the network are often linked through LAN. The existing approaches, e.g., Colorwave [13], utilize the graph coloring algorithm to solve reader collisions. Those solutions thereby are similar to finding the smallest number of total colors for coloring the RCG such that any two adjacent vertices are in different colors. Indeed, a color is corresponding to a periodic reservation for collision-free transmissions. The signal interference can be addressed by well arranging neigh￾boring readers to send commands exclusively. However, as we discussed before, the exclusive scheduling incurs a poor throughput of identification. C. Reader-Tag Collision To resolve reader-tag collision, EPCglobal Gen II stan￾dards [9] specify two separated frequencies for the reader’s query and tag’s response, respectively, if readers are densely deployed. In fact, we can boil down reader-tag collisions to reader collisions as long as we synchronize all readers’ behaviors. For example, if we schedule (r1,r2 ) in sequence, we can only consider the other two types of collisions. D. System Model In our model, we use slotted channel as the communication model between readers and tags. The transmissions happen within predefined and equally spaced intervals, termed as slots. The reader guarantees the slot synchronization via energizing probe/request. Obviously, the time required to identify tags is proportional to the number of tags. All readers are connected by wired or wireless networks which enable them to commu￾nication with each other at high speed. Consider a set of readers R = {r1, · · · , rm} are deployed at a region. An identification procedure is the procedure to identify all the tags within the region at a time. In this paper, we use the terms ‘collect a tag’, ‘collect data from a tag’, and ‘identify a tag’ interchangeably. For simplicity, we assume a unit disk model for the interrogation region of a reader. Note that our scheme is not constrained by this assumption. We denote Ti = {t1, · · · , tn} as the tag set. The tags in Ti are located in the interrogation region of reader ri . T = ∪ri∈RTi denotes the set of all tags. The neighboring reader set of ri is denoted as Γ(ri). The tags in T C i = ∪rj∈Γ(ri)(Ti ∩ Tj ) are the contentious tags of reader ri . They are located in the overlapped regions between ri and its neighboring readers. On the contrary, the tags in T N i = ∪rj∈Γ(ri)(Ti\Tj ) , where Ti\Tj = {t|t ∈ Ti & t /∈ Tj}, are non-contentious tags of reader ri . They are only covered by reader ri . We use undirect graph G = (R, E) to denote RCG. Reader ri and rj ,where ri , rj ∈ R, are adjacent in G if their corresponding nodes are connected by an edge, i.e., (ri , rj ) ∈ E. The degree d(ri) of reader ri is the number of edges connected to ri in RCG. The maximum degree of graph G is defined as ∆(G) = maxr∈Rd(r). We assume the readers can be well synchronized through a global clock and some synchronization protocols [16]. III. SEASON In this section, we first present three important observations that motivate our design. We then present the design of Season and describe the three protocols we propose. A. Observations We observe three intuitive but important facts in practice: Observation 1: Majority of tags are non-contentious due to the well advanced deployment of readers. If we allow the readers concurrently interrogate non-contentious tags, we can improve the identification throughput. Hence, a key step of improving the identification throughput is to enable the concurrency for neighboring readers in identifying non￾contentious tags. This observation motivates us to handle the non-contentious and contentious tags separately. Observation 2: The minor contentious tags indeed cause the major delay during the identification. Sometimes, only one contentious tag may incur large delay. As shown in Fig. 2(a), there is one contentious tag in the contentious region between r1 and r2, while no tag is in the contentious region between r1 and r3. However, both reader r1 and r3 are not aware of this situation since they have no knowledge about the locations of tags. These two readers have to be activated exclusively if utilizing prior works [12]–[14]. Therefore, we seek to design new identification pattern for contentious tags. Observation 3: The signals from the contentious tags can be received by the readers that cover these tags. For instance, the responding signal generated by the contentious tag t1 will be received by two neighboring reader r1 and r2, as shown in Fig. 2(b). If we can deliberately arrange one reader to interrogate the contentious tags while its neighboring readers passively listen to the responses from these tags, the system is able to retrieve the data from the contentious tag even there is a potential reader collisions in RCG. Unfortunately, existing approaches do not facilitate this feature. B. Overview Motivated from the above observations, we split an identi- fication procedure in two phases. In Phase-I, the system iden￾tifies all non-contentious tags. We term this phase as Shelv￾ing Interference. In Phase-II, neighboring readers jointly and collaboratively identify contentious tags. We call this phase as Joint Identification. Hence, we propose our anti-collision