Top-k Queries for Categorized RFID Systems

For categorized RFID systems, this paper studies the practically important problem of top-k queries, which is to find the top-k smallest and (or) the top-k largest categories, as well as the sizes of such categories. In this paper, we propose a Top-k Query (TKQ) protocol and two supplementary techniques called segmented perfect hashing (SPH) and switching to framed slotted aloha (STA) for optimizing TKQ. First, TKQ lets each tag choose a time slot to respond to the reader with a single-one geometric string using the ON-OFF Keying modulation. TKQ leverages the length of continuous leading 1 s in the combined signal to estimate the corresponding category size. TKQ can quickly eliminate most categories whose sizes are significantly different from the top-k boundary, and only needs to perform accurate estimation on a limited number of categories that may be within the top-k set. We conduct rigorous analysis to guarantee the predefined accuracy constraints on the query results. Second, to alleviate the low frame utilization of TKQ, we propose the SPH scheme, which improves its average frame utilization from 36.8% to nearly 100% by establishing a bijective mapping between tag categories and slots. To minimize the overall time cost, we optimize the key parameter that trades off between communication cost and computation cost. Third, we observed from the simulation traces that TKQ+SPH pays most execution time on querying a small number of remaining categories whose sizes are close to the top-k boundary, which sometimes even exceeds the time cost for precisely identifying these remaining tags. Motivated by this observation, we propose the STA scheme to dynamically determine when we should terminate TKQ+SPH and switch to use FSA to finish the rest of top-k query. Experimental results show that TKQ+SPH+STA not only achieves the required accuracy constraints, but also achieves several times faster speed than the existing protocols.