IEEE/ACM TRANSACTIONS ON NETWORKING 8 M bits is identified.Thus,the whole procedure totally contains n Mbits Truncated bits frames,n long slots,and ne ln(n)-n short slots.As shown in Fig.2,a long time slot in which only a single tag intends 5 6 15 to transmit is EPC.is reserved for the transmissions of a 101004 -Moving forward QueryAdjust,an RN16,an ACK,and an EPC:a short time 1112131415， slot in which no tags respond or multiple tags'signals are collided,is reserved for the transmissions of a QueryAdjust Fig.11:The design of modulo.Suppose the optimal size of the and an RN16.Thus,the totally time overhead taken by Q- BF is 11,the reader builds 2=16 bit BF and moves the last Adaptive,denoted by Co-Adaptive,can be computed as follows: 5 bits to align with the first five. Co-Adaptive nTL+(ne ln n-n)T's +nTDelay TL TQuery TRN16 TAck TEPC (4) -th intercepted inventory.In other words,if a tag is supposed Ts=TQueryAdjust TRN16 to be hashed into the bit greater than or equal to M,then the tag is moved to reply at (m mod M)th bit-inventory.As where TL and Ts are the sizes of a long time slot and a short illustrated in Fig.11,the modulo moves the replies at the time slot respectively.According to our prior study [45],the bits equal to or greater than M ahead to align with the first commercial readers require to reserve Tpelay seconds in the bits.Correspondingly,the question of presence turns to: beginning of each frame for some pre-arranged tasks,such as synchronization,clearing tag states,adjustment of frame Problem 3.Is there any tag whose sub-bitstring E[r1,r1+). length,etc.Since n frames are required,the total extra time ...or E [rk,rK+l)in its MemBank3 is equal to m,m+M, consumption is nTDely.The other time symbols Txxx denotes m+2i,.,orm+l岩」？ the time consumed on the corresponding reader commands or Therefore,for the mth bit,the reader initiates an intercepted the tag reply.For example,Touery denotes the time cost for inventory,which contains multiple Selects as follows: transmitting a reader command of Query.Finally,the total overhead taken by the Q-Adaptive is given by S(r1,l;m),S(r2;1,m),...:S(rk:l,m) CQ-Adaptive(n)=n(TDelay TQuery +TRNI6+TAck TErc) +(neln n-n)(TQueryAdjust +TRN16) S(r1,l,m+[ Cleary,the overhead is only related to the total number of tags It is worthing noting the modulo operation would increase (i.e.,n)in the scanning field. the number of tags hashed into the head bits,breaking the randomness of BF.If the upper-layer application requires a B.Overhead Analysis on TagMap strong randomness,a good way is to move truncated bit (i.e., Unlike the Q-Adaptive,all time slots in TagMap are equal indexes >M)forward to a random index less than M while the reader labels the mapping between the tags and bits so the in size.The collection procedure totally contains M slots,each of which is reserved for the transmissions of K Selects,a application can predicate the hashing. Query and an RN16.Thus,the total time overhead taken by TagMap.denoted by CTagMap.can be computed as follows: V.ANALYSIS In this section,we give a comprehensive theoretical analysis CragMap M(K Tselect +TQuery TRN16) on the performance of TagMap compared with the traditional M=「nlog2e·log2(1/e)1≈[1.44nlog2(1/e)l (5) Q-Adaptive protocol K=ln2·(log2e·log2(1/e)l≈「0.99811og2(1/e)l Substituting M and K into CragMap,the above equation can A.Overhead Analysis on O-Adaptive Protocol be overwritten as follows: As aforementioned,the current mainstream RFID readers CTagMap(n,e)=[1.44nlog2(1/e)1([0.998110g2(1/e)1.Tselect use the Q-Adaptive protocol to collect all tags'EPCs.The +TQuery TRN16) Q-Adaptive is a variant of framed slotted ALOAH (FSA) Apart from the number of tags,the overhead of TagMap is protocol.Unlike the traditional FSA,it attempts to adjust the also related to the tolerance (i.e.,E). frame length adaptively to maintain a high probability that a tag is successfully identified in a frame.We have already given the theoretical analysis of Q-Adaptive in our prior work [45]. C.Overhead Comparison For clarity,we directly present the result as below. According to Gen2,we have the following estimated pa- rameter settings: Lemma 3.The protocol of Q-Adaptive requires about neln(n)time slots to collect n tags'EPCs in an optimal Tselect =91 bits,TQuery =37 bits,TQueryAdjust =15 bits condition. TRN16 =22 bits,TAck 25 bits,TEPC 134 bits The proof of the above lemma can be referred to our prior It is worth noting that:(1)the bit rates in the uplink (Tag- work [45].Specifically,keeping the optimal frame length,Reader)and downlink (Reader-Tag)are not exactly same. the protocol must start a new frame anytime when a tag Both are determined by the user settings.For the sake ofIEEE/ACM TRANSACTIONS ON NETWORKING 8 0 1 0 0 1 0 0 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 0 1 0 11 12 13 14 1 0 1 0 0 11 12 13 14 15 0 15 Moving forward Truncated bits M bits M c bits Fig. 11: The design of modulo. Suppose the optimal size of the BF is 11, the reader builds 2 dlog2 11e = 16 bit BF and moves the last 5 bits to align with the first five. -th intercepted inventory. In other words, if a tag is supposed to be hashed into the bit greater than or equal to Mc, then the tag is moved to reply at (m mod M) th bit-inventory. As illustrated in Fig. 11, the modulo moves the replies at the bits equal to or greater than Mc ahead to align with the first bits. Correspondingly, the question of presence turns to: Problem 3. Is there any tag whose sub-bitstring ∈ [r1, r1+l), . . . , or ∈ [rK, rK +l) in its MemBank3 is equal to m, m+Mc, m + 2Mc, . . . , or m + b M MccMc? Therefore, for the mth bit, the reader initiates an intercepted inventory, which contains multiple Selects as follows: S(r1, l, m), S(r2, l, m), . . . , S(rK, l, m) . . . . . . S(r1, l, m + b M Mc cMc), S(r2, l, m + b M Mc cMc), . . . , S(rK, l, m + b M Mc cMc) It is worthing noting the modulo operation would increase the number of tags hashed into the head bits, breaking the randomness of BF. If the upper-layer application requires a strong randomness, a good way is to move truncated bit (i.e., indexes ≥ Mc) forward to a random index less than Mc while the reader labels the mapping between the tags and bits so the application can predicate the hashing. V. ANALYSIS In this section, we give a comprehensive theoretical analysis on the performance of TagMap compared with the traditional Q-Adaptive protocol. A. Overhead Analysis on Q-Adaptive Protocol As aforementioned, the current mainstream RFID readers use the Q-Adaptive protocol to collect all tags’ EPCs. The Q-Adaptive is a variant of framed slotted ALOAH (FSA) protocol. Unlike the traditional FSA, it attempts to adjust the frame length adaptively to maintain a high probability that a tag is successfully identified in a frame. We have already given the theoretical analysis of Q-Adaptive in our prior work [45]. For clarity, we directly present the result as below. Lemma 3. The protocol of Q-Adaptive requires about ne ln(n) time slots to collect n tags’ EPCs in an optimal condition. The proof of the above lemma can be referred to our prior work [45]. Specifically, keeping the optimal frame length, the protocol must start a new frame anytime when a tag is identified. Thus, the whole procedure totally contains n frames, n long slots, and ne ln(n) − n short slots. As shown in Fig. 2, a long time slot in which only a single tag intends to transmit is EPC, is reserved for the transmissions of a QueryAdjust, an RN16, an ACK, and an EPC; a short time slot in which no tags respond or multiple tags’ signals are collided, is reserved for the transmissions of a QueryAdjust and an RN16. Thus, the totally time overhead taken by Q￾Adaptive, denoted by CQ-Adaptive, can be computed as follows:    CQ-Adaptive = nTL + (ne ln n − n)TS + nTDelay TL = TQuery + TRN16 + TAck + TEPC TS = TQueryAdjust + TRN16 (4) where TL and TS are the sizes of a long time slot and a short time slot respectively. According to our prior study [45], the commercial readers require to reserve TDelay seconds in the beginning of each frame for some pre-arranged tasks, such as synchronization, clearing tag states, adjustment of frame length, etc. Since n frames are required, the total extra time consumption is nTDelay. The other time symbols TXXX denotes the time consumed on the corresponding reader commands or the tag reply. For example, TQuery denotes the time cost for transmitting a reader command of Query. Finally, the total overhead taken by the Q-Adaptive is given by CQ-Adaptive(n) = n(TDelay + TQuery + TRN16 + TAck + TEPC) + (ne ln n − n)(TQueryAdjust + TRN16) Cleary, the overhead is only related to the total number of tags (i.e., n) in the scanning field. B. Overhead Analysis on TagMap Unlike the Q-Adaptive, all time slots in TagMap are equal in size. The collection procedure totally contains M slots, each of which is reserved for the transmissions of K Selects, a Query and an RN16. Thus, the total time overhead taken by TagMap, denoted by CTagMap, can be computed as follows:    CTagMap = M(K · TSelect + TQuery + TRN16) M = dn log2 e · log2 (1/ε)e ≈ d1.44n log2 (1/ε)e K = dln 2 · (log2 e · log2 (1/ε))e ≈ d0.9981 log2 (1/ε)e (5) Substituting M and K into CTagMap, the above equation can be overwritten as follows: CTagMap(n, ε) = d1.44n log2 (1/ε)e(d0.9981 log2 (1/ε)e · TSelect + TQuery + TRN16) Apart from the number of tags, the overhead of TagMap is also related to the tolerance (i.e., ε). C. Overhead Comparison According to Gen2, we have the following estimated pa￾rameter settings: TSelect = 91 bits, TQuery = 37 bits, TQueryAdjust = 15 bits TRN16 = 22 bits, TAck = 25 bits, TEPC = 134 bits It is worth noting that: (1) the bit rates in the uplink (Tag→ Reader) and downlink (Reader→Tag) are not exactly same. Both are determined by the user settings. For the sake of