Kevin Duy

Nguyen

Olivier Pascal

Jérôme Sokoloff

Alexandre Chabory
email: alexandre.chabory@recherche.enac.fr

Baptiste Palacin

Nicolas Capet

Discussion About the Link Budget for Electromagnetic Wave with Orbital Angular Momentum

Keywords: antenna, link budget, OAM, gain, MIMO, SVD

This paper presents a discussion about the RF link budget for a communication system based on unusual waves carrying a non-zero orbital angular momentum (OAM). A typical configuration using circular antenna arrays of isotropic sources to transmit and receive OAM waves is considered. We point out issues when usual assumptions are made to express the link budget. Then, we propose to express the power budget associated with OAM in an elementary MIMO matrix approach. Using a single mode communication configuration, some basic numerical calculations and case studies based on the developed formulations can then be led and discussed, highlighting some intrinsic limitations. Indeed, the asymptotic behavior of the link budget leads to question the concepts of gain and propagation losses.

I. INTRODUCTION

From fundamental physics, it has been proven that electromagnetic waves are carrying both linear and angular momentum [START_REF] Poynting | The wave motion of a revolving shaft, and a suggestion as to the angular momentum in a beam of circularly polarised light[END_REF]. Since the thirties, the mechanical properties of the angular momentum have been demonstrated theoretically and experimentally [START_REF] Beth | Mechanical detection and measurement of the angular momentum of light[END_REF]. The total angular momentum can be divided into spin angular momentum (SAM), which refers to polarization, and orbital angular momentum (OAM), which is related to the spatial distributions of the field magnitude and phase [START_REF] Allen | Orbital angular momentum of light and the transformation of laguerregaussian laser modes[END_REF].

On the one hand, the SAM, or polarization, with two orthogonal modes is now well known and widely exploited in operating communication systems. On the other hand, the OAM has not yet been used, even though it represents a fundamental new degree of freedom that might be a powerful asset for many applications like improving radio capacities as controversially discussed in several recent papers [START_REF] Tamburini | Encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF], [START_REF] Edfors | Is orbital angular momentum (oam) based radio communication an unexploited area?[END_REF], [START_REF] Tamagnone | Comment on encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF].

During the last two decades, the photon OAM has been widely studied in optics with Laguerre-Gaussian beams [START_REF] Allen | Orbital angular momentum of light and the transformation of laguerregaussian laser modes[END_REF], [START_REF] Padgett | The poynting vector in laguerre-gaussian laser modes[END_REF]. For some years, it has been proven that OAM can be used in the radiofrequency domain, theoretically [START_REF] Thide | On the utilization of photon orbital angular momentum in the low-frequency radio domain[END_REF], [START_REF] Mohammadi | Orbital angular momentum in radio -a system study[END_REF] and experimentally [START_REF] Tamburini | Encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF]. A circular antenna array [START_REF] Mohammadi | Orbital angular momentum in radio -a system study[END_REF], a plane or spiral phase plate [START_REF] Bennis | Flat plate for oam generation in the millimeter band[END_REF], [START_REF] Beijersbergen | Helical-wavefront laser beams produced with a spiral phaseplate[END_REF] or a helicoidal parabolic antenna [START_REF] Tamburini | Encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF], with dedicated modifications, can generate an electromagnetic wave carrying non-zero OAM. To receive such a wave, a kind of an interferometer appears to be sufficient [START_REF] Tamburini | Encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF]. However, the way experiments are made has to be discussed with the background of traditional communication using multiple-input-multiple-output (MIMO) antenna system [START_REF] Edfors | Is orbital angular momentum (oam) based radio communication an unexploited area?[END_REF], [START_REF] Tamagnone | Comment on encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF].

In this article, we propose to analyze the link between two antennas designed to transmit and receive OAM, and to discuss its efficiency for RF communications. Similar to [START_REF] Tamburini | Encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF], [START_REF] Edfors | Is orbital angular momentum (oam) based radio communication an unexploited area?[END_REF] and [START_REF] Tamagnone | Comment on encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF], a basic configuration using circular antenna arrays both to transmit and receive one single OAM mode will be studied. The link budget is then developed in details and used to question the antenna gain and its asymptotic behavior for different mode orders.

The paper is organized as follows. In Section II, we introduce the classical theory for OAM and link budget. In Section III, the basic geometrical parameters are introduced. The power transfer in an OAM link is then expressed in its simplest form. In Section IV, we perform case studies for different positions of the receiving antenna to question the asymptotic behavior which lead to criticize the concepts of antenna gain and propagation losses.

II. CLASSICAL THEORY

A. Orbital angular momentum

An OAM mode is defined by its integer order l. Remembering the results of [START_REF] Mohammadi | Orbital angular momentum in radio -a system study[END_REF] regarding modal radiation patterns, we can see in Fig. 1 that, assuming l = 0, the main lobe is oriented as usual in the aimed direction of the receiving antenna.

For other values of l, the waves are of vortex shapes with no axial main lobe. The mode mainly radiates energy on a cone which the opening angle of this cone is slightly different when modifying l: the greater the OAM mode, the larger the cone angle.

B. Link budget

A link budget addresses the quality of a communication system. It sums all the gains and losses from the transmitter to the receiver, associated to both the antennas and the propagation medium (Fig. 2).

In its most concise form, its equation is given by

P r = P e G e G r L F S ( 1
)
where P e is the emitted power, G e the transmitting antenna gain, P r the received power, G r the receiving antenna gain and L F S the free space losses.

Firstly, we want to calculate this link budget for two monomode OAM antennas facing each other [START_REF] Tamburini | Encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF], [START_REF] Tamagnone | Comment on encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF]. The Tx antenna radiates an OAM mode of order l and the Rx antenna receives the same OAM mode. This configuration presents issues. When l differs from 0, no field is radiated in the direction of the receiver as shown in Fig. 2. So, no power is transmitted to the receiver, because both G e = 0 and G r = 0 in (1).

Even for vortex waves, if we consider that we are in the very far field, for a classical system we would consider local plane waves coming normally to the receiver. In that case, we could not be able to detect any radio-OAM power at the ports of the receiving antenna because the OAM of a plane wave is equal to zero [START_REF] Humblet | Sur le moment d'impulsion d'une onde lectromagntique[END_REF].

In this section, we have pointed out some problems in the calculation of the link budget. Indeed with classical considerations, it appears that power cannot be neither transmitted nor received with OAM waves. This asymptotic far-field behavior questions the capability of OAM waves to support communications.

III. EXTENDED THEORY

A. Configuration/Setup

Antennas usually do not generate electromagnetic waves with non-zero orbital angular momentum.

To radiate and receive fields carrying a non-zero OAM, we can use a configuration with two circular phased arrays. For the transmitting antenna, the N Tx array elements are distributed equidistantly along the perimeter of a circle. They are phased with a beam forming network (BFN) in such a way that the phase at element n ∈ {0, . . . , N Tx -1} is given by

φ n = 2π ln N Tx ( 2
)
where l is the desired OAM order [START_REF] Thide | On the utilization of photon orbital angular momentum in the low-frequency radio domain[END_REF]. For the sake of simplicity, we further consider that each array element is an isotropic antenna and mutual couplings are negligible. Non-isotropic radiation patterns could be considered for more realistic system analysis. This would not impact the main conclusions of this paper. The receiving antenna is of the same type but may have a different radius R Rx or number of elements N Rx . No hypothesis is made here on the relative position of the receiver with respect to the transmitter in order to achieve a generic formulation. The global configuration is depicted in Fig. 3. In [START_REF] Tamburini | Encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF], [START_REF] Edfors | Is orbital angular momentum (oam) based radio communication an unexploited area?[END_REF], [START_REF] Tamagnone | Comment on encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF], the same configuration is used but the arrays are facing each other, i.e. both are centered and orthogonal to a common axis.

B. OAM link budget

In Fig. 4 we describe the configuration with which OAM modes of orders l are sent and OAM modes of orders l are detected.

The transmission can be divided into three blocks: the beam forming network (BFN) of the transmitter, the propagation channel, and the BFN of the receiver. We will study one by one the contribution of each block.

The first block is the BFN of the transmitter. When we want to transmit one OAM mode of order l and amplitude a OAM l , the BFN must be built in such way that the n-th antenna element is fed with

a feed n = a OAM l √ N Tx exp j2π ln N Tx , n ∈ 0, . . . , N Tx -1 (3)
We can generalize this result by considering that the BFN has N Tx input ports associated with the transmission of OAM modes of order l ∈ {0, . . . , N Tx -1}, considering usual sampling results. N Tx is the number of output ports that feed the array elements. It can also be noticed that although the number of modes is limited with N Tx , the orders can be conveniently shifted to negative values as well.

From (3), the matrix that relates the output a feed n to the output a OAM l is the matrix of the discrete Fourier transform of size N Tx , denoted U.

The second block is the propagation channel, which can be characterized by the channel matrix H. Its terms h pn correspond to the propagation from the element n of the transmitter to the element p of the receiver. Because, we have assumed ideal isotropic array elements, we simply have

h pn = exp (-jkr np ) λ 4πr np ( 4
)
where r np is the distance from element n of the transmitter to element p of the receiver.

