Contentious region Contentious TN before identification.In detail,the reader maintains a tag variable k to record the number of tags that have been collected so far.Initially,k=0.To minimize the identification time.we dynamically adjust the frame to T-k after the k-th tag is collected. D.Season-II After all readers finish their identification of non- contentious tags,the system enters into Phase-II.Based on our (a) (b) third observation,we design joint identification protocols to identify contentious tags.For a group of neighboring readers, Fig.2.(a)Potential reader collisions incur significant delay;(b)The signal we only let one of them become active to interrogate the from tag ti will be received by reader ri and r2 tags while others stay in silence and just passively listen to the signals from contentious tags.Joint identification has two clear advantages:(1)A joint identification can avoid reader scheme,Season,to undertake the tasks of these two phases. collisions among neighboring readers since only one of them Season is a protocol stack comprising of three protocols. sends query commands,(2)Reduce the identification delay Season-I is designed to collect data from non-contentious tags significantly because the readers concurrently receive the IDs in Phase-I.Phase-II includes multiple rounds.In each round, of continuous tags. we first employ Season-II to determine appropriate readers For easy illustration,we term the reader being responsible for actively interrogating contentious tags while keeping other for interrogating tags as active reader and the reader staying readers passively listening.Then we conduct Season-III to in listening state as passive reader.Hence,the first task in collect data from contentious tags.The iterative execution of Phase-II is to select appropriate active readers from a group Season-II and Season-III continues until the system collects of neighboring readers.We propose Season-II,which is a data from all contentious tags. distributed algorithm for determining proper active readers. In our system model,the edges of a reader in RCG C.Season-I represent the contentious regions that the reader shared with In Phase-I,Season-I allows neighboring readers to concur- its neighbors.In RCG,we determine active readers according rently identify tags in spite of the signal interference occurred to two conditions as follows:(1)they are able to cover edges at contentious tags.Although those contentious tags cannot as most as possible:(2)these active readers will not incur correctly resolve the readers'query commands,this treatment signal interference among themselves if they are concurrently helps us to naturally distinguish all non-contentious tags from activated.Namely,the selected active readers are not adjacent contentious tags.The non-contentious tags transmit their IDs in RCG.Clearly,these two conditions are the Necessary and then transfer into the silent state.Our approach can Conditions for the optimal selection of active readers.We guarantee that the majority of tags can be identified after thereby convert the problem of selecting active readers to Phase-I,if most tags are located in non-contentious regions,finding the Maximal Weighted Independent Set(MWIS)in and hence significantly improve the identification throughput. an undirected graph. In an idea case,there are no contentious tags and all tags can Given an undirected graph G.A independent set of V is a be identified after Phase-I. subset SCV such that no any two nodes n,v E S are neigh- Season-I is a state based anti-tag-collision protocol.Similar bors in V,and every node wS has at least one neighbor in to FSA.it divides the identification procedure into many S.The MIS of V is the maximal independent set generated frames and each frame contains several equivalent time slots. from V.A natural variant of MIS is the maximal weighted Different from FSA based approaches,Season-I adaptively independent set (MWIS),where each node is associated with tunes the length of frame to optimize the identification latency.a weight.Solving MWIS is to find a MIS with the maximal That is,the reader will terminate the frame once it successfully total weight of its nodes. receives a tag's ID and then start a new frame. In our problem,we set the weight of each node as the Obviously,each tag independently transmits its ID with a number of its edges since we attempt to employ the min- probability of 1/f in each slot.One important goal of Season- imum nodes (active readers)to cover the maximum edges I is to choose appropriate f so as to minimize the expected (contentious regions)in RCG. identification time.Not surprisingly,the optimal choice of f We adopt a MWIS solution proposed by [23]to determine is TN.The problem of choosing an optimal f for ALOHA active readers.For example,as illustrated Fig.4 (a),the based approaches has been widely studied in the literature [17]set of active readers is A=fr2,r6,r7}while others are [18].But the challenge is that we usually do not know the considered as passive readers,i.e.,the set of passive readers number of tags in advance.Fortunately,a number of recent is P1=[r1,r3,r4,r5).By activating the active readers in A works [19]-[22],effectively estimate the number.We adopt and keeping the readers in P listening,the contentious regions USE [19]in Season.We require the reader to estimate number corresponding to the edges that are connected to the nodes inr1 r2 t1 r1 r2 r3 Contentious tag Contentious region (a) (b) Fig. 2. (a) Potential reader collisions incur significant delay; (b) The signal from tag t1 will be received by reader r1 and r2. scheme, Season, to undertake the tasks of these two phases. Season is a protocol stack comprising of three protocols. Season-I is designed to collect data from non-contentious tags in Phase-I. Phase-II includes multiple rounds. In each round, we first employ Season-II to determine appropriate readers for actively interrogating contentious tags while keeping other readers passively listening. Then we conduct Season-III to collect data from contentious tags. The iterative execution of Season-II and Season-III continues until the system collects data from all contentious tags. C. Season-I In Phase-I, Season-I allows neighboring readers to concur￾rently identify tags in spite of the signal interference occurred at contentious tags. Although those contentious tags cannot correctly resolve the readers’ query commands, this treatment helps us to naturally distinguish all non-contentious tags from contentious tags. The non-contentious tags transmit their IDs and then transfer into the silent state. Our approach can guarantee that the majority of tags can be identified after Phase-I, if most tags are located in non-contentious regions, and hence significantly improve the identification throughput. In an idea case, there are no contentious tags and all tags can be identified after Phase-I. Season-I is a state based anti-tag-collision protocol. Similar to FSA, it divides the identification procedure into many frames and each frame contains several equivalent time slots. Different from FSA based approaches, Season-I adaptively tunes the length of frame to optimize the identification latency. That is, the reader will terminate the frame once it successfully receives a tag’s ID and then start a new frame. Obviously, each tag independently transmits its ID with a probability of 1/f in each slot. One important goal of Season￾I is to choose appropriate f so as to minimize the expected identification time. Not surprisingly, the optimal choice of f is |T N i |. The problem of choosing an optimal f for ALOHA based approaches has been widely studied in the literature [17] [18]. But the challenge is that we usually do not know the number of tags in advance. Fortunately, a number of recent works [19]–[22], effectively estimate the number. We adopt USE [19] in Season. We require the reader to estimate number |T N i | before identification. In detail, the reader maintains a variable k to record the number of tags that have been collected so far. Initially, k = 0. To minimize the identification time, we dynamically adjust the frame to |T N i | − k after the k-th tag is collected. D. Season-II After all readers finish their identification of non￾contentious tags, the system enters into Phase-II. Based on our third observation, we design joint identification protocols to identify contentious tags. For a group of neighboring readers, we only let one of them become active to interrogate the tags while others stay in silence and just passively listen to the signals from contentious tags. Joint identification has two clear advantages: (1) A joint identification can avoid reader collisions among neighboring readers since only one of them sends query commands, (2) Reduce the identification delay significantly because the readers concurrently receive the IDs of continuous tags. For easy illustration, we term the reader being responsible for interrogating tags as active reader and the reader staying in listening state as passive reader. Hence, the first task in Phase-II is to select appropriate active readers from a group of neighboring readers. We propose Season-II, which is a distributed algorithm for determining proper active readers. In our system model, the edges of a reader in RCG represent the contentious regions that the reader shared with its neighbors. In RCG, we determine active readers according to two conditions as follows: (1) they are able to cover edges as most as possible; (2) these active readers will not incur signal interference among themselves if they are concurrently activated. Namely, the selected active readers are not adjacent in RCG. Clearly, these two conditions are the Necessary Conditions for the optimal selection of active readers. We thereby convert the problem of selecting active readers to finding the Maximal Weighted Independent Set (MWIS) in an undirected graph. Given an undirected graph G. A independent set of V is a subset S ⊆ V such that no any two nodes n, v ∈ S are neigh￾bors in V , and every node w /∈ S has at least one neighbor in S. The MIS of V is the maximal independent set generated from V . A natural variant of MIS is the maximal weighted independent set (MWIS), where each node is associated with a weight. Solving MWIS is to find a MIS with the maximal total weight of its nodes. In our problem, we set the weight of each node as the number of its edges since we attempt to employ the min￾imum nodes (active readers) to cover the maximum edges (contentious regions) in RCG. We adopt a MWIS solution proposed by [23] to determine active readers. For example, as illustrated Fig. 4 (a), the set of active readers is A1 = {r2, r6, r7} while others are considered as passive readers, i.e., the set of passive readers is P1 = {r1, r3, r4, r5}. By activating the active readers in A1 and keeping the readers in P1 listening, the contentious regions corresponding to the edges that are connected to the nodes in