Mikaël Capelle
email: mikael.capelle@thalesaleniaspace.com

Marie-José Huguet

Nicolas Jozefowiez

Xavier Olive

Ground stations networks for Free-Space Optical communications: maximizing the data transfer

Keywords: Free-Space Optical Communications, Optical Ground Station Network Optimisation, Dynamic Programming, Mixed-Integer Linear Programming

Free-space optical communications are becoming a mature technology, but unlike current radio-frequency technologies, they are strongly impacted by clouds. In this paper, we aim to find a network of optical ground stations maximizing the amount of data that can be sent from a low-earth orbiting satellite to the Earth during its missions, taking into consideration cloud information. We present a Mixed Integer Linear Program (MILP) and a hierarchical method based on an exhaustive enumeration of the sets of ground stations and on a dynamic programming algorithm and compare them on real scenarios based on archived years of cloud data. Even if the MILP can solve scenarios over small time horizons in less than one hour, experiments show that the hierarchical approach outperforms it in term of CPU time while achieving optimality.

Introduction

Free-Space-Optical (FSO) communications are seen as a key technology [START_REF] Kernec | Space evaluation of optical modulators for microwave photonic on-board applications[END_REF] [8] [START_REF] Roy | Optical feeder links for high throughput satellites[END_REF] to cope with the needs of higher data-rate payloads for future lowearth orbiting (LEO) observation satellites in replacement to the current radiofrequency (RF) technologies. Current RF technologies use X-Band for download which can currently provide up to a few Gbps [START_REF] Eilertsten | Ground station networks vs. geo relay satellites for polar orbiting satellites data download[END_REF]. These are not impacted by weather or atmospheric turbulences. Their main drawbacks are limited data-rates and a need for frequency licensing which will become a major issue in the upcoming years due to increases in the number of operational satellites and constellations. FSO communications offer data-rate order(s) of magnitude higher than current RF technologies: targeted data-rates go from some tens of Gbps to some Tbps. They do not require frequency licensing and are hard to intercept by malicious observers. However, FSO communications are strongly impacted by weather, cloud, and atmospheric turbulences.To evaluate the impact of FSO communications for spatial imagery systems, we aim to find a subset of optical ground stations in order to maximize the percentage of data downloaded from satellites taking cloud information into account using archived data from previous decades.

The optimization of an Optical Ground Stations Network taking into account the influence of clouds was first studied by [START_REF] Link | Mitigating the impact of clouds on optical communications[END_REF] and [START_REF] Wojcik | Deep-space to ground laser communications in a cloudy world[END_REF]. Their objective was to find a network for a deep-space probe in order to reach a given temporal availability using an approximation algorithm with a high-resolution database as input. In [START_REF] Takayama | Estimation of accessible probability in a low earth orbit satellite to ground laser communications[END_REF], a probabilistic approach was used to analyze the availability of ground station networks: one in Japan for a geostationary satellite and one worldwide for a low-earth orbiting satellite (LEO) satellite. In [START_REF] Poulenard | High altitude clouds impacts on the design of optical feeder link and optical ground station network for future broadband satellite services[END_REF] and [START_REF] Poulenard | Ground segment design for broadband geostationary satellite with optical feeder link[END_REF], a greedy algorithm was used to find a network in Europe for a geostationary satellite based on data from the SAF-NWC cloud database and using an hypothetical substrate network.

In 2012, the Optical Link Study Group (OLSG) published a report in which the impact of FSO communications on various space systems (LEO observation satellite, geostationary relay) was evaluated using the Lazercom Network Optimization Tool (LNOT) [START_REF] Link | Mitigating the impact of clouds on optical communications[END_REF].

In Section 2, we will characterize more formally the problem under study and propose a Mixed Integer Linear Program. In Section 3, we will present a hierarchical method based on a dynamic programming algorithm to solve this problem. We will then present our experimental context and the results of our experimentations in Section 4.

Problem statement and MILP modelisation

Problem definition

Considering a LEO satellite and given a set L = {1, . . . , N} for possible locations of ground stations with associated costs w i (i ∈ L), we aim to find a subset L ′ ⊆ L having a cost lower than K that maximize the Percent Data Transferred [START_REF] Ioag) | Optical link study group final report[END_REF] (PDT), i.e. the percentage of data acquired by the satellite that can be successfully send to the ground. This problem is denoted MaxPDT.

Regarding image acquisition, we assume that the time horizon is divided in a set S of successive acquisition slots and that a given amount of data a s is acquired at the beginning of each slot s. The satellite has a buffer of size B ≥ 0 filled with B 0 ≥ 0 gigabits of data at the beginning of the time horizon.

Communications are possible when a station is reachable from the satellite (during visibility windows). We denote by L s ⊆ L the set of reachable stations during the slot s.

Characteristics of optical links during communications between satellites and ground stations are not well known and multiple parameters, mainly clouds, may influence the established link during a visibility windows, thus impacting the final data-rate. The computation of the real data-rate would be too complicated and beyond the scope of this paper, so we choose to simplify the problem as follows: for any visibility window (s, i) between the satellite and the station i during the slot s, we compute beforehand the amount of data q s s that can be downloaded using archived data from a cloud database, and we assume that this volume can be downloaded instantaneously at the beginning of the visibility window. Thus, each visibility window is reduced to a single time point associated with a download volume, which we call a download window. We denote by Q = {(s, i) , s ∈ S, i ∈ L s } the set of all possible download windows.

