A Simulated Annealing Algorithm for Maximum Lifetime Data Aggregation Problem in Wireless Sensor Networks

접수일자 : 2013. 03. 19 심사완료일자 : 2013. 04. 14 게재확정일자 : 2013. 04. 30

* Corresponding Author Kil-woong Jang(E-mail:[email protected], Tel:+82-51-410-4375) Department of Data Information, Korea Maritime University, Busan 606-791, Korea

Open Access

http://dx.doi.org/10.6109/jkiice.2013.17.7.1715

무선 센서 네트워크에서 최대 수명 데이터 수집 문제를 위한 시뮬레이티드 어닐링 알고리즘

장길웅^*

A Simulated Annealing Algorithm for Maximum Lifetime Data Aggregation Problem in Wireless Sensor Networks

Kil-woong Jang

Department of Data Information, Korea Maritime University, Busan 606-791, Korea

요 약

무선 센서 네트워크에서 최대 수명 데이터 수집 문제는 네트워크에 배치된 모든 노드의 데이터 전송 에너지를 최 소화함으로써 네트워크의 수명을 최대화하는 문제이다. 본 논문은 무선 센서 네트워크에서 최대 수명 데이터 수집 문제를 효과적으로 해결하기 위한 메타휴리스틱 기법 중 하나인 시뮬레이티드 어닐링 알고리즘을 제안한다. 제안된 알고리즘에서는 보다 효과적인 해를 찾기 위해 새로운 이웃해 생성방식과 복구함수를 적용한다. 제안된 알고리즘의 성능은 네트워크 수명과 알고리즘 실행시간 관점에서 기존의 알고리즘과 비교평가 하였으며, 실험 결과에서 제안된 알고리즘이 최대 수명 데이터 수집 문제에 효과적으로 적용됨을 보여준다.

ABSTRACT

The maximum lifetime data aggregation problem is to maximize the network lifetime as minimizing the transmission energy of all deployed nodes in wireless sensor networks. In this paper, we propose a simulated annealing algorithm to solve efficiently the maximum lifetime data aggregation problem on the basis of meta-heuristic approach in wireless sensor networks. In order to make a search more efficient, we propose a novel neighborhood generating method and a repair function of the proposed algorithm. We compare the performance of the proposed algorithm with other existing algorithms through some experiments in terms of the network lifetime and algorithm computation time.

Experimental results show that the proposed algorithm is efficient for the maximum lifetime data aggregation problem in wireless sensor networks.

키워드 :

Key word :

Ⅰ. 서 론

최근 무선 센서 네트워크는 다양한 연구와 개발로 인 하여 많은 발전을 이루었다. 무선 센서 네트워크는 비 용이 저렴한 수많은 무선 마이크로 센서들로 구성되어 견고하고 자동화된 방식으로 지진, 수중, 의학 등 다양 한 데이터 정보를 수집하는 환경에 적용할 수 있다. 하 지만 무선 센서 네트워크는 제한된 센서 전력과 계산 용량, 통신 자원을 극복해야하는 몇 가지 문제점을 가 진다[1, 2]. 센서 노드는 대부분 제한된 자체 전력만으 로 구동하게 된다. 따라서 무선 센서 네트워크와 관련 된 프로토콜은 노드의 전력소모를 최소화하고 네트워 크의 수명을 최대화하는데 주로 초점을 맞추고 있다[3].

무선 센서 네트워크의 수명은 일반적으로 다음과 같이 정의한다. 네트워크 노드 중에 전력이 모두 소모되어 작동불능상태에 놓인 첫 번째 노드가 나타나는 시간을 무선 센서 네트워크의 수명이라고 말한다. 즉 네트워크 수명은 작동불능상태가 나타나는 첫 번째 노드가 작동 을 시작하여 멈추는 시간 간격을 말한다[4].

