Due to the recent advances in digital technology, developments of low-cost and multi-functional sensors become possible. When a large number of sensors collaborate using wireless communication, they constitute wireless sensor network. Although wireless sensor network has many applications, it has limited lifetime due to the limited amount of power equipped in each sensor, and replacing the battery is impractical in many applications. Therefore, one of the important design issues in the network is how to use the energy efficiently to extend the network lifetime for performing the sensing and communication tasks.
To monitor a set of targets with known hostile locations, we can spread a large population of sensors in the proximity of the targets instead of positioning them in precise locations. This increases the network density, thus the sensing area of some sensors may overlap. Now we can schedule the sensors` activities such as to allow the redundant sensors to enter the sleep state and save energy for future use. Let the set of sensors which can perform the monitoring task independently as an active set. To maximize the network lifetime, it is critical to rotate the roles of the active set among the sensors in the network. Thus, at any time, only one set of sensors belong to one active set are asked to be active, instead of all the network sensors.
Generally, we use a graph to represent the network. Each sensor of the network is represented as a vertex and there exists an edge between two vertices if and only if two vertices are located within a communication range. A dominating set is a subset of vertices such that each vertex of the graph is either in the dominating set or has a neighbor in the dominating set. Now an active set in the network equivalent to the dominating set in a graph.
In this thesis, we consider several optimization problems to extend the network lifetime in wireless sensor network . First, we consider the maximum disjoint set covers problem. In maximum disjoint set covers problem, we assume that, targets are stationary, all sensors in network are homogeneous and each sensor can participate in at most one dominating set. Under this assumption, the larger the number of disjoint sets, the longer the network lifetime. To obtain a maximum number of disjoint sets, we propose a mathematical formulation, and computational experiments show that our formulation outperforms the previous mathematical formulation in terms of the run times to obtain an exact solution. Also, we propose a heuristic and this algorithm can be used when the expected run time to obtain an exact solution is probably too long.
For a given graph with the different amount of resources in each vertex, obtaining a maximum network lifetime is referred to as a maximum lifetime coverage problem. One of the main difficulties to obtain an exact solution is, if we use a linear programming to formulate the problem, exponential number of variables is required to represent the problem. To overcome this difficulty, we applied a column generation procedure to handle the variables implicitly rather than explicitly. We also suggest using two techniques to accelerate the convergence to an optimal solution during the column generation procedure. We performed extensive computational experiments on randomly generated graphs, and we obtained exact solutions in all cases within a reasonable amount of time.
Next we consider the case when the sensors in a dominating set need to be connected. This requirement happens for proper routing protocol functioning and asks to obtain a minimum connected dominating set for a given graph. In this thesis, we first propose an improved algorithm for the minimum connected dominating set problem. Generally, representing the connectivity requires an exponential number of constraints, thus we first solve the mathematical formulation without the connectivity constraints. If the constructed subgraph using the selected vertices forms a connected dominating set, we obtained a minimum connected dominating set, thus stop the algorithm. Otherwise, since the solution from the formulation is disconnected, we have several components. Now, for each component, we identify the minimum sized vertex cut which separates the current component and the other components, and we only add the corresponding violated constraint to the formulation. Then we solve the enlarged formulation again. This process is continued until we obtain a connected dominating set. We performed extensive computational experiments and the results show that our algorithm can obtain an exact solution in a reasonable amount of time. Also, our exact algorithm is applied to the maximum lifetime coverage problem to obtain a maximum network lifetime, and computational results are included.
Lastly, we consider how the robustness can be achieved in a dominating set. Since sensors in wireless sensor network are prone to failure, it is also important to maintain a certain degree of redundancy in the dominating set. This requirement asks to solve the minimum $\It{k}$-connected $\It{m}$-dominating set problem exactly. In $\It{k}$-connected $\It{m}$-dominating set, there exist at least $\It{k}$ vertex disjoint paths between any pair of sensors in the dominating set, and each sensor not included the dominating set has at least m adjacent sensors in the dominating set. Therefore, this type of the dominating set can enhance the routing flexibility and the fault tolerance of the network. In this thesis, we propose an exact algorithm for the minimum $\It{k}$-connected $\It{m}$-dominating set problem and the scheme is almost similar to the algorithm used for the minimum connected dominating set. Also, we suggest a heuristic algorithm which can be used to construct the $\It{k}$-connected $\It{m}$-dominating set efficiently, and we discuss about the existence of the $\It{k}$-connected $\It{m}$-dominating set when a graph is given with two natural numbers $\It{k}$ and $\It{m}$. We executed performance tests for the algorithms, and our algorithms are also extended to obtain a maximum network lifetime.
최근 디지털 기술 분야에서는 급속한 발전이 있었으며, 이러한 발전은 다양한 기능을 수행할 수 있는 저가의 센서의 등장을 가능케 하였다. 많은 센서들이 하나의 목적을 위하여 협업하며, 무선으로 상호 통신이 가능할 경우 이를 무선 통신망이라고 부른다. 하지만, 많은 무선 통신망 응용 사례에서는 여러 가지 이유 (접근성 등) 들로 인하여 배터리를 교체하는 것이 불가능하다. 따라서 무선 통신망에서 가장 중요한 이슈중의 하나는, 한정된 배터리 자원이 주어졌을 시 어떻게 활용하는 것이 전체 네트워크의 수명을 최대화 하는 것이다.
일반적으로 접근이 용이치 않은 지역을 감시하고자 할 때, 감시 대상의 주변에 많은 개수의 센서들을 무작위로 배치시키는 것도 센서 배치의 한 방법이다. 이러한 센서들의 배치는 네트워크의 밀도를 증가시키며, 특정 센서들의 경우에는 감시 영역이 겹치는 일도 발생한다. 이때 에너지를 아끼기 위하여 이렇게 감시 영역이 중복되는 센서들을 수면상태로 바꾸는 센서의 활동 스케줄을 작성 할 수 있다. 여기서 독립적으로 감시 임무를 수행할 수 있는 센서들의 집합을 활동 집합이라고 하자. 그러면 전체 네트워크의 수명시간을 최대화 하기 위해서는 네트워크에 속하는 모든 센서들이 동시에 동작하기 보다는 이러한 활동 집합에 속하는 센서들만 동작하게 하며, 이러한 활동 집합의 역할을 모든 센서들이 돌아가면서 수행함으로써 달성될 수 있다.
본 논문에서는 그래프를 사용하여 네트워크를 나타내기로 한다. 네트워크의 각 센서들은 노드로 표현되며, 만일 네트워크 상의 두 센서가 서로 통신이 가능한 거리 내에 존재하면 두 노드는 선으로 연결된다. 그래프 이론에서 지배집합이란, 그래프의 노드들의 부분집합이되, 그래프의 각 노드가 지배집합에 포함되거나 지배집합에 있는 노드들과 이웃하는 노드들을 뜻한다. 그러면 무선 센서 망에서의 활동집합은 그래프 이론에서의 지배집합과 동일한 개념으로 사용될 수 있음을 알 수 있다.
본 논문에서는, 무선 센서 망에서 발생하는 여러 가지 네트워크 수명 시간에 대한 연구를 수행하고자 한다. 첫 번째로 최대 분단 범위 집합 문제를 다룬다. 최대 분단 범위 집합 문제에서는, 모든 감시 대상들의 위치가 고정되었고 네트워크 상의 모든 센서들이 동일한 유형의 센서들이며 각 센서는 최대 하나의 분단 범위 집합에만 속할 수 있다고 가정한다. 이러한 가정하에서는, 분단 범위 집합의 수가 많으면 많을수록, 네트워크의 수명이 연장된다. 따라서 본 논문에서는 최대 분단 범위 집합을 얻을 수 있는 수리 모델을 제시하며, 여러 다양한 실험 결과는 본 논문에서 제시된 수리 모델이 기존의 수리 모델보다 최대 분담 범위 집합을 더 빠른 시간 안에 얻을 수 있음을 보여준다. 또한 빠른 시간 내에 효율적으로 해를 찾을 수 있는 발견적 해결 방법을 제시하여, 최대 분단 범위 집합 문제를 푸는데 소요되는 시간이 클 시에 사용될 수 있도록 하였다.
앞으로 그래프의 각 노드들에 각각 다른 양의 자원들이 할당되어있을 시에, 최대 네트워크 사용 가능 시간을 얻는 문제를 최대 네트워크 유효 수명 시간 문제라고 칭한다. 하지만 최대 시간을 얻기 위해서 선형 수리 모델을 사용하여 문제를 나타낼 경우, 기하급수적인 변수의 개수가 필요하다. 이러한 문제를 해결하기 위하여, 변수들을 직접적이 아닌 간접적으로 다루는 열 생성 기법을 사용하였다. 또한 열 생성 기법의 최적해로의 수렴 시간을 단축시키기 위하여 두 가지 기법을 적용하였으며, 다양한 그래프에서의 실험 결과는 우리의 방법이 모든 경우의 문제에 대해서 적정 시간 안에 최적해를 얻을 수 있었음을 보여준다.
다음으로 최대 네트워크 유효 수명 시간 문제에서 사용되는 지배 집합에 연결성이 보장되어야 하는 경우를 살펴보았다. 이러한 연결성은 감지된 데이터들의 운반 경로 설정 프로토콜에서 필요로 하며, 최소 개수의 노드들로 연결된 지배 집합을 구하는 문제를 풀어야 최대 네트워크 유효 수명 시간 문제를 다룰 수 있으므로 먼저 최소 개수의 연결된 지배집합을 구하는 문제를 다룬다. 이를 위해서 먼저 연결성을 나타내는 기하급수적으로 많은 제약식을 제외한 수리모델을 먼저 푼다. 이때 수리모델은 지배성을 나타내는 노드 개수만큼의 제약식이 존재하게 된다. 만일 수리모델을 풀어서 나온 해가 연결된 부분 그래프를 구성한다면, 최소 개수의 연결된 지배집합을 얻을 것이므로 알고리즘을 종료한다. 그렇지 않다면 끊어진 여러 개의 부분 그래프가 존재하므로, 연결성을 보장하기 위해 각 부분 그래프와 다른 부분 그래프들간을 나누는 노드 절단 집합을 구하며 이에 해당하는 연결성 관련 제약을 수리 모델에 더하고 수리 모델을 다시 푼다. 이러한 과정은 연결성을 얻을 때까지 계속된다. 이러한 알고리즘을 가지고 다양한 실험들을 수행 했으며 적정한 시간 내에 최소 개수의 연결된 지배집합을 얻을 수 있었다. 또한 이 알고리즘은 최대 네트워크 유효 수명 시간 문제를 푸는데 적용되었으며, 이 실험결과 역시 본 논문에 포함되어 있다.
마지막으로 본 논문에서는 지배집합에서 강건성을 보장하는 방법에 대해서 다룬다. 무선 센서 망에서 센서들은 고장 날 가능성이 크므로, 지배집합에서 어느 정도의 잉여성 갖는 것이 필요하다. 이를 나타낸 것이 $\It{k}$-노드 연결성과 $\It{m}$-지배성을 가지는 지배집합이다. $\It{k}$-노드 연결성은 지배 집합에 포함된 노드들이 $\It{k}$-1개의 노드가 실패해도 연결성이 보장됨을 의미하며, $\It{m}$-지배성은 지배 집합에 포함되지 못한 노드들의 경우에는 주변에 최소 $\It{m}$개의 지배 집합에 포함된 노드들이 있음을 나타낸다. 그러므로, $\It{k}$-노드 연결성과 $\It{m}$-지배성을 가지는 지배집합에서는 센서 실패에 대한 보장과 데이터 운반 경로 설정에서 다양성을 지님을 알 수 있다. 따라서 본 논문에서는 최소 개수의 $\It{k}$-노드 연결성과 $\It{m}$-지배성을 가지는 지배집합을 구하는 문제에 대해서 최적의 알고리즘을 먼저 제시한다 (이 알고리즘은 연결성이 보장되어야 하는 지배집합에서 사용된 것과 거의 유사하다.). 또한 지배집합을 효율적으로 구할 수 있는 발견적 기법을 제시하며, 그래프와 두 자연수 $\It{k}$와 $\It{m}$이 주어졌을 시에 그래프에 $\It{k}$-노드 연결성과 $\It{m}$-지배성을 가지는 지배집합의 존재 여부에 대해서도 논의한다. 마찬가지로 다양한 그래프에서 알고리즘의 성능을 테스트하였으며, 이 알고리즘은 최대 네트워크 유효 수명 시간 문제를 푸는데 적용되었다. 실험 결과는 본 논문에서 제시된 알고리즘의 유효성을 보여준다.
