Large-scale sensor networks are facing critical challenges in deployment. The deployment problem can be solved by finding the optimal layout subject to various sets of requirements and planning the movement of sensor nodes to construct the optimal layout with minimum energy consumption. However, the previous studies neither guarantee the optimal layout, nor provide the route with minimum energy consumption. Thus, a new approach, $\emph{tree-based approach}$, is proposed with which the optimal layout is guaranteed to be achieved while the energy consumption is minimized.
At first, we have mathematically modeled the optimal layout in order to be dynamically realized into a target layout in the process of deployment. The realization of the layout model makes use of global informations about the initial layout of sensor nodes which are collected through a spanning tree. Then, each sensor node is matched to a vertex of the target layout employing divide-and-conquer strategy so that it can determine the destination within the target layout. By determining the destination before moving, the shortest route can be chosen which minimizes the energy consumption of movement.
Optimally matching the sensor nodes to the vertices in the target layout in tree-based approach is equivalent to minimum-weight complete matching problem of which efficient distributed method is yet unknown. As heuristics, three matching schemes, namely $\emph{rake tree scheme, balanced rake tree scheme}$ and $\emph{rake-id space scheme}$, are presented that exploit the tree structure of the initial layout in order to minimize the moving distance of sensor nodes. In these matching schemes, each sensor node is matched to a vertex in $\emph{rake tree}$ which can be trivially transformed to the target layout.
In our experiments, tree-based approach adopting the proposed matching schemes successfully deploys the sensor networks in the optimal layout, while the previous works do not. It also consumes less energy than previous works.
대규모 센서 네트워크의 배치문제는 매우 중요하고 어려운 문제이다. 배치문제는 다양한 요구조건들의 조합을 만족시키는 최적배치를 찾아내고, 최소한의 에너지만을 사용하여 최적배치로 이동할 수 있는 센서노드 이동경로를 구하는 문제이다. 그러나 센서 네트워크의 배치문제를 다루는 기존 연구들은 최적배치를 보장하지 못하며, 이동에 소요되는 에너지를 최소화하는 문제도 해결하지 못했다. 따라서 본 학위논문에서는 최적배치를 보장하고 동시에 에너지 소모도 최소화할 수 있는 "트리기반 접근법"을 제안한다.
우선, 최적배치에 대한 수학모델을 미리 정의하고, 이 모델에 의거하여 배치 수행중에 동적으로 배치목표를 결정할 수 있도록 한다. 배치목표를 동적으로 결정하는 데는 센서 네트워크의 초기배치에 대한 전역정보가 필요하기 때문에 스패닝 트리를 통해 전역정보를 수집한다. 이후 분할 정복 기법을 사용하여 모든 센서 노드에 배치목표의 정점을 하나씩 대응시킨다. 정점에 대응된 센서 노드는 그 정점을 사용하여 배치목표 안에서 자신의 최종 목적지를 계산할 수 있으며, 그 목적지로 가는 가장 에너지 소모가 적은 경로를 찾을 수 있다.
센서 네트워크 배치문제에 대한 트리기반 접근법에서 센서노드와 배치목표의 정점을 대응시키는 문제는 기존의 최소가중치 완전대응문제(minimum-weight complete matching)와 똑같은 문제이지만, 이 문제에 대해 최적의 결과를 찾을 수 있는 효과적인 분산 알고리즘은 아직 알려져 있지 않다. 따라서 그 대안으로서 세 개의 대응방안(갈퀴트리 방안, 균형진 갈퀴트리 방안, 갈퀴주소공간 방안)이 제시된다. 이 대응방안들은 초기배치에서의 트리구조를 이용함으로써 센서노드의 이동거리를 최소화하는데, 이 때 배치목표 대신 배치목표로 쉽게 변환될 수 있는 "갈퀴트리"의 정점에 센서 노드를 대응한다.
실험을 통해, 기존 접근법은 센서 네트워크의 최적배치를 만들지 못하지만 트리기반 접근법에 제안된 대응방안을 적용하면 최적배치가 성공적으로 만들어짐을 보였다. 또한 트리기반 접근법은 기존 접근법보다 더 적은 에너지를 사용하는 것이 확인되었다.