The third block is the BFN of the receiver. In order to receive at its output the OAM mode of order l , it must be so that

b OAM l = 1 √ N Rx NRx-1 p=0 b feed p exp -j2π pl N Rx , p ∈ 0, . . . , N Rx -1 (5)
Generalizing to the reception of OAM modes of order l ∈ {0, . . . , N Rx -1}, the BFN can be characterized by the matrix V H where V is the matrix of the discrete Fourier transform of size N Rx .

Finally taking into account the 3 blocks, the OAM link can be characterized by the matrix

H t = V H HU (6)
This matrix takes into account all the parts of the link. Thus, it can be used to derive the power transfer in the context of various OAM transmissions, regarding the versatility of the geometry and the multimode formulation.

We consider the transmission and reception of one single mode of order l. Developing the matrix-vector product, the ratio between the output and input powers is explicitly given by

P r P e = b OAM l a OAM l 2 = NRx-1 p=0 NTx-1 n=0 1 √ N Rx N Tx exp j2πl n N Tx - p N Rx exp (-jkr np ) λ 4πr np 2 (7)
This expression of the received power is unusual compared to (1), even asymptotically when D → ∞. The link budget may depend on the mode order. The capability to define antenna gains G e , G r , and free space losses L F S will be numerically addressed in the next section.

IV. SIMULATIONS FOR IDENTICAL ARRAYS FACING EACH

OTHER

We have proposed a basic but general tool to focus on the mode-per-mode OAM link budget. In this section, simulations are performed for two identical arrays facing each other. As in [START_REF] Mohammadi | Orbital angular momentum in radio -a system study[END_REF], we choose N Tx = N Rx = 12 and R Tx = R Rx = λ. Besides, the frequency is 2.45 GHz so that λ = 0.12 m and the Fraunhofer distance is d Fraunhofer = 0.48 m.

In the Fig. 5, the achieved radiation pattern is depicted for l = 1. We observe a conical mainlobe, and also sidelobes that are due to the 2λ diameter of the antenna. As a first link budget result, the received to emitted powers ratio ( 7) is plotted with respect to the distance in Fig. 6.

The asymptotic behavior appears to be decreasing as expected in the far field zone. To define a global antenna gain K we simply compensate the free space losses in [START_REF] Padgett | The poynting vector in laguerre-gaussian laser modes[END_REF]. We obtain

K = P r P e × L F S (8)
The value of K is displayed for various mode orders in Fig. 7.

For an OAM mode l = 0, the gain K is constant in the far field, so that the link budget attenuation is only due to free space losses. In this case, K is asymptotically equal to G e G r . This is a classical result of link budget without OAM. This leads here to K(dB) = 10 log(N Tx × N Rx ) = 21.6 dB.

For a non-zero mode order (l = 0), the gain K is no longer constant and falls rapidly. The gains are dependent to D and l, which is obviously not a standard behavior.

Therefore, communications with a non-zero OAM order (l = 0) using the same type and size of transmitting and receiving antennas have a poor link budget because of its asymptotic behavior in the far-field.

Such a result has been predicted in [START_REF] Tamagnone | Comment on encoding many channels on the same frequency through radio vorticity: first experimental test[END_REF] for the special case l = 1 and for a 2 × 2 MIMO system. Indeed, in this case, the authors have demonstrated that both electric and magnetic fields have a 1/D 4 attenuation in power, different from the classical 1/D 2 attenuation.

Instead of deriving a general demonstration from [START_REF] Padgett | The poynting vector in laguerre-gaussian laser modes[END_REF], we here propose an a priori attenuation in 1/D 2l+2 . In order to test this hypothesis, Fig. 8 shows the evaluation of P r /P e × D 2l+2 .

We observe that the expression P r P e × D 2l+2 is asymptotically constant when D → ∞ for l = 0, 1, 2. Other values of l have been tested and present the same asymptotic behavior which validates this model for the power attenuation with the distance D. Besides, such a result is consistent with Tamagnone's conclusion for l = 1.

V. CONCLUSION

Applying conventional link budget theory for OAM monomode radio communication in a standard face-to-face configuration directly leads to zero received power due to zero antenna gains. A careful development of the non asymptotic link budget allows testing this conclusion as it has been done numerically in the present paper. A 1/D 2l+2 decrease is then observed. Unusually, this result depends on the modal order l and decreases faster than the standard 1/D 2 . A special attention has been paid on a progressive presentation of the results and interpretations considering the controversial context of this topic.

It could be of great interest to extend this study to other configuration, especially when antennas are not facing each other. Several cases like the ones shown in Fig. 9 could be investigated with the presented tool.

Fig. 1 .

 1 Fig. 1. Gain patterns of modes l = 0, 1, 2, 3.

Fig. 2 .

 2 Fig. 2. Standard configuration for the transmission of waves with non-zero OAM.

Fig. 3 .

 3 Fig. 3. Global configuration of the system with two circular arrays.

Fig. 4 .

 4 Fig. 4. Link schematic for OAM.

Fig. 5 .

 5 Fig. 5. Radiation pattern for a N Tx = 12 element array antenna and radius R Tx = λ. (From Mohammadi et al [9])

Fig. 6 .

 6 Fig.6. Link budget as a function of the distance and the mode order l.

Fig. 7 .

 7 Fig. 7. Mode to mode link gain K in dB.

Fig. 8 .

 8 Fig. 8. Test of the 1/D 2l+2 decreasing assumption.

Fig. 9 .

 9 Fig. 9. Possible configuration for the transmission of OAM waves with non-zero power for at least one of the antennas Tx/Rx.

Besides, once the propagation losses have been correctly removed from the link budget, the remaining coefficient could be studied for various antenna parameters, e.g. the array radii, the numbers of sources, the modal orders.

Furthermore, as for MIMO, an analysis based on a singular value decomposition (SVD) of the matrix (6) can be performed to decompose the link in terms of several orthogonal modes. They are given by the singular vectors. The mode-per-mode link budget is simply achieved by the squared singular values. This would also enable to express the MIMO capacity gain.

Note that, in the case where the two antennas are aligned and facing each other, Edfors [5] has demonstrated that singular vectors exactly correspond to OAM modes because H is a circulant matrix.

ACKNOWLEDGMENT

This work has been funded by both French CNES and DGA.


Gilles Simonin
email: gsimonin@laas.fr

Christian Artigues
email: artigues@laas.fr

Emmanuel Hébrard

Pierre Lopez
email: lopez@laas.fr

E Hebrard
email: hebrard@laas.fr

Scheduling scientific experiments for comet exploration

Keywords: global constraint, scheduling, data transfer, energy and memory constraints, space experiments

HAL is

Introduction

Following the fly-by of the comets Halley and Grigg-Skjellerup by the spacecraft Giotto, an even more ambitious mission, including the landing of a robotic module on the comet nucleus, was approved by European Space Agency in 1993. This project involves more than 50 contractors from 14 European countries, Canada and the United States for developing the instruments necessary to a deeper study of the comet. The Rosetta spacecraft, embarking these scientific instruments, was then launched in 2004 by Ariane 5, and was set to travel more than six billion kilometers to finally reach the comet 67P /Churyumov-Gerasimenko in November 2014. Its complex trajectory includes four gravity assist maneuvers (three times around Earth and once around Mars) before finally reaching the comet and entering its orbit. During its travel, the probe has met two asteroids (Steins and Lutetia), and collected data and pictures. Upon arrival at 67P , Rosetta will enter orbit around the comet and follow it on its journey towards the Sun. Finally, a lander module, called Philae, will then be deployed and attempt the first ever landing on the surface of a comet.

Philae features ten instruments, each developed by a European laboratory, to accomplish a given scientific experiment when approaching, or once landed on the comet. The instruments are designed to measure the molecular, mineralogical, and isotopic composition of the comet's surface and subsurface material, and also to measure characteristics of the nucleus such as near-surface strength, density, texture, porosity, ice phases and thermal properties. For instance, ÇIVA and ROLIS are two imaging instruments, used to take panoramic pictures of the comet and microscopic images, whilst the Alpha Proton X-ray Spectrometer (APXS) instrument analyzes the chemical composition of the landing site and its potential alteration during the comet's approach to the Sun. The obtained data will be used to characterize the surface of the comet, to determine the chemical composition of the dust component, and to compare the dust with known meteorite types.

The exploratory mission will have three phases. First, SDL (Separation-Descent-Landing) will run for 30 minutes during which many experiments will be run. Second, FSS (First Science Sequence) will last 5 days. This phase is critical because the execution of the most energetically greedy experiments requires battery power. The quality of the schedule conditions the longevity of the batteries and is therefore a key to the success of the mission. Finally, during the LTS phase (Long Term Science), scientific tasks will be resumed at a much slower pace, using the lander's own solar panels to partially reload the batteries. This phase will continue for months until the probe is destroyed due to the extreme temperatures of the Sun.