무선 센서 네트워크에서 에너지 효율적인 데이터 수 집을 위해 싱크를 루트로 하여 전송범위 내의 노드를 인접 노드로 설정하여 스패닝 트리를 구성하는 방식으 로 주로 연구가 이루어지고 있다. 센서에 의해 탐지된 데이터는 중간 노드를 통해 수집되고 트리 경로에 따라 싱크로 전송된다. 데이터 수집 시에 무선 센서 네트워 크의 수명을 최대화하기 위해 스패닝 트리를 사용하는 연구에서는 크게 두 가지 부류로 나눈다. 첫째는 미리 계산된 후보 트리의 집합에서 각 트리의 시간을 찾는데 초점을 두는 방식이다[4-6]. 일반적으로 미리 계산된 후 보 트리는 싱크를 루트로 한 모든 가능한 트리의 집합 을 의미한다. 하지만 이 방식에서는 노드의 수가 많은 무선 센서 네트워크에서 엄청나게 많은 스패닝 트리가 만들어진다는 문제점을 가진다. 따라서 미리 계산된 후 보 트리를 사용하는 방식은 모든 트리를 나열해야하는 계산상 거의 불가능하게 되는 단점을 가진다. 또 다른 방식[7]은 미리 계산된 후보 트리 집합에 의존하지 않고 하나의 트리를 사용하는 것이다. 이 방식의 장점은 모 든 가능한 스패닝 트리를 나열할 필요가 없다는 것이다.

그러나 이 방식에서 하나의 트리로 데이터를 수집하는 것은 최적의 결과를 찾지 못할 수도 있다는 문제점을 가진다. 앞선 두 가지 방법이 가진 문제점을 해결하기

위한 한 가지 해결책으로 휴리스틱 방식을 사용한 최적 화 방법을 사용하는 것이다. 휴리스틱 방식은 가장 좋 은 결과를 얻는다는 보장은 없지만 합리적인 시간 안에 좋은 결과를 찾을 수 있는 방법으로 알려져 있다.

본 논문에서는 무선 센서 네트워크에서 네트워크 수 명을 최대화하기 위한 데이터 수집 문제 (Maximum Lifetime Data Aggregation: MLDA)[7-9] 를 해결하기 위한 최적화 알고리즘을 제안한다. MLDA 문제는 고전 적인 조합 최적화 문제이며, 네트워크의 노드 수에 비 례하여 지수승으로 계산 시간이 증가하는 NP-hard 문 제로 증명되었다[7]. 현실적으로 NP-hard 문제는 계산 시간을 줄이기 위해 정확한 결과를 찾는 대신에 휴리스 틱 방법을 이용하여 합리적인 계산시간에 근사값을 찾 는 방법으로 다양한 NP-hard 문제에 적용되고 있다[7, 8]. 본 논문에서는 NP-hard인 MLDA 문제를 해결하기 위해 메타 휴리스틱 방법 중 하나인 시뮬레이티드 어닐 링(Simulated Annealing: SA) 알고리즘을 제안한다. 제 안된 SA 알고리즘에서는 새로운 이웃해 생성 방식과 복구 함수를 제안하며, 제안된 알고리즘을 평가하기위 해 다양한 조건하에서 네트워크 최대 수명과 알고리즘 실행 시간 관점에서 기존의 다른 알고리즘과 비교 평가 한다.

Ⅱ. 관련연구

Heinzelman et al.[10] 은 무선 센서 네트워크를 위한

클러스터 기반의 계층적 데이터 전송 알고리즘(Low

Energy Adaptive Clustering Hierarchy: LEACH) 을 제

안하였다. LEACH 알고리즘은 무선 센서 네트워크에

서 대표적인 분산 알고리즘으로 노드의 수와 위치정보

를 미리 알고 있다는 가정 하에 낮은 전력을 사용하여

싱크로 데이터를 전송한다. 클러스터 기반 알고리즘에

서는 각 클러스터마다 존재하는 클러스터헤드를 결정

하는 일이 중요하다. 클러스터헤드는 클러스터 내에 존

재하는 다른 노드로부터 데이터를 수집하여 싱크로 전

송하는 역할을 한다. LEACH 알고리즘은 노드의 위치

정보와 에너지 레벨에 따라 각 라운드마다 클러스터헤

드를 결정한다. LEACH 알고리즘의 핵심내용은 싱크

로 직접 전송하는 노드의 수를 줄이는 데 있다. 작은 수

의 노드로 하나의 클러스터를 구성하고 각 클러스터헤

