1. 연구의 배경 및 목적

최근 무선센서네트워크를 사용하여 미세먼지, 초미세 먼지 등 환경 오염물질 측정, 서식지 및 산불 감시, 지진 관측, 헬스케어 및 재난 관리 구조물 모니터링 등 다양한 응용 분야에 적용될 수 있어 이동 컴퓨팅과 통신 분야에 서 활용성이 매우 높다[15]. 무선센서네트워크는 정보를 수집하는 센서로 구성되는데, 각 센서는 에너지가 한정 되어 있으므로 에너지 소모를 최소화하여 센서네트워크의 수명을 최대화할 수 있는 연구가 필요하다. Ibriq et al. [4]가 제시한 무선센서네트워크 모델 중에서 싱크(Sink) 노드, 클러스터 헤드(Cluster head), 센서 노드로 이루어 진 클러스터링(clustering) 모델은 센서와 클러스터 헤드 를 통하여 데이터를 수집하고 제한된 시간 내에 빠르게 정보를 전달할 수 있기 때문에 다른 모델들과 비교하여 우수하다. 특히, 클러스터링 모델에서 모든 센서들이 데 이터를 가장 가까운 클러스터 헤드로 보내기 때문에 에 너지 소모비용을 감소시킬 수 있다[4, 10, 11, 12, 13]. <Figure 1>은 클러스터링 모델센서네트워크를 산불 감시 및 예방에 적용한 것이다. 각 센서에서 수집된 모든 데이터는 클러스터 헤드로 전송되고 최종적으로 싱크로 전달된다. 이 때, 센서와 클러스터 헤드 또는 클러스터 헤드와 싱크 사이의 통신 거리가 커질수록 데이터 전송을 위해 더 많 은 에너지가 소비된다. 따라서, 센서네트워크 클러스터 링 모델을 어떻게 설계하여 에너지 소비를 최적화 할 것 인가 하는 연구가 필요하다.

Jin et al.[5], Hussain et al.[3], Kannan et al.[6], Latiff et al.[14], Kim et al.[11]은 무선센서네트워크를 최적설계하 기 위해 유전자알고리즘(Genetic Algorithm, GA), 시뮬레 이티드어닐링(Simulated Annealing, SA), 이진파티클군집 최적화(Particle Swarm Optimization, PSO) 방법 등을 적용 하였으나 거리와 클러스터 헤드 수만을 고려하였기 때문 에 실제 에너지 소모를 고려하지 못했다는 한계가 있다.

또한, 무선센서네트워크 설계를 위해 Heinzelman et al. [2]이 제안한 LEACH(Low-Energy Adaptive Clustering Hierarchy) 은 적절한 클러스터헤드 수를 적용하지 못하고 클 러스터헤드가 네트워크에 균형 있게 분포시킬 수 없다는 문제점이 있다. Heinzelman et al.[1]은 LEACH-centralized (LEACH-C)[1]를 제안하여 기존 LEACH의 성능을 개선하 였으나 클러스터 헤드에 실제로 연결된 센서로 에너지 소 모를 계산하지 못하고 센서들의 평균수를 적용하기 때문 에 보다 정확한 실제 에너지 소비를 산정할 수 없다. 이런 문제점을 극복하기 위해 Kim and Byun[10]은 하모니서치 (Harmony Search, HS), Kim et al.[11]은 인공벌 군집(Artificial Bee Colony, ABC)을 제안하고 LEACH, LEACH-C 와 비교분석 하였다.

