1서 론

위성 산업이 가장 강력한 성장 동력으로 부상하게 된 것은 그리 오래되지 않았으나 그 성장 잠재력으로 인해 최근 급속한 발전을 이루고 있다. 특히 다목적 실용위성, 저궤도 위성 산업 등 고부가가치 창출이 가능한 상업 위 성 시장이 주목 받기 시작하면서 상업적인 운영 기술과 이를 활용한 관련 산업들이 빠르게 성장하였다[2, 9].

초기의 위성들은 간단하고 반복적인 임무들이 대부분 을 차지하고 있었지만, 최근에는 고해상도 위성들의 출 현과 기능의 향상으로 다양한 모드에서 영상을 획득할 수 있을 뿐 아니라 수행 임무의 다양성이 증가하였다. 하 지만, 그 증가한 다양성만큼 임무를 수행하기 위해 필요 한 조건과 제약사항 또한 증가하게 되었다[8]. 이러한 상 황 변화에 따라 위성 임무의 효율적인 운용을 위한 연구 에 필요성은 커지고 있다.

위성 임무 스케줄링은 위성에게 할당되는 작업들과 그에 따른 제한 사항 및 여러 변수들을 고려하여 서로 간의 충돌을 회피함과 동시에 주어진 위성의 자원들을 최대한 활용하여 최적의 작업 시간을 설계하는 것을 목 적으로 한다[7, 8]. 그러나 위성임무의 스케줄링은 일반 적인 스케줄링에 관한 변수 이외에도 위성만의 특별한 환경을 고려한 다양한 변수들과 제약조건이 필요하다. 우주 공간 상의 각 종 이벤트, 사용자의 요구 사항, 위성 의 자원 등에 대한 총체적인 고려가 필요하다. 또한 위성 의 운영 목적과 활용 방안에 따라 공익을 목표로 하는 위성과 이윤을 추구하는 상업적 목적의 위성, 재난 혹은 전시와 같은 비상 상황 발생을 대비한 위성 등이 구별되 며, 이러한 위성들은 각 운영 목적에 따라 우선적으로 고 려해야 하는 변수와 임무 기준에 차이가 존재하며, 이러 한 사항에 대한 충분한 검토가 이루어져야 한다.

위성 임무 스케줄링은 국내 및 국외에서 활발히 연구되어 타부 탐색(Tabu Search), 유전 알고리즘(Genetic Algorithm; GA)과 같은 휴리스틱 알고리즘을 활용한 연구[10]가 이 루어졌으나 연산 속도 등에 한계를 지나고 있었다.

본 논문에서는 이러한 단점의 보완을 위하여 생체 군집 이론에 바탕을 둔 입자 군집 최적화(Particle Swarm Optimization; PSO)를 이용하여 인공위성 임무 스케줄링 알고리 즘을 설계하고자 한다. 최적화 알고리즘 중 하나인 PSO 알고리즘은 다양한 분야의 시스템 모델링에 새로운 방법 론적 이슈로써 등장하고 있으며[6] 다양한 문제에서 유 전 알고리즘과 비교하였을 때 더 간결하고 수렴이 빠른 장점이 있다고 알려져 있다[3, 11].

이 논문의 구성은 다음과 같다. 제 2장에서는 이 논문을 이해하기 위한 기본적인 배경 지식과 문제를 정의하고 그 결과들을 설명한다. 제 3장에서는 문제 해결을 위한 PSO 알고리즘 기반 위성 임무 스케줄링 알고리즘을 제시한다. 제 4장에서는 제시된 알고리즘에 대한 효율성의 검증을 위해서 몇 가지 가정 상황에서 시뮬레이션을 실시하고, 그 결과를 CPLEX 모델과 비교하여 유효성을 검증한 후, 검증 된 PSO 알고리즘을 운영 목적이 다른 위성에 적용하여, 각 운영 목적에 적합한 임무 스케줄링이 제시되는지 여부 를 검증하였다. 제 5장에서는 이 논문의 결론을 제시한다.

