A resource allocation approach based on genetic algorithm for service composites in tactical network environments

Abstract

조합된 서비스를 성공적으로 수행하기 위해 다수의 무기 자원이 운용되는 전장환경에서는 서비스 인스턴스와 자원간의 효율적인 바인딩이 필수적이다. 그러나 전장 네트워크 환경은 대역폭이 낮고 통신 실패의 확률이 높아 서비스 수행을 위해 자원간에 많은 양의 데이터가 전송되는 경우 조합된 서비스의 수행을 실패할 확률이 높다. 또한 전장 네트워크 환경은 동적으로 변화하면서 자원간 연결 상태와 각 연결의 대역폭에 영향을 끼친다. 그러므로 자원간 데이터 전송량을 최소화하는 것은 성공적인 서비스 수행에 있어서 필수적이다. 또한 전장 네트워크 환경을 구성하는 자원의 경우 처리 능력(computing power)이 부족하여 서비스 인스턴스를 직접 실행할 수 없고, 자원간 직접적인 통신도 불가능한 경우가 많다. 이 때문에 자원과 함께 전장 환경에 배치된 서비스 게이트웨이가 서비스 인스턴스를 직접 실행하고 자원간의 통신을 중계하게 된다. 그러나 서비스 게이트웨이에는 연결 가용한계(connection capacity)로 인해 동시에 유지할 수 있는 연결의 수가 제한되어 있다. 이 논문에서는 이러한 전장 환경의 제한 조건을 만족시키기 위하여 게이트웨이간 통신량을 최소화하고 연결 가용한계를 초과하지 않는 서비스 자원 할당 방법을 제시한다. 이 논문에서 제안하는 자원 할당 방법은 자원 할당 문제를degree constrained minimum spanning tree 문제의 변형으로 변환한 후 유전자 알고리즘을 사용하여 문제를 해결하였다. 이 문제에 유전자 알고리즘을 적용하기 위하여 적합도 함수와 후보 솔루션의 유전자 형태 인코딩 방식을 정의하였다. 또한 본 연구에서는 제시한 자원 할당 방법을 brute force approach와 비교 실험을 통해 자원 할당 방법의 실행시간, 솔루션의 적합도, 자원 할당 방법의 성공률을 평가하였다. 그 결과 본 연구의 자원 할당 방법은 평균적으로 97%의 성공률을 보이며 준최적해를 찾아내었으며, 입력 값의 크기가 커짐에 따라 선형적인 실행 시간 증가량을 보였다.