최근 애드혹 네트워크는 다양한 연구와 개발로 인하여 많은 발전을 이루었으며 이로 인하여 네트워크를 구축하기 어려운 지역에 기반 네트워크 없이 사용자가 쉽게 통신할 수 있는 여건을 마련하였다. 또한 애드혹 네트워크는 산업, 과학, 국방 등 다양한 환경에서 여러 가지 형태로 활용될 수 있다[1].

특히, 전쟁터나 재난지역과 같은 고정된 전송 시스템이 구축되어 있지 않은 곳에서 다수의 이동단말은 하나의 공통된 목표를 수행하기 위해서 이동단말간의 정보를 공유해야 한다. 목표를 달성하기 위해 이동단말은 그룹을 형성하고 각 이동단말은 이웃한 단말과 통신을 한다. 여기서 그룹의 각 단말은 시작지점과 목표지점을 가지며, 시작지점에서 목표지점으로의 경로에 대해서 제한된 시간과 최대 경로길이가 요구된다. 이러한 두가지 제약조건 아래에서 그룹 내의 모든 이동단말 간에 연결수를 최대화하는 문제를 애드혹 네트워크에서의 협력통신문제라고 알려져 있다[2-3].

애드혹 네트워크에서 협력통신문제는 노드의 이동성으로 인해 네트워크 토폴로지가 다른 네트워크에 비해 더 자주 변경됨으로써 이동단말의 경로를 결정하기 위해서는 방대한 계산량이 요구된다. 이 문제는 조합최적화 문제로 NP-hard 문제로 증명되어 있다[4-5]. NP-hard 문제를 해결하기 위해 최근 수행된 대부분의 연구들은 근사치 방식으로 접근하고 있다. 이 방식들중에 최적해(global solution)를 찾기 위해 모든 가능한 후보해(candidate solution)를 나열하여 찾는 모든해 검색 알고리즘(exhaustive search algorithm)이 일반적인 방식이다. 그러나 이 방식은 방대한 계산시간이 소요된다는 단점을 가진다. 계산의 어려움과 계산량을 줄이기 위해 최적해를 찾는 대신에 계산 시간은 줄이고 최적해에 가까운 해를 찾을 수 있는 메타 휴리스틱 알고리즘이 대안으로 제시되고 있다.

본 논문에서는 제한된 시간과 최대 경로길이를 가진 협력통신문제에 대하여 메타 휴리스틱 알고리즘인 유전 알고리즘을 제안한다. 효율적으로 좋은 결과를 얻기 위해 제안된 알고리즘에서는 새로운 이웃해 생성 방식을 제안하며, 제안된 알고리즘을 평가하기 위해 다양한 조건하에서 최대 노드 연결수와 알고리즘 실행 시간 관점에서 기존의 다른 알고리즘과 비교 평가한다.

협력조정(cooperative control)은 공통된 목표를 달성하기 위해 정보를 공유하는 다수의 동적 개체간의 조정을 의미한다. 예를 들어, 제조공장에서 동작하는 로봇간의 조정, 탐사 무인 비행기간의 조정, 구조 작업, 군사 감시, 공격 임무 등 다양한 환경에서 협력조정은 사용될 수 있다. Butenko et al.은 협력조정시스템과 관련된 모델, 응용, 알고리즘을 제안하였다[2-3]. 이 논문에서는 애드혹 네트워크와 협력조정을 통합할 수 있는 최적화 연구가 일부 이루어졌다. Oliveira and Pardalos는 네트워크에서 목적지가 주어진 상황에서 특정 목표룰 가진 클라이언트의 그룹에 대하여 통신시간을 최대화하는 문제를 수학으로 정식화(formulation)하였다[4-5]. 이들은 우선 애드혹 네트워크에서 협력조정을 이용하여 연결시간을 최대화하는 목적함수를 제안하였다. Commander et al.은 협력통신문제를 해결하기 위해 메타 휴리스틱 알고리즘의 하나인 지역검색(local search) 방식을 제안하였다[6]. 이 논문에서는 지역검색알고리즘을 위해 구축알고리즘(construction algorithm)과 검색을 향상시키기 위한 지역향상방식(local improvement method)를 제안하였다. 하지만, 이 논문에서는 작은 규모의 네트워크에서만 성능을 평가함으로써 알고리즘 확장성(scalability) 능력을 보이지는 못했다.

