Probabilistic Optimal Tree Hopping for RFID Identification
Probabilistic Optimal Tree Hopping for RFID Identification
复制标题
DOI：
10.1145/2465529.2465549
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
Muhammad Shahzad;A. Liu
中科院分区：
文献类型：
--
作者：
Muhammad Shahzad;A. Liu
射频识别（RFID）系统广泛用于各种应用，例如供应链管理、库存控制和对象跟踪。识别给定标签群中的RFID标签是RFID系统中最基本的操作。虽然树行走（TW）协议已成为工业标准，用于识别RFID标签，很少有人知道这个协议的数学性质，只有一些ad hoc算法存在优化it.In本文中，我们首先分析模型的TW协议，然后使用该模型，提出了树跳跃（TH）协议，优化TW在理论和实践。TH的关键新奇在于将标签识别公式化为优化问题，并找到最佳解决方案，以确保根据要求的最小平均查询次数或识别时间。有了这个坚实的理论基础，对于从100到100 K标签的不同标签群体大小，TH在每个标签的查询总数、每个标签的总识别时间和每个标签的平均响应数的度量上分别显著优于最佳的现有标签识别协议平均40%、59%和67%。当标签ID在ID空间中非均匀分布时，分别为50%、10%和30%。
Radio frequency identification (RFID) systems are widely used in various applications such as supply chain management, inventory control, and object tracking. Identifying RFID tags in a given tag population is the most fundamental operation in RFID systems. While the Tree Walking (TW) protocol has become the industrial standard for identifying RFID tags, little is known about the mathematical nature of this protocol, and only some ad hoc heuristics exist for optimizing it. In this paper, first we analytically model the TW protocol, and then using that model, propose the Tree Hopping (TH) protocol that optimizes TW both theoretically and practically. The key novelty of TH is to formulate tag identification as an optimization problem and find the optimal solution that ensures the minimal average number of queries or identification time as per the requirement. With this solid theoretical underpinning, for different tag population sizes ranging from 100 to 100 K tags, TH significantly outperforms the best prior tag identification protocols on the metrics of the total number of queries per tag, the total identification time per tag, and the average number of responses per tag by an average of 40%, 59%, and 67%, respectively, when tag IDs are nonuniformly distributed in the ID space, and of 50%, 10%, and 30%, respectively, when tag IDs are uniformly distributed.