2D 공간에 배치되고 고정 된 제한된 통신 범위를 갖는 모바일 장치를 시뮬레이션하려고합니다. 어떤 노드 쌍이 서로 범위 내에 있는지를 결정할 수 있어야하고 꼭지점이 범위 안으로 또는 범위 밖으로 이동할 때 그에 따라 가장자리가 업데이트되도록해야합니다. 나는 1000 노드 이상의 순서를 가질 것으로 예상되므로 매 단계마다 전체 pairwise 비교 (O (n^2))를 수행하는 것은 실행 불가능합니다. 정점은 다른 방향과 속도를 사용하여 움직일 것이므로 경로를 예측하는 '예측'방법은 매우 어렵다고 가정합니다. 모든 꼭지점의 통신 반경이 같다고 가정합니다.주어진 유클리드 거리 내에서 2D 공간에서 모바일 노드 쌍을 찾으십니까?
기존 시뮬레이션 환경 또는 Java 라이브러리가 이상적이지만 알고리즘도 도움이됩니다. ns-2와 같은 하드웨어 시뮬레이션 환경은 내가 찾고있는 단순한 기능에 극단적 인 과잉이다.
일반적인 쉬운 해결책은 공간을 그리드로 나누는 것입니다. 통신 범위가 R이면 예를 들어 R을 그리드 간격 요소로 사용합니다. 표의 각 셀에서 해당 셀에 속하는 노드의 목록/세트를 계속 유지 관리합니다. 이제 모바일 장치 M의 이웃을 찾으려면 자체 셀 내의 모바일 장치와 해당 셀의 이웃을 확인하는 것으로 충분합니다. 분명히 다른 간격 요소도 사용할 수 있습니다. 모든 모바일 장치가 서로 연결되어있는 경우가 아니면 속도가 훨씬 빨라집니다.
@ antti.huima가 말했듯이 유클리드 공간을 그리드로 나누어야하지만 그리드의 크기를 찾는 것은 요구 사항에 따라 달라집니다. 클러스터를 그리드에서 만들지 만 클러스터를 만드는 것이 더 효율적인지 여부는 확실하지 않습니다. 모바일이 델타 ..로 조금 움직 인다고 가정하고 클러스터에서 C1을 이웃 클러스터로 이동한다고 말하면 c2라고 말합니다. 따라서 우리의 모바일이 클러스터의 주어진 범위의 모든 모바일과 페어링되어야합니다. C2 ... 그래서이 과정에서 우리는 나머지 N-1 요소와 페어링 이벤트를 업데이트해야하지만 클러스터에있는 요소 만 업데이트하면됩니다. 우리는 클러스터 반경이 2R이라고 가정합니다. 여기서 R은 내 추측에서 모바일 범위입니다. 따라서 클러스터가 C1에서 이웃 클러스터로 이동할 때 노드 8 또는 10 클러스터가 주변에 8-10 클러스터 (원으로 상상 함)로 표시되므로 노드 또는 모바일을이 8-10 클러스터의 요소와 비교해야합니다. 숫자 쌍을 최소화하고 있습니다
페어링 및 클러스터에 대한 디비전 및 제약 조건을 쌍으로 연결하는 데 필요한 매개 변수에 대한 자세한 정보를 제공 할 수 있습니까? – Imposter
유일한 매개 변수는 r이며, 2D 평면의 정점 간 거리 의사 소통을 허용했다. 그렇지 않으면 쌍이 형성 될 수있는 다른 제약 조건이 없습니다. – Jeff