제안된 알고리즘을 기술하기에 앞서 협력통신문제를 정식화하기 위해 제안된 유전 알고리즘[7-8]에서 사용되는 기호를 우선 정의한다.

표기

V Set of candidate locations   vx xth candidate location   E Set of edges between vx and vy   N Number of candidate locations   mx xth mobile node   M Number of mobile nodes   Z Set of routes of mobile nodes   zx Route of mx   ζxy yth location of zx   S Set of source locations   D Set of destination locations   sx Source location of zx   dx Destination location of zx   T Time limit   R Transmission range   L Set of distance threshold   lx Distance threshold of zx

기존의 무선 네트워크와 달리 애드혹 네트워크는 제한된 메모리, 짧은 전송거리, 저전력 배터리를 가진 노드로 구성되어있다. 애드혹 네트워크를 위한 알고리즘 개발을 위해서는 고려해야 할 부분이다. 이러한 조건을 고려하여 본 논문에서는 애드혹 네트워크에서 협력통신문제에 대한 네트워크 모델과 제약조건을 우선 기술한다. 네트워크 모델은 비방향성 그래프인 G = (V, E)로 나타낼 수 있으며, V는 이동노드의 위치후보의 집합을 의미하며, E는 위치후보간의 연결을 나타내는 에지의 집합을 의미한다. 각 에지의 길이는 노드의 전송거리보다는 짧다. 이동노드의 집합을 U라고 정의하고, 집합 U에 대하여 각 노드의 시작위치와 목적위치를 각각 S = {s₁, s₂, …, s_M}와 D = {d₁, d₂, …, d_M}로 정의한다.

각 노드의 제한시간 T와 제한거리 L가 주어질 때, 협력통신의 목적함수는 각 이동노드간의 연결을 최대화하는 경로의 집합을 결정하는 것이다. 경로는 각 노드의 시작위치에서 반드시 시작하여야 하며, 모든 이동노드는 제한시간 T이내에 목적위치에 도착해야한다. 제한시간이내의 각 순간시간 t ∈ {1, 2. …, T}에서 이동노드는 이전 위치z_x(t-1)에 머물거나 인접함수 f_n(z_x(t-1))에 의해 결정된 이웃위치로 이동해야 된다. 저전력의 배터리를 가진 이동노드의 제약조건에 대하여 제한거리 L = {l₁, l₂, …, l_M}를 적용한다. 각 이동노드에 대한 경로의 전체거리는 제한거리보다 짧아야 한다. 경로의 거리는 유클리드 거리함수 f_d(s_x, d_x)에 의해 결정된다.

본 논문의 목적함수는 애드혹 네트워크에서 이동노드간의 연결수를 최대화하는 것이다. 따라서 제안된 네트워크 모델에서 협력통신문제는 다음과 같은 목적함수를 최대화하는 조합 최적화 문제로 정식화할 수 있다.

최대화

관하여

식 (1)은 모든 순간시간에 대하여 이동노드간의 연결을 최대화하는 목적함수를 나타낸다. 식 (2)는 순간시간 t에서 ζ_xt와 ζ_yt 간의 거리가 전송거리보다 짧은 경우 1을 돌려주고 그렇지 않을 경우 0을 돌려주는 함수를 나타낸다. 식 (3)은 각 이동노드의 시작위치와 목적위치는 각각 s_x와 d_x여야 함을 나타낸다. 식 (4)는 이동노드의 다음 위치는 이전 위치에 있거나 이웃 위치 중 하나로 이동해야함을 의미한다. 식 (5)는 각 이동노드의 경로 총 길이는 제한거리보다 짧아야함을 나타낸다.

