大规模动态RFID系统中针对热门标签类别的TOP-k查询协议

Translated title of the contribution: A TOP-k Query Protocol for Popular Tag Categories in Large-Scale Dynamic RFID Systems

Bing Xin Niu, Xiu Long Liu, Xin Xie, Ke Qiu Li, Jian Nong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

In dynamic multi-category RFID systems, the number of absent tags in a category can reflect the popularity of this tag category. Hence, it is of great importance to quickly and accurately pinpoint the k categories whose absent tags are the most, for the purpose of making proper marketing strategies. In practical RFID applications, tags are usually categorized into various categories according to the brands or manufacturers of the items that the tags are attached to. We consider a set of tags where each tag has a unique ID that consists of two fields: a category ID that specifies the category of the tag, and a member ID that identifies the tag within its category. Besides the multi-category property, RFID systems also have the dynamic property, e. g., the tagged items are frequently moved out of (or into) the system. This may entail that the set of tags in the current system is not consistent with that stored in the database on the back-end server side. We refer to the tags whose IDs are stored in database but are not present in the system as the absent tags. The number of absent tags in a category sometimes reflects the popularity of this category, e. g., the absent tags may be the sold tagged items in a market. The popular pareto principle states that, for many events, roughly 80% of the effects come from 20% of the causes. Hence, the most popular k categories whose absent tags are the most may determine the profit and loss of a retailer. This paper takes the first step to define the problem of TOP-k query for popular categories in dynamic multi-category RFID systems, and proposes the EPC C1G2-compliant fast query protocol called Hot TOP-k Query (HTKQ). Its basic idea is to let the reader monitor the communication process that the present tags in the current system participate in the framed slotted Aloha protocol, and record each slot state to obtain an actual frame vector. Then, we virtually execute the framed slotted Aloha protocol on the tag IDs in each category that is stored in the back-end server to obtain a virtual frame vector for each category. By comparing the difference between these two vectors, this paper uses statistical methods to estimate the number of absent tags in each category. As the frames go on, the variance in the average estimate will decrease. Moreover, HTKQ can delete the categories whose absent tag numbers are obviously small, and are very likely not in the TOP-k set. Thus, the valuable communication resource can be left for the categories that are more likely in TOP-k set. The HTKQ protocol does not terminate until the number of remaining tags is equal to k, and these categories have met the predefined estimation accuracy. This paper proposes sufficient theoretical analysis to guarantee the query accuracy, meanwhile optimizing the involved parameters to minimize the time cost of the proposed protocol. The extensive simulation results reveal that, the proposed HTKQ protocol can ensure the predefined query accuracy under various conditions, and outperforms the existing protocols by 80% at most in terms of time-efficiency when there are a large number of categories in the system.

Translated title of the contributionA TOP-k Query Protocol for Popular Tag Categories in Large-Scale Dynamic RFID Systems
Original languageChinese
Pages (from-to)266-281
Number of pages16
JournalJisuanji Xuebao/Chinese Journal of Computers
Volume42
Issue number2
DOIs
Publication statusPublished - 1 Feb 2019

Keywords

  • Absent tags
  • Cardinality estimation
  • Dynamic systems
  • Radio Frequency Identification
  • Time-efficiency
  • TOP-k query

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design

Cite this