On Efficient Tree-Based Tag Search in Large-Scale RFID Systems
On Efficient Tree-Based Tag Search in Large-Scale RFID Systems
复制标题
大型 RFID 系统中基于树的高效标签搜索
DOI：
10.1109/tnet.2018.2879979
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Wang Kehao
中科院分区：
文献类型：
--
作者：
Yu Jihong;Gong Wei;Liu Jiangchuan;Chen Lin;Wang Kehao
标签搜索，即在射频识别（RFID）系统中找到一组特定的标签，是库存管理等重要物联网应用中的关键服务。当系统规模较大且标签数量众多时，确定性搜索的成本可能会过高，因此人们提倡概率搜索，以寻求可靠性和时间效率之间的平衡。给定失效概率<inline-formula> < text -math notation="LaTeX"> $\frac {1}{\mathcal {O}(K)}$ </ text -math></inline-formula>，其中<inline-formula> < text -math notation="LaTeX"> $K$ </ text -math></inline-formula>是标签的数量，通过多轮哈希和验证，目前最先进的解决方案已经实现了<inline-formula> < text -math notation="LaTeX"> $\mathcal {O}(K \log K)$ </ text -math></inline-formula>的时间成本。然而，进一步的改进面临着每轮重复验证每个单独目标标签的关键瓶颈。在本文中，我们提出了一种高效的基于树的标签搜索（TTS），通过批量验证，它接近<inline-formula> < text -math notation="LaTeX"> $\mathcal {O}(K)$ </ text -math></inline-formula>。TTS的关键新颖之处在于将多个标签巧妙地散列到每个内部树节点中，并自适应地控制节点度。它采用自底向上的搜索方式，逐组验证标签，组数迅速减少。此外，我们设计了一种增强的标签搜索方案，称为TTS+，以克服不对称标签集大小对TTS时间效率的负面影响。TTS+首先使用过滤向量排除部分不合格的标记，并将缩小的标记集提供给TTS。我们推导了TTS中最优哈希码长度和节点度以适应哈希冲突，以及最优过滤向量大小以最小化TTS+的时间成本。通过理论分析和广泛的仿真，证明了TTS和TTS+优于最先进的解决方案。具体而言，作为尺度上的可靠性需求，TTS+的时间效率最高达到TTS的近2倍。
Tag search, which is to find a particular set of tags in a radio frequency identification (RFID) system, is a key service in such important Internet-of-Things applications as inventory management. When the system scale is large with a massive number of tags, deterministic search can be prohibitively expensive, and probabilistic search has been advocated, seeking a balance between reliability and time efficiency. Given a failure probability <inline-formula> <tex-math notation="LaTeX">$\frac {1}{\mathcal {O}(K)}$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> is the number of tags, state-of-the-art solutions have achieved a time cost of <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(K \log K)$ </tex-math></inline-formula> through multi-round hashing and verification. Further improvement, however, faces a critical bottleneck of repetitively verifying each individual target tag in each round. In this paper, we present an efficient tree-based tag search (TTS) that approaches <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(K)$ </tex-math></inline-formula> through batched verification. The key novelty of TTS is to smartly hash multiple tags into each internal tree node and adaptively control the node degrees. It conducts bottom–up search to verify tags group by group with the number of groups decreasing rapidly. Furthermore, we design an enhanced tag search scheme, referred to as TTS+, to overcome the negative impact of asymmetric tag set sizes on time efficiency of TTS. TTS+ first rules out partial ineligible tags with a filtering vector and feeds the shrunk tag sets into TTS. We derive the optimal hash code length and node degrees in TTS to accommodate hash collisions and the optimal filtering vector size to minimize the time cost of TTS+. The superiority of TTS and TTS+ over the state-of-the-art solution is demonstrated through both theoretical analysis and extensive simulations. Specifically, as reliability demand on scales, the time efficiency of TTS+ reaches nearly 2 times at most that of TTS.
登录
查看更多内容
DOI：
10.1145/2465529.2465549
发表时间：
2013-06
期刊：
IEEE/ACM Transactions on Networking
影响因子：
--
作者：
Muhammad Shahzad;A. Liu
通讯作者：
Muhammad Shahzad;A. Liu
DOI：
10.1109/rfid.2014.6810719
发表时间：
2014-04
期刊：
2014 IEEE International Conference on RFID (IEEE RFID)
影响因子：
--
作者：
J. Kaitovic;M. Rupp
通讯作者：
J. Kaitovic;M. Rupp
DOI：
10.1109/infcom.2010.5461946
发表时间：
2010-03
期刊：
2010 Proceedings IEEE INFOCOM
影响因子：
--
作者：
Bo Sheng;Qun A. Li;W. Mao
通讯作者：
Bo Sheng;Qun A. Li;W. Mao
DOI：
10.1109/infocom.2017.8056986
发表时间：
2017-05
期刊：
IEEE INFOCOM 2017 - IEEE Conference on Computer Communications
影响因子：
--
作者：
Min Chen;Jia Liu;Shigang Chen;Yan Qiao;Yuanqing Zheng
通讯作者：
Min Chen;Jia Liu;Shigang Chen;Yan Qiao;Yuanqing Zheng
用于 RFID 识别的概率最优树跳
影响因子：
3.7
作者：
Shahzad, Muhammad;Liu, Alex X.
通讯作者：
Liu, Alex X.