在大规模RFID系统中快速而可靠的标签搜索：一种基于概率树的方法
摘要
在RFID系统中搜索一组特定的标签是库存管理等重要的物联网应用中的一项关键服务。当系统规模大、标签数量多时，确定性搜索的成本过高，因此有人主张采用概率搜索，在可靠性和时间效率之间寻求一种平衡。考虑到故障概率[1/(O(K))]，其中K是标签的数量，最先进的解决方案通过多轮散列和验证实现了O(K log K)的时间成本。然而，进一步的改进面临着一个关键的瓶颈，即在每一轮中重复验证每个单独的目标标签。在本文中，我们提出了一种新的基于树的标签搜索（TTS），通过分批验证接近O（K）。TTS智能地将多个标签哈希到每个内部树节点，并自适应地控制节点度。它进行自下而上的搜索，逐组验证标签，组的数量迅速减少。我们推导出最佳的哈希代码长度和节点度，以适应哈希碰撞，并通过理论分析和广泛的模拟证明了TTS的优越性。特别是，我们表明，随着可靠性需求和系统规模的增加，TTS实现了更高的性能增益，使其成为一个高度可扩展的解决方案。
作者
于季泓，龚伟，刘江川，陈林
期刊\会议
IEEE INFOCOM (CCF-A) [Link]
关键词
可靠性，搜索问题
