# Satellite Communication Resources Management in a Earth Observation Federation of Constellations

Hénoïk Willot, Jean-Loup Farges, Gauthier Picard, Philippe Pavero

► To cite this version:

Hénoïk Willot, Jean-Loup Farges, Gauthier Picard, Philippe Pavero. Satellite Communication Resources Management in a Earth Observation Federation of Constellations. International Conference on the Integration of Constraint Programming, Artificial Intelligence and Operations Research (CPAIOR-25), Nov 2025, Melbourne (AUS), France. pp.235–251. hal-04972791

HAL Id: hal-04972791

https://hal.science/hal-04972791v1

Submitted on 1 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Satellite Communication Resources Management in a
Earth Observation Federation of Constellations

Henoïk Willot¹[0009-0002-2233-9665], Jean-Loup Farges¹[0000-0002-0737-0640],
Gauthier Picard¹[0000-0002-9888-9906], and Philippe Pavero²[0009-0007-9354-9770]

¹ DTIS, ONERA, Université de Toulouse, France

{henoik.willot,jean-loup.farges,gauthier.picard}@onera.fr

² Airbus Defence and Space, Toulouse, France

philippe.pavero@airbus.com

**Abstract.** This paper addresses a new problem arising from the novel concept of multi-mission federation in Earth observation. This problem arises because of the development of several competing ground station networks that could be used by a component of federated missions called Satellite Communication and Resource Management System (SCRMS). Among the functions of SCRMS selection of contacts is a challenging decision problem. It is an optimization problem with Boolean variables corresponding to the selection of some contacts among potential contacts. Constraints enforce the fulfillment of the communication needs of the satellites. The considered criteria are the communication cost and the conflicts and jamming between satellites when communicating with sites, optimized lexicographically. We propose a linear program, several incomplete search schemes and greedy allocation schemes to address this problem, and evaluate them on realistic systems. Results indicate that the linear program complies with computation time requirements and produces better contact selection plans than other optimization schemes.

**Keywords:** Earth observation · communication resources · GSaaS · Integer Linear Programming · Incomplete Search

# 1 Introduction

Traditionally space missions devoted to Earth Observation (EO) have their own resources. Each mission has its constellation of satellites, its ground stations and its control center. Ground stations are devoted to communication with satellites and allow to upload observation plans and download observations. More recently, third-party communication stations using the Ground Station as a Service (GSaaS) paradigm were developed [3,10]. In this paradigm customers book communication resources from a ground segment provider instead of building their own stations. This provider enables them to communicate, download, and process data from their satellites, on a pay-as-you-go basis. Customers of GSaaS are mainly operators of Low Earth Orbit (LEO) satellites owning or not owning ground stations. The main objective of operators owning their own stations and using GSaaS is to communicate more frequently with their satellites.

A multi-agent federation layer to coordinate systems composed of independent Earth observation missions has been proposed [7]. The goal of this federation is to allow clients
requesting acquisitions of large areas to easily access several constellations of satellites and communication sites to compose and download their acquisitions, in a reduced time compared to conventional uncoordinated requests. A Satellite Communication and Resource Management System (SCRMS) has been identified as a key agent of the federation layer. SCRMS shall manage communication using not only ground stations owned by missions of the federation but also GSaaS. SCRMS was functionally decomposed and a first mathematical model of the problem to be solved by one of its functions has been proposed.

The work presented here is devoted to the development and the experimental assessment of algorithms for solving this allocation problem. Its main contribution is the provision of well grounded guidelines for algorithm selection for the communication site booking function.

Sections 2 overviews the concept of SCRMS developed in the DOMINO-E project [6]. Section 3 briefly discusses the related works. Section 4 expounds the definitions and the decision model related to communication booking. Then, the algorithms proposed for solving the decision problem are detailed in Section 5. Section 6 is devoted to the presentation and analysis of experimental results and finally this article finishes with concluding remarks.

# 2 Satellite Communication Resource Management

## 2.1 Interactions with other agents

SCRMS is in charge of providing opportunities for communicating with ground to all satellites of all federated missions. It manages communication between *N* satellites, seeking for communication windows for uplink and downlink data transfer, and sites including one or several ground stations. Each ground station controls a specific antenna. Missions provide orbits of their satellites and ground station networks publish coordinates and visibility masks of their stations. When the use of GSaaS is necessary, SCRMS interacts with external station networks in order to book communication resources.

## 2.2 Functional decomposition

Because SCRMS needs to be aware of all communication opportunities, to choose the best communication opportunities and to actually book resources necessary for the chosen communication opportunities, it is decomposed in three functions:

- computation of potential contacts,

- selection of contacts and

- booking of selected contacts.

**Computation of potential contacts** Propagating orbits and computing the events with respect to sites coordinates and visibility masks leads for each satellite *i* to $L_i$ potential contacts with the ground. Each contact $l \in \{1, \dots, L_i\}$ is characterized by:

- $s_{i,l}$ its site on ground and

- $[\underline{u}_{i,l}, \bar{u}_{i,l}]$ its time window.
**Selection of contacts** The satellite *i* may not need all its $L_i$ available contacts to ensure uploading of observation plans and downloading of observations. This is a decision problem that is described in Section 4.

**Booking of selected contacts** For owned stations the selected contacts can be used directly, but for GSaaS the protocol of the station provider shall be respected. It includes opening delay for booking and the possibility of a rejection of the booking of a contact. Rejected booking shall be recorded for future calls to the selection of contacts function.

## 3 Related Works

The problem consisting in scheduling downloads from satellites of a constellation to a dedicated ground station network is well covered by the literature. For instance, [5] optimize by evolutionary computation the scheduling model for an observation data topic whose value of observation data decay shortly if the topic is not complete at specified time. Another example is the use of a greedy scheduling algorithm for maximizing the total amount of data downloaded to Earth [4]. On the ground station side, research is also active. Indeed, Monte Carlo simulation allows the assessment of a single ground station saturation in terms of data downlink requirements and increasing number of conflicting passes with the growth of the number of satellites [14]. An automated tool, based on Integer Linear Programming, solves the problem of deconflicting requests for multi-site ground networks serving numerous satellite operators [13]. Scheduling for ground station with equal distribution of redundant contact between requests, associated with data synchronization of satellite downlinks and transmission error recovery, improves ground station network performance, cf. [12].

However, the problem of optimizing communication needs of several constellations using several ground station networks with different access conditions is a new problem resulting from the development of several competing ground station networks such as AWS, see [1], and KSAT, see [8]. Thus the scope of this paper is the development of mathematical problems expressing constraints and criteria related to communication booking.

## 4 Decision Problem Modeling

This section provides the definitions and the decision problem model related to communication booking in SCRMS.

### 4.1 Definitions

**Definition 1 (Need).** A need is a needed contact duration associated to a satellite, a site list and a time window. The $k$th need of satellite *i* is characterized by:

- a communication duration $D_{i,k}$,

- a time window $[\underline{t}_{i,k}, \bar{t}_{i,k}]$,
- a site list $S_{i,k}$, and

- a radio communication band.

The satellite i has $K_i$ needs.

**Definition 2 (Need associated to a contact).** A need is associated to a contact if this contact is able to contribute to fulfilling the needed contact duration. The lth contact of satellite i is associated to the kth need of satellite i if and only if:

- $s_{i,l} \in S_{i,k}$, and

- $\underline{u}_{i,l} \ge t_{i,k}$,

- $\bar{u}_{i,l} \le \bar{t}_{i,k}$, and

- the need radio communication band is included in the set of radio communication bands provided by the site $s_{i,l}$.

Using those definitions, it is possible to determine, for each contact $l$ of satellite $i$, the set of needs it is able to fulfill. This set is denoted $\mathcal{Z}_{i,l}$.

## 4.2 Variables

The proposed model doesn't consider partial use of contacts by satellites. In consequence, decision variables are $x_{i,l} \in \{0, 1\}$ for $i \in \{1, \dots, N\}$ and $l \in \{1, \dots, L_i\}$. $x_{i,l}$ corresponds to the selection of contact $l$ by satellite $i$. The set of all $x_{i,l}$ is noted as $\mathbf{x}$.

## 4.3 Constraints

Each need of each satellite shall be satisfied, leading to the constraints for $i \in \{1, \dots, N\}$ and $k \in \{1, \dots, K_i\}$:

$$ \sum_{l \in \{1, \dots, L_i\} / k \in \mathcal{Z}_{i,l}} d_{i,l} x_{i,l} \ge D_{i,k} \quad (1) $$

where $d_{i,l}$ is the duration of a contact $l$ of satellite $i$. It is given by $\bar{u}_{i,l} - \underline{u}_{i,l}$.

## 4.4 Criteria

If the problem is feasible, setting all $x_{i,l}$ variables to one would respect Equation 1. However, there is a financial cost associated to contact selection and selecting some contacts together induces a risk of not being able to actually use them because of conflict or mutual jamming. For is reason two criteria are relevant for selecting contacts:

1. the total booking cost for the federation and

2. the total level of conflict and jamming suffered by the federation.
**Total cost** With respect to cost, the federation may use the sites owned by its missions at no cost or the sites of ground station networks with a cost depending on their billing method. The cost C is given by:

$$C = \sum_{i=1}^{N} \sum_{l=1}^{L_i} c_{i,l} x_{i,l} \qquad (2)$$

where

$$c_{i,l} = c_{i,l}^{0} + e_{i,l} d_{i,l} \qquad (3)$$