드는 클러스터내의 노드로부터 데이터를 수집하여 그 데이터를 압축하여 데이터를 전송함으로써 전송 에너 지를 줄이고자 한다. Lindsey et al.[11]은 LEACH 알고 리즘의 개념을 확장한 에너지 효율적인 데이터 수집 알 고리즘(Power Efficient Gathering in Sensor Information Systems: PEGASIS) 을 제안하였다. PEGASIS 알고리 즘에서는 각 노드가 가장 인접한 노드로 데이터를 송수 신하는 체인구조를 형성함으로써 싱크까지 데이터를 전송한다. 즉 데이터는 체인의 각 시작점에서부터 출발 하여 클러스터헤드까지 도착하며, 체인을 거치면서 각 노드에서는 데이터를 압축하여 전송함으로써 전송효율 을 높이며 마지막으로 클러스터헤드가 싱크로 데이터 를 전송하는 방식을 취한다. PEGASIS 알고리즘은 LEACH 알고리즘과 비교했을 때 네트워크 수명 관점 에서 더 좋은 성능을 가진 것으로 나타나고 있다. Tan et al.[7] 은 무선 센서 네트워크에서 라운드마다 전체 에너 지를 최소화하기 위한 데이터 전송 알고리즘(Power Efficient Data gathering and Aggregation Protocol - Power Aware: PEDAP-PA) 을 제안하였다. PEDAP-PA 알고리즘은 최적화된 최소 신장 트리를 이용하여 데이 터를 전송하는 방식으로써 각 노드의 남은 에너지양을 고려하여 메시지 전송 시에 소모되는 에너지양을 송신 지에서 목적지 사이의 경로비용으로 결정하였다. Wu et al.[9] 은 데이터 수집 문제에 대한 네트워크 수명을 최대화하는 근사치 알고리즘을 제안하였다. 이 알고리 즘은 임의의 네트워크 트리를 구성하여 반복적으로 데 이터가 집중되는 노드의 부하를 줄이는 방식으로 구성 된다.

Ⅲ. 문제 정식화

MLDA 문제를 정식화하기 위해 제안된 SA 알고리 즘에서 사용되는 기호를 우선 정의한다.

Notations

N Number of sensor nodes vi Identification of node i

pi Identification of parent of node i V Set of nodes = {v

,v

, … v

}, where

v

is a sink

e

Edge between nodes v

and v

E Set of edges = {e

, e

, …, e

} g A gathering tree in a network T(g) Lifetime of a data gathering tree g in

a network

T

(g) Lifetime of node v

in data gathering tree g G Set of all possible data gathering trees in a

network

E

Amount of remained energy of node v

E

Energy for transmitting a packet from nodes

v

to v

E

Energy for receiving a packet from other nodes

c

Number of neighbors sending a packet to node v

e

Energy for the transmitter or receiver circuitry

e

Energy for the transmitter amplifier k Packet size

d

Euclidian distance between nodes v

and v

R

Transmission range of node v

무선 센서 네트워크에서 MLDA 문제를 해결하기 위

한 네트워크 모델은 비방향성 그래프인 G = (V, E)로 나

타낼 수 있으며, V는 N개의 노드로 이루어진 집합을 의

미하며, E는 노드의 연결을 나타내는 링크의 집합을 의

미한다. 노드 i에서 j로의 링크 e

는 노드 j에서 i로의 링

크 e

가 존재함을 의미한다. 노드 v

에 대하여 v

의 전송

범위 R

는 노드 v

를 중심으로 반지름 r을 가지는 원이

된다. 센서 노드는 데이터를 송신하는 부분과 수신하는

부분이 별도로 동작한다. 송신 부분은 전송 장치와 전

송 증폭기로 구성되며, 수신 부분은 수신 장치로 구성

된다. 일반적으로 전송 장치와 수신 장치에서 소모되는

에너지 e

는 50nJ/bit로 가정하고, 전송 증폭기에서 소

모되는 에너지 e

는 100pJ/bit/m

으로 가정한다. 본 논

문에서는 데이터 수집에 의한 네트워크 수명을 계산하

기위해 데이터 수집 트리를 구성하고 구성된 트리에 대

하여 각 노드의 에너지 소모량을 계산한다. 따라서

MLDA 문제는 다음과 같이 목적 함수를 최소화하는 조

합 최적화 문제로 정식화할 수 있다.

최소화

T(g) for g ∊G (1) 에 관한

T(g) = max T