본 논문의 목적은 센서네트워크의 에너지 소모를 최소화 하면서 각 센서의 에너지 소모의 균형을 맞추어 센서네트워크의 수명을 최대화할 수 있는 랭킹인공벌군집(Ranking Artificial Bee Colony, RABC) 클러스터링 방법을 소개하고 제안하 는 것이다. RABC는 ABC 방법을 기본으로 하고 현재까지 가장 좋은 해들을 사용하여 더 좋은 해를 확률적으로 생성 하는 랭킹전략(Ranking Strategy)을 적용함으로써 더 효율 적인 해 탐색이 가능하고, 센서네트워크 환경이 변경되더 라도 안정적인 해를 탐색 할 수 있어 무선센서네트워크의 성능을 최대화 할 수 있다. 본 논문의 제 2장에서는 설계하 고자 하는 무선센서네트워크에 대하여 설명하였고 제 3장 에서는 무선센서네트워크에 어떻게 RABC 설계방법을 적 용했는지 설명하였다. 제 4장에서는 실험 및 분석을 통하여 제안하는 최적설계방법의 성능에 대하여 검증 분석하였다.

2. 무선센서네트워크 설계 문제

본 절에서는 최적 설계하고자 하는 무선센서네트워크 문제를 설명하였다. 무선센서네트워크를 구성하는 센서 는 에너지가 한정되어 있으므로 센서의 에너지 소모를 최 소화해야 한다. 클러스터 헤드와 센서 간의 에너지 소모 량의 차이가 있기 때문에 센서네트워크 설계를 균형 있게 해야만 시간이 지남(라운드가 진행됨)에 따라 센서 간 잔여 에너지의 차이를 줄일 수 있다. 무선센서네트워크에서 에 너지를 모두 소모한 센서가 발생할 경우 해당 센서에서 수집하던 정보를 수집하지 못하게 된다. 기존 무선센서네 트워크 클러스터링 방법의 문제점을 해결할 수 있도록 센 서네트워크의 에너지 소모를 최소화하면서 센서들의 잔 여에너지를 균형 있게 유지할 수 있는 클러스터링 설계방 법이 필요하다. 즉, 센서네트워크를 효율적으로 관리하기 위해서는 센서의 소모에너지 평균을 최소화하면서 센서 들의 잔여에너지가 고르게 유지하는 것이 필요하다[11].

Heinzelman et al.[1, 2]가 무선센서네트워크 설계 문제 를 설명할 때 제시한 식 (1) E t n d i s s i p a t e는 시간의 흐름에 따른 진행 라운드(round) t에서 노드 n(n은 일반 센서 non - CH 또는 클러스터 헤드 CH 를 나타내고)의 소모 에너지를 나타낸다. m_n은 클러스터 n의 클러스터 헤드와 센서의 수, E_elec는 무선 통신으로 메시지를 수신할 때 소모되는 에너 지, E_DA는 병합 에너지, E_mp(다중경로 손실)는 전송되는 증폭기의 에너지, E_fs는 자유공간(free-space model) 손실 에너지를 나타낸다. 식 (1)의 첫 번째는 클러스터헤드 CH 가 소비하는 에너지의 양인데, 클러스터헤드가 (m_n - 1)개의 센서로부터 l-bits 메시지를 수신할 때 소모되는 에너지 (m_n - 1)lE_elec, m_n개(라운드 t에서 클러스터 헤드 n을 포 함한 연결되어 있는 센서의 수)의 센서로부터 l -bits메시 지를 병합(E_DA : 병합 에너지)할 때 소모되는 에너지 m_nlE_DA, 모두 모아진 에너지를 싱크로 전송할 때 소비되는 에너지 l E e l e c + l E m p d n t o B S 4 로 구성되어진다. d n t o B (클러스 터헤드 n과 싱크 B 노드간의 거리)는 일반적으로 d n t o C H (센서 노드 n과 클러스터헤드 CH 간의 거리)보다 길기 때문 에 거리에 4제곱에 비례하여 에너지 소비를 계산하였다. 식 (1)의 두 번째 식은 센서가 수집된 데이터를 클러스터 헤드에 전송할 때 소비되는 에너지의 양이다. 짧은 거리 d n t o C H는 2제곱에 비례하여 에너지가 소비된다.

