algorithm - 在给定的欧氏距离内的二维空间中查找移动节点对？

Question

我想要模拟放置在 2D 空间中并具有固定、有限通信范围的移动设备。我需要能够确定哪些节点对在彼此的范围内，并确保在顶点移入或移出范围时相应地更新边。我希望有大约 1000 个节点或更多，因此每个时间步进行完整的成对比较 ( O(n^2) ) 是不可行的。顶点将使用不同的方向和速度移动，因此我假设预测路径的“预测”方法同样困难。我假设所有顶点都具有相同的通信半径。

现有的模拟环境或 Java 库是最理想的，但算法也会有所帮助。像 ns-2 这样的硬件模拟环境对于我正在寻找的简单功能来说太过分了。

Answer 1

一个典型的简单解决方案是将空间划分为网格。如果通信范围是 R，您可以使用例如R 作为网格间距因子。在网格的每个单元格中，您不断维护属于该单元格的那些节点的列表/集合。现在，为了找到移动设备 M 的邻居，检查其自己小区内的移动设备以及该小区的邻居就足够了。显然，您也可以使用其他间距因子。如果不是每个移动设备都相互连接，这会大大加快速度。