We assume that the satellite cannot switch from one station to another in the middle of a visibility windows (two overlapping visibility windows cannot be both used). Thus, for two overlapping visibility windows, the two associated download windows are in mutual exclusion. We define I ⊆ 2 Q the set of incompatible download windows.

Mixed Integer Linear Program

To model the MaxPDT problem, we first consider two types of binary variables for the selection of stations and download windows. For each station i ∈ L, we define binary variables y i ∈ {0, 1}: y i = 1 if and only if the station i is chosen (L ′ = {i, y i = 1}), and for each reachable station i ∈ L s , we define binary variables x s i ∈ {0, 1}: x s i = 1 if and only if there is a download to station i during the acquisition slot s. Moreover, we introduce two real variables to model the amount of sent and lost data. For each slot s ∈ S we define b s ∈ R + the amount of data in the buffer at the end of s (b 0 = B 0 is the initial amount of data in the buffer) and l s ∈ R + the amount of data lost during s.

The objective is to maximize the Percent of Data Transferred or minimize the amount of data lost: max

L ′ ⊆L P DT (L ′ ) ⇔ min L ′ ⊆L losses(L ′ ) ⇔ min L ′ ⊆L s∈S l s s.t. x s i ≤ y i , s ∈ S, i ∈ L s (1a) (s,i)∈X x s i ≤ 1, X ∈ I (1b) b s + l s = max 0, b s-1 + a s - i∈L s x s i q s i , s ∈ S (1c) 0 ≤ b s ≤ B -a s+1 , s ∈ S (1d) b S = B 0 (1e) i∈L w i y i ≤ K (1f)
Constraints (1a) and (1b) prevent downloads on stations that are not chosen (y i = 0) and on forbidden set of locations. Constraints (1c) and (1d) force the amount of data at the end of a slot s to be consistent with the amount at the beginning of s and s + 1 and to be less than the buffer size B minus the acquisition of slot s + 1 (i.e. at the end of slot s, there must be at least a s+1 free space in the buffer). Constraint (1e) forces the final amount of data in the buffer to be the same as the initial buffer B 0 . Constraint (1f) forces the total cost of the network to be less than the maximum cost allowed K. Constraints (1c) can easily be linearized by introducing binary variables δ s and constraints (1a) can be enhanced by forcing the model to use all nonoverlapping download windows on chosen stations (x s i = y i if ∀X ∈ I, (s, i) / ∈ X ).

Hierarchical approach

Overview

In real instances, the number N of possible locations for the stations is often very small (some tens), but the temporal horizon is large (some years), and thus the number of x s i variables is orders of magnitude larger than the number of y i variables. We propose to separate the decision process of these variables into two cooperative algorithms: A Master algorithm will exhaustively enumerate all possible networks of ground stations (decide y i variables) and a Slave dynamic programming algorithm will evaluate the PDT of each of these networks by affecting values to the x s i variables. Once a network has been found by the Master algorithm (y i are decided), the remaining problem reduces to constraints (1b) to (1e) of the MaxPDT problem. In the following, we will details the Slave dynamic programming algorithm that we use to solve this reduced problem.

Label definition

The algorithm proceeds by extending a tree of labels which can be active or visited. A label h = (b h , l h , Ω h , W h ) is associated to each node in this tree. b h is the current amount of data in the buffer, l h the accumulated losses since the beginning, Ω h the set of conflicting windows and W h the list of download windows used.

The initial tree is made of a single active root node with a label h 0 = (B 0 , 0, ∅, ∅).

Label extension

The tree is extended in a breadth-first search manner: at each step, each active node having a non-dominated label is extended to a set of new active nodes and then marked visited, while any node with a dominated label is simply marked visited (no extension is made from dominated nodes).

Extension steps are made in a chronological order at the beginning of each acquisition slot and for each download window as follows:

When an acquisition slot is processed, each active node with a label h not dominated by another active node is extended to a new node having label h ′ with updated amount of data lost and in the buffer, b h ′ = min(B, b h + a s ) (acquisition data are added to the buffer) and l h ′ = l h + max(0, b h + a s -B) (if the buffer is not big enough, old data are lost). Conflicts and used download windows are not changed (Ω h ′ = Ω h and W h ′ = W h ).

When a download window w = (s, i) is processed, each active node with label h is extended with one or two nodes with associated labels h 1 and h 2 :

• If w ∈ Ω h (the window is in conflict with the solution associated with h), the node is simply duplicated (one new child node is created with h 1 = h).

• Otherwise, two new nodes are created: (i) One is a duplication of the current active node, i.e. it is node with label h 1 = h which corresponds to a solutions where the window w is not chosen (x s i = 0). (ii) The second one is an extension with label h 2 and corresponds to a solution where the window w is used (x s i = 1), thus:

• W h 2 = W h ∪ {w} -
The window is added to the set of used download windows;

• b h 2 = max(0, b h -q s i
) -Data sent during the window are removed from the buffer;

• Ω h 2 = Ω h ∪ ω w -Future windows in conflict with the window w are added to the set of conflicting windows of the solution.

After any extension step, the set of conflicting windows Ω associated with any active nodes is reduced by removing all windows in the past, i.e. windows that cannot be used in future solutions.

Dominance rules

From the above extension rules, we see that the number of nodes can double at each extension step. This exponential growth of the tree must be controlled by the use of dominance rules while ensuring optimality.