The cost value associated to contact *l* of satellite *i* depends on the billing method of the provider of this contact. If this provider is payed per contact $c_{i,l}^0$ is the cost per contact for the provider of the site involved in the contact *l* of satellite *i*. If it is payed per minute of contact, in the term $e_{i,l}d_{i,l}$, $e_{i,l}$ is the cost per unit of time for the provider of the site involved in the contact *l* of satellite *i*.

**Conflict and Jamming** Conflict and jamming may occur when two contacts of two different satellites have overlapping time windows and the same site. It can be written as:

$$J = \sum_{i=1}^{N-1} \sum_{l=1}^{L_i} (f_{i,l} x_{i,l} + \sum_{j=i+1}^{N} \sum_{m=1}^{L_j} b_{i,l,j,m} x_{i,l} x_{j,m}) \qquad (4)$$

where $f_{i,l}$ characterizes the conflict and jamming between contact *l* of satellite *i* and satellites not belonging to the federation. It is only relevant for contacts related to not owned sites and its value shall be estimated by learning on the long term a model of the site. $b_{i,l,j,m}$ characterizes the conflict and jamming between contact *l* of satellite *i* and contact *m* of satellite *j*. If contact *l* of satellite *i* does not overlap with contact *m* of satellite *j* or if those contacts are not related to the same site, i.e. $s_{i,l} \neq s_{j,m}$, or if their respective communication bands differ, $b_{i,l,j,m} = 0$. Otherwise, the value of $b_{i,l,j,m}$ depends on site characteristics.

If the site has a single ground station, it is a conflict and the strength of the conflict is characterized by the ratio between intersection and union of time intervals:

$$b_{i,l,j,m} = \frac{\min\{\bar{u}_{i,l}, \bar{u}_{j,m}\} - \max\{\underline{u}_{i,l}, \underline{u}_{j,m}\}}{\max\{\bar{u}_{i,l}, \bar{u}_{j,m}\} - \min\{\underline{u}_{i,l}, \underline{u}_{j,m}\}} \qquad (5)$$

If the site has multiple antennas, jamming may occur at time $\sigma$ in the overlapping period $[\max\{\underline{u}_{i,l}, \underline{u}_{j,m}\}, \min\{\bar{u}_{i,l}, \bar{u}_{j,m}\}]$, such that $\alpha_{i,l,j,m}(\sigma) \le \alpha$ where $\alpha_{i,l,j,m}(\sigma)$ is the angle between satellites *i* and *j*, seen from the site, during their contacts *l* and *m* respectively, and $\alpha$ is a critical value for angles between satellites seen from a site. We have:

$$\cos \alpha_{i,l,j,m}(\sigma) = Q_{i,l}(\sigma) \cdot Q_{j,m}(\sigma) \qquad (6)$$

where $Q_{i,l}(\sigma)$ is the unit vector pointing from the antenna site $s_{i,l}$ to the satellite *i*. It is given by:

$$Q_{i,l}(\sigma) = \frac{P_{i,l}(\sigma) - P'_{s_{i,l}}(\sigma)}{\|P_{i,l}(\sigma) - P'_{s_{i,l}}(\sigma)\|} \qquad (7)$$
were $P_{i,l}(\sigma)$ and $P'_{s_{i,l}}(\sigma)$ are respectively, in a common frame, the position of satellite $i$ at time $\sigma$ and the position of station $s_{i,l}$. In that case, $b_{i,l,j,m}$ can be computed as the ratio of, on the one hand, the duration of $\alpha_{i,l,j,m}(\sigma) \le \alpha$ holding in the intersection of the two contacts to, on the other hand, the duration of the union of the two contacts. The positions during the intersection of the two contacts shall be obtained from orbit description of the two satellites. If the common frame is not rotating with the Earth, the position of the station shall be obtained considering Earth rotation.

**Lexicographic order** Because $C$ and $J$ haven't a common measure, it is difficult to weight them in an aggregated criterion. Risky federation managers would prefer to minimize $C$ first while cautious federation managers would try to minimize $J$ first. For this reason criteria shall be considered in a lexicographic order and two strategies shall be considered: either $C$ is optimized first and $J$ is optimized restricting the solutions to those providing the optimal $C$ value or $J$ is optimized first and $C$ is optimized restricting the solutions to those providing the optimal $J$ value. The strategies optimizing $C$ first and $J$ first are named MINI and SECURE respectively.

# 5 Algorithms

For solving the communication booking decision problem, i.e. finding an admissible assignment of true or false to each variable in $x$, we propose four types of algorithms: (1) Round-robin algorithms, (2) greedy algorithms, (3) search algorithms and (4) Integer Linear Programming (ILP) algorithms. We present each algorithm in the following sub-sections.

## 5.1 Round-robin

