我正在寻找模拟放置在 2D 空间中并具有固定、有限通信范围的移动设备。我需要能够确定哪些节点对在彼此的范围内，并确保在顶点移入或移出范围时相应地更新边。我希望有大约 1000 个节点或更多，因此每个时间步都进行完整的成对比较 ( O(n^2) ) 是不可行的。顶点将使用不同的方向和速度移动，因此我假设预测路径的“预测”方法同样困难。我假设所有顶点都具有相同的通信半径。
现有的模拟环境或 Java 库是理想的，但算法也会有所帮助。像 ns-2 这样的硬件模拟环境对于我正在寻找的简单功能来说太过分了。
一个典型的简单解决方案是将空间划分为网格。如果通信范围是 R，您可以使用例如 R 作为网格间距因子。在网格的每个单元格中，您不断维护属于该单元格的那些节点的列表/集合。现在，为了找到移动设备 M 的邻居，检查其自身小区内的移动设备以及该小区的邻居就足够了。显然，您也可以使用其他间距因子。如果不是每个移动设备都相互连接，这会大大加快速度。
正如@antti.huima 所说，我们应该将欧几里登空间划分为网格，但找到网格的大小将取决于需求。我不确定我们是否可以使集群脱离网格，但使集群更有效。假设移动台移动了一点delta..并从集群说C1移动到相邻集群说c2所以我们的移动台应该与集群中给定范围的所有移动台配对说C2...所以在这个过程中我们不需要使用所有其余 N-1 个元素更新配对事件，但仅使用集群中的元素。我们进一步假设集群半径为 2R，其中 R 是我假设的移动范围。