Anne-Marie Tobie Tésa
email: anne-marie.tobie@recherche.enac.fr

Axel Garcia-Pena
email: garcia-pena@recherche.enac.fr

Paul Thevenon
email: thevenon@recherche.enac.fr

Processed 5G Signals Mathematical Models for Positioning considering a Non-Constant Propagation Channel

Keywords: 5G systems, CIR, correlator outputs, DLL, GNSS, OFDM, propagation channel, QuaDRiGa

The objective of this paper is to determine the ranging performance of the upcoming fifth generation (5G) signal. In order to do so, it is required to define 5G correlator outputs mathematical models. 5G systems will use OFDM (Orthogonal Frequency Division Multiplexing) signals; in the literature, mathematical models of OFDM signals are developed at the different receiver signal processing stages. These models assumed that the propagation channel is constant over an OFDM symbol; nevertheless, an in-depth study of QuaDRiGa, a 5G compliant propagation channel simulator, invalidates this hypothesis. Therefore, in this paper, mathematical models are developed that take into account the channel evolution. The focus is given on correlator outputs and results are applied to the computation of 5G based pseudo range accuracy.

INTRODUCTION I.

Over the past few years, the need for positioning, and thus the number of positioning services in general, has been in constant growth. This need for positioning has been increasingly focused on constraint environments, such as urban or indoor environments, where GNSS (Global Navigation Satellite System) is known to have significant limitations: multipath as well as the lack of Line-of-Sight satellite visibility degrades the GNSS positioning solution and makes it unsuitable for some urban or indoor applications. In order to improve the GNSS positioning performance in constrained environments, many solutions are already available: hybridization with additional sensors or the use of signals of opportunity for example, [START_REF] Shamaei | Exploiting LTE Signals for Navigation: Theory to Implementation[END_REF], [START_REF] Mensing | Synchronization algorithms for positioning with OFDM communciations signals[END_REF], [START_REF] Mensing | Positioning with OFDM based communications systems and GNSS in critical scenarios[END_REF], [START_REF] Thevenon | Positioning using mobile TV based on DVB-SH standard[END_REF]. Concerning signals of opportunity, mobile communication signals, such as the 4G LTE ( [START_REF] Shamaei | Exploiting LTE Signals for Navigation: Theory to Implementation[END_REF]) or 5G, are naturally envisioned. Indeed, a significant number of users are expected to be "connected-users" and 5G systems offers promising opportunities.

5G technology is being currently standardized and its positioning performance, as well as a potential generic receiver scheme to conduct positioning operations, is still under analysis. In order to develop such a positioning module, it is of the utmost importance to correctly characterize the mathematical models of the processed 5G signals at each stage of the receiver: the knowledge of these mathematical models will allow for the development of signal processing algorithms optimally adapted to the 5G received signal.

Previous efforts have been made to provide the mathematical model of the 5G received signal at the different receiver signal processing stages. For example, taking into account that, as defined in 3GPP standard, 5G systems use Orthogonal Frequency Division Multiplexing (OFDM) signals, the OFDM signal-type correlator output mathematical model and acquisition techniques derived in [START_REF] Mensing | Synchronization algorithms for positioning with OFDM communciations signals[END_REF], [START_REF] Mensing | Positioning with OFDM based communications systems and GNSS in critical scenarios[END_REF], [START_REF] Staudinger | A generic OFDM based TDoA positioning testbed with interference mitigation for subsample delay estimation[END_REF], [START_REF] Thevenon | Positioning using mobile TV based on DVB-SH standard[END_REF], [START_REF] Serant | Development and validation of an OFDM/DVB-T sensor for positioning[END_REF] could be applicable to 5G signals. Moreover, in [START_REF] Serant | Development and validation of an OFDM/DVB-T sensor for positioning[END_REF], tracking and acquisition techniques were proposed, analyzed and tested based on the correlator output mathematical model presented in [START_REF] Thevenon | Positioning using mobile TV based on DVB-SH standard[END_REF]. However, this model was derived by assuming a constant propagation channel over the duration of the correlation (which is performed over one OFDM symbol). Nevertheless, an analysis conducted on the Channel Impulse Response (CIR) of a representative 5G signals propagation channel, QuaDRiGa [START_REF] Jaeckel | QuaDRiGa: A 3-D Multicell Channel Model with Time Evolution for Enabling Virtual Field Trials[END_REF], has shown that the CIR cannot be considered as constant over the duration of the correlation. Moreover, this analysis has also shown that the expected 5G signal processing behavior is different between a time-evolving CIR and a constant one over the duration of an OFDM symbol.

This article aims thus at extending the DVB-T signals ranging module (Delay Lock Loop -DLL) presented in [START_REF] Thevenon | Positioning using mobile TV based on DVB-SH standard[END_REF] for constant CIR propagation channels to a 5G signals ranging module (DLL) for time-evolving CIR propagation channels. The key point of this derivation consists in developing an evolved mathematical model for 5G signals correlator outputs which takes into account the CIR evolution over the duration of one OFDM symbol.

In order to meet this objective, the article is organized in 8 sections in addition to the introduction and conclusion. First, 5G signals structure and a generic communication chain scheme are presented. Second, the architecture of the envisioned DLL based on [START_REF] Serant | Development and validation of an OFDM/DVB-T sensor for positioning[END_REF] is presented for an AWGN. Third, the correlation operation in AWGN is presented. Fourth, the correlator output operation is defined, and its mathematical model is developed and validated for a CIR constant over the duration of the correlation. Fifth, the model for a time-evolving CIR is derived. Sixth, the correlator output mathematical model is developed and validated for a time-evolving CIR. Seventh, the 5G signals compliant propagation channel being adopted, QuaDRiGa, [START_REF] Jaeckel | QuaDRiGa: A 3-D Multicell Channel Model with Time Evolution for Enabling Virtual Field Trials[END_REF] is presented. Finally, the code delay tracking error of the derived 5G signal tracking module is provided for an AWGN channel and for the QuaDRiGa propagation channel model. The OFDM signal is then transmitted through the propagation channel, which CIR mathematical model is usually expressed as 𝛼 𝑘 (𝑡) . The received signal mathematical model can then be expressed by the convolution between the incoming signal and the previously defined CIR propagation channel, where 𝑟 𝑘 (𝑡) expresses the noiseless received signal before the ADC/AGC.

𝑟 𝑘 (𝑡) = 𝑠 𝑘 (𝑡) * 𝛼 𝑘 (𝑡) (2) The CP is removed from this received signal, and finally, the signal is demodulated using a Fast Fourier Transform (FFT).

ENVISIONED 5G RANGING MODULE III.

The main objective of this article is to design a 5G signal ranging module performing the time-of-arrival estimation thanks to a Delay-Lock Loop (DLL). The aim of the ranging module is thus to estimate the transmitted signal propagation delay 𝜏 between the 5G emitter and receiver. The selected generic DLL diagram block scheme is illustrated in Fig2, [START_REF] Shamaei | Exploiting LTE Signals for Navigation: Theory to Implementation[END_REF], [START_REF] Serant | Development and validation of an OFDM/DVB-T sensor for positioning[END_REF]; this scheme is adapted for an AWGN channel. The tracking step provided by Fig. 2 is preceded by an acquisition step. The acquisition process consists in using algorithms such as the Van de Beek algorithm, [START_REF] Van De Beek | ML estimation of Time and Frequency Offset in OFDM Systems[END_REF], followed by the matching pursuit, presented in [START_REF] Serant | Development and validation of an OFDM/DVB-T sensor for positioning[END_REF], to achieve a rough time and frequency synchronization with the incoming signal. The tracking (fine estimation) of the rough estimated propagation delays obtained during the acquisition phase is then conducted by the DLL.

The DLL makes use of correlation between the incoming signal, 𝑟 𝑘 [𝑛]. and a local replica, 𝐿𝑅, performed on the pilot symbols that are present in the 5G Synchronization Signals. The CIR mathematical model of an AWGN channel can be expressed as 𝛼 𝑘 (𝑡) = 𝛼𝛿(𝑡 -𝜏), where 𝛼 is the complex amplitude of the AWGN propagation channel and 𝜏 is the propagation time delay, The noiseless received signal mathematical model can then be derived from the convolution between the incoming signal and this CIR propagation channel as: 𝑟 𝑘 (𝑡) = 𝑠 𝑘 (𝑡) * 𝛼 𝑘 (𝑡). the digital version, 𝑟 𝑘 [𝑛], is provided in [START_REF] Mensing | Positioning with OFDM based communications systems and GNSS in critical scenarios[END_REF].

𝑟 𝑘 [𝑛] = 𝛼 ∑ 𝑑 𝑝 𝑘 𝑒 𝑖2𝜋𝑝(𝑛-𝜏 𝑛 ) 𝑁 𝐹𝐹𝑇 𝑁 𝐹𝐹𝑇 -1 𝑝=0 (3)
The propagation delay estimated by the DLL is denoted as 𝜏. The correlation between the incoming signal and the local replica is computed at three points spaced by a distance 𝑑 called the correlator spacing (d=4 samples in the following). Where 𝜀 𝜏 = 𝜏 -𝜏̂ is defined as the propagation delay estimation error. The discriminator output is then computed thanks to these 3 correlator outputs. The discriminator chosen is the Early Minus Late Power (EMLP) defined in (4) and studied in [START_REF] Serant | Development and validation of an OFDM/DVB-T sensor for positioning[END_REF]:

𝐷 𝐸𝑀𝐿𝑃 𝑛𝑜𝑟𝑚 (𝜀 𝜏 ) = |𝑅 𝐸 (𝜀 𝜏 )| 2 -|𝑅 𝐿 (𝜀 𝜏 )| 2 𝐾 𝑛𝑜𝑟𝑚 |𝑅 𝑃 (𝜀 𝜏 )| 2 (4)
This discriminator is normalized by 𝐾 𝑛𝑜𝑟𝑚 such that 𝐷 𝐸𝑀𝐿𝑃 𝑛𝑜𝑟𝑚 (𝜀 𝜏 ) = 𝜀 𝜏 for 𝜀 𝜏 close to 0, its expression is derived in [START_REF] Serant | Development and validation of an OFDM/DVB-T sensor for positioning[END_REF]. The discriminator output is then filtered by a low-pass filter. The new delay estimate is then generated using a DCO (Digitally Controlled Oscillator) and new Early, Prompt and Late correlator outputs are computed. Finally, the correlation operation is the basis of the ranging module as shown in this section. Therefore, the correct mathematical modelling of its output is mandatory in order to develop a ranging module adapted to the targeted propagation channel. This modelling will be the aim of the next sections.

CORRELATION OPERATION DEFINITION IV.

