Survey Paper: 생체모방기술 초청책임위원 : 정영욱 (광운대) 생체모방 알고리즘 기반 통신 네트워크 기술 최현호, 이정륜 국립한경대학교, 중앙대학교 요 약 수십 억년 동안 진화를 거듭해온 지구상의 생명체들은 외부의 제어 없이 독자적으로 단순한 행동 규칙에 따라 기능을 수행하 여 주어진 목적의 최적해를 달성한다. 이러한 다양한 생명체의 행동 원리를 모델링하여 만든 알고리즘을 생체모방 알고리즘 (Bio-Inspired Algorithm)이라 한다. 생체모방 알고리즘은 다 수의 개체가 존재하며, 주변 환경이 동적으로 변하고, 가용 자 원의 제약이 주어지며, 이질적인 특성을 갖는 개체들이 분산 및 자율적으로 움직이는 환경에서 안정성, 확장성, 적응성과 같은 특징을 보여주는데, 이는 통신 네트워크 환경 및 서비스 요구사 항과 유사성을 갖는다. 본 논문에서는 대표적인 생체모방 알고 리즘으로 통신 및 네트워킹 기술로 사용되는 Ant Colony 알고 리즘, Bee 알고리즘, Firefly 알고리즘, Flocking 알고리즘에 대해 살펴보고, 관련 프로젝트 및 연구 동향을 정리한다. 이를 통해 현재의 생체모방 알고리즘의 한계를 극복하고 미래 통신 및 네트워킹 기술이 나아갈 방향을 제시한다. 현재까지 연구되어 온 생체모방 알고리즘의 예로서 생체의 진 화과정을 모델링한 유전자 (Genetic) 알고리즘, 개미들이 페르 몬 분비를 기반으로 최적의 길을 찾는 과정을 모델링한 개미집 단 최적화 (Ant Colony Optimization: ACO) 알고리즘, 반딧 불의 발광 주기의 동기화 과정을 묘사한 반딧불 (Firefly) 알고 리즘, 꿀벌들의 먹이 찾는 행동을 모델링한 꿀벌 (Bee) 알고리 즘 등이 있다. Ⅰ. 서 론 생태계를 구성하고 있는 각 생물체들은 외부의 제어 없이 독 자적으로 매우 단순하고 적은 수의 행동 규칙의 준수를 통하여 해당 생태계의 유지, 관리 및 동기화 등의 기능을 수행한다 [1]. 이처럼 지구상의 다양한 생물체의 행동 원리를 관찰하여 모델 링한 알고리즘을 생체모방 알고리즘 (Biologically Inspired 또 는 Bio-Inspired Algorithm)이라 한다. 생체모방 알고리즘은 각 개체들의 행동을 일괄 제어하는 하향식 중앙 집중적 제어 방 식과는 달리 각 개체가 간단한 동작 원칙을 독자적으로 수행하 여 전체적으로 일관된 모습을 갖출 수 있게 하는 상향식 분산처 리 형 알고리즘이다. 이러한 생체모방 알고리즘은 주로 최적화 문제에 많이 응용되어 왔으며, 공학은 물론 인문 사회학 분야 에서도 널리 적용되어 왔다 [2]. 그림 1. 자연계의 자기질서화 현상 특히 최근 들어 날아다니는 새 떼, 야생에서의 동물 떼, 물고 기 떼, 그리고 박테리아 떼 등과 같은 생물 집단에서 쉽게 관찰 할 수 있는 집중과 질서화된 운동, 즉 <그림 1>과 같은 자기 질 서화 (Self-Ordered) 현상을 모델링한 군집 이론 (Flocking Theory)에 관한 연구가 활발히 진행되고 있다. 군집 현상은 무 질서한 개체들이 외부 작용 없이 스스로 질서화된 상태로 변해 가는 현상을 총칭하며, <그림 2>와 같은 분리성 (Separation), 정렬성 (Alignment), 결합성 (Cohesion)의 세 가지 법칙을 따 른다 [3]. 첫 번째 분리성은 각 개체는 서로 일정한 간격을 유지 해야 한다는 것이며, 두 번째 정렬성은 각 개체는 그 주변 개체 들의 이동 방향의 평균값으로 자신의 이동 방향을 제어함을 의 62 정보와 통신
미하며, 마지막 결합성은 각 개체가 주변 개체들과 동일한 거리 를 유지하도록 자신의 위치를 정하는 것을 의미한다. 군집 이론은 1986년 Reynolds에 의해 처음 컴퓨터 시뮬레이 션이 이루어진 이후 많은 분야에서 이를 활용한 연구 결과들이 나오고 있다. 특히 F. Cucker와 S. Smale [4]은 각 개체들이 군집 이론의 세 가지 조건들을 분산 방식으로 수행하고, 각 개 체들의 초기 속도와 위치가 특정 값의 범위에 있었다면 일정 시 간이 지난 후에 모든 개체의 속도와 위치는 각 개체들의 초기 속도와 위치의 평균값으로 수렴한다는 사실을 수학적으로 증명 하였다. 이 후 관련 연구가 매우 활발히 진행되고 있는 상황이 다 [5]-[9]. Cucker-Smale 모델은 그 특성상 각 개체에서 정 보의 분산 처리를 가정하고 있어서 분산 처리가 요구되는 분야 에서 최적해를 구하는데 이론적인 바탕을 제공한다. 본 논문에서는 통신 시스템과 생체 시스템의 유사성을 정성적 으로 분석하여 생체모방 알고리즘이 통신망의 주요 문제에 대 한 해결책이 될 수 있음을 보이고, 지금까지 통신망에 적용된 대표적인 생체모방 알고리즘인 Ant Colony 알고리즘, Bee 알 고리즘, Firefly 알고리즘, Flocking 알고리즘에 대해 자세히 살펴본다. 아울러 생체모방 관련 연구 현황을 정리 분석함으로 써 앞으로 나타날 미래 통신 및 네트워킹 기술을 위한 연구 이 슈를 제시한다. Ⅱ. 통신망의 문제점과 생체모방 알고리즘의 필요성 본 장에서는 통신 및 네트워킹 시스템에서 발생하는 주된 문 제점과 생체 시스템과의 유사성에 대해 설명하고, 해당 이슈를 해결하는 생체 시스템의 접근 방안을 소개함으로써 통신 및 네 트워킹 기술 분야에서 생체모방 알고리즘의 필요성에 대해서 논의한다. 그림 2. 군집 이론의 분리성, 정렬성, 결합성 2.1 대규모 네트워킹 구성 노드 수 측면에서 미래 인터넷의 규모는 현재보다 수 자 리수가 더 늘어날 것으로 예상된다 [10]. 유비쿼터스 센서 네트 워크 (Ubiquitous Sensor Network: USN) 및 이동 애드혹 네 트워크 (Mobile Ad-Hoc Network: MANET)의 경우 현재에서 미래 응용 서비스에 대하여 수백에서 수십만까지의 노드 수를 고려하고 있다. 노드 수의 증가로 인한 첫 번째 문제점은 네트워크에 매우 큰 부하를 야기한다는 것이다. 발생하는 트래픽 부하는 손쉽게 네 트워크 용량을 넘어설 것이고, 이로 인해 전송 경로 상의 혼잡 및 충돌이 발생하고, 패킷 손실로 이어져 통신의 신뢰성에 타격 을 줄 것이다. 이를 해결하기 위한 적당한 노드 수의 선택은 시 스템의 복잡도를 증가시키며 신뢰성 보장을 위한 제어 정보의 보고 주기도 망의 규모와 함께 증가한다. 또한, 망 규모의 증가 에 따라 연결 가능한 경로가 증가하므로 최적 경로 선정을 위한 탐색 공간이 급격하게 증가하며, 경로 결정을 위해 유지해야 하 는 라우팅 테이블의 수, 테이블 갱신을 위한 제어 정보 교환 오 버헤드 등이 똑같이 증가하게 된다. 하지만 USN 및 MANET 과 같은 대규모 네트워크 환경에서 기존 기술로는 수많은 노드 의 설치 및 효과적인 통신과 유지 관리가 불가능하다. 따라서 네트워킹 알고리즘은 네트워크 크기 변화에 반드시 확장가능 (Scalable)해야 하고 적응적 (Adaptive) 이어야 한다. 대규모 네트워크 설계에 영감을 준 다양한 생체 시스템이 존재 하는데, 예를 들어 개체 주변 정보의 평균치를 가지고 복잡한 임 무의 최적해를 제공하는 ACO 알고리즘은 대규모 네트워크에서 효율적인 라우팅 방법을 제공한다. 또한 대규모 유기체 집단에 서 바이러스의 전달 방식인 전염병 확산 (Epidemic Spreading) 방식은 대규모 망에서 효과적인 정보 전달을 가능하게 해준다. 2.2 동적 변화 정적인 통신 채널로 구성된 초기의 통신 시스템과는 달리 앞 으로의 망구조는 노드 움직임, 트래픽 양, 대역폭 요구량, 채널 상태, 망 구조 등에 있어서 매우 동적일 것이다. MANET에서는 노드의 이동에 따라 네트워크의 크기, 전송 거리, 채널 상태, 통 신 링크가 계속 갱신될 것이다 [11]. 비슷하게 USN의 타겟 트랙 킹 시스템의 경우 타겟의 움직임에 따라 해당 지역의 센서에서 발생하는 트래픽 량은 급격히 증가하다가 감소할 것이다. 이러 한 경우 기존의 정적 관리 방안은 가해지는 동적 부하량을 감당 하지 못해 네트워크 용량에 비효율성을 야기한다. 생체 시스템은 살아남기 위해 환경 변화에 적응하는 능력이 있다. 인공 면역 체계 (Artificial Immune System)는 효율적으 APRIL 2012 63
로 환경 변화를 감지하여 예상되는 시스템 패턴에 적응한다. 또 한, 활성-억제 (Activator-Inhibitor) 시스템 에서도 동적 환 경에 적응하는 변화 메커니즘을 발견할 수 있다. 2.3 자원의 제약 통신 기술이 발전함에 따라 요구되는 서비스 양, 대역폭, 생 존시간과 같은 서비스 질의 수준이 급격히 증가하는 반면, 본질 적으로 에너지와 통신 자원의 한계를 지닌 노드로 구성된 통신 망은 물리적인 그리고 구조적인 한계를 지닌다. 따라서 제한된 자원을 효율적으로 사용하기 위한 지능적인 자원 할당 방식이 필요하다. 생체 시스템은 높은 요구사항과 한정된 자원 공급 사이의 균형 (Tradeoff) 관계를 갖고 있으며 이를 위한 해결 방향을 제시하 고 있다. 예를 들어 먹이를 찾으러 다니는 개미는 비용 효율적인 (Cost-Effective) 방법으로 먹이의 진원지를 찾기 위해 집단의 전체 행동을 최적화하는 방향으로 개인의 한정된 자원을 사용한 다. 먹이를 찾는 개미 집단의 행동 방식은 주어진 자원을 효율적 으로 사용하기 위한 네트워킹 기술에 적용될 수 있다. 2.4 분산 및 자율 동작 노드 수의 증가로 인한 대규모 네트워크에서 중앙 집중 방식 을 통한 제어는 실제로 불가능할 것이다. 반면 MANET, WSN, Delay Tolerant Network (DTN)과 같은 네트워크는 인프라 없이 존재할 수 있으며, 대부분 분산 방식을 따르고, 통합되지 않은 시스템 구조를 갖고 있다. 이러한 환경에서는 중앙의 도움 없이 효과적으로 동작하는 분산 통신 및 네트워킹 알고리즘이 필요하다. 또한 통신망은 디바이스의 오동작으로 인해 고장이 발생할 수 있는데, 대부분의 네트워크는 이러한 잠재적인 고장 에 의한 중단 없이 동작을 지속해나가기를 기대한다. 따라서 동 적 변화, 인프라의 부재, 중앙 집중형 제어의 어려움을 고려하 여 네트워크는 반드시 재구성되고 고장을 스스로 해결하여 동 작을 지속시킬 수 있는 능력을 가져야 한다. 이러한 요구를 충족시키기 위해 통신망은 생체 시스템에서 널 리 발견되는 지능적인 알고리즘을 사용할 수 있다. 예를 들어 이동하는 기러기 떼들은 한 개체가 유실되거나 새로 유입이 되 어도 중앙 집중적인 관리 없이 쉽게 변경된 환경에 맞춰 새로운 군집 형태를 구성하게 된다. 또한 곤충 집단은 어떠한 중앙 제 어 없이 집단 전체를 위한 임무를 수행하는데, 이는 인프라가 없는 네트워킹 설계에 영감을 줄 수 있다. 게다가 반딧불의 동 기의 원리는 인프라가 없는 환경에서 정확한 시간 동기를 요구 하는 통신 프로토콜의 설계에 적용 가능하다. 2.5 계층 구조 통신망의 또 다른 중요한 특징은 그들이 이질적인 (Heterogeneous) 노드로 연결되어 있다는 점이다. 이로 인하여 매우 복잡한 형태의 다양한 망 구성과 구성 요소간의 수 많은 상호 작용이 나타날 것이다. 차세대 통신 시스템은 일반적으로 통 신, 저장, 프로세싱 능력에 따라 단순한 센서 노드부터 광대역 무선 접속 단말이 탑재된 이동 차량에 이르기까지 다양한 통 신 기기로 구성될 것이다. 예를 들어 사물 인터넷 (Internet of Things)은 현재 인터넷의 능력을 개개의 사물에 내재시켜 대규 모 무선 네트워크로 확대하는 비전을 갖고 있다. 하지만 사물 인터넷의 주된 문제점은 구성 노드가 매우 높은 수준의 이종성 을 가질 것이라는 점이다. 새로운 이종 통신망의 실현을 위해서 는 통신 단말의 능력과 통신 규약의 이종성과 비대칭이 정확히 모델링 되어 효과적으로 관리되어야 한다. 생체 시스템에서도 다양한 이종성이 관찰된다. 예를 들면 많 은 유기체는 외부의 교란에도 불구하고 안정적인 내부 상태를 유지하는데, 신경체계, 내분비체계, 면역체계 등은 이질적인 부 시스템들 간의 상호 협력을 통하여 항상성 (Homeostasis)을 유 지한다. 이러한 동작은 이종 구조를 갖는 네트워킹 기술 개발에 적용될 수 있다. 반면 곤충 집단은 어떠한 환경자극에 대하여 서로 다른 반응 능력을 갖는 개체로 구성된다. 태생적인 이종성 에도 불구하고 그들은 집단 지성을 활용하여 임무 할당과 선택 프로세스를 최적화 할 수 있다. Ⅲ. 생체모방 알고리즘 대표적인 생체모방 알고리즘으로 통신망에 적용 가능한 Ant Colony 알고리즘, Bee 알고리즘, Firefly 알고리즘, Flocking 알고리즘에 대해 자세히 기술한다. 3.1 Ant Colony 알고리즘 Ant Colony 알고리즘은 시력이 없는 개미 집단이 개미집으 로부터 멀리 떨어져있는 먹이를 가장 빠른 경로를 통해 운반하 는 행위를 모방하여 통신망, 스케쥴링 문제, 이동체 경로 탐색, 임무 할당 문제 등의 다양한 최적화 문제에 적용되어 왔다 [12], [13]. <그림 3>과 같이 시력이 없는 개미가 먹이(F)를 발견하면 자 신이 지나온 길(a)에 남아 있는 페로몬(Pheromone)을 따라 개 미집(N)으로 먹이를 운반(b)하게 된다. 이러한 방식으로 개미떼 가 여러 경로를 통해 먹이를 운반하다 보면 개미집과 먹이와의 64 정보와 통신
3.2 Bee 알고리즘 Bee 알고리즘이란 꿀벌이 꽃으로부터 꿀을 채집하는 과정을 모방하여 작업 스케쥴링, 통계적 품질관리 (Statistical Quality Control), 로봇공학 등 다양한 최적화 기법 연구에 적용되고 있 다 [14], [15]. 그림 3. Ant Colony 알고리즘의 개념도 거리가 가장 짧은 경로에 많은 페로몬이 쌓이게 된다. 개미는 페로몬이 가장 많은 경로를 선택하여 이동하는 특징이 있어 일 정 시간이 지나면 모든 개미떼는 가장 짧은 경로를 통해서만 먹 이를 운반하게 된다. i에서 j로 가는 길 위의 현재 페로몬 양을 로, 페로몬의 증발 율을 로, i에서 j로 이동하는 개미떼의 수를 m으로, k번째 개 미가 길 위에 뿌리는 페로몬의 양을 로 정의하면 특정시간 이 지난 후의 i에서 j로 가는 길 위의 페로몬 양 는 다음과 같 이 정의된다. (1) 이와 같이 계산된 페로몬 양에 따라 개미는 다음에 이동할 위 치를 결정하는데, 이때 개미는 자신이 온 길로 되돌아가지 않으 며 1-홉 거리 내에서 이동할 위치를 다시 선택한다. k번째 개미 가 아직 방문하지 않은 1-홉 거리내의 위치를 l이라 하고, 이러 한 위치들의 집합을 N(s p )로 휴리스틱 정보를 로 정의하면, k번째 개미가 i위치에 도착했을 때 다음 경로 j위치로 이동할 확 률 는 다음과 같이 결정된다. (2) 이때 휴리스틱 정보 는 i와 j사이의 거리를 d ij 라 할 때 = 1/d ij 로 정의되며, α와 β값은 각각 페로몬 양과 휴리스틱 정보양에 가중치를 주는 파라미터 이다. 따라서 페로몬의 양이 많고 거리가 가까울수록 해당 경로를 통해 이동할 확률이 커짐 을 알 수 있다. 그림 4. Bee 알고리즘의 개념도 <그림 4>는 Bee 알고리즘의 개념도를 보여준다. 벌은 정찰벌 (Scouter), 채집벌 (Forager), 대기벌 (Onlooker)로 구분되는 데 모든 벌은 세 가지 역할을 번갈아 가며 수행한다. 정찰벌은 주변에 꿀이 많은 꽃을 찾으며, 꿀이 풍부한 꽃을 발견하게 되 면 채집벌로써 꿀을 채취한다. 채취한 꿀을 벌집으로 가져온 채 집벌은 벌집에 있는 대기벌에게 자신이 채취한 꽃의 위치를 8 자 춤 (waggle dance)을 통해 알려주고, 자신이 채취했던 방향 으로 날아가 계속해서 꿀을 채취한다. 해당 지역의 꿀을 모두 채취한 채집벌은 벌집으로 돌아와 정찰벌 혹은 대기벌의 역할 을 하나 선택하여 수행한다. 대기벌은 채집벌이 알려준 위치에 있는 꽃에서 꿀을 채취하며 채집벌의 역할을 수행한다. 꿀을 가진 꽃의 수를 이라 하고, 번째 꽃의 방향을 라고 정의하면 목적함수를 달성하기 위한 최적 값을 구하는 식은 다음과 같다. (3) 이때 는 의 최소값이고, 는 의 최대값이 된다. 값은 정찰벌에 의해 결정된다. 채집벌은 자신이 꿀을 채취 APRIL 2012 65
하던 꽃의 방향 의 인접한 위치에 꿀이 더 많은 꽃을 발견하 면 그 꽃의 방향 으로 날아가 꿀을 채취하게 되는데 은 다음과 같이 계산된다. (4) 이때 는 임의로 선택된 꽃의 방향이고, 는 사이의 임의의 값이다. 대기벌은 채집벌이 추는 8자 춤을 통 해 자신이 날아갈 방향을 정하는데 번째 꽃으로 날아갈 확률 은 다음과 같이 계산된다. (5) 여기에서 은 방향의 꽃의 꿀의 양으로 정의된 다. 3.3 Firefly 알고리즘 Firefly 알고리즘은 자연계에서 볼 수 있는 다양한 집단 동기 화 (Collective Synchronization) 현상 중 하나로, 반딧불들이 반짝거릴 때 초기엔 각자의 고유진동수에 따라 반짝이다가 점 차 시간이 지날수록 상호작용을 통해 상대방 반짝거림에 맞춰 결국엔 한 마리의 거대한 반딧불처럼 반짝거리는 현상에서 영 감을 얻어 개발된 알고리즘이다 [16], [17]. <그림 5>는 처음에 는 개별적으로 반짝이던 반딧불이 점점 시간이 지나면서 동시 에 반짝거리는 동기화 현상을 보여준다. 고유진동수를, 그리고 는 결합력의 세기를 나타내는데, 동기 화가 이루어지지 않은 초기 상태( )에서 개체들은 각자 고유의 진동수에 따라 진동한다. 하지만, 점차 상호 작용을 통 해 각자의 고유 진동수에 변화가 생기고 개체 간의 결합 세기가 점점 커져 고유 진동수 보다 큰 값을 가지게 되면, 개체 간에 위 상 혹은 같은 진동수가 같아지는 동기화가 이루어진다. 이와 같 이 Firefly 알고리즘은 간결한 수학 방정식의 형태로써 집단 동 기화 현상을 효과적으로 모델링 하고 있다. 3.4 Flocking 알고리즘 Flocking 알고리즘은 철새 떼가 V자 형태로 무리 지어 한 방 향으로 날아가는 모습이나 <그림 6>과 같이 작은 물고기 떼가 침입자로부터 자신들을 보호하기 위해 무리 지어 헤엄치는 자 기 질서화 (Self-Ordered) 현상을 모델링한 것으로 1986년 Reynolds [3]에 의해 처음 컴퓨터 시뮬레이션이 이루어진 후 센서 네트워크 및 애드혹 네트워크에서의 노드 배치, 자원 관 리, 스케쥴링 등의 분야에 활용되고 있다 [19], [20]. 그림 6. 물고기 떼의 Flocking 현상 그림 5. Firefly의 동기화 현상 관련하여 최근 F. Cucker와 S. Smale은 각 개체들이 <그림 2>와 같은 간단한 군집 이론의 규칙을 분산 처리 방식으로 수 행하고, 각 개체의 초기 속도와 위치가 특정 범위에 있으면 모 든 개체의 속도와 위치가 일정 시간의 경과 후에 특정 값으로 수렴한다는 사실을 증명하였다. Cucker-Smale 모델로 불리는 Flocking 모델은 다음과 같이 표현된다 [4]. 이러한 집단 동기화 현상을 이해하기 위해 널리 사용되는 모 델인 쿠라모토 (Kuramoto) 모델은 다음과 같이 기술된다 [18]. (6) 여기에서 는 각 개체의 위상을 나타내고, 는 각 개체의 (7) 여기에서 는 번째 개체의 위치, 는 번째 개체의 속도, 은 개체들의 수, 는 개체들 간 결합력의 세기, 그리고 는 개체들의 통신 가능한 범위를 나타내는 감소함수이다. 이와 같 66 정보와 통신
이 각 개체들이 서로 주위 개체들의 정보만을 활용하여 자신의 속도 벡터의 증감을 조절하면 각 개체들의 속도는 다음과 같이 전체 개체의 평균 속도에 수렴한다. (8) Cucker-Smale 모델은 그 특성상 각 개체에서 정보의 분산 처리를 가정하므로 분산 처리가 요구되는 분야에서 최적화된 해를 구하는데 이론적인 바탕을 제공한다. IV. 관련 연구 동향 자연계의 생물체들의 행동원리를 규명하고 이를 모델링 하려 는 시도는 1970년대 초반 처음 시도되었으며 [21] 이후 여러 가 지 체계화된 생체모방 알고리즘이 제시되고 본격적으로 통신 분야에 접목하여 응용연구를 하려는 연구흐름은 최근 10여 년 사이 본격화되었다 [22], [23]. 본 장에서는 산업계의 프로젝트 현황 및 학계에서의 연구 동향에 대해서 소개한다. 4.2 Bio Net 미래의 통신 환경은 모바일 디바이스의 증가, 다양한 네트워 크에서의 노드 기능의 다양성, 노드의 높은 이동성, 관리의 복 잡성, 여분 자원의 활용성 증대와 같은 이유에 의하여 그 복잡 성이 생물유기체, 생태계, 사회 경제적인 공동체와 매우 유사 한 특징을 갖는다. Bio Net 프로젝트는 이러한 문제점을 해결 하고, 개체군이 많은 자연계 혹은 인구가 많은 사회에 존재하 는 다양하고 급변하는 시스템에서 중앙 통제 (Central Control) 없이 지역적 상호작용 (Local Interaction)을 통해 효과적인 협 업과 생존 전략을 개발하고, 효율적인 평형상태에 도달하는 것 을 목표로 설립되었다. Bio Net을 구성하고 있는 개체는 T노 드 (Tiny node)와 U노드 (User node)등이 있다. T노드는 주변 환경으로부터 데이터를 수집하고 U는 주변의 T노드로부터 정 보를 수집한다. U노드는 Islands of Connected 상태를 이루며 같은 Islands에 있는 노드들 간에 정보를 교환한다. <그림 8>은 Bio Net의 구조를 보여준다. 4.1 Autonomic Network Architecture (ANA) ANA 프로젝트는 인터넷 기술을 기반으로 하는 네트워크를 사용하고 조직화하는 새로운 방법을 연구하는 것을 목표로 설 립되었다. 궁극적인 목표는 모든 네트워크 환경에 적응가능하 고, 주변 환경 변화에 강하며, 자율적으로 동작하는, 전체 네트 워크에 적용 가능한 새로운 자가 구성 네트워크 구조를 설계하 고 개발함으로써 단말의 위치가 자주 변하는 이동 환경에서 새 로운 자원을 역동적으로 사용할 수 있도록 하는 것이다. <그림 7>은 ANA 프로젝트의 자가 구성 망 구조를 보여준다. 그림 8. Bio Net의 구조 4.3 Swarmanoid 그림 7. ANA 프로젝트의 자가 구성 망 구조 Swarmanoid는 Swarms와 Humanoid의 합성어로 새로운 분 산형 로봇 시스템의 설계, 구현, 통제를 프로젝트의 목표로 삼고 있다. 이 프로젝트에서는 인간이 만들어 놓은 환경에서 적용 가 능한 행동을 성공적으로 수행하는 로봇을 만드는 방법을 제안하 였으며, 이러한 로봇은 서로 다른 종류의 (Heterogeneous) 작은 자율 로봇들과 동적으로 연결되어 존재한다. 이 프로젝트에서는 생체모방 알고리즘 중에서 <그림 9>와 같은 개미집단최적화 알 고리즘을 적용한 연구 결과를 주로 발표하였다 [24], [25]. APRIL 2012 67
4.4 Wireless Accessible Sensor Populations (WASP) 지난 몇 년간 무선 센서 네트워크와 관련하여 지속적인 유망 한 연구 결과가 도출되고 있음에도 불구하고 산업체에서 센서 네트워킹 기술을 상용화하는 것에 대해 소극적인 것이 현실이 다. 이러한 이유는 기술적 연구 결과와 실질적인 무선 센서 네 트워크를 사용한 성공사례, 무선 센서 네트워크의 개발, 유지, 또는 정보 체계를 통합하는 것에 대한 신뢰가 부족하기 때문이 다. WASP 프로젝트는 무선 센서 네트워크 도입을 촉진하기 위 해 생체모방 알고리즘을 활용하여 다양한 분야의 전문가들의 상호 이해관계의 재정립을 통해 응용 서비스의 최적 구축 사례 를 보이고 비용 효율적인 해결책을 유도하는 것을 목표로 설립 되었다. 관련 생체모방 알고리즘 중에서 Bee 알고리즘을 무선 센서 네트워크에 적용한 연구 결과들을 발표하였다 [26], [27]. <표 1>은 생체모방 알고리즘 기반의 대표적인 프로젝트 현황 을 보여준다. 표 1. 생체모방 알고리즘 관련 프로젝트 현황 Project Name Funding Research Area URL ANA EU FET 자가 구성 네트워크 구조 ana-project. 확장성, 적응성, 생존성을 Bio Net 설계 및 구현하기 위한 생 http:// NSF, 체 네트워크 구조 및 이용 netresearch.ics. DARPA 가능한 네트워크 어플리케 uci.edu/bionet/ 이션 BIONETS EU FET 모든 세대에 적용되는 생 태계 모방 서비스 발전 bionets.eu/ CASCADAS EC Agents 그림 9. ACO 알고리즘을 모방한 로봇 시스템 EU FET EU FET 자율 적이고 상황을 인식 한 통신과 동적으로 적용 가능한 서비스 물리적인 세계와 직접적으 로 상호작용 가능한 통신 에이전트 cascadasproject. http://ecagents. istc.cnr.it/ Haggle EU FET 위치 및 자율 통신 MC NSF, DARPA Swarmanoid EU FET Swarm-bots EU FET WASP EU IP 4.5 학계 연구 동향 나노머신 사이의 통신을 위한 분자 통신 로봇 시스템 분산 제어를 위한 설계, 구현 및 제어 자가 구성과 자가 조립 설 계 및 구현 노드와 무선센서네트워크 에서의 서비스 자가 구성 haggleproject. http:// netresearch.ics. uci.edu/mc/ swarmanoid. swarm-bots. wasp-project. 생체모방 알고리즘에 관한 활발한 연구가 수행됨에 따라 2000년대 후반부터 관련 연구자들을 중심으로 정기적인 학술 대회 및 워크샵이 개최되고 있다. 또한 관련 저널들이 새로 출 간되거나 기존 저명한 저널들의 특집호의 주제로 다뤄지고 있 다. <표 2>는 생체모방 알고리즘과 그 응용에 관한 연구 주제를 다루고 있는 국제학술대회 및 워크샵을 보여주고, <표 3>은 생 체모방 알고리즘과 그 응용에 관한 주제로 2000년대 후반 출간 된 저널과 기존 저널의 특집호 주제를 보여준다. 표 2. 생체모방 알고리즘 관련 학회 및 워크샵 Conference and Workshop Bionetics (International Conference on Bio inspired Models of Network, Information and Computing Systems) Biowire (Workshop on Bio-inspired Design of Wireless Networks and Self-Organizing Networks) EvoCOMNET (European Workshop on Natureinspired Techniques for Telecommunications and other Parallel and Distributed Systems) Bionetworks (Workshop on Socially and Biologically Inspired Wired and Wireless Networks (co-located with IEEE MASS 2007)) BLISS (The 2008 ECSIS Symposium on BIOinspired, Learning, and Intelligent Systems for Security) BADS (International Workshop on Bio-inspired Algorithms for Distributed Systems (co-located with IEEE ICAC 2009)) URL bionetics. usukita.?q=node/225/ evostar. http://san.ee.ic.ac.uk/ bionets07/ see.ed.ac. uk/bliss08/ http://bads.icar.cnr.it/ 68 정보와 통신
표 3. 생체모방 알고리즘 관련 저널 현황 Journal and special issues Elsevier Nano Communication Networks ICST Transactions on Bio-Engineering and Bio-inspired Systems Journal of Bio-inspired Computation Research (JBICR) International Journal of Bio-inspired Computation (IJBIC) Special Issue on Bio-inspired Computing and Communication Elsevier Ad Hoc Networks in Wireless Ad Hoc and Sensor Networks IEEE Journal on Selected Areas in Special Issue on Bio-inspired Communications (JSAC) Networking Springer Transactions on Special Issue on Biosciences Computational Systems Biology and Bio-inspired Information (TCSB) Technologies Special Issue on Swarm Intelligence Springer Swarm Intelligence for Telecommunications Networks International Journal of Autonomous and Adaptive Communication Systems (IJAACS) V. 향후 이슈 Special Issue on Bio-inspired Wireless Networks 지금까지 생체모방 알고리즘을 통신네트워크 분야에 적용하 여 망 동기, 자원 할당, 라우팅과 같은 네트워크 고유의 문제들 을 해결하려는 연구 활동을 진행하여 왔다. 그러나 지금까지의 연구 결과를 분석해 봤을 때, 대부분의 연구들은 생체모방 알고 리즘들을 각 분야에 단순 적용한 후 그 결과를 고찰하는 수준에 그치고 있어 관련 응용 연구의 실용화에 있어 한계가 존재한다. 다시 말하면, 기존의 생체모방 알고리즘을 활용한 통신 관련 연 구들에서는 수학적인 분석 모델의 부재로 인하여, 각 개체의 동 작 수행 결과를 예측할 수 없고 시스템의 안정성 (각 개체들의 동작이 어떤 특정한 값으로 수렴하는지 여부)과 확장성 (개체의 출입에 따른 시스템의 안정성 유지 여부)을 보장할 수 없다. 특 히 생체모방 알고리즘의 적용 시, 각 개체의 동작 초기값의 범 위에 따라 전체 시스템의 안정성 및 확장성이 영향을 받으므로 시스템의 안정성 및 확장성을 보장할 수 있는 초기값에 대한 분 석이 매우 중요하다. 이러한 생체 모방 알고리즘에 관한 엄밀한 수학적 분석의 부재는 실제 각 분야에서 생체 모방 알고리즘을 응용하여 활용하는데 있어 매우 큰 제약 사항이 된다. 하지만 최근 Cucker-Smale이 제시한 Flocking 모델의 경우 군집 이론의 수학적인 모델링과 함께 군집 이론에 의한 결과가 수렴하기 위한 각 개체의 초기값에 관한 연구 결과를 도출하였 다 [4]. 현재 이 연구 결과를 활용하여 후속 연구가 활발하게 진 행되고 있으며, 특히 무인 항공 비행기의 제어 등에 주목할 만 한 성과가 나오고 있다. 따라서 무선 통신 네트워킹 분야에서 도 Cucker-Smale 모델과 같은 수학적 엄밀성을 활용하여 여 러 문제를 해결하려는 시도가 필요하다. 즉, 생체모방 알고리즘 을 무선 통신 네트워킹 분야에 적용하고 실용화 하기 위해서는 정교한 수학적 모델링과 분석을 바탕으로 알고리즘의 안정성과 확장성에 대한 검증이 선행되어야 한다. VI. 결 론 본 논문에서는 생체 시스템과 통신망의 유사성을 바탕으로 통 신망의 문제점을 해결하기 위하여 고안된 생체모방 알고리즘 에 대해서 살펴보았다. Ant Colony 알고리즘, Bee 알고리즘, Firefly 알고리즘, Flocking 알고리즘과 같은 생체모방 알고리 즘은 단순한 행동 규칙에 따라 분산적으로 동작하면서도 복잡 한 환경에서 주어진 문제에 대한 최적해를 안정적으로 제공함 을 확인할 수 있다. 따라서 이러한 생체모방 알고리즘은 향후 나타나게 될 대규모 통신망에 효과적으로 적용될 수 있으리라 예상된다. 이를 위해서는 다양한 생체 시스템에 대한 정교한 수 학적 모델링과 함께 시스템이 갖는 다양한 환경 변수에 따라 성 능 보장 여부에 대한 엄밀한 검증이 요구된다. 참 고 문 헌 [1] F. Dressler, O. B. Akan, A Survey on Bio-inspired Networking, Computer Networks Journal (Elsevier), vol. 54, no. 6, pp. 881-900, April 2010. [2] F. Dressler, O. B. Akan, Bio-inspired Networking: From Theory to Practice, IEEE Communications Magazine, vol. 48, no. 11, pp. 176-183, November 2010. [3] Craig W. Reynolds, Flocks, herds, and schools: A distributed behavioral model, ACM Computer Graphics, vol. 21, no. 4, pp. 25-34, 1987. [4] Cucker, F. ; Smale, S., Emergent Behavior in Flocks, IEEE Transactions on Automatic Control, vol. 52, no. 5, pp. 852-960, May 2007. [5] Hui Yu, Ji-Gui Jian, Flocking motion control of mobile agents based on distance-dependent adjacency matrix, International Conference on Wavelet APRIL 2012 69
Analysis and Pattern Recognition, vol. 1, pp. 17-22, Aug. 2008. [6] Seung-Yeal Ha, Taeyoung Ha, Jong-Ho Kim, Emergent Behavior of a Cucker-Smale Type Particle Model With Nonlinear Velocity Couplings, IEEE Transactions on Automatic Control, vol. 55, no. 7, pp. 1679-1683, July 2010. [7] Demetriou, M.A., Distributed parameter methods for moving sensor networks in unison, American Control Conference, 2008, pp. 273-278, June 2008. [8] Schwager, M., Slotine, J.-J., Rus, D., Consensus learning for distributed coverage control, IEEE International Conference on Robotics and Automation, pp. 1042-1048, May 2008. [9] Bin Xu, Kurdila, A.J., Stilwell, D.J., Geometric ergodicity of the distributional consensus problem in vehicle network control, IEEE Conference on Decision and Control (CDC), pp. 7499-7506, Dec. 2010. [10] OUTLOOK: Visions and research directions for the Wireless World, WWRF(World Wide Radio Forum), no.4, July, 2009. [11] I. Chlamtac, M. Conti, J.J. Liu, Mobile ad hoc networking: imperatives and challenges, Elsevier Ad Hoc Networks, vol. 1, no. 1, pp. 13-64, 2003. [12] Dorigo, M., Birattari, M., Stutzle, T., Ant colony optimization, IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, Nov. 2006. [13] M. Dorigo, C. Blum, Ant colony optimization theory: A survey, Theoretical Computer Science, vol. 344, pp.243-278, Nov. 2005. [14] Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm, Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005. [15] Karaboga.D, An idea based on honey bee swarm for numerical optimization., Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005. [16] G. Werner-Allen, G. Tewari, A. Patel, R.Nagpal, and M. Welsh, Firefly-Inspired Sensor Network Synchronicity with Realistic Radio Effects. InSenSys, 2005. [17] J. Degesys, I. Rose, A. Patel, R. Nagpal, Desync: Self-organizing desynchronization and tdma on wireless sensor networks, International Conference on Information Processing in Sensor Networks, ACM, pp. 11~20, 2007. [18] J.A. Acebron, L.L. Bonilla, C.J. Perez-Vicente, F. Ritort, R. Spigler, The Kuramoto model: A simple paradigm for synchronization phenomena, Rev. Mod. Phys., vol. 77, pp. 137~185, 2005. [19] Olfati-Saber, R., Flocking for multi-agent dynamic systems: algorithms and theory, IEEE Transactions on Automatic Control, vol.51, no.3, pp. 401-420, March 2006. [20] J. A. Carrillo, M. Fornasier, J. Rosado, and G. Toscani, Asymptotic flocking dynamics for thekinetic cucker-smale model, SIAM Journal on Mathematical Analysis, 2010. [21] M. Eigen, P. Schuster, The Hypercycle: A Principle of Natural Self Organization, Springer, 1979. [22] M. Wang, T. Suda, The Bio-Networking Architecture: A Biologically inspired Approach to the Design of Scalable, Adaptive and Survivable/Available Network Applications, IEEE Symposium on Applications and the Internet (SAINT), 2001. [23] J. Suzuki, T. Suda, Adaptive Behavior Selection of Autonomous Objects in the Bio-Networking Architecture, Symposium on Autonomous Intelligent Networks and Systems, 2002. [24] Montes de Oca M.A., Stuetzle T., Birattari M., Dorigo M. Incremental Social Learning Applied to a Decentralized Decision-Making Mechanism: Collective Learning Made Faster, IEEE Computer Society Press, 2010. [25] Stirling T., Wischmann S., Floreano D. Energyefficient indoor search by swarms of simulated flying robots without global information, vol. 4, no. 2, pp. 117-143, Feb. 2010. [26] F. Ingelrest, G. Barrenetxea, G. Schaefer, M. Vetterli, O. Couach and M. Parlange SensorScope: Application-Specific Sensor Network for Environmental Monitoring, ACM Transactions on Sensor Networks, vol 6, no 2, 2010. 70 정보와 통신
[27] C. Jardak, K. Rerkrai, A. Kovacevic, J. Riihijarvi and P. Mahonen, Design of Large-scale Agricultural Wireless Sensor Networks: Email form the Vineyard, International Journal for Sensor Networks (IJSNET). vol. 8, no. 1, 2010. 약 력 최 현 호 2001년 KAIST 전기및전자공학과 공학사 2003년 KAIST 전기및전자공학과 공학석사 2007년 KAIST 전기및전자공학과 공학박사 2007년~2011년 삼성종합기술원 전문연구원 2011년~ 현재 국립한경대학교 전기전자제어공학과 전임강사 관심분야: 매체접속제어, 무선자원관리, 생체모방 통신 및 네트워킹 이 정 륜 1995년 서울대학교 수학과 공학사 1997년 서울대학교 수학과 공학석사 2006년 KAIST 전기및전자공학과 공학박사 1997년~ 2006년 LG전자 이동통신연구소 책임연 구원 2006년~2008년 인천대학교 전임강사 2008년~현재 중앙대학교 전자전기공학부 부교수 관심분야: 저전력 통신 프로토콜, 메쉬 네트워크, 네트워크 이동성, 생체모방 통신 등 APRIL 2012 71