협력통신문제를 위한 제안된 유전 알고리즘은 다음과 같은 진행순서로 이루어진다.

다음 절에서 제안된 유전 알고리즘에서 적용된 염색체 인코딩과 부모 개체군 생성, 교배, 돌연변이, 정지 기준에 대하여 자세히 기술한다.

단계 1. 염색체 인코딩(encoding)

단계 2. 부모 개체군 생성

단계 3. 부모 개체군을 이용한 다음 세대 생성

가. 교배(crossover) 나. 돌연변이(mutation) 다. 우수한 유전자 선택(selection)

제안된 알고리즘에서는 정수를 가진 인코딩 방식을 적용한다[9-10]. 본 논문에서는 염색체를 인코딩하기 위해 2개의 테이블이 필요하다. 즉, 하나의 후보위치에서 인접한 후보위치까지의 거리를 나타내는 거리 테이블과 각 후보위치로부터 전송범위 내에 존재하는 후보 위치를 나타내는 인접 테이블이 요구된다. 2가지 테이블을 이용하여 그림 1과 같이 각 이동노드의 경로로 구성된 리스트가 하나의 염색체를 구성한다.

제안된 염색체 인코딩 방식을 이용하여 유전 알고리즘에 적용할 부모 개체군을 생성한다. 부모 개체군 생성은 모든 이동노드에 대하여 시간변수 t가 1에서 T까지 변함에 따라 시작위치에서 목적위치까지의 경로를 가진 해(chromosome)를 정해진 개수(population)만큼 발생시키는 과정이다.

순간시간 t = 1일 때, 해의 첫 번째 요소는 이동노드에 미리 정해진 시작위치로 결정된다. 제안된 알고리즘에서는 최초 부모 개체군을 생성하기 위해 플로이드 알고리즘을 이용하여 2차원 배열로 모든 이동노드에 대한 최단경로정보를 우선적으로 저장한다. 특히 최초 부모 개체군의 결과를 높이기 위해 하나의 비율 w를 사용하여 각 경로의 위치를 균형 있게 배치시킨다. 여기서 비율 w는 각 이동노드의 제한시간 T를 최단경로길이로 나눈 값으로 결정된다.

즉, 남은 시간에 비해 경로의 길이가 많이 남으면 이전 위치에 계속 머물게 하는 효과를 가진다. 이러한 과정을 완전한 하나의 염색체가 만들어질 때까지 수행하며, 이러한 과정을 정해진 염색체 개수(population)만큼 반복한다. 그림 2는 부모 개체군을 생성하는 과정을 순서도로 나타낸 것이다.

S제안된 유전 알고리즘의 교배는 확률 P_c에 따라 두개의 염색체간에 발생한다. 제안된 알고리즘의 교배는 다음과 같이 동작한다.

단계 1. 전체 개체군의 염색체를 두 개씩 쌍으로 구성 단계 2. 무작위로 교배점(crossover point)을 선택하고, 쌍을 이룬 염색체에서 같은 교배점이후의 모든 유전자를 교환 단계 3. 새로 생성된 염색체에 대하여 적합도 검사. 만약 적합할 경우 새로운 염색체로 채택하고 그렇지 못할 경우 다시 단계 2 시도 단계 4. N × Pc번만큼 단계 1을 반복

그림 3은 제안된 알고리즘의 절차를 보여주기 위해 나타낸 하나의 네트워크 예이다. 그림 3은 편의상 4 × 4 그리드 형태의 네트워크로 구분하였으며, 3개의 이동노드와 27개의 후보위치를 가진 네트워크이다. 네트워크상의 동그라미는 이동노드의 후보위치를 나타내며, 3개의 이동노드 m₁, m₂, m₃의 시작위치는 1, 2, 4이고, 목적위치는 18, 27, 26이 된다.