The round-robin procedure is a system to consider fair distribution of items among agents [2]. The round-robin allocation scheme proposed here associates needs to agents and contacts to items. Thus, each need is considered in turn and selects an additional contact as to optimize its valuation. The order to consider the needs either depends on the needs' valuation (the need with the best valuation chosen first), or depends on the hardness of the need (the hardest need chosen first). This results in two round-robin allocation schemes: **valuation-guided round-robin** (coined v_RR) and **hardness-guided round-robin** (coined h_RR). Needs' valuation and hardness are defined as follows. For the valuation of need $k$ of satellite $i$ all contacts that can contribute to the need $k$ and are not selected, i.e. $l \in \{1, \dots, L_i\}/k \in Z_{i,l} \wedge x_{i,l} = 0$, are examined for a possible selection, i.e. $1 \to x_{i,l}$ and resulting values of criteria $J$ and $C$ are computed. The valuation of the need is the best couple of criteria considering the lexicographic order. The need's hardness is computed by:

$$ \frac{D_{i,k}}{1 + \sum_{l \in \{1, \dots, L_i\} / k \in Z_{i,l}} d_{i,l} (1 - x_{i,l})} \qquad (8) $$

Note that when no contact is selected for a need its hardness is the smallest value possible, i.e. almost the ratio between the needed duration and the total potential contact duration associated to the need, and that selecting contacts increases its hardness.
## 5.2 Greedy procedures

A greedy allocation scheme consists in allocating some contacts by making the choice that seems best at the moment, without revising this decision afterwards. It is a very fast (polynomial) method, but it might result in sub-optimal allocations. Here, two ways of making allocation choices are proposed: either the main focus is the need or the main focus is the contact. In the first way needs are recursively selected for full fulfillment while in the second way contacts are recursively selected.

For the first way, we defined two greedy allocation algorithms: a **need valuation-guided greedy** (coined $v_G$), that first fulfills the best need wrt. its valuation (cost then jamming, or jamming then cost, depending on the strategy), and a **need hardness-guided greedy** (coined $h_G$), that first fulfills the need that is the hardest to fulfill: the one with the smallest margin of freedom, cf. Equation (8).

The second way leads to **contact valuation-guided greedy** ($c_G$). Very similar to $v_G$, instead of looping over needs and selecting the best need at each step, it loops over all the non booked contacts, and select the best one. It repeats until all the contacts have been considered or all the needs are fulfilled.

## 5.3 Local searches

Round-robin and greedy procedures are constructive heuristics: they produce partial solution at each step until reaching admissibility. At the opposite local searches work on complete solutions trying to improve criteria while maintaining admissibility. Those methods need an initial solution and the definition of the neighborhood of a solution, i.e. the set of solutions that are defined as reachable from a given solution.

Concerning the initial solution, several possibilities can be considered, such as :

1. setting all $x_{i,l}$ to 1,

2. for each $i$ setting $x_{i,l}$ to 1 by increasing $l$ index order until all Equations (1) related to $i$ and $k \in \{1, ..., K_i\}$ are satisfied,

3. for each $i$ setting $x_{i,l}$ to 1 by increasing $c_{i,l}$ order until all Equations (1) related to $i$ and $k \in \{1, ..., K_i\}$ are satisfied or

4. using any constructive heuristic.

Results of initial tests conduct to choose the third option when the strategy is MINI and the fourth option with $v_G$ when the strategy is SECURE. Those choices are driven by a trade-off between computation time to find the initial solution and quality of the initial solution.

Concerning the definition of the neighborhood two options have been investigated here:

- a small neighborhood consisting of flipping any one of the $x_{i,l}$ variables forbidding $1 \to 0$ flips that violate Equation (1) and

- a large neighborhood consisting in making a given number of $1 \to 0$ flips and reconstructing admissibility.
For the small neighborhood we defined two search schemes: **best first search** (coined BFS) and **depth first search** (coined DFS). Both use the development of the neighborhood of a solution: from a solution all new solutions in the neighborhood are evaluated. In BFS, the process selects first the solution with the best valuation among all the solutions that are already evaluated but not already developed. In DFS, the process selects the best neighboring solution of the current solution. Note that BFS is local w.r.t. all already evaluated solutions while DFS is local w.r.t. the current solution.

Large Neighborhood Search (LNS) is a metaheuristic method employed in optimization problems, particularly those involving combinatorial optimization [11]. It is an advanced version of the simpler neighborhood search technique. For the large neighborhood the algorithm mainly alternates between *destroy*, *repair* and *accept* operations to find better solutions. The definition of those operations leads to **large neighborhood search** (coined LNS):

- *destroy* unset randomly a proportion of positive values in x. In other word, it cancels some contacts.

- *repair* set variables for each unfulfilled need using h_G principle.

- *accept* only filter improving solutions.