The correlation operation can be defined for an OFDM symbol from its direct time-domain expression or from the equivalent frequency-domain expression. The schemes of the time-domain and frequency-domain correlation operations are given in Fig. 3. In the time domain, the incoming signal is multiplied with the local replica, and then accumulated (integration and dump) to get the correlation result. In the frequency domain, the incoming signal is first demodulated thanks to a FFT operation and then it is multiplied with the FFT of the local replica. Then, an iFFT is performed in order to come back to the time domain. Only the first term of the iFFT output is considered and denominated as "IFFT in 0" in Fig. 3.

Additionally, note that the received signal is also demodulated by applying a FFT as presented in (5) when 𝜏 𝑛𝑝 ′ 𝑁 𝐹𝐹𝑇 [START_REF] Thevenon | Positioning using mobile TV based on DVB-SH standard[END_REF] With such expressions it is easier to tune the shifting process in the frequency domain. Therefore, the correlator output mathematical model is derived from this implementation, i.e. the FFT in the frequency domain.

CORRELATOR OUTPUT MATHEMATICAL MODEL FOR A V.

CONSTANT CIR OVER ONE OFDM SYMBOL In this section, the correlator output mathematical model is derived for a constant CIR over one OFDM symbol. A more general propagation channel CIR mathematical model is now expressed as follow 𝛼 𝑘 (𝑡) = ∑ 𝛼 𝑙 𝑘 𝛿(𝑡 -𝜏 𝑙 )

𝐿-1 𝑙=0

. Where 𝛼 𝑙 𝑘 is the complex amplitude of the 𝑘 𝑡ℎ OFDM time symbol and the 𝑙 𝑡ℎ path, 𝜏 𝑙 is the delay of the 𝑙 𝑡ℎ multipath, 𝐿 is the total number of multipath and 𝑙 is the multipath id. The noiseless received digital signal mathematical model 𝑟 𝑘 [𝑛] is provided in [START_REF] Serant | Development and validation of an OFDM/DVB-T sensor for positioning[END_REF].

𝑟 𝑘 [𝑛] = ∑ 𝛼 𝑙 𝑘 ∑ 𝑑 𝑝 𝑘 𝑒 𝑖2𝜋𝑝(𝑛-𝜏 ̃𝑙) 𝑁 𝐹𝐹𝑇 𝑁 𝐹𝐹𝑇 -1 𝑝=0 𝐿-1 𝑙=0 (6)
Where 𝜏̃𝑙 = 𝜏 𝑙 /𝑇 𝑠 is the normalization of the continuous parameter by the sampling time 𝑇 𝑠 .

The correlation is performed on pilots only; the general correlation function expression is defined in [START_REF] Serant | Development and validation of an OFDM/DVB-T sensor for positioning[END_REF] as:

𝑅(𝜏) = 1 𝑁 𝑝 ∑ 𝑑 ̃𝑝 𝑘 𝐿𝑅 𝑝
𝑘 * 𝑝∈𝛲 [START_REF] Jaeckel | QuaDRiGa: A 3-D Multicell Channel Model with Time Evolution for Enabling Virtual Field Trials[END_REF] Where 𝐿𝑅 𝑝 𝑘 = 𝑝 𝑝 𝑘 𝑒 -2𝑖𝜋𝑝 𝑁 𝐹𝐹𝑇 𝜏 , 𝑝 𝑝 𝑘 is the pilot symbol localized in the 𝑝 𝑡ℎ subcarrier on the 𝑘 𝑡ℎ symbol. 𝑁 𝑝 is the number of pilot symbols and 𝑃 is the set of pilots. In order have a generic formula, the set of pilots 𝑃 can be defined as: 𝑃 = 𝛾𝑝 ′ + 𝛽. Where 𝛾 is the period of repetition of the pilots in the OFDM symbol, 𝑝 ′ ∈ [0 … 𝑁 𝑃 -1] and 𝛽 is the subcarrier index of the first pilot in the symbol. Applying this equation, the final expression of the correlator output is given in [START_REF]TS 38.211 Physical channels and modulation[END_REF] with 𝜀 𝜏 𝑙 = (𝜏 -𝜏 𝑙 ). The previously developed model assumes that the propagation channel model is constant over the duration of the OFDM symbol. In this section, the consequences of a non-constant propagation channel on the correlation function are presented.

For a time-evolving propagation channel model, the CIR is modelled as:

𝛼 𝑘 (𝑡, 𝜏) = ∑ 𝛼 𝑙 𝑘 (𝑡, 𝜏)

𝐿-1 𝑙=0

(9) The CIR, 𝛼 𝑙 𝑘 (𝑡, 𝜏), for a given received multipath can be expressed as follow:

𝛼 𝑘 (𝑡, 𝜏) = ∑ 𝛼 𝑙 𝑘 (𝑡) • 𝛿(𝜏 -𝜏 𝑙 )

𝐿-1 𝑙=0

(10) Where 𝜏 is a mathematical variable used for the convolution, 𝑡 is used to model the complex amplitude evolution of each multipath and 𝛼 𝑙 𝑘 (𝑡) is the evolving complex amplitude of the 𝑘 𝑡ℎ OFDM symbol and the 𝑙 𝑡ℎ multipath. Then, the received signal for the 𝑙 𝑡ℎ multipath is calculated as 𝑟(𝑡) = 𝛼 𝑙 𝑘 (𝑡) , then the convolution in the frequency domain will create a spectral broadening effect. This spectral broadening implies the loss of the orthogonality between the subcarriers of the OFDM signal. This process is illustrated in Fig. 4.

CORRELATOR OUTPUT MATHEMATICAL MODEL VII. FOR A NON-CONSTANT CIR OVER ONE OFDM SYMBOL

A. Correlator output mathematical model derivation

The previous correlator output formula, equation ( 8), was derived for a propagation channel constant over the duration of one OFDM symbol. However, in general, 5G signals propagation channels, cannot be considered as constant, e.g. QuaDRiGa [START_REF] Jaeckel | QuaDRiGa: A 3-D Multicell Channel Model with Time Evolution for Enabling Virtual Field Trials[END_REF]. In order to develop a correlator output mathematical model for a time-evolving propagation channel, the method used for a constant CIR was repeated. Equations ( 13) and ( 14) show the OFDM demodulated symbol and correlator output mathematical models:

𝑑 ̃𝑝 𝑘 = 𝑑 𝑝 𝑘 + 𝐼𝑛𝑡𝑒𝑟𝑓𝑒𝑟𝑒𝑛𝑐𝑒 (13) 𝑅(𝜀 𝜏 ) = 𝑅 𝑢𝑠𝑒𝑓𝑢𝑙 (𝜀 𝜏 ) + 𝑅 𝑖𝑛𝑡𝑒𝑟𝑓 (𝜀 𝜏 ) (14) It must be noted that the useful term, in (14), is different from the correlator output derived in (8) for a constant channel. Fig. 7 can help to understand the impact of the channel on a particular symbol 𝑘. For a constant channel, only one coefficient is considered for each path 𝑙 for each symbol 𝑘, 𝛼 𝑙 𝑘 (violet curve); while for an evolving channel, the impact of the 𝑙-th path on symbol 𝑘 is modelled by the , the values 𝛼 𝑙 𝑘 (𝑛) will be constant over period shorter than the OFDM symbol, and will therefore depend on the chosen CIR sampling rate. In Fig. 7, 3 different sampling rates are illustrated: 10, 20 and 100 CIR sps.

The statistics of the two terms, useful and interference, of the OFDM demodulated symbols as well as the correlator output mathematical model have been analyzed for QuaDRiGa channel (presented in next section). The study proves the negligibility of the interference term with respect to the useful term for this channel. Mathematical demonstrations are not provided here, nevertheless, in Fig. 5, an illustration is provided as a justification. Monte-Carlo simulations have been used to assess the amplitude of the useful and interference term of the correlation function for a CIR sampling rate of 100 CIR samples per symbol. On the left is presented the correlation main peak, on the middle the useful (up) and interference (bottom) terms and on the right, the useful and interference terms contributions; which are equal to 100.0048% and 0.0789% of the total correlation function respectively. The contribution is computed using: |𝑅 𝑢𝑠𝑒𝑓𝑢𝑙 (𝜀 𝜏 )|/|𝑅 𝑢𝑠𝑒𝑓𝑢𝑙 (𝜀 𝜏 ) + 𝑅 𝑖𝑛𝑡𝑒𝑟𝑓 (𝜀 𝜏 )| • 100 and |𝑅 𝑖𝑛𝑡𝑒𝑟𝑓 (𝜀 𝜏 )|/|𝑅 𝑢𝑠𝑒𝑓𝑢𝑙 (𝜀 𝜏 ) + 𝑅 𝑖𝑛𝑡𝑒𝑟𝑓 (𝜀 𝜏 )| • 100 respectively; this permits to understand that the interference term can be destructive, making the useful contribution higher than 100%. Therefore, the final model adopted is limited to 𝑅 𝑢𝑠𝑒𝑓𝑢𝑙 (𝜀 𝜏 ) which is defined in (15):

