This paper proposes a genetic algorithm to maximize the connectivity among the mobile nodes for the cooperative communication in ad-hoc networks. In general, as the movement of the mobile nodes in the networks increases, the amount of calculation for finding the solution would be too much increased. To obtain the optimal solution within a reasonable computation time for a high-density network, we propose a genetic algorithm to obtain the optimal solution for maximizing the connectivity. In order to make a search more efficient, we propose some efficient neighborhood generating operations of the genetic algorithm. We evaluate those performances through some experiments in terms of the maximum number of connections and the execution time of the proposed algorithm. The comparison results show that the proposed algorithm outperforms other existing algorithms.
최근 애드혹 네트워크는 다양한 연구와 개발로 인하여 많은 발전을 이루었으며 이로 인하여 네트워크를 구축하기 어려운 지역에 기반 네트워크 없이 사용자가 쉽게 통신할 수 있는 여건을 마련하였다. 또한 애드혹 네트워크는 산업, 과학, 국방 등 다양한 환경에서 여러 가지 형태로 활용될 수 있다[1].
특히, 전쟁터나 재난지역과 같은 고정된 전송 시스템이 구축되어 있지 않은 곳에서 다수의 이동단말은 하나의 공통된 목표를 수행하기 위해서 이동단말간의 정보를 공유해야 한다. 목표를 달성하기 위해 이동단말은 그룹을 형성하고 각 이동단말은 이웃한 단말과 통신을 한다. 여기서 그룹의 각 단말은 시작지점과 목표지점을 가지며, 시작지점에서 목표지점으로의 경로에 대해서 제한된 시간과 최대 경로길이가 요구된다. 이러한 두가지 제약조건 아래에서 그룹 내의 모든 이동단말 간에 연결수를 최대화하는 문제를 애드혹 네트워크에서의 협력통신문제라고 알려져 있다[2-3].
애드혹 네트워크에서 협력통신문제는 노드의 이동성으로 인해 네트워크 토폴로지가 다른 네트워크에 비해 더 자주 변경됨으로써 이동단말의 경로를 결정하기 위해서는 방대한 계산량이 요구된다. 이 문제는 조합최적화 문제로 NP-hard 문제로 증명되어 있다[4-5]. NP-hard 문제를 해결하기 위해 최근 수행된 대부분의 연구들은 근사치 방식으로 접근하고 있다. 이 방식들중에 최적해(global solution)를 찾기 위해 모든 가능한 후보해(candidate solution)를 나열하여 찾는 모든해 검색 알고리즘(exhaustive search algorithm)이 일반적인 방식이다. 그러나 이 방식은 방대한 계산시간이 소요된다는 단점을 가진다. 계산의 어려움과 계산량을 줄이기 위해 최적해를 찾는 대신에 계산 시간은 줄이고 최적해에 가까운 해를 찾을 수 있는 메타 휴리스틱 알고리즘이 대안으로 제시되고 있다.
본 논문에서는 제한된 시간과 최대 경로길이를 가진 협력통신문제에 대하여 메타 휴리스틱 알고리즘인 유전 알고리즘을 제안한다. 효율적으로 좋은 결과를 얻기 위해 제안된 알고리즘에서는 새로운 이웃해 생성 방식을 제안하며, 제안된 알고리즘을 평가하기 위해 다양한 조건하에서 최대 노드 연결수와 알고리즘 실행 시간 관점에서 기존의 다른 알고리즘과 비교 평가한다.
협력조정(cooperative control)은 공통된 목표를 달성하기 위해 정보를 공유하는 다수의 동적 개체간의 조정을 의미한다. 예를 들어, 제조공장에서 동작하는 로봇간의 조정, 탐사 무인 비행기간의 조정, 구조 작업, 군사 감시, 공격 임무 등 다양한 환경에서 협력조정은 사용될 수 있다. Butenko
제안된 알고리즘을 기술하기에 앞서 협력통신문제를 정식화하기 위해 제안된 유전 알고리즘[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
기존의 무선 네트워크와 달리 애드혹 네트워크는 제한된 메모리, 짧은 전송거리, 저전력 배터리를 가진 노드로 구성되어있다. 애드혹 네트워크를 위한 알고리즘 개발을 위해서는 고려해야 할 부분이다. 이러한 조건을 고려하여 본 논문에서는 애드혹 네트워크에서 협력통신문제에 대한 네트워크 모델과 제약조건을 우선 기술한다. 네트워크 모델은 비방향성 그래프인
각 노드의 제한시간
본 논문의 목적함수는 애드혹 네트워크에서 이동노드간의 연결수를 최대화하는 것이다. 따라서 제안된 네트워크 모델에서 협력통신문제는 다음과 같은 목적함수를 최대화하는 조합 최적화 문제로 정식화할 수 있다.
최대화
관하여
식 (1)은 모든 순간시간에 대하여 이동노드간의 연결을 최대화하는 목적함수를 나타낸다. 식 (2)는 순간시간
협력통신문제를 위한 제안된 유전 알고리즘은 다음과 같은 진행순서로 이루어진다.
다음 절에서 제안된 유전 알고리즘에서 적용된 염색체 인코딩과 부모 개체군 생성, 교배, 돌연변이, 정지 기준에 대하여 자세히 기술한다.
단계 1. 염색체 인코딩(encoding)
단계 2. 부모 개체군 생성
단계 3. 부모 개체군을 이용한 다음 세대 생성
가. 교배(crossover) 나. 돌연변이(mutation) 다. 우수한 유전자 선택(selection)
제안된 알고리즘에서는 정수를 가진 인코딩 방식을 적용한다[9-10]. 본 논문에서는 염색체를 인코딩하기 위해 2개의 테이블이 필요하다. 즉, 하나의 후보위치에서 인접한 후보위치까지의 거리를 나타내는 거리 테이블과 각 후보위치로부터 전송범위 내에 존재하는 후보 위치를 나타내는 인접 테이블이 요구된다. 2가지 테이블을 이용하여 그림 1과 같이 각 이동노드의 경로로 구성된 리스트가 하나의 염색체를 구성한다.
제안된 염색체 인코딩 방식을 이용하여 유전 알고리즘에 적용할 부모 개체군을 생성한다. 부모 개체군 생성은 모든 이동노드에 대하여 시간변수
순간시간
즉, 남은 시간에 비해 경로의 길이가 많이 남으면 이전 위치에 계속 머물게 하는 효과를 가진다. 이러한 과정을 완전한 하나의 염색체가 만들어질 때까지 수행하며, 이러한 과정을 정해진 염색체 개수(population)만큼 반복한다. 그림 2는 부모 개체군을 생성하는 과정을 순서도로 나타낸 것이다.
S제안된 유전 알고리즘의 교배는 확률
단계 1. 전체 개체군의 염색체를 두 개씩 쌍으로 구성 단계 2. 무작위로 교배점(crossover point)을 선택하고, 쌍을 이룬 염색체에서 같은 교배점이후의 모든 유전자를 교환 단계 3. 새로 생성된 염색체에 대하여 적합도 검사. 만약 적합할 경우 새로운 염색체로 채택하고 그렇지 못할 경우 다시 단계 2 시도 단계 4. N × Pc번만큼 단계 1을 반복
그림 3은 제안된 알고리즘의 절차를 보여주기 위해 나타낸 하나의 네트워크 예이다. 그림 3은 편의상 4 × 4 그리드 형태의 네트워크로 구분하였으며, 3개의 이동노드와 27개의 후보위치를 가진 네트워크이다. 네트워크상의 동그라미는 이동노드의 후보위치를 나타내며, 3개의 이동노드
그림 4는 제안된 유전 알고리즘의 교배를 그림 3의 네트워크 예를 이용하여 나타낸 것이다. 제안된 알고리즘의 교배는 전체 개체군에서 랜덤하게 2개의 염색체를 선택하고, 교배점을 랜덤하게 한개 선택한다. 만약 교배점의 위치가
제안된 유전 알고리즘에서 돌연변이는 확률
단계 1. 염색체 개체군 중 한 개의 염색체와 그 염색체의 유전자 중 한 개(X)를 랜덤하게 선택 단계 2. 선택된 유전자의 인접 후보위치 중 한 개(K)를 랜덤하게 선택 단계 3. 선택된 유전자 X 다음의 유전자를 K로 교환 단계 4. 새로 생성된 염색체에 대하여 적합도 검사. 만약 적합할 경우 새로운 염색체로 채택하고 그렇지 못할 경우 다시 단계 2 시도 단계 5. N × Pm번만큼 단계 1을 반복
그림 5는 제안된 유전 알고리즘의 돌연변이를 그림 3의 네트워크 예를 이용하여 나타낸 것이다. 염색체에서
제안된 유전 알고리즘의 정지 기준은 미리 정해진 세대 진행 회수에 의해 결정된다. 즉 기존 개체군에 대하여 교배와 돌연변이를 진행한 후 새로운 세대를 발생시킨 횟수가 정해진 횟수만큼 진행되면 알고리즘을 멈춘다.
본 논문에서는 협력통신문제에 대한 제안된 유전 알고리즘의 성능을 컴퓨터 시뮬레이션을 이용하여 평가하였다. 모든 실험은 Windows OS 기반의 2GB 메모리와 2.4GHz Intel processor로 구성된 PC상에서 수행되었으며, 각 알고리즘은 C++ 언어를 이용하여 구현되었다. 제안된 알고리즘의 성능을 비교평가하기 위해 최대 노드 연결 수와 실행시간 관점에서 랜덤(Random)방법과 기존에 제안된 지역검색(Local search)방법[6]과 비교하였다.
성능평가를 위해 전송범위(
그림 6과 7은 이동노드의 수가 변할 때 10개의 다른 네트워크 예제에 대한 연결수를 비교한 것이다. 성능평가에서 네트워크를 4 × 4형태의 그리드로 구분하여 이동노드의 시작위치(
그림 6은 최대 노드 연결수 관점에서 후보위치의 수가 500일 때 제안된 알고리즘과 기존의 방법인 지역검색방법과 랜덤방법을 비교한 것이다. 그림에서 제안된 알고리즘이 기존의 방법에 비해 모든 네트워크 예제에서 성능이 우수함을 볼 수 있다. 그림 7은 후보위치의 수가 1000일 때 제안된 알고리즘과 기존의 방법과 비교 평가한 것이다. 네트워크의 밀집도가 더 커진 상황에서도 제안된 알고리즘은 기존의 방법보다 성능이 우수함을 볼 수 있다.
그림 6과 7에서 제안된 유전 알고리즘이 기존의 검색방법인 지역검색방법보다 성능이 우수한 이유는 지역검색방법은 로컬 최적해에 수렴한 반면에 제안된 알고리즘은 보다 향상된 결과를 가진 해에서 수렴하기 때문이다. 즉, 제안된 유전 알고리즘의 이웃해 생성방법인 교배와 돌연변이 동작이 효과적으로 동작하고 있음을 알 수 있다. 이 결과에서 어떠한 검색을 수행하지 않는 랜덤방법이 가장 좋지 않은 결과를 발생시키며, 반면에 이웃해 검색을 하는 제안된 알고리즘과 지역검색방법이 보다 좋은 결과를 보임을 알 수 있다.
그림 8은 전송범위와 후보위치의 수를 조합한 조건에서 알고리즘의 평균 계산시간을 비교한 것이다. 평균 계산시간은 10개의 네트워크 예제에 대하여 계산시간의 총합을 평균해서 나타낸 시간이다. 그림에서 이웃해 생성을 하지 않는 랜덤방법이 가장 빠르며 제안된 알고리즘이 지역검색방법보다 조금 더 빠름을 볼 수 있다. 결과적으로 제안된 알고리즘이 기존의 방법에 비해 비슷한 실행시간 내에서 더 좋은 결과를 찾고 있음을 알 수 있다.
결론적으로 성능평가 결과에서 제안된 알고리즘이 NP-hard 문제인 협력통신문제를 적정한 실행시간 내에 좋은 결과를 얻을 수 있으며 협력통신문제를 효과적으로 해결할 수 있음을 알 수 있었다.
본 논문은 애드혹 네트워크에서 협력통신을 위한 이동노드간의 연결수를 최대화하는 유전 알고리즘을 제안하였다. 효과적인 알고리즘을 설계하기 위해 협력통신문제에 적합한 인코딩과 부모개체군 생성, 인접해 검색을 위한 교배와 돌연변이방법을 제안하였다. 제안된 알고리즘을 평가하기 위해 최대 노드 연결 수와 알고리즘 실행시간 관점에서 기존의 방식과 비교 평가하였다. 비교결과에서 제안된 알고리즘이 기존의 방식보다 더 우수함을 볼 수 있었으며, 또한 애드혹 네트워크에서 협력통신문제를 효과적으로 해결할 수 있음을 볼 수 있었다.