Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.41 No.1 pp.39-49
DOI : https://doi.org/10.11627/jkise.2018.41.1.039

A Mathematical Model for Optimal Communication Scheduling between Multiple Satellites and Multiple Ground Stations

Eugine Jeong^*

, Heungseob Kim^**†

^*3^rd Flying Training Wing, Republic of Korea Air Force
^**Department of Systems Engineering, Republic of Korea Air Force Academy

heungseob79@gmail.com

^†Corresponding Author : Heungseob Kim

Received 23/01/2018 Finally Revised 07/02/2018 Accepted 08/02/2018

Abstract

In the satellite operation phase, a ground station should continuously monitor the status of the satellite and sends out a tasking order, and a satellite should transmit data acquired in the space to the Earth. Therefore, the communication between the satellites and the ground stations is essential. However, a satellite and a ground station located in a specific region on Earth can be connected for a limited time because the satellite is continuously orbiting the Earth, and the communication between satellites and ground stations is only possible on a one-to-one basis. That is, one satellite can not communicate with plural ground stations, and one ground station can communicate with plural satellites concurrently. For such reasons, the efficiency of the communication schedule directly affects the utilization of the satellites. Thus, in this research, considering aforementioned unique situations of spacial communication, the mixed integer programming (MIP) model for the optimal communication planning between multiple satellites and multiple ground stations (MS-MG) is proposed. Furthermore, some numerical experiments are performed to verify and validate the mathematical model. The practical example for them is constructed based on the information of existing satellites and ground stations. The communicable time slots between them were obtained by STK (System Tool Kit), which is a well known professional software for space flight simulation. In the MIP model for the MS-MG problems, the objective function is also considered the minimization of communication cost, and ILOG CPLEX software searches the optimal schedule. Furthermore, it is confirmed that this study can be applied to the location selection of the ground stations.

Key Words : Satellite Communication System , Multiple Satellites , Scheduling , Visibility Conflict , Mixed Integer Programming

다수의 인공위성-지상국 간 통신 스케줄 최적화 모형

정유진^*

, 김흥섭^**†

^*공군 제3훈련비행단
^**공군사관학교 시스템공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

인공위성(Satellite)은 방송통신, 영상, 기상예보, 전자 지도, 내비게이션과 같은 편의 서비스부터 미사일 경보, 정밀유도항법, 감시․정찰 등의 안보․군사적 목적에 이 르기까지 현대인의 실생활과 뗄 수 없는 중요한 요소가 되었다. 또한, 인공위성을 운영함에 있어 지구와의 통신 은 필수적이다. 즉, 인공위성은 우주공간에서 관측한 영 상, 데이터 등을 지구로 송신하고, 지상국(Ground station) 에서는 인공위성의 상태 감시, 임무명령 전송 등을 지속 적으로 수행하여야 한다.

하지만, 지구의 특정 지역에 위치한 지상국이 우주공간 에서 지구를 공전하고 있는 인공위성과 통신할 수 있는 시간은 제한적이다. 즉, <Figure 1>에서와 같이 인공위성 이 지상국 상공의 한정된 공간을 비행하고 있는 동안에 만 통신이 가능하며, 인공위성과 지상국은 1:1 통신만이 가능하다. 즉, 하나의 인공위성이 복수의 지상국, 하나의 지상국이 복수의 인공위성과 동시에 통신할 수 없다. 따 라서 지상국과 통신이 가능한 공간을 2대 이상의 인공위 성이 동시에 비행하고 있다면, 지상국은 그 인공위성들 중 1대를 선정하여 통신하여야 한다. 또한, 과거에는 인 공위성의 임무가 간단하고, 운용 대수가 적어 지상국과 의 통신 스케줄 관리가 용이하였으나, 현재는 인공위성 의 임무도 다양해지고 운용 대수도 지속적으로 증가함에 따라 통신 스케줄 관리의 복잡도도 점증되고 있다. 따라 서 인공위성-지상국 간의 통신 스케줄링은 인공위성 운 용의 효율성에 직접적인 영향을 미치게 되었으며, 이에 따라 관련 연구도 활발하게 수행되고 있다. 다수의 인공 위성-지상국 간 통신 스케줄링 문제는 m대의 기계에 n 개의 작업을 할당하는 n-Job/m-Machine 문제 또는 다중 선택 배낭문제(Multiple knapsack problem)와 유사하지만 [3, 4, 10], 통신환경의 특수성이 고려되어야 한다.

인공위성 운용 환경에서의 스케줄링(Scheduling)에 대 한 기존 연구들의 주제는 크게 인공위성의 임무 스케줄링 과 지상국과의 통신 스케줄링 문제로 분류되며, 이들은 유사한 특성을 갖는다. 예를 들어, 지구관측 영상을 촬영 하여 제공하는 인공위성은 지정된 임무지역 상공을 비행 하는 제한된 시간 동안 영상을 촬영할 수 있으며, 촬영한 영상의 송신은 지상국과 통신이 가능한 공간을 비행하는 시간 동안에 한해 가능하다는 공통점을 갖는다. 이러한 임무수행과 통신이 가능한 시간대(Time slot)는 인공위성 의 비행궤도(Orbit)에 따라 결정된다. 또한, 하나의 인공위 성에 여러 임무가 부여되거나, 여러 인공위성이 지상국과 통신을 시도할 때에는 임무/통신이 가능한 시간대들이 중 복될 수 있다. 따라서 임무 스케줄링은 고유의 시간대를 갖는 다수의 임무들 중 실제 수행할 임무들을 선택하는 문제로, 선택된 임무들 간에 시간대의 중복(Overlapping) 이 없어야 하며, 목적함수는 주로 고객의 중요도, 긴급성, 보상 등을 고려하여 수익(Profit)이 최대화로 고려되고 있다. 유사하게, 통신 스케줄링 문제에서는 인공위성별 지구로 전송할 데이터 용량에 따라 필요한 통신 시간을 충족할 수 있도록 시간대들을 할당한다. 또한, 인공위성 스케줄링 연구들은 고려하는 인공위성과 지상국의 수에 따라 Single Satellite/Single Ground station(SS-SG)[1, 2, 7, 14, 18], SS/ Multiple Ground station(SS-MG)[17, 23], MS-SG[6, 15], 그 리고, 가장 일반화된 형태의 문제로 MS-MG[5, 11-13, 16, 19-22]와 같이 분류된다. 이러한 연구들은 인공위성의 통 신 환경을 비선형 모델(Nonlinear model)로 제시하고, 해법 으로써 유전자 알고리즘(Genetic algorithm), 탐욕적 탐색 (Greedy search) 알고리즘, 타부서치(Tabu search) 등의 메타- 휴리스틱(Meta-heuristic)을 이용하고 있다. 하지만, 이들은 짧은 계산시간의 장점을 갖으나, 최적해(Optimal solution) 를 보장하지 않는다.