This metaheuristic requires several meta-parameters to be set:

- The maximum number of iterations,

- The ratio of contact assignments destroyed at each iteration and

- The maximum number of iterations without improvement before stopping.

## 5.4 Integer Linear Programming

ILP solvers are general purpose software that are able to solve optimization problems with a linear criterion and linear constraints. Examples of such software are IBM CPLEX 3 [9] and Google OR-Tools 4 . The problem described by Equations (1), (2) and (4) is almost linear. Indeed, only Equation (4) is not linear. The general idea for using a ILP approach is to linearize this equation.

**Linearization of the conflict and jamming criterion** In order to linearize the conflict and jamming criterion, a new variable is introduced for each couple of contacts, contact *l* of satellite *i* and contact *m* of satellite *j*, that presents a non null $b_{i,l,j,m}$ parameter:

- $\forall i \in \{1, \dots, N-1\}, \forall l \in \{1, \dots, L_i\}, \forall j \in \{i+1, \dots, N\}, \forall m \in \{1, \dots, L_j\}$ such that $b_{i,l,j,m} > 0$, the variable is $y_{i,l,j,m} \in \{0, 1\}$.

This new variable stands for the product $x_{i,l}x_{j,m}$. The set of all those new decision variables is noted y. Those new variables allow a rewriting of the conflict and jamming criterion in a linear form:

$$J = \sum_{i=1}^{N-1} \sum_{l=1}^{L_i} (f_{i,l}x_{i,l} + \sum_{j=i+1}^{N} \sum_{m \in \{1 \dots L_j\}: b_{i,l,j,m} > 0} b_{i,l,j,m}y_{i,l,j,m}) \quad (9)$$

<footnote n="3">3 https://www.ibm.com/products/ilog-cplex-optimization-studio</footnote>

<footnote n="4">4 https://developers.google.com/optimization</footnote>
However $y_{i,l,j,m}$ shall stick to $x_{i,l}x_{j,m}$ on $\{0, 1\} \times \{0, 1\}$. In order to have this property the following constraints are introduced:

$$ \forall i \in \{1, \dots, N-1\}, \forall l \in \{1, \dots, L_i\}, \forall j \in \{i+1, \dots, N\}, \forall m \in \{1, \dots, L_j\}: b_{i,l,j,m} > 0 $$

$$ y_{i,l,j,m} \le x_{i,l} \qquad (10) $$

$$ y_{i,l,j,m} \le x_{j,m} \qquad (11) $$

$$ y_{i,l,j,m} \ge x_{i,l} + x_{j,m} - 1 \qquad (12) $$

Equation (10) and Equation (11) ensure that if $x_{i,l}$ or $x_{j,m}$ is null $y_{i,l,j,m}$ is also null. In those three cases Equation (12) is verified. Equation (12) ensures that in the fourth case, i.e. if $x_{i,l} = x_{j,m} = 1$, $y_{i,l,j,m} = 1$. In this case Equation (10) and Equation (11) are verified. Finally, note that because the MILP solver is minimizing and $b_{i,l,j,m}$ are positive, reciprocal constraints corresponding to Equations (10) and (11) are not absolutely necessary.

**Problem provided to the solver** In consequence, the problem provided to the ILP solver has the following characteristics:

- Variables: x and y

- Constraints: Equations (1), (10), (11) and (12).

- Criteria: Equations (2) and (9)

Note that it is a bi-criteria ILP problem. CPLEX solves bi-criteria problems while Google OR-Tools is not able to directly handle lexicographic bi-objective optimization. For Google OR-Tools we implemented the lexicographic bi-objective optimization by procedurally chaining two mono-objective optimization processes, whose order depends on the booking strategy. The value of the first criterion found at the end of the first optimization is used as a constraint for the optimization of the second criterion. We made preliminary experiments with both solvers, but **only retain Google OR-Tools**, because solution quality was identical to IBM CPLEX's one, and execution time was in the same order of magnitude, while being an open source software. In the following this Google OR-Tools based solver is coined ILP.

# 6 Experimental Evaluation

## 6.1 Scenarios

Sixty different scenarios, corresponding to sixty consecutive days, are defined for the assessment of algorithms. Those scenarios differ with respect to the communication needs of the satellites and constellations and with respect to positions of satellites on their orbits. Each day, a contact selection plan is computed for the next ten days. This computation is performed by applying ten times the considered algorithm changing the initial position of satellites. The sums of criteria over the days are provided as indicators for the considered scenario. The timeout is applied to each day of a scenario. In our case, we set 30s per day-related subproblem, which means 5 min per scenario.

We developed all the proposed algorithms in Java (SDK 1.8). Experiments have been run on a 20-core Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz, 62GB RAM, Ubuntu 18.04.5 LTS.
**Constellations** There are four constellations in the configuration. The first three constellations are handled by the system, while the last one contains the external satellites that can produce unforeseen jammings. The three internal constellations are configured as followed :

