摘要：
在动态多类别RFID(Radio Frequency Identification)系统中,某类标签的缺失数量能够反映该类别的"热门"程度.因此,如何快速准确地找出缺失数量最多的k类标签对制定合理的营销策略具有重要意义.为此,该文首次定义了动态多类别RFID系统中针对热门标签类别TOP-k查询问题,并提出了符合EPC C1G2标准的快速查询协议Hot TOP-k Query(HTKQ).其核心思想是,先用阅读器监听当前系统中所有标签参与帧时隙阿罗哈协议的过程,并记录每个时隙的状态,从而获得真实时隙帧向量;然后在服务器端保存的每类标签ID集合上分别虚拟执行阿罗哈协议,为每个标签类别分别得到虚拟时隙帧向量.该文利用概率统计的方法,通过对比两类时隙帧的差异,分别估计每类标签的缺失数量.该文提出了大量理论分析,在保证查询结果准确性的同时优化参数使得算法时间代价最小.大量的仿真实验结果表明,该文提出的HTKQ协议能够在不同实验条件下满足预定的查询精度,并且当RFID系统中标签类别较多时,HTKQ协议的时间效率比现有协议可以提升80％.%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 asthe 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 C1 G2-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-kset.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.