2위성 임무 스케줄링

2.1위성 임무 스케줄링 업무 흐름

위성의 관제와 운영을 담당하는 기상관제국의 위성 임무 계획 수립에 대한 업무는 이벤트 예측, 임무 스케줄링, 명령 계획으로 나눌 수 있다. 이벤트 예측은 위성의 궤도 예측, 사용자의 요구, 임무 수행에 따라 자세 및 궤도 수 정 등의 정보를 종합하고 이를 분석하여 임무 계획에 주 요 요소로 작성하는 이벤트에 대한 정보를 생성하는 단 계라 할 수 있다.

임무 스케줄링 단계에서는 전 단계에서 생성된 정보 를 기반으로 미리 정의한 규칙 및 방법론에 기반하여 각 각 임무 및 작업 그리고 고려해야 할 제한사항 등으로 나누고, 이 정보를 토대로 기 구축된 스케줄링 알고리즘 에 따라 최적의 스케줄링 해를 도출하여, 수행 할 임무와 그에 따른 작업을 시간 순서에 따라 정리하는 단계이다.

명령 계획 단계는 기 도출된 임무 스케줄링의 결과에 따라 위성이 각 종 작업들을 수행할 수 있도록 위성이 수행 가능한 명령으로 변환하는 기능 수행하는 단계라 할 수 있다.

본 연구는 주로 두 번째 단계의 위성 임무의 최적화된 스케줄링을 수립하는 내용을 연구하고 있으며, 주로 영 상 촬영 임무를 주 대상으로 하고 있다.

2.2위성 임무 스케줄링 주요 변수 및 조건

본 연구의 목적은 최적의 위성 임무 스케줄링 알고리 즘을 제안하고, 실제 정보를 기반으로 임의로 설정된 시 나리오에 적용해 봄으로써 적합성을 검증하는데 있으며, 따라서 본 연구는 백승우 외[1]의 연구에서 제안한 8가 지 변수 및 조건 중에서 촬영 면적을 제외하고 거리와 촬영 각에 대한 조건을 추가하여 전체 변수 및 고려해야 할 조건을 구성하였다.

2.3위성 운영 목적 별 변수 가중치 산정

위성의 운영 목적에 따라 일반위성, 상용위성, 전술위 성으로 나눌 수 있으며, 종류에 따라 운영 목적이 상이한 부분이 존재한다.

일반 위성은 공익과 상업적 수익을 복합적으로 고려 하지만 상업적 수익보다는 공익을 우선으로 하고 있다. 따라서 긴급 상황과 관련된 임무에 대한 중요성을 고려 해야 한다.

상용위성은 국가가 운영하는 일반 위성과는 다르게, 공익추구가 아닌 상업적 수익을 최대화 하는데 그 운영 의 목적을 두고 있다. 따라서 고객 중요도나 임무의 긴급 성과는 무관하게 보상과 임무완료 기한을 중점적으로 고 려해야 한다.

전술 위성은 정부나 군의 요구와 같은 공익을 중시하 고 재난 지역, 정찰과 같은 임수 수행을 가장 중요한 운 영 목적이라 할 수 있다. 따라서 임무의 긴급성이 가장 고려해야 할 요소인 반면 보상은 크게 중요치 않음을 알 수 있다.

이와 같이 위성 임무 스케줄링은 각 위성의 목적에 따 라 변수에 적용할 가중치(Weight)를 차별화할 필요가 있 으며, 이를 반영하기 위해서 <Table 1>는 기존 연구[4]의 자료를 기반으로 작성하였으며 상황에 따라 가중치의 값 은 수정될 수 있다.

가중치는 상대적인 중요도를 의미를 나타내고 있으며 <Table 1>에서는 편의상 전체 총 합 10으로 하였다. 일 반 위성의 경우는 업무의 긴급성이 가장 중요한 고려 사 항이며 마감 시한, 고객의 중요도 순으로 중요도를 평가 되고 있다. 상업용의 경우는 업무의 보상이 가장 중요한 요인이며, 그 다음은 마감 시한이라 할 수 있다.