(g) for i = 1, …, N (2) T

(g) = E

- (E

+ c

E

) for j = 0, …, N (3)

E

= e

k (4)

E

= e

* k + e

* d

* k (5)

식 (1)은 식 (2)를 만족하는 트리 중 가장 작은 트리를 찾는 알고리즘의 목적함수를 나타낸다. 식 (2)는 네트워 크의 모든 노드를 포함하는 데이터 수집 트리에 대하여 각 노드의 남은 에너지를 모두 총합하여 최대값을 가지 는 트리를 구하는 함수이다. 식 (3)은 전송에너지와 수 신에너지에 의하여 각 노드의 남은 에너지를 구하는 함 수이다. 식 (4)는 패킷 크기에 따른 수신에너지를 나타 내며, 식 (5)는 데이터 전송에 따른 에너지 소모량을 나 타낸다. 데이터 전송에 의한 에너지 손실은 두 노드 v

와 v

간 거리 d

의 제곱에 비례한 것으로 정의한다.

Ⅳ. MLDA를 위한 SA

본 논문에서 MLDA 문제에 대한 제안된 SA 알고리 즘은 다음과 같은 순서로 진행된다.

단계 1. 해(solution)의 인코딩 설계 단계 2. 하나의 초기 해 생성 단계 3. 인접해 생성

3-1. 교환동작(Replace Operation) 3-2. 복구함수(Repair Function) 3-3. 정지 기준 및 온도 검사

단계 4. 정지 기준을 만날 때까지 단계 3을 반복

좋은 해를 찾기 위한 방법으로 해에 대한 효율적인 인코딩(encoding)을 설계하는 것이다. 따라서 인코딩 설계에 따라 알고리즘의 성능은 달라질 수 있다. 인코 딩이 결정되면 제약식을 만족하는 하나의 초기해를 랜 덤하게 생성한다. 초기해 S

는 현재해 S

와 최적해 S

로

저장된다. 현재해에 대하여 제안된 교환동작에 의하여 인접해 S

를 생성한다. 생성된 S

는 주어진 제약식에 맞 는지 검사하여 제약식을 만족하지 않으면 복구함수를 이용하여 제약식에 적합한 해로 수정한다. 제약식을 만 족하는 S

는 S

와 비교하여 더 좋은 해일 경우 S

을 S

와 S

로 저장하고 그렇지 못할 경우에는 현재 온도상태에 따라 S

을 S

로 선택될 수 있다. 그리고 현재의 S

값은 다음 인접해를 생성하는 데 사용한다. 이러한 방식으로 정지 기준을 만날 때까지 인접해 생성 과정을 반복한다.

지금까지 기술한 제안된 SA의 전체 알고리즘은 다음과 같다.

procedure SA() S

← InitialSolution() S

← S

// current solution: S

S

← S

// best solution: S

t ← T

// initial temperature: T

while t < T

do // final temperature: T

iter ← 0 // the number of iteration: iter while iter < IterSA do

// Maximum iteration: IterSA j ← 0

while j <length(S

) do while true do

v

← selNode() p

← selDestination(v

)

S

← replaceOperation(S

, v

, p

) if S

≠ S

then

break end end

if Invalid(S

) then repairFunction(S

) end

if cost(S

) – cost(S

) > 0 then S

← S

S

← S

else if rand(0, 1) < exp(C/t) then S

← S

else

j ← j + 1

end end

iter ← iter + 1 end

t ← t * a end return S

end procedure SA

4.1. 인코딩

메타휴리스틱 알고리즘에서 사용되는 인코딩은 일 반적으로 이진 스트링[12, 13]으로 구현되지만 정수 값 을 이용한 인코딩 방식이 조합 최적화를 위해 더 효과 적일 수 있다[14]. 제안된 알고리즘에서도 정수를 가진 인코딩 방식을 적용한다. 본 논문에서 사용되는 인코딩 구조는 그림 1과 같이 소스 노드와 목적 노드의 쌍으로 이루어진다. 그림에서 v

와 p

는 해의 i번째 요소에 해당 하는 소스 노드와 목적 노드를 의미한다. 이러한 인코 딩 구조를 지원하기 위해 제안된 SA 알고리즘에서는 노드 간의 거리를 저장하는 노드 간 거리 테이블과 각 노드의 전송범위 내에 위치하는 인접 노드의 위치정보 를 저장하고 있는 인접노드 테이블을 가진다.