현재 배터리의 에너지가 남아 있는 센서 또는 클러스 터헤드 수를 N 으로 나타낸다. Heinzelman et al.[1, 2]이 제시한 식 (1) E t n d i s s i p a t e을 사용하여 라운드 t에서 소 모되는 에너지의 평균을 구할 수 있다. 또한, 라운드 t + 1 에서 노드 n의 잔여에너지를 구하고 이 잔여 에너지의 평균과 표준편차를 사용하여 센서네트워크의 모든 센서 와 클러스터 헤드가 소모되는 에너지의 평균과 노드에 남아 있는 에너지간의 편차를 구할 수 있다. 즉, RABC 방법을 적용하여 탐색하는 각각의 해는 식 (1)을 기본으 로 각 노드의 소비 에너지 평균과 에너지간의 편차로 평 가하였다. 소비 에너지 평균과 에너지간의 편차 최소화 의 중요도에 따라 가중치를 다르게 설정할 수 있으나 본 논문에서는 가중치가 같다고 가정하였다[11]. 노드 15개 무선센서네트워크 예제는 데이터가 최종적으로 수집되는 싱크(Sink)는 원점이고 15개 노드 위치는 <Figure 2(a)>와 같다. 본 논문에서 제안하는 방법을 적용하여 어떤 경로 로 데이터를 수집할 것인지 무선센서네트워크 설계 해 <Figure 2(b)>를 제시한 것이다. 싱크와 직접 연결된 5개 의 클러스터 헤드 2, 5, 6, 7, 8, 12와 각 클러스터 헤드와 연결된 나머지 센서로 구성된다.

본 논문에서는 라운드 t의 각 해에 대하여 각 클러스터 헤드와 연결된 센서의 소모 에너지 E t n d i s s i p a t e를 식 (1)을 적용하여 계산한다. RABC 방법 적용 시 해를 평가 할 때, 평균 소모에너지와 잔여에너지의 표준편차의 합을 식 (2)와 같이 평가한다[10, 11]. 본 연구에서는 평균 소모에너지와 잔여에너지의 표준편차 가중치(α, β)는 같게 설정한다. 이 평가함수는 평균 소모에너지를 최소화하여 센서네트워크의 성능과 수명을 최대화할 수 있고, 잔여에너지의 표준편차를 최소화하여 가능하면 모든 노드의 에너지가 골고루 남아 있게 하여 편중된 정보의 수집을 최소화한다. N은 센서네 트워크에서 배터리의 에너지가 남아 있는 노드 수를 나타 낸다. E t n d i s s i p a t e을 사용하여 라운드 t에서 노드 n의 소모 되는 에너지의 평균은 A V G ( E d i s s i p a t e ) = ( ∑ n ∈ N E t ( n ) d i s s i p a t e ) / N 와 같다. 라운드 t + 1에서 노드 n의 잔여에너지는 E t + 1 n r e s i d u a l = E t n r e s i d u a l − E t n d i s s i p a t e 와 같다. 잔여 에너지의 평균은 A V G ( E r e s i d u a l ) = ( ∑ n ∈ N E t ( n ) r e s i d u a l ) / N 이고 표준편차는 S T D E V E r e s i d u a l = ∑ n ∈ N { A V G ( E r e s i d u a l ) − E ( n ) r e s i d u a l } 2 / N 와 같다.

본 논문의 목적은 센서네트워크의 노드들이 소모되는 에너지의 평균과 노드들에 남아 있는 에너지간의 편차를 가중치 α와 β를 고려하여 식 (2)를 최소화하는 것이다.

3. 랭킹인공벌군집 RABC 최적설계 방법