This project is a collaboration with CNES 1 in Toulouse (France) on the planning of the experimentation sequence on each of the three phases. The plans are elaborated on the ground at the Science Operations and Navigation Centre (SONC) in Toulouse. Many planning decisions rely on SONC's expert knowledge and are outside the scope of this paper. However, a set of scheduling decisions are modeled as a constraint program. A software (called MOST) has been developed on top of the Ilog-Scheduler/Solver library by an industrial subcontractor to solve this constraint program. In particular, constraints on the instruments energy usage, on data collection and transfers, as well as incompatibilities between experiments, have been implemented in this framework. Solutions are generated using classic depth-first search. Once they have been validated, these schedules are sent to the mission center located in Germany where they are encoded in the format expected by the Command and Data Management Systems (CDMS) onboard Rosetta and Philae. The communication delay to reach the spacecraft is roughly 25 minutes when approaching the comet. The CDMS can then execute the timed plan by triggering the different subsystems at the specified dates. It is important to mention that many parameters such as the orbital trajectory of Rosetta, which conditions the communication links with the lander Philae, will be known precisely only shortly before the landing. Currently, many different scenarios are solved and validated on the 1 Centre National d'Etudes Spatiales ground. However, the final and real plan will only be computed on yet partially unknown data, just a few days before being executed. This project has many similarities with the (interrupted) NetLander program [START_REF] Mancel | Complex optimization problems in space systems[END_REF].

The experiments of the FSS and LTS and the maneuvers of the SDL are modeled in MOST as a scheduling problem with two main types of resources.

First, the tasks within the experiments concurrently use the energy from a centralized source, mainly from batteries, and up to some extent from solar panels. There is an upper limit on the instant power that can be delivered to the experiments. Moreover, experiments are linked to the batteries through several power lines, themselves linked to a different converter. Each line and each converter entails another instant power threshold. Within MOST this is modeled as a hierarchy of CUMULATIVE constraints [START_REF] Aggoun | Extending CHIP in order to solve complex scheduling and placement problems[END_REF], one for the total instant power, one for each converter, and one for each line.

Second, each experiment produces data that must be transferred back to Earth. Each experiment has its own memory, collecting data as it is produced. This data is then transferred to a central mass-memory, then sent to Rosetta (the orbiter) when it is in visibility, i.e., above the horizon of the comet with respect to Philae. The orbiter thus acts as a relay and transfers the data to Earth (this also requires visibility between Rosetta and Earth2 ). All transfers from the experiments to the mass memory, and from the mass memory to the orbiter are executed (that is, computed onboard) by the CDMS following a greedy rule: priorities are assigned off-line to experiments. Then, on-line, data is systematically transferred from the experiment of highest priority with available data to the mass-memory, unless the mass-memory is full, in which case all transfers are blocked. This transfer policy may lead to data loss when an experiment produces more data than its memory can store and its priority is not high enough to allow a transfer to the mass-memory. This is modeled within MOST using RESERVOIR constraints [START_REF] Laborie | Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results[END_REF]. Data production tasks fill the reservoir, while multiple pre-defined data transfer tasks of variable duration empty it.

This modeling choice has several drawbacks and it quickly became apparent that it was the critical aspect of the problem to tackle in order to find better solutions faster. The first problem with this model is that data transfers are not accurately represented. For each experiment, a sequence of tasks standing for data transfers are pre-defined. Their duration is constrained so that the experiment with the highest priority is allowed to transfer as much as possible, and no overlap is allowed among transfers. In the current implementation there is a transfer task every 120 seconds over the horizon, with a maximum duration of 120 seconds. This is too few to accurately represent the policy of the CDMS, however, this is already too much for Ilog-Scheduler to handle (the planning horizon may be up to one day, i.e., about 700 transfer tasks for each experiment).

Instead we propose to encapsulate data transfers into a global constraint. The decision variables are start times of data-producing tasks (data-producing rate and duration are known in advance) and the priority permutation. This allows us to very quickly check the satisfiability of a schedule with respect to data transfer. Moreover, we can compute bounds allowing to filter out the domain of the variables standing for start time of the data-producing tasks. Unfortunately, enforcing arc consistency or even bounds consistency on this constraint is NP-hard, so we do not give a complete filtering al-gorithm. However, our approach reduces the solving time dramatically: from hours in some cases to seconds in all scenarios currently considered by the SONC. Moreover, the result is much more accurate, to the point that some scenarios for which MOST could not show that transfers were feasible can now be solved efficiently.

In Section 2, we briefly outline the energetic aspect of the problem and more formally define the data transfer aspect. Then, in Section 3 we introduce our approach to modeling data transfers. In particular, we formally define a new global constraint and oppose exact and approximate models to transfer blocks of data. In Section 4 we give an efficient satisfiability checking procedure and two filtering rules for the introduced global constraint. Last in Section 5, we report experimental results and compare results between old and new models.

Problem Description

Each experiment can be seen as a list of tasks to be scheduled. Disregarding data transfers, the problem can be seen as a scheduling problem over a set of experiments with relatively standard constraints.

Disjunctive resources: Each task of an experiment may require during its processing one or several instruments. Several tasks using the same instrument cannot be scheduled simultaneously, which corresponds to a standard disjunctive resource.

Precedences: Tasks within the same experiment might have precedence constraints; for instance the lander carries a Sampling Drilling and Distribution device (SD2 instrument), which will drill more than 20 cm into the surface, collect samples, and deposit them in different ovens, which are mounted on a circular and rotatable carousel. Four ovens of this carousel are dedicated to the Ptolemy instrument. With an appropriate sample loaded into one of the ovens, the carousel rotates to a position whereby a device referred to as a "tapping station" is used to connect the oven to the inlet of the gas management system of the Ptolemy instrument. At this point, the oven must be heated so that volatile samples are analyzed by Ptolemy. In this typical experiment, we have three tasks using three different instruments, each task preceding each other w.r.t. standard precedence constraints.

Cumulative Resources: Tasks within the experiments concurrently use energy from a centralized source, mainly from batteries and up to some extent from solar panels. All energy sources (batteries and solar panels) are centralized on a main power line (see Figure 1). The energy needed to run each task is supplied by an auxiliary power line. Each auxiliary line is linked to a converter, and each converter is linked to the main power line. At each level, the total instant power delivered cannot exceed a given threshold. For each auxiliary power line, all the tasks supplied by this line are constrained by a CUMULATIVE constraint [START_REF] Aggoun | Extending CHIP in order to solve complex scheduling and placement problems[END_REF] with capacity equal to this threshold. Similarly another CUMULATIVE constraint is associated to each converter, and a last one is associated to the main power line, involving all tasks of the problem. State Resources: In addition to instrument availability, which is modeled with a disjunctive constraint, each instrument can have multiple states along the schedule. Some tasks can trigger the modification of the state of an instrument, and the processing of certain tasks might be subject to some instruments having a given state. This is modeled using state resource constraints in Ilog-Scheduler.

Data Transfer and Memory Constraints: Every experiment has its own memory. Some tasks produce data, temporarily stored on the experiment's memory. Then this data will be transferred onto the mass-memory and subsequently to the orbiter. Note that for a given experiment, the precedence constraints between tasks are such that dataproducing tasks do not overlap. Therefore, at every time only one task of each experiment shall write in the experiment's memory.

The onboard CDMS controls all data transfers, from the experiments to the mass memory, and from the mass memory to the orbiter. Within a plan, experiments are (totally) ordered according to a priority function. Apart from this ordering, the CDMS is completely autonomous. It simply transfers data from the experiment with highest priority among those with transferable data. Moreover, it transfers data from the mass-memory to the orbiter whenever possible, that is, when there is some visibility. However, it does not ensure that all produced data will eventually be transferred to the orbiter. When too much data is produced simultaneously and not enough can be transferred on the mass-memory, or when there is no visibility with the orbiter and therefore the mass-memory cannot be emptied, the capacity of an experiment's memory may be overloaded and data is lost.

The Mars Express mission, launched in 2003 and still in operation, also featured a data transfer planning problem, similar to Rosetta's in many respects. In both cases, data-producing tasks are to be scheduled, data is kept into a number of memory storage devices on board and periodically transmitted to the Earth during visibility windows. However, a critical difference is that in Mars Express, the transfers are actually decisions to be made at the planning level. A flow model was proposed to address the so-called Memory Dumping Problem in [START_REF] Cesta | Mexar2: AI solves mission planner problems[END_REF][START_REF] Oddi | Improving robustness of spacecraft downlink schedules[END_REF] and further improved in [START_REF] Righini | A mathematical programming solution to the Mars Express memory dumping problem[END_REF]. In our case, however, the CDMS policy is given. To be more accurate, it is actually possible to change the experiments' priorities. However this cannot be done at any time since it corresponds to a global configuration change of the CDMS. Hence, only a few priority changes can be allowed in the planning horizon, which yields the need of considering the fixed priority case. When priorities are fixed, data loss can only be controlled through the schedule of data-producing tasks.

In other words, we shall consider data transfers as a global constraint on the start times of tasks ensuring that no data will be lost with respect to the CDMS policy.

A Global Constraint for Data Transfer

Except for data transfer, all the constraints above can be modeled using the standard methods and algorithms [START_REF] Baptiste | Constraint-Based Scheduling[END_REF], all available in Ilog-Scheduler. Hence, we focus on data transfers and propose a global constraint to reason about this particular aspect of the problem.