We say that a label h 2 is dominated by a label h 1 (h 2 ≺ h 1 ) if and only if Ω h 1 = Ω h 2 , two labels can only be compared if they have the same set of conflicting windows, and:

b h 1 < b h 2 ∧ l h 1 ≤ l h 2 or b h 1 = b h 2 ∧ l h 1 < l h 2 (2a) or b h 1 = b h 2 ∧ l h 1 = l h 2 ∧ W h 1 ≺ W h 2 (2b)
Conditions (2a) compares labels according to the amount of data lost (current objective value) and the amount of data in the buffer. If there are less losses and less data remaining in the buffer in h 1 than in h 2 , then the solution corresponding to h 1 is better than the one for h 2 . Since Ω h 1 = Ω h 2 , any choice possible for extending h 2 is also possible for h 1 (the only constraints for extension come from conflicting windows), so if h 1 is better than h 2 , there will be at least one solution made from extending h 1 that will be better than any solution created by extending h 2 , thus h 1 dominates h 2 . Condition (2b) is only used to avoid having solution with the same objective value: two solutions may have the same amount of data lost and in the buffer, keeping both of them would be inefficient, so we remove the one with the worst set of used download windows (≺ must be a strict total order). This algorithm has a worst-case exponential complexity, but we will see that on real instances with few overlaps, the computation time is near linear. Moreover, the dominance rules guarantee that the dynamic programming algorithm provides optimal solutions, and combined with the exhaustive enumeration of the Master algorithm, we have the guarantee to find optimal solutions to the original MaxPDT problem.

Experiments and Results

The algorithm was implemented in C++. All experiments where run on a 8-cores machine with 32GB of RAM running Linux (Ubuntu v14.04.4 LTS) and the proposed hierarchical algorithm was made parallel and was allowed to use the 8 cores of the machine. The MILP solver used was CPLEX 12.6.3.

We generated custom instances for a low-earth orbiting satellite using concepts of operations from [START_REF] Ioag) | Optical link study group final report[END_REF], [START_REF] Guérin | Evaluation of new technological concepts for high data rate payload telemetry[END_REF] and [START_REF] Lacoste | Fso ground network optimization and analysis considering the influence of clouds[END_REF] (data-rate D R = 10.5 Gbps, buffer size B = 2300 Gbits, an acquisition (slot) every hour and a constant acquisition volume of a s = 500 Gbits). We used the ERA Interim cloud database (freely available) [START_REF] Dee | The era-interim reanalysis: configuration and performance of the data assimilation system[END_REF] to approximate the cloud cover c s i ∈ [0, 1] during any visibility window (s, i). Visibility windows of the satellite were computed using the Systems Tool Kit (AGI). We assumed that the download volume for a download window (s, i), q s i , was proportional to (1c s i ) and to the duration of the visibility window d s i , i.e.

q s i = D R * d s i * (1 -c s i ).
We discarded visibility windows that were too cloudy (c s i > γ) or too small (q s i < β = 1 Gbits). We used two different networks composed of 11 (N 11 ) and 16 (N 16 ) possible locations and since we could not find realistic information on the costs, we choose to simply select fixed numbers K of stations (between 1 and 16). We generated instances of various time horizons of one year, five years (partial instances) and 21 years (global instances).

Table 1 compares the MILP and the hierarchical approach on yearly, partial and global instances (with K = 7 and γ = 1.0), results are averaged for yearly and partial instances and Gap is the difference between the two methods. Results show that while the MILP solver manages to provide optimal solutions for the yearly instances, it only manages to provide non-optimal ( * ) solutions for some partial instances (optimal only for N 11 ), and it cannot solve the more complex instances (global), while the hierarchical approach provides optimal solutions for all instances in reasonable time. Figure 1 shows computation times for the hierarchical approach on N 16 for the four partial instances (with a time horizon of 5 years, results are averaged for all values of γ). Figure 1a displays an exponential behavior regarding the number of selected stations due to the exhaustive enumeration of the Master algorithm, while Figure 1b shows a near-linear behavior regarding the size of the time horizon. This linear growth may be explain by the fact that their are few overlaps and a lots of slots without any download windows in real instances, thus allowing the dominance rules to prune branches efficiently.

N
These results show that although the dynamic programming algorithm has a worst-case exponential complexity, the dominance rules perform very well on real instances.

Conclusion and perspectives

In this paper, we consider the MaxPDT optimization problem in the context of optical communications between a satellite and a network of ground stations. We model this problem using an aggregation of visibility windows. We propose a Mixed Integer Linear Program and an optimal hierarchical method using a complete enumeration of the subsets of locations and a dynamic programming (sub-)algorithm from the remaining problem. We show that while this dynamic-programming algorithm is theoretically exponential, its running time on real instances is nearly linear regarding the size of the temporal horizon of the instances and allow the hierarchical approach to outperform the MILP solver we tested. Solving such instances rapidly make it possible to analyze the impact of system parameters (data-rate, buffer size, network size) on spatial imagery systems using free-space optical communications. For our hierarchical approach, we use a simple exhaustive enumeration to find networks, which may not work on large instances with tens of stations. In the near future, we hope to solve instances with bigger networks and with more realistic costs by using custom (possibly approximate) algorithms for the enumeration of the networks. Furthermore, in the MaxPDT problem, we average the Percent Data Transferred over the whole horizon, which may result in solutions having months with very low PDT. In order to avoid such solutions, it might be interesting to look at a MaxMinPDT problem, in which the objective would be to maximize the minimum monthly PDT. A slightly modified version of our dynamic programming algorithm could be used for this purpose.

