센서 네트워크의 경로 커버리지 문제를 위한 추가 센서의 최적 배치 방법

Abstract

무선 센서 네트워크에서 경로 커버리지(path-based coverage) 문제는 이동하는 물체의 경로에 대해서 배치된 센서들의 탐지능력을 측정하고 추가 배치를 통해 개선하는 문제이다. 우리는 본 논문을 통해서 경로 커버리지를 개선하기 위한 추가 센서의 효율적인 배치 방법을 제시한다. 이전 경로 커버리지 문제는 주어진 시작점과 끝점을 연결하는 경로에 대해서 센서로부터 탐지가 취약한 경로를 강화하는 최악경우 커버리지(worst-case coverage) 문제와 센서와의 거리가 최소화되도록 경로를 개선하는 최선경우 커버리지(best-case coverage) 문제로 각각 연구되었다. 최악경우 커버리지는 침입자 탐지 시스템 등에서 취약한 경로를 개선하기 위한 개념이지만, 시작점과 끝점이 주어진 상황에서만 연구가 이루어져 현실을 잘 반영하지 못했다. 따라서 우리는 이 문제를 시작점과 끝점이 주어지지 않는 모든 경로에 대한 최악경우 커버리지 문제로 확장한다. 1개의 센서를 추가할 때 확장된 문제를 위한 최적의 위치를 찾는 효율적인 알고리즘을 계산기하학 분야의 병목 스타이너 트리(bottleneck Steiner tree)를 이용하여 제안한다. 또한, 시작점과 끝점이 주어진 최선경우 커버리지 문제에 대해서는 아직까지 추가 센서의 최적 위치에 대한 연구결과가 없기 때문에 우리는 1개의 센서를 추가할 때 최적의 위치를 찾는 효율적인 알고리즘을 처음으로 제시하고 Delaunay 삼각분할의 성질을 이용하여 이를 증명한다. 또한 다수의 센서를 추가 배치하는 경우에 대해서 1개의 추가 센서에 대한 최적 알고리즘을 이용한 휴리스틱 방법을 제안한다.