그림 1. 해 인코딩 Fig. 1 Solution encoding

4.2. 초기해 생성

제안된 SA에서 최적의 해를 구하기 위해 제안된 인 코딩 방식에 따라 제약식을 만족하는 초기해 하나를 랜덤하게 생성한다. 여기서 제약식을 만족하는 해는 네트워크에 존재하는 모든 노드가 싱크로 직접 전송 하거나 다른 노드를 거쳐 전송할 수 있는 해를 말한다.

초기해를 생성하는 동작은 다음과 같은 절차로 이루 어진다.

단계 1: 네트워크에 존재하는 모든 노드에 대하여 싱크로 데이터를 전송하는 하나의 경로를 설정한다.

우선 싱크와 직접 전송할 수 있는 노드를 찾아 싱크를 목적 노드로 하여 초기해에 삽입한다. 제안된 알고리 즘에서는 초기해를 구성하기 위해 집합 Q를 사용한다.

집합 Q는 식 (6)과 같이 싱크와 선택된 소스 노드를 포 함한다.

 ← 

∪ 

(6)

단계 2: 노드가 싱크로 직접 전송하지 못하는 경우 인접한 노드 중에 집합 Q에 포함된 노드를 찾는다. 만 약 집합 Q에 포함된 노드가 여러 개 존재할 경우 가장 가까운 노드를 선택하여 그 노드를 목적 노드로 선택하 여 목적 노드와 함께 초기해에 삽입하고 집합 Q에 포함 시킨다.

단계 3: 단계 2를 반복하여 네트워크에 존재하는 모 든 노드가 집합 Q에 포함되면 초기해 생성 과정을 마 친다.

그림 2. 교환 동작의 예

Fig. 2 An example of the replace operation

4.3. 이웃해 생성

SA 에서 가장 중요한 단계는 현재해에서 새로운 해

를 생성하기 위해 인접해로 이동하는 이동방법을 정의

그림 3. 복구함수의 예

Fig. 3 An example of the repair function

하는 것이다. 제안된 SA 알고리즘의 이동방법은 현재 해의 모든 요소에 대하여 순차적으로 적용되며, 해의 요소 중 목적 노드를 소스 노드의 또 다른 인접노드로 교환하는 방식을 사용한다. 따라서 본 논문에서는 이 방식을 교환동작(replace operation)이라고 칭한다. 본 논문에서 제안한 교환동작은 다음과 같이 동작한다.

단계 1: 현재해의 요소 (u, v)에서 소스 노드 u가 하나 이상의 인접 노드를 가지면, 그 노드의 인접 노드 중 하 나인 노드 w를 랜덤하게 선택한다.

단계 2: 초기해에서 인접해가 하나일 경우에는 그대 로 (u, v)를 유지하고, 만약 두 개 이상이면 v를 제외한 나머지 인접 노드 중 하나를 랜덤하게 선택한다. 만약 선택된 노드가 w라고 하면 (u, w)로 바꾸어 새로운 인접 해를 하나 생성한다. 이때 새로 생성된 인접해가 제약 식을 만족하면 이 해를 수용한다. 만약 제약식을 만족 하지 않으면 복구함수를 이용하여 제약식을 만족하는 해로 수정한다.

그림 2는 제안된 SA의 이동방법을 나타낸 예이다.

싱크를 제외한 5개의 노드를 가진 네트워크에서 현재해 가 (1, s)–(2, s)–(3, 1)–(4, 1)–(5, 2)라고 가정한다.

현재해의 네 번째 요소인 (4, 1)이 선택되어 인접해로 이동시킬 경우, 노드 4의 인접 노드 중 1을 제외한 나머 지 노드 2, 3, 5 중에 하나를 선택할 수 있다. 만약 노드 2 가 선택된다면 새로운 인접해 (1, s)–(2, s)–(3, 1)–(4, 2)–(5, 2)가 될 것이며, 이것은 제약식을 만족하는 해가 된다. 만약 다른 노드 3 이나 5가 선택되더라도 제약식 을 만족하는 해가 된다.

4.4. 복구함수