𝑅(𝜀 𝜏 ) ≈ 𝑅 𝑢𝑠𝑒𝑓𝑢𝑙 (𝜀 𝜏 ) = { ∑ 𝐴 𝑙 𝑘 (0) 𝑁 𝐹𝐹𝑇 𝑁 𝑃 𝐿-1 𝑙=0 𝑒 𝑖𝜋𝜀 𝜏 (2𝛽+𝛾(𝑁 𝑃 -1) 𝑁 𝐹𝐹𝑇 𝑠𝑖𝑛( 𝜋𝛾𝜀 𝜏 𝑁 𝑃 𝑁 𝐹𝐹𝑇 ) 𝑠𝑖𝑛( 𝜋𝛾 𝜀 𝜏 𝑁 𝐹𝐹𝑇 ) 𝜀 𝜏 ≠ 0 1 𝑁 𝐹𝐹𝑇 ∑ 𝐴 𝑙 𝑘 (0) 𝐿-1 𝑙=0 𝜀 𝜏 = 0 (15)

B. Simplified OFDM correlator output mathematical models for a non-constant CIR over one OFDM symbol

The correlator output mathematical model contains the sum 𝐴 𝑙 𝑘 (0) = ∑ 𝛼 𝑙 𝑘 (𝑛) 𝑁 𝐹𝐹𝑇 -1 𝑛=0

which contains the impact of the evolution of the propagation channel over one symbol for the l th multipath. The objective of this section is to simplify this term in order to further simplify the complete correlator output mathematical model. A potential application of this simplified model would be the implementation of a simulator; where the computational burden is an important factor that must not be forgotten.

In order to simplify 𝐴 𝑙 𝑘 (0), the following hypotheses are considered:  The sum of the complex amplitudes is split in two sums, the sum over the modulus and the sum over the phases:

∑ 𝛼 𝑙 𝑘 (𝑛) 𝑁 𝐹𝐹𝑇 -1 𝑛=0 ≈ (∑ |𝛼 𝑙 𝑘 (𝑛)| 𝑁 𝐹𝐹𝑇 -1 𝑛=0 ) ( ∑ 𝑒 𝑖𝜃(𝑛) 𝑁 𝐹𝐹𝑇 -1 𝑛=0 𝑁 𝐹𝐹𝑇 ) (16)
 The sum over the modulus is replaced by the mean value of the first modulus of the channel impulse response at the instants of the symbols k and k+1:

∑ |𝛼 l k (n)| N FFT -1 n=0 ≈ (|𝛼 l k (0)| + |𝛼 l k+1 (0)|)N FFT /2 (17)
 The phase variation is assumed linear over one symbol (this assumption has been verified through simulations):

𝜃(𝑛) = 𝜃 0 𝑘 + 2𝜋𝛿 𝑓 • 𝑛. Where 𝜃 0 𝑘 is the phase of the first propagation channel sample applied to the 𝑘 𝑡ℎ OFDM symbol and 𝛿 𝑓 = (𝜃 0 𝑘 -𝜃 0 𝑘+1 )/(2𝜋𝑁 𝐹𝐹𝑇 ) is the normalized Doppler frequency. This simplification would allow generating only 1 CIR sample per OFDM symbols instead of 𝑁 𝐶𝐼𝑅 CIR samples, which would greatly reduce the computation time of propagation channel models, e.g. QuaDRiGa. 𝑁 𝐶𝐼𝑅 represents the required number of CIR samples per OFDM symbol to obtain a propagation channel model equivalent to a time-continuous channel.

Finally, the channel contribution term can be simplified as presented in (18).

QUADRIGA: A 5G PROPAGATION CHANNEL VIII.

A. Presentation of the channel

In this article, the propagation channel selected to validate the correlator output mathematical models developed in the previous sections is the QuaDRiGa propagation channel, [START_REF] Jaeckel | QuaDRiGa: A 3-D Multicell Channel Model with Time Evolution for Enabling Virtual Field Trials[END_REF].

QuaDRiGa allows choosing between different scenarios representative of 5G signals propagation channel models. In this article, among the proposed configurations "3GPP_38.901_UMi_LOS" has been selected. This scenario models typical terrestrial pico-base stations deployed below rooftop in densely populated urban areas covering carrier frequencies from 500 MHz to 100GHz. The Line-Of-Sight (LOS) scenario is a favorable case; the LOS signal is received with significant higher power than multipath. Picobase stations have typically a 4-to-200m-radius-size; thus, the trajectory simulated is a few meter-long arc of a 100mradius circle. Finally, regarding the 5G signal characteristics, the carrier frequency used is set to 6GHz and the subcarrier is 15kHz.

B. Time-evolving CIR correlator output validation using

QuaDRiGa In order to validate the different correlator output mathematical models presented in section VII, the following method is applied. First, the correlation is computed over 2000 symbols for four cases: 1. the correlation operation using a sampling interval of 100 CIR samples per OFDM symbols (the reference), 2. the correlation operation using a sampling interval of 10 CIR samples per OFDM symbols, 3. the correlation using a sampling interval of 10 CIR samples per OFDM symbols using (15), and 4. the correlation using (18), using only 1 CIR sample per OFDM symbol. The correlation operation refers to the correlation obtain after performing the complete OFDM transmission chain of Fig. 1 (generation of OFDM symbol, modulation, CP addition, channel degradation, CP removal, demodulation, correlation). Second, the last three correlation output values are compared to the reference in terms of relative evolution (RE). Results are averaged with respect to the main correlation peak (right of Fig. 6) and with respect to the 2000 symbols (left of Fig. 6). Results are summarized in Table . 1 These results permit to validate the usage of the simplified correlator outputs mathematical model. Results obtained with the simplified model are even better than the two previous one. In order to understand this result, see Fig 7. This figure illustrates the method used to model the time evolution of the propagation channel over one OFDM symbol. Supposing that an OFDM symbol is composed of N signal samples and that X CIRs are applied, then over N/X samples, the applied channel coefficients are constant. It can be seen that the first complex amplitude of symbol k+1 is closer to the last complex amplitude applied to symbol k with the reference than the last complex amplitude of symbol k obtained with 10 CIR. It means that the complex amplitudes considered in the simplified model are closer to the reference, which explained the results.

APPLICATION OF THE CORRELATOR OUTPUT MODEL TO IX.

THE CODE DELAY TRACKING OF A 5G SIGNAL The correlator output mathematical model developed in the previous sections is applied to the code delay tracking of a 5G signal-type, defined in section III. The performances of the DLL are provided for 3 cases:

1. an AWGN channel, 2. a multipath channel and 3. a LOS channel.

The tracking performance is analyzed by calculating the variance of the estimated delay. In Fig. 8, the standard deviation of the tracking error estimate is provided in function of the SNR for an AWGN, for a multipath channel and for a channel composed of only a LOS signal. According to this study, the 5G ranging performance can provide sub-meter accuracy (3σ) for SNR as low as 0dB for the AWGN; this provides the optimal performances that can be reached. In red and yellow, the standard deviation is provided for a channel composed of only one LOS path; these curves are computed using the reference correlation (with 100 CIR sampling rate) and the simplified model from (18) respectively. In violet and green, a multipath channel is used; these curves are computed using the reference correlation (with 100 CIR sampling rate) and the simplified model from (18) respectively. Two conclusions can be made from this figure. First, the validity of the simplified model is proved. Second, due to the multipath, there is a threshold from which the precision of the DLL cannot be improved.

CONCLUSION

This article has proposed a 5G ranging module (DLL), using an EMPL discriminator, for non-constant over an OFDM symbol duration CIR propagation channels. This proposal has required the derivation of OFDM-type signal processing mathematical models for a time-evolving CIR of the different stages of a navigation receiver: OFDM demodulated symbols and correlator outputs.

The developed correlator output mathematical model was applied to a 5G pilots, using a realistic channel model (QuaDRiGa). The development of these mathematical models has been validated by comparing the tracking error standard deviation using the correlation model using 100 CIR sps and the simplified correlation model. These simulations show that the same performance is observed, even though the sampling of the channel model has been reduced by a factor 100.

Future work will now use the simplified correlator output model to implement a realistic simulator that will allow the evaluation of the 5G positioning performance and the development of innovative techniques to optimize the processing of such signal for positioning. The simplified correlator model could also be applied on the promising 5G mm-wave signals, which would have a different emitter network topology and signal characteristics, and where the channel characteristics evolve even more rapidly within an OFDM symbol duration.

  correlator output: 𝑅 𝐸 (𝜀 𝜏 )  𝜏̂ for the prompt correlator output: 𝑅 𝑃 (𝜀 𝜏 )  𝜏̂+ 𝑑 2 for the late correlator output: 𝑅 𝐿 (𝜀 𝜏 )

Fig. 1 -

 1 Fig. 1 -OFDM transmission and reception chain Fig. 2 DLL architecture

𝑅

  This formula has been validated using 5G pilots. After deep study of the 3GPP standard,[START_REF]TS 38.211 Physical channels and modulation[END_REF], only one set of pilots can be used since its scheme is the only one fixed and predictable: the 4-OFDM-symbol-long Synchronization Signal Physical Broadcast CHannel (SSPBCH). The detection and decoding of this block allow the user to achieve downlink synchronization in time/frequency domain and to obtain 5G signal characteristics such as the cell identity or the bandwidth; information required to perform the communication with the network. More specifically, in the following, the focus is done on the second (and fourth) symbol which are composed of 1 Demodulation Reference Signal (DMRS) each 4 subcarriers over 240 subcarriers: 𝑁 𝑝 = 60, 𝛾 = 4, 𝛽 = 0 in the following.MODEL OF A TIME-EVOLVING CIR VI.

Fig. 4 Fig

 4 Fig. 4 Impact of a non-constant propagation channel

Fig 5 .

 5 Fig 5. Negligibility of the interference term

Fig. 6

 6 Fig. 6 Validation of the simplified model

  Where 𝑁 𝐶𝑃 is the number of Cycle Prefix samples, 𝑁 𝐹𝐹𝑇 is the size of the FFT window, 𝑝 is the subcarrier, 𝑛 indicates the 𝑛 𝑡ℎ discrete time epoch, 𝑘 indicates the 𝑘 𝑡ℎ OFDM symbol, 𝑑 𝑝 𝑘 is the 𝑘 𝑡ℎ modulated symbol carried by the 𝑝 𝑡ℎ subcarrier.

	II.	5G SIGNAL PRESENTATION
	5G systems use OFDM signals. The process to
	generate an OFDM signal is illustrated in Fig.1. The
	symbols {𝑑 0 𝑘 , … , 𝑑 𝑁-1 𝑘	} are first modulated by applying an
	inverse Fast Fourier Transform (IFFT). Then the Cycle
	Prefix (CP) is added creating an OFDM time symbol. At
	this point the complex envelope signal model (consisting in
	one OFDM time symbol) can be expressed as in (1).
	𝑠 𝑘 [𝑛] = ∑ 𝑝=0 𝑁 𝐹𝐹𝑇 -1	𝑑 𝑝 𝑘 𝑒	𝑖2𝜋𝑝𝑛 𝑁 𝐹𝐹𝑇	-𝑁 𝐶𝑃 ≤ 𝑛 ≤ 𝑁 𝐹𝐹𝑇 -1 (1)

  • 𝛿(𝜏 -𝜏 𝑙 ) * 𝑠(𝜏)| 𝜏=𝑡 = 𝛼 𝑙 𝑘 (𝑡) • 𝑠(𝑡 -𝜏 𝑙 ) (11)

	Assuming for simplification purposes 𝜏 𝑙 = 0 , the
	received signal Fourier transform is equal to:
	𝑘 (𝑓) * 𝑆(𝑓) 𝑅(𝑓) = Α 𝑙 𝑘 (𝑡)]. If the propagation channel is (12) 𝑘 (𝑓) = 𝐹𝑇[𝛼 𝑙 Where Α 𝑙 constant over the duration of the correlation, 𝛼 𝑙 𝑘 , 𝑘 (𝑡) = 𝛼 𝑙 𝑘 (𝑓) is a periodic Dirac function. However, if the channel 𝐴 𝑙 evolves, 𝛼 𝑙 𝑘 (𝑡) ≠ 𝛼 𝑙 𝑘

TABLE 1 -

 1 RELATIVE EVOLUTION MEAN AND STANDARD DEVIATION

	Model	10CIR	Initial	Simplification
	μ	0.1267%	0.1379%	0.1016%
	σ	0.1178%	0.1237%	0.0866%


Marco Di Renzo
email: marco.direnzo@l2s.centralesupelec.fr

Spatial Modulation Based on Reconfigurable Antennas -A New

come

I. INTRODUCTION

The Internet of Things (IoT) can be broadly defined as the current commercial effort for integrating a wide variety of technical and commercial information-generating components to provide new business opportunities based upon device and system intelligence. A NATO Science and Technology Organisation (STO) task group was recently established to identify the potential military applications of the IoT (IST-147) and various potential areas have been identified and are currently under analysis [1]. This includes: 1) logistics -command and control of combined operations logistics support, 2) situational awareness -building on the tactical level of a battlefield (from global, to company, platoon and squad commanders down to single soldiers level) including monitoring, sensing, threat identification (e.g., sniper), target positioning, marking, vehicles and soldiers status monitoring, environmental monitoring (environment conditions), and 3) medical care -battlefield health monitoring, patients monitoring, etc.