Fig. 1 .

 1 Fig. 1. Hierarchical Approach performance on partial instances

Table 1

 1 Comparison of CPU time and GAP between MILP and HA.


Mikaël Capelle

Marie-José Huguet

Nicolas Jozefowiez

Xavier Olive

For space industries, free-space optical communications are becoming a mature technology, but the impact of their use to download observations from spatial imagery systems has still to be evaluated. Unlike current radio-frequency technology, freespace optical communications are strongly impacted by weather conditions, and most notably by clouds. In order to cope with the later, it is necessary to achieve ground station diversity, i.e. having a network of optical ground stations able to receive data from satellites. In this paper, we aim to find a subset of a given number of ground stations maximizing the amount of data that can be downloaded from a low-earth orbiting satellite to the Earth during its missions. We present a Mixed Integer Linear Program model and a hierarchical method based on an exhaustive enumeration of the sets of stations and on a dynamic programming algorithm to solve it. The efficiency of this method is evaluated on several instances based on real ground station networks and on cloud cover throughout the last twenty years.

A hierarchical approach for the selection of optical ground stations maximizing the data transfer from low-earth observation satellites

I. Introduction

Free-Space-Optical (FSO) communications are seen as a key technology [START_REF] Kernec | Space evaluation of optical modulators for microwave photonic on-board applications[END_REF] [2] [START_REF] Roy | Optical feeder links for high throughput satellites[END_REF] to cope with the needs of higher data-rate for future low-earth orbiting (LEO) observation satellites in replacement to current radio-frequency (RF) technologies. While the later is a very mature and well proven technology which has been used for decades, the former may be able to offer data-rates beyond the reach of RF.

Current RF technology uses X-Band for downloads which can currently provide some Gbps ( [START_REF] Eilertsten | Ground station networks vs. geo relay satellites for polar orbiting satellites data download[END_REF]). These are not impacted by weather or atmospheric turbulences, thus allowing the establishment of communication link at very low elevation angle, thus increasing the link duration. Its main drawbacks are its limited data-rate and the need of frequency licensing which will be a major issue in the upcoming years due to the increase in the number of operational satellites and constellations. FSO communications offer data-rate order(s) of magnitude higher than current RF technologies: targeted data-rates go from some tens of Gbps to some Tbps. Thanks to their very narrow beam, they do not require frequency licensing and are hard to intercept by malicious observer. They offer a better power efficiency compare to RF and reduced payload sizes which is very useful for nano and micro satellites. However, FSO communications are strongly impacted by weather, cloud, and atmospheric turbulences. Most clouds block the communications and atmospheric turbulences have to be compensated using new technologies such as adaptive optics or DPSE (Differential Phase Shift Encoding) [5] [6].

This paper focuses on the so-called MaxPDT problem, an Optical Ground Station Network (OGSN) optimization problem for LEO satellites. We aim to obtain an efficient network of optical ground stations in order to maximize the percentage of data downloaded, taking cloud information into account using archived data from previous decades. We propose a new model for the problem based on a simplification of the visibility windows into download windows which allows us to solve it on very large temporal horizon (multiple decades), hence allowing us to mitigate temporal variations in the atmosphere and to analyze the system evolution over multiple years.

In Section II, we will start by a state of the art on existing work regarding the optimization of network of optical ground stations. Then, we will characterize more formally the problem under study, propose a Mixed Integer Linear Program and a hierarchical method based on a dynamic programming algorithm to solve it in Section III. Finally, we will present our experimental context and the generation of instances based on past cloud data in Section IV and the results of our experimentation in Section V.

II. State Of the Art

The optimization of an OGSN taking into account the influence of clouds was first studied by [START_REF] Link | Mitigating the impact of clouds on optical communications[END_REF] and [START_REF] Wojcik | Deep-space to ground laser communications in a cloudy world[END_REF]. Their objective was to find a network for a deep-space probe in order to reach a given temporal availability using an approximation algorithm with a high-resolution cloud database as input.

In [START_REF] Takayama | Estimation of accessible probability in a low earth orbit satellite to ground laser communications[END_REF], a probabilistic approach was used to analyze the availability of various ground station networks: one in Japan for a geostationary satellite and one worldwide for a low-earth orbiting satellite (LEO) satellite. In [START_REF] Guérin | Evaluation of new technological concepts for high data rate payload telemetry[END_REF] the impact of using FSO for LEO satellites was analyzed using mission information from multiple existing satellites showing that the average download volume could reach 26.9 (resp. 81.9) terabits a day for mid-latitude (resp. high-latitude) stations assuming average clear sky probability of 65% (resp. 55%). In [START_REF] Guérin | Optimisation of an optical ground stations network[END_REF], a custom algorithm based on geographical information and monthly and yearly cloud statistics was used to create and analyze the daily availability of networks of two, three and four stations in Europe. These results were analyzed in [START_REF] Lacoste | Fso ground network optimization and analysis considering the influence of clouds[END_REF] using orbital information from various missions, showing that one midlatitude station could handle some terabits a day while one high-latitude station was not able to handle 80 terabits a day as predicted in [START_REF] Guérin | Evaluation of new technological concepts for high data rate payload telemetry[END_REF], and that network composed of two to four stations were able to outperforms RF ones even for low optical data-rate (10.5 Gbps).

