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

A TOP-k Query Protocol for Popular Tag Categories in Large-Scale Dynamic RFID Systems

作　　者：牛炳鑫 刘秀龙 谢鑫 李克秋[1] 曹建农[2] NIU Bing-Xin;LIU Xiu-Long;XIE Xin;LI Ke - Qiu;CAO Jian-Nong(School of Computer Science and Technology, Dalian University of Technology, Dalian 116023;Department of Computing, Hong Kong Polytechnic University, Hong Kong 999077)

机构地区：[1]大连理工大学计算机科学与技术学院,大连116023 [2]香港理工大学电子计算学系,香港999077

出　　处：《计算机学报》2019年第2期266-281,共16页Chinese Journal of Computers

基　　金：国家自然科学基金重点项目(61432002)资助~~

摘　　要：在动态多类别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 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 cat

关 键 词：射频识别 动态系统 缺失标签 数量估计 TOP-K查询 时间效率 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]