A coverage problem is one of the fundamental problems in wireless sensor networks, robotics, and various application fields. Coverage can be considered as a measure of the quality of services, thus a coverage problem becomes one of the fundamental problems for the composition of the sensor network. Each sensor may have own influence range to cover the region and various sensors has been used and deployed to keep and monitor a target region. Proper sensor deployment is required to perform surveillance and monitoring tasks successfully, since a single sensor by itself has resource constraints and the sensor can cover only a small part of the region of interest. The importance of sensor deployment strategies for the coverage in the target region cannot be overemphasized.
First, Minimum Sensor Full-coverage Problems (MSFPs) with space constraints using various sensors are defined. Some given target region which has non-penetrable space constraints should be covered by a set of sensors. While maintaining the full-coverage state, the number of sensors or the cost of sensor network is also minimized. For this purpose, a map representation, a sensor representation, objective functions and coverage evaluation conditions are defined to represent the MSFPs in detail. The main characteristics of the problem are to deal with area coverage, non-penetrable obstacles. MSFPs are a NP-hard problem, so the metaheuristic methods are utilized to solve the problem with less computational cost. To solve the full-coverage problem intuitively, we decompose the MSFPs into two subproblems. One is a coverage increment problem and the other is a one-sensor reduction problem to solve the whole MSFPs efficiently.
After then, we focus on co-evolutionary sensor deployment algorithm (ESDA) to acquire a full-coverage state with minimum number of sensors in the predetermined target region including non-penetrable obstacles. Variable-length chromosome representations include only feasible sensors without redundant sensors. Sensor deployment operators produce various candidates to optimize the sensor deployment solutions closed under the infeasible region. A dual population structure is composed of the full-coverage population and the partial-coverage population to solve each subproblem efficiently. In addition, the information changes between two populations are performed by adopting the sensor deployment operators properly. Incremental deployment revision procedure is proposed to solve the full-coverage problem locally without the re-initialization from scratch when the environment is slightly changed.
In simulation studies, three types of sensors are used to validate the performance of the ESDA. The ESDA outperforms the other counter parts algorithms in various virtual maps for each MSFP in terms of the number of deployed sensors and the number of required cost evaluation for obtaining the deployment solution with the full-coverage state.
Finally, we consider two types of sensor deployment application. One is the localization by using the passive landmarks and an active IR sensor. Each landmark which is regarded as the node of the network has its own influence range to be responded by the nearby IR sensor. When the IR sensor is located on some position out of the influence range of passive landmarks, the dead zone is appeared not to be covered by any landmark. The other one is the surveillance by using a laser rangefinder. Each measurement point of a laser rangefinder is regarded as the node of the sensor network. Minimum number of operations of the laser rangefinder are performed and the experimental validation to generate coverage map in a target building by measurement data of the laser rangefinder.
센서 배치 문제는 무선 센서 네트워크(WSNs)와 로보틱스와 관련하여 많은 문헌에서 다루어져왔다. 커버리지는 목표 지역에 센서를 배치할 때, 가장 주요하게 고려되는 목적 함수 중 하나이다. 센서들은 그 위치 근처 영역을 커버할 수 있는 고유의 영향 범위를 가진다. 다양한 센서들이 목표 지역을 감시하고 살펴보는데 사용된다. 적절한 센서 배치는 감시나 모니터링을 위한 작업을 성공적으로 하기 위해서 필수적이다.
먼저 공간 제약이 있는 최소 센서 완전-커버리지 문제(MSFPs)를 다양한 종류의 센서에 맞게 정의한다. 어떤 투과 불가능한 공간 제약들이 존재하는 주어진 목표 지역이 센서 네트워크 내의 센서 집합들에 의해 커버가 되어야 한다. 완전-커버리지 조건을 만족하면서 센서 네트워크의 크기를 줄이게 된다. 이를 위해, 지도 표현, 센서 표현, 목적 함수들 및 커버리지 조건들을 MSFPs를 자세하게 표현하기 위해 정의한다. 이 문제의 주요한 특징들은 공간-커버리지, 투과 불가능 장애물로 들 수 있다. MSFPs는 NP-난해 문제이며, 따라서 메타휴리스틱 방법을 활용하여 적은 계산 비용을 들여서 문제를 푸는 방식으로 접근하게 된다. 이 완전-커버리지를 직관적으로 풀기 위해 우리는 MSFPs를 두 가지 소문제들로 나누게 된다. 하나는 커버리지 증가 문제이며 다른 하나는 센서 하나 줄이기 문제이다.
그 다음, 우리는 투과 불가능 장애물이 포함된 지역에서 최소 개수의 센서로 완전-커버리지 상태를 획득하기 위해 공진화적 센서 배치 알고리즘(ESDA)를 제안한다. 가변 길이 염색체 표현법은 과잉 센서 없이 오로지 동작 가능한 센서들을 포함하게 만든다. 센서 배치 연산자들은 비어 있는 지역 내에서 닫혀 있으며, 센서 배치 해를 최적화하기 위한 다양한 후보군들을 생성할 수 있게 한다. 이중 모집단 구조는 완전-커버리지 모집단과 부분-커버리지 모집단으로 구성되어, 각각의 소문제들을 풀도록 만든다. 뿐만 아니라, 두 모집단 사이에서 센서 배치 연산자를 적절히 활용하여 서로 염색체들을 이주시킬 수 있도록 한다. 점진적 배치 수정 부분은 기존의 최적 배치해가 존재할 때, 주위 환경이 약간 변하여 그 최적성을 잃을 경우, 완전-커버리지 문제를 국소적으로 풀기 위해 제안되었다. 이는 완전히 재초기화하거나 재탐색을 통하는 것에 비해 효율적으로 새로운 최적 배치 해를 찾게 한다.
시뮬레이션에서는 세 가지 종류의 센서를 활용해 ESDA의 성능을 검증한다. ESDA는 다양한 가상의 지도들에서 기존 알고리즘에 비해 배치 센서의 개수 및 완전-커버리지 상태를 달성하기 위한 배치 해를 얻기까지 필요한 비용 계산의 수를 줄이는 방향에서 우월함을 보인다.
마지막으로, 두 가지 센서 배치 어플리케이션을 고려한다. 하나는 수동적 랜드마크와 하나의 적외선 센서를 활용한 위치 인식과 관련된 실험이다. 각각의 랜드마크는 적외선 센서가 반응할 수 있는 영향 범위를 가진다고 볼 수 있다. 각각의 랜드마크는 센서 네트워크 상의 정점이라고 볼 수 있으며, 적절한 랜드마크를 배치한다면 어느 지역에서나 적외선 센서가 반응할 수 있는 랜드마크가 반드시 존재하게 된다. 만약 적외선 센서가 어떤 랜드마크의 영향 범위 내에 들지 못한다면, 데드 존이 발생하게 된다. 데드 존이 발생되지 않는 것을 확인하였다. 다른 하나는 레이저 거리 센서를 활용한 감시 문제이다. 레이저 거리 센서는 센서 네트워크의 능동적 정점이라고 간주할 수 있다. 목표 건물에서 센서를 설치하고, 근처 환경까지의 거리를 측정하는 실험을 통해 커버리지 지도를 구성함으로써 최소 정점의 배치 계산 결과를 검증하였다.