그리고 <Table 1>에 Score는 가중치를 각 항목의 최대 치로 나눈 값으로 원 점수를 이용하여 각 임무의 점수를 산출할 때 사용된다.

2.4위성 임무 스케줄링 문제 정의

본 연구에서 고려하고 있는 임수 스케줄링 문제는 먼 저 고객으로부터 요청받은 임무를 위성의 지나가는 위치 를 고려하여 순서대로 정렬할 후 고객 요구사항을 고려하 면서 할당된 임무 수행을 하기 위해서는 다양한 제약 사 항들이 있으며, 이들과 위성의 가용성을 종합적으로 고려 하여 짧은 시간 내 성과를 최대화 할 수 있는 임무들을 선택하는 문제라 할 수 있다. 따라서 이 문제의 형태는 대표 적인 조합 최적화 문제인 배낭 문제[5](Knapsack Problem) 와 동일한 구조를 가지고 있다.

이 문제의 의사결정 변수는 x_j는 j번째 위성임무의 수 행여부를 나타내는 이진변수로 정의하고 수행하면 1, 수 행하지 않으면 0의 값을 가진다고 하면 총 요청 받은 N 개의 위성임무에 대한 스케줄링 문제는 다음과 같이 표 현될 수 있다.

Maximize

Subject to

위 식에서 사용된 기호는 다음과 같은 의미를 가지고 있다.

본 연구의 목적식 (1)은 수행될 임무의 임무수행 점수들 의 총합을 최대화하는 것을 나타내고 있다. 여기서 각 임 무의 임무수행 점수는 <Table 1>에서 정의된 고려 사항 들의 점수와 각 임무의 각 고려 사항의 점수의 곱들의 합으로 이루어져 있으며 다음과 같이 계산될 수 있다.

여기서 w_i는 <Table 1>에서 제시된 위성의 목적에 따른 고려 사항의 점수들을 의미하며 <Table 1>에 소개된 i번 쩨 변수의 점수를 의미한다. 즉 w₂는 일반위성의 임무완 료기한의 점수를 의미하며 0.25의 값을 가진다. 그리고 p_i는 각 임무의 변수에 대한 점수를 의미하며 차례대로 고객의 중요도, 임무완료기한, 보상, 임무의 긴급성의 실 제 점수를 의미하고 있다. 따라서 각 임무의 임무수행 점 수는 10을 초과할 수 없도록 되어 있다.

제약 조건 식 (2)는 전체 에너지 소비량이 최대 전력량을 초과할 수 없음을 나타내고 있으며, 제약 조건 식 (3)은 전체 수행될 임무들의 총 메모리 용량이 시스템에서 제공 되는 가용 메모리 총량을 초과하지 못함을 의미하고 있다.

그리고 각 임무를 수행하고자 하는 지역의 운량 또한 중요한 제약요소인데 운량이 일정한 양을 넘으면 임무 수 행이 힘든 것으로 알려져 있으며, 이를 식 (4)에 반영되어 있으며, 일반적으로 Cloud_max = 70으로 설정해 놓고 있다.

각 임무들의 첨자는 임무의 수행 위치에 따라 순서대 로 정의되어 있기 때문에 위성이 거리 1당 촬영 각을 5° 씩 움직일 수 있고 이전 임무 지에서 다음 임무지 까지 떨어진 거리 안에 다음 임무가 요구하는 촬영 각을 만족 시키지 못할 경우 임무를 수행할 수 없다는 조건식은 식 (5)로 표현될 수 있다.

3스케줄링 알고리즘 설계

본 논문에서는 생체 군집 이론에 바탕을 둔 입자 군집 최적화(Particle Swarm Optimization; PSO)를 이용하여 인 공위성 임무 스케줄링 알고리즘을 설계하고자 한다. 최 적화 알고리즘 중 하나인 PSO 알고리즘은 다양한 분야 의 시스템 모델링에 새로운 방법론적 이슈로써 등장하고 있으며[6], 많은 분야에서 유전 알고리즘과 비교하였을 때 더 간결하고 수렴이 빠른 장점이 있다고 알려져 있다[8].