In the context of IoT-based military and civilian applications, the so-called connected objects are expected to require more modest data rates, lower power consumption, and smaller form factors compared to those of typical mobile multi-media services. By contrast, they are expected to support higher data rates at a higher power consumption, and at a more bulky form factor compared to typical wireless sensor nodes. Hence, new air interface techniques have to be developed, which are capable of satisfying these new emerging requirements and of offering a better Spectral Efficiency (SE) vs. Energy Efficiency (EE) design flexibility. In this context, Multiple-Input-Multiple-Output (MIMO) techniques [START_REF] Di Renzo | GREENET -An early stage training network in enabling technologies for green radio[END_REF] are expected to provide the necessary design flexibility to meet these requirements. For emerging IoT applications, however, new MIMO paradigms are necessary. Why?

The capacity of MIMO systems is proportional to min{N t , N r }, where N t and N r represent the number of transmit and receive antennas. This implies that the throughput may be increased linearly with the number of antennas. As a consequence, MIMO techniques can provide high data rates without any bandwidth-expansion and without increasing the transmit power [START_REF] Di Renzo | Spatial modulation for multiple-antenna wireless systems: A survey[END_REF]. However, in practice, conventional MIMO systems rely on a multiplicity of independent circuits for each available antenna element, such as power amplifiers, RF frontends, mixers, synthesizers, filters, etc., which substantially increase the circuit power dissipation of all network elements. It is known, in particular, that the power amplifiers dissipate the majority of the power consumed in current cellular base stations [START_REF] Stavridis | An energy saving base station employing spatial modulation[END_REF]. Recent studies, in fact, have proved that the EE gain of MIMO transmission increases with the number of antennas, provided that only the transmit power is taken into account and that their circuit power dissipation is neglected. On the other hand, the EE gain of MIMO transmission remains modest and decreases with the number of active transmit antennas, if realistic power consumption models are considered [START_REF] Stavridis | Energy evaluation of spatial modulation at a multi-antenna base station[END_REF]. These results highlight that, at the time of writing, the design of energy efficient and low-complexity MIMO transmission schemes is an open research issue, especially in the context of IoT applications.

In this context, the design of MIMO transmission schemes that exploit fewer RF chains compared to the number of available radiating elements is currently emerging as a promising research field [START_REF] Di Renzo | Spatial modulation for multiple-antenna wireless systems: A survey[END_REF]. Usually, this family of MIMO designs is referred to as single-RF MIMO. Suffice to say, however, that there are also various compromise-schemes, which rely on diverse antenna selection schemes, where a specific subset of the antennas is activated, which determines the number of RFchains that is needed. Hence, in parlance, we can refer to these schemes as single-RF, full-RF and few-RF arrangements.

Why having fewer RF chains than radiating elements is beneficial for designing spectral-and energy-efficient MIMO schemes? The fundamental idea behind the few-RF MIMO concept is to attain spatial multiplexing and/or transmit-diversity gains with the aid of many antenna-elements, where only a subset of them -or possibly just a single antennaelement -is activated at the transmitter at any modulation instant. The rationale behind the full-RF to few-RF paradigm shift in MIMO design originates from the consideration that multiple transmit antennas (radiating elements) may be accommodated at both the transmitters and receivers, bearing in mind that the complexity and power consumption/dissipation of MIMO transmission is mainly determined by the number of simultaneously active transmit antennas, i.e., by the number of RF chains [START_REF] Di Renzo | Spatial modulation for multiple-antenna wireless systems: A survey[END_REF].

Fueled by these considerations, Spatial Modulation (SM) has recently established itself as a promising transmission concept, which belongs to the few-RF MIMO wireless system family, whilst exploiting the availability of multiple antennas in a novel fashion compared to state-of-the-art highcomplexity and power-hungry classic MIMO systems [START_REF] Di Renzo | Spatial modulation for multiple-antenna wireless systems: A survey[END_REF]. In simple terms, SM can be regarded as a MIMO concept that possesses a larger set of radiating elements than the number of transmit-electronics chains. SM-MIMO takes advantage of the entire antenna-array at the transmitter, whilst using a limited number of RF chains. The main distinguishing feature of SM-MIMO is that it maps additional information bits onto a "SM constellation diagram", where each constellation element is constituted by either a single antenna-element or a subset of antenna-elements. These unique characteristics result in high-rate MIMO implementations relying on a reduced signal processing and circuit complexity, as well as an improved EE. Recent analytical and simulation studies have shown that SM-MIMO has the inherent potential of outperforming many stateof-the-art MIMO schemes under the fair assumption that the number of RF chains is the same [START_REF] Di Renzo | Bit error probability of space shift keying MIMO over multiple-access independent fading channels[END_REF]- [START_REF] Lu | Performance analysis of spatial modulation MIMO in a Poisson field of interferers[END_REF]. Readers interested in further information on SM-MIMO systems are invited to consult recently published and comprehensive survey papers [START_REF] Di Renzo | Spatial modulation for generalized MIMO: Challenges, opportunities and implementation[END_REF]- [START_REF] Di Renzo | Spatial modulation for multiple-antenna communication[END_REF]. It is worth mentioning that the SM-MIMO concept was recently validated via experimental activities [START_REF] Younis | Performance of spatial modulation using measured real-world channels[END_REF] and was successfully implemented in a testbed platform [START_REF] Serafimovski | Practical implementation of spatial modulation[END_REF]. SM-MIMO is one of the proposed technologies for next-generation communication systems [START_REF]White paper for research beyond 5G[END_REF].

In this paper, we will first review the basic principle of SM-MIMO and will then describe a new air interface that synergistically combines SM and RecAnts for application to the IoT, aiming to the design of medium-throughput, lowcomplexity and energy-efficient communication systems that are specifically tailored to meet the requirements of the connected objects for military and civilian applications [START_REF]Modulation spatiale et antenne reconfigurable pour connecter en haut debit des capteurs mobiles et autonomes en energie[END_REF].

II. CONVENTIONAL SPATIAL MODULATION

A. How It Works

In this section, we introduce the SM-MIMO concept with the aid of simple examples. We denote by N t and N r the number of Transmit Antennas (TAs) and Receive Antennas (RAs), respectively. The cardinality of the signal-constellation diagram is denoted by M . Either Phase Shift Keying (PSK) or Quadrature Amplitude Modulation (QAM) are considered. In general, N t , N r and M can be chosen independently of each other. At the receiver, Maximum-Likelihood (ML-) optimum demodulation is considered. Thus, N r can be chosen independently of N t [START_REF] Di Renzo | Spatial modulation for multiple-antenna communication[END_REF]. For ease of presentation, we assume N t = 2 nt and M = 2 m with n t and m being two positive integers. For ease of illustration, a single RF chain is available at the transmitter (single-RF MIMO).

In Fig. 1, the SM-MIMO concept is illustrated for N t = M = 2 and is compared to Spatial Multiplexing (SMX) and Orthogonal Space-Time Block Code (OSTBC) schemes. In the latter case, the Alamouti scheme is considered [START_REF] Di Renzo | Spatial modulation for generalized MIMO: Challenges, opportunities and implementation[END_REF].

1) In SMX-MIMO, two PSK/QAM symbols (S 1 and S 2 ) are simultaneously transmitted from a pair of TAs in a single channel use. For arbitrary N t and M , the rate of

SMX is R SMX = N t log 2 (M ) bpcu. 2) In OSTBC-MIMO, two PSK/QAM symbols (S 1 and S 2 )
are first encoded and then simultaneously transmitted from a pair of TAs in two channel uses. For arbitrary N t and M , the rate of OSTBC is

R OSTBC = R c log 2 (M ) bpcu, where R c = N M /N cu ≤ 1
is the rate of the spacetime block code and N M is the number of information symbols transmitted in N cu channel uses. If, as shown in Fig. 1, the Alamouti code is chosen, then R c = 1. 3) In SM-MIMO, only one (S 1 ) out of the two symbols is explicitly transmitted, while the other symbol (S 2 ) is implicitly transmitted by determining the index of the active TA in each channel use. In other words, in SM-MIMO the information symbols are modulated onto two information carrying units: 1) a PSK/QAM symbol; and 2) a single active TA via an information-driven antennaswitching mechanism. For arbitrary N t and M , the rate of SM is

R SM = log 2 (M ) + log 2 (N t ) bpcu [3].
In Fig. 2 and Fig. 3, the encoding principle of SM-MIMO is illustrated for N t = M = 4 by considering two generic channel uses, where the concept of "SM or spatialconstellation diagram" is also introduced. The rate of this Fig. 2. Three-dimensional encoding of SM (first channel use) [START_REF] Di Renzo | Spatial modulation for generalized MIMO: Challenges, opportunities and implementation[END_REF]. Fig. 3. Three-dimensional encoding of SM (second channel use) [START_REF] Di Renzo | Spatial modulation for generalized MIMO: Challenges, opportunities and implementation[END_REF].

MIMO setup is R SM = log 2 (M ) + log 2 (N t ) = 4 bpcu, hence the encoder processes the information bits in blocks of 4 bits each. In the first channel use shown in Fig. 2, the block of bits to be encoded is "1100". The first log 2 (N t ) = 2 bits, "11," determine the single active TA (TX 3 ), while the second log 2 (M ) = 2 bits, "00," determine the transmitted PSK/QAM symbol. Likewise, in the second channel use shown in Fig. 3, the block of bits to be encoded is "0001". The first log 2 (N t ) = 2 bits, "00," determine the single active TA (TX 0 ), while the second log 2 (M ) = 2 bits, "01," determine the transmitted PSK/QAM symbol.

The illustrations shown in Fig. 2 and Fig. 3 highlight a pair of unique characteristics of SM-MIMO:

1) The activated TA may change every channel use according to the input information bits. Thus, TA switching is an effective way of mapping the information bits to TA indices and of increasing the transmission rate.

