2013 Proceedings IEEE INFOCOM view,all slots are shared by all groups uniformly at random Clearly,for tags of group g,the indices of their (through independent hashing),which means the noise is selected slots in the frame can only be H(gid F(ri,0)), uniformly distributed in the whole time frame.Such uniform H(gid F(ri,1))....,H(gidF(ri,m-1)).These slots noise is measurable.To estimate the size of a group,we will or more precisely,the bits converted from these slots,form use the logical bitmap of that group.but subtract the noise the logical bitmap of g.denoted as LB(g). that other groups introduce into the bitmap. Note that the value of H(tid)mod m gives the index of To further improve performance,the reader repeats the the corresponding bit in the logical bitmap.For example,if above approach multiple times to gather multiple independent a tag selects the H(gidF(ri,H(tid)mod m))th slot to logical bitmaps for each group,and estimation based on transmit,the (H(tid)mod m)th bit in the logical bitmap multiple logical bitmaps reduces the variance of the result. will be set to '1'.Essentially,we embed the logical bitmaps of all in Bi. B.Overview Our threshold-based classification(TBC)protocol consists D.Report Phase of three phases:the parameter-precomputing phase,the frame phase,and the report phase.The parameter-precomputing After w pollings,the reader obtains w bitmaps,Bi, phase computes system parameters for optimal performance l≤i≤w.It sends the bitmaps to an offline data of the protocol.Using these parameters,the frame phase processing module.There,the logical bitmaps of each group makes w(1)polling requests,each of them followed by is extracted.For an arbitrary group g,we extract a logical a time frame,during which tags of all groups transmit in bitmap LB;(g)from B;as follows:Set the jth bit of LB;(g) to be the H(gid F(ri,j))th bit in Bi,i.e..LB;(g)i]= selected slots.The reader converts each time frame into a bitmap,from which logical bitmaps are extracted.Using B[H(gd⊕F(r,j)l,where1≤i≤wand0≤j≤m-l. these logical bitmaps,the report phase employs the Maximum Let z;be the number of zeros observed in LBi(g).Let Likelihood Estimation (MLE)method to report the above- n be the total number of tags in the system and k be the threshold groups. actual population of group g.Below we derive the formula There are three system parameters:1)w is the number of to compute an estimate k of the population. pollings (or time frames),2)f is the size of each time frame, Consider the ith polling in the frame phase and an arbitrary i.e.,the number of slots in a frame or the number of bits in bit b in LBi(g).A tag in group g has a probability of to the bitmap that the frame is converted to,and 3)m is the select this bit and set it to'1'because the tag only sets one of size of each logical bitmap.Clearly,m<f.The execution the m bits in the logical bitmap of g.Any tag in other groups time of TBC is dominated by the w time frames,which have has a probability of to set this bit to '1'due to dynamic wx f time slots in total.We want to find the optimal values slot sharing across the whole frame.Hence,the probability for w,f and m such that the constraints in (1)are met and for b to remain zero is the value of w x f is minimized. g=0-7--a (2) Before presenting the parameter-precomputing phase for how the optimal system parameters are computed,we will Hence,the likelihood function L;for us to observe z;bits first describe the frame phase and the report phase because of zeros in LBi(g)is deriving the formulas for optimal system parameters relies on the knowledge of how the frame phase works. =a--1- C.Frame Phase The frame phase is composed of w pollings,which are x0-1--1-m (3) performed in a similar way:In the ith polling(where 1 i<w),an RFID reader first broadcasts a request message, The likelihood function L for us to observe all zi values, including a random number ri and the system parameters, 1≤i≤w,in the w logical bitmaps is L=Π1La.That f and m.The request message also serves the purpose of 1s, synchronizing the clocks of all tags for starting a time frame of f slots right after the request. =Π[-子-1-r Consider an arbitrary tag t in an arbitrary group g.The tag computes a hash value H(gid F(ri,H(tid)mod m)) as the index of the time slot selected for its transmission, ×a-1-n-a-aym-] (4) where H()is a hash function whose range is [0,f-1], gid is the tag's group ID,tid is the tag's member ID,and We want to find an estimate k that maximizes L,namely, F(z,y)is a pseudo-random number function that takes two input parameters:z and y.F(r,y)uses x as the seed, =arg max (5) generates y random numbers,and outputs the yth number. k The transmission from all participating tags forms a bitmap Since the maximum is not affected by monotone Bi. transformations,we take the logarithm of both sides 894view, all slots are shared by all groups uniformly at random (through independent hashing), which means the noise is uniformly distributed in the whole time frame. Such uniform noise is measurable. To estimate the size of a group, we will use the logical bitmap of that group, but subtract the noise that other groups introduce into the bitmap. To further improve performance, the reader repeats the above approach multiple times to gather multiple independent logical bitmaps for each group, and estimation based on multiple logical bitmaps reduces the variance of the result. B. Overview Our threshold-based classification (TBC) protocol consists of three phases: the parameter-precomputing phase, the frame phase, and the report phase. The parameter-precomputing phase computes system parameters for optimal performance of the protocol. Using these parameters, the frame phase makes w(≥ 1) polling requests, each of them followed by a time frame, during which tags of all groups transmit in selected slots. The reader converts each time frame into a bitmap, from which logical bitmaps are extracted. Using these logical bitmaps, the report phase employs the Maximum Likelihood Estimation (MLE) method to report the above￾threshold groups. There are three system parameters: 1) w is the number of pollings (or time frames), 2) f is the size of each time frame, i.e., the number of slots in a frame or the number of bits in the bitmap that the frame is converted to, and 3) m is the size of each logical bitmap. Clearly, m<f. The execution time of TBC is dominated by the w time frames, which have w × f time slots in total. We want to find the optimal values for w, f and m such that the constraints in (1) are met and the value of w × f is minimized. Before presenting the parameter-precomputing phase for how the optimal system parameters are computed, we will first describe the frame phase and the report phase because deriving the formulas for optimal system parameters relies on the knowledge of how the frame phase works. C. Frame Phase The frame phase is composed of w pollings, which are performed in a similar way: In the ith polling (where 1 ≤ i ≤ w), an RFID reader first broadcasts a request message, including a random number ri and the system parameters, f and m. The request message also serves the purpose of synchronizing the clocks of all tags for starting a time frame of f slots right after the request. Consider an arbitrary tag t in an arbitrary group g. The tag computes a hash value H(gid F(ri, H(tid) mod m)) as the index of the time slot selected for its transmission, where H(·) is a hash function whose range is [0, f − 1], gid is the tag’s group ID, tid is the tag’s member ID, and F(x, y) is a pseudo-random number function that takes two input parameters: x and y. F(x, y) uses x as the seed, generates y random numbers, and outputs the yth number. The transmission from all participating tags forms a bitmap Bi. Clearly, for tags of group g, the indices of their selected slots in the frame can only be H(gid F(ri, 0)), H(gid F(ri, 1)), ... , H(gid F(ri, m − 1)). These slots or more precisely, the bits converted from these slots, form the logical bitmap of g, denoted as LBi(g). Note that the value of H(tid) mod m gives the index of the corresponding bit in the logical bitmap. For example, if a tag selects the H(gid F(ri, H(tid) mod m))th slot to transmit, the (H(tid) mod m)th bit in the logical bitmap will be set to ‘1’. Essentially, we embed the logical bitmaps of all in Bi. D. Report Phase After w pollings, the reader obtains w bitmaps, Bi, 1 ≤ i ≤ w. It sends the bitmaps to an offline data processing module. There, the logical bitmaps of each group is extracted. For an arbitrary group g, we extract a logical bitmap LBi(g) from Bi as follows: Set the jth bit of LBi(g) to be the H(gid F(ri, j))th bit in Bi, i.e., LBi(g)[j] = Bi[H(gid F(ri, j))], where 1 ≤ i ≤ w and 0 ≤ j ≤ m−1. Let xi be the number of zeros observed in LBi(g). Let n be the total number of tags in the system and k be the actual population of group g. Below we derive the formula to compute an estimate ˆ k of the population. Consider the ith polling in the frame phase and an arbitrary bit b in LBi(g). A tag in group g has a probability of 1 m to select this bit and set it to ‘1’ because the tag only sets one of the m bits in the logical bitmap of g. Any tag in other groups has a probability of 1 f to set this bit to ‘1’ due to dynamic slot sharing across the whole frame. Hence, the probability for b to remain zero is q = (1 − 1 f ) n−k(1 − 1 m) k. (2) Hence, the likelihood function Li for us to observe xi bits of zeros in LBi(g) is Li = ((1 − 1 f ) n−k(1 − 1 m) k) xi × (1 − (1 − 1 f ) n−k(1 − 1 m) k) m−xi . (3) The likelihood function L for us to observe all xi values, 1 ≤ i ≤ w, in the w logical bitmaps is L = w i=1 Li. That is, L = w j=1  ((1 − 1 f ) n−k(1 − 1 m) k) xi × (1 − (1 − 1 f ) n−k(1 − 1 m) k) m−xi  . (4) We want to find an estimate ˆ k that maximizes L, namely, ˆ k = arg max{L} k . (5) Since the maximum is not affected by monotone transformations, we take the logarithm of both sides 2013 Proceedings IEEE INFOCOM 894