그림 4는 제안된 유전 알고리즘의 교배를 그림 3의 네트워크 예를 이용하여 나타낸 것이다. 제안된 알고리즘의 교배는 전체 개체군에서 랜덤하게 2개의 염색체를 선택하고, 교배점을 랜덤하게 한개 선택한다. 만약 교배점의 위치가 z₁의 6번째 유전자가 선택되었다면 z₁의 6번째 유전자 이후의 모든 유전자를 상대 염색체의 같은 위치 유전자와 교환한다. 염색체 1과 2의 같은 위치의 유전자를 모두 교환한다. 만약 교배에 의해 교환이 발생했을 때 교배점을 중심으로 교배점 이전의 위치(5번째 유전자)와 교환된 교배점의 위치(6번째 유전자)가 이동노드의 전송거리보다 더 멀 경우 부적합한 염색체로 판단하여 다시 원점에서 교배를 수행한다. 이러한 적합검사를 통해 적합한 새로운 염색체가 나올 때까지 교배를 수행한다.

제안된 유전 알고리즘에서 돌연변이는 확률 P_m에 따라 염색체의 유전자에 적용된다. 일반적으로 돌연변이는 지역 영역에 빠지지 않도록 하기 위해 유전자의 염색체를 교환하거나 뒤집는 동작을 한다. 제안된 알고리즘의 돌연변이 절차는 다음과 같다.

단계 1. 염색체 개체군 중 한 개의 염색체와 그 염색체의 유전자 중 한 개(X)를 랜덤하게 선택 단계 2. 선택된 유전자의 인접 후보위치 중 한 개(K)를 랜덤하게 선택 단계 3. 선택된 유전자 X 다음의 유전자를 K로 교환 단계 4. 새로 생성된 염색체에 대하여 적합도 검사. 만약 적합할 경우 새로운 염색체로 채택하고 그렇지 못할 경우 다시 단계 2 시도 단계 5. N × Pm번만큼 단계 1을 반복

그림 5는 제안된 유전 알고리즘의 돌연변이를 그림 3의 네트워크 예를 이용하여 나타낸 것이다. 염색체에서 z₁의 첫 번째 유전자가 선택되었다면, 유전자 1의 인접 후보위치(2, 3, 4, 5) 중 한 개를 선택한다. 만약 2가 선택 되었다면 선택된 위치의 다음 위치 유전자 4와 교환한다. 이 때 염색체에서 유전자 4는 두 번째와 세 번째에 걸쳐 존재함으로 두 개의 유전자를 모두 2로 교환한다. 돌연변이를 수행한 후 교배와 마찬가지로 적합도 검사를 수행하여 부적합한 새로운 염색체일 경우에는 다시 돌연변이 동작을 수행한다.

제안된 유전 알고리즘의 정지 기준은 미리 정해진 세대 진행 회수에 의해 결정된다. 즉 기존 개체군에 대하여 교배와 돌연변이를 진행한 후 새로운 세대를 발생시킨 횟수가 정해진 횟수만큼 진행되면 알고리즘을 멈춘다.

본 논문에서는 협력통신문제에 대한 제안된 유전 알고리즘의 성능을 컴퓨터 시뮬레이션을 이용하여 평가하였다. 모든 실험은 Windows OS 기반의 2GB 메모리와 2.4GHz Intel processor로 구성된 PC상에서 수행되었으며, 각 알고리즘은 C++ 언어를 이용하여 구현되었다. 제안된 알고리즘의 성능을 비교평가하기 위해 최대 노드 연결 수와 실행시간 관점에서 랜덤(Random)방법과 기존에 제안된 지역검색(Local search)방법[6]과 비교하였다.