From now on, we consider a set {E 1 , . . . , E m } of m experiments. An experiment E k = {t k1 , . . . , t kn } is a set of data-producing tasks 3 , and is associated with a memory of capacity M k . A task t ki produces data for a duration p ki at a rate π ki in the experiment's memory. The lander possesses a mass memory of capacity M 0 , where data can be transferred from experiments.

The CDMS is given as input a priority ordering on experiments. For i ∈ [1, . . . , m], we denote by P (i) the index of the experiment coming at rank i in this ordering and its dual R(k) standing for the rank of experiment E k in the priority ordering (P (i) = k ⇔ R(k) = i). We shall say that experiment E k has higher priority than experiment

E j iff R(k) < R(j).
For reasons that will be explained later, the rate of the transfer from the experiment memory to the mass memory is not fixed and depends on three factors: (i) the number of active experiments, (ii) the relative priority of the experiment being transferred with respect to other active experiments, and (iii) the presence of a simultaneous transfer from the mass memory to the orbiter. An experiment is said to be active if its first task has already started and its last task has not finished, or if it has some data in memory. When there are simultaneous transfers to and from the mass-memory, the transfer rate from experiments is lower. These parameters are function of time, so we define a predicate τ (k,t) that gives the transfer rate from an experiment E k to mass-memory according to its priority, to the number of active experiments, and to the presence of a transfer to the orbiter at time t. However, transfers between mass-memory and the orbiter have a constant rate denoted by τ orbiter .

Data can only be transferred out to the orbiter when it is in visibility, that is, in the line of sight of the lander over the horizon of the comet. Visibility is represented as a set of intervals {[a 1 , b 1 ], . . . , [a v , b v ]} in the scheduling horizon, their lengths and frequencies depend on the chosen orbit. We shall use V (t) as a Boolean function which equals true iff time t is included in one of the visibility intervals. Moreover, data is transferred in and out memories by block units of 256 bytes. A data-producing task therefore entails as many transfer tasks as blocks of data it produces.

We consider the following decision variables: s 11 , . . . , s mn , with domain in [0, . . . , H], standing for the start times of data-producing tasks {t 11 , . . . , t mn }, respectively. The fact that data loss should be avoided can be seen as a relation (i.e., a constraint) between these decision variables. It is relatively easy to understand this relation procedurally since the CDMS policy is deterministic. Given a priority ordering and a fixed schedule of the data-producing tasks, one can unroll the rules outlined in Section 2 and further detailed in Section 3.1 to check whether the CDMS policy will lead to data loss or not.

First, in Section 3.1 we discuss an "exact" definition of this constraint based on following the transfer of each block of data individually. However, this formulation is not practical, so we propose an alternative model in Section 3.2. And finally, in Section 3.3 we study the worst case approximation error of this alternative model.

CDMS Policy

In this section, we detail the CDMS policy, then we define a constraint modeling the relation between the start time of data-producing tasks induced by this policy. Let m t k stand for the quantity of data in the memory of experiment E k at time t (with t ∈ R) and m t 0 be the quantity of data in the mass-memory. The CDMS transfers data by blocks of 256 bytes. Its policy is relatively simple and can be described using a simple automated earliest transfer scheduling algorithm (AETS). AETS runs the two following processes in parallel:

-Repeat: Scan experiments by order of priority until one with at least one block of data on its memory is found. In that case, transfer one block from this experiment to the mass memory unless the mass memory is full. -Repeat: If the orbiter is visible, and there is at least one block of data on the mass memory, then dump one block (transfer from the mass memory to the orbiter).

We can define the DATATRANSFER constraint as the relation allowing only assignments of start times and priorities such that given the CDMS policy (AETS), no block of data is produced while the memory of the experiment is full.

In order to specify this constraint as precisely as possible we would need to consider each block of data, and its associated transfer task, individually. More precisely, we need π ki p ki transfer tasks for each data-producing activity t ki (the production rate π ki is in blocks per second (blk/s) and the duration p ki is in seconds). The release time of the j th block's transfer task is s ki + j(1/π ki ), where s ki is the start time of t ki . Moreover, the start times and durations of these transfer tasks are functionally dependent on the start times of data-producing activities and experiment priorities. This dependence relation is a consequence of the AETS procedure. The time-dependent duration of the transfer tasks come from time-dependent transfer rates τ (k,t) . Blocks are actually transferred from experiments memories to the mass memory at a constant rate. However, when seeking which experiment to transfer from, the length of the scanning process depends on the number of active experiments and on the priority of the experiment eventually selected. An experiment E k is active between the start of its first task and the end time of its last task, or if the experiment memory is not empty. The transfer rate is thus larger in practice for the higher priority experiments as they are scanned first. Furthermore, transfers from the experiment memory are slower when there are simultaneous transfers from the mass memory to the orbiter. To emulate this, we use variable transfer rates. The transfer rate τ (k,t) in blocks per second (blk/s) is actually read in a table (τ observed k,x,y,z ), which entries were measured experimentally and give the transfer rate for experiment k depending on the number x of active experiments, on its relative priority y among them and on the Boolean presence z of a transfer to the orbiter, at the considered time t.

More precisely,

τ (k,t) = τ observed k,|X(t)|,y(k,t),z(t)
, where the set of active experiments at time t is defined by:

X(t) = {k | ∃i, s ki ≤ t ≤ s ki + p ki ∨ m t k > 0}
The relative priority of experiment k at time t is defined by:

y(k, t) = |{k ′ ∈ X(t)|R(k ′ ) ≤ R(k)}|
The presence of a transfer to the orbiter is defined by

z(t) = V (t) ∧ m t 0 > 0
It can be easily checked that y(k, t) ∈ {1, . . . , |X(t)|}. However, it has been somewhat counterintuitively observed that the transfer rate between mass-memory and the orbiter can be considered constant (denoted by τ orbiter ).

We can define a constraint DATATRANSFER([s 11 , . . . , s mn ]) ensuring that the schedule of tasks {t 11 , . . . , t mn } is such that no data is lost according to the CDMS rule described above.

Such an "exact" formulation would not be practical, as considering the transfer of each block of data would be too difficult. Therefore, we propose an alternative model in the next section. The basic idea is to represent all the data produced by a task as a continuous quantity.

Approximated Definition

We have seen that it is difficult to capture very precisely the behavior of the CDMS. When we consider a data-producing task in isolation, the number and frequency of the transfer tasks is easy to compute. However, when we consider several data-producing tasks with different priorities and unknown start times, this viewpoint becomes impractical. We therefore propose an alternative model that approximates very closely the amount of transferred data with a reasonable time and space complexity.

The basic idea is to consider data produced by a task as continuous quantity. This idea is straightforward in the case where experiments fully use the transfer bus. Indeed, consider a task t ki that produces more data than it can transfer: τ (k,t) ≤ π ki , with τ (k,t) the transfer rate at time t from an experiment E k to mass-memory. Suppose first that there is no task with higher priority. The transfer can be seen as a continuous task of duration π ki p ki τ (k,t) . It is therefore easy to compute how the usage of the memory will be impacted by this transfer. However, when taking into consideration priorities, variable transfer, and production rates, it becomes significantly more complex. We list here three difficulties.

First, as explained in the previous section, we have time-dependent transfer rates τ (k,t) (from the experiment to the mass memory) due to the scanning process of the AETS procedure.

Second, transfer tasks can be interrupted, however, they are different from classic preemptive tasks in that we do not decide when the interruption occurs. When an experiment with higher priority starts producing data, it preempts any current transfer of lower priority. This is the unique context where an interruption can happen. If there is no experiment with higher priority to interrupt the transfer, the usage of the experiment's memory increases at rate π ki -τ (k,t) during p ki seconds. Similarly, during π ki p ki τ (k,t) seconds the usage of the mass memory increases at rate τ (k,t) .

The third difficulty concerns tasks producing data at a lower rate than the possible transfer rate (i.e., τ (k,t) > π ki ). In this case, data is transferred one block at a time, with a lag between each transfer to wait for the next block to be produced (see Figure 2). Other tasks of lower priority with non-empty memory can use these gaps to begin the transfer of a block of data. In other words, the duration of the transfer of highest priority is still very close to π ki p ki τ (k,t) seconds, however other transfers can be squeezed in that same period. In order to simulate this, we consider that the data bus has a capacity (bandwidth) normalized to 1. The demand of a task t ki at time t is min(r, π ki τ (k,t) ), where r stands for the remaining bandwidth. Bandwidth is allocated recursively, according to this demand function and to priority (see Figure 3).

In other words, we approximate the "vertical" partition of the data bus shown in Figure 3 (exact transfers) by a "horizontal" partition, i.e., we consider that the bus has a bandwidth that can be divided over parallel transfers.

We shall see that this model allows us to represent memory usage very precisely, with a computational complexity independent on the time horizon and on the amount of data produced.

