This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the main Technical Program at IEEE INFOCOM 2010. backscatter efficiency are probabilistic.In order to depict the Theorem I:According to the probabilistic propagation RFID tag identification process under the probabilistic propa- model,the probability for a tag to successfully reply in the gation situation,assume that the distance between the reader frame with size f by monitoring the QueryRep messages is and the tag to be identified is r.We use pi(r)to denote the equal to pi(r),that is pe(f,r)=pi(r). probability for the tag to successfully receive the message from Proof:Since pa(t,x,r)denotes the probability for the the reader,and then use pt(r)to denote the probability for the tag to receive x OueryRep messages at the tth slot,and in reader to successfully receive the backscattered message from order to succeed to do it within the specified frame size f, the tag.Then by definition we have it should satisfy 1≤x≤t≤f.Therefore according to the definition for pe(f,r)in Eq.(4),pe(f,r)can be expressed in p(T)=Prob{P≥Ps} (2) the following equivalent form: p(r)=Prob{P4≥Prs P≥Pa} (3) p(f,r） B.Probabilistic model for tag identification According to Section III-B,considering one specified RFID Then,as we have tag,we can divide the tag inventory and access procedure into four phases:(1)Obtain frame size from the Query/QueryAdjust ∑pa(t,玉，r）=p(r)·∑Cgm(r)P-(1-p(r)-r message,(2)Monitor the QueryRep messages for selected slot, r=1 (3)Backscatter the RN/6 message,and(4)Backscatter the ID =P(T)·[P(r）+(1-P:(r)-1=P(r), message.Here we do not consider the optional Select message thus in the probabilistic model.In the following we respectively analyze the actual impact on the four phases due to the probabilistic propagation. p%f,r)=台 1)Obtain frame size from Query/QueryAdjust message: Assume before each Query Round,the number of tags left The theorem gets proved. unread is n.When the reader sends the Query/QueryAdjust The Ouery message actually acts as the role of the first message,the tag will detect and resolve this message with QueryRep message,especially when f =1 the unique Query probability pi(r).Thus n.pi(r)tags are able to select the message takes the role of the OueryRep message.Thus the slots inside the frame. first phase and the second phase are not independent to each 2)Monitor QueryRep messages for selected slot:For those other.However,as long as the frame size f is large enough, tags which have successfully selected the slot number ac- we can assume that the first phase and the second phase are cording to the frame size f,each tag counts down the slot independent to each other.In this situation,given the number counter slot according to the received QueryRep messages. of unread tags,n,the expected number of tags successfully Each OueryRep message is detected and resolved by the tag obtaining a slot inside the frame is with probability pi(r).When slot=0 the tag backscatters n'=n·p(r）·pg(f,r）=n·(p(r)2 the RN16 message to the reader.Due to the loss of QueryRep messages,the tag actually may have to wait for more slots Note that after successfully receiving the Ouery message after the exact slot it selects.In this situation suppose a tag tags randomly select the slots inside the frame with size f, has selected the zth slot(1<z<f)within the frame size using a uniform approach.Then due to the probabilistic loss of f,the probability for it to detect x QueryRep messages at the OueryRep messages,the actual slot t in which the tag replies is actual tth (t>x)slot is deferred to some extent over the original selected slot z.Since the original slot z is selected with uniform probability,then as pa(t,x,r）=(p(r)·C(p(r)F-1(1-p(r)-x indicated in Theorem I's proof,the probability for the tag ac- As t varies over the range [+oo,if t<f,then the tag can tually replies in slot t is P(t)= z=17·P(t,x,r)=过 reply inside the frame;otherwise,the tag cannot reply inside Since P(t)is the same for all slot t,it infers that the actual slot the frame.Therefore if a tag originally selects the ath slot,the t in which the tag replies is uniformly distributed inside the probability for it to successfully reply in the frame is frame.Therefore,if we do not consider the propagation loss for backscattering.then,according to the binomial distribution the expected number of empty slots,single slots,and collision pa(f;z,r)=>pa(t,z,r). slots,no,n1,ne,can be calculated as follows: t工 As each tag uniformly selects a slot from 1 to f,then the n0=f(1-)m, probability for it to successfully reply in the frame is n1=n'(1-3)-1 (5) ne f-no-n1. (4) We denote the above mentioned empty/single/collision 1 slot as original empty/single/collision slot,which means Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply.backscatter efficiency are probabilistic. In order to depict the RFID tag identification process under the probabilistic propa￾gation situation, assume that the distance between the reader and the tag to be identified is r. We use pi(r) to denote the probability for the tag to successfully receive the message from the reader, and then use pt(r) to denote the probability for the reader to successfully receive the backscattered message from the tag. Then by definition we have pi(r) = P rob{P2 ≥ Pts}, (2) pt(r) = P rob{P4 ≥ Prs|P2 ≥ Pts}. (3) B. Probabilistic model for tag identification According to Section III-B, considering one specified RFID tag, we can divide the tag inventory and access procedure into four phases:(1) Obtain frame size from the Query/QueryAdjust message, (2) Monitor the QueryRep messages for selected slot, (3) Backscatter the RN16 message, and (4) Backscatter the ID message. Here we do not consider the optional Select message in the probabilistic model. In the following we respectively analyze the actual impact on the four phases due to the probabilistic propagation. 1) Obtain frame size from Query/QueryAdjust message: Assume before each Query Round, the number of tags left unread is n. When the reader sends the Query/QueryAdjust message, the tag will detect and resolve this message with probability pi(r). Thus n · pi(r) tags are able to select the slots inside the frame. 2) Monitor QueryRep messages for selected slot: For those tags which have successfully selected the slot number ac￾cording to the frame size f, each tag counts down the slot counter slot according to the received QueryRep messages. Each QueryRep message is detected and resolved by the tag with probability pi(r). When slot = 0 the tag backscatters the RN16 message to the reader. Due to the loss of QueryRep messages, the tag actually may have to wait for more slots after the exact slot it selects. In this situation suppose a tag has selected the xth slot (1 ≤ x ≤ f) within the frame size f, the probability for it to detect x QueryRep messages at the actual tth (t ≥ x) slot is pα(t, x, r)=(pi(r)) · Cx−1 t−1 (pi(r))x−1(1 − pi(r))t−x. As t varies over the range [x, +∞], if t ≤ f, then the tag can reply inside the frame; otherwise, the tag cannot reply inside the frame. Therefore if a tag originally selects the xth slot, the probability for it to successfully reply in the frame is pβ(f, x, r) = f t=x pα(t, x, r). As each tag uniformly selects a slot from 1 to f, then the probability for it to successfully reply in the frame is pθ(f, r) = f x=1 1 f pβ(f, x, r) = 1 f f x=1 f t=x pα(t, x, r). (4) Theorem 1: According to the probabilistic propagation model, the probability for a tag to successfully reply in the frame with size f by monitoring the QueryRep messages is equal to pi(r), that is pθ(f, r) = pi(r). Proof: Since pα(t, x, r) denotes the probability for the tag to receive x QueryRep messages at the tth slot, and in order to succeed to do it within the specified frame size f, it should satisfy 1 ≤ x ≤ t ≤ f. Therefore according to the definition for pθ(f, r) in Eq. (4), pθ(f, r) can be expressed in the following equivalent form: pθ(f, r) = 1 f f t=1 t x=1 pα(t, x, r). Then, as we have t x=1 pα(t, x, r) = pi(r) · t x=1 Cx−1 t−1 (pi(r))x−1(1 − pi(r))t−x = pi(r) · [pi(r) + (1 − pi(r))]t−1 = pi(r), thus pθ(f, r) = 1 f f t=1 pi(r) = pi(r). The theorem gets proved. The Query message actually acts as the role of the first QueryRep message, especially when f = 1 the unique Query message takes the role of the QueryRep message. Thus the first phase and the second phase are not independent to each other. However, as long as the frame size f is large enough, we can assume that the first phase and the second phase are independent to each other. In this situation, given the number of unread tags, n, the expected number of tags successfully obtaining a slot inside the frame is n = n · pi(r) · pθ(f, r) = n · (pi(r))2. Note that after successfully receiving the Query message, tags randomly select the slots inside the frame with size f, using a uniform approach. Then due to the probabilistic loss of QueryRep messages, the actual slot t in which the tag replies is deferred to some extent over the original selected slot x. Since the original slot x is selected with uniform probability, then as indicated in Theorem 1’s proof, the probability for the tag ac￾tually replies in slot t is P(t) = t x=1 1 f · Pα(t, x, r) = pi(r) f . Since P(t) is the same for all slot t, it infers that the actual slot t in which the tag replies is uniformly distributed inside the frame. Therefore, if we do not consider the propagation loss for backscattering, then, according to the binomial distribution, the expected number of empty slots, single slots, and collision slots, n0, n1, nc, can be calculated as follows: ⎧ ⎪⎨ ⎪⎩ n0 = f · (1 − 1 f )n , n1 = n · (1 − 1 f )n −1, nc = f − n0 − n1. (5) We denote the above mentioned empty/single/collision slot as original empty/single/collision slot, which means This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the main Technical Program at IEEE INFOCOM 2010. Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore. Restrictions apply.