2) The information bits are modulated onto a threedimensional constellation diagram, which generalizes the known two-dimensional (complex-valued) signalconstellation diagram of PSK/QAM modulation. The third dimension is provided by the antenna-array, where some of the bits are mapped to the TAs. Again, in SM-MIMO research, this third dimension is often termed as the "spatial-constellation diagram" [START_REF] Di Renzo | Spatial modulation for multiple-antenna wireless systems: A survey[END_REF].

B. Why It Works

From Section II-A, we have learned that the fundamental operational principle of SM-MIMO relies on transmitting part of the information bits via an implicit information-driven antenna-switching mechanism. In this section, we provide some insights on how the receiver becomes capable of retrieving the information bits encoded into the TA-indices. This, in fact, showcases the underlying "essence" that equips SM-MIMO with its innate properties.

In SM-MIMO, the signal emitted by the active TA traverses through a generic wireless channel, which is characterized by a unique channel impulse response. Owing to the different spatial locations occupied by the TAs in the antennaarray, the signal transmitted by the active TA experiences different propagation conditions due to the different dispersive and reflecting environmental objects along any transmitter-toreceiver wireless links. As such, the same PSK/QAM symbol emitted by each TA-element travels through a communication channel, which introduces a specific "channel signature or fingerprint," i.e., the channel impulse response, that makes it unique compared to the same symbol emitted by any other TAs. This constitutes the fundamental essence of SM-MIMO: the more different the channel signatures/fingerprints are from each other, the simpler it becomes to distinguish the signals at the receiver. Hence, the communication channel plays the role of a "modulation unit," where the channel impulse responses are the actual messages being transmitted.

At the receiver, the demodulation unit exploits the unique fingerprint introduced by the wireless channel for retrieving the information bits. The receiver is assumed to be aware of the N t channel impulse responses, however the actual channel impulse response that is received in each channel use depends on the index of the active TA. The demodulator performs an exhaustive search among all the possible combinations of channel impulse responses and modulation symbols, and makes a decision in favor of the hypothesis associated with the lowest Euclidean distance. In a nutshell, due to the information-driven antenna-switching mechanism of SM-MIMO transmission, the N t channel impulse responses become part of the search space of the hypothesis-testing problem solved by the receiver. Based on the estimated channel impulse response, the demodulator is capable of retrieving the information bits associated with it. In summary, the essence of SM-MIMO transmission is all about exploiting the TA-specific property of the wireless channel, i.e., the uniqueness of each transmit-to-receive wireless link, for data communication.

III. SM BASED ON RECONFIGURABLE ANTENNAS

In this section, we motivate and introduce the concept of RecAnt-SM and highlight its potential benefits for the IoT.

A. The IoT Motivation

Reconfigurability can be thought of as a software-defined functionality, where flexibility is controlled predominately through the specification of bit patterns. Reconfigurable systems can be as simple as a single switch, or as abstract and powerful as programmable matter [START_REF] Lyke | An introduction to reconfigurable systems[END_REF]. One of the most prevalent pursuits in reconfigurable RF research has been in the development of antennas, which have been studied extensively [START_REF] Christodoulou | Reconfigurable antennas for wireless and space applications[END_REF]. For the most part, a reconfigurable antenna is a set of passive structures infused with switches, which are opened and closed to elicit desired resonances for end-user applications. Reconfigurability has become an important and desired feature of modern, agile, RF systems for wireless communications and sensing. The use of reconfigurable antennas can significantly reduce the number of components, and, thus, hardware complexity, size, and cost compared to today's radio technology, which are based on communication systems with inflexible (non-reconfigurable) hardware. In the burgeoning IoT market, the size of the mobile devices ("the connected objects") will continue to shrink compared to the past while their data rate and energy efficiency capabilities will continue to raise in light of the envisioned use cases. The IoT will likely create an enormous demand for small wireless systems with sizes comparable to those of tiny sensors but with higher data rate requirements and similar or higher energy efficiency requirements. In this context, RecAnts are expected to better design communication systems satisfying the conflicting tradeoffs of reducing the size, power consumption, and cost of the IoT, while simultaneously increasing their data rate through innovative MIMO technologies [START_REF]Modulation spatiale et antenne reconfigurable pour connecter en haut debit des capteurs mobiles et autonomes en energie[END_REF].

The idea of using reconfigurable antennas for implementing and generalizing the SM principle was introduced in [START_REF] Di Renzo | Spatial modulation for generalized MIMO: Challenges, opportunities and implementation[END_REF] with the twofold attempt of increasing the achievable data rate and reducing the implementation complexity, e.g., by avoiding the need of using mechanical or RF switches. In this section, the idea of using RecAnts for application to SM systems is summarized and ongoing research activities are discussed.

B. Reconfigurable Antennas -Preliminaries

Before going into the details of applying RecAnts to SM, we briefly summarize the fundamental working principle of RecAnts and illustrate an example of RecAnt-SM system.

In general terms, reconfiguring an antenna is achieved through deliberately changing its radiation characteristics, e.g., its far field radiation pattern. In practice, this change is obtained in a controlled manner, by adequately redistributing the antenna currents and, thus, altering the electromagnetic fields of the antenna's effective aperture. In other words, thus, the far field antenna radiation pattern can be modified by appropriately controlling the distribution of the current of the antennas. Based on [START_REF] Christodoulou | Reconfigurable antennas for wireless and space applications[END_REF], e.g., there are several techniques for obtaining RecAnts, which include i) electrically-reconfigurable, ii) optically-reconfigurable, iii) physically-reconfigurable, and iv) material-reconfigurable antennas. Among the many potential benefits of RecAnts, important peculiarities for application to the IoT include the minimization of cost, volume requirements, and a simplified integration. It worth mentioning, in addition, that RecAnts are different from smart antennas, since the reconfiguration process lies inside the antenna rather than in the external network as in beamforming network.

In Fig. 4, we illustrate a simple example of reconfigurable dipole antenna, where the radiation pattern (vertical polarization) depends on the inclination angle (α) of the dipole antenna itself (the so-called polarization parameter) [START_REF] Taga | Analysis for mean effective gain of mobile antennas in land mobile radio environments[END_REF].

C. How It Works

The idea of using RecAnts for providing a low-complexity implementation solution for realizing SM systems was proposed in [START_REF] Di Renzo | Spatial modulation for generalized MIMO: Challenges, opportunities and implementation[END_REF]. In this section, we briefly discuss the idea with the aid of Fig. 4 and by considering the simplest case study.

Let us assume that the transmitter is equipped with a RecAnt that is capable of producing the far field radiation patterns depicted in Fig. 4. For ease of illustration, let us assume that the data stream to be transmitted is encoded exclusively into one of the four radiation patterns of Fig. 4. For example:

• If "00" needs to be transmitted, the polarization parameter α is set equal to 0 degrees and the corresponding antenna radiation pattern is generated and used for transmission. • If "01" needs to be transmitted, the polarization parameter α is set equal to 30 degrees and the corresponding antenna radiation pattern is generated and used for transmission. • If "10" needs to be transmitted, the polarization parameter α is set equal to 60 degrees and the corresponding antenna radiation pattern is generated and used for transmission. • If "11" needs to be transmitted, the polarization parameter α is set equal to 90 degrees and the corresponding antenna radiation pattern is generated and used for transmission. It is known that the characteristics of multipath radio channels are determined by the distribution of the scatterers in the RF propagation environment and by the interplay between multipath components and antenna radiation patterns. More precisely, the transmitted electromagnetic wave is radiated by the RecAnt according to the radiation pattern in Fig. 4 and it then interacts with the scatterers that are spatially distributed in the environment. Depending on the radiation pattern being activated by the data stream to be transmitted, as a result, the received signal depends on the interaction between the spatial distribution of the scatterers and the directional characteristics of the antenna. In general, different radiation patterns interact with different scatterers, which results in a unique received signal (fingerprint) for every possible radiation pattern. This is another way of exploiting the SM principle [START_REF] Di Renzo | Spatial modulation for generalized MIMO: Challenges, opportunities and implementation[END_REF] and of encoding the information not only in the impulse response of the channel, but in the interplay between antenna radiation pattern and nearby scatterers. Similar to the conventional SM principle [START_REF] Di Renzo | Spatial modulation for generalized MIMO: Challenges, opportunities and implementation[END_REF], the receiver is capable of retrieving the information by solving a hypothesis testing problem based on the four radiation patterns depicted in Fig. 4, as discussed in Section II for conventional SM systems.

The potential advantages of this approach compared to conventional SM is the possibility of realizing very compact and low-complexity antennas that are inherently used for modulating data. In addition, the use of RecAnts may avoid the need of using mechanical switches, which, on the other hand, are replaced by appropriate circuits that are integrated in the antenna design and that are capable of changing the distribution of the current of the RecAnt. These peculiarities are suitable for IoT applications and the research project "SpatialModulation", led by Orange Labs in France, is focused on designing and optimizing RecAnts for realizing this vision and for applying SM to IoT, 5G and WLAN systems [START_REF]Modulation spatiale et antenne reconfigurable pour connecter en haut debit des capteurs mobiles et autonomes en energie[END_REF].

D. State-Of-The-Art: Theoretical and Experimental Activities

Even though the idea of using RecAnts in the context of SM research was proposed just recently, quite a few theoretical and experimental activities are currently available. They are briefly summarized in this section.

In [START_REF] Sugiura | Coherent versus non-coherent reconfigurable antenna aided virtual MIMO systems[END_REF], the author proposes a distributed antenna system, where a single-RF reconfigurable antenna is employed at the transmitter. More specifically, the use of a single-RF reconfigurable antenna, capable of switching/forming multiple antenna patterns, is used to create virtual multiple-antenna channels without relying on the cooperation with other nodes. The author shows that the proposed technique is capable of outperforming classical virtual multiple-antenna systems. The proposed scheme, in addition, is generalized to its noncoherent detection-based counterpart, which uses differential encoding of unitary pattern-time codewords. The proposed non-coherent scheme is capable of dispensing channel state information estimation at the receiver.

In [START_REF] Martin | Differential spatial modulation for APSK in time-varying fading channels[END_REF], the author develops a Differential Spatial Modulation (DSM) scheme for amplitude phase shift keying modulation with better throughput or performance compared with conventional PSK modulation. The impact of time-varying fading is studied and it is shown that the performance degrades if the fading is too fast due to differential detection. The impact of a long outer error control code is also considered. It is shown that its performance is limited by the slowly varying channel required for differential detection. The author suggests using RecAnts to periodically changing the channel conditions and improving the coded performance of DSM systems.