이동방법에 의해 생성된 인접해들은 일반적으로 제

약식을 만족하는 경우와 만족하지 않는 경우로 나누

어진다. 이전의 많은 연구에서는 제약식을 만족하지

않는 인접해일 경우에 제거하거나 벌칙 함수(penalty

function) 을 이용하여 제약식을 만족하는 인접해로 간

주하였다. 그러나 제안된 알고리즘에서는 복구 함수를 이용하여 제약식을 만족하지 않는 해를 제약식을 만족 하는 해로 바꾸는 방식을 사용한다. 제안된 알고리즘의 복구함수는 두 가지 경우에 대하여 복구과정이 발생한 다. 제안된 알고리즘에서 이동방법을 동작시키면 제약 식을 만족시키지 못하는 경우가 2가지 발생한다. 첫 번 째 경우는 싱크로 직접 데이터를 전송하는 노드가 싱크 로 직접 전송하지 않는 노드를 목적 노드로 선택할 경 우 데이터가 싱크로 전달되지 않는 경우가 발생할 수 있다. 그림 3(b)와 같이 노드 2가 싱크로 데이터를 직접 전송하다가 노드 5로 데이터를 전송하는 경우 노드 2, 4, 5 는 루프가 발생하고 데이터를 싱크로 전송하지 못 하는 경우가 발생한다. 이런 경우에 제안된 알고리즘에 서는 싱크로 직접 전송하던 노드는 싱크로 직접 전송하 는 노드로 계속 유지하거나 인접 노드 중에 싱크로 직 접 전송하는 노드를 목적 노드로 선택하도록 한다. 따 라서 그림 3(b)처럼 노드 2의 인접 노드 중 싱크로 직접 전송하는 노드 1을 목적 노드로 선택하여 문제를 해결 한다. 두 번째 경우는 자신에게 데이터를 전송하는 노 드로 데이터를 전송하여 루프가 발생하는 경우이다. 그 림 3(c)처럼 노드 4가 노드 5를 목적 노드로 선택할 경 우 두 노드 간에는 루프가 발생한다. 이러한 경우 자신 을 목적 노드로 가지는 노드는 제외하고 나머지 노드 중에 하나를 랜덤하게 선택하여 목적 노드로 바꾼다.

4.5 종료 기준

제안된 알고리즘의 정지 기준은 미리 정해진 진행 횟 수에 의해 결정된다. 즉 현재해에 대하여 이동방법을 수행하여 새로운 인접해를 발생시켰을 때 성능이 개선 되지 않는 횟수가 정해진 횟수만큼 진행되면 알고리즘 이 종료된다.

Ⅴ. 성능평가

본 논문에서는 MLDA 문제에 대한 제안된 SA 알고 리즘의 성능을 컴퓨터 시뮬레이션을 이용하여 평가하 였다. 모든 실험은 Windows OS 기반의 2GB 메모리와 1.8GHz Pentium 4 로 구성된 PC상에서 수행되었으며, 각 알고리즘은 C++ 언어를 이용하여 구현되었다. 제안 된 알고리즘의 성능을 비교평가하기 위해 네트워크 수

명과 실행시간 관점에서 기존에 제안된 FEGASIS[12]

및 FEDAP-PA[13]과 비교하였다. 성능평가는 100 × 100m

크기의 네트워크에서 노드의 수는 300에서 1000 까지 설정하였으며 각 노드의 전송 범위는 15m로 구성 된 토폴로지에 대해서 수행되었다. 식 (4)와 (5)에서 사 용되는 e

는 50nJ, e

는 100pJ로 설정하였으며, 제안 된 SA 알고리즘에 사용되는 반복횟수는 50000으로 설 정하였다.

Time (rounds)

0 100 200 300 400 500 600 700 800

Minimum energy among nodes (nJ)

0 2e+5 4e+5 6e+5 8e+5 1e+6

PEGASIS PEDAP-PA MLDA-SA

(a)

Time (rounds)

0 100 200 300 400 500 600 700 800 900

Minimum energy among nodes (nJ)

0 2e+5 4e+5 6e+5 8e+5 1e+6

PEGASIS PEDAP-PA MLDA-SA

(b)

그림 4. 네트워크상에 에너지를 가장 적게 가지는 노드의 에너지양 (a) N = 500 (b) N = 900