- PNEO : Two S950 satellites on the same SSO orbit, in phase opposition,

- SSO : Four S250 satellites on the same SSO orbit, in quadrant phases,

- Inclined : Two pairs of S250 satellites in phase opposition, each pair on an 40° inclined orbit. The orbits have a 180° RAAN difference.

Figure 1 shows sample ephemerides of each constellation.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Sample ephemerides for some satellites used in the scenarios</figcaption></figure>

**Station providers** There are four providers considered in the configuration:

- **Owned**: contains the stations that are owned by the system. Its cost is considered free.

- **Preferred**: this simulates a provider with optimized cost and location.

- **Normal**: this simulates a bonus provider with basic contract.

- **Expensive**: this simulates a premium provider that should be used only in emergency.

The stations are created with a 5° mask, and are positioned as illustrated in Figure 2.

**Needs** Needs consists of communication requirements to be fulfilled at each period of time (every 24h for Band X and every 6h for Band S). Needs are expressed in terms of minimum communication duration for each band, for each satellite and/or constellation. Initial needs are given in Table 1. Then, all along the 60-days period, the needs evolve as illustrated in Figure 3, as to simulate growing or decreasing needs depending on the period of the two months.

**6.2 Results**

Figure 4 presents the average values of cost, jamming and conflict, and computation time for the two strategies and the nine algorithms.
<figure><img src="image_3.png" /><figcaption>Fig. 2: Stations and their respective visibility circles at 500km altitude: violet is Owned, green is Preferred, yellow is normal, red is Expensive.</figcaption></figure>

<table><caption>Table 1: Initial routine needs</caption><thead><tr><th>constellation</th><th>satellite</th><th>band duration (per period in min)</th></tr></thead><tbody><tr><td>PNEO_S950</td><td></td><td>S 5</td></tr><tr><td>PNEO_S950</td><td></td><td>X 50</td></tr><tr><td>SSO_S250</td><td></td><td>S 5</td></tr><tr><td>SSO_S250</td><td></td><td>X 70</td></tr><tr><td>SSO_S250</td><td>SSO_S250_1</td><td>X 60</td></tr><tr><td>Inclined_S250</td><td></td><td>S 5</td></tr><tr><td>Inclined_S250</td><td></td><td>X 50</td></tr><tr><td>Inclined_S250</td><td>Inclined_S250_1</td><td>X 50</td></tr></tbody></table>

**Cost** All methods applying a MINI strategy which aims at minimizing costs present a lower cost than any method applying a SECURE strategy, indicating that the priority given to the cost by the MINI strategy is always efficient. Moreover, all the solution methods converge to solutions with a cost around 23000, when following a MINI strategy. When aiming to minimize the jamming and conflicts (SECURE strategy) the search methods reach solutions around 35000, but there is a large difference between the best method ILP, with an average cost around 28000, and the worst methods c_G, with an average cost around 48000, and h_G, with an average cost around 40000. However, in SECURE strategy costs shall be compared only for equivalent value of jamming and conflict.

**Conflicts and jamming** All methods applying a SECURE strategy present a lower conflict and jamming than any method applying a MINI strategy, indicating that the priority given to conflict and jamming by the SECURE strategy is always efficient. For conflicts and jamming the same discrepancies arise when following a MINI strategy: ILP and search-based solvers find quasi optimal solutions around 80, while other solvers
<figure><img src="image_4.png" /><figcaption>Fig. 3: Band X needs evolution over time</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4: Pareto analysis of the main performance metrics, cost and jamming.</figcaption></figure>

struggle with values between 82 and 105. The good news is that, when following a SECURE strategy, all the algorithms manage to find almost jamming free allocations. This is due to the fact that there are numerous contacts, and it is easy to find configuration without jamming. But let's note that we consider here only jamming with owned constellations. In real contexts, it is highly probable that external constellations generate extra jamming. To assess this we need a model of the other constellations and of the service acceptance behavior.
<figure><img src="image_6.png" /><figcaption>Fig. 5: Solution cost all along the successive scenarios for all the solvers</figcaption></figure>

