센서 네트워크 배포 알고리즘

Question

주어진 공간에 센서를 배포하기위한 알고리즘이 필요합니다. 그 공간에는 장애가있을 수 있습니다. 각 센서에는 도달 반경 (서로 통신하기 위해)이 있으며 반경을 고려하여 전체 영역을 커버해야합니다. 목표는 사용되는 센서의 수를 최소화하고 대상 영역을 최대화하는 것입니다. 누군가?

감사합니다.

Answer 1

커버 된 영역과 사용 된 센서 수 사이의 절충을 정의해야합니다. 그렇지 않으면 작은 영역을 제외하고 거의 모든 영역이 이미 덮여있는 경우, 조금만 추가 센서를 추가할지 여부를 알 수 없습니다. 고정 된 주어진 수의 센서에 대한 최대 면적을 다루는 것으로 문제를 다시 표현할 수 있습니다. 가시 영역이 구멍 (장애물)이있는 다각형 영역 인 경우 문제가 해결되었다고 생각하고 문헌을 검토하면됩니다. 임의로 정의 된 공간과 장애가있는 경우 알려진 솔루션이 있는지 모릅니다.