论文标题
使用对局部敏感的散列搜索
Using Locality-sensitive Hashing for Rendezvous Search
论文作者
论文摘要
多通道会合问题是许多物联网应用程序中邻居发现的基本问题。文献中的现有作品主要集中在改善最差的表现上，而平均案例的性能通常不如随机算法那样好。由于物联网设备（用户）彼此接近，因此它们的可用频道集（尽管可能不同）是相似的。我们在数据挖掘中使用对局部敏感的哈希（LSH）技术，我们提出了通道跳跃算法，以利用两个可用通道集之间的相似性来增加集合概率。对于同步设置，我们的算法具有预期的时间段（ETTR）与称为jaccard索引的众所周知的相似性度量成反比。对于异步设置，我们使用尺寸降低来加快集合过程。我们的数值结果表明，我们的算法可以优于ETTR的随机算法。
The multichannel rendezvous problem is a fundamental problem for neighbor discovery in many IoT applications. The existing works in the literature focus mostly on improving the worst-case performance, and the average-case performance is often not as good as that of the random algorithm. As IoT devices (users) are close to each other, their available channel sets, though they might be different, are similar. Using the locality-sensitive hashing (LSH) technique in data mining, we propose channel hopping algorithms that exploit the similarity between the two available channel sets to increase the rendezvous probability. For the synchronous setting, our algorithms have the expected time-to-rendezvous (ETTR) inversely proportional to a well-known similarity measure called the Jaccard index. For the asynchronous setting, we use dimensionality reduction to speed up the rendezvous process. Our numerical results show that our algorithms can outperform the random algorithm in terms of ETTR.