In [START_REF] Poulenard | High altitude clouds impacts on the design of optical feeder link and optical ground station network for future broadband satellite services[END_REF] and [START_REF] Poulenard | Ground segment design for broadband geostationary satellite with optical feeder link[END_REF], a greedy algorithm was used to find a network of stations in Europe for a geostationary satellite based on data from the SAF-NWC cloud database and using an hypothetical substrate network. In [START_REF] Fuchs | Ground station network optimization for space-to-ground optical communication links[END_REF] and [START_REF] Giggenbach | A high-throughput satellite system for serving whole europe with fast internet service, employing optical feeder links[END_REF], various network were found and analyzed in Germany, Europe and "extended" Europe with custom algorithms (one optimal for small instances, and another approximate for large instances) using cloud data from the SEVIRI payload, showing that concentrated network were not as efficient as distributed one, even for geostationary satellites. Finally, the link availability of networks of one, two or three stations for a 77°E geostationary satellite were analyzed in [START_REF] Chen | The link availability analysis of geo satellite-to-ground laser communication[END_REF] using cloud images taken between October 2013 and September 2014 from various satellites.

In 2012, the Optical Link Study Group (OLSG), established by the Inter-agency Operations Advisory Group (IOAG) in 2010, published a report in which the impact of FSO communications on various space systems (LEO observation satellite, geostationary relay) was evaluated using the so-called Lazercom Network Optimization Tool (LNOT) [START_REF] Link | Mitigating the impact of clouds on optical communications[END_REF].

III. Modeling and Solving the MaxPDT problem A. Problem statement

In this paper, we are interested in the MaxPDT problem: given a set L of N locations of ground stations, find a subset L of these stations with a cost lower than K that maximize the Percent Data Transferred [START_REF] Olsg | Optical link study group final report[END_REF] (PDT), i.e. the percentage of data acquired during a run that has been successfully sent to the ground.

We do not take into account complex mission information regarding image acquisition: We assume that the time horizon is divided in successive acquisition slots and that a given amount of data is acquired at the beginning of each of these time slots [START_REF] Olsg | Optical link study group final report[END_REF]. The policy for the acquisition downloads is First-In First-Out.

Communications are possible when a station is reachable from the satellite (during visibility windows). We assume that the satellite cannot switch from one station to another during a visibility window (two overlapping visibility windows cannot be both used).

Characteristics of optical links during communications between satellites and ground stations are not well known and multiple parameters, mainly clouds, may influence the established link during a visibility window, thus impacting the final data-rate. The computation of the real data-rate would be too complicated and beyond the scope of this paper, so we choose to simplify the problem as follows: for each visibility window, we compute beforehand the amount of data that could be downloaded using archived data from a cloud database, and we assume that this volume can be downloaded instantaneously at the beginning of the visibility window. Thus, each visibility window is reduced to a single time point associated with a download volume, which we call a download window, and for two overlapping visibility windows, the two associated download windows are in mutual exclusion.

B. Mixed Integer Linear Program

In this section we propose a Mixed Integer Linear Program model for the MaxPDT problem. We define:

• K: maximum cost for the stations;

• L = {1, . . . , N }: set of available locations; • S = {1, . . .

, S}: set of acquisition slots;

• w i : cost of opening a ground station at location i; • L s : set of stations reachable during s (L s ⊆ L); • B ≥ 0: size of the buffer; • B 0 ≥ 0: initial amount of data in the buffer;

• a s : amount of data acquired at the beginning of s; During an acquisition slot s, to each reachable station i ∈ L s is associated a download window and its amount of data q s i ∈ R + . Furthermore, Q = {(s, i) , s ∈ S, i ∈ L s } represents the set of all possible download windows, and I ⊆ 2 Q is the set of incompatible download windows (due to overlapping visibility windows).

For each station i ∈ L, we define binary variables x i ∈ {0, 1}: x i = 1 if the station i is chosen, 0 otherwise, for each slot s ∈ S we define b s ∈ R + the amount of data in the buffer at the end of s (b 0 = B 0 is the initial amount of data in the buffer) and l s ∈ R + the amount of data lost during s. For each slot s ∈ S and each reachable station i ∈ L s , we define binary variables x s i ∈ {0, 1}: x s i = 1 if there is a download to station i during the acquisition slot s, 0 otherwise.

The objective is to maximize the Percent of Data Transferred [START_REF] Olsg | Optical link study group final report[END_REF] or minimize the amount of data lost: max

L ⊆L P DT (L ) ⇔ min L ⊆L losses(L ) ⇔ min L ⊆L s∈S l s
The constraints are:

x s i ≤ x i , s ∈ S, i ∈ L s (1a) (s,i)∈X x s i ≤ 1, X ∈ I (1b) b s + l s = max 0, b s-1 + a s - i∈L s x s i q s i , s ∈ S (1c) 0 ≤ b s ≤ B -a s+1 , s ∈ S (1d) b S = B 0 (1e) i∈L w i x i ≤ K (1f)
Constraint 1a prevents downloads on stations that are not chosen (x i = 0). Constraint 1b prevents mutual downloads on forbidden set of locations. Constraint 1c forces the amount of data at the end of a slot s to be consistent with the amount at the beginning of s and s+1. Constraint 1d forces the amount of data in the buffer at the end of slot s to be less than the buffer size B minus the acquisition of slot s + 1, i.e. at the end of slot s, there must be at least a s+1 free space in the buffer. Constraint 1e forces the final amount of data in the buffer to be the same as the initial buffer B 0 . Constraint 1f forces the total cost of the network Cost(L ) to be less than the maximum allowed cost K.

