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. no/one/multiple tag(s)select(s)this slot and is (are)ready to follows: backscatter the RN/6 message to the reader.Specifically,we n(n,r,f)=n0+1·(1-pt(r) define s-collision slot as the slot which is selected by s tags. +f·∑2P(s)pm(s,r, 3)Backscatter the RN16 message:If a tag has received (7) enough QueryRep messages for its selected slot,then it n(m,rf)=m1p(r)+f·∑2P(s)p2(s,r, backscatters the RN/6 message to the reader,and the reader n2(m,n,f)=f·∑2P(s)ps(s,r): is able to detect and resolve the backscattered message with 4)Backscatter the ID message:When a tag successfully probability p(r).According to the slotted Aloha protocol, transmits a RN16 message to the reader without collisions, due to the probabilistic loss of the RN/6 message,for some the reader will transmit a ACK message to the tag,and then original single slots it is possible for the reader unable to detect the tag will backscatter its ID message to the reader.The above the RN/6 messages,thus transferring those original single slots process is successfully completed with a probability of pi(r). into actual empty slots.For the original s-collision slots,s pt(r),otherwise the tag will keep active for the next round. tags try to send the RN/6 message simultaneously.Due to the Therefore the number of tags that successfully read within the probabilistic loss of the message,when all s messages are lost frame is n(n,T,f)·pi(r)·pt(r) with a probability of pi(s,r),it is possible that the reader is unable to detect any of the messages,thus transferring this C.Obtain the propagation and backscatter parameters slot into actual empty slot;similarly when s-1 messages In the above subsection,we have built a probabilistic model are lost with a probability of pa(s,r),it is possible for the for the RFID tag identification.Recall that we utilize two reader to detect only one of the messages,thus transferring parameters pi(r)and pt(r)to formalize the probabilistic this slot into actual single slot;otherwise,this slot remains model,thus obtaining these two important parameters is a as a collision slot with a probability of pa(s,r).The above prerequisite to the probabilistic model.However,it is rather probabilities,pi(s,r),p2(s,r),and pa(s,r),are calculated as difficult to directly compute these two parameters by using follows: realistic physical layer parameters obtained from sophisticated instruments [3].Here we claim that by using one reader and p1(s,r）=(1-p(r) one tag,it is enough to estimate pi(r)and pt(r)from the p2(s,r）=s·(1-p(r)-1·p(r following experiment results.We separate the reader and the (6) p3(s,T)=1-P1-P2 tag with a distance of r.First we set the frame size f to 1 =1-(1-p4(r)°-s·(1-p(r)s-1·p(r) for the reader,and let the reader issue m rounds to read the same tag and check the number of successful responses m. Suppose the actual numbers of empty slots,single slots and Thus we get the read ratio asr.Secondly we set collision slots are no,n,n.Fig.3 shows the translation the frame size f to a large enough value,say f=100,and relationship from original empty/singel/collision slots to actual also let the reader issue m2 rounds to read the same tag and empty/singel/collision slots. check the number of successful responses m2.Thus we get the read ratio as rtf(r)=m2. Translation Probability According to the probabilistic model,for the case when frame size f=1,the Ouery message is successfully detected Original Empty Slots 100% Actual Empty Slots and resolved by the tag with probability of pi(r),and the tag 1-pt successfully backscatters the RN/6 message with probability of pt(r).After that the reader successfully responds the ACK Original Single Slots -pt(r) Actual Single Slots message with probability of pi(r),and the tag successfully pi(s.r) backscatters the ID message with probability of pt(r).So P25,j rti(r)=(pi(r))2.(pt(r))2.For the case when frame size Original s-Collis on p3(s.r) Actual Collision Slot起 f is set to a large enough value,first the Query message is sots(5-1) successfully detected and resolved by the tag with probability of pi(r),then the tag monitors enough QueryRep messages Fig.3.Relationship for slot transformation for its selected slot with probability pe(f,r).It has been proved that pe(f,r)=pi(r).Then the tag successfully Suppose n'tags are able to successfully obtain a slot in the backscatters the RN/6 message with probability of pt(r).After frame of size f,then the proportion for the original s-collision that the reader successfully responds the ACK message with slots P(s)inside the frame is probability of pi(r),and the tag successfully backscatters the ID message with probability of p(r).Hence rtf(r)= (p((pa().Therefore we can derive that p(r P(s)=C· /(rt(1)3 and p(r).We can store the values of pa(r)and P(r)at various distance r.In our probabilistic model,for Thus given f,n'and pt(r),we can calculate no,n1,n as simplification of the problem we do not consider the impact Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply.no/one/multiple tag(s) select(s) this slot and is (are) ready to backscatter the RN16 message to the reader. Specifically, we define s-collision slot as the slot which is selected by s tags. 3) Backscatter the RN16 message: If a tag has received enough QueryRep messages for its selected slot, then it backscatters the RN16 message to the reader, and the reader is able to detect and resolve the backscattered message with probability pt(r). According to the slotted Aloha protocol, due to the probabilistic loss of the RN16 message, for some original single slots it is possible for the reader unable to detect the RN16 messages, thus transferring those original single slots into actual empty slots. For the original s-collision slots, s tags try to send the RN16 message simultaneously. Due to the probabilistic loss of the message, when all s messages are lost with a probability of p1(s, r), it is possible that the reader is unable to detect any of the messages, thus transferring this slot into actual empty slot; similarly when s − 1 messages are lost with a probability of p2(s, r), it is possible for the reader to detect only one of the messages, thus transferring this slot into actual single slot; otherwise, this slot remains as a collision slot with a probability of p3(s, r). The above probabilities, p1(s, r), p2(s, r), and p3(s, r), are calculated as follows: ⎧ ⎪⎪⎨ ⎪⎪⎩ p1(s, r) = (1 − pt(r))s p2(s, r) = s · (1 − pt(r))s−1 · pt(r) p3(s, r)=1 − p1 − p2 = 1 − (1 − pt(r))s − s · (1 − pt(r))s−1 · pt(r) (6) Suppose the actual numbers of empty slots, single slots and collision slots are n 0, n 1, n c. Fig. 3 shows the translation relationship from original empty/singel/collision slots to actual empty/singel/collision slots. Fig. 3. Relationship for slot transformation Suppose n tags are able to successfully obtain a slot in the frame of size f, then the proportion for the original s-collision slots P(s) inside the frame is P(s) = Cs n · ( 1 f ) s(1 − 1 f ) n −s. Thus given f,n and pt(r), we can calculate n 0, n 1, n c as follows: ⎧ ⎪⎪⎪⎨ ⎪⎪⎪⎩ n 0(n, r, f) = n0 + n1 · (1 − pt(r)) +f · n s=2 P(s) · p1(s, r), n 1(n, r, f) = n1 · pt(r) + f · n s=2 P(s) · p2(s, r), n c(n, r, f) = f · n s=2 P(s) · p3(s, r). (7) 4) Backscatter the ID message: When a tag successfully transmits a RN16 message to the reader without collisions, the reader will transmit a ACK message to the tag, and then the tag will backscatter its ID message to the reader. The above process is successfully completed with a probability of pi(r)· pt(r), otherwise the tag will keep active for the next round. Therefore the number of tags that successfully read within the frame is n 1(n, r, f) · pi(r) · pt(r). C. Obtain the propagation and backscatter parameters In the above subsection, we have built a probabilistic model for the RFID tag identification. Recall that we utilize two parameters pi(r) and pt(r) to formalize the probabilistic model, thus obtaining these two important parameters is a prerequisite to the probabilistic model. However, it is rather difficult to directly compute these two parameters by using realistic physical layer parameters obtained from sophisticated instruments [3]. Here we claim that by using one reader and one tag, it is enough to estimate pi(r) and pt(r) from the following experiment results. We separate the reader and the tag with a distance of r. First we set the frame size f to 1 for the reader, and let the reader issue m1 rounds to read the same tag and check the number of successful responses m 1. Thus we get the read ratio as rt1(r) = m 1 m1 . Secondly we set the frame size f to a large enough value, say f = 100, and also let the reader issue m2 rounds to read the same tag and check the number of successful responses m 2. Thus we get the read ratio as rtf (r) = m 2 m2 . According to the probabilistic model, for the case when frame size f = 1, the Query message is successfully detected and resolved by the tag with probability of pi(r), and the tag successfully backscatters the RN16 message with probability of pt(r). After that the reader successfully responds the ACK message with probability of pi(r), and the tag successfully backscatters the ID message with probability of pt(r). So rt1(r)=(pi(r))2 · (pt(r))2. For the case when frame size f is set to a large enough value, first the Query message is successfully detected and resolved by the tag with probability of pi(r), then the tag monitors enough QueryRep messages for its selected slot with probability pθ(f, r). It has been proved that pθ(f, r) = pi(r). Then the tag successfully backscatters the RN16 message with probability of pt(r). After that the reader successfully responds the ACK message with probability of pi(r), and the tag successfully backscatters the ID message with probability of pt(r). Hence rtf (r) = (pi(r))3 ·(pt(r))2. Therefore we can derive that pi(r) = rt(f) rt(1) and pt(r) = (rt(1))3 (rt(f))2 . We can store the values of pi(r) and pt(r) at various distance r. In our probabilistic model, for simplification of the problem we do not consider the impact 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.