Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/75776
Title: Top-k queries for categorized RFID systems
Authors: Liu, XL 
Li, KQ
Guo, S 
Liu, AX
Li, P
Wang, K 
Wu, J
Keywords: RFID
Categorized tags
Estimation
Top-k
Issue Date: 2017
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE/ACM transactions on networking, 2017, v. 25, no. 5, p. 2587-2600 How to cite?
Journal: IEEE/ACM transactions on networking 
Abstract: 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.
URI: http://hdl.handle.net/10397/75776
ISSN: 1063-6692
EISSN: 1558-2566
DOI: 10.1109/TNET.2017.2722480
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

4
Last Week
0
Last month
Citations as of Nov 12, 2018

WEB OF SCIENCETM
Citations

3
Last Week
2
Last month
Citations as of Nov 12, 2018

Page view(s)

21
Last Week
5
Last month
Citations as of Nov 11, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.