성능평가를 위해 전송범위(R)는 10과 15, 후보위치의 갯수(N)는 500과 1000로 구성된 100 × 100 m² 크기의 네트워크를 랜덤하게 생성하여 수행하였다. 생성된 각 네트워크에서 이동노드의 수(M)는 20과 30, 제한시간(T)는 20과 25로 설정하여 성능평가를 수행하였다. 유전 알고리즘에 사용되는 개체군의 수는 100으로 설정하였으며, 교배 확률인 P_c는 1, 돌연변이 확률인 P_m는 0.05로 설정하였다. 각 알고리즘은 10번씩 시도하여 평균값으로 결과로 나타내었다.

그림 6과 7은 이동노드의 수가 변할 때 10개의 다른 네트워크 예제에 대한 연결수를 비교한 것이다. 성능평가에서 네트워크를 4 × 4형태의 그리드로 구분하여 이동노드의 시작위치(s_x)와 목적위치(d_x)를 (1, 1)과 (4, 4) 그리드 내에 임의의 위치로 설정하였다. 또한 각 이동노드의 제한거리(l_x)는 각 이동노드의 가장 짧은 경로 길이의 1.5배로 가정하였다.

그림 6은 최대 노드 연결수 관점에서 후보위치의 수가 500일 때 제안된 알고리즘과 기존의 방법인 지역검색방법과 랜덤방법을 비교한 것이다. 그림에서 제안된 알고리즘이 기존의 방법에 비해 모든 네트워크 예제에서 성능이 우수함을 볼 수 있다. 그림 7은 후보위치의 수가 1000일 때 제안된 알고리즘과 기존의 방법과 비교 평가한 것이다. 네트워크의 밀집도가 더 커진 상황에서도 제안된 알고리즘은 기존의 방법보다 성능이 우수함을 볼 수 있다.

그림 6과 7에서 제안된 유전 알고리즘이 기존의 검색방법인 지역검색방법보다 성능이 우수한 이유는 지역검색방법은 로컬 최적해에 수렴한 반면에 제안된 알고리즘은 보다 향상된 결과를 가진 해에서 수렴하기 때문이다. 즉, 제안된 유전 알고리즘의 이웃해 생성방법인 교배와 돌연변이 동작이 효과적으로 동작하고 있음을 알 수 있다. 이 결과에서 어떠한 검색을 수행하지 않는 랜덤방법이 가장 좋지 않은 결과를 발생시키며, 반면에 이웃해 검색을 하는 제안된 알고리즘과 지역검색방법이 보다 좋은 결과를 보임을 알 수 있다.

그림 8은 전송범위와 후보위치의 수를 조합한 조건에서 알고리즘의 평균 계산시간을 비교한 것이다. 평균 계산시간은 10개의 네트워크 예제에 대하여 계산시간의 총합을 평균해서 나타낸 시간이다. 그림에서 이웃해 생성을 하지 않는 랜덤방법이 가장 빠르며 제안된 알고리즘이 지역검색방법보다 조금 더 빠름을 볼 수 있다. 결과적으로 제안된 알고리즘이 기존의 방법에 비해 비슷한 실행시간 내에서 더 좋은 결과를 찾고 있음을 알 수 있다.

결론적으로 성능평가 결과에서 제안된 알고리즘이 NP-hard 문제인 협력통신문제를 적정한 실행시간 내에 좋은 결과를 얻을 수 있으며 협력통신문제를 효과적으로 해결할 수 있음을 알 수 있었다.

본 논문은 애드혹 네트워크에서 협력통신을 위한 이동노드간의 연결수를 최대화하는 유전 알고리즘을 제안하였다. 효과적인 알고리즘을 설계하기 위해 협력통신문제에 적합한 인코딩과 부모개체군 생성, 인접해 검색을 위한 교배와 돌연변이방법을 제안하였다. 제안된 알고리즘을 평가하기 위해 최대 노드 연결 수와 알고리즘 실행시간 관점에서 기존의 방식과 비교 평가하였다. 비교결과에서 제안된 알고리즘이 기존의 방식보다 더 우수함을 볼 수 있었으며, 또한 애드혹 네트워크에서 협력통신문제를 효과적으로 해결할 수 있음을 볼 수 있었다.