유전자 알고리즘을 이용한 센서 네트워크의 수명연장에 관한 연구

Abstract

무선센서네트워크를 이용한 응용분야에서 중요한 사항은 네트워크의 수명이다. 센서 네트워크는 자신이 갖는 자체 전원의 수명이 다 될 때까지 무선 통신, 데이터의 연산 등을 수행할 수 있다. 따라서 적절한 전원의 관리와 센서노드의 운영모드 스케줄링은 네트워크의 수명을 효과적으로 연장시킬 수 있다. 센서 네트워크의 수명을 연장하는 방안으로 동작노드 선택 프로토콜(active node selection protocol) 기반의 MSC (maximum set cover)문제가 제안되었다. 이 MSC 문제는 특정지점을 커버(target coverage)하는 응용분야에 적용된다. 이러한 MSC 문제는 NP-complete 이며 이에 대한 해로서 최적화 식을 이용한 방안들이 제안되었다. 제안된 알고리즘들은 다음과 같은 특징을 갖고 있다. 첫째, 중앙처리방식이다. 둘째, 대용량의 노드와 target 지점이 적용될 경우 많은 수행시간이 요구된다. 셋째, 노드의 감지와 스케줄링에 있어서 네트워크의 동작모드가 바뀐다. 본 논문에서는 MSC 문제에 대하여 유전자 알고리즘을 이용하여 네트워크의 수명을 연장함과 동시에 스케줄링 결과를 센서 네트워크에 적용함에 있어서 발생되는 네트워크의 동작 전환 횟수를 줄였다. 이러한 동작전환은 연속적인 감지기능을 저해하는 요인이 된다. 유전자 알고리즘을 MSC 문제 적용하기 위하여 다양한 유전 연산자를 새로히 설계하였으며, 센서 네트워크의 토폴로지 특성을 이용한 병렬 유전자 방식의 알고리즘도 같이 개발하였다. 제안한 유전자 알고리즘방식을 다양한 환경에서 시뮬레이션 한 결과 MSC 문제에 대하여 유효한 결과를 얻었으며, 특히 동작전환 횟수에 대해서는 기존의 방식에 비하여 우수한 결과를 도출하였다. 본 논문을 통하여 기여한 바는 다음과 같다. ⅰ) NP-complete 인 MSC 문제에 대하여 유전자 알고리즘을 적용한 방법을 제안 ⅱ) 센서 네트워크의 토폴로지 특성을 이용한 병렬처리 방식의 유전자 알고리즘 방법 개발 ⅲ) 제안한 방법이 네트워크의 연속적인 감지기능의 QoS에 대하여 우수함을 입증

A critical aspect of applications with wireless sensor networks is network lifetime. Power-constrained wireless sensor networks are usable as long as they can communicate sensed data to a processing node. Therefore, judicious power management and scheduling of sensor node's operation can effectively extend network lifetime. Active node selection protocol based MSC(maximum set cover) problem was suggested for prolonging the lifetime of the sensor networks in target coverage applications. MSC model is NP-complete and for this, some optimization algorithms were proposed. These algorithms have following features that 1) algorithms are centralized 2) algorithms need too much run-time in huge sensor networks 3) change of network's operation modes between sensing and scheduling The genetic algorithm is a global optimum random search algorithm based on the principles of evolution and natural genetics. In this thesis, applied GA(genetic algorithm) as a new method to MSC problem for extending networks lifetime and reducing the number of mode exchange on networks operations. To apply the genetic algorithm to MSC problem, designed a new chromosome encoding, crossover and mutation process and then, evaluated the of effectiveness suggested methods (GA based a centralized and a parallel version) by the software simulation. Simulation results showed that suggested GA based algorithms were suitable and effective on MSC problem and produced better results on QoS of network's continuous sensibility. The contributions of this thesis are ⅰ) applied GA on NP-complete MSC problem ⅱ) developed parallel GA on considering network topology ⅲ) verified that GA based methods are suitable and produced better results on QoS of network's continuous sensibility