Fig. 4 The amount of energy of node having the lowest remained energy in networks (a) N = 500 (b) N = 900

그림 4는 노드의 수를 500, 900으로 설정했을 때 네

트워크상의 노드 중에 남은 에너지가 가장 적은 노드의

에너지양을 나타낸 결과이다. 시간이 지남에 따라 네트

워크에 배치된 노드는 에너지 소모가 발생한다. 사용되 는 프로토콜에 따라 특정 노드의 에너지양이 다른 노드 의 에너지양보다 많이 소모될 수 있다. 그림에서 제안 된 알고리즘이 기존의 다른 알고리즘에 비해 특정 노드 의 에너지 소모량이 적음을 볼 수 있다. 즉, 모든 노드가 공평하게 에너지를 사용함으로써 네트워크의 수명을 늘일 수 있다는 예측을 할 수 있다. 이러한 결과는 제안 된 SA 알고리즘의 이웃해 탐색방법이 기존의 알고리즘 에서 사용되는 노드선택방법보다 효과적으로 해를 탐 색하고 있음을 알 수 있다. 또한 노드의 수가 많은 네트 워크에서도 기존의 알고리즘보다 성능이 우수함을 볼 수 있다.

Number of nodes

300 400 500 600 700 800 900 1000

Maximum lifetime (rounds)

200 300 400 500 600 700 800 900 1000

PEGASIS PEDAP-PA MLDA-SA

그림 5. 노드 수에 따른 에너지 소멸이 첫 번째 발생하는 노드의 시간

Fig. 5 The time of the first failure node according to the number of nodes

그림 5는 노드의 수를 300에서 1000까지 적용되었 을 때 첫 번째로 에너지 소멸이 발생하는 노드의 시간 을 나타낸 결과이다. 결과값은 각 알고리즘에 대하여 10 번 시도한 것에 대한 평균값을 나타낸 것이다. 그림 4 에서 예측한 대로 전체적으로 제안된 알고리즘이 우 수한 성능을 나타내고 있음을 볼 수 있다. 즉 에너지 소 모로 소실되는 첫 번째 노드의 시간이 다른 알고리즘 에 비해 우수함을 나타내고 있다. 그림 6은 실행시간 관점에서 3가지 알고리즘을 비교한 것이다. 네트워크 수명이 우수함에도 불구하고 제안된 알고리즘이 기존 의 다른 알고리즘과 비슷한 실행시간 내에 동작하고 있음을 보인다.

Number of nodes

300 400 500 600 700 800 900 1000

Computation time (sec)

0 1 2 3 4 5

PEGASIS PEDAP-PA MLDA-SA

그림 6. 노드 수에 따른 계산 시간

Fig. 6 The computation time of the algorithms according to the number of nodes

그림 7은 전송하는 데이터의 패킷 크기가 다른 상황 에서 3가지 알고리즘을 비교한 것이다. 앞선 결과와 비슷하게 제안된 알고리즘이 가장 성능이 우수하며, PEDAP-PA 가 PEGASIS보다 우수함을 볼 수 있다. 이 러한 결과는 제안된 알고리즘에서 사용되는 이웃해 검 색방법인 교환동작과 복구함수가 효과적으로 동작함을 나타낸 것이다. 결과적으로 제안된 알고리즘이 기존의 알고리즘에 비해 비슷한 실행시간 내에서 더 좋은 결과 를 찾고 있음을 알 수 있다. 결론적으로 성능평가 결과 에서 제안된 알고리즘이 NP-hard 문제인 MLDA 문제 를 적정한 실행시간 내에 좋은 결과를 얻을 수 있으며 MLDA 문제를 효과적으로 해결할 수 있음을 알 수 있 었다.

Ⅵ. 결 론

본 논문은 무선 센서 네트워크에 배치된 모든 노드로

부터 데이터를 수집하는 과정에서 네트워크 수명을 최

대화하는 최대 수명 데이터 수집 문제를 위한 시뮬레이

티드 어닐링 알고리즘을 제안하였다. 효과적인 알고리

즘을 설계하기 위해 최대 수명 데이터 수집 문제에 적

합한 인코딩과 초기해 생성, 인접해 검색을 위한 이동

방법과 복구함수를 제안하였다. 제안된 알고리즘을 평