본 절에서는 무선센서네트워크 최적설계 랭킹인공벌군집 (RABC) 방법이 어떻게 효율적으로 센서네트워크 클러스 터링 설계할 수 있는지를 설명하였다. Karaboga[7, 8, 9]가 제안한 인공벌군집(Artificial Bee Colony, ABC) 최적화 방 법은 벌들이 꽃 음식(Food source, FS)을 찾아 꿀을 채취하 는 메커니즘을 모방하여 개발한 알고리즘이다. ABC는 벌 을 이웃해 탐색을 위한 employed bee(EB), 전역해 탐색을 위한 onlooker bee(OB), 다양한 해 탐색을 위한 scout bee (SB)로 구분한다. EB는 현재 꽃의 이웃 꽃을 탐색하여 더 꿀이 많은 꽃을 찾는 것처럼 현재 해의 더 좋은 이웃 해를 탐색한다. OB는 각각의 EB들이 탐색한 꽃들의 정보를 이 용하여 여러 개의 꽃들로부터 더 좋은 꽃을 확률적으로 추가 탐색하여 꽃을 찾아낸다. SB는 EB와 OB가 더 이상 꿀이 많은 꽃을 탐색해 내지 못할 때 새로운 꽃을 찾아 탐색하는 역할을 한다. 즉, EB와 OB는 수렴성을 추구하여 더 좋은 꽃을 탐색하려고 하는 반면, SB는 새로운 꽃 탐색 을 통해 지역해에 머물지 않고 다양한 해 탐색으로 더 좋 은 해를 찾을 수 있는 시도를 하는데 ABC는 이러한 수렴 성과 다양성의 균형을 조절하여 최적화를 하는 방법이다. 이 알고리즘을 적용하기 위해서는 적용 분야와 문제에 맞게 알고리즘을 설계하는 것이 가장 중요하고 다양하고 문제에 적용되어 왔다[7, 8, 9].

RABC는 위에서 설명한 ABC를 더 효율적인 탐색 방 법으로 발전시키기 위해 현재까지 탐색한 해들 중에서 가 장 우수한 해들을 활용하여 더 좋은 해를 확률적으로 생 성하여 투입함으로써 해 탐색을 개선 발전시키기 위한 방 법이다. 센서네트워크 클러스터링 설계를 위한 RABC의 FS 해의 표현은 <Figure 3>과 같이 전체 노드 수(N = 15 )를 길이로 하는 <Figure 2(b)>의 설계 해를 1차원 행렬의 형 태로 표현하는데, 해를 구성하는 클러스터헤드에는 1의 값을 일반 센서 노드에는 0을 표시하는데 각 센서는 가장 가까운 클러스터에 소속된다.

즉, 클러스터 헤드 2, 5, 6, 7, 8, 12는 ‘1’로 표시하고, 나머지 센서 노드 1, 3, 4, 9, 10, 11, 13, 14, 15는 ‘0’으로 표시하고 각각 가장 가까운 클러스터 헤드에 연결된다. 클러스터 헤드 2에 연결된 센서 3, 클러스터 5에 연결된 센서 1과 4, 클러스터 8에 연결된 센서 9, 10, 14, 15, 클 러스터 헤드 12에 연결된 센서 11과 13, 클러스터 헤드 6 과 7은 독자적으로 데이터 수집을 한다.