C. Hierarchical approach 1) Decomposition of the problem:

The problem MaxPDT may be split into two parts:

• the choice of the stations (variables x i );

• the choice of the download windows (variable x s i ). In real instances, the number N of possible locations for the stations is often very small (some tens), the temporal horizon is large (some years), and thus the number of x s i variables is orders of magnitude larger than the number of x i variables.

Even if these two types of variables are linked by the constraint 1a, it is possible to separate their decision processes in two different stages:

• A Master algorithm selects subsets L ⊆ L of ground stations such that Cost(L ) ≤ K; • for each set L of ground stations, a Slave algorithm chooses optimal values for the x s i variables. These two stages can be iterated: for each subset L ⊆ L of stations found by the Master algorithm, the Slave algorithm can be used to complete the solution.

In the next section, we focus on the second stage of this approach, i.e. the choice of optimal values for the x s i variables, and we propose to solve it using a dynamic programming algorithm.

2) Master algorithm: For our Master algorithm, we will use a simple exhaustive enumeration of all possible networks (running in exponential complexity).

3) Dynamic programming algorithm for the choice of download windows: Once the stations have been chosen, the targeted problem reduces to constraints 1b to 1e.

The algorithm proceeds by extending a tree. A label h = (b h , l h , Ω h , W h ) is associated to each node in this tree: b h : the current amount of data in the buffer; l h : the accumulated losses since the beginning; Ω h : the set of overlapping (conflicting) windows; W h : the list of download windows used. The initial tree is made of a single root node with a label h 0 = b 0 , 0, ∅, ∅ . The tree is extended in a breadthfirst search (BFS) manner: at each extension step, a new level is created and every node that is not dominated is extended to at least one node in the new level.

An extension step is made at the beginning of each acquisition slot and for each download window. These extension steps are made in a chronological order: given two slots s and s + 1, an extension step for a window in L s is made after the one for the beginning of s and before the one for the beginning of s + 1.

The extension of the tree is made as follow: When an acquisition slot is processed, each leaf label h not dominated by another label on the same level is extended to a new node label h with:

h = (min(B, b h + a s ), l h + max(0, b h + a s -B), Ω h , W h )
When a download window w = (s, i) is processed, each leaf label h is extended with one or two labels: If w ∈ Ω h , the label is simply duplicated (one new child is created), otherwise, the label is duplicated and a new one h is created, where:

h = (max(0, b h -q w ), l h , Ω h ∪ ω w , W h ∪ {w})
With q w = q s i the download volume of w = (s, i) and ω w the set of overlapping windows for w.

From this, we know that the number of labels in the new level is at most twice the number of labels in the extended level. This exponential growth of the tree must be controlled by the use of dominance rules while ensuring optimality.

Before describing this dominance rule, we define Ω - h as the reduced set of overlapping windows for h containing only the relevant windows for the following acquisition slots (this set can be reduced since conflicts in the "past" do not affect future choices):

Ω - h = {w = (s , i) ∈ Ω h | s > s} We say that a label h 2 is dominated by a label h 1 (h 2 ≺ h 1 ) iff Ω - h1 = Ω - h2
(two labels can only be compared if they have the same conflicts) and:

b h1 < b h2 ∧ l h1 ≤ l h2 (2a) or b h1 = b h2 ∧ l h1 < l h2 (2b) or b h1 = b h2 ∧ l h1 = l h2 ∧ W h1 ≺ W h2 (2c)
Labels are compared by their amount of data lost and in the buffer. 2c is used to avoid having solution with same objective value: two solutions may have the same amount of data lost and in the buffer, keeping both of them would be inefficient, so we remove the one with the worst set of used download windows ( ≺ must be a strict total order).

We can see from this that if ω w ⊆ Ω h , h will always be dominated by h , thus there is no need to duplicate h in this case.

This algorithm has a worst-case exponential complexity, but on real instances with few overlaps, the computation time is near linear. Moreover, the dominance rule guarantees that the dynamic algorithm provides optimal solutions, and combined with the exhaustive enumeration of the Master algorithm, we have the guarantee to find optimal solutions to the original problem.

IV. Experiments A. Description of the scenarios

Our work focuses on sun-synchronous satellites (LEO satellites that pass over any given point of the planet's surface at the same local solar time), with an altitude of about 700 kilometers. Concepts of operations for our satellites are taken from [START_REF] Olsg | Optical link study group final report[END_REF]: we assumed that the satellites acquire data at a fixed rate of 500 Gbits every hour (there is an acquisition slot each hour), and have a buffer of 2.3 terabits.

We assume that it is possible to establish an optical link between a station and the satellite if the elevation is greater than 20 degrees ([10], [START_REF] Lacoste | Fso ground network optimization and analysis considering the influence of clouds[END_REF], [START_REF] Olsg | Optical link study group final report[END_REF]) and that the data-rate D R is constant at 10.5 Gbps during the whole communication.

1) Cloud database: We were not able to access or use databases used by previous papers on the problem, because there were either not freely available or restricted to specific areas of the world (typically Europe).