In [START_REF] Bouida | Reconfigurable antenna-based space-shift keying (SSK) for MIMO channels[END_REF], the authors consider the application of RecAnts for data modulation. More precisely, the effect of RecAnts on the channel consists of changing the Rician K-factor of the channel itself. Based on this observation, the authors propose a system that encodes the information into the variation of the Rician K-factor. A mathematical framework for computing the bit error probability is proposed, and it is shown that the proposed scheme is capable of enhancing the system performance. In [START_REF] Bouida | Reconfigurable antenna-based space-shift keying for spectrum sharing systems under Rician fading[END_REF], the same authors extend their proposed modulation scheme for application to spectrum sharing systems and prove that the performance of the secondary users is improved while satisfying the constraints on the primary users.

In addition to these theoretical studies, some experimental activities that are aimed to design new RecAnts specifically tailored for SM applications have been proposed. In addition, preliminary testbed implementations have been realized.

In [START_REF] Ourir | Compact reconfigurable antenna with radiation pattern diversity for spatial modulation[END_REF], the authors design a compact reconfigurable antenna suitable for communication systems based on the SM principle. The reconfigurable antenna is based on a meander line radiating element surrounded by two L-shaped wire resonators connected to a metallic ground plane with two PIN diodes. By switching the PIN diodes, the proposed printed antenna is capable of generating four different radiation patterns. The cross-correlation between the different patterns is shown to lie in the range 11% -80%, which is shown to be acceptable for SM applications. Other antenna geometries are proposed in order to increase the number of radiation patterns that can be generated while still preserving good correlation properties for practical communication applications.

In [START_REF] Phan-Huy | First visual demonstration of transmit and receive spatial modulations using the radio wave display[END_REF], the authors report the world's first "visual" demonstration of a testbed implementation that adopts RecAnts for implementing the SM principle. Different new RecAnts are used for encoding the information bits and their different "energy patterns" are visualized with the aid of an innovative radio wave display that is capable of measuring the received power. The display shows that distinct received energy patterns are obtained if different radiation patterns of the RecAnts are activated at the transmitter. This world's first demonstration was showcased at the Int. ITG Workshop on Smart Antennas in Berlin, Germany, in March 2017 and at the IEEE Int. Conference on Communications in Paris, France, in May 2017.

IV. CONCLUSIONS AND RESEARCH OUTLOOK

The emerging market of the IoT requires new energyefficient and low-complexity MIMO-aided radio access technologies. In this paper, we have discussed a new air interface, conceived for satisfying the IoT requirements, that synergistically combines the potential of SM and RecAnt concepts. The basic technology and current theoretical and experimental research activities have been discussed and summarized.

In spite of the pioneering contributions towards the application of RecAnts to SM, major theoretical, algorithmic, and implementation issues need to be addressed. This includes, a deeper understanding of the achievable performance of SM systems based on RecAnts, the development of lowcomplexity demodulation schemes, e.g., without requiring channel state information at the receiver, and the implementation and test of RecAnts having multiple radiation patterns with controllable characteristics. For example, at the time of writing, there is no general understanding on the impact of the radiation pattern on the achievable performance if realistic (three-dimensional) multi-path fading channels are considered. In addition, all the activities conducted so far are based on the sub-6 GHz band, while no studies are available for higher transmission frequencies. The results reported in [START_REF] Liu | Line-of-sight spatial modulation for Indoor mmWave communication at 60 GHz[END_REF]- [START_REF] Liu | Variable-Nu generalized spatial modulation for indoor LOS mmWave communication: Performance optimization and novel switching structure[END_REF] on the application of SM to the millimeter-wave band highlights that this technology may be used for high frequencies as well, where RecAnts may be even more beneficial.

Fig. 1 .

 1 Fig. 1. Illustration of three MIMO concepts: (a) spatial-multiplexing; (b) transmit-diversity; and (c) spatial modulation [14].

Fig. 4 .

 4 Fig. 4. Example of different radiation patterns of a RecAnt (dipole).

ACKNOWLEDGMENT