**Algorithm performance w.r.t. the strategy** Figure 5 illustrates on the cost indicator that the workload generates a wide variance, that impacts all the algorithms in the same way. For this reason, significance of differences between algorithms is computed by first computing the difference each day and then checking the resulting variable for significant mean value. Table 2 presents such computations while using the SECURE strategy. With this kind of analysis, it is possible to compare algorithm performance w.r.t. the requirement derived from the strategy. For comparisons of algorithms while using the MINI strategy the most important criterion is the cost and the less important criterion is the jamming. It is possible to note that ILP is always better than other algorithms. Both BFS and DFS are slightly equivalent but significantly better than LNS. LNS is better than greedy algorithms. There is no significant difference between hardness guided greedy and valuation guided greedy and both are better than contact greedy which is better than hardness guided Round-Robin, which in turn is better than
value guided Round-Robin, but those differences are due to the less important criterion. When comparing the algorithms for the SECURE strategy the most important criterion is the jamming and the less important criterion is the cost. As indicated by Table 2, at a 95% level the ranking is partly driven by the most important criterion, i.e. the jamming. In that case it is possible to note that ILP is always better than other algorithms. For LNS, BFS, DFS, h_G and c_G, there is no difference on the most important criterion, i.e. the jamming. Then the order LNS > BFS > DFS > h_G > c_G is driven by significant differences in the less important criterion, i.e. the cost. LNS, BFS, DFS, h_G and c_G are better than v_G and Round-Robin algorithms (h_RR and v_RR) on the basis of a significant difference on the most important criterion. v_G is better than h_RR on the basis of a significant difference on the less important criterion and better than v_RR on the basis of a significant difference on the most important criterion. h_RR is better than v_RR because of a significant difference on the most important criterion. In conclusion, it is worth noting that of course the ILP is the best option since it performs better on both MINI and SECURE strategies. However, the local search and LNS are very close.

<table><caption>Table 2: Average degradation of criteria w.r.t. reference algorithms (left column) when using algorithms in SECURE strategy; in a cell on first line jamming degradation and on the second line cost degradation: * and ** indicate respectively 95% and 99.7% statistical significance on a test with data twined per day</caption><thead><tr><th>Other Reference</th><th>LNS</th><th>BFS</th><th>DFS</th><th>h_G</th><th>c_G</th><th>v_G</th><th>h_RR</th><th>v_RR</th></tr></thead><tbody><tr><td>ILP</td><td>0.02*<br>6104**</td><td>0.02*<br>8363**</td><td>0.02*<br>8477**</td><td>0.02*<br>11254**</td><td>0.02*<br>18924**</td><td>0.96*<br>3284**</td><td>1.01*<br>4354**</td><td>1.68*<br>5691**</td></tr><tr><td>LNS</td><td>0<br>2259**</td><td>0<br>2373**</td><td>0<br>5150**</td><td>0<br>12820**</td><td>0<br>-2821**</td><td>0.94*<br>-1751*</td><td>0.99*<br>-1.41</td><td>1.67*<br>-413</td></tr><tr><td>BFS</td><td>0<br>114**</td><td>0<br>2891**</td><td>0<br>10561**</td><td>0<br>-5080**</td><td>0<br>-4009**</td><td>0.94*<br>-2672*</td><td>0.99*<br>-4009**</td><td>1.67*<br>-2672*</td></tr><tr><td>DFS</td><td>0<br>2777**</td><td>0<br>10447**</td><td>0<br>-5194**</td><td>0<br>-4123**</td><td>0.94*<br>-2786*</td><td>0.99*<br>-4123**</td><td>0.99*<br>-2786*</td><td>1.67*<br>-2786*</td></tr><tr><td>h_G</td><td>0<br>7670**</td><td>0<br>-7970**</td><td>0<br>-6900**</td><td>0<br>-6900**</td><td>0<br>-5563**</td><td>0.94*<br>-15641**</td><td>0.99*<br>-14570**</td><td>1.67*<br>-13233**</td></tr><tr><td>c_G</td><td>0<br>7670**</td><td>0<br>-7970**</td><td>0<br>-6900**</td><td>0<br>-6900**</td><td>0<br>-5563**</td><td>0.94*<br>-15641**</td><td>0.99*<br>-14570**</td><td>1.67*<br>-13233**</td></tr><tr><td>v_G</td><td>0<br>1070**</td><td>0<br>2407**</td><td>0<br>2407**</td><td>0<br>2407**</td><td>0<br>2407**</td><td>0.94*<br>-15641**</td><td>0.99*<br>-14570**</td><td>1.67*<br>-13233**</td></tr><tr><td>h_RR</td><td>0<br>1337**</td><td>0<br>2407**</td><td>0<br>2407**</td><td>0<br>2407**</td><td>0<br>2407**</td><td>0.94*<br>-15641**</td><td>0.99*<br>-14570**</td><td>1.67*<br>-13233**</td></tr></tbody></table>

**Computation time** We observed that search algorithms requires 5min (the fixed time-out) while greedy and round-robin may only require few seconds each scenario day. Interestingly, the ILP does not need to reach to time out to prove the optimality of the solutions. That makes us think this is a very promising option here. Compromises between
cost (resp. jamming) and computation time confirm this tendency: for the SECURE
strategy, all the greedy algorithms being able to reach jamming-free allocations, h_G
and c_G, are good candidates, but they struggle to find low cost allocations. However,
time might not be a strong constraint since these algorithms should be executed only a
few times a day depending on the availability of the services. Looking at the variability
due to the workload, it is interesting to note that ILP sometimes solves the problems
very fast (as fast as greedy and round-robin solvers). This is due to some configurations
that are very easy to solve, even optimally.