PSO 알고리즘은 새들이 먹이가 많은 장소 등을 찾아 가는 과정을 모방하여 컴퓨터로 시뮬레이션 하는 최적화 알고리즘이다. 즉, 문제 해결을 위해 각 Particle들에 이 동 방향과 속도를 설정하고 일정 시간마다 Particle들이 갖는 해를 구하고, 각 Particle들이 거쳐 왔던 가장 좋은 해와 모든 Particle들이 가지는 가장 좋은 해를 활용하여 방향과 속도를 재설정하며 반복적으로 이를 수행하여 최 적의 해를 찾는 모델이다.

PSO 알고리즘은 <Figure 1>와 같이 Particle의 움직임 에 따라 진행된다. 매 반복 당 도출되는 전체에서 가장 좋은 해인 Gbest값과 각 Particle이 갖고 있던 해중 가장 좋은 해인 Pbest로 다음 방향, 속도가 결정되어 움직이게 된다. x i k를 Particle i의 k번째 위치, v i k는 Particle i의 k번째 속 도라 정의하면, k+1번째의 위치와 속도는 다음의 식에 의해 계산되어 진다.

여기서 c₁와 c₂는 Learning Factor라 불리며 어느 정도 좋 은 해의 방향으로 Particle들이 방향, 속도를 바꿀 것인지 결정하는 계수로 일반적으로 c₁ = c₂ = 2가 주로 쓰인다. 그리고 r 1 t 과 r 2 t 는 Uniform(0, 1)를 따른 확률변수이며, Learning Factor가 얼마나 적용될 것인가를 매 반복마다 무 작위로 결정한다. 이와 같은 기본 개념을 바탕으로 PSO 알고리즘의 전형적인 구조는 다음과 같이 표현할 수 있다.

Initialize position x i 0, c₁, c₂, velocity v i 0.

Evaluate f i 0 (using x i 0)

Set P, Set N for (k < N) { for (i < P) {

v i k + 1 = v i k + c 1 r 1 k [ P b e s t i − x i k ] + c 2 r 2 k [ G b e s t i − x i k ] x i k + 1 = x i k + v i k + 1

Evaluate f i k (using x i k) if ( f i k ≤ f P b e s t i ) f P b e s t i = f i k , P b e s t i = x i k if ( f i k ≤ f G b e s t ) f G b e s t = f i k , G b e s t = x i k

} if (k ǁ N ∥ satisfied with terminal condition) stop; }N :

최대 반복 횟수

P :

총 Particle 수

i :

각 Particle에 부여된 고유 숫자(Particle Index)

t :

전체 Particle이 재생산된 횟수(Iteration Index)

<Figure 2>는 PSO 알고리즘을 활용하여 위성 임무 스 케줄링을 구하는 절차를 표현한 것으로 위성의 종류, 기 준에 따라 가중치, 제약 조건을 각 단계별로 설정하여 효 율적으로 위성임무 스케줄링 문제를 해결할 수 있다.

4실험 결과

4.1시나리오 생성

실제 고객의 요청 정보를 수집하는데 한계가 존재하 기 때문에 PSO 알고리즘이 위성 임무 계획 스케줄링에 대한 실험을 위해서 가상의 고객으로부터 요청받은 임무 와 그에 따른 각 임무별 세부 데이터가 필요하다. 이를 위해 <Table 2>와 같이 총 200개의 위성 임무의 정보를 난수를 발생시켜 임의로 생성하였다. 생성된 정보는 제 2장에서 변수 설명에 따른 제약과 조건을 고려하였다.

<Table 2>의 Distance는 임무사이의 거리를 의미하며, Angle은 각 임무를 수행하기 위한 위성의 촬영각을 나타 낸다.

