私は、2D空間に配置され、固定された通信範囲が限られているモバイルデバイスをシミュレートしようとしています。私はどのノードのペアが互いの範囲内にあるかを決定し、頂点が範囲の内外に移動するときにそれに応じてエッジが更新されるようにする必要があります。私は1000ノード以上のオーダーを期待しているので、毎回のステップが完全にペアワイズされた比較（O（n^2））を実行することは不可能です。頂点は異なる方向と速度を使用して移動するため、パスを予測する「予測的」手法も同様に難しいと仮定します。すべての頂点の通信半径が同じであると仮定します。与えられたユークリッド距離内の2次元空間での移動ノードのペアの発見？
既存のシミュレーション環境またはJavaライブラリが理想的ですが、アルゴリズムも役立ちます。 ns-2のようなハードウェアシミュレーション環境は、私が探しているシンプルな機能の極端な過剰です。
典型的な簡単な解決策は、スペースをグリッドに分割することです。通信範囲がRの場合は、たとえばRをグリッド間隔係数として使用します。グリッドの各セルでは、そのセルに属するノードのリスト/セットを継続的に更新します。ここで、モバイルデバイスMの近隣を見つけるためには、それ自身のセル内のモバイルデバイスおよびそのセルの近隣のものをチェックするだけで十分である。明らかに、他の間隔係数も使用できます。これは、すべてのモバイルデバイスがお互いに接続されているとは限りません。
@ antti.huimaが述べたように、ユークリデン空間をグリッドに分割する必要がありますが、グリッドのサイズを見つけることは要件に依存します。私たちがクラスタをグリッドから外すことができるかどうかは確かではありませんが、クラスタを作る方が効率的です。 モバイルがデルタ..で少し動いたとし、クラスターC1から近隣クラスターに移動すると、クラスター内の与えられた範囲のすべてのモバイルとペアにする必要があるので、このプロセスでは残りのN-1要素すべてでペアリングイベントを更新する必要はありませんが、クラスタ内にある要素のみで更新する必要はありません。クラスターの半径が2Rであると仮定して、私の見方を変えましょう。ここで、Rは私の推測の中でモバイルの範囲です。したがって、クラスタがC1から隣接するクラスタに移動するとき、その周りには8-10クラスタ（円として想像する）がありますので、ノードまたはモバイルをこの8-10クラスの要素の要素と比較する必要があります。ペアの数を最小にしています
ペアリングとクラスタのデビエーションと制約をペアにするために必要なパラメータについて詳しく教えてください.... – Imposter
唯一のパラメータはrです.2次元平面内の頂点間の距離通信することができます。それ以外の場合、ペアが形成できる他の制約はありません。 – Jeff