무선 센서 네트워크에서 에너지 효율적인 클러스터 헤드 선출 알고리즘

국문 초록 (Abstract)

클러스터 기반의 네트워크 토폴로지(topology)를 구성하고 유지하는 클러스터링 기술은 애드 혹(Ad-hoc) 및 센서 네트워크에서 많은 연구가 이루어져 왔다. 에너지 효율성이 중요한 무선 센서 네트워크에서 클러스터링 기술은 클러스터 헤드 노드가 클러스터 멤버 노드의 데이터를 병합하여 싱크로 전송함으로써 노드 간 통신의 양을 줄이게 하고 클러스터 내부적으로는 TDMA 스케쥴에 기반하여 클러스터 헤드가 클러스터 멤버 노드의 스케쥴을 조정함으로써 노드의 슬립 타임을 연장하게 한다. 클러스터링 알고리즘에서 기본적으로 요구되는 사항은 클러스터링 후 모든 노드는 클러스터 헤드 이거나 단 하나의 클러스터에 속해야 하고 추가적인 오버헤더는 최소화 되어야 한다. 또한, 안정적인 네트워크 토폴로지를 유지하고 네트워크 자원을 효율적으로 이용하여야 하며 센서 노드의 에너지 소비를 최소화 하여야 한다. 본 논문에서는 선행된 연구로 LEACH, EACHS, HEED의 문제점을 확인하였다. 요약하여 설명하면, LEACH 및 EACHS는 모든 노드의 에너지를 알아야 하는 제한사항이 존재하고 HEED는 클러스터 헤드 선출 수를 보장하지 않는 문제점이 존재한다. 제안하는 ECS(Energy efficient Cluster-head Selection) 알고리즘은 노드의 에너지가 제한되는 센서 네트워크의 수명 향상을 위하여 3가지 변수값(노드의 초기 및 현재 에너지, 클러스터 헤드에 의해 병합된 데이터가 싱크로 전송되는 각 라운드, 노드 자신이 클러스터 헤드로 선출된 수)을 이용하여 클러스터 헤드를 적절하게 선출한다. 제안하는 ECS 알고리즘의 성능을 확인하기 위하여 클러스터 헤드 선출에 있어 널리 알려진 프로토콜인 LEACH와의 시뮬레이션 비교를 통하여 ECS의 네트워크 수명이 68% 향상되었다는 것을 알 수 있다. ECS는 LEACH나 EACHS와는 다르게 클러스터 헤드의 선출에 있어서 단지 대상 노드의 정보만을 이용한다. 다시 말하면, 클러스터 헤드 선출 매 라운드마다 모든 노드의 에너지를 알 필요가 없다는 것이다. 따라서, 제안하는 ECS 알고리즘은 에너지가 제한되는 무선 센서 네트워크의 수명 향상을 위한 클러스터 헤드 선출 기법으로 효과적으로 적용될 것으로 기대된다.

다국어 초록 (Multilingual Abstract)

Cluster-based routing algorithm for wireless ad-hoc and sensor networks has been widely studied in recent years. The advantages of clustering algorithm are reducing the redundancy of exchanged messages, reducing the energy consumption, and extending the networks lifetime. And also, TDMA-schedule coordination of the cluster head extends sleep times of the node. There are some basic requirements for clustering algorithm. First of all, every node should be selected once as a cluster head. Second, clustering requires minimized overhead. Third, net-work topology must be stable. Also, network resources should be utilized efficiently. Finally, as sensor nodes are operated by low power, low energy consumption is required. In this thesis, we identified some problems of LEACH, EACHS and HEED. Simply speaking, LEACH and EACHS require the knowledge of energy for every node in the network topology. The other protocol, HEED does not guarantee the number of cluster heads. In order to extend network lifetime for WSNs, we proposed ECS algorithm which selects cluster-head using three vari-ables. They are consisted of initial and current energy of nodes, round information and total numbers of nodes which have been selected as cluster head until current round. In order to evaluate the energy efficiency for ECS algorithm, we compared ECS with LEACH. LEACH is a famous clustering algorithm in WSNs. Network lifetime of ECS is increased by 68% than LEACH algorithm. ECS only utilizes the information of node itself in cluster head selection process. But, LEACH and EACHS utilize the information of other nodes. In other words, ECS does not require energy information of all nodes. Therefore, proposed ECS algorithm can make full use of cluster-head selection technique of WSNs