4.2일반위성 시나리오 스케줄링

<Table 3>의 임의로 생성된 일반 위성의 가상 시나리오 를 PSO 알고리즘을 통해 스케줄링을 실시하고, 그 결과의 유효성을 검증하기 위해 동일한 문제에 대해 IBM ILOG CPLEX Optimization Studio를 이용하여 풀이한 결과와 비교 해 보았다. <Table 3>은 임무 수 50개, 100개, 200개의 가상 시나리오에 대해 PSO 알고리즘과 CPLEX를 이용한 결과를 각각 두 번째와 세 번째 행에 보여주고 있다. 그리고 기존 연구에서 적용한 것과 같이 에너지, 메모리, 운량에 대한 최대 허용치를 각각 Energy_max = 350, Memory_max = 5,500, Cloud_max = 70으로 설정하였다.

임무 수 50개, 100개, 200개에 대해 각각의 목적 값을 비교해 본 결과 그 값의 차이가 3% 이내임을 보여주고 있 으며, 이를 통해 PSO 알고리즘을 활용한 위성 임무 스케 줄링이 유효함을 확인 할 수 있다. 또한 본 연구에서는 5 가지 종류의 제약 조건만을 고려하였으나 현실에서 매우 복잡한 위성 임무 스케줄링 문제에 대해 많은 가정과 제 약 조건이 존재하는 것으로 알려졌다. 비록 현재의 모델을 적용하면 이 연구에서 제시한 PSO 알고리즘과 CPLEX를 이용한 경우는 크게 연산속도에 차이가 나지 않는 것으로 나타났으나 일반적으로 조건이 복잡해짐에 따라 PSO 알 고리즘의 유용성이 부각되는 것으로 알려져 있다. 향후 연구를 계속적으로 수행함에 있어 가정된 부분들을 제거 해 더욱 현실에 가까운 상태에서 스케줄링을 수행한다면 PSO 알고리즘을 통한 풀이는 CPLEX를 이용하여 문제를 해결하는 것 보다 경쟁력을 유지할 것이라 예상할 수 있 으며, 본 연구는 적용 가능성을 보여주었다는 점에서 그 의의를 찾을 수 있다.

4.3위성의 종류에 따른 스케줄링

제 2장에서 설명한 바와 같이 위성은 그 운영 목적에 따라 일반 위성, 상용 위성, 전술 위성으로 나눌 수 있으 며, 각 목적에 따라 고려해야 할 사항이 달라짐을 설명하 였다. 따라서 본 연구에서는 <Table 2>에서 생성한 50개 의 시나리오를 대상으로 위성의 종류에 따라 서로 다른 운영 목적을 고려한 각기 다른 변수 가중치를 적용하여 위성 임무 스케줄링 문제를 PSO 알고리즘으로 적용한 결과 <Table 4>와 같은 결과를 얻었다.

<Table 4>는 첫째 열은 <Table 1>에서 생성된 가상의 임무이며 숫자 0은 해당 임무가 스케줄링에 포함되지 않 음을 나타내고 숫자 1은 해당 임무가 스케줄링에 포함됨 을 의미하고 있다.

첫 번째 임무(M₁)의 경우 일반 위성과 전술 위성의 스 케줄에는 포함되지 않은 반면에 상용 위성의 스케줄에는 포함됨을 알 수 있다. 이는 M₁의 경우 상용 위성에서 가 장 중요한 인자인 임무 완료 기한과 보상에서 높은 점수 를 가지고 있어 상용 위성의 경우 수행해야 할 임무라 할 수 있으나, 일반 위성이나 전술 위성에서 가장 중요한 변수인 긴급성 측면에서는 0의 값을 갖고 있기 때문에 일반 위성이나 전술 위성에서는 우선 순위가 낮은 것이 당연하며 따라서 현 상황에서는 임무를 수행하지 않는 것이 최적의 해인 것으로 나타났다.