RABC 방법을 적용할 때, 모든 해 평가는 제 2장에서 설명한 평가함수(라운드 t의 소모에너지 평균과 라운드 t + 1의 잔여에너지의 표준편차 적용한 평가함수[11])를 최소화 하도록 적용하고 <Figure 4>와 같이 RABC 단계 1~6으로 설명할 수 있다. 단계 1에서는 초기 해 군의 해 의 수와 각 해의 더 좋은 이웃해 탐색 최대 수(Limit)의 파라미터 값과 종료 조건을 결정한다. 단계 2에서는 각 노드를 클러스터헤드로 할당 할 때는 1, 일반 센서 노드 인 경우는 0으로 표시하여 초기 해들을 생성한다. 단계 3 에서는 각 해(Food source, FS)에 대하여 EB를 결정하고 각 해들의 지역탐색을 위하여 이웃해를 탐색한다. 각 해 에 대하여 평가값을 계산하고 더 좋은 해가 발견되면 더 좋은 해로 업데이트 하고 이웃해 탐색 시도 횟수를 기록 하는 Trial을 0으로 설정한다. 그렇지 않을 경우 해당 해의 Trial의 횟수를 증가시킨다. 단계 4에서는 평가값에 비례 하는 확률로 이웃해 탐색 후 평가값을 계산 한다. 즉, 현 재 모든 해를 사용하여 평가값(i번째 해의 평가값 f_i)에 비례하는 확률 식으로 해를 추가적으로 선택하고 더 좋 은 해가 생성되면 더 좋은 해로 업데이트 하고 이웃해 탐색 시도 횟수 카운터 Trial을 0으로 설정한다. 그렇지 않을 경우 Trial의 횟수를 증가 시킨다. 이와 같은 전역 해 탐색은 OB에 의해서 수행된다. 단계 5에서는 랭킹전 략을 적용한다. 즉, 현재까지 탐색해 낸 해들 중에서 평 가값이 좋은 것에 비례하여 임의로 해들을 선택한다. 이 해들을 조합하여 새로운 해를 생성한다. 생성된 해를 해 군(solution population)에 투입 하고 정렬하여 가장 좋지 않은 해를 탈락시킨다. 단계 6에서는 Trial 값이 Limit값 이상일 경우 SB는 다양한 탐색을 위해 새로운 해를 생 성한다. 즉, Trial이 기존에 설정한 값 Limit보다 클 경 우 해당 이웃해는 더 개선될 수 없다고 판단하고 더 이 상 탐색하지 않는다. 탈락한 수만큼의 해들을 SB를 통하 여 임의적으로 생성하여 지역 해에 빠지지 않고 다양한 해 탐색을 추구하여 전역 해를 탐색 한다. 이 모든 단계 수행 후 종료 조건에 맞으면 종료하고 그렇지 않으면 단 계 3의 EB의 이웃해 생성부터 반복 수행한다.

4. 실험 및 분석

본 절에서 제안하는 무선센서네트워크 설계 방법의 성 능을 검증하기 위해 임의적으로 선택된 100개 노드 센서 네트워크를 사용하였다. RABC 방법을 클러스터링 설계에 적용할 때 Intel(R) Core(TM)2 Quad CPU 2.33GHz, 4GB RAM, 윈도우7 32비트 컴퓨터 운영체제, Visual C++로 실 험하였으며, 파라미터 값은 초기 해군의 수는 50개, 이웃해 탐색 최대 수 Limit는 100으로 하였다. 종료 조건은 사용 자가 제시한 계산시간 한도 내 또는 일정 세대가 진행되어도 해 개선이 되지 않을 경우 종료하였고 비교 실험 시 LEACH 클러스터 헤더 확률은 0.1로 설정하였다. 초기 에너지 E_j는 0.5J, E_elec는 50nJ/bit, E_mp는 0.0013pJ/bit/m⁴, E_fs는 10 pJ/bit/m², EDA는 5nJ/bit/signal, l는 1024bit이다.

<Figure 5(a)>~<Figure 5(c)>는 싱크가 원점에 위치하는 경우, <Figure 5(d)>~<Figure 5(f)>는 싱크가 중앙에 위치 하는 경우 100개 노드 센서네트워크에서 기존 LEACH[2], LEACH-C[1], HS[10]와 RABC 클러스터링 방법을 적용 할 때 라운드 진행에 따른 성능(평균잔여에너지(Average residual energy), 살아남은 노드 수(Number of nodes alive), 수신한 아이템의 수(Number of received items))을 비교하 였다. 매 라운드의 클러스터링 방법을 적용하여 센서네 트워크의 모든 노드들의 에너지가 소모될 때(특정 라운 드 시점이 아닌 모든 라운드가 진행되었을 때)까지의 성 능을 비교하였다. <Figure 5>에서 평균 잔여에너지가 많 이 남아 있을수록, 살아남은 노드 수가 많을수록, 수신한 아이템의 수가 많을수록 경쟁력 있는 클러스터링 방법이 다. 싱크의 위치가 한쪽으로 치우쳐있는 원점(0, 0)일 경 우보다는 넓게 퍼져있는 노드들의 중앙에 싱크가 위치한 경우 무선센서네트워크 클러스터링 설계 해의 성능이 우 수한 것으로 분석되었다. RABC 클러스터링 설계 방법과 ABC의 성능의 차이는 크지 않으나, RABC은 기존 LEACH, LEACH-C, HS 방법보다 우수하고 경쟁력이 있는 것으로 분석되었다.

