In wireless sensor network (WSN), scheduling and power management algorithms have been researched as key techniques to extend network lifetime. In this thesis, we address Multiple Target Coverage Problem (MTCP) in WSN. Conventional sensor scheduling algorithms assume that sensors consume the same transmission energy regardless of how many targets are observed by itself. However, in the MTCP, since the sensor which monitors more number of targets would gather more sensed data, it consumes more transmission energy for sending the collected data to a sink node. Therefore, we assume that the transmitting energy of sensor is proportional to the number of targets covered by sensor itself and its sensing duration. In the MTCP, there also exist overlapped targets that are sensed by adjacent multiple sensors at the same time. Obviously, the overlapped targets are redundancy and result in energy waste due to multiple transmission of the same information. In this thesis, we study on the enhancement of WSN considering the MTCP that has different characteristics unlike the conventional WSN.
First, we propose a novel energy efficient scheduling algorithm in the MTCP that considers the transmitting energy in accordance with the number of targets and sensing time. For performance evaluation, we model the optimal sensor scheduling algorithm for MTCP as an Integer Programming that was proved to be NP-complete. To solve the optimal algorithm for MTCP, we propose two heuristic algorithms based on a Linear Programming and a greedy approach which reduce complexity efficiently. Simulation results show that the network lifetime of two heuristic algorithms is close to that of the optimal algorithm for MTCP in case of relatively small number of sensors and targets.
Second, we propose an enhanced scheduling algorithm considering overlapped targets in the MTCP. The overlapping sensors, which cover the overlapped target at the same time, gather the same information and send them to the sink node. To remove the redundancy of overlapped targets, we propose an energy efficient method that only one or small number of sensors are responsible for transmitting the overlapped information. Simulation results show that the network lifetime of enhanced sensor scheduling scheme considering overlapped targets is longer compared to the original MTCP.
무선 센서 네트워크에서는 센서 스케쥴링이나 전력 관리 알고리즘이 네트워크의 수명을 연장하기 위한 핵심 기술로 연구되어 왔다. 본 논문에서는 다중 목표물을 지원하는 센서 네트워크의 에너지 효율 개선 방안을 연구하였다. 기존의 센서 스케쥴링 알고리즘들은 센서가 관찰하는 목표물 수에 관계 없이 일정한 전송 전력을 소모한다고 가정하였다. 하지만, 더 많은 목표물을 관찰하는 센서는 더 많은 데이터를 수집할 것이고, 수집한 데이터를 싱크 노드로 전송하기 위해 더 많은 전송 에너지를 소모할 것이다. 따라서, 센서의 전송 에너지는 센서가 관찰하는 목표물의 수와 목표물 감지 시간에 비례한다고 할 수 있다. 또한, 다중 목표물 지원 시 인접한 다수의 센서들에 의해 동시에 관찰되어지는 중복된 목표물들이 존재하게 된다. 이러한 중복된 목표물은 같은 정보의 중복 전송을 발생시키기 때문에 에너지 낭비를 야기한다. 따라서, 본 논문에서는 기존의 무선 센서 네트워크와 다른 특성을 가지는 다중 목표물을 지원하는 무선 센서 네트워크에서 에너지 효율을 개선하기 위한 방안을 제안한다.
첫째, 센서가 관찰하는 목표물의 수에 따른 전송 에너지를 고려한 다중 목표물 지원 센서 망에서의 에너지 효율적인 센서 스케쥴링 알고리즘을 제안하였다. 제안 방안의 성능 검증을 위해 다중 목표물 지원을 위한 최적의 센서 스케줄링 알고리즘을 NP-complete로 증명된 정수 계획법으로 모델링하였다. 이를 효율적으로 풀기위해 선형 계획법과 greedy 접근을 기초로 하는 두 가지의 heuristic 알고리즘을 제안하였다. 시뮬레이션 결과는 제안한 두 가지 heuristic 알고리즘으로 계산한 네트워크 수명이 최적의 센서 스케쥴링 알고리즘으로 계산한 최대 네트워크 수명에 근접함을 보여준다.
둘째, 중복된 목표물을 고려한 센서 스케쥴링 알고리즘을 제안하였다. 중복된 목표물을 동시에 관찰하는 중복된 센서들은 같은 정보를 수집하고 이를 싱크 노드에 전송한다. 이러한 중복된 목표물의 중복성을 제거하기 위해서 하나의 센서만 중복된 정보를 싱크 노드로 전송하는 에너지 효율적인 방법을 제안하였다. 시뮬레이션 결과는 중복된 목표물을 고려하였을 때의 네트워크 수명이 고려하지 않았을 때보다 연장되었음을 보여준다.