We can now formally define the constraint which is satisfied if and only if data production tasks are scheduled such that the approximated view of the CDMS policy would not entail data loss.

) ⇔ ∀t, k, π t k = π ki if ∃i s.t. s ki ≤ t ≤ s ki + p ki 0 otherwise (1) ∀t, k, p(τ t k ) =    0 if m t 0 = M 0 τ (k,t) if m t 0 < M 0 ∧ m t k > 0 min(π t k , τ (k,t) ) otherwise (2) ∀t, k, τ t k = min(p(τ t k ), τ (k,t) (1 - R(k)-1 i=1 τ t P (i) τ (P (i),t) )) (3) ∀t, k, m t k = t 0 (π t k -τ t k )dt (4) ∀t, m t 0 = t 0 ( m k=1 τ t k -V (t)τ orbiter )dt (5) ∀t, k, m t k ≤ M k (6)
Equation 1 states that if a data-producing task t ki is running at time t, then the dataproducing rate π t k of an experiment k at that time is equal to the data-producing rate of t ki , and it is null otherwise.

Equation 2 defines the potential transfer rate p(τ t k ) of experiment E k at time t if it is not trumped by other experiments of higher priority. The first case corresponds to a a full mass memory. When this happens, all transfers are stopped, hence the potential transfer rate is null. The second case corresponds to the transfer of data hold on the experimental memory. In this case, it can be transferred at the maximum available rate (τ (k,t) ). The last case corresponds to data being transferred as soon as it is produced. In this case, the experimental memory is empty (m t k = 0) and will remain so, if the production rate is smaller than or equal to the possible transfer rate (π t k ≤ τ (k,t) ). Otherwise, data will build up onto the experiment memory, and will be transferred at rate τ (k,t) .

Equation [START_REF] Beldiceanu | Sweep as a generic pruning technique applied to the non-overlapping rectangles constraint[END_REF] gives the real transfer rate (in the approximation scheme), that is, taking into account experiments with higher priorities. The experiment with highest priority uses the bandwidth proportionally to the ratio between its potential transfer rate p(τ t k ) and the maximum transfer rate τ (k,t) . Then the residual bandwidth is assigned using recursively the same rule.

Finally, Equations ( 4) and ( 5) link the usage of the different memories to the sum of the in and out transfer rates (π k and τ k are used here as functions of t) while Equations [START_REF] Mancel | Complex optimization problems in space systems[END_REF] ensure that memory capacity is never exceeded.

Figure 4 illustrates the difference between the two models on a small example with two tasks t 1 and t 2 such that t 2 has higher priority.

Exact transfer (t1) Exact transfer (t2) production (t1) production (t2) Fig. 4: Comparison of the two representations: two data-producing tasks t 1 and t 2 (bottom); The "exact" view of the corresponding transfers, sharing the transfer bus because of gaps due to the low data-producing rate (middle); The alternative reformulation, where this is modeled as sharing the bandwidth (top).

Approximation Error

Here we study the worst case approximation error of the "bandwidth" model. We shall refer to the "real" behavior of the CMDS as the exact model, whereas the formulation given in Definition 1 shall be referred to as the approximate model. Let m t k be the load of the memory of experiment E k in the exact model, and let m t k ′ be the load of the memory of experiment E k in the approximate model. We denote by

∆ t k = m t k -m t k ′
the discrepancy between the two models. We will show that for all values of t and k, the absolute error |∆ t k | is bounded by 1 + α, where α is the maximum ratio between two transfer rates in the transfer matrix τ observed , for a fixed number of active experiments. Usually, the difference in transfer rates comes from side effects of the CDMS policy and is close to 1.

In order to simplify the proofs, we will use the following notation: π k (resp. τ k ) for π t k (resp. τ t k ) when the rates are constant over time, and simply π (resp. τ ) when there is no ambiguity. We first consider the case of a single experiment, then the general case.

Single experiment:

Theorem 1. If only one experiment is active, the absolute error is bounded by 1 (|∆ t 1 | ≤ 1). Proof. Without loss of generality, we suppose that the considered data production task starts at time 0. There are two cases:

either π > τ .

Since the transfer starts at time 0 in the approximate model and 1/π in the exact model (this is the time required to produce the first block of data), the error ∆ t 1 is equal to 1 for t = 1/π. Now, since the transfer rates are equal to τ in both the exact and approximate models, we have

∆ t 1 ≤ 1, ∀t ≥ 1/π.
or π ≤ τ .

In the exact model we have a sequence of transfers at rate τ with start times equal to i π where i is a positive integer (see Figure 5). In the approximate model, however, data transfer starts at time 0 at a fixed rate equal to π. In the time interval [0, 1/π], the value of ∆ t 1 will therefore increase linearly from 0 to 1. Then, in the interval [1/π, 1/π+1/τ ], ∆ t 1 decreases from 1 to π τ . Finally, in the interval [1/π+1/τ, 2/π], it increases from π τ up to 1. We can observe that there is a cyclic pattern and thus we have a maximum error of |∆ Observe that one could propose a slightly different model where the transfer of the data produced by an experiment E k starts after 1/π k seconds, that is, the time it requires to produce the first block of data. By doing this, the error in the simplest case (single experiment and π k > τ k ) would be reduced to 0. However, if a high producing task directly follows a smaller producer of the same experiments, the delay on the first transfer is larger than on the second transfer. This situation may entail an overlap between the two transfers, making this idea very difficult to implement for a very small theoretical gain.

General case:

When multiple experiments are active simultaneously, the analysis is more complex. Consider Figure 6. In this example, we have two experiments E 1 and E 2 such that E 1 has higher priority than E 2 . Moreover, we suppose that at time t 2 = 1/π 1 + 1/τ 1 (i.e., when the transfer of the first block produced by E 1 ends), E 2 has at least one block of data in memory. Since the transfer channel is free, E 2 will start transferring a block. However, the duration of this transfer may be longer than 1/π 1 . Moreover, the transfer of a single block cannot be interrupted. Therefore, the transfer of the next block of data from E 1 might be delayed beyond the expected date 2/π 1 . Figure 6 illustrates such a case, where the transfer of the second block produced by E 1 is delayed to

t 3 = 1 π1 + 1 τ1 + 1 τ2 .

Results:

We consider a sequence of experiments E 1 , . . . , E m ordered by decreasing priority. Let α = τ1 τm be the highest ratio of transfer rates for these experiments (experiments with lower priority have lower transfer rates). We analyze the error for the experiment with highest priority. Indeed, the type of disruption described above only comes from the interaction with experiments of lower priorities. Moreover, experiments of lower priorities use the gaps left by the experiment of higher priority. Therefore, accuracy on the latter implies accuracy on the former. Last, we restrict our analysis to the case where the production rate π is lower than the transfer rate τ . Indeed, otherwise the experiment fully uses the bandwidth, and the behavior described above does not happen.

Theorem 2. If several experiments are active, the absolute error is bounded by

1 + α (|∆ t 1 | ≤ 1 + α).
Exact Transfer Data Production

Approx Transfer

Legend: Proof. As in the previous proof, we first consider the period of transfer of the first block of E 1 , starting at time 1 π1 and ending at time 1 π1 + 1 τ1 . At time 1 π1 + 1 τ1 , experiments of lower priorities might have data in their memory and hence start transferring. However, observe that as soon as the transfer of the block in process at time 2 π1 ends, experiment E 1 will take precedence since it has the highest priority. Therefore, the maximum delay is the size of the transfer of this block. Let E k be the experiment that produced this data block. We can analyze the value of

π 1 = τ 1 = 0.25 blk/s 1 π 2 π 3 π 4 π Exp 1 Exp 2 t 5 t 4 t 3 t 2 t 1 α ∆ t
∆ t 1 = m t 1 -m t 1
′ for any t. First, observe that since π 1 < τ 1 , data is transferred in and out of m t 1 ′ at the same rate. Consequently, we have m t 1 ′ = 0 for all t until the start of another data production task. In other words, we bound the value of m t 1 = ∆ t 1 . At time t 1 = 1/π 1 , we have m t1 1 = 1 and it will then decrease to π 1 /τ 1 at time t 2 = 1/π 1 + 1/τ 1 (i.e., m t2 1 ≤ 1). Now, over the interval

[t 2 , t 3 ] = [1/π 1 + 1/τ 1 , 1/π 1 + 1/τ 1 + 1/τ k ]
, experiment E 1 produces data at rate π 1 during 1/τ k seconds, and does not transfer any block out. The memory load will therefore increase by π 1 /τ k during this period. Since we have π 1 < τ 1 , we can bound this value by τ 1 /τ k ≤ α. In other words, ∆ t3 1 = m t3 1 ≤ 1 + α. Subsequently, since E 1 has the highest priority, it will transfer its data onto the mass memory at rate τ 1 until strictly less than one block is left its memory. It follows that m t 1 will decrease linearly over an interval [t 3 , t 4 ] with m t4 1 < 1. Now we can use a recursive argument: the delay due to the transfer of an experiment of lower priority will increase the usage of the memory of E 1 by at most α, starting from a value smaller than 1. Therefore we have

∆ t 1 = m t 1 ≤ 1 + α for all t. ⊓ ⊔
In theory, the transfer rate should be a constant, and therefore we should have α = 1. However, in practice, the observed transfer rates fluctuate with respect to the number of simultaneously active experiments, the relative priority of each experiment, and the presence of simultaneous transfers to the orbiter. This is due to the CDMS scanning procedure, as explained in Section 3.1. Table 1 illustrates typical observed transfer rates for a set of five experiments. The third column gives the transfer rates from experiments to the mass memory. We can see that the highest value of α will be 3.85/2.0 = 1.925 for 5 active experiments. It follows that our model will emulate the state of the memories with an error of less than 3 blocks of data in this case.