따라서 본 연구는 기존 연구들이 비선형 모델로 제시한 인공위성 통신환경의 제약조건들을 선형화하고, MS-MG 환경에서 인공위성 통신 스케줄링 최적화를 위한 혼합 정수계획(MIP : Mixed Integer Programming) 모형을 제시 한다. 수리모형의 목적함수는 다양하게 고려될 수 있으 나, 본 연구에서는 통신비용 최소화로 설정하였다. 또 한, 복수의 인공위성이 하나의 지상국과 통신할 수 있 는 시간대가 중복되는 경우, 임의의 인공위성과 지상국 의 통신 시작․종료 시간에 대한 결정변수는 해당 시간 대를 인공위성들 간에 나누어 사용할 수 있도록 설계되 었다. 또한, 통신 효율성을 향상시킬 수 있는 인공위성 들 간의 상대위치 조정에 대한 정보를 제공할 수 있는 결정변수를 도입하였으며, 이는 인공위성 개발 및 발사 에 대한 중․장기적 계획에 참고할 수 있을 것이다(제 2장 참고).

본 연구의 제 2장에서는 인공위성 통신환경에 대한 문제를 정의하고, 통신 스케줄링을 위한 혼합정수계획(MIP) 모형 을 제시한다. 제 3장에서는 실제의 인공위성들과 지상국들 을 대상으로 통신 스케줄링에 대한 수치실험 수행 결과를 제시하며, 수치실험에는 AGI사의 STK(System Tool Kit)와 IBM사의 ILOG CPLEX가 사용되었다. 마지막으로, 제 4장 에서는 결론 및 향후 연구방향을 제시한다.

2. 문제정의 및 수리모형

2.1. 문제정의

우주공간에서 지구를 공전하는 인공위성의 시간에 따 른 궤적(Trajectory)은 궤도의 모양, 크기, 방향, 자세를 정 의하기 위한 5가지, 궤도상의 위치를 정의하는 1가지로 구 성된 궤도요소(Orbit elements)에 따라 결정되며, <Figure 2>는 지구를 중심으로 하는 스푸트니크 케플러 타원 궤도 의 궤도요소를 정의하고 있다[9].