반대로 M₇의 경우에는 고객의 중요도와 긴급도에 관 한 변수의 값이 상대적으로 높기 때문에 해당 변수에 대 한 가중치가 높은 일반 위성과 전술 위성의 스케줄에 포 함되어 수행해야 할 임무라 할 수 있으나 상용 위성의 경우 이 두 가지 변수에 대한 가중치가 그리 크지 않기 때문에 만약 상업 위성이라 하면 이 임무는 다른 임무에 비해 우선 순위가 낮을 수 밖에 없어 현재 상황에 이 임 무는 수행되지 않는 것이 최적의 스케줄이라 할 수 있다.

나머지 임무들에 대해서도 위와 같은 방법으로 비교 분석하여 위성의 종류에 따라 변수에 대한 가중치를 서 로 다르게 설정하여 스케줄링을 시행하였을 때 그 위성 의 운영 목적에 적합한 임무들이 스케줄에 포함됨을 확 인할 수 있다. 위 결과로부터 일반 위성뿐 아니라 다른 운영 목적을 가진 위성에 대해서도 PSO 알고리즘을 활 용한 스케줄링의 유용성을 확인할 수 있다.

5결 론

위성 산업이 미래의 먹거리 산업으로 발전하면서 많 은 국가와 기업에서 관심을 기울이고 있으며, 이에 따라 많은 발전과 연구가 이루어지고 있다. 또한 위성을 이용 한 정보들이 생성되고 이를 요청하는 기업의 요구가 증 가하고 있다. 이러한 환경에서 고객의 요구를 효과적으 로 수행하기 위해 많은 노력을 기울이고 있는데, 그 중에 하나가 위성 임무 스케줄링이다.

본 연구는 최근까지 가장 활발하게 연구가 진행되고 있고 많은 분야에서 적용되고 있는 PSO 알고리즘을 위 성 임무 스케줄링에 적용하여 효율적인 스케줄링을 수립 하였고, 본 연구의 유용성을 검토하기 위해 임의로 생성 된 시나리오를 가지고 CPLEX를 이용한 최적해와 비교 해 봄으로써 본 연구에서 제시한 알고리즘을 유용성을 검증하였다.

임의로 생성된 위성 임무 200개와 각 임무의 각 종 정 보를 생성하였으며, 생성된 정보를 입력 요소로 본 연구 에서 제안된 PSO 알고리즘과 CPLEX를 이용하여 도출 된 최적해와 결과를 비교 분석하였다. 그 결과 최적해와 오차율이 3% 내외로 PSO 알고리즘을 활용한 위성 임무 스케줄링이 유효성이 있음을 확인 할 수 있었다. 그리고 운영 목적에 따라 구분되는 일반 위성, 상용 위성, 전술 위성에 대해서 각각의 성격에 맞는 가중치를 설정하여 스케줄링을 수행하고 그 결과를 비교하여 PSO 알고리즘 을 활용한 위성 임무 스케줄링이 목적에 따른 유연한 적 용이 가능함을 보여 주었다.

본 연구의 한계로는 다양한 임무를 가지고 있는 위성 의 임무 중 가장 많은 고객의 요청이 있는 위성 촬영 임 무를 주 연구 대상으로 하여, 실제 위성 임무 스케줄링을 수립하는데 한계를 가지고 있다. 그러나 다양한 임무를 고려하게 되면 복잡도가 증가하는데 본 연구에서 적용한 PSO 알고리즘은 기존의 많은 복잡한 문제에서도 훌륭한 성능을 발휘하는 것으로 알려져 있어 여전히 유용한 접 근 방법이라 할 수 있다. 또 하나의 한계는 국내 위성 산 업이 그리 발달되지 않는 관계로 실제 정보를 쉽게 구할 수 없어 이를 이용하기 쉽지 않았다는 점이 있다. 하지만 다양한 상업 위성이 국내에서도 도입되고 많은 정보들이 접근 가능하면 더 다양한 방향에서 연구가 진행될 수 있 을 것으로 기대하고 있다.