Algorithm 1 New send-and-reply protocol for the reader of the FNEB estimator is shown in Algorithm 3.The algorithm 1:if f is not a power of 2 then takes tmar,6 and e as inputs,where tmaz denotes the upper 2: f =2flog2f bound of tag population t.Initially,the reader computes pa- 3:end if rameters f,k,and n by inputs,and then applies the combined 4:a=0,b=f/2-1 send-and-reply protocol n rounds to obtain the average value of 5:Set the search range r [a,b]and random seed R X.denoted by Y.At last,the estimation t is calculated below: 6:for i=1 to log2 f do 7: Reader broadcasts r,f,and R,and listens in the forth- 1+Y coming slot for reply (only one slot) i=f.mn-y (1) 8: if the slot is EMPTY then 9 21=0 10: a=b+1,b=b+rl/2,and updates r 1 else Algorithm 3 FNEB estimator for static tag set 12: 21=1 b=(b-1)/2,and updates r INPUT:tmaz,6,and e 13: OUTPUT:t 14 end if 1:Compute the frame size f and waiting slots k 15:end for i6:ReturnX=∑ef(1-2)·2lo8ef-i 2:Compute the number of rounds n 3: for i =1 to n do 4: Generate a new random seed Ri Algorithm 2 New send-and-reply protocol for each tag 5: Broadcast (f,Ri)to all tags and wait their replies 1:Receive range r,f,and R from reader 6: Run the original send-and-reply protocol 2:Compute slot number sn=h(f.R,id) if receive reply before kth slot then 3:if sn is inside r then 8 Xi slot number of first reply -1 4: Reply immediately 9 else 5:else 10: Run the new send-and-reply protocol 6: Keep silent X;value returned by Algorithm 1 7:end if 12: end if 13:end for Frame Size=16 Empty Slots 14:Add all Xi and get the average Y=Xi/n L-0 15:Return fIn 1tY 3 4 In the next two subsections,we will explain why this algo- ④。5 rithm can achieve the desired accurate estimation and how to 16 0(6 07 compute parameters f,k,and n(lines 1 and 2 in Algorithm 3). 8 To ease understanding,we first present the mathematics behind 0 -10 the algorithm and how to pick parameter n.We then describe 11 12 how to determine f and k. 013 。15 14 B.Pick n 0101☐ Z3 The value of n directly determines the performance of our Fig.2.Illustration of our new send-and-reply protocol scheme.If n is too small,the estimated f cannot meet the de- sired accuracy.However,a large n will increase the estimation time.Next,we first present the theoretical underpinnings for Our combined send-and-reply protocol requires a slight mod- the FNEB algorithm,followed by the bounds for n that can ification to existing RFID tags.We add an optional bit mask satisfy the accuracy requirement. to indicate the search range r in each end slot command sent Given the frame size f,each tag has the probability to by the reader.If the parameter is set to a valid range,those select a specific slot in the frame.For t tags in total,the tags who pick a response slot inside the range will reply in probability of a certain slot to be empty (denoted as Po)is the forthcoming slot,no matter what value their slot counters Po=(1-).Since f is normally large,Po can be simplified are.If the parameter is set to null,the original send-and-reply to Poe-,where p=t.We call p the load factor.Let protocol is then used. the random variable X be the number of consecutive empty With the basic idea described above,the complete algorithm slots before the first non-empty slot in a frame.We then haveAlgorithm 1 New send-and-reply protocol for the reader 1: if f is not a power of 2 then 2: f = 2⌈log2 f⌉ 3: end if 4: a = 0, b = f /2 − 1 5: Set the search range r = [a, b] and random seed R 6: for i = 1 to log2 f do 7: Reader broadcasts r, f, and R, and listens in the forth￾coming slot for reply (only one slot) 8: if the slot is EMPTY then 9: zi = 0 10: a = b + 1, b = b + |r|/2, and updates r 11: else 12: zi = 1 13: b = (b − 1)/2, and updates r 14: end if 15: end for 16: Return X = Plog2 f i=1 (1 − zi) · 2 log2 f−i Algorithm 2 New send-and-reply protocol for each tag 1: Receive range r, f, and R from reader 2: Compute slot number sn = h(f, R, id) 3: if sn is inside r then 4: Reply immediately 5: else 6: Keep silent 7: end if z1 z2 z3 z4 [0~7] [0~3] 0 2 4 6 8 2 3 4 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 5 6 7 8 9 11 12 13 15 14 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 Empty Slots 0 1 0 1 10 Frame Size = 16 1 10 12 14 [12~13] [8~11] [8~9] [4~5] [0~1] Fig. 2. Illustration of our new send-and-reply protocol Our combined send-and-reply protocol requires a slight mod￾ification to existing RFID tags. We add an optional bit mask to indicate the search range r in each end slot command sent by the reader. If the parameter is set to a valid range, those tags who pick a response slot inside the range will reply in the forthcoming slot, no matter what value their slot counters are. If the parameter is set to null, the original send-and-reply protocol is then used. With the basic idea described above, the complete algorithm of the FNEB estimator is shown in Algorithm 3. The algorithm takes tmax, δ and ǫ as inputs, where tmax denotes the upper bound of tag population t. Initially, the reader computes pa￾rameters f, k, and n by inputs, and then applies the combined send-and-reply protocol n rounds to obtain the average value of X, denoted by Y . At last, the estimation t˜ is calculated below: t˜= f · ln 1 + Y Y (1) Algorithm 3 FNEB estimator for static tag set INPUT: tmax, δ, and ǫ OUTPUT: t˜ 1: Compute the frame size f and waiting slots k 2: Compute the number of rounds n 3: for i = 1 to n do 4: Generate a new random seed Ri 5: Broadcast (f, Ri) to all tags and wait their replies 6: Run the original send-and-reply protocol 7: if receive reply before kth slot then 8: Xi = slot number of first reply - 1 9: else 10: Run the new send-and-reply protocol 11: Xi = value returned by Algorithm 1 12: end if 13: end for 14: Add all Xi and get the average Y = Pn i=1 Xi/n 15: Return t˜= f ln 1+Y Y In the next two subsections, we will explain why this algo￾rithm can achieve the desired accurate estimation and how to compute parameters f, k, and n (lines 1 and 2 in Algorithm 3). To ease understanding, we first present the mathematics behind the algorithm and how to pick parameter n. We then describe how to determine f and k. B. Pick n The value of n directly determines the performance of our scheme. If n is too small, the estimated t˜ cannot meet the de￾sired accuracy. However, a large n will increase the estimation time. Next, we first present the theoretical underpinnings for the FNEB algorithm, followed by the bounds for n that can satisfy the accuracy requirement. Given the frame size f, each tag has the probability 1 f to select a specific slot in the frame. For t tags in total, the probability of a certain slot to be empty (denoted as P0) is P0 = (1− 1 f ) t . Since f is normally large, P0 can be simplified to P0 ≈ e −ρ , where ρ = t f . We call ρ the load factor. Let the random variable X be the number of consecutive empty slots before the first non-empty slot in a frame. We then have