We found two freely available databases matching our criteria: ERA Interim [START_REF] Dee | The era-interim reanalysis: configuration and performance of the data assimilation system[END_REF] and ISCCP [START_REF] Rossow | Advances in understanding clouds from isccp[END_REF]. While the later has a better temporal resolution (3 hours against 6), its spatial resolution is worse so we chose to use the former.

2) Computation of the download volume: Using the ERA Interim dataset, we first approximate c i (t) the cloud cover ratio (c i (t) ∈ [0, 1]) over the station i at time t: Since this dataset has a 0.75×0.75 degrees spatial resolution and a 6 hours temporal resolution, we chose to use the closest cell to the station (spatially) and linearly interpolate ( [START_REF] Grisheckin | Clouds handling for planning of optical space missions[END_REF]) the cloud cover between two measures (temporally).

Given a visibility window vw starting at t vw start and ending at t vw end , and the cloud cover ratio c i (t), we assume that the download volume dl vw is proportional to the window length (t vw end -t vw start ) and the cloud cover (1 -c i (t vw start )). We set a threshold γ on cloud cover such that if c i (t vw start ) is greater than γ, the download volume is equal to 0. Furthermore, we discard any visibility windows vw where the download volume is less than a given volume threshold β by analogy with the fact that short windows are not used in RF. To summarize, the download volume dl vw is obtained by:

dl vw =      0 if c i (t vw start ) ≥ γ 0 if D R * (t vw end -t vw start ) × (1 -c i (t vw start )) ≤ β D R * (t vw end -t vw start ) × (1 -c i (t vw start )
) otherwise We choose to set β to 1 gigabit and we consider different values of γ from 0.1 (discard if the cloud cover is greater than 10%) to 1.0 (never discard due to cloud cover) to analyze the "impact" of our cloud hypothesis on the solutions.

B. Input networks and temporal horizons

We run our experiments on two ground locations networks: one from [START_REF] Olsg | Optical link study group final report[END_REF] denoted N 16 and containing 16 stations around the world, and the other, N 11 , composed of 11 stations mainly located in Europe.

Since no relevant information could be obtained regarding the cost of opening or converting a station at the given locations, we chose to set w i = 1 for all stations i ∈ L. The purpose of the algorithm was then to find a subset L of stations with |L | = K (select K stations from L).

The visibility windows between the satellites and the stations of the two networks were generated using STK1 on a 21 years horizon (1990 to 2010). For each network, yearly instances from 1990 to 2010, partial instances containing 5 years of data (1990-1994, 1995-1999, 2000-2004 and 2005-2009) and a global instance spanning the whole 21 years were created.

V. Results

The algorithm was implemented in C++. All experiments where run on a 8-cores machine with 32GB of RAM running Linux (Ubuntu v14.04.4 LTS) and the proposed hierarchical algorithm was made parallel and was allowed to use the 8 cores of the machine.

A. Computation time and PDT for MaxPDT

Table I shows the computation time and PDT using K = 1, 4 or 7 stations on N 11 and N 16 in average for yearly and partial instances and for the global instances (21 years) with a cloud threshold γ = 1.0. Figure 1 focuses on the computation time for N 16 when selecting from K = 1 up to K = 16 stations, and for different temporal horizons (1 year, 5 years, 21 years).

Results from Table I and Figure 1 show that on real instances, the computation time growth almost linearly with the temporal size of the instances and exponentially with the number of stations chosen (due to the exhaustive enumeration by the Master algorithm). The linear growth may be explained by the distribution of download windows over the slots: On real instances, there are few overlaps (and thus few duplication of labels) and a lots of slots without any windows, allowing the dominance rule to prune labels efficiently.

Except for the single station network, results from Table I show that the PDT found for N 11 are lower than the one for N 16 , this may be explained by the fact that N 11 stations are concentrated on Europe while N 16 is a worldwide network. Moreover, results show that PDT for N 11 varies more over the years and is less stable than the one for N 16 -The standard deviation (not shown in Table I) is always about one order of magnitude larger for N 11 than for N 16 .

B. Comparison with previous work

In [START_REF] Guérin | Optimisation of an optical ground stations network[END_REF], monthly and yearly percentage of cloud free line-of-sight (PCFLOS) for 6 European stations and a polar station (Svalbard) are given, and in [START_REF] Lacoste | Fso ground network optimization and analysis considering the influence of clouds[END_REF], average daily download volumes for these stations are shown for various LEO satellites. We computed the PCFLOS and average daily download volumes for these stations using our database and the same method from [START_REF] Guérin | Optimisation of an optical ground stations network[END_REF] or [START_REF] Lacoste | Fso ground network optimization and analysis considering the influence of clouds[END_REF].The results for some stations are shown Figures 2a and2b (2b contains the 7 stations used in [START_REF] Guérin | Optimisation of an optical ground stations network[END_REF] and [START_REF] Lacoste | Fso ground network optimization and analysis considering the influence of clouds[END_REF] while 2a focuses on specific ones).

