As the wireless sensor network technology advances, many applications for wireless sensor networks interacting with mobile agents continue to emerge. In these applications, paths for mobile agents are often considered important. In this thesis, we consider two problems related with the paths in sensor networks : path-based coverage problem and navigation problem.
In the path-based coverage problem, we solve two geometric problems. First, we propose
a new coverage measure of the sensor network considering arbitrary paths. Surprisingly,
this new measure captures both the best-case and the worst-case coverage of the sensor
network, namely, support and breach, simultaneously, enabling us to evaluate the given
network in a global viewpoint. We also present algorithms to deploy additional sensors to
improve the coverage. Second, we consider the path-based coverage in heterogeneous sensor networks. This is the first attempt to deal with the path-based coverage in heterogeneous
sensor networks.
In the navigation problem, we consider the problem of navigating a user to visit event
nodes in wireless sensor networks without location information. A set of event nodes is not
known in advance. As the set of event nodes changes over time, a navigation path needs to be updated on-line. We propose a novel distributed algorithm to construct and update such a dynamic navigation path to visit a set of event nodes.
본 연구는 센서 네트워크 환경에서 제기되는 경로 문제들에 대해 기하학적으로 접근하여 문제를 해결하고자 한다. 본 연구에서는 경로 커버리지 문제와 센서 네트워크에서 네비게이션 문제를 다룬다. 주어진 문제에 대해, 계산 기하학의 이론을 적용하는 방식으로 효율적으로 문제를 풀 수 있었다.
경로 커버리지 문제에서는 관련된 두가지 문제를 다룰것이다. 첫번째, 임의의 경로를 고려하는 새로운 커버리지 척도를 제안했다. 새로운 커버리지 척도를 최선과 최악의 커버리지를 동시에 고려하며, 전체 네트워크의 커버리지를 측정할 수 있다. 또한 커버리지 향상을 위해 센서를 추가하는 효율적인 알고리즘을 제시하였다. 두번째, 이기종 센서 네트워크 환경에서 경로 커버리지 문제를 고려하였다. 이기종 센서 네트워크 상에서 관련 문제를 제시한것은 처음이다.
네비게이션 문제에서는 위치 정보가 없는 센서 네트워크 상에서 유저가 이벤트 노드를 방문하는 경로를 생성하는 방법을 연구한다. 이벤트 노드들은 언제 발생하는지 미리 알수 없고, 실시간으로 생성된다. 이에 따라 경로 또한 실시간으로 갱신되어야 한다. 이를 위해 동적으로 경로를 만드는 분산 알고리즘을 제시한다.