Checking and Filtering Algorithms

In this section, we introduce a filtering procedure for the DATATRANSFER constraint.

Observe that the DATATRANSFER constraint is NP-complete to satisfy, hence NPhard to filter. Indeed, consider the particular case where memory capacities are all of exactly one block of data, mass-memory is unlimited, and production rates are equal to transfer rates. Since the capacities are all equal to one block, each block produced must be immediately transferred. Moreover, since production and transfer rates are equal, a transfer will stop exactly when production stops. However, since there is a single transfer channel to the mass-memory, no overlap is possible between these tasks. Since we have time windows on the variables s ki , this particular case is therefore equivalent to a disjunctive unary resource, i.e., it is strongly NP-hard. It follows that achieving arc-or even bound-consistency on the exact or approximated version of the constraint would be NP-hard. We shall therefore propose two filtering rules, that are correct, however incomplete (with respect to bound-or arc-consistency).

We first present an efficient O(nm log(nm)) (recall that nm is the total number of tasks) procedure for computing transfers and memory usage of a given schedule. This procedure executes a sweep of the horizon similar to that described in [START_REF] Beldiceanu | Sweep as a generic pruning technique applied to the non-overlapping rectangles constraint[END_REF]. Besides checking whether the constraint is violated, we shall also use this algorithm to compute lower bounds in order to filter the domains.

Data Transfer Verification

Given a complete schedule of the data-producing tasks, and a priority ordering, we now describe an algorithm that computes the effective transfer rate (in the sense of Definition 1) and the memory usage for each experiment over the whole horizon in time O(nm log(nm)). Notice that both are step functions, moreover we will see that there are at most O(nm) breaking points, so they can be stored on O(nm) bits. This algorithm can be used to verify whether an assignment is consistent by simply checking that the usage of all experiments remains within the memory's capacity. We shall also use it to compute bounds on the memory usage of extreme scenarios (e.g., all tasks set to their earliest start time). It sweeps the time horizon chronologically, computing variations of various parameters only when certain events occur.

First, we build a list of events. Each event is time tagged. There are six types of "static" events, i.e., that are known before executing the sweep procedure (for O(nm) events in total):

-Start/end of an experiment; -Start/end of a data-producing task; -Start/end of visibility.

Moreover, "dynamic" events will be created and inserted while executing the sweep. Those events correspond to deadlines due to the memory capacity. In other words, outside the events above, the conditions might change if an experiment memory is emptied (in which case, a transfer might stop or continue at the production rate), or if the mass memory is filled or emptied. We call these Deadline events.

We first sort the events in chronological order. Next, in the main loop we explore the list of events in that order. For each time point t where at least one event occurs, we go through all events occurring at t and update the following arrays accordingly:

visibility stands for whether there is a visibility line at time t. It is flipped whenever encountering a "Start of visibility" or "End of visibility" event; -production(k) stands for the data-producing rate of experiment E k at time t. It is increased (resp. decreased) by the data-producing rate of the task whenever encountering a "Start of production" (resp. "End of production") event; -active stands for the number of active experiments at time t. It is increased (resp. decreased) by one whenever encountering a "Start of experiment" (resp. "End of experiment") event.

At each step of the loop, we therefore know the complete state (data-producing rate on each experiment, whether we are in visibility or not, and how many experiments are active). Moreover, we also keep track of the memory usage with another array: memory. We then compute what are the current transfers, and partition the bandwidth between them using the principle described in Section 3.2.

For each experiment E k (visited by order of priority), if it has data on memory, or if it is currently producing data, and if the bandwidth is not zero, we create a transfer. We first compute its potential transfer rate p(τ (k,t) ) according to Expression (2) and setting t to the event time. We then compute the actual transfer rate τ t k using Expression (3). These computations can be done in O(1) for each experiment as the cumulative bandwidth usage