가하기 위해 네트워크 최대 수명과 알고리즘 실행시간

관점에서 기존의 방식과 비교 평가하였다. 비교결과에 서 제안된 알고리즘이 기존의 방식보다 더 우수함을 볼 수 있었으며, 또한 에너지 효율이 중요한 무선 센서 네 트워크에서 최대 수명 데이터 수집 문제를 효과적으로 해결할 수 있음을 볼 수 있었다.

Packet size (bits)

1000 2000 3000 4000 5000

Maximum lifetime (rounds)

0 200 400 600 800

PEGASIS PEDAP-PA MLDA-SA

(a)

Packet size (bits)

1000 2000 3000 4000 5000

Maximum lifetime (rounds)

0 200 400 600 800 1000

PEGASIS PEDAP-PA MLDA-SA

(b)

그림 7. 패킷 크기에 따른 에너지 소멸이 발생하는 첫 번째 노드의 시간 (a) N = 500 (b) N = 1000

Fig. 7 The time of the first failure node according to packet size (a) N = 500 (b) N = 1000

REFERENCES

[ 1 ] I. F. Akyildiz, W. Su, Y. Sankarasubermanian, and E.

Cayirici, “A survey of sensor networks”, IEEE Communications Magazine, vol. 40, pp. 102-14, 2002.

[ 2 ] R. Min, M. Bhardwaj, S. Cho, A. Sinha, E. Shih, A. Wang, and A. Chandrakasan, “Low-power wireless sensor networks”, VLSI Design, 2001.

[ 3 ] Tubaishat. M and Madria. S, “Sensor networks: An overview”, IEEE Potentials, vol. 22, pp. 20-23, Feb. 2003.

[ 4 ] Wang. J and Howitt. I, “Optimal traffic distribution in minimum energy wireless sensor networks”, in 2005 IEEE Global Telecommunications Conference, pp. 3274-3278, 2005.

[ 5 ] J. Stanford and S. Tongngam, “Approximation algorithm for maximum lifetime in wireless sensor networks with data aggregation,” in Proceedings of the Seventh ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel / Distributed Computing (SNPD), pp. 273-277, June 2006.

[ 6 ] K. Kalpakis and S. Tang, “A combinatorial algorithm for the Maximum Lifetime Data Gathering and Aggregation problem in sensor networks,” in Proceedings of the International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), pp. 1-8, June 2008.

[ 7 ] H. O. Tan and I. Korpeoglu, “Power Efficient Data Gathering and Aggregation in Wireless Sensor Networks,”

ACMSIG MOD Record, vol. 32, no. 4, pp. 66-71, Dec.

2003.

[ 8 ] W. Liang and Y. Liu, “Online Data Gathering for Maximizing Network Lifetime in Sensor Networks,” IEEE Transaction on Mobile Computing, vol. 1, no. 2, pp. 2-11, Jan. 2007.

[ 9 ] Y. Wu, S. Fahmy, and N. B. Shroff, “On the Construction of a Maximum-Lifetime Data Gathering Tree in Sensor Networks: NP-Completeness and Approximation Algorithm,” in Proceedings of the IEEE INFOCOM, pp.

356-360, April 2008.

[10] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan,

“Energy efficient communication protocol for wireless microsensor networks,” in 33rd Annual Hawaii International Conference on System Sciences, pp. 3005– 3014, 2000.

[11] S. Lindsey and C. S. Raghavendra, “Pegasis: Power- efficient gathering in sensor information systems,” in IEEE Aerospace Conference, March 2002.

[12] J. Holland, Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, 1975.

[13] D. E. Goldberg, Genetic Algorithms in Search, Optimi- zation & Machine Learning, Addison Wesley, 1989.

[14] J. Antonisse, “A new interpretation of schema notation that

overturns the binary encoding constraint,” in Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 86-91, 1989.

장길웅(Kil-woong Jang)

1997년 2월：경북대학교 컴퓨터공학과 학사 1999년 2월：경북대학교 컴퓨터공학과 석사 2002년 8월：경북대학교 컴퓨터공학과 박사

2003년 3월~현재：한국해양대학교 데이터정보학과 부교수

※ 관심분야 : 네트워크 프로토콜, 센서네트워크, 네트워크 최적화