This work is supported in part by the Agence Nationale de la Recherche Scientifique (ANR) through the research project SpatialModulation (Société de l'Information et de la Communication -Action Plan 2015) as well as by the the European Commission through the H2020-ETN-5Gaura project under grant 675806 and the H2020-ETN-5Gwireless project under grant 641985.


Alberto Colorni
email: alberto.colorni@polimi.it

Alexis Tsoukiàs
email: tsoukias@lamsade.dauphine.fr

What Is a Decision Problem? Designing Alternatives

This paper presents a general framework for the design of alternatives in decision problems. The paper addresses both the issue of how to design alternatives within "known decision spaces" and on how to perform the same action within "partially known or unknown decision spaces". The paper aims at providing archetypes for the design of algorithms supporting the generation of alternatives.

Introduction

Most scholar articles in decision analysis and operational research, when introducing the problem formulation they talk about, start with a claim of the type "given a set A of alternatives". Both researchers and practitioners know that in reality the set A is never "given" . . . It is actually constructed during the decision aiding process and most of the times defined several times during that same process.

Surprisingly enough this topic is almost ignored in the specialised literature. With the notable exception of [START_REF] Keeney | Value-focused thinking. A path to creative decision making[END_REF] who stated the principle that decision making should start considering "values" (in the sense of attributes) and not "alternatives" the latters derived from the formers, (see also [START_REF] Keeney | Creativity in decision-making with value-focused thinking[END_REF][START_REF] Leon | Valued-focused thinking versus alternative-focused thinking: Effects on generation of objectives[END_REF]) very few contributions are available: some early attempts include [START_REF] Norese | Identification and development of alternatives: Introduction to the recognition of process typologies[END_REF] and [START_REF] Ozernoy | Generating alternatives in multiple criteria decision making problems: A survey[END_REF], while other contributions were mainly focussed on how to structure the decision problem suggesting alternatives generation algorithms (see [START_REF] Baetz | Generating alternative solutions for dynamic programming-based planning problems[END_REF][START_REF] Chakhar | Generation of spatial alternatives based on a planar subdivision of the study area[END_REF][START_REF] Farquhar | Decision structuring with phantom alternatives[END_REF][START_REF] Pereira | Generating alternatives for siting retail and service facilities using genetic algorithms and multiple criteria decision techniques[END_REF]). To a certain extend work done in the area of preference disaggregation (Jacquet-Lagrèze andSiskos 1982, 2001) and preference learning [START_REF] Fürnkranz | Preference learning[END_REF][START_REF] Mousseau | Preference elicitation and learning[END_REF] can also be seen as a tentative to work first of all upon values (preferences), which establish a potential decision space, and then to assess alternatives (or to compute an optimal solution). Finally, to our knowledge the topic has been partially considered in behavioural and cognitive science studies analysing how real decision makers handle alternatives construction (see [START_REF] Newstead | Generating alternatives: A key component in human reasoning?[END_REF]. This is remarkably strange. Practically the mainstream decision analysis literature focus on how to "choose" an alternative without considering where these alternatives come from and how they can be established. On the other hand it should be obvious: if all the alternatives in the considered set are "bad" we are going to choose a bad option even if it is the best one . . . On the other hand who and how decides which are "good" options to include in the set of alternatives?

This paper is far from being a survey. We want to construct a general framework allowing handling this topic in a formal way. The topic results as part of the research in conducting decision aiding processes (see [START_REF] Tsoukiàs | On the concept of decision aiding process[END_REF]. We recall that within that framework we will always make the hypothesis that the information used within such a process is the result of the interaction of at least two agents: the client and the analyst. This attempt follows our recent work on defining what a decision problem is (see [START_REF] Colorni | What is a decision problem? Preliminary statements[END_REF] and should include both known procedures which are actually used in order to generate alternatives as well as to give the basis for defining new procedures of more general validity. Our objective is two-fold:

-show that constructing a set of alternatives is a decision problem itself; -show which are the conceptual and algorithmic challenges in developing a general theory about alternatives construction, a key topic in conducting decision aiding processes (see [START_REF] Tsoukiàs | On the concept of decision aiding process[END_REF].

The paper is organised as follows. In Sect. 2 we present the general framework (what is a decision problem) within which we consider the problem of generating alternatives. In Sect. 3 we show that this problem is a decision problem itself. Section 4 discusses how existing methods handle the issue of generating "known" alternatives. In Sect. 5 we show instead how to handle the issue of generating "unknown" alternatives when the set of available ones is unsatisfactory. Section 6 discusses related literature.

Concepts and Notation

This work follows our previous contribution about "What is a Decision Problem" [START_REF] Colorni | What is a decision problem? Preliminary statements[END_REF] where we introduced a general framework aiming to characterise decision problems on the basis of the information the client in a decision situation can provide. Indeed our framework is independent of any method characterisation: it should instead help defining a decision problem (and thus choosing or constructing any new method) from some minimal information which we call the primitives. Within such a framework a decision problem is "the tsoukias@lamsade.dauphine.fr partitioning of a set A satisfying some properties and preferential information". The primitives then are:

-the set A described along a set of attributes satisfying separability, in other terms these attributes are the minimal descriptors necessary to make a decision and each one considered alone is sufficient to make a decision; -the problem statement Π establishing the type of partitioning to perform; -the preference statements H provided by the client, to be modelled through appropriate structures and languages.

Let's present these topics with more details.

1. The set A of alternatives can be essentially of three types:

-a subset of a vector space, where alternatives are described as points (vectors) of an n-dimensional "feasible" decision space (often each dimension being associated to a "decision variable"), A ⊆ R n ; -a subset of a combinatorial structure, where alternatives are described as combinations of decision variables having a finite and discrete number of possible values (possibly binary), A ⊆ j X j where ∀j X j = {x 1j , • • • x nj }, X j being ordered; -an explicit enumeration of objects, possibly described by one or more features or attributes.

2. The problem statement Π can be:

-a ranking: construct a partition of ordered equivalence classes which are not defined a-priori; -a rating: construct a partition of ordered equivalence classes which are defined a-priori; -a clustering: construct a partition of unordered equivalence classes which are not defined a-priori; -an assignment: construct a partition of unordered equivalence classes which are defined a-priori.

3. The preference statements H (the reader should note that we use the term of preference in a very general way: any ordering relation can be considered as a preference relation, see [START_REF] Oztürk | Preference modelling[END_REF] and [START_REF] Roubens | Preference modeling[END_REF], including similarity and equivalence relations) can be of different types:

-single or multi-attribute ones; -relative (comparing elements of A among them) or absolute (comparing elements of A to some external norm); -simple (comparing single elements of A) or extended (comparing whole subsets of A); -ordinal or more than ordinal (expressing some notion of difference of preference); -positive or negative (negative preference statements should not be considered as the complement of positive ones); -first order or higher (preferences about preferences).

4. Let's recall finally that in order to choose or to construct a "resolution" method what we strictly need is the set A (minimally described), a problem statement Π and enough preference statements where we need to check (wrt to H):

-how differences of preferences are considered on each single dimension/attribute; -how differences of preferences are considered among the different dimensions or attributes; -whether preferences are conditional/dependent from other preferences; -whether negative preferences should be considered explicitly or not.

It is important to note that the concept of "preference" applies to all three principal reasons for which decisions are variable: values, opinions and scenarios.

Constructing A as a Recursion

Proposition 1 Constructing the set A is itself a decision problem.

Proof Suppose a decision situation where any option is possible. In other terms a situation where we do not really have a well established set, but only hypotheses of what this should be. We can represent this situation representing this ill defined set A as follows:

A ⊆ R n ∨ j X j admitting that n is unknown and that equally exist unknown X j . That is, the set A is only partially known (possibly totally unknown).

On the other hand let's recall that in order to establish a decision problem we need at least a set A, a problem statement Π and some preference statements H (at least of the type x y or x k where x and y are members of A and k an external norm not necessarily member of A). Finally the description of set A needs to satisfy separability. With these elements in mind we can establish a fix point:

A decision problem exists iff -∃X j such that X j is known and -∀X j such that X j is unknown these are not separable.

In other terms applying our minimality requirements either there is no decision problem or if there is one then there is at least one known descriptive dimension of the set A, any other potential, but unknown dimension, being not separable and thus irrelevant. Let's call this the set Â.

We can now establish a recursion constructing the set A:

-

A 1 = Â -A n = i [A n-1 ] i where [A n-1
] are some of the equivalence classes constructed for a decision problem defined at step n -1 and thus upon the set A n-1 .

Let's explain better our proposition. Despite the fact that the set A is not given, there is always a starting point for constructing it. It can be large and ill defined, tsoukias@lamsade.dauphine.fr but there always exist a set to start with (otherwise there is no problem . . . to work with). The construction of the set A is a recursion where at each step we construct a set as a result of the partition of the set defined at the previous step. The ending condition of this process is subjective. It is the client of the decision aiding process that declares that the present version of set A satisfies his/her requirements. In the following we provide three small examples in order to show the generality of our model.

Example 1 Consider the problem of constructing the feasible set of some linear programming problem. We can start establishing  = R n , n being the known decision variables (at least one should be known). Then:

-A 1 = Â -A 2 = [A 1 : x 1 ≥ 0] -• • • -A m = [A m-1 : x m ≥ 0]
-establishing thus a first feasible set this being the non negative reals; then:

-

A m+1 = [A m : f (x 1 , • • • x m ) ≥ 0]
, introducing a first linear constraint -and then introducing all known constraints.

The reader should note that each time we solve a rating decision problem with two possible equivalence classes (the feasible and the unfeasible solutions) defined by an external norm (the rhs of each constraint). It should also note our implicit preference statements (feasible solutions are better than the unfeasible ones) and that the preferences upon each variable and then upon bundles of variables (the constraints) are independent (thus allowing to establish a linear, additive, model).

Example 2 Consider the case of a company aiming to offer promotional tickets to the population for some advertising purpose. Then if Ω is the target population, Â will be the subset of Ω for which some information is known (sex, age, education, income etc.).

A clustering decision problem would generate n equivalence classes (unknown at the beginning)

[A 1 ], • • • [A n ]
each being an homogeneous advertising target (i.e. young, female, not-single, no-children, low income). Each of such equivalence classes could then become the set A 1 for some ranking decision problems identifying the recipients of the promotional tickets.

Example 3 Consider the case of a national park administrator who needs to apply preservation policies for the park's animals. The starting point will be to consider the whole animal population Ω of the park. Then through an assignment decision problem she will identify the species within the park (let's say mammals, birds and reptiles,

A 1 = [A 1 ] m ∪ [A 1 ] b ∪ [A 1 ] r ).
Then a rating decision problem may distinguish between endangered and not endangered animals (A 2 ). A clustering decision problem will identify "geographical communities" of animals within the park (A 3 ). Further on an assignment procedure may distinguish between local and imported animals (A 4 ). Finally a ranking procedure may order the animals on the basis of their attractiveness for the visitors (A 5 ). Why these sets may be generated? tsoukias@lamsade.dauphine.fr

The client (the park administrator) first realises that different species need different policies (she thus introduces the attributes characterising species), then she realises that endangered animals may be a priority (using new attributes describing animals' threats), then she decides to consider the differences which might be necessary for the different locations in the park (using now spatial attributes), she decides to separate local from imported animals since this is imposed by bio-diversity considerations and finally considering cost (and revenue) issues she decides to rank animals by attractiveness. Different intersections (and unions of intersections) of the above partitionings will produce now the input for further decision problems. For instance, given a group of animals being described by their relevant attributes: "local endangered mammals breading around X", cluster preservation actions into policies. In this case the starting set will be a universe of potential preservation actions (known in the literature), but the separable attributes are the ones relevant for that specific group of animals, resulting to an initial set of relevant preservation actions for that group.

Generating Known Alternatives

All existing methods in operational research, decision analysis and artificial intelligence implicitly follow the general procedure shown in the previous section, generating sets of alternatives as part of the resolution algorithm they implement. Alternatives are implicitly known and only explicitly shown when they happen to be a solution for the algorithm within the method (most of the times an optimisation one).

The reason for this is that alternatives are almost never explicitly enumerated (most of the times the whole set could be impossible to describe explicitly or even be infinite). They are described as combination of variables. Humans also, in order to handle their limited computing capability, tend to use the same approach: either reduce the number of variables (thus reducing the number of alternatives) or just focus to a limited set of "interesting alternatives" (most of the times resulting from some screening process).

Let's start with some simple human heuristics. These are always based on two simple ideas: screening and choosing (see also [START_REF] Tversky | Elimination by aspects: A theory of choice[END_REF] and/or fixing the value of one or more variables and exploring the reduced set of combinations (possibly applying the method recursively). However let's consider the following simple example (borrowed from Rivett 1994):

Example 4 Consider the transportation problem shown in Table 1, implying three production units (p1, p2 and p3) and three warehouses (w1, w2 and w3; the figures in the cells representing the costs).

Most experienced managers, when trying to solve intuitively the problem, try to maximise the amount of shipping corresponding to variable x 1 (from p 1 to w 1 , cost 0, the lowest), keeping at 0 the shipping corresponding to variable x 8 (p 3 to w 2 , cost tsoukias@lamsade.dauphine.fr 7, the highest). This gives a relatively reasonable solution, but far from the optimal one which is x 1 = 0, x 2 = 0, x 3 = 300, x 4 = 400, x 5 = 0, x 6 = 200, x 7 = 200, x 8 = 300, x 9 = 0 . The reason for failing to see intuitively the optimal solution is due to the fact that without a model and an algorithm is difficult to consider a counterintuitive choice (ship nothing from p 1 to w 1 ). For a more general and interesting discussion about these topics the reader can see [START_REF] Gilovich | Heuristics and biases: the psychology of intuitive judgment[END_REF].

The use of a formal model and some exploring algorithm certainly improves the situation. However, we know that due to algorithmic complexity most exact resolution algorithms are of little practical interest since in the worst case they require inconceivable amount of computing resources or time. Most of the times we end using heuristics (see [START_REF] Ball | Heuristics based on mathematical programming[END_REF][START_REF] Pearl | Heuristics: Intelligent search strategies for computer problem solving[END_REF].

The use of heuristics does not really change the problem. Consider the well known "knapsack" problem and the use of the equally well known simple heuristic consisting in choosing the variables (the objects to put in the knapsack) following the magnitude of the ratio between the value (the coefficient of the objective function) and the weight (the coefficient of the constraint). This procedure produces rapidly good results, but can easily miss the best solution since this may not necessarily respect this reasonable order. Heuristics generate sets of alternatives biased by the specific resolution procedure they use and in doing so they tend to eliminate alternatives which could be "interesting".

Finally let us consider the case where efficient exact algorithms are available for the problem at hand. In this case we are sure to be able to explore the whole set of potential alternatives although not explicitly enumerating them. The problem here is that despite this algorithm will provide a solution (most of the times denoted optimal), this might not be satisfactory for the client. The reason most of the times is that we are using the "wrong" set of alternatives. We should bear in mind that clients have a limited knowledge of the technical details of algorithms and more generally of problem solving methods. An initial description of a decision problem using a set of separable attributes (variables) might not be immediately perceived as partial. Usually it is when we present the results to the client that they realise that this first description of their problem does not really fit what they have in mind: all suggested solutions are perceived as unsatisfactory.

Let us summarise: generating alternatives only through resolution oriented procedures does not allow to conduct neither efficiently nor creatively a decision aiding process. We need to be able to generate further "unknown" alternatives and we need specific procedures to do so. tsoukias@lamsade.dauphine.fr

Generating Unknown Alternatives

Let's start with three examples where the known alternatives might be unsatisfactory for the decision maker.

Example 5 Ahmed, is a young man going to an appointment with his recent new girlfriend. Crossing a flowers' shop he suspects it might be her birthday. To buy or not to buy the flowers? That's the dilemma . . . However these two options appear to be equally unsatisfactory. If he buys the flowers and is not the birthday (actually the most likely scenario) there will be interminable discussions on why he did that. If he does not buy the flowers and it happens to be the birthday then it is just a tragedy. Ahmed needs more options before deciding.

Example 6 Aisha is a young French PhD student having the opportunity to visit Sydney for a conference (if her paper is accepted and conditional to the finances of the lab). Aisha's boyfriend is considering joining her. Tickets for Sydney sell presently as low as 1000 e, but they are expected to rise very soon. The problem is that Aisha will know if she will make the travel only 1 month before the conference, while today we are 4 months before the conference. Once again the available options are unsatisfactory: either low price tickets combined to high risk of losing the money in case Aisha does not make the travel, or being sure about the travel combined to a high risk of not being able to pay for the ticket. Aisha and her boyfriend would like to have more alternatives before deciding.

Example 7 Aisha and Ahmed are celebrating 10 years of living together and they look for a 1 week holiday package. The problem is that what they get are either expensive resorts in attractive locations or cheap resorts located in unattractive locations . . . Aisha and Ahmed need to expand the set of alternatives they are looking for.

The three examples are inspired from the decision analysis literature (see [START_REF] French | Decision theory -An introduction to the mathematics of rationality[END_REF][START_REF] Keeney | Value-focused thinking. A path to creative decision making[END_REF][START_REF] Smit | Strategic investment: Real options and games[END_REF]. Indeed there already exist suggestions on how to handle such decision situations expanding appropriately the set of alternatives. These include "decision trees", "real options theory" and "valued focussed thinking".

1. A well known strategy in decision under uncertainty consists in asking for more information (an action called an "oracle" given the limited trust to the information provided). Under such a perspective the two options b (buy) and ¬b (not buy) can be expanded to ib (get information and then buy), i¬b (get information and then not buy), ¬ib and ¬i¬b (same as before, deciding to buy or not without any further information). The reader will note that until information is not a separable characteristic of the decision to take, this variable simply does not exist (consistently with our hypothesis that not separable variables are not relevant). The new expanded set results thanks to information becoming a separable dimension (influencing our decision).

tsoukias@lamsade.dauphine.fr 2. In real options theory the idea is to add "'time" as a separable explicit dimension among the attributes. The unsatisfactory nature of the alternatives is due to the fact that we need to decide today for something expected to occur after a certain time. Introducing time as a further dimension we could introduce alternatives which realisation has a shortest time horizon but not preclude realising the original options. For instance airlines offer today the possibility to pay a non refundable fee fixing the price of a ticket at today's price for a certain amount of time. Instead having the two options b 0 (buy today) and ¬b 0 (not buy today) we get the expanded set ob 1 (pay the fee and then buy 1 month later), o¬b 1 (pay the fee, but then not buy), ¬ob 0 and ¬o¬b 0 (same as before, deciding to buy today or not without paying any fee). This set can be further expanded if we introduce options with different time horizons. Once again we note that is the explicit separation of time as a relevant decision dimension that allows to expand the set of alternatives. 3. In valued focussed thinking Keeney suggests to consider principally the values behind any decision questioning instead fixing the set of alternatives. In the vacation example we can relax the "1 week" constraint allowing getting more interesting offers (for instance 2 weeks packages could be more valuable than the 1 week ones, although relatively more expensive). However, we can do more than that. After all, why celebrating 10 years of common life should be done through a holiday? What about buying ten concert tickets or booking ten famous restaurants or ten tickets for recent Broadway productions? Keeney's suggestion to distinguish between core objectives (celebrating) and mean objectives (buy a holiday) allows identifying dimensions with which we can compose more alternatives from the ones initially considered. An approach more likely to generate satisfying alternatives to assess.

Let's make a first summary of what we knew about the generating algorithms problem.

Claim 1 From a decision aiding process perspective (implying some time extension), generating further sets of alternatives is related to some non satisfactory assessment of the present set of alternatives.

Claim 2 Generating unknown alternatives is always related to some expansion (or more generally revision) of the separable attributes describing the existing set.

Let's focus on Claim 2 and see what happens in a combinatorial optimisation case.

Example 8 Consider a client formulating a problem where a city (organised in n districts) should be covered by shops belonging to the client's brand, under the hypothesis that a shop opened in a certain district "covers" also the adjacent ones.

The client asks to do the minimum necessary.

tsoukias@lamsade.dauphine.fr This is a well known location problem formulated as follows:

min j x j st Dx ≥ 1 x j ∈ {0, 1}
where j = 1 • • • n are the districts;

x j are binary variables representing the opening in a certain district; D is the adjacency matrix; the meaning of the set of constraints being to satisfy covering the whole city.

Once the problem solved, the client realises that the minimum openings necessary to cover the whole city cannot be inferior of k (the minimum value of j x j ). At this point he realises that this goes beyond his budget capacity. How the problem formulation should evolve? A new version of the problem will be the following one:

max j w j y j st Dx ≥ y j c j x j ≤ C
x j , y j ∈ {0, 1}

where j = 1 • • • n are the districts;

x j are binary variables representing the opening in a certain district; y j are binary variables representing the covering of a certain district; D is the adjacency matrix; w j representing the importance of each district; and c j representing the cost of each opening, C being the available budget; the meaning of the set of constraints being to satisfy the logical relations between opening and covering as well as the budget availability provided by the client.

tsoukias@lamsade.dauphine.fr

The reader should note that the problem could also be formulated as a bi-objective optimisation one: max j w j y j min j c j x j st Dx ≥ y

x j , y j ∈ {0, 1}

Discussion Initially, the problem being formulated under the constraint of covering the whole city, the covering dimension characterising potential alternatives is not separable (since all covering variables are implicitly equal to 1). The set A is established considering only combinations of the variables x j . The unsatisfactory result obliges us to expand this set using the covering variables (since now we allow some of these to be 0: some districts might not be covered). To put it on a formal basis, using our general decision problem framework the decision aiding process will be described as follows:

1. The starting set A 1 is defined by all combinations of the variables x j (openings).

2. The constraints Ax ≥ 1 defines a rating decision problem resulting to a new set A 2 to be used in the next step. 3. The objective function min j x j defines a ranking decision problem resulting to a minimum of k openings. This information qualifies the whole set A 2 as unsatisfactory since k openings are practically impossible (but we only discover it at this stage of the process). 4. A 2 being unsatisfactory we backtrack to the initial set A 1 and we create a new starting set, let's call it B 1 as combinations of all opening and covering variables. This is possible relaxing the constraint obliging to cover the whole city, resulting in making the covering variables separable (relevant for the client's decisions). 5. The constraints Ax ≥ y and j c j x j ≤ C establish a new rating decision problem resulting to a new feasible set B 2 . 6. The objective function max j w j y j establishes a new ranking problem which hopefully will provide a satisfactory solution to the client.

Can we generalise what we described until now? Yes! Let's go back to the procedure used in order to prove Proposition 1. Introducing at each step a generalised rating decision problem (is the resulting set A i satisfying?) we are able to control the process of generating subsequent As. Further on we need to add two more possible actions (remember that A is always described by separable attributes):

-backtrack at any point of the recursion and open a new branch; tsoukias@lamsade.dauphine.fr -revise the set of separable variables describing the set A in order to generate alternatives not considered until this moment (unknown alternatives).

What do we get?

Claim 3 Generating unknown alternatives is possible allowing within the recursion constructing A two actions: backtracking and revising the set of separable variables.

Discussion

What we are presenting here are not necessarily completely new ideas, although we are sure that they have never been discussed as in this paper and combined under our perspective.

Expanding the set of variables describing a set of objects is borrowed from C-K theory [START_REF] Hatchuel | Towards design theory and expandable rationality: The unfinished program of Herbert Simon[END_REF][START_REF] Hatchuel | C-K design theory: An advanced formulation[END_REF]. This is the only formal theory of design we are aware of and is very powerful although essentially simple. The theory addresses the problem of designing new "objects" (products or services) identifying two spaces:

-the knowledge one, where objects are completely described on finite set of known attributes (a house, a car. . . ); -the concept one, where objects are only partially known, the list of attributes describing them being only partially defined;

The design process is then described as a sequence of variables transformation between the two spaces allowing the exchange of attributes between knowledge and concepts such that "new objects" can appear: a house which is also a car; a camping car.

We are firmly convinced that there are many more important links between C-K theory and our suggestion about the process of constructing alternatives. These links are yet to be explored.

Preference disaggregation (Doumpos and Zopounidis 2011) offers a first example of reorganising a set of alternatives due to a preference learning process. Robust regression preference learning methods (see [START_REF] Greco | Ordinal regression revisited: Multiple criteria ranking using a set of additive value functions[END_REF][START_REF] Greco | Robust ordinal regression for multiple criteria group decision: UTAGMS-group and UTADISGMS-group[END_REF][START_REF] Greco | Robust ordinal regression for value functions handling interacting criteria[END_REF] are a good example of methods exploiting a progressive learning of value functions allowing also to identify solutions which initially might not be considered by the decision maker.

Algorithms controlling the execution of algorithms and allowing intelligent backtracking are as old as TMS (see [START_REF] Doyle | A truth maintenance system[END_REF] and are regularly used in planning and automated reasoning devices [START_REF] Pollock | OSCAR -A general purpose defeasible reasoner[END_REF]. We can certainly see our alternatives generation procedure under such a perspective although the information conducting the process is provided on-line (during the decision aiding process) and not as an input (as it happens is most of the existing literature, for an exception see [START_REF] Pollock | Against optimality: Logical foundations for decision-theoretic planning in autonomous agents[END_REF].

tsoukias@lamsade.dauphine.fr

The whole idea of revising the conclusion of a process as a result of new information is central in Non Monotonic Reasoning (NMR) formalisms [START_REF] Ginsberg | Readings in nonmonotonic reasoning[END_REF][START_REF] Makinson | Bridges between classical and nonmonotonic logic[END_REF]. In [START_REF] Tsoukiàs | Preference modelling as a reasoning process: A new way to face uncertainty in multiple criteria decision support systems[END_REF] it has already been suggested a relation between model revision in NMR and preference modelling. Our idea about generating alternatives shows several relations to this literature:

-a decision aiding process is naturally subject to updates (new information becoming available and existing information becoming obsolete and/or inconsistent) and revisions (of values, opinions and scenarios) two notions central in the study of NMR (see [START_REF] Gärdenfors | Knowledge in flux[END_REF]); -expanding the set of conclusions derivable from given knowledge, adding defeasible reasoning is a suitable logical framework for our suggestion about the alternatives generation process starting from a partially described decision space. Since this space is only partially known we can proceed to multiple expansions which could (and actually are) defeasible, as soon as the client assess their satisfiability.

It is less obvious to us how the dimension of "creative" construction of alternatives can be considered within this framework, but this is only a special case of the more general problem; in most cases the dimensions which could be added, revised or updated are already implicitly considered in the problem formulation, but not yet explicitly considered due to the separability condition. Concluding we are not afraid to state that is likely that other relations exist between our proposal and other artificial intelligence areas including argumentation theory, learning and knowledge discovery. But these are yet to be explored.

Conclusions

The paper presents a problem often neglected and/or underestimated in decision analysis: how the set of alternatives on which a decision support method/algorithm applies is constructed. Our effort to discuss this topic is part of a long term project aiming at establishing a characterisation of decision problems independent from methods and only relying on simple primitives, the set A of alternatives being one of these ones.

In the paper we have been able to show two results. The first consists in showing that the construction of A is itself a decision problem (allowing a recursion of decision problems) and thus, that it can be studied within our general framework. The second consists in showing that the crucial problem in constructing A is the generation of "unknown" alternatives, when the set presently available is considered to be unsatisfactory. Under such a perspective we have been able to show that generating such alternatives is practically possible through backtracking the recursion which generated the present set A and expanding/revising the set of separable dimensions describing the set. tsoukias@lamsade.dauphine.fr

We concluded showing that our research is strongly related to existing fields of research in design theory and artificial intelligence. Given the low interest of this topic in the mainstream literature, it is not surprising that most of these links are yet to be explored. We hope our contribution may motivate more efforts in this promising (for us) direction.

Table 1

 1

	A simple 3 × 3 transportation problem	p1	w1 0	w2 4	w3 1 300 prd. capacity
		p2	1	6	3 600
		p3	3	7	6 500
		wrh capacity 600 300 500

tsoukias@lamsade.dauphine.fr