R(k)-1 i=1 τ t P (i)
τ (P (i),t) is computed incrementally. Then, for each experiment currently in transfer, we compute a theoretical deadline, i.e., the date at which it will be emptied at this rate of transfer if nothing changes. Notice that it can be never. Similarly, we compute a theoretical deadline for filling the massmemory. If the earliest of all these deadlines happens earlier than the next scheduled event, we create a dynamic Deadline event and we add it to the list of events. Events of this type will do nothing on their own, however, they will allow the algorithm to recompute the transfers according to the new situation (the mass-memory being filled, or an experiment's memory being empty).

Finally, the usage of each memory at time t is updated according to the transfers.

This algorithm has a worst case time complexity of O(nm log(nm)). The list of events has initially O(nm) elements. There are two for each data-producing task, two for each visibility window, and two for each experiment (we assume that the number of visibility windows is less than nm). Sorting them can therefore be done in O(nm log nm) time. In the main loop, events are processed only once, and this takes at most O(m) time. Moreover, in some cases, "deadline" events can be added during the exploration of the event list. However, at most one such event can be added for each event initially in the list. Indeed, consider a deadline event. It is created only if no other event yet to process has an earlier date. In other words, transfer and data-producing rates as well as visibility do not change. The experiment memory that was emptied will therefore stay empty at least until the next standard event. The same is true for deadline event triggered by filled mass-memory: it will stay full at least until the next visibility event. Therefore, the worst case time complexity of the main loop is O(nm).

Filtering Rules

In this section we introduce two propagation rules for the DATATRANSFER constraint.

Minimal transfer span:

The first rule tries to guess a lower bound on the total span of a subset of tasks of the same experiment E k . The intuition is that if data is produced at a higher rate than it can be transferred out, the capacity of a memory could be reached and data will be lost. In other words, given a set Ω ⊆ E k of data-producing tasks of an experiment E k , the total amount of data produced by these tasks, minus what can be stored on the memory of E k , need to be transferred out. The duration of this transfer is a lower bound on the span of this set of tasks, i.e., the duration between the minimum start time and maximum end time of any task in this set.

The total amount of data produced by tasks in Ω is equal to t ki ∈Ω π ki p ki . At most M k can be stored on the experiment's own memory, hence at least t ki ∈Ω π ki p ki -M k has to be transferred out before the end of the last data-producing task. Let τ be the highest possible transfer rate for data out of the experiment's own memory. We can use this rate to derive a lower bound on the total duration of Ω:

max t ki ∈Ω (e ki ) -min t ki ∈Ω (s ki ) ≥ t ki ∈Ω π ki p ki -M k τ (7)
Observe that if we set the experiment's memory M k to 0 and all production and transfer rates to 1, then enforcing constraint [START_REF] Oddi | Improving robustness of spacecraft downlink schedules[END_REF] on all subsets of tasks of a given experiment is equivalent to forbid overlaps between tasks. Indeed, let t ki and t kj be two tasks of duration p ki and p kj , respectively. Constraint (7) guarantees a duration of at least p ki + p kj between the start of the first and the end of the second task. In other words, if we can schedule tasks so that this constraint is satisfied on each subset, then no two task may overlap. In the other direction, if we can schedule a set of tasks without overlaps, then the makespan for this set of tasks is at least the sum of the tasks' durations, hence Constraint [START_REF] Oddi | Improving robustness of spacecraft downlink schedules[END_REF] would be satisfied on this set. It shows that computing tight bounds satisfying Constraint ( 7) on all subsets Ω of tasks in a given experiment is NP-hard since we have time-window constraints (that is, feasible bounds for each task). We shall therefore apply this rule only for subsets of tasks that are consecutive when ordered by earliest start time (so that only a polynomial number of subsets is checked), and independently for each such subset.

In real scenarios, however, the order of data-producing tasks of a given experiment is often known a priori. Assuming that the tasks in Ω are ordered, with t kf being the first task and t kl being the last task in Ω, we can often induce the simpler constraint:

e kl -s kf ≥ t ki ∈Ω π ki p ki -M k τ
Example 1. Figure 7 depicts the application of this rule. For an experiment k, we have two tasks t k1 , t k2 , the former producing π k1 = 5 blocks/sec and the latter π k2 = 4 blocks/sec, both for 70 seconds. Therefore, π k1 p k1 +π k2 p k2 = 630 blocks are produced. Assume that the memory of this experiment has a capacity of 250 blocks. Consequently, 380 blocks need to be transferred out in order to avoid data loss. Since the maximum transfer rate is 2 blocks/sec, this transfer will take at least 190 seconds. We can conclude that the end of t k2 is at least 190 seconds after the start of t k1 . The grey scale gives the evolution of the memory for t k2 finishing exactly 190 seconds after the start of t k1 .

Moreover, we can take into account the data produced by tasks of experiments with higher priority, since the corresponding data transfer will preempt those of lower priority.

Consider an interval of time

min (|t ki ∩ [a, b]|) = min (|[a, b] ∩ [min(s ki ), min(s ki ) + p ki ]|, |[a, b] ∩ [max(s ki ), max(s ki ) + p ki ]|)
We can compute a lower bound T k (a, b) on the time required to transfer the data produced by experiments of higher priority than k over the interval [a, b] as a lower bound on the data produced, divided by the maximum transfer rate:

T k (a, b) =   j<R(k) j=1 n i=1 |t P (j)i ∩ [a, b]| * π P (j)i   τ
Given a subset Ω ⊆ E k of experiment E k , consider the time interval [a, b] between the latest start time of any task in Ω (a = max t ki ∈Ω (min(s ki ))) and the earliest end time of any task in Ω (b = min t ki ∈Ω (max(s ki ) + p ki )). The lower bound on the span given above assumes continuity of the transfer, and by definition this duration must include the interval [a, b]. Therefore, any interruption of the transfer during this period induces the same delay on the minimal span of Ω. In other words, any time taken to transfer data of experiments with higher priority during [a, b] (T k (a, b)) can be simply added to the lower bound above.

Hence we can tighten Constraint (7) as follows (with a = max t ki ∈Ω (min(s ki )) and b = min t ki ∈Ω (max(s ki ) + p ki )):

max t ki ∈Ω (e ki ) -min t ki ∈Ω (s ki ) ≥ t ki ∈Ω π ki p ki -M k τ + T k (a, b) (8)
We apply this rule for every set of consecutive tasks (with respect to their earliest start times) of every experiment. There are n 2 m such sets, and computing the lower bound takes at most O(nm) time. The whole procedure hence has a worst case time complexity of O(n 3 m 2 ).

Mass memory saturation: Since transfers from the lander to the orbiter are possible only during some visibility windows, the data can only accumulate on the mass-memory while not in visibility. As a consequence, the period that precedes a visibility window is critical since the mass memory can be saturated hence blocking all transfers. When this happens, data produced by an experiment remains on its memory at least until the next visibility window, and it is possible to lose data when the experiment's memory itself is saturated.

We use this observation to deduce that data-producing tasks which would generate too much data to hold on the mass memory and on their own memory should be either advanced or postponed. Suppose that we know that at time t, the mass-memory will necessarily be filled. It will remain so until the next visibility. Now, if a task t ki produces more data in the interval between t and the next visibility window than its own memory can hold, it will be lost. Indeed, no data can be transferred onto the mass-memory as long as it is full, and it will start to be emptied only when the visibility allows it. We can therefore deduce that the task t ki must start either early enough to produce before t or late enough so that the data in excess will be produced during the visibility period (in order to have a chance to be transferred).

First, we show how to compute an upper bound t on the time when the massmemory will reach its maximum before a given visibility window. We consider a single visibility cycle V = (a, v, b), where a < v < b denote, respectively, the end of the previous cycle, the start of a visibility window, and the end of that visibility window. Let Ω(V) be the set of data-producing tasks that are necessarily scheduled within the interval [a, b].

Proposition 1. Scheduling all data-producing tasks in Ω(V) to their latest start time minimizes the memory usage of the mass-memory (m t 0 ) for all t ∈ [a, b]. Proof (sketch). Clearly if we consider a data-producing task t ki in isolation, setting its start time to the latest possible time point (max(s ki )) delays the transfer onto the mass memory hence its memory usage for any time point in [a, b].

When multiple data-producing tasks can run in parallel, experiments of high priority can preempt transfer intervals of experiment of lower priority. Therefore, one could advance a data-producing task t jl in time in order to use the resource and therefore delay the transfer of some of the data produced by t ki . However, since the transfer rate increases with the priority, for any time interval where the transfer of the data produced by t jl preempts that produced by t ki , data is being transferred to the mass memory at a higher rate. Thus, advancing a data-producing task t ji of higher priority never helps minimizing the mass memory usage.

⊓ ⊔

Given a visibility cycle V = (a, v, b), we can therefore get a lower bound on m t 0 on the usage of the mass memory for any t in the interval [a, b] using the sweep algorithm. For every task in Ω(V), we tentatively fix it to its latest start time and execute the sweep algorithm. Hence, we can easily compute t, the smallest value of t for which m t 0 = m v 0 . Given an experiment E k , we can bound the amount of data that can be produced by any task of this experiment in the period [t, v] and stored without loss. There are m t 0 blocks of data already on the mass-memory, so M 0 -m t 0 is free. Moreover, up to M k can be stored on the experiment's own memory, for a total of δ k = M 0 + M k -m t blocks. Above this threshold, data produced by tasks of experiment E k between t and v will be lost. If |t ki ∩ [t, v]| stands for the length of the overlap between a task t ki and the interval [t, v], a task t ki produces |t ki ∩ [t, v]| * π ki blocks of data in the interval [t, v]. Therefore, the following relation must hold:

n i=1 min(|t ki ∩ [t, v]|) * π ki ≤ δ k
from which we can deduce the following implied constraint:

|t ki ∩ [t, v]| ≤   δ k - j =i∈[1,n] (min(|t kj ∩ [t, v]|) * π kj )   π ki (9)
We run the sweep algorithm once to obtain the value of t. Then, for each experiment, we can compute δ k and in time O(n) the values of min(|t kj ∩ [t, v]| for each task t ki . Finally we compute the implied constraint also in time O(n) (it takes constant time for each task, once min(|t kj ∩ [t, v]| is known). Finally we apply it only when it collapses to a simple lower or upper bound on the start time s ki of a task t ki . The total time complexity of this filtering rule is thus O(nm log(nm) + nm) = O(nm log(nm)).

Experimental Results

All the previous algorithms and filtering rules have been implemented on the latest version of MOST. We conducted experiments on different scenarios provided by the SONC group of CNES. Each scenario consists in several experiments of the SDL or FSS which must be scheduled on a time window between 10 hours and 5 days for the longest scenario. On the last three scenarios, we search a valid solution for either or both of the two experimental sequences SDL and FSS, albeit with in a macroscopic view.

For each subset of experiments, several variations are tested in order to assess uncertain parameters. For instance, the visibility cycle depends on the exact mass and shape of the comet, the orbit selected by Rosetta, and the landing site chosen for Philae, all of which are unknown at this time. Some scenarios have continuous visibility, while other have different periods for the visibility cycles. The hardware onboard the probe will have travelled in extreme temperatures for ten years, so the exact charge and efficiency of the batteries is also uncertain. Moreover, engineers of SONC test a range of variations on other parameters such as the memory capacity simply to stress-test the system (MOST).

Search Effort

We ran 13 scenarios and compared the results of the current version of MOST against the ad-hoc propagator introduced in this paper. Both versions were run on quad-core Sun T 5120 running Solaris 2.10 with 8 GB of RAM. The current version of MOST (denoted by MOST+ILCRESERVOIR) models data transfers using Ilog-Scheduler ILCRESERVOIR constraints. Our version is denoted by MOST+DATATRANSFER.In both cases, we used the same default search strategy. Interval variables standing for activities are explored in chronological order of their earliest start times, and we branch by assigning them to this earliest start time. Indeed, SONC's engineers prefer rather simple strategies which make the solver choices more foreseeable and hence the solutions easier to validate. Moreover, we shall see that because of the constrainedness of the implemented scenarios, no real search is required provided a sufficiently strong filtering on data transfers.

We report the results in Table 2. We present for each scenario the set of experiments involved, the memory capacities, and whether the visibility is periodic (P) or continuous (C). Then we give the number of fails calculated by Ilog-Scheduler during search, the initialization time, and finally the solving time.

We observe first that using our approach, solutions can be obtained backtrack-free, whereas the previous model actually needs to branch on the variables standing for transfer durations and therefore requires exploring a sizeable search tree. The reformulation using ILCRESERVOIR constraints was indeed very loose, and did not allow to detect inconsistencies early. Moreover, to overcome this weakness, the scenarios produced by the SONC group are overly constrained in order to cut possibilities and allow the solver to converge more easily. Finally, our propagator is relatively light and therefore more time effective, compared to the model using a large amount of transfer tasks throughout the horizon for each reservoir constraint.

In fact, the previous model was so large that the initialization time is very high. The few seconds of initialization time in our approach correspond to the rest of the model (cumulative and unary resources), which is common to both implementations.

In two cases (Consert/Romap scenarios), no solution was found by MOST+ILCRESERVOIR within the time cutoff. However, this is not explained (only) by performance issues. In fact, these two scenarios do not have a valid solution under the old model, whereas they are feasible.

Our model significantly reduces the search effort with respect to the previous approach. In fact, all scenarios used by SONC's engineers are solved backtrack-free using our method, even if we use a "minimal" version of the constraint. In this version we simply check, whenever the start time of a new task is fixed, whether the DATATRANSFER constraint is violated. It shows that the search effort observed on the previous model was devoted to compute a transfer policy which is in fact functionally dependent on the schedule of producing tasks. However, since the real parameters will only be fully known days before launching Philae, and will probably be revised after its landing, it is important to be robust and consider even scenarios that may not seem realistic now. We therefore manually tweaked the instance "Overview FSS" in two ways. First, we gave more flexibility to the tasks in order to increase the potential search space. Second, we decreased some memories and increased some production rates so that the filtering rules are more likely to be triggered. We ran four versions of our approach on these harder instances. The first does not do any filtering and simply checks the DATATRANSFER constraint after each assignment. The other three versions use the first (1), the second (2) or both filtering rules (1 & 2).

We report the results in Table 3 for three instances obtained as described above. The best results appear in bold. We observe that the first filtering rule actually does reduce the search effort significantly on these instances. However, the second filtering rule was not able to effectively prune on any of the modified instances. Although we can generate toy instances where the second filtering rule is triggered, this is not the case for the considered set of real scenarios.

Model Accuracy

In the model MOST+ILCRESERVOIR, tasks with very low data-producing rates are treated differently because of rounding issues: It is assumed that the data is produced all at once at the end of the task. Therefore in these scenarios, transfers can be delayed by a substantial amount compared to the real behavior of the CDMS.

Moreover, since transfer tasks have a frequency of 120 seconds, they cannot accurately model situations where the CDMS frequently switches between different transfers. Scenarios Consert/Romap highlight this problem on SONC's version of MOST. Both experiments have small data-producing tasks and small memory capacities. Therefore, switches between transfers from these two experiments are extremely frequent. Fig. 8: Example of MOST+ILCRESERVOIR However, with MOST+ILCRESERVOIR it is not possible to switch frequently enough since data-transfer tasks are preallocated every 120 seconds on the time line. As a result, the model using the ILCRESERVOIR constraint has no solution, whereas transfers are actually possible.

Figure 8 is a screenshot of the MOST's GUI showing a zoom on a plan (a solution) of the scenario SD2/Ptolemy. The bottom bars represents the transfer of Ptolemy, and the bars just above are data-producing tasks. We can see that the transfer task does not coincide with the data-producing task. Indeed there is a gap, because data-producing rate is too low to trigger a transfer task earlier.

These results show that our model is closer to the real case, because our approximate representation of data transfers gives a solution very similar to the exact one. One of the most important improvements of our version is the precision and the realism of our model; we accurately model the behavior of the CDMS.

Conclusions

The problem of planning the scientific experiments to be undertaken by the lander Philae can be modeled as a task scheduling problem with additional constraints to ensure that no data is lost. In this paper, we have introduced a new model for managing data transfers, relying essentially on the global constraint DATATRANSFER. This new approach improves the previous methods in two ways.

First, data transfers do not need to be discretized. Whereas, in the previous model, predefined "transfer tasks" of a given size were used to represent data transfer, we showed that they can be efficiently approximated. One key idea was the observation that the exclusive usage of the transfer channel and the priority rule of the transfer policy could actually be simulated by a bandwidth-sharing model. We have proven that the approximation error with respect to the real transfer policy is fixed and extremely small compared to the large amount of data being transferred. This approach therefore provides a much higher level of precision in the evolution of the memory usage, hence a greater confidence that the proposed plans will not entail any data loss.

Second, this new approach also greatly reduced the computational cost for solving the overall planning problem. We proposed an efficient sweep-based method to check the feasibility of data transfers and compute memory usage through time. Thanks to this algorithm, scenarios that required several hours of computation with the previous model can now be solved in a few seconds.

Although such exploration missions are extremely rare, from a constraint programming viewpoint, there are several lessons to be learned from this study. First, such data transfer problems are common in space applications, for instance for Earth observation satellites. Moreover, there are other scenarios where we want to model continuous or very finely grained quantities produced by activities requiring an exclusive resource shared through a fixed policy. For instance in a logistics problem, we might have a set of suppliers sending orders to a set of customers through a common transportation resource. In such cases, the sharing policy should be either impartial, or dependent on the premiums paid by the suppliers or customers. In either case, it is fixed externally and our approach of modeling an exclusive resource with some fine grained sharing policy by a bandwidth model would apply. Other potential examples concern makespan minimization in project scheduling with inventory constraints including both renewable and storage resources, reliability and quality of service in wireless sensor networks that require collecting all data without any loss, or spatio-temporal resolution of operational data in pipeline infrastructures and time/bandwidth complex sharing policies in frequency allocation problems.

Moreover, if we consider even more general situations where a potentially very complex system is functionally dependent on a schedule, a sweep-based algorithm seems to be a very robust approach. It has a low time complexity, and can easily be adapted to model even very complex systems. For instance, in our case, there are aspects that we voluntarily did not cover in this paper, as they have little "computer scientific" interest, whilst making the presentation much more complex. Direct transfers from experiment memory to the orbiter when the mass memory is empty, or dedicated partition and allocation of the mass memory to each experiment are such additional features. Even though some of these changes were brought up after the basic algorithm had been implemented, the sweep architecture was relatively easy to adapt, for instance by introducing new types of events. Finally, we proposed two filtering rules for the constraint DATATRANSFER. Unfortunately, the scenarios generated by SONC's engineers are solved with almost no failure when using this new constraint. Therefore, the impact of the two filtering algorithms is difficult to assert. We can observe an improvement when relaxing the domains and restricting the memory capacities, however only from the first filtering rule. Moreover, our experimental evaluation indicates that with the previous approach search was necessary to handle data transfers. With our approach, however, it seems relatively easy to schedule the experiments in such a way that there is no data loss. So far, we have not seen a real scenario that would be hard when using the DATATRANSFER constraint.

Fig. 1 :

 1 Fig. 1: Illustration of the global power system

Productionπ 1 τFig. 2 :Fig. 3 :

 123 Fig. 2: Exact transfer model

t 1 | ≤ 1 Fig. 5 :

 115 Fig. 5: Value of discrepancy of memory usage ∆ t 1 when π ≤ p(τ ) (single experiment)

Fig. 6 :

 6 Fig. 6: Value of discrepancy of memory usage ∆ t 1 when π ≤ p(τ ) (multiple experiments)

π k2 = 4 tFig. 7 :

 47 Fig. 7: Example of minimal span constraint.

  Let π t k stand for the data-producing rate on experiment E k at time t, let p(τ t k ) stand for the potential transfer rate of experiment E k at time t if it was of highest priority, and let τ t k stand for the actual (approximate) transfer rate from experiment E k to the mass memory at time t.

	Definition 1.
	DATATRANSFER(s 11 , . . . , s mn

Table 1 :

 1 Variable transfer rates

	Nb. Exp. x Priority y τ observed k,x,y,0 τ observed k,x,y,1
	1	1	6.14	3.77
	2	1	5.36	3.99
	2	2	4.74	4.09
	3	1	4.74	4.09
	3	2	4.28	3.77
	3	3	3.80	3.45
	4	1	4.31	4.09
	4	2	3.88	3.55
	4	3	3.46	3.08
	4	4	3.10	2.37
	5	1	3.90	3.85
	5	2	3.48	3.30
	5	3	3.06	2.80
	5	4	2.80	2.30
	5	5	2.65	2.00

Table 2 :

 2 Old vs. new version of MOST on 8 standard scenarios

	Scenario	Parameters	MOST+ILCRESERVOIR MOST+DATATRANSFER
		M k	M0 Visi.	Fails	time (s) init. search	Fails	time (s) init. search
	Consert	500	17456 P	295	4.06	20.07	0 0.88	0.08
	Consert/Romap	500/250	17456 P	7112 11.13 Time out	0 1.17	0.10
	Consert/Romap	500/250	37456 P	7051 11.03 Time out	0 1.17	0.10
	SD2/Ptolemy	64/2000	17456 P	234 26.71	41.72	0 3.37	0.09
	SD2/Ptolemy	64/2000	17456 C	211 32.78	79.48	0 3.25	0.08
	SD2/Cosac/Civa	64/24000/4000 37456 P	407 50.20	181.91	0 2.75	0.14
	SD2/Cosac/Civa	64/24000/4000 17456 P	413 50.84	179.19	0 2.95	0.15
	SD2/Cosac/Civa	64/24000/4000 17456 C	390 25.12	91.08	0 1.82	0.10
	APXS/Sesame	125/2000	17456 P	44 27.74	28.53	0	3.5	0.19
	SD2/Ptolemy/Cosac/ Mupus/Sesame	64/2000/24000/ 17456 P 750/1750	1657 265.45 1639.33	0 21.14	6.71
	Overview FSS (10 exps)		17456 P	591 125.69	565.09	0 2.12	0.49
	SDL 30min (8 exps)		17456 P	1145 14.94	20.52	0 9.47	0.23
	SDL 360min + FSS (15 exps) macro vision		17456 P 44201 217.09 10801.40	0 4.44	1.20

Table 3 :

 3 Impact of the Filtering Algorithms

	Scenario DATATRANSFER DATATRANSFER(1) DATATRANSFER(2) DATATRANSFER(1 & 2)
	Fails time (s) Fails	time (s)	Fails	time (s)	Fails	time (s)
	Overview A 569	49	569	54	569	65	569	68
	Overview B 2143	102	516	30	2143	99	516	54
	Overview C 3278	170	1651	99	3278	257	1651	149

Nasa and Russian relays are used to cover the whole surface.

To simplify the notations, we assume that all experiments have the same number of tasks. This is of course not the case; however it does not affect the methods we introduce.

Acknowledgements

This work has been supported by CNES. We would like to thank members of the Science Operations and Navigation Centre (SONC) in Toulouse for their invaluable input.