Efficient Algorithms for Finding Vulnerability and Deploying Additional Sensors in a Region with Obstacles

Abstract

We presents efficient algorithms which finds the approximate path that is least covered path by sensors in a region. The algorithm requires significantly fewer computation than previous methods. We also present an deterministic algorithm which deploys an additional sensor to cover the least covered path deterministically. In our algorithm, the sensors, obstacles, and region are modeled with the most general forms. We define the degree of discover and the vulnerability of a region, build data structures to efficiently manage sensing areas generated by sensors and obstacles in the region, and define feasible area which roughly represents the vulnerable area of the region. The feasible area contains the least covered path, so we divide the feasible area into fine grids, not the whole region like previous methods, and deploy the additional sensors a specific points and directions in the feasible area to decrease the vulnerability deterministically. This will provide the specific number of required sensors for a specific surveillance in a region

무선 센서 네트워크는 자연 관찰이나 산업 시설 관리, Internet of Things (IoT) 등을 효과적으로 관리하기 위해 센서들을 무선 네트워크로 관리하는 시스템을 말한다. 이 논문은 장애물이 있는 지역에서 미리 배치된 센서들로부터 보안이 취약한 경로가 어디인지 빠르게 파악하는 방식과 보안이 취약한 경로에 효과적으로 센서를 배치하는 방식을 제시하여 surveillance 문제를 효과적으로 해결할 수 있도록 한다. 본 연구에서는 현재까지 연구된 surveillance 문제에 대해 정의된 센서들 중 수학적으로 가장 일반적인 형태를 다루도록 했으며, 주어진 영역에 장애물을 배치하도록 하여 영역도 가장 일반적인 형태를 취할 수 있도록 하였다. 그리고 보안이 취약한 경로를 수학적으로 정의하기 위해 각 센서들에 대한 sensing area를 정의하였다. 그로부터 한 지점에 대한 discover 함수와 주어진 경로에 대해 그 함수를 적분한 것을 exposure라 정의하고, exposure를 가장 최소로 갖는 path를 가장 취약한 path라고 정의하였다. 기존 방식은 이 path를 찾기 위해 비효율적인 계산을 많이 하였고, 센서 배치에 대해서도 현재까지는 처음에 임의로 배치한 후 가상적인 척력을 가정하거나 속도 등을 임의로 두는 등 랜덤 배치까지만 연구가 되어있었다. 본 연구에서는 전체 영역보다 작은 feasible area를 정의하고, 그 안에 가장 취약한 path가 있음을 증명하였다. 그래서 가장 취약한 path를 찾기 위해서 전체 영역을 다룰 필요 없이 feasible area에서만 관찰하여 찾도록 하여 기존의 방법들보다 훨씬 효율적이었고, 센서 배치에서도 feasible area에서 주어진 센서가 feasible area를 포함하게 배치하도록 하여 매 배치마다 확실하게 취약한 path를 감시하게 하여 주어진 영역의 surveillance를 확실하게 처리할 수 있도록 하였다.