7 Conclusions

The result of this research is the design, development and assessment of nine algorithms for the communication resource management in EO federation of constellations. The algorithms we developed mostly provide good solutions, when following a strategy aiming at minimizing costs. However, when it comes to minimize the jamming first, while minimizing costs, the best algorithms (search-based, and ILP) requires more computation time (still less than 5 min). Yet, this computation time is very reasonable, since such procedures should only be called few times each day.

One limitation of the assessment presented here is that it is done in open loop: accep-
tance ot rejection of selected contacts by GSaaS is not simulated and the optimization of
the scenario for the next day starts from scratch. Closed loop assessment is a challenge
that will be addressed soon. For this, GSaaS behavior and resolution of conflicts and
jamming with competing constellation shall be simulated. In closed loop settings, the
uniform time constraint sharing among days is questionable. Indeed, the first day of the
optimization horizon is the most critical but also the one that should have the largest
number of contacts already booked. Learning time constraint sharing among day would
be an interesting challenge to address.

Other limitations are related to the model and its link with real life elements. First the
cost as defined by Equation (2) does not cover all the billing possibilities. For instance, it
is possible to imagine communication packages where a given amount is pre-paid at low
cost, thus free of charge when considering real time operation, and excesses with respect
to this amount are paid more expensively. Then, in the test only global communication
needs are associated to satellites. However, when communication is urgent, needs can
be associated to areas of the Earth surface, for instance where a disaster is occurring.
In that case, the need for S and X bands are respectively before and after the satellite is
flying over the area. The Z_{i,l} set is theoretically able to model such a situation, however
the difficulty is to determine which contacts have such needs in their Z_{i,l} set. Indeed,
it requires fine visibility computations depending on the areas of interest. Finally, the
impact of external constellations on the jamming is modeled by f_{i,l} coefficients, but the
value of those coefficients is difficult to set. One track would be to simulate external
constellations and their respective workload, to assess an average jamming value for
each potential contact. A second track would be to build a model of the acceptance
behavior of service providers, as to provide allocations that are robust to the providers'
response. Finally, a third track could try to learn those coefficients using past contact
rejections from the GSaaS and past jamming from external constellations.
References

1. AWS, A.W.S.: Aws ground station (2023), https://aws.amazon.com/ground-station/

2. Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum nash welfare. ACM Trans. Econ. Comput. 7(3) (sep 2019). https://doi.org/10.1145/3355902, https://doi.org/10.1145/3355902

3. Carcaillon, E., Bancquart, B.: Market perspectives of ground segment as a service p. 60462 (10 2020)

4. Castaing, J.: Scheduling downloads for multi-satellite, multi-ground station missions (2014)

5. Chen, H., Zhai, B., Wu, J., Du, C., Li, J.: A satellite observation data transmission scheduling algorithm oriented to data topics. International Journal of Aerospace Engineering 2020, 1–16 (2020)

6. DOMINO-E Consortium: https://domino-e.eu/ (2024)

7. Farges, J.L., Perotto, F.S., Pralet, C., Picard, G., de Lussy, C., Guerra, J., Pavero, P., Planchou, F.: Going beyond mono-mission earth observation: Using the multi-agent paradigm to federate multiple missions. In: 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS-24). pp. 2674–2678. International Foundation for Autonomous Agents and Multiagent Systems (2024)

8. KSAT: Ground network services (2023), https://www.ksat.no/ground-network-services/

9. Manual, C.U.: Ibm ilog cplex optimization studio. Version 12(1987-2018), 1 (1987)

10. Nguyen, L.: Ground stations as a service (gsaas) for near real-time direct broadcast earth science satellite data. Tech. rep., NASA (2012), https://esto.nasa.gov/forums/estf2021/Presentations/June10/Nguyen_GSON_ESTF2021.pdf

11. Pisinger, D., Ropke, S.: Large Neighborhood Search, pp. 99–127. Springer International Publishing. https://doi.org/10.1007/978-3-319-91086-4_4, https://doi.org/10.1007/978-3-319-91086-4_4

12. Schmidt, M.: Ground station networks for efficient operation of distributed small satellite systems. Universität Würzburg (2011)

13. Vazquez, R., Perea, F., Vioque, J.G.: Resolution of an antenna-satellite assignment problem by means of integer linear programming. Aerospace Science and Technology 39, 567–574 (2014)

14. Writt, A.J.: Optimization of CubeSat Ground Stations for Increased Satellite Numbers. Ph.D. thesis, Monterey, CA; Naval Postgraduate School (2018)