<Figure 6>은 100개의 노드로 구성된 무선센서네트워 크 문제에 매 라운드마다 RABC를 적용한 최적의 클러 스터링 설계 결과이다. 100개 네트워크에서 싱크(●)위치 에 따른 클러스터 헤드(●)와 센서(각 클러스터에 연결되 는 센서는 다른 모양으로 구별) 노드 해 위치를 표시한 것이다. <Figure 6(a)>는 싱크가 원점, <Figure 6(b)>는 싱 크가 중심에 위치한 경우를 나타낸다. 모든 클러스터 헤 드는 싱크에 연결되고 각 센서는 가장 가까운 클러스터 로 연결된다.

<Table 1>은 싱크가 원점이거나 중심인 100개 노드 센서 네트워크에서 LEACH[2], LEACH-C[1], HS[10], ABC[11] 와 RABC 클러스터링 방법에 따른 첫 번째 센서가 사라지 는 라운드(Round first node dies), 마지막 센서가 사라지는 라운드(Round last node dies) 및 수신 가능한 총 메시지 양 (Total messages received)으로 평가할 수 있는 센서네트워크 성능을 비교 분석한 것이다. 첫 번째 센서와 마지막 센서가 사라지는 라운드가 클수록, 수신 가능한 총 메시지 양이 클수 록 경쟁력 있는 설계 방법이다. 노드가 사라지면 에너지가 모두 소비되어 정보를 수집할 수 없다. 본 논문의 실험에 따르면 싱크의 위치가 원점(0, 0)에 위치시키는 경우보다는 센서네트워크의 중심에 위치시킬 때 센서네트워크의 성능 이 우수하였다. LEACH-C가 LEACH보다 성능이 우수하고 RABC, ABC, HS이 LEACH와 LEACH-C보다 성능이 우수 하였다. 싱크의 위치가 원점(0, 0)에 위치시키는 경우 HS, ABC, RABC의 성능의 차이는 크지 않았으나, 싱크의 위치 가 센서네트워크의 중심에 위치시킬 때 RABC와 ABC의 성능이 HS보다는 성능이 우수한 것으로 분석되었다.

5. 결 론

본 논문에서는 무선센서네트워크의 에너지 소모를 최 소화하면서 각 센서의 에너지 소모의 균형을 맞추어 네 트워크의 성능을 최대화하기 위해 랭킹전략을 인공벌군집 (ABC)에 적용한 랭킹인공벌군집(RABC)을 제안하고 기 존 LEACH, LEACH-C 등 기존 설계 방법과 비교 분석하 였다. 제안하는 RABC 설계 방법은 현재까지 생성한 해 들 중에서 평가값이 좋은 해를 확률적으로 선택 조합하 여 더 좋은 해를 생성하고 탐색에 활용함으로써 탐색 효 율을 높이고자 했다. 또한, 해 평가 시 클러스터 헤드에 연결된 센서의 수를 고려하고 에너지 모델을 적용하여 에너지 소모를 계산하였다. 제안하는 최적설계방법은 센 서네트워크 전체 평균 소모 에너지를 최소화하면서 센서 의 에너지 소모를 균형화 할 수 있는 해를 매 라운드마 다 적용하여 모든 센서에서 정보의 수집이 계속될 수 있 도록 하였다. 실험 분석에 따르면 RABC를 무선센서네트 워크 설계에 적용했을 때 네트워크 성능이 기존 방법보 다 우수한 것으로 분석되었다. 본 논문에서 제안한 무선 센서네트워크 설계방법은 다양한 이동 컴퓨팅과 통신분 야에서 널리 적용될 수 있을 것으로 기대된다.