access networks,where each terminal transmits a single packet slots,it sets pi=1 for one slot and if it still finds an empty twice at two randomly-selected time slots in each MAC frame slot,it knows that the IDs of all tags have been collected. [22].The throughput upper bound can be predicted if the number of packets per slot is known (which requires the B.Collision Resolution knowledge of the number of transmitting terminals).In our When the CRC received in the report segment is verified to context,we do not derive a throughput upper bound for a be correct,the reader learns the ID of a tag from the current given set of system parameters.Instead,we determine the slot i.Knowing the ID,the RFID reader can easily figure out best system parameter that optimizes the throughput.We do the previous slots in which this tag has transmitted.For an not assume the knowledge for the number of tags that is arbitrary collision record with slot index j,the tag must have participating in the protocol.In fact,this number changes over transmitted if H(Dlj)≤lp:×2」.If that is the case,the time because after a tag successfully delivers its ID to the reader removes the signal received in the current slot from reader,it will stop transmitting.A tag may transmit for one, the mixed signal in the collision record,treats the result as two or more times at any time slots during the reading process. if it was the ID signal of a single tag,and extracts the CRC Moreover,because the number of participating tags changes, code.If the CRC code is verified to be correct,the collision the optimal system parameter also changes over time. record is resolved and the reader learns an additional tag ID. IV.SLOTTED COLLISION-AWARE TAG IDENTIFICATION The signal for that ID can be used to resolve other collision records in a similar process as described above. PROTOCOL Resolving the collision slots incurs computation overhead. In this section,we propose the Slotted Collision-Aware Tag Hence,we expect the reader to be computationally capable or identification protocol (SCAT).In the next section,we will connected to a powerful computing device.It is worth noting optimize the protocol for less overhead. that the RFID system works in a low speed channel (53 Kbps A.Protocol Description for the Philips I-Code system),while the original ANC [1] SCAT is a time-slotted protocol.The time slots are synchro- and the follow-up work [23]are designed for 11 Mbps or higher throughput channels,which is far more demanding, nized by the reader's signal.Each time slot consists of three yet experimentally-demonstrated feasible. segments:the advertisement segment,the report segment,and the acknowledgement segment. C.Determining the Optimal Value for Pi In the advertisement segment,the RFID reader sends out a We want to determine the optimal report probability pi for slot index i and a report probabiliry pi,where i begins from each slot such that the number of slots for collecting the IDs zero and increases by one after each slot. of all tags is minimized.Consider an arbitrary time slot with In the report segment,each tag decides to transmit its ID with probability pi.To actually broadcast the report prob- index i.When there is only one tag transmitting,the RFID ability,the reader may send out an l-bit integer pix 2] reader will learn the ID of the tag.If there are two tags transmitting,the reader will not learn any ID now but will instead of a real number pi.A tag computes a hash function H(IDli)whose range is [0.2).IfH(Dli)≤p:×2」，the learn one ID later when the other ID is known (such that the collision record of this slot can be resolved).Similarly,when tag transmits its ID】 k tags transmit in this slot for k≤入，the reader will learn For an empty slot,the reader transmits a negative acknowl- edgement.For a collision slot,the reader will not be able one ID from the collision record when the other (k-1)IDs are known.Essentially,a singleton slot or a k-collision slot to tell how many tags have transmitted simultaneously in the report segment.It will record the mixed signal and transmit will allow the reader to learn one ID now or later.Hence,we a negative acknowledgement.The mixed signal and the slot shall choose the value of pi that maximizes the probability index form a collision record.Over time the reader will collect for one,two,.,or A tags to transmit in the current slot. Let N be the number of tags in the system.Its value can a group of such records.The operation for a singleton slot is more complicated.The reader learns the ID of a tag in the be estimated to an arbitrary accuracy [24]in a pre-step of report segment.Using this ID,it tries to resolve some collision SCAT.This pre-step will be removed in the next section. Before slot i,the reader may have successfully collected and records to learn more tag IDs (see the next subsection).It then transmits a positive acknowledgement,together with the IDs acknowledged a number ni of tag IDs,and those tags will that are learned from the resolution of the previous collision no longer participate in the protocol of SCAT.Let N be the number of tags that the reader has not identified yet before records. When the tag that transmits in the report segment receives slot i.Since ni is known to the reader,Ni is also known. the positive acknowledgement,it will stop participating in the As each tag decides to transmit with probability pi,the SCAT protocol as its ID has been successfully delivered to number of tags that transmit will be a random variable X;that follows the binomial distribution.The probability for Xi=k. the reader.Similarly,when a tag that transmitted its ID at an earlier slot but has not received a positive acknowledgement k∈[0Nis(）·p(1-ps)Ne-k.Our objective is to yet receives its own ID in the acknowledgement segment,it maximize the probability of Xi [0..A,which is will stop participating in SCAT. The SCAT protocol stops when no tag transmits any more. When the reader finds a certain number of consecutive empty =-（）-w四 550access networks, where each terminal transmits a single packet twice at two randomly-selected time slots in each MAC frame [22]. The throughput upper bound can be predicted if the number of packets per slot is known (which requires the knowledge of the number of transmitting terminals). In our context, we do not derive a throughput upper bound for a given set of system parameters. Instead, we determine the best system parameter that optimizes the throughput. We do not assume the knowledge for the number of tags that is participating in the protocol. In fact, this number changes over time because after a tag successfully delivers its ID to the reader, it will stop transmitting. A tag may transmit for one, two or more times at any time slots during the reading process. Moreover, because the number of participating tags changes, the optimal system parameter also changes over time. IV. SLOTTED COLLISION-AWARE TAG IDENTIFICATION PROTOCOL In this section, we propose the Slotted Collision-Aware Tag identification protocol (SCAT). In the next section, we will optimize the protocol for less overhead. A. Protocol Description SCAT is a time-slotted protocol. The time slots are synchro￾nized by the reader’s signal. Each time slot consists of three segments: the advertisement segment, the report segment, and the acknowledgement segment. In the advertisement segment, the RFID reader sends out a slot index i and a report probability pi, where i begins from zero and increases by one after each slot. In the report segment, each tag decides to transmit its ID with probability pi. To actually broadcast the report prob￾ability, the reader may send out an l-bit integer pi × 2l  instead of a real number pi. A tag computes a hash function H(ID|i) whose range is [0..2l ). If H(ID|i) ≤ pi × 2l , the tag transmits its ID. For an empty slot, the reader transmits a negative acknowl￾edgement. For a collision slot, the reader will not be able to tell how many tags have transmitted simultaneously in the report segment. It will record the mixed signal and transmit a negative acknowledgement. The mixed signal and the slot index form a collision record. Over time the reader will collect a group of such records. The operation for a singleton slot is more complicated. The reader learns the ID of a tag in the report segment. Using this ID, it tries to resolve some collision records to learn more tag IDs (see the next subsection). It then transmits a positive acknowledgement, together with the IDs that are learned from the resolution of the previous collision records. When the tag that transmits in the report segment receives the positive acknowledgement, it will stop participating in the SCAT protocol as its ID has been successfully delivered to the reader. Similarly, when a tag that transmitted its ID at an earlier slot but has not received a positive acknowledgement yet receives its own ID in the acknowledgement segment, it will stop participating in SCAT. The SCAT protocol stops when no tag transmits any more. When the reader finds a certain number of consecutive empty slots, it sets pi = 1 for one slot and if it still finds an empty slot, it knows that the IDs of all tags have been collected. B. Collision Resolution When the CRC received in the report segment is verified to be correct, the reader learns the ID of a tag from the current slot i. Knowing the ID, the RFID reader can easily figure out the previous slots in which this tag has transmitted. For an arbitrary collision record with slot index j, the tag must have transmitted if H(ID|j) ≤ pi × 2l . If that is the case, the reader removes the signal received in the current slot from the mixed signal in the collision record, treats the result as if it was the ID signal of a single tag, and extracts the CRC code. If the CRC code is verified to be correct, the collision record is resolved and the reader learns an additional tag ID. The signal for that ID can be used to resolve other collision records in a similar process as described above. Resolving the collision slots incurs computation overhead. Hence, we expect the reader to be computationally capable or connected to a powerful computing device. It is worth noting that the RFID system works in a low speed channel (53 Kbps for the Philips I-Code system), while the original ANC [1] and the follow-up work [23] are designed for 11 Mbps or higher throughput channels, which is far more demanding, yet experimentally-demonstrated feasible. C. Determining the Optimal Value for pi We want to determine the optimal report probability pi for each slot such that the number of slots for collecting the IDs of all tags is minimized. Consider an arbitrary time slot with index i. When there is only one tag transmitting, the RFID reader will learn the ID of the tag. If there are two tags transmitting, the reader will not learn any ID now but will learn one ID later when the other ID is known (such that the collision record of this slot can be resolved). Similarly, when k tags transmit in this slot for k ≤ λ, the reader will learn one ID from the collision record when the other (k − 1) IDs are known. Essentially, a singleton slot or a k-collision slot will allow the reader to learn one ID now or later. Hence, we shall choose the value of pi that maximizes the probability for one, two, ..., or λ tags to transmit in the current slot. Let N be the number of tags in the system. Its value can be estimated to an arbitrary accuracy [24] in a pre-step of SCAT. This pre-step will be removed in the next section. Before slot i, the reader may have successfully collected and acknowledged a number ni of tag IDs, and those tags will no longer participate in the protocol of SCAT. Let Ni be the number of tags that the reader has not identified yet before slot i. Since ni is known to the reader, Ni is also known. As each tag decides to transmit with probability pi, the number of tags that transmit will be a random variable Xi that follows the binomial distribution. The probability for Xi = k, ∀k ∈ [0..Ni] is Ni k  · pk i (1 − pi)Ni−k. Our objective is to maximize the probability of Xi ∈ [0..λ], which is λ k=1 P rob{Xi = k} = λ k=1  Ni k  · pk i (1 − pi) Ni−k. (2) 550