Figure 2a shows that monthly and yearly PCFLOS from our database (dashed lines) are most of the times lower than the one found by [START_REF] Guérin | Optimisation of an optical ground stations network[END_REF] (plain lines). For European stations, the difference is small (except for one station), but for Svalbard (the polar station), the difference may go up to 40%. Figure 2b shows that using the ERA Interim database, the average daily volume of data downloaded is always lower, especially for Svalbard (the volume found by [START_REF] Lacoste | Fso ground network optimization and analysis considering the influence of clouds[END_REF] is twice as much as the volume we found). Figures 2a and2b shows that for European stations, the two databases are similar for most of the stations, but for polar stations such as Svalbard, the difference are really important. The average daily download volumes were obtain using the method from [START_REF] Lacoste | Fso ground network optimization and analysis considering the influence of clouds[END_REF] which is equivalent to the one described in IV-A2 with a cloud threshold γ = 1.0. Since we did not have access to the database used by [START_REF] Guérin | Optimisation of an optical ground stations network[END_REF] and [START_REF] Lacoste | Fso ground network optimization and analysis considering the influence of clouds[END_REF], we were not able to compare the results for different values of γ.

In [START_REF] Olsg | Optical link study group final report[END_REF], a network of 7 stations (from the N 16 network) was found with a PDT of 94.8%. Figure 3 compare the results of the Optical Link Study Group [START_REF] Olsg | Optical link study group final report[END_REF] with our results for various cloud thresholds γ. In order to obtain these results, we generated instances using the network from [START_REF] Olsg | Optical link study group final report[END_REF] for various value of γ, then solved these using our dynamic programming algorithm and finally compared the output with our hierarchical approach. Results show that our algorithm MaxPDT always find a better network, whatever the cloud threshold γ used, using our cloud database. We do not have information on the cloud database and cloud model used in [START_REF] Olsg | Optical link study group final report[END_REF], but given the network found, we obtained almost the same PDT (shown by the dashed line) as [START_REF] Olsg | Optical link study group final report[END_REF] with γ = 0.5.

VI. Conclusion

For the MaxPDT problem, we proposed a Mixed Integer Linear Program based on a simplification of the visibility windows, and an optimal hierarchical method based on a complete enumeration of the subsets of the stations and on a dynamic programming (sub-)algorithm for the choice of the download windows. From our results, we proved that it was possible for an Optical Ground Station Network to achieve more than acceptable results regarding the Percent of Data Transferred. Comparisons with previous works showed that different cloud databases and models can give very different results, thus, we designed our model and algorithm such that the pre-processing of the instances allows for an easy switch from one database or cloud model to another.

The proposed algorithm aims at maximizing the Percent Data Transferred over a given horizon, but from a commercial point of view, a more robust guarantee may be to try to maximize the minimum Percent Data Transferred for given rolling time periods (e.g. 30 days). A slightly modified version of our dynamic programming algorithm could be used for this purpose. Experiments made here are from real instances (real network of stations), with 11 and 16 stations respectively, which make our exhaustive enumeration work pretty well. In the near future, we hope to solve instances with larger networks using a custom algorithm for the enumeration of the sub-sets of stations. Finally, in our experiments we used a specific cloud database (ERA Interim); As previously mentioned, our algorithms do not dependent on the cloud database or cloud model used so it would be an interesting idea to validate our algorithms using different databases or models such as the ones used by other authors.

Fig. 1 :

 1 Fig. 1: Computation time for N 16

Fig. 2 :

 2 Fig. 2: Comparison with [10] [11] [12]

Fig. 3 :

 3 Fig.3: Comparison of PDT between our method and the OLSG[START_REF] Olsg | Optical link study group final report[END_REF] results

TABLE I :

 I Computation time and PDT for N 11 and N 16 .

Systems Tool Kit, former Satellite Tool Kit -http://www.agi. com/products/stk/


est destinée au dépôt

The expression of motion in Russian.

Tatiana Iakovleva

To cite this version:

  Tatiana Iakovleva. The expression of motion in Russian.: Proposal for the workshop 'Neglected aspects of motion-event descriptions Beyond the Path/Manner dichotomy' . NAMED (Neglected aspects of motion-event descriptions Beyond the Path/Manner dichotomy), May 2017, Paris, France. . hal-The expression of motion in Russian: intra-language variation Tatiana Iakovleva Variability in the expression of vertical (UP/DOWN) and horizontal (ACROSS) motion in Russian. Signs of a split system and a parallel system of conflation in Russian Main Argument Neglected aspects of motion in Russian *This study was carried out at the SFL laboratory (Paris, Pouchet) (CNRS) The study • Subjects: 12 Russian adult L1 speakers • Items: a series of cartoons showing: -different manners of motion (Hendriks & Hickmann 2011): climbing, running, swimming, crawling, biking, skating, sliding… -three Paths: upward motion ↑, downward motion ↓, boundary-crossing motion Results Table 1: Semantic information encoded in verbs(a) and other devices(b) P = Path, M = Manner, PM = Manner-and-Path conflation (hybrid verbs), L = Location, 0 -No information encoded Choice of different constructions depending on the event type (SPLIT SYSTEM): : -hybrid verbs vs. Manner verbs (zabratsia/zabirat'sia vs. za-lezt' 'climb') with UP (PARALLEL system) -predominant verb-framed constructions with DOWN (spustit'sia 'descend') -satellite-framed constructions with ACROSS (<pere+Manner in the verb root>) Manner-and-Path (MP) in hybrid verb roots: -zabrat'sia/zabirat'sia 'climb[PF/IPF] (onto)' -bezhat' 'courir', lezt' 'climb' (simplex unidirectional verbs of motion) Simplex multidirectional verbs of motion: katat'sia (na kon'kax) 'skate', begat' 'run' email: tatiakovleva@yahoo.fr of stimuli, N=12 (Hendriks & Hickmann 2011)