또한, 다수의 인공위성이 각자의 궤도를 따라 비행할 때, 지구상의 임의 지상국과 통신할 수 있는 시간대와 각 인공위성의 제원에 따라 각 시간대에서 전송 가능한 데 이터 용량을 <Figure 3>과 같은 형태로 가시화(Visualization) 할 수 있으며, 각 인공위성의 통신 시간대는 공전주 기에 따라 반복된다. 또한, <Figure 3>에서 시뮬레이션 시 간 약 10분에 인공위성 6대(#02~#05, #7, #10)의 통신 시 간대가 중복되고 있다. 이러한 경우, 지상국은 6대의 인공 위성 중 1대만을 선택하여 통신할 수 있다. 따라서 각 인 공위성은 수집된 데이터를 지구로 전송하기 위한 통신 시간을 할당받아야 하며, 이를 위해 중복된 시간대를 여 러 인공위성이 분할하여 사용할 수도 있다. 단, 지상국과 통신하는 인공위성이 변경될 때, 통신모드 변환, 안테나 지향점 조정 등을 위한 시간(Set-up time)이 필요하다. 예 를 들어, 인공위성 #02와 #03의 시간대가 각각 4~13분, 6~14분이라 할 때, 인공위성 #02가 4~10분 동안 통신, 10~ 11분 동안 인공위성 #03과 통신을 위한 준비, 그리고 11분 부터 14분까지 인공위성 #03과 통신이 연결된다.

2.2. 혼합정수계획(MIP) 모형

본 절에서는 다수의 인공위성과 다수의 지상국이 운용 되고 있고, 인공위성이 임의의 지상국과 통신하려면 통신 비용을 지불해야하는 상황을 가정하고, 총 통신비용을 최 소화하는 인공위성-지상국 통신 스케줄을 수립하기 위한 혼합정수계획(MIP) 모형을 제시한다. 또한, 혼합정수계획 모형에서 사용된 표기(Notation)와 결정변수(Decision variables) 는 다음과 같다.

<표기(Notation)>

S : 인공위성 인덱스 집합; i∈S
G : 지상국 인덱스 집합; j∈G
K : 인공위성-지상국 통신 시간대 집합; k∈K
T_sim : 시뮬레이션 시간
T_min : 최소 통신시간
$T_{i j k}^{S}, T_{i j k}^{E}$ : 인공위성 i와 지상국 j의 k번째 통신 시간 대의 시작과 종료 시간
D_i : 인공위성 i가 전송할 데이터 용량(Mb)
r_ijk : 인공위성 i와 지상국 j간의 k번째 통신 시 간대에서 데이터 전송 속도(Mbps)
F_j : 지상국 j에 대한 고정 사용료
Vj : 데이터 용량에 비례하는 지상국 j의 사용료
M : 충분히 큰 수(Big-M)

<결정변수(Decision variables)>

$x_{i j k} = {\begin{array}{l} 1, & 인공위성 i 와 지상국 j 가 k 번째 통신 \\ 0, & 시간대에서 통신하면, \end{array}$
$z_{j} = {\begin{array}{l} 1, & 지상국 j 가 인공위성 통신에 사용되면, \\ 0, & Otherwise \end{array}$
$s_{i j k}, e_{i j k}$
Δt_i : 인공위성 i의 통신 시간대 조정량(시간)

(11)(12)

Minimize \sum_{j \in G} [F_{j} z_{j} + V_{j} \sum_{i \in S} \sum_{k \in K} r_{i j k} (e_{i j k} - s_{i j k})]

(1)

subject to :

T_{i j k}^{s} + Δ t_{i} \leq s_{i j k}, \forall i \in S, \forall j \in G, \forall k \in K

(2)

s_{i j k} + T_{Min} x_{i j k} \leq e_{i j k}, \forall i \in S, \forall j \in G, \forall k \in K

(3)

e_{i j k} \leq Min [T_{Sim}, T_{i j k}^{E} + Δ t_{i}], \forall i \in S, \forall j \in G, \forall k \in K

(4)

\begin{array}{l} (e_{i j k} - s_{i j k}) + (e_{h j q} - s_{h j q}) \\ \leq Max [e_{i j k}, e_{h j q}] - Min [s_{i j k}, s_{h j q}], \\ \leq i \in S, h \in S (h \neq i), \forall j \in G, \\ \forall k \in K, q \in K (q \neq k) \end{array}

(5)

\begin{array}{l} (e_{i j k} - s_{i j k}) + (e_{i υ q} - s_{i υ q}) \\ \leq Max [e_{i j k}, e_{i υ q}] - Min [s_{i j k} - s_{i υ q}], \\ \forall i \in S, \forall j \in G, υ \in G (υ \neq j), \\ \forall k \in K, q \in K (q \neq k) \end{array}

(6)

r_{i j k} \sum_{j \in G} \sum_{k \in K} (e_{i j k} - s_{i j k}) \geq D_{i}, \forall i \in S

(7)

\frac{1}{M} (e_{i j k} - s_{i j k}) \leq x_{i j k}, \forall i \in S, \forall j \in G, \forall k \in K

(8)

\frac{1}{M} \sum_{i \in S} \sum_{k \in K} x_{i j k} \leq z_{j}, \forall j \in G, \forall k \in K

(9)

x_{i j k} \in {0, 1}, \forall i \in S, \forall j \in G, \forall k \in K

(10)

z_{j} \in {0, 1}, \forall j \in G

(11)

s_{i j k}, e_{i j k} \geq 0, \forall i \in S, \forall j \in G, \forall k \in K

(12)

Δ t_{i} \geq 0, \forall i \in S

(13)

수리모형의 목적함수 식 (1)은 인공위성 통신을 위한 지상국 사용료를 최소화하는 것이며, 지상국별 사용료는 고정비(Fixed cost)와 전송되는 데이터 용량에 비례하여 지불하는 변동비(Variable cost)의 합으로 구성된다. 식 (2) 는 <Figure 4>와 같이 인공위성 i의 통신 시간대에 Δt_i의 조정이 있을 때, 지상국 j와 k번째 시간대에서의 통신시 작 시간(s_ijk)은 조정된 시간대 내에 있어야 함을 제약하고 있다. 또한, <Figure 4>는 시간대 조정을 통해 시간대 간 의 중복을 회피할 수 있음을 설명하고 있다. 즉, Satellite 1과 2가 임의의 지상국과 연결되는 시점을 조정하는 것으 로, <Figure 4>에서는 Satellite 2의 진입을 늦춰 인공위성 들 간의 임의의 시점에서의 상대적 위치를 조정하는 예시 를 보여주고 있다. 이는 Satellite 2의 발사단계에서의 발사 시간 조정 또는 운영단계에서 일시적 궤도 조정을 통해 실현될 수 있다.

식 (3)은 통신모드 변경, 안테나 조정 등의 준비시간을 고려할 때, 단시간의 통신은 비효율적이기 때문에 최소 T_min 이상의 통신시간이 확보되도록 하고, 식 (4)는 통신 종료시간(e_ijk)은 시뮬레이션 시간과 조정된 시간대의 종 료시간 이내에서 결정되어야 함을 제약하고 있다. 식 (5)와 식 (6)은 임의의 인공위성과 지상국에 할당되는 시간대들 간의 중복(Overlap)을 방지하기 위한 제약으로, <Figure 5> 에 제시된 논리에 따라 설계되었다. 세부적으로, 식 (5) 는 임의의 지상국을 기준으로 각 인공위성에 할당된 통 신 시간대의 중복을 점검한다. 즉, 임의의 지상국은 동시 에 복수의 인공위성과 통신할 수 없다. 또한, 식 (6)은 임 의의 인공위성이 동시에 여러 지상국과 통신할 수 없도 록 한다.

식 (7)은 인공위성과 지상국 간의 데이터 전송 속도를 고려하여, 각 인공위성이 수집된 데이터 용량을 전송할 수 있을 만큼의 통신시간이 할당되어야 함을 의미한다. 식 (8)은 인공위성 i와 지상국 j의 k번째 시간대에 통신 시간이 할당되면 결정변수 x_ijk가 1이 되도록 하며, 식 (9) 는 지상국 j가 사용되면 결정변수 z_i가 1이 되도록 한다. 식 (10)부터 식 (13)까지는 결정변수의 범위와 형태를 지 정한다. 즉, 결정변수 x_ijk와 z_i는 이진형(Binary) 변수이며, s_ijk, e_ijk와 Δt_i는 양의 실수(Positive real number)로 정의 된다.

3. 수치실험 및 결과

본 장에서는 제 2장에서 제시된 최적화 수리모형을 검증하고, 현실 사례에서의 적합성 검토하기 위한 수치 실험을 수행하고, 실험결과를 제시한다. 실험예제는 실 제 운용되었거나, 운용 중인 인공위성과 지상국을 대상 으로 하였으며, 수치실험에 이용된 인공위성에 대한 궤 도 정보는 <Table 1>, 지상국에 대한 정보는 <Table 2> 와 같다. 또한, 각 인공위성과 지상국 간의 통신 가능 시 간대의 데이터는 우주비행 시뮬레이션을 위한 전문 소 프트웨어인 AGI사의 STK를 통해 생성하였다. STK는 <Table 1>과 같은 인공위성 궤도 정보와 실제적인 중력장 (Gravitational field) 모델을 기반으로 우주비행을 모의하고, <Table 2>와 같은 지상국 위치 정보에 따라 <Figure 6>과 같은 형태로 각 인공위성과 통신할 수 있는 시간대 데이 터를 제공한다.

3.1. MS-MG 통신 스케줄링

본 절에서는 우리나라의 인공위성 5대(ARIRANG 3대, SITSAT-2C, OSSI-1)와 지상국 10개소를 대상으로 통신 스케줄을 수립하는 수치실험이 수행되었으며, 제 2장의 수리모형과 실험예제 데이터의 적합성을 점검하는데 목 적이 있다. <Table 3>은 인공위성별 전송할 데이터 용량, 전송속도와 인공위성-지상국의 통신 시간대 입력 데이터의 예시를 보여주고 있으며, 통신 시간대는 AGI사의 STK를 통해 얻어진 인공위성 5대와 우리나라의 지상국 KGS 간 의 현황이다. 또한, 최소 통신시간 T_min은 0.5분(30초)으 로 가정하였다.

실험예제의 최적해(Optimal solution)는 IBM사의 ILOG CPLEX를 이용하여 탐색되었으며, 실험결과를 통해 시 간대 중복 방지 제약 등 제 2장의 수리모형이 정상적으 로 작동함을 확인할 수 있었으며, 각 인공위성과 지상국 간의 통신시간 할당 현황은 <Table 4>와 같았다. 이때, 총 10개의 지상국 중 Alcantara와 South Africa 지상국은 사용되지 않았으며, McMurdo부터 Pocker Flat까지의 지 상국 5개소는 사용률(Utilization)이 낮게 나타났다. 하지 만, 이러한 지상국들에도 고정비를 지불하게 된다. 따라 서 통신비용 절감을 위해 인공위성 설계/발사 단계에서 데이터 전송속도 향상과 궤도 조정 등을 검토를 통해 사용하는 지상국을 감소시킬 필요가 있음을 시사하고 있다.

3.2. 인공위성의 통신 시간대 조정 효과

본 절에서는 제 3.1절에서 제기된 인공위성들의 통신 시간대 조정(Δt_i )에 대한 효과를 검토한다. 실험은 인공 위성 5대와 지상국 7개소에 대해 수행되었다. 인공위성은 우리나라의 ARIRANG-3, STSAT-3과 독일의 RAPIDEYE-5, COMPASS-1, 그리고, 미국의 SWAS가 사용되었으며, 지 상국은 Perth, KGS, GSOC, Wallops, Poker Flat, S. Africa 와 Massda로 고려하였다. 또한, 시간대의 조정은 우리나 라의 인공위성 ARIRANG-3(i = 1), STSAT-3(i = 1)에 한 해 가능하고, 다른 국가의 인공위성에 대해서는 현재의 궤도를 유지함을 가정하였다. 이러한 상황은 이미 운영 중에 있는 3대의 인공위성이 있을 때, 통신 효율성을 측 면에서 신규로 발사하는 인공위성 2대의 발사계획 조정 을 검토하는 것과 유사한 의미를 갖는다. 이러한 상황을 묘사하기 위해 수리모형의 식 (13)은 식 (14), 식 (15)와 같이 변경하여 적용된다.

Δ t_{i} \geq 0, \forall i \in {1, 2}

(14)

Δ t_{i} = 0, \forall i \in {3, 4, 5}

(15)

수치실험에 사용된 인공위성과 지상국에 대한 파라미 터는, 인공위성별 전송할 데이터 용량(Amount of data)과 전송속도(Transfer rate)는 <Table 5>, 그리고, 지상국별 사 용료(F_j, V_j)는 <Table 2>에 제시된 바와 같다. 또한, 최소 통신시간 T_min은 0.5분으로 가정하였으며, 각 인공위성- 지상국 간의 통신 가능 시간대는 AGI사의 STK의 시뮬레 이션 결과를 이용하였다.

일부 인공위성의 통신 시간대 조정에 대한 효과는 시간대 조정이 없는 경우(Δt_i = 0, ∀i)와의 비교를 통해 분석된다. <Table 6>은 실험결과를 요약하여 보여주고 있으며, 세부적 인 인공위성-지상국 간의 통신 스케줄링 결과는 <Table 7> 과 <Table 8>에 제시되었다. 통신 시간대 조정이 없는 경우 에서는 지상국 7개소 중 Wallops, Poker Flat, Massda를 제외 한 4개소가 사용되었으며, 지상국 사용료는 총 50,444.5 단 위로 산정되었다. 또한, ARIRANG-3와 STSAT-3의 통신 시간대 조정을 검토하기 위한 실험에서는, 두 인공위성의 통신 시간대를 약 13분(Δt₁ = Δt₂ = 12.99) 정도 늦추면, S. Africa 지상국이 추가적으로 제외되어 Perth, KGS, GSOC 지상국 3개소만으로 모든 데이터를 전송할 수 있게 되었다. 이때, 지상국 사용료는 49,294.5 단위로 산정되었으며, 통신 시간대 조정이 없는 경우에서의 지상국 사용료 50,444.5 단위 대비 1,150 단위(약 2.3%)가 절감되었다.

4. 결론 및 향후 연구방향

인공위성의 운용 목적을 달성하기 위해서는 지구와의 지속적인 통신이 필수적이며, 이에 따라 통신 스케줄은 인 공위성 활용도에 직접적인 영향을 미친다. 또한, 인공위성 과 지상국 간의 통신 환경은 일반적인 산업현장에서의 스 케줄링 환경과 다소의 차별성을 갖는다. 가장 주요한 특징 으로는, 인공위성이 지구를 공전함에 따라 특정 시간대에 한해 통신이 가능하고, 인공위성과 지상국이 1:1 통신만 가능하다는 것이다. 더욱이, 다수의 인공위성과 다수의 지 상국에 대한 통신 스케줄링의 복잡도는 인공위성과 지상 국의 수가 증가함에 따라 지수적으로 증가한다. 따라서 본 연구는 다수의 인공위성-지상국의 통신 스케줄링을 자동 화하기 위한 혼합정수계획 모형을 제안하였다. 또한, 실제 적인 실험예제를 구성하고, 이에 대한 수치실험을 통해 수 리모형의 적합성과 본 연구의 실효성을 검증하였다. 또한, 본 연구의 수치실험은 현존하는 지상국들을 대상으로 수 행되었다. 하지만, 그들의 위치를 지상국 건설을 위한 후 보지로 고려한다면, 이는 지상국 입지선정 문제로 전환된 다. 즉, 본 연구의 결과는, 중․장기적 인공위성 발사/운용 계획 수립과 지상국 임차 및 건설을 위한 검토 등에 다양 하게 활용될 수 있을 것으로 기대한다.

향후 연구방향으로는, 첫째, 본 연구를 포함한 현재까 지의 인공위성 스케줄링 관련 연구들은 인공위성의 임무 와 통신(데이터 전송) 중 한 가지만을 고려하고 있다. 하 지만, 지구관측, 정찰위성 등과 같은 경우, 임무(영상 촬 영) 후 데이터를 전송하는 임무-통신의 순서가 고려되어 야 하며, 영상 저장을 위한 메모리(Memory)의 제약으로 다음 임무 전에 데이터를 전송해야 할 수도 있다. 따라서 임무와 통신을 동시에 고려한 연구가 필요하다. 둘째로 는, 본 연구에서는 인공위성 스케줄링을 위해 통신만을 고려하고 있으나, 보다 다양한 현실적 요소들을 고려할 필요가 있다. 즉, 각 인공위성의 잔여 에너지(Energy), 메모 리 등에 따라 통신 긴급도가 달라질 수 있다. 따라서 이에 대한 연구들에서는 여러 요소들을 동시에 고려하기 위해 다기준 의사결정(MCDM : Multi-criteria decision making) 방법론이 도입되거나, 다목적(Multi-objective) 최적화 문 제로 고려될 수 있다.

Figure

<Figure 1>.

Communicable Condition between a Satellite and a Ground Station[7, 11]

<Figure 2>.

Six Elements of Kepler Orbit[9]

<Figure 3>.

Example of Communicable Slots

<Figure 4>.

Adjustment of Communicable Slot

<Figure 5>.

Discriminant of Schedule Overlap

<Figure 6>.

Communicable Slot Data by STK

Table

<Table 1>.

Information on Satellites

Satellite	Nationality	Semi-majoraxis	Eccentricity	Inclination	Arg’ of perigee	RAAN	True anomaly
ARIRANG-2	S. Korea	7063.14km	0.0017	98.13°	308.29°	108.08°	51.68°
ARIRANG-3	S. Korea	685km(Sun-sync’)	0.0008	98.16°	272.13°	145.64°	87.89°
ARIRANG-5	S. Korea	550km(Sun-sync’)	0.0002	97.61°	96.26°	33.24°	354.65°
SITSAT-2C	S. Korea	Sun-synchronous	0.0447	80.23°	49.23°	163.4°	314.60°
STSAT-3	S. Korea	6993.26km	0.0022	97.68°	184.12°	33.61°	175.98°
OSSI-1	S. Korea	6,778.00km	0.0215	64.90°	59.00°	114.84°	350.06°
RAPIDEYE-5	Germany	620km(Sun-sync’)	0.0016	97.80°	160.75°	48.65°	199.44°
COMPASS-1	Germany	6,967.00km	0.0014	97.59°	96.60°	5.79°	263.68°
SWAS	U.S.A.	6,968.10km	0.0005	69.89°	74.66°	85.85°	285.51°

<Table 2>.

Information on Ground Stations

Station	Perth	Alcantara	KGS	McMurdo	GSOC	Syalbard	Wallops	PokerFlat	S.Africa	Massda
Nationality	Australia	Brazil	S. Korea	Antarctica	Germany	Norway	U.S.A.	U.S.A.	S. Africa	Japan
Latitude	-31.9513	-2.3906	36.3760	-77.8426	48.0873	78.8580	37.9344	39.6940	-33.8563	30.6153
Longitude	115.8608	-44.4099	127.3541	166.6948	11.2815	17.5520	-15.4861	-120.8436	23.0797	130.9906
Fee	Fixed	1,250	1,300	1,150	1,200	1,200	1,400	1,350	1,200	1,150	1,200
Var.	12/Mb	13/Mb	14/Mb	15/Mb	13/Mb	12/Mb	14/Mb	15/Mb	16/Mb	14/Mb

<Table 3>.

Example of Communicable Slots Data(Station : KGS, Time unit : min.)

Satellite	Amount of data(Transfer rate)	Communicable slots
ARIRANG-2	1,530Mb (0.250Mbps)	Start	104.59	200.33	299.20	767.68	861.64	961.28	-
End	113.90	214.24	308.83	776.37	875.58	971.77	-
ARIRANG-3	1,620Mb (0.270Mbps)	Start	230.36	327.06	426.98	893.08	988.50	1,090.08	-
End	241.81	340.65	433.57	903.94	1,002.41	1,097.32	-
ARIRANG-5	1,580Mb (0.283Mbps)	Start	406.05	499.34	1,194.05	1,288.50	-	-	-
End	416.16	510.67	1,205.27	1,298.66	-	-	-
STSAT-2C	1,235Mb (0.275Mbps)	Start	1,144.05	1,157.45	1,170.91	1,184.40	1,197.92	1,211.47	1,225.00
End	1,144.55	1,158.16	1,171.71	1,185.23	1,198.71	1,212.14	1,225.50
OSSI-1	905Mb (0.265Mbps)	Start	679.40	779.51	880.67	982.32	1,084.86	-	-
End	689.30	791.53	893.08	994.08	1,093.78	-	-

<Table 4>.

Experimental Result of Section 3.1(Time unit : min.)

Classification	Perth	KGS	McMurdo	GSOC	Syalbard	Wallops	PokerFlat	Massda	Sum
Communicable time	267	255	259	402	271	281	256	233	2,224
Assigned time	238	89	16	3	11	4	16	48	425
	ARIRANG-2	51	21	-	-	-	-	-	30	102
ARIRANG-3	53	33	-	-	-	-	-	14	100
ARIRANG-5	25	12	16	3	11	4	16	7	94
STSAT-2C	75	-	-	-	-	-	-	-	75
OSSI-1	34	23	-	-	-	-	-	-	57
Utilization	89.1%	34.9%	6.2%	0.7%	4.1%	1.4%	6.3%	20.6%	19.1%

<Table 5>.

Input Parameters for the Example of Section 3.2

Satellite	S. Korea	Germany	U.S.A.
Amount of data	1,830Mb	1,860Mb	1,850Mb	1,860Mb	1,860Mb
Transfer rate	0.270Mbps	0.250Mbps	0.260Mbps	0.280Mbps	0.295Mbps

<Table 6>.

Communication Time between Satellites and Stations(Time unit : min.)

Station	Condition	Perth	KGS	Wallops	PokerFlat	GSOC	S. Africa	Massda	Sum
ARIRANG-3	∆ti = 0(∀i)	80.8	-	-	-	32.2	-	-	113.0
∆t1, ∆t2 ≒13	80.8	-	-	-	32.2	-	-	113.0
STSAT-3	∆ti = 0(∀i)	68.8	4.2	-	-	51.1	-	-	124.1
∆t1, ∆t2 ≒13	68.8	4.2	-	-	51.1	-	-	124.1
RAPIDEYE-5	∆ti = 0(∀i)	11.2	51.8	-	-	5.6	50.0	-	118.6
∆t1, ∆t2 ≒13	60.2	30.0			28.4	-	-	118.6
COMPASS-1	∆ti = 0(∀i)	50.1	21.5	-	-	26.6	12.6	-	110.8
∆t1, ∆t2 ≒13	59.7	23.7	-	-	27.4	-	-	110.8
SWAS	∆ti = 0(∀i)	72.5	1.6	-	-	31.0	-	-	105.1
∆t1, ∆t2 ≒13	73.6	5.0	-	-	26.5	-	-	105.1
Total	∆ti = 0(∀i)	283.4	79.1	-	-	146.5	62.6	-	571.6
∆t1, ∆t2 ≒13	343.1(+59.7)	62.9(-16.2)	-	-	165.6(+19.1)	-(-62.6)	-	571.6

<Table 7>.

Experimental Result of Section 3.2(when ∆t_i = 0, ∀_i)

Satellite	Station	Slot	#1	#2	#3	#4	#5	#6	#7	#8	#9
ARIRANG-3 (i= 1)	Perth	Start	5.2	105.8	719.5	816.9	915.6	1,293.5	1,387.3	-	-
End	19.1	115.4	732.4	830.4	924.4	1,302.1	1,400.8	-	-
Duration	13.9	9.6	12.9	13.5	8.8	8.6	13.5	-	-
GSOC	Start	231.4	328.7	891.2	986.9	1,091.3	-	-	-	-
End	243.9	335.2	893.1	996.9	1,092.6	-	-	-	-
Duration	12.5	6.5	1.9	10.0	1.3	-	-	-	-
STSAT-3 (i= 2)	Perth	Start	41.8	138.1	236.8	605.7	698.7	795.7	1,401.8	-	-
End	54.6	149.7	239.9	614.2	711.3	806.9	1,410.8	-	-
Duration	12.8	11.6	3.1	8.5	12.6	11.2	9.0	-	-
KGS	Start	222.5	X	X	1,015.0	1,111.7	-	-	-	-
End	223.0	X	X	1,016.2	1,114.2	-	-	-	-
Duration	0.5	-	-	1.2	2.5	-	-	-	-
GSOC	Start	210.0	305.7	922.7	1,016.2	1,114.2	-	-	-	-
End	221.4	317.4	930.1	1,029.3	1,121.7	-	-	-	-
Duration	11.4	11.7	7.4	13.1	7.5	-	-	-	-
RAPIDEYE-5 (i= 3)	Perth	Start	39.6	136.3	235.7	614.2	711.3	X	1,410.7	-	-
End	41.7	138.1	236.8	615.0	712.2	X	1,415.2	-	-
Duration	2.1	1.8	1.1	0.8	0.9	-	4.5	-	-
KGS	Start	210.0	306.0	923.2	1,016.9	1,114.4	-	-	-	-
End	222.0	317.4	929.6	1,029.3	1,124.0	-	-	-	-
Duration	12.0	11.4	6.4	12.4	9.6	-	-	-	-
GSOC	Start	208.0	304.5	930.1	1,029.3	X	-	-	-	-
End	210.0	305.7	930.5	1,031.3	X	-	-	-	-
Duration	2.0	1.2	0.4	2.0	-	-	-	-	-
S.Africa	Start	64.0	677.2	779.3	1,330.6	1,425.5	-	-	-	-
End	71.3	689.7	785.8	1,341.4	1,438.4	-	-	-	-
Duration	7.3	12.5	6.5	10.8	12.9	-	-	-	-
COMPASS-1 (i= 4)	Perth	Start	69.1	165.6	630.3	732.4	830.5	1,425.3	-	-	-
End	82.0	175.6	640.7	737.0	831.8	1,436.2	-	-	-
Duration	12.9	10.0	10.4	4.6	1.3	10.9	-	-	-
KGS	Start	X	X	334.7	945.6	1,039.9	1,137.6	-	-	-
End	X	X	335.2	946.5	1,052.8	1,144.8	-	-	-
Duration	-	-	0.5	0.9	12.9	7.2	-	-	-
GSOC	Start	146.4	243.9	335.2	946.5	1,052.8	-	-	-	-
End	148.9	248.6	343.0	957.1	1,053.8	-	-	-	-
Duration	2.5	4.7	7.8	10.6	1.0	-	-	-	-
S.Africa	Start	X	702.5	X	X	-	-	-	-	-
End	X	715.1	X	X	-	-	-	-	-
Duration	-	12.6	-	-	-	-	-	-	-
SWAS (i= 5)	Perth	Start	21.5	121.4	219.9	318.7	X	1,071.1	1,166.7	1,266.5	1,369.0
End	27.3	130.3	232.5	331.5	X	1,079.8	1,179.9	1,274.0	1,372.0
Duration	5.8	8.9	12.6	12.8	-	8.7	13.2	7.5	3.0
KGS	Start	X	X	X	1,190.0	X	X	-	-	-
End	X	X	X	1,191.6	X	X	-	-	-
Duration	-	-	-	1.6	-	-	-	-	-
GSOC	Start	583.0	680.0	X	1,192.0	X	X	-	-	-
End	592.0	692.0	X	1,202.0	X	X	-	-	-
Duration	9.0	12.0	-	10.0	-	-	-	-	-

<Table 8>.

Experimental result of Section 3.2(when ∆t_i ≥ 0, i∈{1, 2} and ∆t_i ≥ 0, i∈{3, 4, 5})

Satellite	Station	Slot	#1	#2	#3	#4	#5	#6	#7	#8	#9
ARIRANG-3 (i= 1)	Perth	Start	18.2	118.8	732.5	829.9	928.6	1,306.4	1,400.3	-	-
End	32.1	128.4	745.4	843.4	937.4	1,315.0	1,413.8	-	-
Duration	13.9	9.6	12.9	13.5	8.8	8.6	13.5	-	-
GSOC	Start	250.2	353.1	904.2	1,000.9	1,104.3	-	-	-	-
End	256.9	353.6	915.2	1,013.6	1,105.6	-	-	-	-
Duration	6.7	0.5	11.0	12.7	1.3	-	-	-	-
STSAT-3 (i= 2)	Perth	Start	54.8	151.1	249.8	618.7	711.7	808.7	1,414.8	-	-
End	67.6	162.7	252.9	627.2	724.3	819.9	1,423.8	-	-
Duration	12.8	11.6	3.1	8.5	12.6	11.2	9.0	-	-
KGS	Start	234.5	330.4	X	X	1,124.7	-	-	-	-
End	235.7	330.9	X	X	1,127.2	-	-	-	-
Duration	1.2	0.5	-	-	2.5	-	-	-	-
GSOC	Start	223.0	318.7	935.7	1,029.2	1,127.2	-	-	-	-
End	234.4	330.4	943.1	1,042.3	1,134.7	-	-	-	-
Duration	11.4	11.7	7.4	13.1	7.5	-	-	-	-
RAPIDEYE-5 (i= 3)	Perth	Start	39.6	136.3	235.7	605.3	699.1	796.9	X	-	-
End	52.5	147.9	237.9	615.0	711.7	808.1	X	-	-
Duration	12.9	11.6	2.2	9.7	12.6	11.2	-	-	-
KGS	Start	209.9	316.4	X	1,016.9	1,114.4	-	-	-	-
End	222.0	318.4	X	1,029.9	1,117.3	-	-	-	-
Duration	12.1	2.0	-	13.0	2.9	-	-	-	-
GSOC	Start	208.0	304.5	923.8	X	1,117.3	-	-	-	-
End	210.0	316.4	932.4	X	1,123.2	-	-	-	-
Duration	2.0	11.9	8.6	-	5.9	-	-	-	-
COMPASS-1 (i= 4)	Perth	Start	69.1	165.6	630.3	724.3	822.6	1,425.3	-	-	-
End	82.0	175.6	640.7	732.5	829.9	1,436.2	-	-	-
Duration	12.9	10.0	10.4	8.2	7.3	10.9	-	-	-
KGS	Start	X	237.9	334.7	945.6	X	1,137.6	-	-	-
End	X	250.2	338.4	946.1	X	1,144.8	-	-	-
Duration	-	12.3	3.7	0.5	-	7.2	-	-	-
GSOC	Start	146.4	236.2	333.7	946.5	1,042.2	-	-	-	-
End	148.9	237.9	334.7	957.1	1,053.8	-	-	-	-
Duration	2.5	1.7	1.0	10.6	11.6	-	-	-	-
SWAS (i= 5)	Perth	Start	X	X	219.9	318.7	419.7	1,071.1	1,166.8	1,266.5	1,369.0
End	X	X	232.5	331.5	425.8	1,079.8	1,179.9	1,278.6	1,377.2
Duration	-	-	12.6	12.8	6.1	8.7	13.1	12.1	8.2
KGS	Start	X	X	X	1,190.0	X	1,389.0	-	-	-
End	X	X	X	1,192.0	X	1,392.0	-	-	-
Duration	-	-	-	2.0	-	3.0	-	-	-
GSOC	Start	583.0	679.0	782.1	1,192.0	X	1,392.0	-	-	-
End	592.0	680.0	784.6	1,202.0	X	1,396.0	-	-	-
Duration	9.0	1.0	2.5	10.0	-	4.0	-	-	-

Reference

S-W. Baek , K-R. Cho , D-W. Lee , H-D. Kim (2010) A Comparison of Scheduling Optimization Algorithm for the Efficient Satellite Mission Scheduling Operation., Journal of The Korean Society for Aeronautical and Space Sciences, Vol.38 (3) ; pp.48-57
S-W. Baek , S.M. Han , K.R. Cho , D.W. Lee , J.S. Yang , P.M. Bainum , H.D. Kim (2011) Development of a scheduling algorithm and GUI for autonomous satellite missions., Acta Astronaut., Vol.68 (7) ; pp.1396-1402
H. Bahn (2016) Efficient Scheduling of Sensor-based Elevator Systems in Smart Buildings., Journal of the Korea Academia-Industrial cooperation Society, Vol.17 (10) ; pp.367-372
J.Y. Choi (2015) Two-Agent Single-Machine Scheduling with Linear Job-Dependent Position-Based Learning Effects., Journal of Society of Korea Industrial and Systems Engineering, Vol.38 (3) ; pp.169-180
G. Corrao , R. Falone , E. Gambi , S. Spinsante (2012) Ground station activity planning through a multi-algorithm optimisation approach., Satellite Telecommunications (ESTEL), 2012 IEEE First AESS European Conference on,
Q. Dishan , H. Chuan , L. Jin , M. Manhao (2013) A Dynamic Scheduling Method of Earth-Observing Satellites by Employing Rolling Horizon Strategy., Sci. World J., ; pp.1-11
S. Han , S. Baek , S. Jo , K. Cho , D. Lee , H. Kim (2008) Optimization of the Satellite Mission Scheduling Using Genetic Algorithms., The Korean Society For Aeronautical And Space Sciences,
KARI(Korea Aerospace Research Institute) https://www.kari.re.kr/kor/sub07_02_03_14.do
H-B. Kim , H-S. Kim (2016) Optimal Satellite Constellation Design for Korean Navigation Satellite System., Journal of Society of Korea Industrial and Systems Engineering, Vol.39 (3) ; pp.1-9
J.W. Kim (2016) A Study on Deterministic Utilization of Facilities for Allocation in the Semiconductor Manufacturing., Journal of Society of Korea Industrial and Systems Engineering, Vol.39 (1) ; pp.153-161
C.H. Lee , K.M. Cheung (2012) Mixed integer programming & heuristic scheduling for space communication networks, Aerospace Conference, IEEE, ; pp.1-10
J. Lee , H. Kim , H. Chung , K. Ko (2016) Genetic algorithm- based scheduling for ground support of multiple satellites and antennae considering operation modes., International Journal of Aeronautical and Space Sciences, Vol.17 (1) ; pp.89-100
J. Lee , S. Wang , D. Chung , C. Hyun , S. Choi , K. Ko , H. Ahn , O. Jung (2013) Visibility conflict resolution for multiple antennae and multi-satellites via genetic algorithm., in Aerospace Conference, 2013 IEEE,
Y. Lee , K. Lee , I. Seo , S-S. Ko (2016) Efficient Satellite Mission Scheduling Problem Using Particle Swarm Optimization., Journal of Society of Korea Industrial and Systems Engineering, Vol.39 (1) ; pp.56-63
H.J. Li , Y. Lu , F.H. Dong , R. Liu (2012) Communications satellite multi-satellite multi-task scheduling., Procedia Eng., Vol.29 ; pp.3143-3148
K. Luo , H. Wang , Y. Li , Q. Li (2017) High-performance technique for satellite range scheduling., Comput. Oper. Res., Vol.85 ; pp.12-21
S. Spangelo , J. Cutler , K. Gilson , A. Cohn (2015) Optimization- based scheduling for the single-satellite, multiground station communication problem., Comput. Oper. Res., Vol.57 ; pp.1-16
J. Sun , F. Xhafa (2011) A genetic algorithm for ground station scheduling., in Complex, Intelligent and Software Intensive Systems (CISIS), 2011 International Conference on,
P. Wang , G. Reinelt , P. Gao , Y. Tan (2011) A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation., Comput. Ind. Eng., Vol.61 (2) ; pp.322-335
P. Wang , Y. Tan , G. Reinelt (2009) A Comparison of Heuristic Methods for Scheduling Earth Observing Satellites Fleet., In Information Technology and Computer Science (ITCS) 2009, International Conference on, Vol.2 ; pp.164-167
G. Wu , H. Wang , W. Pedrycz , H. Li , L. Wang (2017) Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy., Comput. Ind. Eng., Vol.113 ; pp.576-588
F. Xhafa , J. Sun , A. Barolli , A. Biberaj , L. Barolli (2012) Genetic algorithms for satellite scheduling problems., Mobile Information Systems, Vol.8 ; pp.351-377
F. Xhafa , J. Sun , A. Barolli , M. Takizawa , K. Uchida (2012) Evaluation of genetic algorithms for single ground station scheduling problem., in Advanced Information Networking and Applications (AINA), 2012 IEEE 26th International Conference on, ; pp.299-306

Satellite	Amount of data(Transfer rate)	Communicable slots
Satellite	Amount of data(Transfer rate)	Class.	#1	#2	#3	#4	#5	#6	#7
ARIRANG-2	1,530Mb (0.250Mbps)	Start	104.59	200.33	299.20	767.68	861.64	961.28	-
ARIRANG-2	1,530Mb (0.250Mbps)	End	113.90	214.24	308.83	776.37	875.58	971.77	-
ARIRANG-3	1,620Mb (0.270Mbps)	Start	230.36	327.06	426.98	893.08	988.50	1,090.08	-
ARIRANG-3	1,620Mb (0.270Mbps)	End	241.81	340.65	433.57	903.94	1,002.41	1,097.32	-
ARIRANG-5	1,580Mb (0.283Mbps)	Start	406.05	499.34	1,194.05	1,288.50	-	-	-
ARIRANG-5	1,580Mb (0.283Mbps)	End	416.16	510.67	1,205.27	1,298.66	-	-	-
STSAT-2C	1,235Mb (0.275Mbps)	Start	1,144.05	1,157.45	1,170.91	1,184.40	1,197.92	1,211.47	1,225.00
STSAT-2C	1,235Mb (0.275Mbps)	End	1,144.55	1,158.16	1,171.71	1,185.23	1,198.71	1,212.14	1,225.50
OSSI-1	905Mb (0.265Mbps)	Start	679.40	779.51	880.67	982.32	1,084.86	-	-
OSSI-1	905Mb (0.265Mbps)	End	689.30	791.53	893.08	994.08	1,093.78	-	-

Satellite	S. Korea		Germany		U.S.A.
Parameter	ARIRANG-3	STSAT-3	RAPIDEYE-5	COMPASS-1	SWAS
Amount of data	1,830Mb	1,860Mb	1,850Mb	1,860Mb	1,860Mb
Transfer rate	0.270Mbps	0.250Mbps	0.260Mbps	0.280Mbps	0.295Mbps