not have to make advertisement in each slot.It may advertise at most once in the frame.In FCAT,each tag participates once every certain number of slots,and the tags will use the probabilistically in every slot of the frame. same report probability in those slots. Let Xi be the indicator random variable for the event that Third,after resolving a collision record,the reader learns the jth slot in the frame is empty.i.e.,X;=1 means the jth an extra ID and it broadcasts the ID in order to inform slot is empty and Xj=0 means it is not empty.Similarly.let the corresponding tag to stop participating in the protocol. Yi be the indicator random variable for the event that the jth However,instead of transmitting the whole ID (which is 96 slot is a singleton slot.Because each tag decides to transmit bits for GEN2 tags),the reader may transmit the slot index with probability pi in every slot in the frame,we have of the collision record.A tag stores the indices of the slots in which it has transmitted.If the tag receives a slot index Prob(Xj =1)=(1-pi)N,vje[1..f]. (6 that matches a stored one,it knows that the reader must have The expected value of no is collected its ID.A slot index can be much smaller than 96 bits.If we use 23-bit slot indices,more than 8 million slots are allowed.In our simulations,the number of slots required E(no)=(1-P)N=f(1-)4 (7) j=1 never exceeds2W」 The probability for the jth slot in the frame to be a singleton B.Using Frames is We propose the Framed Collision-Aware Tag identification protocol (FCAT),which improves SCAT by eliminating the Prof-1)-(N)p.(1-p)-1-Np(1-p)-1. inefficiency described in Section V-A.FCAT shares much (8) of the protocol details with SCAT.Below we will focus on describing their differences. The expected value of nI is In FCAT,time is divided into frames of size f.That is, each frame consists of f time slots.Each frame has an index, starting from zero.The index of the jth slot in the ith frame is En）)=∑Np1-p.)M-1=fN1-)M-1.9) i=l ix f+j.Before a frame begins,the RFID reader broadcasts Obviously,E(no)+E(n1)+E(ne)=f.Hence a pre-frame advertisement,including the frame index i and the report probability pi.Each slot of the frame consists of E(ne)=f-E(no)-E(n1) a report segment,during which the tags transmit their IDs, =f(1-(1-p)N-NP(1-p)N-1) and an acknowledgement segment,during which the reader (10) transmits either a positive acknowledgement or a negative =f1-(1-p)-1(1-p:+w) acknowledgement. The above equation can be rewritten as In any slot of the ith frame,each tag transmits its ID with probability pi.After receiving the signal in the report segment, N:= 1-2)-n1-%+ +1. (11) the reader performs the same operations as in SCAT,except n(1-p) that it does not transmit the IDs learned from resolving the At the end of the ith frame,the reader counts the value of collision records in the acknowledgement segment.Instead, ne.Substituting E(nc)by the instance value ne (obtained in it transmits the slot indices of the resolved collision records, the ith frame),the reader obtains an estimation of Ni by the which are shorter than the IDs themselves.If a tag receives a following formula: slot index that matches a slot in which it has transmitted its ID,it stops participating in FCAT.Certainly,if a tag receives 1-学)-n1-+w）+1. Ni= (12) a positive acknowledgement for its ID just transmitted in the In(1-Pi) report segment,it will also stop participating in FCAT. Next,we derive E(N;).To simplify the equations,let C1= C.Estimating the Number of Tags within FCAT Ca=+1,and function g(ne)=mn(1 In(1-Pi) Finally,we address the problem of how to learn the value of )We expand the right hand side of(12)by its Taylor series N.There exist efficient methods for estimating the number of about g=E(ne). tags.However,using them as a pre-step of FCAT incurs con- siderable overhead.In the following,we embed an estimation method within FCAT. )+(n-)+(nc-q)"(a) Consider an arbitrary frame with index i.Let no,ni and ne be the random variables for the numbers of empty,singleton ne"++C.(13) and collision slots,respectively.We can estimate the statistical Since q=E(nc).the mean of the second term in (13)is 0. relationship between these random variables and the number Therefore,we keep the first three terms when computing the Na of tags that are currently participating in the protocol. approximated value of E(Ni). Based on that relationship,we can estimate Ni from the measured values of no and ne.Our approach shares some similarity with [24].However,in [24],each tag transmits E()=C(+((ne)+Ca.(14) 552not have to make advertisement in each slot. It may advertise once every certain number of slots, and the tags will use the same report probability in those slots. Third, after resolving a collision record, the reader learns an extra ID and it broadcasts the ID in order to inform the corresponding tag to stop participating in the protocol. However, instead of transmitting the whole ID (which is 96 bits for GEN2 tags), the reader may transmit the slot index of the collision record. A tag stores the indices of the slots in which it has transmitted. If the tag receives a slot index that matches a stored one, it knows that the reader must have collected its ID. A slot index can be much smaller than 96 bits. If we use 23-bit slot indices, more than 8 million slots are allowed. In our simulations, the number of slots required never exceeds 2N. B. Using Frames We propose the Framed Collision-Aware Tag identification protocol (FCAT), which improves SCAT by eliminating the inefficiency described in Section V-A. FCAT shares much of the protocol details with SCAT. Below we will focus on describing their differences. In FCAT, time is divided into frames of size f. That is, each frame consists of f time slots. Each frame has an index, starting from zero. The index of the jth slot in the ith frame is i × f + j. Before a frame begins, the RFID reader broadcasts a pre-frame advertisement, including the frame index i and the report probability pi. Each slot of the frame consists of a report segment, during which the tags transmit their IDs, and an acknowledgement segment, during which the reader transmits either a positive acknowledgement or a negative acknowledgement. In any slot of the ith frame, each tag transmits its ID with probability pi. After receiving the signal in the report segment, the reader performs the same operations as in SCAT, except that it does not transmit the IDs learned from resolving the collision records in the acknowledgement segment. Instead, it transmits the slot indices of the resolved collision records, which are shorter than the IDs themselves. If a tag receives a slot index that matches a slot in which it has transmitted its ID, it stops participating in FCAT. Certainly, if a tag receives a positive acknowledgement for its ID just transmitted in the report segment, it will also stop participating in FCAT. C. Estimating the Number of Tags within FCAT Finally, we address the problem of how to learn the value of N. There exist efficient methods for estimating the number of tags. However, using them as a pre-step of FCAT incurs con￾siderable overhead. In the following, we embed an estimation method within FCAT. Consider an arbitrary frame with index i. Let n0, n1 and nc be the random variables for the numbers of empty, singleton and collision slots, respectively. We can estimate the statistical relationship between these random variables and the number Ni of tags that are currently participating in the protocol. Based on that relationship, we can estimate Ni from the measured values of n0 and nc. Our approach shares some similarity with [24]. However, in [24], each tag transmits at most once in the frame. In FCAT, each tag participates probabilistically in every slot of the frame. Let Xj be the indicator random variable for the event that the jth slot in the frame is empty, i.e., Xj = 1 means the jth slot is empty and Xj = 0 means it is not empty. Similarly, let Yj be the indicator random variable for the event that the jth slot is a singleton slot. Because each tag decides to transmit with probability pi in every slot in the frame, we have P rob{Xj = 1} = (1 − pi) Ni , ∀j ∈ [1..f]. (6) The expected value of n0 is E(n0) = f j=1 (1 − pi) Ni = f(1 − pi) Ni . (7) The probability for the jth slot in the frame to be a singleton is P rob{Yj = 1} = Ni 1  pi(1 − pi) Ni−1 = Nipi(1 − pi) Ni−1. (8) The expected value of n1 is E(n1) = f i=1 Nipi(1 − pi) Ni−1 = fNipi(1 − pi) Ni−1. (9) Obviously, E(n0) + E(n1) + E(nc) = f. Hence E(nc) = f − E(n0) − E(n1) = f(1 − (1 − pi) Ni − Nipi(1 − pi) Ni−1) = f(1 − (1 − pi) Ni−1(1 − pi + ω)). (10) The above equation can be rewritten as Ni = ln(1 − E(nc) f ) − ln(1 − pi + ω) ln(1 − pi) + 1. (11) At the end of the ith frame, the reader counts the value of nc. Substituting E(nc) by the instance value nc (obtained in the ith frame), the reader obtains an estimation of Ni by the following formula: Nˆi = ln(1 − nc f ) − ln(1 − pi + ω) ln(1 − pi) + 1. (12) Next, we derive E(Nˆi). To simplify the equations, let C1 = 1 ln(1−pi) , C2 = −ln(1−pi+ω) ln(1−pi) +1, and function g(nc) = ln(1− nc f ). We expand the right hand side of (12) by its Taylor series about q = E(nc). Nˆi = C1  g(q)+(nc − q)g (q) + 1 2 (nc − q) 2g(q) + 1 6 (nc − q) 3g(q) + ... + C2. (13) Since q = E(nc), the mean of the second term in (13) is 0. Therefore, we keep the first three terms when computing the approximated value of E(Nˆi). E(Nˆi) C1  g(q) + 1 2 E((nc − q) 2)g(q)  + C2. (14) 552