One of the fundamental problems in wireless sensor networks is a coverage problem related to a moving target detection capability of a network. In this thesis, we present efficient algorithms to deploy additional sensors to improve path-based coverage. Two types of path-based coverage problems have been studied: the worst-case coverage problem whose purpose is to extract the most vulnerable path and the best-case coverage problem which is to find the path most easily detected by sensors. But previous works for path-based coverage only deal with a given source and destination pair. In real-world applications, however, it is not realistic to assume that we know a target or intruder`s source and destination. So, we extend the worst-case coverage problem to arbitrary source and destination pairs. We also show that a bottleneck Steiner tree problem in computational geometry is equivalent to the extended worst-case coverage problem. By this relationship, we propose an algorithm to find an optimal location of a single additional sensor for the problem. For the best-case coverage problem with a given source and destination pair, we provide an efficient method to find an optimal placement of a new sensor for the first time and prove its correctness using the properties of Delaunay triangulation. In case of multiple sensor additions, we propose heuristics based on optimal single addition algorithms and show its performance through simulations.
무선 센서 네트워크에서 경로 커버리지(path-based coverage) 문제는 이동하는 물체의 경로에 대해서 배치된 센서들의 탐지능력을 측정하고 추가 배치를 통해 개선하는 문제이다. 우리는 본 논문을 통해서 경로 커버리지를 개선하기 위한 추가 센서의 효율적인 배치 방법을 제시한다. 이전 경로 커버리지 문제는 주어진 시작점과 끝점을 연결하는 경로에 대해서 센서로부터 탐지가 취약한 경로를 강화하는 최악경우 커버리지(worst-case coverage) 문제와 센서와의 거리가 최소화되도록 경로를 개선하는 최선경우 커버리지(best-case coverage) 문제로 각각 연구되었다. 최악경우 커버리지는 침입자 탐지 시스템 등에서 취약한 경로를 개선하기 위한 개념이지만, 시작점과 끝점이 주어진 상황에서만 연구가 이루어져 현실을 잘 반영하지 못했다. 따라서 우리는 이 문제를 시작점과 끝점이 주어지지 않는 모든 경로에 대한 최악경우 커버리지 문제로 확장한다. 1개의 센서를 추가할 때 확장된 문제를 위한 최적의 위치를 찾는 효율적인 알고리즘을 계산기하학 분야의 병목 스타이너 트리(bottleneck Steiner tree)를 이용하여 제안한다. 또한, 시작점과 끝점이 주어진 최선경우 커버리지 문제에 대해서는 아직까지 추가 센서의 최적 위치에 대한 연구결과가 없기 때문에 우리는 1개의 센서를 추가할 때 최적의 위치를 찾는 효율적인 알고리즘을 처음으로 제시하고 Delaunay 삼각분할의 성질을 이용하여 이를 증명한다. 또한 다수의 센서를 추가 배치하는 경우에 대해서 1개의 추가 센서에 대한 최적 알고리즘을 이용한 휴리스틱 방법을 제안한다.
