Eitan Altman

Véronique Serfaty

Rémi, Raouia, Sock- chenda Alan Bouchra

Hasan Je

Trois Années, En Particulier Gaël

Ludovic

Mathilde Leïla

Marina, Erbao David P Q Laurent

Julie Leïla

Alan Fanny

Véronica, Annick Pauline Liang

Keywords: P [, ] Probability, E [, ] Expectation, xix

excellent conseil, qui a su être présente malgré la distance et qui m'a souvent aidé à mettre des mots sur mes idées.

Résumé de thèse

Dans les standards actuels tels que HSDPA ou LTE, des protocoles de retransmissions (ARQ : Automatic Repeat reQuest) sont utilisés conjointement au codage de canal afin de palier aux erreurs dues à l'absence ou la mauvaise connaissance sur le canal à la transmission. De tels protocoles sont appelés protocoles de retransmission hybrides (HARQ). On garantit ainsi la fiabilité du lien physique pour les couches OSI supérieures (du moins un taux d'erreur paquet faible). L'objet de cette thèse est de proposer des outils permettant l'analyse et l'optimisation des systèmes de communication en présence de protocoles HARQ avec une emphase particulière sur les systèmes cognitifs.

Dans la première partie, nous étudierons un système point-à-point dans lequel trois différents protocoles HARQ adaptatifs seront considérés. Nous considérerons principalement le régime asymptotique (i.e. codes optimaux gaussiens) pour lequel nous étudierons la maximisation du débit moyen sous des contraintes de puissance instantanée et de puissance moyenne. Nous montrerons que les Processus de Décision Markoviens (MDP) sont des outils adaptés aux problèmes d'optimisations considérés.

Dans la seconde partie, nous considérerons un contexte de radio cognitive. La radio cognitive est une approche permettant d'augmenter l'efficacité spectrale des réseaux sans fil. Pour ce faire, des utilisateurs non-licenciés (réseau secondaire) sont autorisés à communiquer dans les mêmes bandes de fréquences que des utilisateurs licenciés (réseau primaire). Les utilisateurs secondaires doivent, en revanche, limiter la quantité d'interférence générée sur les signaux primaires.

Nous étudierons, dans cette thèse, le cas où un utilisateur secondaire interfère un utilisateur primaire qui emploie un protocole HARQ. Nous montrerons que si l'état du protocole HARQ est connu du système secondaire, une allocation conjointe de puissance et de rendement est possible, même sans connaissance instantanée du canal à l'émetteur secondaire. Cette allocation permet de maximiser le débit de l'utilisateur secondaire sous différentes contraintes. Nous considérerons en particulier des contraintes de puissance instantanée et de puissance moyenne pour l'utilisateur secondaire et une contrainte de garantie en débit pour l'utilisateur primaire. Nous montrerons, là encore, que les MDP sont des outils adéquats afin de résoudre le problème d'optimisation proposé.

iii

Thesis Abstract

Automatic Repeat Request protocols (ARQ) are widely implemented in current mobile wireless standards such as HSDPA and LTE. In general, ARQ protocols are combined with channel coding to overcome errors caused by the lack of channel knowledge at the transmitter side. These protocols are called Hybrid ARQ protocols (HARQ). HARQ protocols ensure a good reliability (at least a small packet error rate) of the physical layer for the OSI upper layers. The purpose of this thesis is to provide tools for the analysis and the optimization of HARQ communication systems with an emphasis on cognitive systems.

In the first part of this work, we consider a point-to-point context. In this context, we study three different types of adaptive HARQ protocols (HARQ with no combining, with code combining, and with Chase combining). Under hypotheses of asymptotically optimal Gaussian codes and Rayleigh block fading channel, we address the maximization of the average throughput under peak and average power constraints. In this part, we show that Markov Decision Processes (MDP) provide a theoretical framework to this optimization problems.

In the second part, we consider the cognitive radio context. Cognitive Radio (CR) is an approach aiming to increase the spectral efficiency of wireless networks. In a CR context, unlicensed users (also called secondary users) are allowed to communicate within the same frequency bands and at the same time as licensed users (also called primary users). Secondary users must however limit the amount of interference generated on the primary users signals. In this thesis, we consider a scenario in which the secondary user interferes a primary user employing a HARQ protocol. When the secondary user knows the state of the primary HARQ protocol, we show that a joint power and rate allocation can be performed. This result holds even without instantaneous channel knowledge at the transmitter side. The power and rate allocation we propose maximizes the throughput of the secondary user under different constraints. In particular, we take into account constraints on the secondary instantaneous and average powers and a constraint on the primary throughput loss. We show again that the MDPs offer a good theoretical framework to solve the proposed optimization 1 A (•) Function that is equal to 1 if x belongs to A and 0 otherwise,

General Introduction

The work presented in this PhD thesis has been done within the Information, Communications, Imagerie (ICI) team of the Equipes Traitement de l'Information et Systèmes (ETIS) laboratory in Cergy, France. This thesis has been co-founded by the Centre National de la Recherche Scientifique (CNRS) and the Direction Générale de l'Armement (DGA).

Problem statement

In the past decade, there has been a dramatic growth in the demand for new wireless services such as video transmissions and high-speed data transmissions.

To meet the needs for these new services in terms of Quality of Service (QoS), highly reliable communication systems have to be designed. In modern telecommunication standards such as High Speed Downlink Packet Access (HSDPA) or Long Term Evolution (LTE) these QoS requirements are guaranteed by link layer adaptation techniques. In these telecommunication standards, link layer adaptation techniques are a combination of Adaptive Modulation and Coding (AMC) and HARQ protocols. Although, when considered separately, these techniques are now well understood; their joint optimal design is still a challenging open issue.

AMC techniques exploit Channel Side Information at the Transmitter (CSIT)

to adapt the code and modulation to the channel condition. This adaptation is in general performed to guarantee a certain level of Frame Error Rate (FER) for upper-layers. The CSIT required to design an AMC is generally provided through a Channel Quality Indicator (CQI). The CQI represents the data rate supported by the channel using a quantized index representation (see e.g. [START_REF] Sesia | LTE -The UMTS Long Term Evolution: From Theory to Practice[END_REF]). Because of the channel versatility, some errors can still occur; these errors are then handled with a HARQ protocol acting as an error control protocol.

The first objective of this thesis is to provide a theoretical framework for analysing and optimizing systems implementing an adaptive HARQ protocol in several contexts of communication.

On the other hand, the command-and-control regulation imposes each service to be allocated in an exclusive band. The main consequence of this commandand-control regulation is that almost all the frequency bands have already been allocated. This makes the wireless spectrum a scarce resource. In parallel, a report of the Federal Communications Commission (FCC) [FCC, 2002], has shown although every bands has been allocated, the spectrum is underutilized. In this context, the Cognitive Radio (CR) paradigm has been proposed in [START_REF] Mitola | Cognitive radio: making software radios more personal[END_REF]. The CR paradigm consists in allowing Secondary Users (SUs) to opportunistically access the bandwidth initially dedicated to Primary Users (PUs) (or licensed users) to increase spectrum usage.

In this paradigm, the PUs are considered as the legitimate users of the bandwidth; in consequence, the SUs have to control the degradation done to the PUs performances.

Although PUs should have devices based on modern wireless communication standards, only a few works consider that the PUs implement a HARQ protocol.

However, it has been shown in [START_REF] Eswaran | Bits through arqs: Spectrum sharing with a primary packet system[END_REF] that the feedback bits used for the HARQ can be used by the SUs to evaluate the throughput-loss of the HARQ protocol of the PUs .

A second objective of this thesis is to provide a theoretical framework for optimizing the throughput of a secondary user who evaluates the throughput-loss of the primary HARQ protocol using only the information fed back by the PU over its feedback channel.

Outline and contributions

This section presents the outline of this thesis as well as the main contributions. This thesis is organized around four chapters that are briefly reviewed in the sequel.

Chapter 1

In Chapter 1, we review the main features of HARQ based telecommunication systems, presenting the main protocols of retransmissions and their performance analysis. In particular, we focus on the ACcumulated Mutual Information (ACMI) introduced in [START_REF] Cheng | Adaptive incremental redundancy [wcdma systems[END_REF] to model the HARQ protocols.

After reviewing the state of the art, this chapter ends with a first contribution for modelling an HARQ protocol:

• It is shown that HARQ protocols can be modelled efficiently using Markov chains on general (not necessarily countable) state spaces. This model allows us to link the dynamical behaviour of HARQ protocols with the Markov Decision Process (MDP) formalism. We conclude this chapter with the proposal of the power allocation problem to maximize the throughput of HARQ protocols under peak and average power constraints.

Chapter 2

In Chapter 2 we review existing literature about MDPs with a particular attention on CMDPs. The theoretical framework of CMDPs is commonly used to handle problems where decisions are taken sequentially to maximize a long-term reward under long-term cost constraints. To cope with the applications such as resource allocation for the Physical (PHY) layer of HARQ systems, we present the CMDP framework in the general case of possibly uncountable but compact state and action spaces. In this chapter, we provide sufficient conditions for the existence of a solution to the CMDP problem.

Because we are interested in computing solutions for practical problems, we also present how solutions of CMDPs can be approximated using finite linear programs. In particular we provide conditions so that the solutions obtained through finite linear programs converge to a continuous solution.

Generally, CMDPs assume that the controller (who takes actions) can observe the state of the system that is controlled. However, in our applications for HARQ systems, the controller does not have this complete information. In consequence, in this chapter, we also introduce (constrained) Partially Observable Markov Decision Process (POMDP) and (constrained) Partial State Information Markov Decision Process (PSI-MDP) frameworks. We finally present how these partially observable problems can be solved theoretically and numerically.

• The main contribution of this chapter has been to provide a condition so that the (constrained and with continuous state and action spaces) PSI-MDP under long-term average criteria is solvable.

Chapter 3

In Chapter 3 we apply the results presented in Chapter 2 about CMDPs to the power allocation problems considered at the end of Chapter 1. This chapter has mainly two contributions:

• Our first contribution has been to verify that CMDPs constitute a suitable framework for allocating resources in situations in which CQI is continuous and conveys the whole state of the HARQ protocol. We propose simulation results

to show the accuracy of the proposed method.

• Our second contribution has been to address the same power allocations problem considering 1-bit feedback. This problem has been addressed within the PSI-MDP framework. Again, we verify by simulations that the PSI-MDP method is accurate.

Chapter 4

In Chapter 4, we address the problem of allocating the power of a SU while mitigating the throughput-loss incurred to the PU. As proposed in [START_REF] Eswaran | Bits through arqs: Spectrum sharing with a primary packet system[END_REF], this throughput-loss is evaluated only by listening the feedback bits of the HARQ protocol of the PU. This contribution is twofold:

• We first derive an upper bound of the solution of the initial problem by relaxing the constraint of the throughput-loss evaluation. In particular, we assumed a "genie aided" problem assuming the complete knowledge of the PU state (defined in Chapter 1) by the SU. To solve this problem, we have proposed a modified version of the model presented in Chapter 1 that takes into account interferences generated by the SU. Finally, this optimization problem is solved using the CMDP framework.

• Then we derive a PSI-MDP framework for performing power allocation when the state of the PU is partially known. This case only requires the PU to be compliant with the SU and to broadcast its feedback bits.

In both situations, we have provided simulation results to evaluate the policies obtained numerically from the CMDP framework and the PSI-MDP framework.

Publications

International Journal Papers and references therein) has been proved to be an appropriate quantity for theoretically analysing HARQ protocols. These models are usually derived from an information theoretical perspective and assume asymptotically long Gaussian codewords. Although this hypothesis might seem restrictive at first glance, such codes has been proved to provide some general insights of what are the key parameters for the communication systems. In particular, the ACMI model has also been extended to coded modulations and Bit Interleaved Coded-Modulations (BICMs) in [START_REF] Cheng | Coding performance of hybrid arq schemes[END_REF]. This ACMI model was also found to be a good representation for allocation problems in [START_REF] Li | Mutual-information-based adaptive bit-loading algorithms for ldpc-coded ofdm[END_REF], [START_REF] Stiglmayr | Adaptive coding and modulation in OFDM systems using BICM and rate-compatible punctured codes[END_REF][START_REF] Stiglmayry | Adaptive coding and modulation in mimo ofdma systems[END_REF] and [START_REF] Pfletschinger | Versatile link adaptation based on mutual information[END_REF]. In addition to their optimality in the asymptotic regime, these codes have been shown to provide good insights on modern codes such as Turbo codes (see [START_REF] Buckingham | The information-outage probability of finite-length codes over awgn channels[END_REF]) or Low Density Parity Check codes (see [START_REF] Marcille | Allocation de ressources pour les réseaux ad hoc mobiles basés sur les protocoles HARQ[END_REF]). The Gaussian codes framework (as in [START_REF] Caire | The throughput of hybrid-arq protocols for the gaussian collision channel[END_REF]) has been chosen for a unified treatment of the concepts that are discussed in this thesis.

This chapter is organised as follows. In Section 1.2 we described the singlecarrier and single-user framework that will be considered throughout this thesis (with the exception of Chapter 4 that considers multi-user scenarios). In Section 1.2, we define in particular the block-fading channel, the considered channel codes, different Channel Side Information (CSI) assumptions and the Automatic Repeat reQuest (ARQ) protocols. In Section 1.3, we review the concept of a HARQ protocol and we give the definitions of three HARQ protocols. In all cases we present a throughput analysis based on the ACMI. The main contribution of this chapter is given in Section 1.4. In Section 1.4, we model the HARQ protocol by an original Markov chain. This Markov chain will be the cornerstone for the results presented in Chapter 3 and Chapter 4.

Transmitter (Tx)

Receiver (Rx)

Channel

√ P n

Channel Encoder

h n z n Channel Decoder Power Allocation u n x n x n y n û n ACK / NACK

System Model

We consider the single-user, single-carrier communication system depicted in Figure 1.1. In this system, a transmitter (Tx) sends data to a receiver (Rx) over a discrete-time wireless channel. We suppose a slotted communication system where slots have duration T seconds. The slots are indexed by n ∈ N so that slot n happens between time nT and (n + 1)T (see Figure 1

.2). time Slot n -1 Slot n Slot n + 1 (n -1)T nT (n + 1)T (n + 2)T Figure 1.2 -Time slot model.
Suppose that the data sent by Tx is composed of information messages u n , each conveying b information bits. Tx encodes u n into a coded message

x n of length L = B W T symbols where B W is the bandwidth and T is the duration of the slot. We suppose here that every possible coded message has unit power. Before sending x n over the channel, Tx applies its power allocation by multiplying x n by √ P n . We suppose that the power allocation is defined as a sequence {P n } n∈N is known to Tx and Rx. The received signal at Rx is denoted by y n . This signal is decoded into an information message denoted by ûn .

Channel model

For modelling a wireless communication, the channel is often modelled as a block-fading channel (see [START_REF] Tse | Fundamentals of Wireless Communication[END_REF]] and references therein). In this model, the channel is assumed to be constant for the whole duration of the slot. The channel gains {H n } n∈N are a discrete time independent and identically distributed (i.i.d.) stochastic process.

Let X n be the coded message considered as a complex Gaussian random vector of dimension L with i.i.d.components of zero mean and unit variance. When X n is sent over the block-fading channel with power p n , the received signal Y n at Rx is given by

Y n = P n H n X n + Z n , (1.1)
where the noise vector Z n is a length L complex Gaussian random vector with i.i.d. components with zero mean and variance σ 2 z . In this thesis we will consider a Rayleigh block-fading model. This model represents well situations where there is no line of sight between Rx and Tx. In this case {H n } n∈N can be considered as a Gaussian process. In this case, the phase of H n is uniformly distributed in [0, 2π], the modulus of H n is distributed according to a Rayleigh distribution with parameter √ ᾱ:

f |H| (x) = 2x ᾱ exp -x 2 ᾱ , x ≥ 0
and the fading power α n = |H n | 2 is exponentially distributed with mean ᾱ:

f α (x) = 1 ᾱ exp -x ᾱ , x ≥ 0.
Other distributions such as the Nakagami-m distribution or Rice distribution can be considered in the literature but are out the scope of this thesis.

Channel State Information

|h 0 | 2 |h 1 | 2 |h 2 | 2 |h 3 | 2 |h 4 | 2 time 0 T 2T 3T 4T 5T Figure 1.3 -Block fading channel 1.2. System Model 11
CSI is a cornerstone for communication systems since it defines the knowledge of the communicating devices to operate. In the system presented in Figure 1.1, CSI is defined as the knowledge of H n at time index n. We call Channel Side Information at the Transmitter (CSIT) or Channel Side Information at the Receiver (CSIR), the fact that Tx or Rx has CSI, respectively. In some references (see for example [START_REF] Tuninetti | On the benefits of partial channel state information for repetition protocols in block fading channels[END_REF]), this CSI is called Causal CSI because only the current H n is known but not the future ones {H t } t≥n+1 .

In this thesis, Causal CSI and CSI are identical, however we use the term Outdated Channel Side Information (OCSI) for the cases where some information about {H t } t≤n-1 is available but H n is not. This term is used in particular for resource allocation in the presence of HARQ protocols (see for example [START_REF] Szczecinski | Adaptive incremental redundancy for harq transmission with outdated csi[END_REF]).

In some situations, H n is not known but its distribution is. This will be referred to as Statistical Channel Side Information (SCSI). In the literature (see for example [START_REF] Goldsmith | Wireless Communications[END_REF]), SCSI is sometimes referred to as Channel Distribution Information.

Asymptotically optimal Channel Coding

In the model presented in Figure 1.1, errors introduced by the channel are corrected using channel coding. In this section, we suppose that there is CSIR but not CSIT.

Let us consider that every codeword x at the output of the channel coder span N T slots and is a complex Gaussian random vector of dimension N T L with i.i.d. components of zero mean and unit variance. Let P = (P 0 , P 1 , . . . P N T -1 )

be the vector such that P j is the power allocated for the j th slot. Suppose that

x is split into N T blocks of size L: x = (x 0 , x 1 , . . . x N T -1
) . Each block is then sent over the block fading channel.

For this channel, it has been shown in [START_REF] Caire | The throughput of hybrid-arq protocols for the gaussian collision channel[END_REF]] that, in the asymptotic regime (L → ∞) the Frame Error Rate (FER) is given by

p f (N T ) = P ⎡ ⎣ N T -1 j=0 C P j |H j | 2 σ 2 z < R ⎤ ⎦ , (1.2)
where C(x) is the capacity of complex valued Additive White Gaussian Noise (AWGN) channel C(x) = log 2 (1 + x), R is the equivalent information rate of the first transmission given by R = b/L, b is the number of information bits conveyed in the information messages u and σ 2 z is the noise variance. This probability is referred to as outage probability or information outage probability (see [START_REF] Knopp | On coding for block fading channels[END_REF], [START_REF] Caire | The throughput of hybrid-arq protocols for the gaussian collision channel[END_REF], [START_REF] Sesia | Incremental redundancy hybrid arq schemes based on low-density parity-check codes[END_REF], Chapter 1. An overview of HARQ-based telecommunication systems [START_REF] Cheng | Coding performance of hybrid arq schemes[END_REF] and references therein).

Remarks

• In [START_REF] Cheng | Coding performance of hybrid arq schemes[END_REF], the quantity

N T -1 j=0 C P j |Hj | 2 σ 2 z
is referred to as the ACMI.

Using the ACMI definition, the author has shown that an equation similar to equation (1.2) holds for modulation constrained AWGN channel (the modulation may change at every slot). In this case, we replace C by the capacity of the corresponding constrained input AWGN channel for each slot. In the same paper, this result is extended to BICM.

• In [START_REF] Caire | The throughput of hybrid-arq protocols for the gaussian collision channel[END_REF], equation (1.2) is shown using a typical set decoder. This decoder is suboptimal, (compared to the Maximum Likelihood (ML) decoding rule) in terms of FER for finite length codes, however, it is asymptotically optimal (see [START_REF] Cover | Elements of Information Theory[END_REF]). The authors have also pointed out two other advantages for HARQ protocols. The first one is that, asymptotically (L → ∞), this decoder performs a perfect error detection. In other words, asymptotically, there is a null probability of not detecting an error. Note that this step is usually performed by adding Cyclic Redundancy Check (CRC) bits to the information message when considering practical channel coding schemes and decoders.

The second advantage is that this decoder can handle puncturing. Suppose that we only send the following blocks: x 0 , x 1 , . . . x m-1 . At the decoder, Rx can complete its received message by N Tm dummy signal blocks ξ m , . . . ξ N T -1 as long as they are generated independently from the received signal. After this step, Rx uses ỹ = y 0 , y 1 , . . . y m-1 , ξ m , . . . ξ N T -1 to decode. This method is similar to classical puncturing techniques; in this case, the FER becomes

p f (m) = P ⎡ ⎣ m-1 j=0 C P j |H j | 2 σ 2 z < R ⎤ ⎦ . (1.3) From equation (1.
2) we observe that, in a block-fading channels, it is impossible to have a zero probability of error even though L → ∞. Outage events will always happens due to deep fades. To ensure reliability of the communication, ARQ based protocols are used.

Automatic Repeat reQuest

These protocols enable the end-to-end delivery of information packets by allowing the same information packet to be sent multiple times.

Performance evaluation of the ARQ protocol

By definition, the ARQ protocol makes the transmission of information packets reliable since Rx will always end up decoding correctly (if an infinite number of retransmissions is allowed). On the other hand, this reliability is earned at the expense of delay. Indeed, in the definition of the ARQ protocol, it may happen that the protocol retransmits a large number of times a packet before decoding it correctly. The average time taken by the ARQ protocol to correctly transmit a packet is called delay and is one figure of merit of the performance of ARQ protocols.

A trade-off can be achieved between reliability and delay by imposing a maximum number of retransmissions. This case is often referred to as truncated ARQ in the literature. Let N T -1 be this maximum number of retransmissions (N T takes also into account the initial transmission). In this case, the overall protocol may fail. This is called an outage event. The probability of such event is commonly referred to as outage probability (see [START_REF] Caire | The throughput of hybrid-arq protocols for the gaussian collision channel[END_REF]).

Definition 1.1. The outage probability that the ARQ protocol fails after N T -1 retransmissions is called the outage probability

To be completely fair, we have to re-define the delay to take into account the finiteness of N T . Several definitions of delays may be found in the literature. In this thesis we choose a definition of [Le Duc, 2010]:

Definition 1.2. The delay is the mean time between the beginning and the end of an ARQ protocol when a successful decoding occurs.

The third figure of merit usually presented in the literature to evaluate the performance of ARQ protocols is the throughput. In this thesis, we will adopt the definition of throughput given in [START_REF] Lin | Error control coding[END_REF]]:

Definition 1.3. The throughput is "the ratio of the average number of information digits successfully accepted by the receiver per unit of time to the total number of digits that could be transmitted per unit of time".

Let b c (n) be defined as the total number of bits correctly decoded up to slot n, the throughput is given by

η = lim n→∞ bc(n) nT L T = lim n→∞ b c (n) nL in b/s/Hz. (1.4)
The computation of this throughput is classically done using the renewal and reward theorem as proposed in [START_REF] Zorzi | On the use of renewal theory in the analysis of arq protocols[END_REF]. Let E be the event defined as: "Tx starts the transmission of a new information packet". A random reward R E is attached to this recurrent event. This random variable is R E = b (the number of bits contained in u n ) if the packet is successfully decoded by Rx and R E = 0 otherwise. Relying on this event and this reward the renewal-reward theorem states that (see [START_REF] Ross | Introduction to probability models[END_REF])

η = E [R E ] E [D E ] , ( 1.5)
where E [R E ] is the expected reward earned in the recurrent event and D E is the random time between two successive occurrences of E. In the description of the ARQ protocol, we have assumed that once Tx finishes transmitting a packet, it starts the transmission of a new information packet. Under this assumption, D E is also defined as the time between the start and the end of the transmission of an information packet.

We now further develop the expression of the throughput given in equation (1.5). We introduce O n as the following event: "the decoding fails after n transmission attempts". Let p s (n) and p f (n) be the probability of decoding success in exactly n transmission attempts and the probability of decoding failure after n transmission attempts. Because of the sequential aspect of the ARQ protocol, these two probabilities p s (n) and p f (n) can be written using the event O n as follows:

p f (n) = P [O 1 , O 2 , . . . , O n-1 , O n ] (1.6) p s (n) = P O 1 , O 2 , . . . , O n-1 , O n (1.7)
(N T -1).
Finally, the throughput is expressed as follows

η = b L 1 -p f (N T ) N T -1 l=1 lp s (l) + N T p f (N T -1)
.

(1.8)

This equation can be further simplified by introducing the information rate equivalent to the first transmission R = b/L and remarking that

⎧ ⎨ ⎩ p s (n) = p f (n -1) -p f (n), n > 0 p f (0) = 1 (1.9)
Introducing (1.9) in (1.8), we obtain

η = R 1 -p f (N T ) 1 + N T -1 l=1 p f (l)
.

(1.10)

In this thesis, we will only consider the throughput as a main figure of merit for the performance evaluation of HARQ protocols. However one can refer to [START_REF] Zorzi | On the use of renewal theory in the analysis of arq protocols[END_REF], [START_REF] Caire | The throughput of hybrid-arq protocols for the gaussian collision channel[END_REF], [START_REF] Sesia | Incremental redundancy hybrid arq schemes based on low-density parity-check codes[END_REF]], [Le Duc, 2010], [START_REF] Marcille | Allocation de ressources pour les réseaux ad hoc mobiles basés sur les protocoles HARQ[END_REF], and references therein to have a more complete view and analysis of other performance criteria. We now present some practical issues that have not been considered in the previous analysis.

Practical issues

The description of the ARQ protocol as given above does not taken into account possible imperfections encountered in practice. In practice, several additional delays occur. These delays, depicted in Figure 1.4, are the following:

• τ p : the one-way delay, which represents the delay incurred by the propagation time between Tx and Rx,

• τ d : the data processing delay, which represents the delay incurred by the time that takes Rx for demodulating, decoding, and detecting errors.

The protocol presented at the beginning of this section is called the Stop-and-Wait protocol: when Tx has sent one block, it waits to receive the acknowledgement bit to continue its transmission. This protocol is obviously inefficient.

This inefficiency can be observed by computing the effective throughput. Let τ be the overhead time for the transmission of one block defined as τ = 2τ p + τ d .

From [START_REF] Lin | Error control coding[END_REF] we get

η sw = T T + τ η, (1.11)
where η is the throughput computed without taking into account delays. Note that in the situation depicted in Figure 1.4, we have τ = 2T and

T T +2τp+τ d = 1 3
so the effective throughput is divided by three compared to the case τ = 0.

To overcome the impact of these delays, several protocols have been proposed in the literature. In particular, in [START_REF] Lin | Error control coding[END_REF]] the Go-Back-N protocol and the Selective and Repeat protocol are described. The main result that has been proved in the literature is the following: under an assumption of infinite buffer at Rx, the throughput of the Selective and Repeat is equal to the throughput of a Stop-and-Wait protocol with τ = 0 (see [START_REF] Lin | Error control coding[END_REF]], [START_REF] Aoun | Optimisation des techniques de codage et de retransmission pour les systemèmes radio avec voie de retour[END_REF], [START_REF] Marcille | Allocation de ressources pour les réseaux ad hoc mobiles basés sur les protocoles HARQ[END_REF] and references therein). In consequence, in this thesis we will consider a Stop-and-Wait protocol with τ = 0.

Other imperfections can be considered in the ARQ protocol. In particular one may consider that error may occur on the feedback channel. In this context, cross layer optimization techniques have been proposed in [START_REF] Marcille | Performance computation of cross-layer hybrid arq schemes at ip layer in the presence of corrupted acknowledgments[END_REF] and [START_REF] Marcille | A cross-layer harq scheme robust to imperfect feedback[END_REF]. One can of course think of mixing the imperfections.

HARQ Protocols

The Go-Back-N protocol under imperfect feedback has been studied in [START_REF] Zorzi | On the use of renewal theory in the analysis of arq protocols[END_REF].

Through this thesis, we will always suppose that Assumption 1.1 holds. In consequence, every throughput that will be computed in this thesis has to be understood as an upper bound on the possible throughput if imperfections were taken into account.

Assumption 1.1.

(a)

The feedback channel is instantaneous and error-free.

(b) The probability of an undetected error and the probability of detecting an error while the decoding is successful are 0.

(c) T x is backlogged: it always has an information packet to transmit in its queue.

HARQ Protocols

The main advantage of the ARQ protocol is that it guarantees a high reliability of the communication link. Indeed, when an infinite number of retransmissions is allowed, there is a null outage probability. However, the ARQ protocol does not benefit, neither from error correcting codes, nor from information contained in the earlier transmissions (since it discards the outdated message before decoding the new one) to decrease the probability of successfully decoding a packet.

In this Section, we will study three different ways of combining Forward Error Correction (FEC) and ARQ. This combining approach is referred to as HARQ, where the term "Hybrid" indicates that both FEC and ARQ are used.

The first type of HARQ protocol is the so-called Type-I HARQ protocol and is analysed in Subsection 1.3.1. The second method to improve the throughput is to use the information contained in the first retransmissions to decrease the probability of error in the next retransmissions. These protocols are referred to as Type-II HARQ protocols. There exist two main approaches for Type II-HARQ protocols: the Type II-Chase Combining (CC)-HARQ protocol (denoted CC-HARQ in the sequel) and the Type II-Incremental Redundancy (IR)-HARQ protocol (denoted IR-HARQ in the sequel). The CC-HARQ protocol and the IR-HARQ protocol are described in Section 1.3.2 and Section 1.3.3 respectively.

Type-I HARQ protocol

In order to improve the throughput of the ARQ protocol one can think of using FEC to send coded packets instead of non-coded packets. It decreases the outage probability and thus increases the throughput. This newly defined Chapter 1. An overview of HARQ-based telecommunication systems protocol is called the Type-I HARQ protocol. The Type-I HARQ protocol is then equivalent to the truncated ARQ protocol except that the Type-I HARQ protocol uses FEC to correct errors.

In this case, we consider that the codewords of Gaussian codebooks of Section 1.2.3 span one slot. Other schemes could be considered with the same qualitative conclusions. Because the codeword is assumed to span only one slot, and because the j th attempt is independent of every other attempt, the probability that the j th attempt of decoding the information packet fails is given by

p o (j) = P log 2 1 + P j |H j | 2 σ 2 z < R , (1.12)
where P j is the power used on slot j and R = b/L. Since all the retransmissions are independent, the probability of failure after n attempts p f (n) (defined in (1.6)) is given by

p f (n) = n j=1 P log 2 1 + P j |H j | 2 σ 2 z < R . (1.13)
One can remark that what has been presented in Section 1.2.4 for the computation of the throughput for the ARQ protocol can also be applied for the Type-I HARQ protocol. The throughput of the Type-I HARQ protocol is finally expressed using equation (1.10) as follows:

η t1 = R 1 - N T j=1 P log 2 1 + P j |H j | 2 σ 2 z < R 1 + N T -1 n=1 n j=1 P log 2 1 + P j |H j | 2 σ 2 z < R . (1.14)
This expression simplifies if we consider a constant power allocation

P 1 = P 2 = • • • = P N T = P as follows η t1 = R 1 -P log 2 1 + P |H| 2 σ 2 z < R N T 1 + N T -1 n=1 P log 2 1 + P |H| 2 σ 2 z < R n , ( 1
η t1 = R 1 -P log 2 1 + P |H| 2 N 0 < R . (1.16)
One can remark that the throughput of the Type-I HARQ protocol is equal to the throughput of the same FEC code used without ARQ. However, the Type-I HARQ protocol exploits the ARQ to improve the reliability of its transmission compared to pure FEC. Indeed, the outage probability of the Type-I HARQ

protocol is P log 2 1 + P |H| 2 σ 2 z < R N T whereas it is P log 2 1 + P |H| 2 σ 2 z < R
for a transmission using FEC only.

Type-II Chase Combining (CC) HARQ protocol

The major drawback of a Type-I HARQ protocol is that it does not benefit from the different retransmissions. Indeed, all retransmissions are independent and independently processed at Rx. This makes the Type-I HARQ protocol highly inefficient. To improve the efficiency of Type-I HARQ protocol other protocols have been proposed with more complex processing at Rx. We here consider one of these protocols named the Type-II CC HARQ protocol (noted CC-HARQ for the rest of this thesis).

Protocol definition

The main difference between Type-I HARQ and CC-HARQ protocols is the processing done at Rx. From the point of view of Tx, nothing is changed. Tx always sends the same codeword among all the retransmissions. For ease of presentation, suppose that the transmission of the current packet has begun at slot 0 and the current time is nT so that the n attempts to decode has been done without a positive result.

Let {Y 0 , Y 1 , . . . , Y n-1 } be the received signals for slots 0 to n -1. Whereas the Type-I HARQ protocol only considers Y n-1 at the decoder, the CC-HARQ considers the following combined signal

R n = n-1 j=0 g j Y j , (1.17)
where g j are given complex coefficients. Assuming CSIR the optimal choice (see [START_REF] Brennan | Linear diversity combining techniques[END_REF]) for the coefficients g j is called Maximum Ratio Combining (MRC) and is given by: and replacing y j by its expression given in equation (1.1), we obtain

g j = H * j σ 2 z , ( 1
R n = X n-1 j=0 P j |H j | 2 σ 2 z + n-1 j=0 H * j σ 2 z Z j , (1.19)
At this point, the Signal to Noise Ratio (SNR) at Rx is denoted γ n and is defined as

γ n = n-1 j=0 |H j | 2 P j σ 2 z .
(1.20)

One can note here that the CC-HARQ protocol "accumulates" SNR; indeed, the SNR given by equation (1.20) can be rewritten as the following recursion:

⎧ ⎪ ⎨ ⎪ ⎩ γ 0 = 0, γ n+1 = γ n + |H n | 2 P σ 2 z . (1.21)
This accumulation result is classical in the literature, see for example [START_REF] Cheng | Coding performance of hybrid arq schemes[END_REF].

Performance Analysis

To compute the throughput of the CC-HARQ protocol, we will again use equation (1.10). Note that the throughput expression given in equation (1.10) is dependent on the type of HARQ protocols only through the p f (n), n ∈ {1, . . . , N T }. We will then compute the throughput by computing these probabilities of failure p f (n).

Again we present results based on the FEC scheme presented in Section 1.2.3. The only difference between the Type-I HARQ and the CC-HARQ protocol is that the CC-HARQ protocol considers R n (the combined signal after n attempts) instead of Y n (the last received signal) to decode. Let R = b/L be the information rate corresponding to the initial transmission. The probability of decoding failure after n transmission attempts p f (n) is computed as follows:

p f (n) = P ⎡ ⎣ log 2 ⎛ ⎝ 1 + n-1 j=0 P j |H j | 2 σ 2 z ⎞ ⎠ < R ⎤ ⎦ = P ⎡ ⎣ n-1 j=0 P j |H j | 2 σ 2 z < 2 R -1 ⎤ ⎦ (1.22)
In the sequel we denote by Γ = 2 R -1. Γ is referred to as the decoding threshold for Rx. The throughput of the CC-HARQ protocol is again computed using the 1.3. HARQ Protocols 21 renewal and reward theorem. The expression of the throughput is then given by equation (1.5):

η cc = R 1 -p f (N T ) 1 + N T -1 l=1 p f (l) , ( 1.23)
where R = b/L. In this case, the p f probabilities are given by equation (1.22).

In the case of constant power allocation, the expressions of the different p f (n) are

p f (n) = P ⎡ ⎣ n-1 j=0 P |H j | 2 σ 2 z < Γ ⎤ ⎦ . (1.24)
To evaluate this expression, one can remark that, because the |H j | 2 are i.i.d.

and exponentially distributed,

n-1 j=0 |H j | 2 is gamma-distributed: n-1 j=0 |H j | 2 ∼ Gamma(n, 1/λ).
A closed-form expression of p f (n) obtained thanks to the this Gamma distribution can be obtained but is out of the scope this thesis.

Type-II Incremental Redundancy (IR) HARQ protocol

The IR-HARQ protocol is different from the Type-I HARQ and the CC-HARQ protocols in the sense that Tx does not send the same packet over the channel.

We will now describe the IR-HARQ protocol.

In this section, Tx sends information packets u of b information bits. The IR-HARQ protocol considers a FEC scheme of Section 1.2.3 where the codewords spans N T slots. Similarly to the description done in Section 1.2.3, each codeword

x is divided into N T blocks of equal length:

x = (x 0 , x 1 , . . . x N T -1 ) . (1.25)
The main difference between the IR-HARQ protocol and the FEC scheme proposed in 1.2.3 is as follows: the IR-HARQ protocol intends to decode after each slot whereas the FEC scheme of Section 1.2.3 decodes only after the N T slots.

For ease of presentation, we suppose that the transmission of the current packet begins at slot 0. Tx sends x 0 over the channel. Rx receives the signal y 0 and decodes. Using equation (1.3), the average probability of error is given by 3), the average probability of error is obtained as

p f (1) = P log 2 1 + P 0 |H 0 | 2 σ 2 z < R . ( 1
p f (2) = P ⎡ ⎣ 1 j=0 log 2 1 + P j |H j | 2 σ 2 z < R ⎤ ⎦ . (1.27)
More generally, the probability of failure after n attempts is given by

p f (n) = P ⎡ ⎣ n-1 j=0 log 2 1 + P j |H j | 2 σ 2 z < R ⎤ ⎦ . (1.28)
From this equation, one can observe that the IR-HARQ protocol accumulates mutual information. In [START_REF] Cheng | Coding performance of hybrid arq schemes[END_REF],

i n = n-1 j=0 log 2 1 + |H j | 2 P σ 2 z (1.29)
is referred to as ACMI. The throughput of the IR-HARQ protocol is again given by

η ir = R 1 -p f (N T ) 1 + N T -1 l=1 p f (l)
.

where R = b/L and p f (n) is given by (1.28). Note that in this case, the expression p f (n) cannot be further simplified for a constant power allocation.

In this section, we defined the Type-I HARQ protocol, the CC-HARQ protocol and the IR-HARQ protocol. In the three cases, we have shown that the throughput can be expressed as

η = R 1 -p f (N T ) 1 + N T -1 l=1 p f (l) ,
where R = b/L, and the probabilities p f (n) are given by equation (1.13) for the Type-I HARQ case, by equation (1.22) for the CC-HARQ protocol, and by equation (1.28) for the IR-HARQ protocol.

A unified analysis based on Markov chains

In the precedent section, we have done the throughput analysis for the Type-I HARQ protocol, the CC-HARQ protocol, and the IR-HARQ protocol. These three analyses are based on the renewal and reward theorem as proposed in [START_REF] Zorzi | On the use of renewal theory in the analysis of arq protocols[END_REF]. The main drawback of these analyses is that, except in the Type-I HARQ case, we are not able to derive closed-form expressions for the probabilities p f (n) for all n ∈ 1, . . . , N T (given by (1.22) and (1.28) ).

Some closed-form expressions exist (see e.g. [START_REF] Chaitanya | Outage-optimal power allocation for hybrid arq with incremental redundancy[END_REF][START_REF] Marcille | Allocation de ressources pour les réseaux ad hoc mobiles basés sur les protocoles HARQ[END_REF]), however they are often difficult to compute and to handle. In this thesis we propose a different approach based on a controlled Markov chains with possibly infinite and uncountable state space. Our approach is based on the following observation:

the three HARQ protocols are finally driven by an accumulation of some quantities (SNR, mutual information).

Controlled Markov Chain associated with the Type-I HARQ protocol

Firstly, we focus our study on the Type-I HARQ protocol. Let K n be a random variable representing the number of attempts done by Tx to transmit its current information packet. For each time nT , K n can take one of the following N T + 1 values:

• 0 : Tx starts the transmission of a new information packet after a successful decoding (ACK),

• 1 : Tx has done 1 attempt and a NACK bit is received,

• 2 : Tx has done 2 attempts and a NACK bit is received, . . .

• N T : Tx has done N T attempts and NACK is received, this state corresponds to an outage event and, in consequence, to the start of the transmission of a new information packet.

For the sake of completeness, suppose that the power allocation π = {P n } n∈N is a random process so that in each slot n, Tx sends x n with a random power P n . We are now interested in showing that the random process {K n } verifies the following Markov property

P [K n+1 = k n+1 |P n = p n , K n = k n , P n-1 = p n-1 , K n-1 = k n-1 , . . . ] = P [K n+1 = k n+1 |P n = p n , K n = k n ] (1.30) Chapter 1.

An overview of HARQ-based telecommunication systems

Firstly, we introduce the Gain to Noise Ratio (GNR) which is defined similarly in [Marcille et al., 2012a] as follows:

α n = |H n | 2 σ 2 z . (1.31)
Let us now interpret the left-hand side of equation (1.30). For the sake of simplicity, suppose first that

N T > k n > 0. By definition, K n = k n means that,
at the beginning of slot n, Tx had done k n attempts and that a retransmission is required by Rx (a NACK bit is received). In this case, we have shown that Tx sends the same codeword over the channel. Only two situations can occur: Rx fails to decode its received signal or Rx succeeds in decoding its received signal.

We have seen in the preceding section, that the blocks sent over the channel are independent of each other and that (conditionally on P n = p n ) the probability of decoding failure by Rx is given in equation (1.12) and slightly modified to introduce α n and to stress the dependence on p n as follows:

p o (p n ) = P [log 2 (1 + p n α n ) < R] . (1.32)
From this probability, we can prove that if the random variable Δ

(α n , p n ) = log 2 (1 + p n α n ) is smaller than R,
Rx fails in decoding the information packet.

Hence, K n+1 will be: 'Tx has done k n + 1 attempts and a NACK bit is received'.

The second possible scenario is Δ(α n , p n ) ≥ R. In this case Rx succeeds in decoding the information packet and K n+1 will be 'Tx starts the transmission of a new information packet after a successful decoding (ACK)'. More formally it means that

P [K n+1 = k n+1 |P n = p n , K n = k n , P n-1 = p n-1 , K n-1 = k n-1 , . . . ] = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ P [Δ(α n , P n ) ≥ R|P n = p n ] if k n+1 = 0 P [Δ(α n , P n ) < R|P n = p n ] if k n+1 = k n + 1 0 otherwise. (1.33)
It proves that when N T > k n > 0, equation (1.30) is verified. Similarly to the proof of the case N T > k n > 0, we can easily derive the cases k n = 0 and k n = N T . These proofs are omitted but Table 1.1 summarizes the possible values for K n+1 depending on k n (lines) and on the random variable Δ(α n , P n ) (columns).

Finally, one can remark that equation (1.30) is similar to a Markov property except that the probability of transition are dependent on {P n } n∈N . In consequence, we can represent the transition graph of this Markov chain by a graph similar to the one given in Figure 1.5. On this graph, circles represent 1.4. A unified analysis based on Markov chains 25 the possible states for K n and arrows represents the possible transitions given in Table (1.30). Hitherto, we have proposed a controlled Markov chain that represents the state evolution of the random process K n that model the state of the Type-I HARQ protocol. Let r(K n ) be the random variable defined as

Δ (α n , p n ) < D T Δ (α n , p n ) ≥ D T k n < N T -1 k n + 1 0 k n = N T -1 N T 0 k n = N T 1 0 Table 1.1 -
p o (p n ) p o (p n ) p o (p n ) 1 -p o (p n ) 1 -p o (p n ) 1 -p o (p n ) 1 -p o (p n ) p o (p n )
r(K n ) = ⎧ ⎨ ⎩ b if K n = 0 0 otherwise. (1.34)
From the definition of K n it is obvious that r(K n ) is the same as defining R E . Indeed, the event E has been defined in Section 1.2.4 as the start of a transmission of a new information packet and R E = b only after successful decoding of Rx. Because of this equivalence, the throughput of the controlled Type-I HARQ protocol is rewritten as follows

η(π) = 1 L lim n→∞ 1 n n-1 i=0 r(K n ),
where π = {P n } n∈N is added to show the dependence of the throughput on π (see Table 1.1 or Figure 1.5). We next show that a very similar analysis can be done for the CC-HARQ and the IR-HARQ protocols.

The state of Type-II HARQ protocols

1 0 2 3 x x x x s n (1, x) (0, 0) D T D T D T D T f Δ|P (x -x n |p n ) s n+1
(0, 0)

Figure 1.6 -Transition graph of a Type-II HARQ protocol.

In Section 1.3.2 we have shown that the main difference between Type-I HARQ protocol and CC-HARQ protocol is that the CC-HARQ protocol accumulates SNR. On the other hand, in Section 1.3.3, we have seen the IR-HARQ protocol differs from the Type-I HARQ protocol by accumulating mutual information. In the sequel we denote by Δ (α n , p n ) the increment of the accumulated quantity. For the CC-HARQ protocol we have:

Δ (α n , p n ) = α n p n ,
while for the IR-HARQ protocol we have:

Δ (α n , p n ) = log 2 (1 + α n p n ).
The model that is considered for analysing both Type-II HARQ protocols is a simple extension of the model proposed in Section 1.4.1 for Type-I HARQ protocols. This model is based on the random process {S n } n∈N such that, at every time nT , S n = (K n , X n ). K n has the same definition as in Section 1.4.1, and X n represents either the accumulated SNR or the ACMI. In the sequel S n will be referred to as the state of the HARQ protocol. Let D T be defined as From each k we represent a vertical line that accounts for the possible values for x n . For example, in Figure 1.6 the state s n corresponds to a state of the form (1, x n ). In the rest of this section, we will use Figure 1.6 as a transition graph to illustrate our saying.

We now show that for every B ⊂ S the following Markov property holds: The second case {x n + Δ (α n , p n ) < D T }, corresponds to a decoding failure.

P [S n+1 ∈ B|P n = p n , S n = s n , P n-1 = p n-1 , S n-1 = s n-1 , . . . ] = P [S n+1 ∈ B|P n = p n , S n = s n ] . ( 1
+ Δ (α n , p n ) ≥ D T } or {x n + Δ (α n , p n ) < D T }. If {x n + Δ (α n , p n ) ≥ D T },
In this case, a retransmission is requested by Rx. The state of the protocol at time (n+1)T is:

S n+1 = (k n + 1, x n + Δ (α n , p n ))
. This situation is represented in Figure 1.6 by the red dashed arrow leaving s n . Because Δ (α n , P n ) |P n = p n is a continuous random variable, it has a probability density function (pdf) denoted by f Δ|P (x|p n ) that is represented in Figure 1.6. In Figure 1.6, we did not represent a transition s n → (2, x ) since this transition has 0 probability. This analysis can be easily generalized for every other couple (k n , x n ). These case are summarized in Table 1.2. In this table, we enumerate every possible values for S n+1 depending on s n = (k n , x n ) and on the value of Δ (α n , p n ).

To prove equation (1.35), it suffices to remark from Table 1.2 that s n+1 can be written as a deterministic function G of s n , α n , and p n :

s n+1 = G(s n , α n , p n ).
(1.36)

We do not give a more formal expression of G since it will just be an enumeration of the different cases shown in Table 1.2. However, equation (1.36) suffices to prove the Markov property of equation (1.35) (see [START_REF] Meyn | Markov Chains and Stochastic Stability[END_REF]).

Chapter 1. An overview of HARQ-based telecommunication systems The transition probability

x n + Δ (α n , p n ) < D T x n + Δ (α n , p n ) ≥ D T k n < N T -1 (k n +1, x n +Δ (α n , p n )) (0, 0) k n = N T -1 (N T , 0) (0, 0) k n = N T (1, Δ (α n , p n )) (0, 0)
Q(B|s n , p n ) = P [S n+1 ∈ B|S n = s n , P n = p n ] (1.37)
is omitted for the sake of clarity but is given in Appendix A.1 since it will be used in Chapter 3.

For the same reason as in the Type-I HARQ case, the throughput of Type-II HARQ protocols can be computed introducing the following function:

r(s) = ⎧ ⎨ ⎩ b if s = (0, 0) 0 otherwise. (1.38)
Let π = {P n }, the throughput initially defined by equation (1.5) is rewritten using the function r(•) as follows:

η(π) = 1 L lim n→∞ 1 n n-1 i=0 r(S i ), (1.39)
where L is the number of symbols sent in one slot, where r is defined in equation (1.38), and where π = {P n } n∈N is added to show the dependence of the throughput on π (see Table 1.2).

Conclusion

In this section, we have reviewed the different HARQ protocols. In particular, we have given the definitions of the Type-I HARQ protocol, the CC-HARQ protocol, and the IR-HARQ protocol. In the asymptotic context of optimal Gaussian codes, we have presented the classical analysis of the throughput of these protocols in the block-fading channel case.

From this classical analysis, we have established controlled Markov models HARQ protocol has been presented in [START_REF] Levorato | Cognitive interference management in retransmission-based wireless networks[END_REF], the model for Type-II HARQ model is an original contribution (to the best of the author's knowledge). The models proposed in [START_REF] Tuninetti | On the benefits of partial channel state information for repetition protocols in block fading channels[END_REF] and [START_REF] Szczecinski | Adaptive incremental redundancy for harq transmission with outdated csi[END_REF] are similar models to the one presented here for Type-II HARQ protocols except that they do not integrate K n which is useful for taking into account outage events. On the other hand, these models allow us to highlight easily the impact of a power allocation π = {P n } n∈N on the throughput of the HARQ protocols. A more formal definition of π will be given in Chapter 2. Because of this dependence, one can logically wonder if there exists π that maximizes η(π) under peak and average power constraints. This problem can be stated as follows:

sup

π={Pn} n∈N η(π) (1.40) lim n→∞ 1 n n-1 i=0 P n ≤ P A P n ≤ P M
In Chapter 2, we present the Constrained Markov Decision Process (CMDP) framework which is a suitable theoretical framework for solving optimization problems similar to the one given in equation (1.40). This optimization problem is then solved in Chapter 3.

Chapter 2. CMDP: an Introduction

The objective of this chapter is to provide an overview of technical results related to Constrained Markov Decision Processes (CMDPs). These technical results will be used in the next chapters to derive resource allocation for the physical layer in different telecommunication contexts.

Introduction

System

S t+1 = F (S t , A t , W t ) t ← t + 1 Controller A t+1 = π t+1 (S t+1 , A t , S t , . . . ) Disturbance W t Reward/Costs R t = r(S t , A t , W t ) C t = c(S t , A t , W t ) A t+1 S t , A t S t+1

Figure 2.1 -Markov Control Model

Markov Decision Processes (MDPs) naturally appear in contexts in which decisions (or actions) are made sequentially by a controller at some discrete

times (called decision epochs).

The general framework of MDPs is depicted Figure 2.1. The controller observes the state (S t in Figure 2.1) of a system and influences this system through its actions (A t in Figure 2.1). The actions have two effects: they generate some incomes and costs (r and c in Figure 2.1) and they change the dynamical behaviour of the system (F in Figure 2.1). The first effect is a shortterm effect while the second one can have long-term consequences. The goal of the controller is to find a sequence of actions (a policy, π t in Figure 2.1) for maximizing some long-term reward. The CMDPs framework appears when the controller possesses multiple objectives. For example the controller may want to maximize its long-term reward under a long-term cost constraint.

The MDP framework has been introduced by Richard Bellman in the 1950s

(see [START_REF] Bellman | On the theory of dynamic programming[END_REF], [START_REF] Bellman | Dynamic Programming[END_REF]). First applications of MDPs have been proposed early in their development. For example [START_REF] Manne | Linear programming and sequential decisions[END_REF] uses MDPs to solve inventory management problems. Nowadays MDPs and CMDPs have applications in numerous areas. In particular, applications exist in robotics where MDPs has been used for autonomous navigation (see [START_REF] Theocharous | Approximate planning with hierarchical partially observable markov decision process models for robot navigation[END_REF]). In finance MDPs can be used for portfolio and asset management (see [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF] and [START_REF] Bertsekas | Dynamic Programming and Optimal Control, Two Volume Set[END_REF]). MDPs have also found important applications in the area of communication networks. In this area, it is shown in [Feinberg & Shwartz, 2002, Chapter 16] (and references therein) that MDPs are appropriate for handling problems such as: call admission control, buffer management, packet admission control, flow control, congestion control, routing, scheduling. A few MDPs have also been proposed for optimizing physical layer performance for wireless networks. Among others, we can cite [START_REF] Negi | Delay-constrained capacity with causal feedback[END_REF] [ [START_REF] Karmokar | POMDP-based coding rate adaptation for type-i hybrid arq systems over fading channels with memory[END_REF], [START_REF] Djonin | Mimo transmission control in fading channels; a constrained markov decision process formulation with monotone randomized policies[END_REF], [START_REF] Tuninetti | On the benefits of partial channel state information for repetition protocols in block fading channels[END_REF], [START_REF] Levorato | Cognitive interference management in retransmission-based wireless networks[END_REF][START_REF] Levorato | Cognitive interference management in retransmission-based wireless networks[END_REF], and [Michelusi et al., 2013b,a]. This chapter has one principal objective: introducing the CMDP framework in a suitable context for Physical (PHY) layer resource allocation, in particular for HARQ based systems. This objective comprises three sub-objectives.

• We present a general framework that allows us to manage theoretically continuous values. Indeed, in resource allocation problems for the PHY layer, we may have to cope with ACMI, SNR, power, rate and many other continuous variables. This is the goal of Section 2.2.

• We present a general framework that allows us to manage, in practice, these continuous values. Indeed, in the MDPs literature, general theories for handling continuous spaces are often not suited for practical implementation. This sub-objective is fulfilled by Section 2.4 and 2.5. In Section 2.4 we show that the framework described in Section 2.2 can be viewed as an infinite dimensional Linear Programming (LP). In Section 2.5 we provide finite LP approximations for the infinite dimensional LP.

• We present a general framework that allows us to cope with partially observable problems. This is required because in many situations some parameters of the system cannot be observed. This happens often in problems where the system and the controller (in Figure 2.1) belong to two distinct systems: in the context of Chapter 3 transmitter/receiver, and in the context of Chapter 4 primary user/secondary user. The introduction of partially observable problems is the goal of Section 2.6.1.

Introduction to the CMDP framework

Model formulation

A CMDP is defined by a tuple (S, A, U, W, Q, r, c). We will now give the description of each component of this model.

• S is the state space. The elements of S are denoted by s and are called states. Throughout this thesis, we may need to consider finite as well as infinite (possibly not countable) spaces S. So we consider a more general framework including every case. In consequence, we consider that S is a Borel space. In particular, we will often consider S as a subset of R or a finite set or a finite product of these two first cases. When S is a finite or countable space it is endowed with its discrete topology. When S is a subset of R it is endowed with B(S), the Borel σ-algebra. B(S) is the σ-algebra engendered by the compact subsets of S. When S is a finite product of these two kinds of spaces, S is endowed with the product σ-algebra.

• A is a Borel space called the action space. Its elements are called actions.

For every state s ∈ S, the set of admissible actions is denoted by A(s). For every s in S, A(s) is a measurable subset of A.

• U is the space of all admissible state-action pairs. U is the measurable subset of S × A defined as U = {(s, a)|s ∈ S and a ∈ A(s)}. The elements of U are referred to as admissible state-action pairs and are denoted by u.

• W is a Borel space called the disturbance space. For every decision epoch, t ∈ N, the disturbance W t is a random element whose distribution is given by the stochastic kernel on W given S × A: p W (dw|s, a). This means that, on one hand for every (s, a) ∈ S × A, p W (•|s, a) is a probability measure; on the other hand for every B ∈ B(W), p W (B|•) is a measurable function on S × A. The disturbance W t is acting as a "noise" for the temporal evolution of S t . This temporal evolution is governed by the following recurrence equation

S t+1 = g(S t , A t , W t ).
(2.1)

• Q(B|u) is the transition law. It is formally defined as a stochastic kernel on S given U. If the system is in state S t = s and the controller takes action A t = a, the system moves from s to S t+1 with distribution Q(•|s, a). Formally, for every B ∈ B(S), Q(B|s, a) is defined as

Q(B|s, a) = P [S t+1 ∈ B|S t = s, A t = a] . (2.2)
Using equation (2.1), equation (2.2) is expressed as

Q(B|s, a) = P [g(S t , A t , W t ) ∈ B|S t = s, A t = a] . (2.3) • r(s, a
) is called the one-step reward. It is a function from S × A to R. For every s ∈ S and a ∈ A, r(s, a) corresponds to the reward earned when the system is in state s and the controller chooses action a. In some situation, it is possible that the natural definition of the reward also depends on the disturbance. In this case, we define the instantaneous reward as

r(s, a) = S r (s, a, w)p W (dw|s, a). (2.4)
The definition of r given by equation (2.4) was proposed in Bertsekas & Shreve [1978] and will not change the results in the sequel.

• c is vector of n c one-step costs. c is a function from S × A to R nc representing n c costs incurred if the controller chooses action a while the system is in state s. As for r, if the natural definition of this cost vector c also depends on the disturbance w, we introduce

c(s, a) = S c (s, a, w)p W (dw). (2.5)
This definition of c completes the description of the MDP. In the next subsection we present a formal description of policies.

Policies

The formal definition of a policy requires the formal concept of history, thus we first defined this notion. In a second time, we will define the concept of policy and describe various kinds of policies. Finally, we will end this subsection by some additional remarks.

History

At every decision epoch t ∈ N, a history up to time t is the vector defined as

h t = (s 0 , a 0 , s 1 , a 1 , . . . , s t-1 , a t-1 , s t ) . (2.6)
The space of all possible histories up to time t is recursively defined as H 0 = S and H t = H t-1 × U.

Chapter 2. CMDP: an Introduction

Policy

A policy is informally defined as a "sequence of rules" for making decisions depending on an observed history. We will now present different kinds of policies that are the general policies, the Markov policies, the randomized stationary policies, and the deterministic stationary policies.

• Formally, a general policy π is defined as a sequence π = {π t } t∈N where,

for
Π DS ⊂ Π RS ⊂ Π M ⊂ Π.
Other categories of policies can be found in the literature, in particular [START_REF] Altman | Constrained Markov decision processes[END_REF] also distinguishes between randomized Markov and deterministic Markov policies.

Remarks

• The first remark concerns the probability space underlying the random processes {S t } t∈N and {A t } t∈N when the policy π ∈ Π is used by the controller and the initial distribution of S 0 is ν 0 . This probability space is (Ω, F, P ν0 π ) where Ω = (S × A) ∞ and F is the product σ-algebra. The Ionescu-Tulcea theorem (see [Hernández-Lerma, 1989, p. 4]) states that there exists a unique probability measure P ν0 π on Ω such that

P ν0 π [ds 0 , da 0 , ds 1 , da 1 , ds 2 , da 2 . . . ] = ν 0 (ds 0 )π 0 (da 0 |s 0 )Q(ds 1 |s 0 , a 0 ) . . . π 1 (da 1 |s 1 , a 0 , s 0 )Q(ds 2 |s 1 , a 1 )π 2 (da 2 |s 2 , a 1 , s 1 , a 0 , s 0 ) • • • (2.7)
verifying that for all B ∈ B(S) and all C ∈ B(A)

P ν0 π [H ∞ ] = 1 (2.8) P ν0 π [s 0 ∈ B] = ν 0 (B) (2.9) P ν0 π [a t ∈ C|h t ] = π t (C|h t ) (2.10) P ν0 π [s t+1 ∈ B|a t , h t ] = Q(B|s t , a t ), (2.11)
where H ∞ = U ∞ is the set of all admissible histories. In the sequel, E μ π [•] denotes the expectation associated with

P ν0 π [•].
• The second remark is an interesting property of the Markov policies. This property is that every policy π ∈ Π M induces a Markov Chain (MC) on S.

Indeed, let π ∈ Π M be a Markov policy and ν 0 an initial distribution, we have

P ν0 π [S t+1 ∈ B|h t ] = A P ν0 π [S t+1 ∈ B|h t , a t ] P ν0 π [da t |h t ] (2.12) = A Q(B|s t , a t )π t (da t |s t ). (2.13)
The first equality comes from the law of total probability and the second one comes from (2.10) and (2.11). The transition kernel of this MC on S is the following

Q π,t (•|s) = A Q(•|s, a)π t (da|s). (2.14)
For every randomized stationary policy ϕ, this transition kernel is time-homogeneous and will be denoted by

Q ϕ (•|s) = A Q(•|s, a)ϕ(da|s).
(2.15)

Performance criteria

Hitherto, we have defined the CMDP model and different sets of policies. To complete the definition of a CMDP we need to define the long term reward and costs. In the sequel, ν 0 is the initial distribution, π a policy and T a positive real number called horizon. Various kinds of performance criteria are encountered in the literature (see [START_REF] Altman | Constrained Markov decision processes[END_REF][START_REF] Bertsekas | Stochastic optimal control: the discrete time case[END_REF] Hernández-Lerma, 1989; Hernández-Lerma & Lasserre, 1996, 1999]). We now give the most common performance criteria.

We first present a finite-horizon performance criterion. Let r T be some reward depending on the terminal state, the finite-horizon performance criterion Chapter 2. CMDP: an Introduction is defined as

R(ν 0 , π) = E ν0 π T -1 t=0 r(S t , A t ) + r T (S T ) , ( 2.16)
where E ν0 π [•] is the expectation associated with the probability measure P ν0 π [•] defined in equation (2.7).

We now present two different infinite horizon performance criteria. The first one is called the infinite-horizon discounted-cost performance criterion. It is defined as follows

R(ν 0 , π) = lim T →∞ E ν0 π T -1 t=0 α t r(S t , A t ) ,
(2.17)

where α ∈ [0, 1[ is called the discount factor.
We finally present a last performance criterion that will be the one considered in the sequel. This last criterion is called the infinite-horizon average-cost performance criterion. This performance criterion is defined as:

R(ν 0 , π) = lim inf T →∞ 1 T E ν0 π T -1 t=0 r(S t , A t ) . (2.18)
As pointed out in [Hernández- [START_REF] Hernández-Lerma | Adaptive Markov control processes[END_REF]], the choice of considering lim inf and not lim in equation (2.18) is motivated by the fact that the limit may not exist. The choice of lim inf over lim sup is on the other hand motivated by the fact that we will consider the maximisation of R(ν 0 , π) and that lim inf is somewhat similar to considering a worst-case scenario. Similarly, for long-term costs, it will be preferable to use lim sup to consider a worst-case scenario.

Consequently, the long-term cost is defined as:

C(ν 0 , π) = lim sup T →∞ 1 T E ν0 π T -1 t=0 c(S t , A t ) . (2.19)

Constrained optimisation problem

Henceforth, the initial distribution ν 0 is supposed to be known. The constrained optimization problem associated with the CMDP is the following:

R (ν 0 ) = sup π∈Π R(ν 0 , π) (2.20) s.t. C(ν 0 , π) ≤ V (2.21)
In view of future applications, we are interested in finding R (ν 0 ) as well as finding an optimal policy π (if it exists). An optimal policy π ∈ Π is a policy 2.3. Existence of an optimal policy 39 verifying equations:

R(ν 0 , π ) = R (ν 0 ) (2.22) C(ν 0 , π ) ≤ V. (2.23)
In the sequel, Θ represents the set of all admissible policies:

Θ = {π ∈ Π : C(ν 0 , π ) ≤ V} . (2.24)
The next sections of this chapter will be devoted to giving sufficient conditions for the existence of an optimal policy π in Θ. In the sequel we will also show that the optimization problem (2.20) is equivalent to an infinite dimensional LP. We then show that finite approximations of this LP can be performed to obtain "near-optimal" policies. Finally we will show that these finite approximations are asymptotically optimal.

Existence of an optimal policy

The goal of this section is to provide sufficient conditions, that can be checked in practical applications, for the existence of an optimal policy for equation (2.20). Every result shown in this section has been shown in [START_REF] Kurano | Constrained markov decision processes with compact state and action spaces: the average case[END_REF]; in consequence, this chapter is highly inspired by this article. In this section, we first provide assumptions that will we be our theoretical framework, not only for this section but also for the following sections. Based on these assumptions and on [Hernández-Lerma, 1989], we first remind some general properties about policies in Π RS when the CMDP is ergodic. We then couple these properties together with properties on the components of the CMDP to prove that Π RS is a dominating class of policies. We finally prove that an optimal policy exists within Π RS . This methodology, to prove the existence of an optimal policy, has the same structure as in [Hernández-Lerma & Lasserre, 1996] and [Hernández-Lerma & Lasserre, 1999] for MDPs, [START_REF] Altman | Constrained Markov decision processes[END_REF] for countable CMDPs, and [START_REF] Kurano | Constrained markov decision processes with compact state and action spaces: the average case[END_REF]] and [Hernández- [START_REF] Hernández-Lerma | Constrained average cost markov control processes in borel spaces[END_REF] for Borel spaces CMDPs.

Assumptions on the CMDP model

As far as we know, it is impossible to prove the existence of a solution for the problem (2.20) in the general case depicted in Section 2.2. On the other hand, under mild assumptions we will show that the optimization problem (2.20) has a solution. This subsection is devoted to the exposition of these assumptions. we will say that Q verifies the weak Feller property, or simply Q is weak feller.

(e) For every policy ϕ ∈ Π RS , the random process {S t } n∈N is a uniformly ergodic Markov chain (see [START_REF] Meyn | Markov Chains and Stochastic Stability[END_REF]).

Assumptions

Properties of randomized stationary policies

Assumption 2.1(e) (the uniform ergodicity assumption) implies that for every ϕ ∈ Π RS there exists a unique probability measure on S denoted by

Q ∞ ϕ , such that Q ∞ ϕ (B) = S Q ϕ (B|s)Q ∞ ϕ (ds). (2.26)
For every ϕ ∈ Π RS the n step transition kernel recursively defined as

⎧ ⎨ ⎩ Q 1 ϕ (B|s) = Q ϕ (B|s) Q n ϕ (B|s) = S Q n-1 ϕ (B|s )Q(ds |s) (2.27) converges to Q ∞ ϕ (B) in the Total Variation norm (TV-norm) at a geometrical rate: there exist ρ ∈ [0, 1[ such that Q ∞ ϕ -Q n ϕ T V ≤ 2ρ n .
(2.28)

In the literature, ρ is called the ergodicity rate. For every signed measure μ, the TV-norm is the norm defined as

||μ|| T V = sup B∈B(S) μ(B) -inf B∈B(S)
μ(B).

(2.29)

For two probability measures μ 1 and μ 2 , ||μ 1μ 1 || T V is given by

||μ 1 -μ 2 || T V = 2 sup B∈B(S) |μ 1 (B) -μ 2 (B)| . (2.30)
The last consequence of the uniform ergodicity condition is that the longterm functions (R(ν 0 , ϕ) and C(ν 0 , ϕ)), are independent of ν 0 and are expressed using the Law of Large Numbers (LLN) by

R(ϕ) = S×A r(s, a)ϕ(da|s)Q ∞ ϕ (ds), (2.31)
C(ϕ) = S×A c(s, a)ϕ(da|s)Q ∞ ϕ (ds).
(2.32)

Domination of randomized stationary policies

This section is devoted to showing that Π RS is a dominating class of policies for the optimization problem (2.20). This is the statement of the following lemma:

Lemma 2.1. Under Assumptions 2.1, Π RS is a dominating class of policies.
Proof. This domination property is proved by showing that for every policy

π ∈ Π, there exists ϕ ∈ Π RS such that ⎧ ⎨ ⎩ R(ϕ) ≥ R(ν 0 , π) C(ϕ) ≤ C(ν 0 , π).
(2.33)

For every initial distribution ν 0 and every policy π ∈ Π, an occupation measure is defined as where

μ t (U ) = 1 t t-1 j=0 P ν0 π [(s j , a j ) ∈ U ] , ∀U ∈ B (S × A) . ( 2
Ω RS = Ω ∩ Π RS .
A second consequence of Lemma 2.1 is that R is independent of ν 0 . This is due to the fact that for every ϕ ∈ Π RS , R(ν 0 , ϕ) = R(ϕ) and C(ν 0 , ϕ) = C(ϕ).

Existence of a solution

We now conclude this section by showing that there exists a solution to the optimization problem (2.20).

Infinite Linear Programming

In Section 2.3 we have shown that there exists an optimal policy ϕ ∈ Π RS for the optimization problem (2.20). In this section, we will show that under Assumption 2.1, the optimization problem (2.37) is equivalent to an infinite dimensional LP. As it is shown in [Hernández-Lerma & Lasserre, 1996] for unconstrained MDPs, the main idea is to embed Ω into suitable vector spaces.

Dual pairs of vector spaces

In this subsection, we provide a complete description of the different vector spaces that will be used through this section. However, we will not present a general description of LP on general vector spaces. For more information about LP on general spaces, one can refer to [START_REF] Anderson | Linear programming in infinite-dimensional spaces: theory and applicationsa[END_REF] To correctly define the concept of LP on general vector spaces, we will need some definitions and notation. First, let F(U) be the vector space of bounded measurable functions on U, i.e. the set of all measurable functions v on U such that sup

(s,a)∈U v(s, a) < ∞. (2.42)
Let M(U) be the vector space of all bounded signed measures concentrated on U, i.e. the set of measures m verifying Under these conditions (M(U), F(U)) is a dual pair. Under similar conditions, the pair (M(S), F(S)) is also a dual pair. We now use these vector spaces to define an equivalent LP for the optimization problem (2.37).

||m|| T V < ∞, (2.43) m(U c ) = 0, ( 2

LP associated with CMDP

In this subsection, we prove that the optimization problem (2.37) is equivalent to a LP on M(U). This approach to solve CMDP on Borel spaces is mainly inspired from the following works:

m(B × A) - S×A Q(B|s, a)m(d(s, a)) = 0. (2.46)
then there is a policy ϕ ∈ Π RS such that for all

B ∈ B(S), Q ∞ ϕ (B) = m(B × A).
Proof. For every probability measure m in M(U), there exists a stochastic kernel ϕ on A given S so that m is disintegrated as We now show that the optimization problem (2.37) is equivalent to an infinite dimensional programming. First, let L 0 be the linear map from M(U) to M(S) defined as follows: ,a)m(d(s,a)).

m(B × C) = B ϕ(C|s) m(ds), ∀B ∈ B(S), C ∈ B(A), ( 2
L 0 m(B) = m(B × A) - S×A Q(B|s
( (m, α), (r, 0) (2.50)

s.t. L 0 m = 0 m, 1 = 1 m, c j + α j = V j , ∀j ∈ {1 . . . n c } (m, α) ∈ M + (U) × R nc .
In equation (2.50), for every

(m, x) ∈ M(U) × R nc and (v, y) ∈ F(U) × R nc (m, x), (v, y) = m, v + nc j=1 x j y j , (2.51)
where n c is the number of long-term cost constraints.

Proof. The reward function (m, α), (r, 0) is already linear. In consequence, to show that equation (2.50) defines a LP, we have to verify that the linear map

L from M(U) × R nc to M(S) × R × R nc defined as L(m, α) = (L 0 m, m, 1 , m, c 1 + α 1 , . . . , m, c nc + α nc ) (2.52)
is continuous. Let L be the adjoint map of L. For every triplet (u, β, λ) ∈ Chapter 2. CMDP: an Introduction

F(S) × R × R nc , L is defined as follows: L(m, α), (u, β, λ) = (m, α), L (u, β, λ) . (2.53)
To show the continuity of the map L, it is sufficient to prove that L defines a map from F(S) × R × R nc to F(U) × R nc . In our case, under Assumption (2.1), this trivially holds. Indeed, one can easily verify that L is the map defined as:

L (u, β, λ) = ⎛ ⎝ u(s) - S u(s )Q(ds |s, a) + β + nc j=1 λ j c j (s, a), λ ⎞ ⎠ . (2.54)
We now use the map L to define the dual LP of (2.50). This dual LP is expressed as:

β = inf (λ,u,β) β (2.55) s.t. β + u(s) ≥ r(s, a) + n C j=1 λ j (V j -c j (s, a)) + S u(y)Q(dy|s, a) λ ≥ 0 (u, β, λ) ∈ F(S) × R × R nc .
In this subsection, we have shown that the optimization problem (2.37) can be viewed as a infinite dimensional LP. We have given this LP and its dual. In the next subsection we will give some properties between the primal LP (2.50) and its dual (2.56).

Properties of the dual LP

In this subsection, we derive some results given in [START_REF] Kurano | Constrained markov decision processes with compact state and action spaces: the average case[END_REF]. In particular, we show that the dual LP is consistent. This means that there exists (u, β, λ) ∈ F(S) × R × R nc admissible for equation (2.56). We then prove that β is equal to R . To finish, we prove that there exists a triplet (u , β , λ ) optimal for the programming (2.56).

We first prove that under Assumption 2.1, the dual LP (2.56) is consistent.

To prove this consistency we just note that, because of the boundedness of the function r, (0, r M , 0) is admissible. Using classical results on LP (see [START_REF] Anderson | Linear programming in infinite-dimensional spaces: theory and applicationsa[END_REF]) we have that:

β ≥ R . (2.56)
This property is called weak duality. We will now show that this weak duality Proof. The proof of this theorem is based on a result given in [START_REF] Anderson | Linear programming in infinite-dimensional spaces: theory and applicationsa[END_REF]]. This result is the following: proving the closeness of the set H defined hereafter is equivalent to proving Theorem 2.3.

H = (L(m, α), (m, α), (r, 0) + ι) , m ∈ M + (U), α ∈ R nc + , ι ∈ R + (2.57)
The closeness of H is proven considering three sequences {m n } n∈N ,{α n } n∈N , {ι n } n∈N such that as n → ∞:

m n (U) → a 1 (2.58) L 0 (m n ) → m 1 (2.59) m n , r + ι n → r 1 (2.60) m n , c j + α j,n → v j , ∀j ∈ {1 . . . n c } (2.61)
and showing that there exists (m, α, ι) such that

m(U) = a 1 (2.62) L 0 (m) = m 1 (2.63) m, r + ι = r 1 (2.64) m, c j + α j = v j , ∀j ∈ {1 . . . n c } . (2.65)
This proof is identical to the one proposed in [Hernández-Lerma & Lasserre, 1996] and is omitted here.

We now prove that there exists a triplet (u , β , λ ) optimal for the programming (2.56). This property is called strong duality.

Assumption 2.2 (Slater Condition).

There exists a policy ϕ 0 ∈ Π RS such that C(ϕ 0 ) < V.

R = inf λ≥0 sup ϕ∈Π RS ⎛ ⎝ R(ϕ) + nc j=1 λ j (V j -C j (ϕ)) ⎞ ⎠ (2.66)
The proof of this proposition is given in the proof of Theorem

λ ≤ r M -R(ϕ 0 ) sup j∈[1,nc] V j -C j (ϕ 0 ) , ( 2

.67)

where ϕ 0 is the policy of Assumption 2.2.

Proof. This inequality is inspired by a similar inequality proposed in [Altman, 1999, equation (13.4)]. However, since our proof is slightly different, it is given as follows. Let (β , λ , u ) be an optimal triplet for the dual LP. From Proposition 2.1 we obtain sup

ϕ∈Π RS ⎛ ⎝ R(ϕ) + nc j=1 λ j (V j -C j (ϕ)) ⎞ ⎠ ≤ R = r M (2.68)
where the second inequality comes from the boundedness of r(s, a). In particular, for the policy ϕ 0 of Assumption 2.2 we have

R(ϕ 0 ) + nc j=1 λ j (V j -C j (ϕ 0 )) ≤ r M .
(2.69)

Because, we have C(ϕ 0 ) < V and λ ≥ 0, we obtain that for every i ∈ [1, n c ]

λ i ≤ λ , 1 ≤ r M -R(ϕ 0 ) min j∈[1,nc] V j -C j (ϕ 0 ) , ( 2.70)
where 1 = (1, 1, . . . , 1) is the vector composed by n c ones.

In this section we have proved that the nature of the optimization problem (2.37) is a LP on the infinite dimensional space of bounded measures. We have also shown that the dual of this LP is consistent, solvable, and that there is no duality gap. On the other hand, this formulation does not provide an optimal policy for the optimization problem (2.37). However, this formulation can be used to propose approximations for the optimal policy. This is the object of the next section.

Discrete Approximations 49

Discrete Approximations

It has been shown in [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF]] that a continuous (unconstrained) MDP can be approximated by solving discrete (and finite) MDPs. Their method first defines a finite partition of the state and action spaces. Afterwards, they propose a finite MDP on the finite partition. This new MDP is discrete and finite; consequently it can be solved numerically. Finally they prove that the procedure converges to a solution of the continuous MDP when the grid becomes finer. To prove this result, they propose a new MDP which has the same state space as the original MDP and which is equivalent to the discrete one. This method is schematically represented in Figure 2.2. We now show that this procedure is still valid for CMDPs. This chapter has been inspired by the work [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF]. [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF]. The initial CMDP is represented in red. The discrete version of the CMDP is represented in green. In blue is a intermediary problem that is equivalent to the discrete CMDP (green) but has the same state space as the continuous problem (red). A,U,Q,r,c) be a CMDP defined similarly as in Section 2.2. In this model, W is omitted since it only plays an indirect role for discretization results. Indeed, the disturbances have been considered only for the definitions of Q, r and c. In the rest of this section, we suppose that Assumption 2.1 holds as well as Assumption 2.2, so that every result proved in the previous sections remain valid. In particular, we assume that S and A are compact. To simplify the exposition, we will assume that S = [0, [START_REF] Stiglmayr | Adaptive coding and modulation in OFDM systems using BICM and rate-compatible punctured codes[END_REF] ns and A = [0, 1] na . This method Chapter 2. CMDP: an Introduction remains valid for any CMDP with S and A compact subsets of R ns and R na , respectively. This method can be also extended if S is a subset of a compact set of R ns (see [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF]).

Discrete approximation of a CMDP

Let (S,

Inspired by the work of [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF], we define two CMDPs. The first one is (S, Ãh , Ũh , Qh , rh , ch ). This CMDP is built on the same state space as the initial CMDP. The second CMDP is ( Sh , Ãh , Ũh , Qh , rh , ch ), it is a discrete and finite CMDP. This second CMDP is equivalent to (S, Ãh , Ũh , Qh , rh , ch ) except that it can be numerically solved using finite LP. These two CMDPs are described as follows.

• Let n h > 1 be the number of sets constituting the partition of [0, 1]. Since we consider a uniform grid, the grid size is defined as h = n -1 h . For this h, let I h be the partition of [0, 1] constituted by the sets of the form [jh, (j + 1)h[ and by the set [(n h -1)h, 1]. By extension, the space S is then partitioned as follows:

S h = {I 1 × I 2 × . . . I ns |I j ∈ I h } .
S h is composed by a finite number of sets which are denoted as

S i h for i ∈ [0, n h n s -1].
For every set of S h , we choose a representative. Let si be the representative of the set S i h for every i ∈ [0, n h n s -1]. For every s ∈ S, S h (s) is the element of S h to which s belongs. Similarly, for every s ∈ S we define sh (s ) the representative of the set S h (s ). Sh denotes the set of all representatives.

• The action set A is discretized so that every ã ∈ Ãh can be written as a vector of size n a with all its coordinates multiple of h. For every s ∈ S, the set Ãh (s ) is defined as follows:

Ãh (s ) = ã ∈ Ãh | ||u -ũ|| ∞ ≤ h 2 for some u ∈ U (s h (s )) . (2.71)
The set of all admissible state-action pairs is defined as Ũh = (s, ã)|s ∈ S and ã ∈ Ãh (s) .

• In this section, we will suppose that Q has a density Q(s |s, a) with respect to the Lebesgue measure. The density Qh (s |s, ã) is defined as follows

Qh (s |s, ã) = 1 h S h (s ) Q(s |s h (s), ã)ds (2.72)
• Finally, the reward and cost functions are defined as

rh (s, ã) = r(s h (s), ã) (2.73) ch (s, ã) = c(s h (s), ã) (2.74)

Assumptions

Obtaining results on the convergence of discrete states and action approximations requires assumptions that are stronger than Assumption 2.1. In this section, Assumption 2.1 is then replaced by Assumption 2.3 defined as follows.

Assumption 2.3.

(a)

The spaces S = [0, 1] ns and A = [0, 1] na , respectively.

(b) For all s, s ∈ S and a, a ∈ A, there exist r M and K r such that r is a bounded by r M and r is a K r -Lipschitz function:

⎧ ⎨ ⎩ |r(s, a)| ≤ r M |r(s, a) -r(s , a )| ≤ K r ||(s, a) -(s , a )|| ∞ .
(2.75) (c) For all j ∈ {1, ..., n c }, for all s, s ∈ S and a, a ∈ A, there exist M cj and K cj such that c j is a bounded by c M,j and c j is K cj -Lipschitz function:

⎧ ⎨ ⎩ |c j (s, a)| ≤ c j,M |c j (s, a) -c j (s , a )| ≤ K cj ||(s, a) -(s , a )|| ∞ .
(2.76) (d) For all s, s ∈ S and a, a ∈ A, there exists K Q such that Q is K Q -Lipschitz function in the total variation norm:

||Q(•|s, a) -Q(•|s , a )|| T V ≤ K Q ||(s, a) -(s , a )|| ∞ .
(2.77) (e) For every policy ϕ ∈ Π RS , the MC induced on S by ϕ is a uniformly ergodic.

We note by K the constant defined as

K = max M r , K r , M cj , K cj j∈nc , K Q . (2.78)
Henceforth, the functions r, c j , and Q are all K-Lipschitz and the functions r and c j are bounded by K.

Assumption 2.4. For every s ∈ Sh and every ã ∈ Ãh Qh verifies:

Q(•|s, ã) -Qh (•|s, ã) T V ≤ K q h (2.79)
In [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF], it has been shown that if the density s → Q(s |s, a) is bounded by K and piecewise K-Lipshitz, then the quantized kernel defined by (2.72) satisfies Assumption 2.4.

Solving the discrete CMDP

Suppose that the (unconstrained) MDP (S, A, U, Q, r) verifies Assumption 2.1(e).

It this case, it is shown in [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF]] that the discrete MDP, ( Sh , Ãh , Ũh , rh ) inherits this ergodicity condition (Assumption 2.1(e)). Based on this result the ( Sh , Ãh , Ũh , rh ) has been shown to be solvable and its optimal value R h verifies:

|R h -R | ≤ K h, (2.80)
where h is the grid size and K is a constant depending on K and K Q .

We now extend the result established by [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF] for unconstrained MDPs to the case of CMDPs. Consider first the discretized problem ( Sh , Ãh , Ũh , Qh , rh , ch ).

(2.81)

For every l ∈ [0, N U -1], we denote by s(ũ l ) and ã(ũ l ) the components of ũl on Sh and Ãh respectively; i.e. ũl = (s(ũ l ), ã(ũ l )). Using this notation, we define M as the matrix of size N S × N U which is composed by the following elements:

M i,l = ⎧ ⎨ ⎩ 1, if s(ũ l ) = si 0, otherwise.
Let also L0,h be the matrix of size N S × N U given by L0,h = M -Qh .

(2.82)

Following [START_REF] Altman | Constrained Markov decision processes[END_REF], we have that solving the discrete CMDP is equivalent to solving the following finite LP:

R h = sup m∈R N U Rm T (2.83) s.t. L0,h m T = 0 1m T = 1 C j m T ≤ V j m ≥ 0,
where the notation R, C j and 1 stand for the vectors of size N U containing respectively r(ũ l ), c(ũ l ), and 1 for every l ∈ [0, N U -1]. Suppose now that there exists a solution to the finite LP proposed in equation (4.27) and let m be a solution. From m , we build a policy for the continuous state and action

R h -R ≤ K h. (2.85)
Proof. This proof is given in Appendix B.4.

Partially Observable Markov Decision Processes

System Q Observer Q y t ← t + 1 Controller π t+1 (A t+1 |Y t+1 , A t , Y t , . . . ) Reward/Costs R t = r(S t , A t ) C t = c(S t , A t ) A t+1 S t , A t S t+1 A t Y t+1

Figure 2.3 -Partially Observable Markov Control Model

In many real-life applications, the state of the system S t may not be completely available to the controller. The controller may have access to S t only through an observation Y t . This situation is depicted in Figure 2.3. The Figure 2.3 is similar to 2.1 except that the state evolution is directly denoted by the stochastic kernel Q. Similarly, in Figure 2.3, the observation is also given by a stochastic kernel: Q y . Since the controller has only access to the process {Y t } t∈N its policy takes only into account Y t . The framework that encompasses Chapter 2. CMDP: an Introduction this "partial observability" is called Partially Observable Markov Decision Process (POMDP). In this thesis, we will focus on a particular type of POMDPs where the state space S can be written as X × Y where X and Y respectively represent the non-observable part and the completely observable part of S. In . The state space of this equivalent MDP is the set P(S) and is referred to as the belief space(the set of all probability measures on S). In consequence, solving POMDPs is theoretically the same as solving MDPs.

In this section, we will face three major difficulties that are the following.

• The practical applications considered in Chapter 3 and Chapter 4 consider the long-term average criterion (to compute the throughput). As it is shown in [START_REF] Yu | Discretized approximations for pomdp with average cost[END_REF]], the long-term average case is more difficult to handle than others. Indeed, even if in the general case we can provide equations to solve to obtain an optimal policy, it is generally difficult to guarantee the existence of a solution for these equations. In this chapter, we propose a sufficient condition, based on our applications, for guaranteeing the existence of an optimal solution.

• The second difficulty is that the space P(S) is generally not suited for numerical implementations. When the state space is finite with cardinality |S|, the set P(S) is a continuous space of dimension |S|; in this case, many methods has been proposed (see the survey given in [START_REF] Aberdeen | A (Revised) Survey of Approximate Methods for Solving Partially Observable Markov Decision Processes[END_REF] and references there in). In our case, S is continuous; this makes P(S) to be infinite dimensional and most methods for finite S not appropriate. However, it has been observed in [START_REF] Roy | Finding approximate pomdp solutions through belief compression[END_REF]] that we need not consider the whole space P(S). This is due to the fact that the beliefs (the elements of P(S)) of interest for the application lie in a space of much smaller dimension (this is referred to as "belief compression" in [START_REF] Roy | Finding approximate pomdp solutions through belief compression[END_REF]). Based on that idea, a heuristic method for solving continuous POMDP has been proposed in [START_REF] Zhou | Solving continuous-state pomdps via density projection[END_REF]. Their method is the following: i) project the beliefs on the exponential family of densities, this leads to a MDP of much smaller dimension, ii) solve this low dimensional MDP with classical tools.

• The last difficulty is that most applications proposed for POMDPs/PSI-MDPs are unconstrained. Although there exist methods for handling Constrained-POMDP(see [START_REF] Isom | Piecewise linear dynamic programming for constrained pomdps[END_REF], [START_REF] Kim | Point-based value iteration for constrained pomdps[END_REF], and references therein), they 2.6. Partially Observable Markov Decision Processes 55 are all given in the case of finite state space rarely adaptable to cases with continuous state spaces. In this section we extend the method proposed in [START_REF] Zhou | Solving continuous-state pomdps via density projection[END_REF] to constrained PSI-MDPs.

Partially Observable Model

When adapting the general definition of POMDPs for problems with constraints, we get the following definition. A (constrained) POMDP is defined by a tuple (S, Y, A, Q, Q y , r, c). For ease of presentation, we suppose that the initial state s 0 is known. Each component of the POMDP is defined as follows.

• S is a Borel space called the state space.

• Y is a Borel space called the observation space

• A is a Borel space called the action space. In this section we will suppose that for every state s ∈ S, A(s) = A.

• Q is the transition kernel of equation (2.11):

Q(B|s, a) = P [S t+1 ∈ B|S t = s, A t = a] .
• Q y is the observation kernel. The definition of Q y is the following:

Q y (B|s, a) = P [Y t ∈ B|S t = s, A t-1 = a] , ∀B ∈ B(Y).
• r is the instantaneous reward

• c is the instantaneous cost vector

The classical definition of POMDP only differs from this definition by not having c.In this POMDP context, the controller bases the choices of its actions with the observable history defined as: h t = (s 0 , a 0 , y 1 , a 1 , y 2 , a 2 . . . , y t-1 , a t-1 , y t ) .

(2.86)

The different kinds of policies described in Section 2.2 remain the same except that they are defined on the observable history instead of the complete history.

The long-term reward and cost functions (R(s 0 , π) and C(π, s 0 )) remain also unchanged.

The Partial State Information model

The PSI-MDP model is a particular type of POMDP in which the state space can be written as S = X × Y where X and Y represent the non-observable and fully observable parts of the state space. For clarity of exposition, we will suppose that the spaces S, X , Y, and A are [0, 1] nx , [0, 1] ny , [0, 1] ns , and [0, 1] na , respectively. In addition to these definitions, we will suppose that the Chapter 2. CMDP: an Introduction transition kernel Q possesses a density q with respect to the Lebesgue measure.

Consequently, Q has the following expression Q(B|s, a) = B q(x , y |s, a)dx dy .

(2.87)

In the sequel we decompose q(x , y |x, y, a) as follows q(x , y |x, y, a) = q X (x |x, y, a, y )q Y (y |x, y, a)

(

Equivalent CMDP model

We will now show that the PSI-MDP model (X , Y, A, Q, r, c) presented above is equivalent to a CMDP model (Z, A, Q Z , r , c ) such that:

• the state space Z is P(X ) × Y, where P(X ) is the space of all probability measures on X and Y is the observable part of S,

• the action space is A,

• Q Z is a stochastic kernel on Z given Z × A that will be defined later,

• r (z, a) and c (z, a) are the instantaneous reward and cost functions that will be defined later.

At some decision epoch t ∈ N, let z t ∈ Z be defined as the couple (b x,t , y t ), where b x,t = f (x t |h t ) is the a posteriori distribution of X t given an observable history H t = h t and Y t is the fully observable part of S t . We now give the expression of the stochastic kernel Q Z defined, for every B ∈ B(Z), as

Q Z (B|z t-1 , a t-1 ) = P [Z t ∈ B|Z t-1 = z t-1 , A t-1 = a t-1 ] . ( 2

.89)

To build Q Z , we will first describe the evolution of b x,t , and in a second time we will study the evolution of y t . We will now show that the dynamical evolution of b x,t can be described by means of the following deterministic relationship:

b x,t = H b (z t-1 , a t-1 , y t ).
(2.90)

This relationship (as proved in Appendix B.5) has the following expression:

b x,t (x t ) = X q (x t , y t |x t-1 , y t-1 , a t-1 ) b x,t-1 (x t-1 )dx t-1 X X q (x t , y t |x t-1 , y t-1 , a t-1 ) b x,t-1 (x t-1 ) dx t-1 dx t .
(2.91)

To complete the definition of

Q Z we now build Q Y , a stochastic kernel on Y given Z ×A. Q Y is the probability that Y t belongs to C given that Y t-1 = y t-1 , X t-1 is distributed according to b x,t-1 and the controller chooses action A t-1 . For all C ∈ B(Y), Q Y is defined as follows Q Y (C|z t-1 , a t-1 ) = P [Y t ∈ C|Z t-1 = z t-1 , A t-1 = a t-1 ] , (2.92) = X Q Y (C|x t-1 , y t-1 , a t-1 )b x,t-1 (x t-1 )dx t-1 (2.93)
where Q Y is the marginal distribution of Q defined as

Q Y (C|x t-1 , y t-1 , a t-1 ) = C q Y (y t |x t-1 , y t-1 , a t-1 ) dy t . (2.94)
Consequently, the stochastic evolution of Z t can be described by a stochastic kernel Q Z on Z given Z × A. For every B ∈ B(P(X )) and C ∈ B(Y), Q Z is defined as follows:

Q Z (B × C|z t-1 , a t-1 ) = P [Z t ∈ B × C|Z t-1 = z t-1 , A t-1 = a t-1 ] = C P [B x,t ∈ B|Z t-1 = z t-1 , A t-1 = a t-1 , Y t = y t ] Q Y (dy t |z t-1 , a t-1 ) = C 1 (H b (z t-1 , a t-1 , y t ) ∈ B) Q Y (dy t |z t-1 , a t-1 ) (2.95)
To complete the definition of the equivalent CMDP, (Z, A, Q z , r , c ), it remains to define the one-step reward and cost functions r and c . By analogy to the literature (see [START_REF] Bertsekas | Stochastic optimal control: the discrete time case[END_REF]] and [Hernández-Lerma, 1989])

we define these functions as

⎧ ⎨ ⎩ r (z, a) = X r(x, y, a)b x (dx) c (z, a) = X c(x, y, a)b x (dx), (2.96)
where z = (b x , y).

In the end, we obtain the following CMDP: (Z, A, Q z , r , c ). A history for this CMDP model is referred to as an information vector and is defined as:

ι t = (x 0 , y 0 , a 0 , b x,1 , y 1 , a 1 , . . . b x,t , y t ) , ( 2.97)
where we recall that x 0 is part of the known initial state s 0 . The set of these information vectors is denoted by H ι . A policy for this CMDP is referred to as an information policy. The set of all information policies is denoted by Π ι .

A general policy π ι ∈ Π ι is defined as a sequence π ι = {π ι,t (da t |ι t )} t∈N (see Section 2.2).

The proof of the equivalence of this CMDP and the initial PSI-MDP is the same as the one presented in [START_REF] Arapostathis | Discrete-time controlled markov processes with average cost criterion: a survey[END_REF] hence the complete proof is omitted here. Their proof is done by observing that the beliefs b x,1 . . . b x,t of every ι t can be obtained from a particular h t by using equation (2.91). This is then used to prove that for every π ι , there exists

π o such that E s0 πι [•] = E s0 πo [•]
. This proves that for every π ι , there exists π o such that R(π o , s 0 ) = R(π ι , s 0 ) and C(π o , s 0 ) = C(π ι , s 0 ). Since showing that for every π o , there exists π ι such that R(π o , s 0 ) = R(π ι , s 0 ) and C(π o , s 0 ) = C(π ι , s 0 ), they have proved the equivalence between the initial PSI-MDP and the CMDP (Z, A, Q z , r , c ).

Existence of a solution of the CMDP

We now give sufficient conditions on the initial PSI-MDP so that the CMDP (Z, A, Q z , r , c ) is solvable. These conditions are principally designed so that (Z, A, Q z , r , c ) verifies Assumption 2.1.

(d) H b is a continuous function on Z × A × Y. (e) i) There exists a measure ν Y such that ν Y (Y) > 0 and for all s ∈ S and all

a ∈ A, Q Y (C|s, a) ≥ ν Y (C).
ii) There exists a set C 0 ∈ B(Y) with ν Y (C 0 ) > 0 and a measure m 0 ∈ P(X ) such that for every y ∈ C 0 , z ∈ Z and every a ∈ A, H b (z, a, y) = m 0 . Conditions 2.2(a)-2.2(d) are almost identical to Assumptions of [Hernández- [START_REF] Hernández-Lerma | Adaptive Markov control processes[END_REF]]; the only differences are that we impose the compactness of X and Y which is not required in [Hernández- [START_REF] Hernández-Lerma | Adaptive Markov control processes[END_REF]] and that we do not impose Q Y to be weak Feller since in our case this is obtained automatically by showing that Q is weak Feller. Conditions 2.2(a)-2.2(d) are meant to guarantee that the CMDP given by (Z, A, Q z , r , c ) verifies Assumptions 2.1(a)-2.1(d) (see [START_REF] Hernández-Lerma | Adaptive Markov control processes[END_REF]). In consequence, to prove that the CMDP (Z, A, Q z , r , c ) is solvable, it only remains to prove that it verifies Assumption 2.1(e). As proposed in the following therorem, Assumption 2.1(e) is a consequence of Condition 2.2(e) (to the best of the author knowledge this condition is specific to this thesis).

Theorem 2.6. If Condition 2.2(e) is satisfied, then the CMDP (

Z, A, Q z , r , c ) verifies Assumption 2.1(e).
Proof. The proof of this theorem is given in Appendix B.6.

We have finally shown that Condition 2.2 implies that the CMDP given by (Z, A, Q z , r , c ) verifies Assumption 2.1. Using Theorem 2.1, we have that if there exists π ∈ Π o such that C(π, s 0 ) ≤ V, the CMDP (Z, A, Q z , r , c ) is solvable.

To conclude this subsection, we will do the following remarks:

Remark 2.1. [Hernández-Lerma & Lasserre, 1996, Chapter 6]: If Y is count- able, then Condition 2.

2(c) implies Condition 2.2(d).

This remark will be of practical interest in Chapter 3 and 4. Indeed this remark means that we will only need to prove that Q is weak Feller to prove Condition 2.2(c) and Condition 2.2(d).

Remark 2.2. If there exists a state s 0 = (x 0 , y 0 ) and > 0 such that: for every s ∈ S and every a ∈ A, Q({s 0 } |s, a) > and q X (dx |x, y, a, y 0 ) = δ x0 (dx ), then Condition 2.2(e) is checked.

Proof. This proof is given in Appendix B.7. However, we can do two remarks: i) Q({s 0 } |s, a) > is equivalent to saying that s 0 is accessible from every other states for any actions, and ii) Q X (dx |x, y, a, y 0 ) = δ x0 (dx ) is equivalent to saying that the state s 0 ∈ S is completely observable. This provides a physical interpretation of 2.2: if there is a completely observable recurrent state, then Condition 2.2(e) is checked.

So far, we have given theoretical results concerning PSI-MDPs. In the next subsection we give a heuristic way of solving PSI-MDPs.

Numerical solutions for Partial State Information models

In this section, we do a brief presentation of the heuristic method presented in [START_REF] Zhou | Solving continuous-state pomdps via density projection[END_REF] to approximate continuous (unconstrained) POMDP. Since PSI-MDP are a special case of POMDP, we will present this method from the PSI-MDP point of view. We then prove that without any change, this method can be applied to constrained PSI-MDPs.

The main idea behind the method presented in [START_REF] Zhou | Solving continuous-state pomdps via density projection[END_REF] is that the beliefs b x,t live in a finite dimensional subset of P(X ). Hence they decide to approximate the continuous MDP, (Z, A, Q z , r ) by projecting the beliefs b x,t Chapter 2. CMDP: an Introduction on a space of small dimension. This projected-MDP can then be solved by any usual methods.

Their method is the following. Let Ψ be a set of parametrized pdfs, Ψ = {f (•, θ), θ ∈ Θ 0 }, where Θ 0 ⊂ R n θ . They propose to project the beliefs using the Kullback-Liebler divergence defined as follows (2.100)

D KL (b x ||f ) = X b x (x ) log b x (x ) f (x ) dx . ( 2
From this projection, [START_REF] Zhou | Solving continuous-state pomdps via density projection[END_REF] has proposed to solve the following projected MDP (Z , A, Q z , r ) where each component is defined as follows:

• Z = Θ 0 × Y, • A is unchanged,
• Q z is defined, for every z = (θ , y ) and every y ∈ Y as

Q Z (B × C|z , a) = C 1 (H θ (z , a, y) ∈ B) Q Y (dy|z , a) , (2.101)
where H θ (z , a, y) is the function from Θ 0 × Y × A × Y to Θ 0 defined as

H θ (θ , y , a, y) = θ (H b (f (•, θ ) , y , a, y)) , (2.102) • r is defined as follows: r (θ, y, a) = r (f (•, θ), y, a)
This MDP has a continuous state space of dimension n θ + n y which is finite.

Furthermore, in [START_REF] Zhou | Solving continuous-state pomdps via density projection[END_REF], they propose to take Ψ as a parametrized set of policy from the exponential family of pdfs. In this case n θ is often small, making the whole state of small dimension if Y has a small dimension. Finally, this MDP is solved using any method.

In prevision of telecommunication applications, we need to be able to take into account constraints. The method in [START_REF] Zhou | Solving continuous-state pomdps via density projection[END_REF]] can be extended to constrained PSI-MDP by considering (Z , A, Q z , r , c ), where c is obtain by the same transform as r . This time (Z , A, Q z , r , c ) is a finite dimensional 2.7. Conclusions 61 CMDP. In this thesis, we have applied the method of Section 2.5 to solve this CMDP.

Conclusions

To conclude this chapter, we have done a review on the CMDPs framework. We have in particular introduced the following notions as parts of the definition of a CMDP:

• S is the state space,

• A is the action space,

• U is the space of all admissible state-action pairs,

• W is the disturbance space,

• Q(B|s, a) is the transition law,

• r(s, a) is the short-term reward function,

• c(s, a) is the vector of short-term cost function.

We have introduced the notion of policy and specified the following types of policies:

• Π the general set of policies,

• Π M the set of Markov policies,

• Π RS the set of Randomized Stationary policies,

• Π DS the set of Deterministic Stationary policies.

We have introduced two infinite-horizon average-cost performance criteria, R and C defined as

⎧ ⎨ ⎩ R(ν 0 , π) = lim inf T →∞ 1 T E ν0 π T -1 t=0 r(S t , A t ) C(ν 0 , π) = lim sup T →∞ 1 T E ν0 π T -1 t=0 c(S t , A t ) .
From these performance criteria we have introduced a constrained optimization problem:

R (ν 0 ) = sup π∈Π R(ν 0 , π) s.t. C(ν 0 , π) ≤ V.
We have shown that under Assumption 2.

Perspectives and future works

Because many resource allocation for the PHY layer of telecommunications systems can be seen as a problem where decisions are made sequentially, MDPs (in the wide sense) are an appropriate tool. On the other hand, when using the MDP framework to resource allocation for the PHY layer of telecommunications systems, we generally have to address difficult problems: in fact, in the end, we have considered a setting with: a constrained + partially observable + Borel state and action space + under average-cost MDP. In [START_REF] Yu | Discretized approximations for pomdp with average cost[END_REF],

the partially observable problem with finite state space and long-term averagecost is told to be a difficult problem. In consequence, there are still challenging research to do on MDPs, even after 60 years of abundant research.

In particular, we did not provide conditions so that the projected-CMDP of Section 2.6.4 is solvable. To prove that the proposed approximation can (actually) be solved will be part of future work. Our first idea for this work is that the following condition should suffice:

Condition 2.3.
(a) The Condition 2.2 is verified for the PSI-MDP.

(b) For every function on X v which is bounded and continuous, the function v defined as

v(θ) = X v(x)f (x, θ)dx, θ ∈ Θ 0 (2.103) is continuous on Θ 0 .
The second perspective of this work is the following: it is shown in [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF] that the bounds on the approximations presented in Section 2.5 are loose for h > 0 (even if they are good when h → 0). This means that we cannot 2.7. Conclusions 63 use these bound to determine h that guarantees to be -close to the optimum.

For a lot of applications, this can be a real problem. Methods that provide better approximations and/or better bounds exist in the literature, however they are rarely suited for constrained problems. Finding approximations that are implementable and that provide a good insight on how close we are for the optimal solution is a challenging open problem. In this chapter, we show that the CMDP framework presented in Chapter 2 is an appropriate framework to solve power allocation problems for various HARQ protocols.

Introduction

AMC has been widely adopted for link adaptation to improve the spectral efficiency of modern communication systems. This technique dynamically adapts the modulation (type and size) and coding (rate) parameters to the variations of the channel. In modern wireless standards, AMC is assisted by the use of a Channel Quality Indicator (CQI) feedback. The CQI feedback is a quantized information on the quality of the channel and the parameters of the receiver (including HARQ protocols for example). In CQI-based systems, the transmitter (Tx) selects its modulation and coding schemes according to the CQI. In (see [START_REF] Wan | A fading-insensitive performance metric for a unified link quality model[END_REF] and references therein). The EESM has the advantage of being simple to compute but seems to be less accurate than the MIESM. A trade-off between complexity and accuracy has been proposed more recently in [START_REF] Stupia | A novel link performance prediction method for coded mimo-ofdm systems[END_REF] and is referred to as κ-Effective SNR Mapping (κ-ESM). In every cases (EESM, MIESMor κ-ESM) indexes are all "effective SNRs" and can be interpreted as: the SNR of the equivalent AWGN channel which gives the same FER. The main advantage of such types of CQI is that we only need to know the performance of the coded modulations for the AWGN channel. In the spirit of MIESM, other methods have been proposed based on ACMI that do not require a mapping to an effective SNR. In particular, a mutual information based bit-loading algorithm has been proposed in [START_REF] Li | Mutual-information-based adaptive bit-loading algorithms for ldpc-coded ofdm[END_REF]. In [START_REF] Cheng | Adaptive incremental redundancy [wcdma systems[END_REF], [START_REF] Stiglmayr | Adaptive coding and modulation in OFDM systems using BICM and rate-compatible punctured codes[END_REF], and [START_REF] Pfletschinger | Versatile link adaptation based on mutual information[END_REF]], heuristic methods are proposed for choosing the modulation type and dimensioning the length of incremental blocks for adaptive IR-HARQ protocols. In the same context, a more formal optimization has been proposed for power allocation in adaptive IR-HARQ protocols in [START_REF] Tuninetti | On the benefits of partial channel state information for repetition protocols in block fading channels[END_REF].

In this chapter, we consider the system depicted in Figure 3.1 except that the CQI only conveys information about the state of the HARQ protocol at time n, not about the current channel state. This means that throughout the communication Tx has only OCSI and SCSI. In our case the CQI is a quantized version of the state s n of the HARQ protocol in the feedback channel described in Section 1.4.2. This context has already been proposed in [START_REF] Szczecinski | Adaptive incremental redundancy for harq transmission with outdated csi[END_REF] to propose a rate adaptive IR-HARQ protocol. Our work differs from [START_REF] Szczecinski | Adaptive incremental redundancy for harq transmission with outdated csi[END_REF] in the fact that we propose a power allocation.

The rest of this chapter is organized as follows. In Section 3.2 we will show that the problem of allocating power to optimize the throughput of a HARQ protocol under a constraint on the average power is a CMDP, in the case of Type-I HARQ. We will show that this CMDP verifies the assumptions of Chapter 2. These assumptions imply that we can approximate the solution of the CMDP with finite linear programming. These assumptions also imply that approximations provided by the finite linear programming converge to the optimal power allocation of the initial optimization problem. In Section 3.3, the same analysis is performed for the IR-HARQ protocol, and the CC-HARQ protocol.

Power allocation for the Type-I HARQ protocols

In this section, we propose to analyse, under the scope of CMDPs presented in Chapter 2, the power allocation for the maximization of the throughput under average power and peak power constraints.

CMDP model associated with the Power allocation for the Type-I HARQ protocols

In this subsection, we first introduce the CMDP model associated with the power allocation for the maximization of the throughput under average power and peak power constraints. Secondly, we will show that the proposed CMDP verifies Assumption 2.3. This assumption provides sufficient conditions for proving that the discrete approximations converge to the solution obtained with continuous action space (we will see that in this case S is already discrete). The action space A is defined as the set of available powers to Tx. In our case we will consider A = [P min , P max ]. The powers P min and P max constitute two peak power constraints. Although P max is a classical peak power constraint, P min is a much less classical constraint. In fact, we will see that this constraint has only a theoretical range. We will assume P min > with ≥ 0. We will further suppose that Tx can always use the whole set of powers. This implies that A(s) = A for every s ∈ S and U = S × A.

Definition of the CMDP

1 2 3 0 p o (p n ) p o (p n ) p o (p n ) 1 -p o (p n ) 1 -p o (p n ) 1 -p o (p n ) 1 -p o (p n ) p o (p n )
In Section 1.4.1, we have shown that the state evolution is based on the random GNR: α. Consequently we take W = R + , the set of every possible value for the GNR. For the Rayleigh block fading channel, the channel gain 3.2. Power allocation for the Type-I HARQ protocols 69 α has an exponential distribution with average ᾱ = E [α]. Also, based on the value of α and a, we have given in Table 1.1 the rules of the evolution of the state. These rules have lead to the transition law given in equation (1.33). This transition law has the following expression:

Q(s |s, a) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1 -p o (a) if s = 0 p o (a) if s = s + 1, s < N T p o (a) if s = 1, s = N T , 0 otherwise (3.1)
where p o (a) = P [log 2 (1 + aα) < R]. For the Rayleigh block fading channel p o (a) can be computed analytically as

p o (a) = 1 -exp - 2 R -1 ᾱa . (3.2)
For every s ∈ S and every a ∈ A, we have given the short-term reward as the reward associated with the computation of the (long-term) throughput. This reward has the following expression:

r(s, a) = ⎧ ⎨ ⎩ b if s = 0 0 otherwise. (3.3)
In equation (3.3) we wrote r(s, a) to be faithful to the definition of short-term reward of Chapter 2. However, in our case, r only depends on s.

Similarly to what we have proposed for the short-term reward, we introduce a short-term cost associated with the average power. This cost is simply defined as follows:

p(s, a) = a.

(3.4)

This short-term cost definition concludes the description of the component of the CMDP: ( S,A,U,W,Q,r,c). This CMDP definition also settles the history and policy definitions (see Section 2.2).

Finally, the power allocation problem for maximizing the throughput under peak power and average power constraints can be written under the CMDP formalism as follows. Without loss of generality, we assume that the initial state is s 0 = 0. The throughput of the policy π when the initial state is s 0 is defined as follows

η(s 0 , π) = lim inf T →∞ 1 T E s0 π T -1 t=0 r(S t , A t ) . (3.5)
Similarly to the definition of the throughput, we introduce the average power as

P (s 0 , π) = lim inf n→∞ 1 n E s0 π n-1 i=0 p(S t , A t ) .
Finally, the power allocation problem is written as

η (s 0 ) = sup π∈Π η(s 0 , π) (3.6) s.t. P (s 0 , π) ≤ P A ,
where P A is the average power constraint. Note that in the optimization problem given by equation (3.6), the peak power constraints does not appear explicitly. These constraint are in fact contained in Π because of the definition of A.

Properties of the proposed CMDP model

We now analyse this CMDP model to prove that Assumption 2.3 is verified.

This assumption will, in turn, allow us to build a finite LP that solves the power allocation problem.

Because of the finiteness of S, Assumption

Q(s 0 |s, a) = 1 -p o (a) ≥ 1 -p o (P min ) = exp - 2 R -1 ᾱP min > 0,
where the last inequality holds because P min > 0.

The Finite Linear Programming

In the preceding subsection, we have shown that the CMDP corresponding to the power allocation problem for Type-I HARQ protocol verifies Assumption 2.3. This has mainly two consequences: i) since Assumption 2.3 implies Assumption 3.2. Power allocation for the Type-I HARQ protocols 71 2.1, Theorem (2.1) guarantees that the optimization problem given by (3.6) is solvable at the condition that P A ≥ P min .The condition P A ≥ P min ensures that the power allocation with a constant power of P min is admissible and then that the set of admissible policies (Ω in Theorem (2.1)) is non-empty.

ii) Under Assumption 2.3, Theorems 2.1 and 2.2 imply that the optimization problem given by equation (3.6) is equivalent to an infinite dimensional LP.

We now build the finite LP approximating the infinite LP of Theorem 2.2. To do so, we introduce the following finite CMDP: ( Sh , Ãh , Ũh , Qh , rh , ˜ph ). As we have already observed in the preceding section, for Type-I HARQ, S is already discrete. We then only need to discretize the set A. The discretized action space Ãh is defined, as proposed in Section 2.5, as Ãh = {P min , P min + h, P min + 2h • • • , P min + (N a -1)h = P max } , where P min and P max are the peak powers, N a is the number of actions considered in the discrete set, and h is defined as

h = P max -P min N a -1 . (3.7)
Note that in our case, A is not [0, 1] but the discretization procedure is identical. Moreover, since U = S × A, the set Ũh is in our case, the set S × Ãh . In this case the number of elements contained in Ũh is

N U = N T N a .
Since S is discrete, the discretization of the transition law is trivial: Q is unchanged. To have a more compact notation, we introduce for every ã ∈ Ãh , the notation Qã ; Qã is the transition matrix, parametrized by ã, that is built

as follows: Qã (s, s ) = Q(s |s, ã). (3.8)
Because S is already finite, the reward and cost functions are also unchanged: rh = r and ch = c.

With these notations, the finite LP is finally given by: η = sup

m∈R N U Rm T s.t. s∈S m(s, ã) -Q ãm T = 0, ∀ã ∈ Ãh 1m T = 1 Pm T ≤ P A m ≥ 0,
where R, P and 1 are the vectors of size N U containing respectively r(ũ) for Chapter 3. Power Allocation for HARQ protocols all ũ ∈ Ũh , p(ũ) for all ũ ∈ Ũh and only ones. Once the optimal m is found, the corresponding policy consists in choosing randomly a power in Ãh with a distribution:

ϕ(ã|s) = m (s, ã) s m (s , ã)
.

(3.9)

Simulation results

The finite approximation method detailed in the preceding section has been evaluated by simulation. We consider a HARQ protocol with a maximum number of transmission attempts N T = 5 and an initial rate R = 3 bpcu. In these results, we consider without loss of generality, that the GNR α is exponentially distributed with average ᾱ = 1. When a power allocation is performed, we consider a set Ãh from P min = -10dBW to P max = 10dBW with N a = 128.

In Figure 3.3 we compare three results. These three results are all compared at a given average SN R. Note that since in each slot a n is independent of α n , the average SNR can be computed as

P A ᾱ = P A .
• The first result is depicted in Figure 3.3 as the blue curve with triangle marker. This curve corresponds to the result of the finite LP: η as a function of P A .

• The second result is depicted in Figure 3.3 as the red curve with triangle marker. This curve corresponds to the result of the simulation of the Type-I HARQ protocol using the power allocation ϕ(ã|s) computed thanks to the finite LP. These simulations has been realized by the Monte-Carlo method over 10 4 slots.

• The third result is depicted in Figure 3.3 as the violet curve with square marker. This curve corresponds to the constant power allocation case. This curve represents what is achieved in the classical Type-I HARQ systems. As expected, we observe in Figure 3.3 that the power allocation obtained by means of finite LP, outperforms the constant power allocation. Before drawing general conclusions, we give the same three simulation results for R = 1 bpcu, every other parameters remaining unchanged. With the result given in Figure 3.4, we can remark that the power allocation obtained by the finite LP of the preceding subsection is really efficient for low average SNR. To corroborate this conclusion, we have performed the following simulation: within the same framework as the two preceding simulations, we have computed the throughput for a range of R going from 0.75 bpcu to 5 bpcu. For every average SNR value we only kept the best throughput (among every initial rate R). These results are given in Figure 3.5 and confirm the intuition of the preceding simulation.

This new result leads us to the following conclusion: when dealing with HARQ protocols, choosing the appropriate initial rate R gives in general better results than allocating power. However, in most modern communication systems, the appropriate rate R may not be available among the different coded modulations. In this case, a power allocation is useful to compensate the absence of such coded modulation.

Power allocation for the throughput maximization of Type-II HARQ protocols

In this section, we propose to analyse the power allocation for the maximization of the throughput under average power and peak power constraints for Type-II HARQ based systems.

CMDP model associated with the Power allocation for the Type-II HARQ protocols

Following the same reasoning as the one proposed for Type-I HARQ protocols in the preceding section, we first define every component of the CMDP associated with the power allocation problem for maximizing the throughput of the Type-II HARQ protocols. This CMDP has the following form: (S, A, U, W, Q, r, p) where each component is described in the sequel. In Section 1.4.2, we have analysed the CC-HARQ protocol and the IR-HARQ under the same formalism.

In consequence, we will present every theoretical result of this section under the same framework as in Section 1.4.2; we will specify our analysis only for the simulation results.

Definition of the CMDP

In Section 1.4.2, we have shown that a HARQ protocol can be efficiently modelled using a Markov chain on the space S = {0, . . . , N T } × [0, D T ] where N T is the maximal number of decoding attempts and D T is the decoding threshold. The set S = {0, . . . , N T } × [0, D T ] is the state space of the CMDP. We can already remark that S is compact, which verifies a part of Assumption 2.3(a).

Similarly to what we have presented in Section 3.2, the action space of the CMDP is taken as the set of available power levels for Tx, this set is again A = [P min , P max ]. Again, we will suppose that Tx can use the whole set of powers in each state so that U = S × A. In the sequel we again suppose that P min ≥ with > 0 and that P min ≤ P max . Directly from the definitions of A and U, we can remark that the spaces A and U are compact, which proves that Assumption 2.3(a) is verified.

When the Type-II HARQ protocol is in state s n and when action a n is taken by Tx, we have seen in Section 1.4.2 that the state of the HARQ evolves according to rules defined as in Table 1.2. This table is given again in Table 3.1 for ease of presentation. The only difference between Table 1.2 and Table 3.1 is that in Table 3.1 we use the CMDP notation.

One can note that writing Table 3.1 is equivalent to writing that the random variables S n evolve according to the following deterministic equation: S n+1 = Chapter 3. Power Allocation for HARQ protocols

x n + Δ (α n , a n ) < D T x n + Δ (α n , a n ) ≥ D T k n < N T -1 (k n +1, x n +Δ (α n , a n )) (0, 0) k n = N T -1 (N T , 0) (0, 0) k n = N T (1, Δ (α n , a n )) (0, 0)
F (S n , A n , α n ).
In consequence, the GNR α n plays again the role of disturbance.

The disturbance space W is then defined as the range of the GNR: [0, ∞). The

transition kernel Q is again defined in (A.3). The proof that Q verifies 2.3(d) for the Rayleigh channel is given in Appendix C.2.
The short-term reward associated with the computation of the throughput as well as the short-term cost associated with the computation of the average power are still unchanged compared to the case of Type-I HARQ. The shortterm reward is defined as:

r(s) = ⎧ ⎨ ⎩ b if s = (0, 0) 0 otherwise.
The short-term cost is defined as: p(s, a) = a.

(3.10)

The reward and the cost functions are again trivially bounded and Lipschitz continuous functions on U.

We now give the long term reward and cost and the associated optimization problem. Without loss of generality, we assume that the initial state is s 0 = (0, 0). The throughput of the policy π when the initial state is s 0 is defined as

η(s 0 , π) = lim inf T →∞ 1 T E s0 π T -1 t=0 r(S t , A t ) . (3.11)
Similarly to the definition of the throughput, we introduce the average power as

P (s 0 , π) = lim inf n→∞ 1 n E s0 π n-1 i=0
p(S t , A t ) .

Power allocation for the throughput maximization of Type-II HARQ protocols 77

Finally, the power allocation problem is written as

η (s 0 ) = sup π∈Π η(s 0 , π) (3.12) s.t. P (s 0 , π) ≤ P A ,
where P A is the average power constraint. Note that, here also, the peak power constraint does not appear explicitly.

Properties of the proposed CMDP model

We now analyse this CMDP model to prove that Assumption 2.3 is verified.

This assumption will, in turn, allow us to build a finite LP that solves the power allocation problem.

Along with the description of the CMDP problem associated with the Type-II HARQ power allocation, we have shown that Assumption

≥ P [x + Δ (P min α) ≥ D T ] ≥ P [Δ (P min α) ≥ D T ] > 0,
where the second inequality holds because Δ is an increasing function of a, the third inequality holds because x is positive and the last inequality holds because P min > 0.

The finite linear programming

In the preceding subsection, we have shown that the CMDP corresponding to the power allocation problem for Type-II HARQ protocol verifies Assumption 2.3. This again proves that the optimization problem given by (3.12) is solvable at the condition that P A ≥ P min . Under Assumption 2.3, Theorems 2.1 and 2.2 imply that the optimization problem given by equation (3.12) is equivalent to an infinite dimensional LP. We now build finite LP approximating the infinite LP (see Theorem 2.2). To build the finite LP, we introduce the following finite CMDP: ( S, Ã, Ũ, Q, r, p). For this finite CMDP, we drop the index h since it Chapter 3. Power Allocation for HARQ protocols is more convenient in practice to consider two different grids, one of size h for S, the other of size for A. Theorem 2.5 remains unchanged except that we consider that h = min(h, ) → 0 instead of h → 0. We now describe each component of ( S, Ã, Ũ, Q, r, p).

• The partition of S, denoted as S h , is built from the following partition of the set [0, D T ]:

[0, D T ] = N I -2 j=0 [jh, (j + 1)h[ ∪ [(N I -1)h, D T ] , (3.14)
where N I represents the number of sets in the partition of [0, D T ] and h = D T /N I defines the length of each interval. S h is composed by the sets S k,j of the form

S k,j = {k} × [jh, (j + 1)h[ . (3.15)
The set S is the set of every representatives of the sets S k,j . We suppose in this section that the elements of S have the following form:

sk,j = (k, (j + ω)h), ω ∈ [0, 1[ . ( 3.16)
• The discretized action space à is defined, as proposed in Section 2.5, as à = {P min , P min + , P min + 2 • • • , P min + (N a -1) = P max } ,

where P min and P max are the peak powers, N a is the number of actions considered in the discrete set, and is defined as

= P max -P min N a -1 .
(3.17)

• For every sk ,j , sk,j , and ãl , the transition law is discretized as follows:

Q (s k ,j |s k,j , ãl ) = Q ({k } × [j h, (j + 1)h[ |s k,j , ãl ) , (3.18)
where Q is given in Appendix A.1. In the sequel of this section, Q is interpreted as a collection of matrices parametrized by ã ∈ Ã. For all s, s ∈ S and for all ã ∈ Ã these matrices are expressed as follows Qã (s, s ) = Q(s |s, ã).

(3.19)

Power allocation for the throughput maximization of Type-II HARQ protocols 79

With these notations, the finite LP is finally given by: η = sup

m∈R N U Rm T s.t. s∈ S m(s, ã) -Q ãm T = 0, ∀ã ∈ Ãh 1m T = 1 Pm T ≤ P A m ≥ 0,
where R, P and 1 are the vectors of size N U containing respectively r(ũ) for all ũ ∈ Ũ , p(ũ) for all ũ ∈ Ũ and only ones. Once the optimal m is found, the corresponding policy consists in choosing randomly a power in à with a distribution:

ϕ(ã|s) = m (s k,j , ã) s∈ S m (s, ã)
, ∀s ∈ S k,j .

(3.20)

Numerical results

For the Type-II HARQ protocol, we also consider a HARQ protocol with a maximum number of transmission attempts N T = 5 and an initial rate R = 7 bpcu. In these results, we consider without loss of generality, that the GNR α is exponentially distributed with average ᾱ = 1. When a power allocation is performed, we consider a partition of S = [0, R] into N I = 16 parts of equal sizes, we consider a set à from P min = -10dBW to P max = 10dBW with N a = 16. In Figure 3.6 we compare three results. These three results are all compared at a given average SNR. Note that since on each slot a n is independent of α n , the average SNR can be computed as P A ᾱ = P A .

• The first result is depicted in Figure 3.6 as the blue curve with triangle marker. This curve corresponds to the result of the finite LP: η as a function of P A .

• The second result is depicted in Figure 3.6 as the red curve with triangle marker. This curve corresponds to the result of the simulation of the IR-HARQ protocol using the power allocation ϕ(ã|s) computed thanks to the finite LP.

These simulations has been realized by the Monte-Carlo method over 10 4 slots.

• The third result is depicted in Figure 3.6 as the violet curve with square marker. This curve corresponds to the IR-HARQ scheme with constant power allocation.

For the CC-HARQ protocol, we have done the same experiment except that R = 3bpcu. This result is given in Figure 3.7. For both the IR-HARQ and CC-HARQ cases, we can observe the same conclusion as the one for Type-I HARQ protocol: the proposed power allocation works well for medium to low SNR. In order to observe the impact of R, we present in Figures 3.8 and 3.9 the result obtained by maximizing over initial rates from R = 0.1 bpcu and R = 10 bpcu.

From these simulation results, we draw the exact same conclusion as for the Type-I HARQ: choosing the appropriate initial rate R gives in general better results than allocating power.

The Partially Observable problem

In this subsection, we consider a system based on the Type-II HARQ protocol.

The only difference with the preceding section is that we now consider that the CQI only conveys the classical 1-bit feedback: ACK/NACK. This model is depicted in Figure 3.10 and is the one described in Chapter 1 except that we consider that the ACK/NACK bits are also used for power allocation.

Let S n = (K n , I n ) ∈ S be the random variable representing the state of the Type-II HARQ protocol at time nT . This state is defined in the preceding section. From the ACK/NACK bits, Tx can only infer K n indeed, from the definition of K n given in Section 1.4.1, one can observe that it is sufficient to "count" the NACK bits and to observe the ACK bits. On the other hand, the random variable I n is non-observable from Tx by using only the ACK/NACK bits. Based only on this observation, we want to find the power allocation that maximizes the throughput of the Type-II HARQ protocol under the peak and average power constraints. This problem is the following:

η (s 0 ) = sup π∈Πo η(s 0 , π) s.t. P (s 0 , π) ≤ P A ,
where Π o is only the observable history (the history containing only the present and past values of K n and the past values of A n (the actions).

Since the corresponding completely observable problem has been shown to be a CMDP (see preceding subsection), it is logical to consider this problem as a PSI-MDP. This PSI-MDP is the following (X , Y, A, Q, r, c) where each component is defined as follows:

-

X n = I n /D T , • Y = {0, 1, . . . , N T } is the observable space. In this case, Y n = K n ,
• A = [P min , P max ] is the action space defined in the preceding subsection,

• Q is the transition law defined in the preceding subsection,

• r is the instantaneous reward for the throughput η defined in the preceding subsection, • p is the instantaneous cost associated with average power P defined in the preceding subsection.

The observable history is defined as in Section 2.6.1,

h o,t = (s 0 , a 0 , y 1 , a 1 , y 2 , a 2 . . . , y t-1 , a t-1 , y t ) .
The set of all the histories of size t is denoted by H o,t . Note that every history in H o,t only considers the ACK/NACK through the y j , j ∈ [1, t].

Following the method presented in Section 2.6.2, we know that we can con- • Z = P(X ) × Y where P(X ) is the set of every probability measures on X and Y = {0, 1, . . . , N T }. • A is the action space and is unchanged compared to the above definition.

• Q Z is the transition matrix for Z t , defined by equation (2.95).

• r is defined as So far, we have converted the initial PSI-MDP problem into a CMDP problem and we have proved that this new CMDP is solvable. To solve numerically this PSI-MDP, we have used a method that is similar to the method presented in Section 2.6.4. We have projected the beliefs (the elements of P(X )) on the parametrized set of Beta(θ 1 , θ 2 ) laws. The Beta laws belong to the exponential set of densities. For every θ 1 > 0, θ 2 > 0, if X is a random variable with distribution Beta(θ 1 , θ 2 ), its pdf f (x; θ 1 , θ 2 ) is defined as follows:

⎧ ⎨ ⎩ r (z, a) = X r(x,
f (x; θ 1 , θ 2 ) = x θ1-1 (1 -x) θ2-1 1 0 x θ1-1 (1 -x) θ2-1 dx , x ∈ [0, 1] . (3.24)
The choice for Beta laws is motivated by the two following facts: i) the set X = [0, 1], ii) using the method of moments (see [START_REF] Kay | Fundamentals of statistical signal processing[END_REF]) instead of the

Conclusion 85

Kullback-Liebler divergence (used by [START_REF] Zhou | Solving continuous-state pomdps via density projection[END_REF]), allows us to have a compact parametrization of the Beta laws. Indeed, the method of moments is based on the fact that we can compute the parameters (θ 1 , θ 2 ) of a Beta distribution from the mean m and variance v of X by the following transformation

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ θ 1 = m m(1 -m) v -1 θ 2 = (1 -m) m(1 -m) v -1 .
(3.25) Furthermore, if X has a distribution Beta(θ 1 , θ 2 ), its mean m and variance v verify that:

( m, v) ∈ Θ mv = [0, 1] × [0, 0.25] .
So instead of parametrizing the set of Beta laws by (θ 1 , θ 2 ) as in Section 2.6.4, we will use the same set with ( m, v). We have finally solved the CMDP problem (Θ mv × Y, A, Q Z , r , p ) using the method proposed in Section 2.5.

The result of this method is presented in Figure 3.11. These results has been computed by discretizing Θ mv with a uniform grid of 100 possible values for m, 100 possible values for v, and only N a = 16 possible powers for Tx. The results computed by the projected-CMDP are also compared with simulation results obtained by simulating the policy found by the method of Section 2.5 applied to the projected-CMDP. Similar results for the case of the CC-HARQ protocol are presented in Figure 3.12.

In both cases, we observe that the policies found by solving the projected-CMDP perform well; these policies outperform the results obtained by the classical Type-II HARQ methods and are close to the performance obtained with complete observability. The main advantage of these methods is that they require only 1-bit of feedback. This brings us to the following conclusion, for the case where the initial rate R cannot be optimized, we can find power allocation policies that perform close to the completely observable CMDP(that required multiple bits CQI) without changing anything to the HARQ protocol.

Conclusion

In this section, we solved the problem, proposed in Chapter 1, of finding the power allocation that maximizes the throughput of an HARQ protocol under peak and average power constraints. We have studied this power allocation problem for the Type-I HARQ protocol, the IR-HARQ protocol, and the CC-HARQ protocol. The approach proposed in this chapter consists in applying the CMDP tion of the HARQ protocols proposed in Chapter 1. In any case, the policies found thanks to the discretization procedure presented in Section 2.5 have been compared with their simulations counterparts. From these simulations, we have shown that when the initial rate R can be optimized, the gain of performing power allocation is limited. This results tend to corroborate the affirmation done in [START_REF] Szczecinski | Adaptive incremental redundancy for harq transmission with outdated csi[END_REF].

For the two Type-II HARQ protocols, we have considered two different situations: i) the state of the HARQ protocol is perfectly known by Tx or ii) only the number of attempts is known at Tx. The first case has been solved by applying the discretization procedure described in Section 2.5 for the corresponding CMDP. The second case is proposed as a PSI-MDP of the case i). We have provided simulation results showing that the degradation caused by the absence of multiple bits feedback is low.

In [START_REF] Szczecinski | Adaptive incremental redundancy for harq transmission with outdated csi[END_REF], an adaptive IR-HARQ protocol is proposed.

Their protocol adapts the size of the retransmissions according to some unquantized feedback. In [START_REF] Szczecinski | Adaptive incremental redundancy for harq transmission with outdated csi[END_REF], a constrained dynamic programming approach is proposed to solve the adaptive IR-HARQ. In fact their method can be viewed as a fractional programming between two finite horizon MDPs. With this approach, we could compute their results with N T = 5. These results are given in Figure 3.13 and are compared with the power allocation results proposed in this chapter. The simulation results proposed in Figure 3.13 tend to show that rate adaptation is better suited for improving the performance of the IR-HARQ protocol. On the other hand to be really efficient, the adaptive IR-HARQ proposed in [START_REF] Szczecinski | Adaptive incremental redundancy for harq transmission with outdated csi[END_REF] requires a large variety of coders and a theoretically unquantized feedback. 90 Chapter 4. Resource allocation for SU and HARQ PU (PUs)), cognitive radio has been shown to be a promising technique to improve the efficiency of wireless networks (see e.g. [START_REF] Mitola | Cognitive radio: making software radios more personal[END_REF], [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF], and references therein).

Historically, cognitive radio considered an Opportunistic Spectrum Access (OSA) framework. In this framework, the SUs probe the PUs bandwidth to detect white-spaces. The SUs use agile radios such as Software Defined Radio (SDR) to dynamically move from a white-space to another white-space targeting a zero-interference policy. This zero-interference constrain is relaxed in the spectrum sharing framework (see [START_REF] Etkin | Spectrum sharing for unlicensed bands. Selected Areas in Communications[END_REF], [START_REF] Jovicic | Cognitive radio: An information-theoretic perspective[END_REF]] and references therein) where the SUs can interfere the PUs as long as the degradation of the PUs performance remains within some Quality of Service (QoS) constraints. Spectrum sharing has been the subject of extensive research in recent years (see [START_REF] Asghari | Adaptive rate and power transmission in spectrum-sharing systems[END_REF], [START_REF] Bagayoko | Spectrum-sharing power control with outage performance requirements and direct links csi only[END_REF][START_REF] Bagayoko | Power control of spectrumsharing in fading environment with partial channel state information[END_REF], [START_REF] Etkin | Spectrum sharing for unlicensed bands. Selected Areas in Communications[END_REF], [START_REF] Jovicic | Cognitive radio: An information-theoretic perspective[END_REF], [START_REF] Kang | Sensing-based spectrum sharing in cognitive radio networks[END_REF], [Makki & Eriksson, 2012;Makki et al., 2012[START_REF] Makki | Green communication via power-optimized harq protocols[END_REF], [START_REF] Masmoudi | A closed-form solution to the power minimization problem over two orthogonal frequency bands under qos and cognitive radio interference constraints[END_REF], [START_REF] Tajan | Opportunistic secondary spectrum sharing protocols for primary implementing an IR type Hybrid-ARQ protocol (regular paper)[END_REF], [START_REF] Tannious | Cognitive radio protocols based on exploiting hybrid arq retransmissions[END_REF], [START_REF] Zhang | Optimal power control over fading cognitive radio channel by exploiting primary user csi[END_REF][START_REF] Zhang | On active learning and supervised transmission of spectrum sharing based cognitive radios by exploiting hidden primary radio feedback[END_REF], and references therein).

In this chapter we are interested in a spectrum sharing context where the SU shares the channel with one PU implementing a HARQ protocol. This context is motivated by the fact that from an information theoretical perspective, it has been shown in [START_REF] Eswaran | Bits through arqs: Spectrum sharing with a primary packet system[END_REF] that, by listening to the PUs feedback bits, the SU can infer the throughput-loss of the PU. Furthermore using this information about the throughput-loss, the authors have shown that a non-negligible throughput can be achieved by the SU. This result is important because it means that, in order to be compliant with the SU, the PU only has to broadcast the feedback bits of its HARQ protocol.

Within the proposed context, the case of a PU implementing a Type-I HARQ protocol has been addressed in [START_REF] Levorato | Cognitive interference management in retransmission-based wireless networks[END_REF]. In [START_REF] Levorato | Cognitive interference management in retransmission-based wireless networks[END_REF], a CMDP approach is used to derive an optimal ON/OFF allocation while managing the throughput-loss of PU. In this chapter we propose to address the Type-II HARQ problem. This chapter is organised as follows. In Section 4.2 we present the channel model, the protocol of the PU, the protocol of the SUand we finally propose an optimization problem. In Section 4.3 we show that the optimization problem proposed in Section 4.2 is equivalent to a CMDP, we prove the existence of a solution for this CMDP. In Section 4.3, we assume that the SU has access to the complete state of the PU HARQ protocol and uses this state to maximize its own throughput while managing the QoS loss of the PU. In Section 4.4, we propose to solve the problem in which the SU has only access to the PU feedback.

System model

In this section, we give more details on the system presented in Figure 4.1. We present the HARQ protocol that the PU is using in order to retrieve erroneous packets. We also present the power and rate allocation of the SU. The protocols of the PU and the SU are studied in terms of throughput. Similarly to [START_REF] Jovicic | Cognitive radio: An information-theoretic perspective[END_REF], we consider the network illustrated in Figure 4.1. This network is composed of a PU (with transmitter T x 1 and receiver Rx 1 ) and a SU (with transmitter T x 2 and receiver Rx 2 ). The P U and the SU share a block-fading interference channel. In this context, the signals

Channel Model

x n 1 T x 1 x n 2 T x 2 y n 1 Rx 1 z n 1 y n 2 z n 2 Rx 2 h n
y 1,

The PU model

In this chapter, we consider that the PU implements an IR-HARQ protocol, with a maximum of N T,1 attempts, with a constant power p 1 , and with an initial rate of r 1 (see Section 1.3.3). Additionally to the classical assumptions on HARQ protocols given by Assumption 1.1, we suppose that the PU is compliant for the SU. In our situation, it means that the PU is aware of the possible presence of the SU and sends its feedback bits over a common broadcast channel so that the SU can hear it. On the other hand the PU does not manage the SU and consequently is oblivious to the presence (or absence) of the SU. For the sake of clarity, all assumptions that we have made about the PU are listed in Assumption 4.1. (f) the PU is oblivious to the presence (or absence) of the SU, in particular Rx 1 processes the SU signal as noise.

As it has been presented in Section 1.4.2, the state of the IR-HARQ protocol of the PU, at time nT , can be represented by two variables

s n = (k 1,n , i 1,n ).
The component k 1,n can take one of the following N T,1 + 1 values

• 0: T x 1 starts the transmission of a new information packet after a successful decoding (ACK),

• 1: T x 1 has done 1 attempt and a NACK bit is received,

• 2: T x 1 has done 2 attempts and a NACK bit is received, . . .

• N T,1 : T x 1 has done N T,1 attempts and NACK is received. This state corresponds to an outage event and, in consequence, to the start of the transmission of a new information packet.

The state component i 1,n represents the ACMI at Rx 1 . We only consider the throughput η 1 as main figure of merit for the performance of the PU. This throughput will be denoted as η 1 and is defined as

η 1 (π 2 ) = lim inf t→∞ 1 t E π2 t-1 n=0 R 1 (s n , p 2,n ) , (4.4)
where R 1 (s n ) is defined as follows

R 1 (s n ) = ⎧ ⎨ ⎩ r 1 , if s n = (0, 0) 0, otherwise (4.5)
and where π 2 is a power allocation of the SU defined in its more general form as a random process π 2 = {p 2,n }. π 2 is written in equation

The SU model

We now describe the model of the SU, starting by describing the CSI assumptions on the SU. We suppose that the SU has partial CSIR: in this case it means that Rx 2 knows h 12,n and h 22,n . We will also suppose SCSI at T x 2 and Rx 2 . In the Rayleigh channel case that is of interest here, SCSI at T x 2 and Rx 2 means that both T x 2 and Rx 2 know every α ij . No CSIT is considered at T x 2 . For the rest of this chapter, we will make the following assumptions on the SUs system.

Associated optimization problem

In this chapter, we assume that the SU potentially changes its transmission parameters (power and rate) in each slot. Theoretically it means that at each time nT , the SU chooses a power p 2,n and a code-rate r 2,n and uses these parameters to transmit data in slot n. Because of the no CSIT assumption, once p 2,n has been chosen by T x 2 , the appropriate choice for r 2,n is given by the following

r 2,n = r 2 (p 2,n ) = max r∈R + rP [log 2 (1 + p 2,n β 2,n ) ≥ r] . (4.6)
This choice for r 2,n ensures to obtain the best instantaneous rate for a given level of interference p 2,n . In the end, it means that, at each slot, the SU only adapts its power p 2,n , choosing its rate by r 2,n = r 2 (p 2,n ).

The performance of the SU is also evaluated considering the throughput.

The SU throughput is defined as

η 2 (π 2 ) = lim inf t→∞ 1 t E π2 t-1 n=0 r 2 (p 2,n ) . (4.7)
In the same way, we also introduce here the SU average power as follows

The completely observable problem

In the preceding section, we have addressed the optimization problem (4.9)

under Assumptions 4.1 and 4.2. To simplify the resolution of this optimization problem, we suppose in this section that, at every time nT , T x 2 and Rx 2 have access to i 1,n , the ACMI at Rx 1 . This access can be done by any means.

In a realistic scenario, one can assume that a Rx 1 sends i 1,n over a broadcast common control channel to be more compliant with the SU. In a more theoretical scenario, one can assume that T x 2 and Rx 2 are genie aided. In any case, since we suppose that the SU has more information about the PU, the obtained results will be an upper bound on the achievable results considering Assumptions 4.1 and 4.2. The last advantage of considering that T x 2 and Rx 2 have access to i 1,n is that, using results of Section 1.4.2, the optimization problem (4.9) can be viewed as a CMDP. An a posteriori consequence of considering this CMDP is that the initial problem, considering Assumptions 4.1 and 4.2, can be thought as a PSI-MDP, this will be the object of Section 4.4.

The CMDP formulation

Similarly to what has been proposed in Chapter 3, we address the optimization problem given in equation (4.9) as a CMDP. The CMDP definition adapted to this problem is the tuple (S, A, W, Q, R 2 , R 1 , P 2 , η 1T , P 2A ) where each component is described as follows.

• The state space: S = {0, 1, ..., N T,1 } × [0, r 1 ] is the set of all possible states of the PU IR-HARQ protocol (see Section 1.4.2 for more details). By construction this state is compact and then verifies Assumption 2.3(a).

• The action space A = [0, P 2M ] is the space of all available powers for T x 2 .

We suppose that for every s ∈ S, A(s) = A so that U = S × A. By construction again A and U are compact which proves Assumption 2.3(a). where the α ij,n are given by equation (4.2), p 1 is the constant primary power and note that we have assumed σ z1 = σ z2 = 1.

i 1,n + Δ (w n , p 2,n ) < D T i 1,n + Δ (w n , p 2,n ) ≥ D T k 1,n = 0 (1, Δ (w n , p 2,n )) (0, 0) 0 < k 1,n < N T -1 (k n +1, i 1,n +Δ (w n , p 2,n )) (0, 0) k 1,n = N T -1 (N T , 0) (0, 0) k 1,n = N T (1, Δ (w n , p 2,n )) (0, 0)

Existence and computation of an optimal policy

In the preceding subsection, we have checked almost every assumptions of Assumption 2.3. The only one missing is Assumption 2.3(e). This assumption is that every policy ϕ ∈ Π RS induces a uniform ergodicity Markov chain on S. To check Assumption 2.3(e), we will verify Condition 2.1(a): "There exists s 0 ∈ S and ∈ R + such that Q({s 0 } |s, a) ≥ 0, with > 0".

To check Condition 2.1(a), we remark that state s 0 = (0, 0) is accessible from every other state. s 0 physically represents a successful decoding of Rx 1 . The fact that s 0 is accessible from every other state means that from every state s, there is always a non-zero probability of a successful decoding at Rx 1 (as long as P 2M is finite). From any state s = (k 1 , i 1 ) ∈ S and an action p 2 ∈ A, using Table 3.1 (or equivalently the expression of Q given in D.3) we have

Q({s 0 } |k 1 , i 1 , p 2 ) = P i 1 + log 2 (1 + p 1 α 11 1 + p 2 α 21 ) ≥ r 1 |i 1 , p 2 ≥ P log 2 (1 + p 1 α 11 1 + P 2M α 21 ) ≥ r 1 > 0. (4.20)
where the first line is obtained by applying the definition of a successful decoding (see Section 1.2.3), and the second equation comes from the positiveness of i 1 and p 2 and from the finiteness of P 2M . This is sufficient to prove that Assumption 2.3(e) holds.

We finally suppose that η 1T < η 1 (ζ 0 ) and P 2A > 0 to guarantee that the set of admissible policies is not-empty. The policy ζ 0 is the policy such that T x 2 always transmits with power p 2 = 0. Using Theorem 2.1, it follows that the optimization problem given in equation (4.9) is solvable: there exists an optimal policy for equation (4.9) within the set Π RS . It also proves that an optimal policy can be found using an infinite dimensional programming.

In the next subsection, we propose a discrete CMDP, that can be solved numerically and leads to an approximation of an optimal policy for the optimization problem (4.9).

Evaluation of the performances of the optimal policy

Similarly to what we proposed in Section 3.3.2, we propose different grids for S and A so we drop the indexes in the definition of the discrete CMDP. We now describe the discretization procedure proposed in Section 2.5. In particular we introduce the following finite CMDP: S, Ã, Q, R2 , R1 , P2 .

The proposed method is almost the same as the one for discretizing the CMDP in Section 3.3.2.

• The set S is built from the following partition of the set [0, r 1 ]:

[0, r 1 ] = N I -2 j=0 [jh, (j + 1)h[ ∪ [(N I -1)h, r 1 ] , (4.21)
where N I represents the number of sets in the partition of [0, r 1 ] and h = r 1 /N I defines the length of each interval. The set S is composed of elements of the following form: sk,j = (k, (j + ω)h), (4.22)

where ω belongs to [0, 1[. • The set of actions is discretized as à = {0, P 2M , . . . , (N A -1)P 2M }, where = 1/N A and P 2M is the SU peak power constraint. • For every sk ,j , sk,j , and ãl , the transition law is discretized as follows:

Q (s k ,j |s k,j , ãl ) = Q ({k } × [j h, (j + 1)h[ |s k,j , ãl ) . ( 4.23)
Q can be interpreted as a matrix of N S lines and N S × N A columns.

• We finally define the reward functions on Ũ as follows

R2 (ũ k ) = R 2 (ũ k ) (4.24) R1 (ũ k ) = R 1 (ũ k ) (4.25) P2 (ũ k ) = P2 (ũ k ). (4.26)
We finally build a finite linear programming based on the method proposed in Section 2.5. Let the notation R 2 , R 1 , P 2 and 1 stand for the vectors of size N U containing respectively R2 (ũ), R1 (ũ) , P2 (ũ) and 1. Using these vectors, we can write the following finite linear programming: For some pairs (η 1T , P 2A ) and some discretization parameters (N S , N A , ω), m may not exist. This happens, in particular, if the linear programming (4.27) is not consistent. In this case, we have considered φ = ζ 0 . This choice is made because ζ 0 is admissible for the problem given in equation (4.9).

η2 = sup m∈R N U R 2 m T (4.27) s.t. s∈ S m(s, ã) -Q ãm T = 0, ∀ã ∈ Ã 1m T = 1 R 1 m T ≥ η 1T P 2 m T ≤ P 2A m ≥ 0.
In the sequel, we will make the difference between η 2 ( φ) and η2 = R 2 m T . η 2 ( φ) corresponds to the SU throughput of the policy φ. The policy φ is a "continuous" policy built from m , solution of the problem (4.27). In a similar way we consider η1 = R 1 m T and η 1 ( φ) for the throughput of the PU, and P2 = P 2 m T and P2 ( φ) for the SU average power.

Influence of ω and N S

In this subsection, we present some simulation results that highlight the impact of ω, N S , and N A . For all the results proposed in this section, we have considered a PU using an IR-HARQ protocol with 3 retransmissions (so that N T,1 = 4), r 1 = 7.12 bits per channel use (bpcu), and a power of p 1 = 10dBW . The channel parameters are ᾱ11 = ᾱ22 = 1 and ᾱ12 = ᾱ21 = 0.5. The secondary user has a peak power constraint P 2M = 10dBW , an average power constraint P 2A = 5dBW .

The parameter ω defines the position of the representative si within the sets S i . Taking ω = 0 is equivalent to considering the PU worst case scenario. Indeed, when the discretized system is in state si , the true state s is in the set S i = {k i } × [j i h, (j i + 1)h[. Taking ω = 0 is equivalent to considering that the state is in j i h, which is the worst case scenario among every state of S i . On the other hand, the case ω → 1 -is equivalent to an optimistic guess on the real state s. In Figure 4.2, we show curves of the SU throughput as a function of η 1T

for ω equal to 0, 0.5, and 0.999. The results presented in Figure 4.2 correspond either to the optimal value of the finite linear programming (dashed lines) or to the simulation of the policy given by the linear programming. put of the PU and the target PU throughput η 1T . The results presented in Figure 4.3 corroborate that the PU throughput is underestimated when ω = 0, correctly estimated when ω = 0.5, and underestimated when ω → 1 -.

We complete these two results by comparing the simulated values of the average power of the SU to the constraint value of P 2A = 5dBW . These comparisons are given in Figure 4.4 for ω = 0, ω = 0.5, and ω → 1 -. As expected, the results obtained when ω = 0.5 are close to the constraint. Surprisingly, we observe that when ω = 0, the constraint is sometimes not respected. On the other hand, when ω → 1 -the simulated values of the average SU power remains within the constraint.

We will now analyse the influence of the parameter N S . This parameter represents the number of states in S. Considering N S → ∞ is equivalent to considering h → 0 therefore high values of N S lead to better approximation of η 1 , η 2 , and P2 . The limiting case is discussed in Section 4.5. Figure 4.5 highlights that the solution of the infinite linear programming can be approximated from below by increasing N S and taking ω = 0. On the contrary, Figure 4.6 indicates that the infinite linear programming can be approximated from above by increasing N I and taking ω → 1 -.

The partially observable problem

In Section 4.3, we have shown that under Assumption 4. The only difference between the framework of Section 4.3 and the one of this section is that, in this section T x 2 and Rx 2 do not know i 1,n . On the other hand, we still consider the PU to be compliant (cf. Assumption 4.1(e)). Hence, by counting the PU ACK and NACK bits, T x 2 and Rx 2 can easily track k 1,n . This framework is then equivalent to the PSI-MDP model presented in Section 2.6.1 where k 1,n is the fully observable part of the PU IR-HARQ protocol and i 1,n is the hidden part of this system.

Let X and Y be defined as the respective sets: X = [0, r 1 ] and Y = {0, 1, . . . , N T,1 }, the PSI-MDP considered in this section is given by the tuple

(X , Y, A, Q, R 2 , R 1 , P 2 ), where A, Q, R 2 , R 1 , P 2 are these of Section 4.3.
To solve this PSI-MDP, wee apply the method proposed in Section 2.6.1: we first convert this PSI-MDP to the CMDP (Z, A, Q Z , R 2 , R 1 , P 2 ) where each component is defined as follows.

• Z = P(X ) × Y where P(X ) is the set of every probability measures on X and Y = {0, 1, . . . , N T }.

• A is the action space and is unchanged compared to the above definition.

• Q Z is the transition matrix for Z t , defined by equation (2.95).

• R 2 , P 2 , and R 1 are defined, for every z = (b i , y) ∈ Z and every a ∈ A, as follows:

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ R 2 (z, a) = X R 2 (x, y, a)b i (dx), R 1 (z, a) = X R 1 (x, y, a)b i (dx) P 2 (z, a) = X P 2 (x, y, a)b i (dx). (4.29)
This CMDP is again projected on the Beta laws parametrized by their mean and variance. We have finally solved the CMDP problem

(Θ mv × Y, A, Q Z , R 2 , R 1 , P 2 )
using the method proposed in Section 2.5.

In this subsection, we present some simulation results that highlight the PSI-MDP performances. We have considered a PU using an IR-HARQ protocol with 2 retransmissions (so that N T,1 = 3), r 1 = 7.12 bits per channel use (bpcu), and a power of p 1 = 10dBW . The channel parameters are ᾱ11 = ᾱ22 = 1 and ᾱ12 = In Figure 4.7 , we observe that the loss due to the absence of knowledge of i 1,n is small (less than 10% of throughput loss for the PU for a given SU throughput). However, the achieved SU throughput is still substantial and is performed by considering uniquely that the SU can hear the 1-bit feedback of the PU IR-HARQ protocol. Finally one can note that although the pdf of the ACMI has been projected on Beta laws, the simulated throughput is still very close to the one obtained using the projection.

Conclusion and Perpectives

In this chapter we have proposed to address the SU power allocation under a throughput-loss constraint for an IR-HARQ based PU. By assuming a compliant PU that broadcasts its feedback bits, we have shown that a significant SU 106 Chapter 4. Resource allocation for SU and HARQ PU throughput can be achieved while mitigating the throughput loss of the PU. We have proposed, in a first time, an upper bound on the SU achievable throughputs by considering that the SU has complete access to the state of the PU. In this case, we have shown that the SU power allocation reduces to a CMDP. This is a direct consequence of the IR-HARQ model proposed in Chapter 1. From this model, we have shown the existence of a solution and proposed a finite LP to approximate this solution. This approximation was simulated. We have in particular observed that in the case ω = 0.5 only a few number of discrete states (N I = 16) are required to obtain an accurate estimation of the optimal policy. In a second time, we have considered the same SU power allocation except that the state of the PU is only accessible to the SU through the PU feedback bits. Although this only information is sufficient for ARQ for the Type-I HARQ protocol (see [START_REF] Levorato | Cognitive interference management in retransmission-based wireless networks[END_REF]), it is not the case for the IR-HARQ protocol considered in our context. In the case of the IR-HARQ protocol, the feedback bits only provide a partial state information. In consequence, this problem has been considered as a PSI-MDP. Using the method proposed in Section 2.6.4, we have given approximations for the PSI-MDP solution. We have in particular observed that a non-negligible throughput can be obtained for the SU.

On the structure of optimal allocation policies

For practical considerations, one can think of some other (simpler) kind of policies. For instance policies with constant power. This kind of policy arises when the feedback of the PU cannot be heard by the SU. In this case, the SU does not have any information on the instantaneous state of the PU IR-HARQ protocol. Since the SU transmitter (T x 2 ) has only SCSI, it will look for the maximal power (to maximize its own throughput) that guarantees the SU throughput target (η 1T ). Figures 4.8 and 4.9 highlight that constant power allocations are the policies that maximize the SU throughput when η 1T = 0 and that there is a gain in using the PU feedback (this effect was pointed out in [START_REF] Eswaran | Bits through arqs: Spectrum sharing with a primary packet system[END_REF]).

One can also consider policies where the only admissible powers are P 2M or 0. These policies are called ON/OFF policies in our paper. These policies are somewhat at the opposite from the policies with constant power. Indeed Figure 4.9 shows that, when P 2M = P 2A , ON/OFF strategies are close to optimal strategies with A = [0, P 2M ]. This result is surprising and we do not have any proof of this optimality even if this fact has been observed in many different contexts (PU, SU and channel setting).

On the admissibility of φ

As we have seen in the simulation results, it may happen that φ lies outside the set Ω of admissible policies for the problem given by equation (4.9). This can be problematic in an HARQ context where we want to guarantee the QoS constraint for the PU. In this case, we propose to build a non-stationary policy π such that, (P1): if φ ∈ Ω, then η 2 (π) = η 2 ( φ), η 1 (π) = η 1 ( φ) and P2 (π) = P2 ( φ), (P2): if φ / ∈ Ω, then π ∈ Ω.

To build π, we solve (4.27) with η 1T = η 1T + 1 and P 2A = P 2A -2 . The parameters 1 > 0 and 2 > 0 are chosen so that η 1T < η 10 and P 2A > 0. T x 2

tracks the following values

⎧ ⎨ ⎩ η 1N = 1 N t-1 n=0 R n 1 , P2N = 1 N t-1 n=0 p n 2 .
Let Φ be the subset of R 2 defined as Φ = (x, y) ∈ R 2 : x ≥ η 1T and y ≤ P 2A . The policy π is built as follows: if (η 1N , P2N ) ∈ Φ, T x 2 uses φ. In every other cases, T x 2 uses ζ 0 . By assumption we have that (η 10 , 0) ∈ Φ. Using the results of [START_REF] Ross | Randomized and past-dependent policies for markov decision processes with multiple constraints[END_REF], we can easily prove that the properties (P1) and (P2) hold. This method is heuristic and more evolved methods should be considered.

On Successive Interference Cancellation

In this chapter, the SU always considers the PU signal as noise. This means that the SU does not need to know the PU codebook and a fortiori the PU sent codeword. Although this is an advantage in terms of confidentiality (SU does not decode the PU messages), methods such that Backward Interference Cancellation (BIC) SIC can dramatically improve the performances of both systems. This was shown in [Michelusi et al., 2013a] in the Type-I HARQcontext.

BIC and SIC techniques are extended in [START_REF] Michelusi | Cognitive access policies under a primary arq process via chain decoding[END_REF]] by introducing Chain Decoding (CD). These techniques have not yet been studied in a Type-II HARQ context but we can show their limit performances.

The limit of the BIC/SIC/CD schemes is attained when there is no interference from the PU to the SU. This limit means that all the interference is correctly removed for every block. This case corresponds to ᾱ12 = 0 in our context. In consequence, the case ᾱ12 = 0 is an upper bound on what is possible using the interference cancellation techniques of [Michelusi et al., 2013a] or [START_REF] Michelusi | Cognitive access policies under a primary arq process via chain decoding[END_REF]. In 4.10 the potential gain of the techniques proposed in [Michelusi et al., 2013a] and [START_REF] Michelusi | Cognitive access policies under a primary arq process via chain decoding[END_REF]] is substantial.

Conclusion

In this thesis we have proposed a CMDP approach to solve the problem of allocating resources for HARQ-based systems. This approach has been suggested because of the sequential evolution of a HARQ protocol. In this thesis, we have applied this approach, not only for the optimization of various HARQ protocols; but we have also considered this approach for problems involving HARQ protocols (even if these are not to be optimized).

In Chapter 1, we have proposed an introduction on the different types of HARQ protocols. In particular, we have presented the Type-I HARQ protocol, the CC-HARQ protocol and the IR-HARQ protocol. The throughput analysis of these three protocols has been proposed in the context of asymptotic Gaussian codebooks. This asymptotic Gaussian codebooks context has allowed us to derive controlled Markov models for representing the state evolution of these protocols depending on a power allocation. We have in particular derived a unified model to handle the CC-HARQ and the IR-HARQ protocols. Finally, the last contribution of Chapter 1 is to define a power allocation problem for optimizing the throughput of an HARQ protocol under peak and power constraints.

In Chapter 2, we have reviewed the existing literature about the general framework on CMDPs. This review not only presents the theoretical framework of CMDPs, but also the practical implementation aspects of CMDPs. In particular, we have given discretization procedures for dealing with approximating CMDPs with continuous state and action spaces. Since in the telecommunication area, the encountered problems are not always fully observable, we have presented a practical method for handling CMDP with partial state information (PSI-MDP). The main contribution of Chapter 2 has been to provide a practical condition, Condition 2.2, for ensuring that the CMDP corresponding to the PSI-MDP model is solvable.

In Chapter 3, we have analysed the throughput maximization under peak and power constraints. We have in particular considered two possible scenarios: i) the full state of the HARQ protocol is known by Tx before each slot, ii) this state is only partially observable. In the first case, we have that CMDPs are the appropriate tool for solving the allocation problems given in Chapter 1.

The second proposed power allocation has been formulated as a PSI-MDP. The solution of this PSI-MDPhas shown that with only 1 bit of feedback, the power allocation obtained with the PSI-MDP case has almost the same performance 112 Chapter 4. Resource allocation for SU and HARQ PU as the one obtained with full state information (case i).

Finally, in Chapter 4, we have shown that with only one bit of feedback, we can evaluate and mitigate the throughput loss of the PU and obtain a nonnegligible throughput for the SU. To show this result, we have formulated a completely observable problem in which the SU has access to the full state of the HARQ protocol of the PU. This completely observable problem has allowed us to upper-bound the achievable performance of the SU. From this completely observable problem, we have derived a PSI-MDP to handle the case where the SU can only listen to the feedback bits of the PU. In both cases, we have shown that non-negligible throughputs can be achieved by the SU while managing their impact on the performance of the IR-HARQ protocol of the PU.

To conclude this thesis, we want to point out that, due to their sequential nature, the HARQ protocols are in general more difficult to optimize than other communication systems. In the block-fading channel, there is often no exploitable closed-form expression for the throughput of the Type-II HARQ protocols. The framework proposed by the CMDPs is known to be well suited for sequential decision problems. In consequence, the framework of CMDPs is well suited for the resource allocation for HARQ protocols. On the other hand, there are still open problems left in this thesis, we now list some of them that are of notable interest.

Perspectives

• In this thesis, SCSI is required at the transmitter to perform resource allocation such as power or rate allocation considering HARQ protocols. It should be interesting to consider problems in which this SCSI is not available but can be inferred or learned along with the power allocation. Some learning algorithms exist and do not suppose any knowledge on the transition matrix (or kernel) for the MDP model. It is the case for example of some versions of the Q-learning algorithm. The major drawback of these techniques is that the constraints are in general difficult to handle. Extending these techniques to CMDPs is an interesting and challenging task.

• We have seen that the cornerstone of our approach is that the receiver accumulates some quantities: for example SNR or mutual information. Exploiting these quantity, we have built Markov models that are then used in CMDPs. In the context of resource allocation for BICM, the ACMI is often used to perform bit-loading and power allocation. It could be interesting to study if these problems can be interpreted in the CMDP framework.

• In this thesis, we have considered single user scenarios. Extending the proposed method to multiple users scenarios is a challenging task. However, 4.5. Conclusion and Perpectives 113 stochastic games are a generalization of the CMDP framework for problems with multiple players. In consequence, we expect that stochastic games are an appropriate tool to generalize the results presented in this thesis to multi-user environments.

• Every optimization problem presented in this thesis can be re-written as follows:

max π E π T i=1 R i E π T i=1 D i s.t. E π T i=1 C i E π T i=1 D i ≤ C.
This kind of problem is called fractional programming. The fractional programming approach for solving certain classes of CMDP has been proposed in [START_REF] Neely | Online fractional programming for markov decision systems[END_REF]. Furthermore, we have already observed that this framework is appropriate for the design of rate adaptive HARQ systems. Generalizing this approach for optimization problems with continuous state space, should provide us new insights and new algorithms for solving rate or power allocation for HARQ based systems.

-

B.2 Convergence of probability measures

Let X be a given Borel space. Let {m n } be a sequence of probability measures on the same space X . Let m be probability measures on the same space X . In this section we are interested in situations in which "m n → m" in some way see We show here that the function λ → β λ is a continuous coercive function. This will be used to prove that this function attains its infimum. To do so, let ∈ R nc + , from equation (B.12) we obtain where λ M = max λ M , λM . Also we have that for every λ such that λ ≤ λ M the function r + λ j (V jc j ) is K(1 + n c λ M )-Lipschitz continuous. Using the result of [START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF] we have that there exist a constant K such that for every λ such that λ ≤ λ M L(λ) -K h ≤ Lh (λ) ≤ L(λ) + K h (B.27) which, in turn implies

|β λ+ -β λ | ≤
R -K h ≤ R h ≤ R + K h. (B.

1 . 1

 11 System model and block fading channel . . . . . . . . . . . . . . 1.2 Time slot model. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Block fading channel . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Delays in the ARQ protocol. . . . . . . . . . . . . . . . . . . . . 1.5 State Diagram of the Markov chain {K n } n∈N for a Type-I HARQ protocol with N T = 3. . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Transition graph of a Type-II HARQ protocol. . . . . . . . . . . 2.1 Markov Control Model . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Schematic representation of the discretization procedure proposed in [Chow, 1989]. The initial CMDP is represented in red. The discrete version of the CMDP is represented in green. In blue is a intermediary problem that is equivalent to the discrete CMDP (green) but has the same state space as the continuous problem (red). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Partially Observable Markov Control Model . . . . . . . . . . . . 3.1 CQI-based system model . . . . . . . . . . . . . . . . . . . . . . . 3.2 State Diagram of the Markov chain {K n } for a Type-I Hybrid Automatic Repeat reQuest (HARQ) protocol with N T = 3. . . . 3.3 Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for a Type-I HARQ. Simulations parameters: N T = 5, R = 3 bpcu, ᾱ = 1, P min = -10dBW , P max = 10dBW , and N a = 128. . . . . 3.4 Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for a Type-I HARQ. Simulations parameters: N T = 5, R = 1 bpcu, ᾱ = 1, P min = -10dBW , P max = 10dBW , and N a = 128. . . . . 3.5 Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for a Type-I HARQ. Simulations parameters: N T = 5, ᾱ = 1, P min = -10dBW , P max = 10dBW , and N a = 128. The curves presented, are obtained by taking the maximum over values of R going from 0.75 bpcu to 5 bpcu . . . . . . . . . . . . . . . . . . Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for an IR-HARQ protocol. Simulations parameters: N T = 5, R = 7 bpcu, ᾱ = 1, P min = -10dBW , P max = 10dBW , N I = 16, and N a = 64. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.7 Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for a CC-HARQ protocol. Simulations parameters: N T = 5, R = 3 bpcu, ᾱ = 1, P min = -10dBW , P max = 10dBW , N I = 16, and N a = 128. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.8 Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for an IR-HARQ protocol. Simulations parameters: N T = 5, ᾱ = 1, P min = -10dBW , P max = 10dBW , N I = 16, and N a = 64. The curves presented, are obtained by taking the maximum over values of R going from 0.5 bpcu to 10 bpcu . . . . . . . . . . . . 82 3.9 Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for an CC-HARQ protocol. Simulations parameters: N T = 5, ᾱ = 1, P min = -10dBW , P max = 10dBW , N I = 16, and N a = 128. The curves presented, are obtained by taking the maximum over values of R going from 0.1 bpcu to 5 bpcu . . . . . . . . . . . . 83 3.10 System model and block fading channel . . . . . . . . . . . . . . 84 3.11 Comparison of the results presented in Figure 3.6 and the result obtained by solving the projected-CMDP for solving the PSI-MDP in the IR-HARQ case. The following simulations parameters has been considered: N T = 5, R = 7 bpcu, ᾱ = 1, P min = -10dB, P max = 10dB, N a = 16, and Θ mv discretized with a uniform grid of 100 values for m and 100 values for v. . . 86 3.12 Comparison of the results presented in Figure 3.7 and the result obtained by solving the projected-Constrained Markov Decision Process (CMDP) for solving the PSI-MDP in the CC-HARQ case. The following simulations parameters has been considered: N T = 5, R = 3 bpcu, ᾱ = 1, P min = -10dB, P max = 10dB, N a = 16, and Θ mv discretized with a uniform grid of 100 values for m and 100 values for v. . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 3.13 Comparison of the results presented in Figure 3.8 with the adaptive IR-HARQ protocol proposed in [Szczecinski et al., 2011] . . 88 4.1 The Gaussian interference channel at the n th slot. . . . . . . . . 91 List of Figures xiii 4.2 Comparison between throughput regions (η 1 , η2 ) obtained by solving (4.27) and the simulated throughput region (η 1 ( φ), η 2 ( φ)). The comparison is done for ω ∈ {0, 0.5, 0.999} with N I = 16 and N A = 16. The simulated throughput region is computed using a Monte-Carlo method on 10 6 slots. . . . . . . . . . . . . . . . . . 4.3 Simulated throughput of the PU versus η 1T for ω ∈ {0, 0.5, 0.999}. φ has been computed with N I = 16 and N A = 16. The simulated values of η 1 ( φ) are computed using Monte-Carlo methods on 10 6 slots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Comparison of the simulated average power P2 ( φ) and P 2A for different values of η 1T and ω ∈ {0, 0.5, 0.999}. φ has been computed with N I = 16 and N A = 16. The simulated values of η 1 ( φ) are computed using Monte-Carlo methods on 10 6 slots. . . . . . . 4.5 Throughput regions for different values of N I ∈ {4, 8, 16, 32, 64} with N A = 16 and ω = 0. We give two other curves as references. The first one is the simulated throughput region of (η 1 ( φ), η 2 ( φ)) where the φ are computed with N I = 64. The simulated values have been computed using Monte-Carlo method on 10 6 slots. The second reference is the throughput region obtained with N I = 64, N A = 16 and ω = 0.999. . . . . . . . . . . . . . . . . . . . . . . . 4.6 Throughput regions for different values of N I ∈ {4, 8, 16, 32, 64} with N A = 16 and ω = 0.999. We give two other curves as references. The first one is the simulated throughput region of (η 1 ( φ), η 2 ( φ)) where the φ are computed with N I = 64. The simulated values have been computed using Monte-Carlo method on 10 6 slots. The second reference is the throughput region obtained with N I = 64, N A = 16 and ω = 0. . . . . . . . . . . . . . . . . . 4.7 Throughput regions for the completely observable problem and the partially observable problem, for N A . . . . . . . . . . . . . . 4.8 η1 and η2 versus P2 for different values of η 1T . . . . . . . . . . . 4.9 Throughput regions for different values of P 2A . The throughput region obtained when considering an On/Off allocation and a constant power allocation are give as references. These curves have been obtained taking N A = 32, N I = 32, and ω = 0.5. . . . 4.10 Comparison of the throughput regions with or without interference cancellation. . . . . . . . . . . . . . . . . . . . . . . . . .

1. 1

 1

NR

  Set of positive integers; {0, 1, 2, . . . }, Set of real numbers, R + Set of positive real numbers, R Extender real numbers: R ∪ {-∞, +∞}, C Set of complex numbers, × Cartesian product C b (X) Set of bounded continuous functions on X, C(X) Set of continuous functions on X, B(X) Set of measurable bounded functions on X, Measure and Probability Notation B(X) Borel σ-algebra of space X, (•) Lebesgue Measure ( (]a, b[) = ba), δ x (•) Dirac measure in x (δ x (A) = 1 A (x)), f X (•) probability density function of the random variable X, F X (•) cumulative density function of the random variable X,

Figure 1 . 1 -

 11 Figure 1.1 -System model and block fading channel

Chapter 1 .Figure 1 . 4 -

 114 Figure 1.4 -Delays in the ARQ protocol.

  .26) In case of successful decoding Rx sends an ACK bit to Tx who starts the transmission of the next information packet. If the decoding fails, Rx sends a NACK Chapter 1. An overview of HARQ-based telecommunication systems bit to Tx who sends x 1 over the channel. At the reception of x 1 , Rx builds r 1 = (y 0 , y 1 ) and tries to decode r 1 . Using again equation (1.

Figure 1 . 5 -

 15 Figure 1.5 -State Diagram of the Markov chain {K n } n∈N for a Type-I HARQ protocol with N T = 3.

1. 4 .

 4 Figure 1.6. In this figure, each possible value for k ∈ {0, . . . , N T } is represented by a state (circle). From each k we represent a vertical line that accounts for

  Rx succeeds in decoding the information packet. In this case Rx sends an ACK bit in the feedback channel and Tx starts a new transmission. Using the state definition, it means that S n+1 = (0, 0). This transition is represented as the green arrow from s n to (0, 0) in Figure1.6.

  HARQ protocols. Whereas the proposed model for the Type-I

Assumption 2. 1 .

 1 (a) S and U are compact. (b) r is continuous on S × A and there exists r M ∈ R + such that for every (s, a) ∈ S × A, |r(s, a)| ≤ r M . (c) For every i ∈ [1, n c ], c i is a continuous function on S × A and there exists c i,M such that for every (s, a) ∈ S × A, |c i (s, a)| ≤ c i,M . (d) For every bounded continuous function v on S, v(s, a) = S v(s )Q(ds |s, a) is a bounded continuous function on S × A. Following [Meyn & Tweedie, 2009],

Condition 2 . 1 (

 21 [START_REF] Hernández-Lerma | Adaptive Markov control processes[END_REF]). (a) There exist s 0 ∈ S and ∈ R + such that Q({s 0 } |s, a) ≥ , with > 0. (b) There exists a measure ν on S such that ν(S) > 0 and, Q(B|s, a) ≥ ν(B), ∀(s, a) ∈ U and ∀B ∈ B(S). (2.25) It can be shown (see Hernández-Lerma [1989]) that both Condition 2.1(a) and Condition 2.1(b) are sufficient for Assumption 2.1(e).

  or [Hernández-Lerma & Lasserre, 1996, Chapter 6]. This section uses the results of [Hernández-Lerma & Lasserre, 1996, Chapter 6] for unconstrained MDPs and of [Hernández-Lerma et al., 2003] for CMDPs.

  .44) where ||•|| T V is the TV-norm defined by equation (2.29) and U c = {(s, a) ∈ S × A|(s, a) / ∈ U} . For every m ∈ M(U) and every v ∈ F(U), let m, v = vdm. (2.45) It is shown in [Hernández-Lerma & Lasserre, 1996] that equation (2.45) defines a bilinear form on M(U) × F(U) as long as we take the convention that every function v ∈ F(U) is measurably extended to S ×A in such a way that for every m ∈ M(U) U c vdm = 0.

  m(B × A)(see [Hernández-Lerma & Lasserre, 1996, Appendix D8]). Since ϕ is a stochastic kernel on A given S, it can be viewed as a policy in Π RS . Using equation (2.47) in equation (2.46) gives that m verifies m(B) -S A Q(B|s, a)ϕ(da|s) m(ds) = 0. (2.48) Because of the uniqueness of the invariant probability measure of Q ϕ , we have m = Q ∞ ϕ .

Theorem 2 . 2 .

 22 .49) In Section 2.3.3, we have shown that under Assumption 2.1, R(ϕ) = m, r andC(ϕ) = m, c where m(d(s, a)) = ϕ(da|s)Q ∞ ϕ (ds).The equivalence between the optimization problem (2.37) and an infinite dimensional LP is stated in the following theorem. The optimization problem (2.37) is then equivalent to:

Sh,Figure 2 . 2 -

 22 Figure 2.2 -Schematic representation of the discretization procedure proposed in[START_REF] Chow | Multigrid algorithms and complexity results for discrete-time stochastic control and related fixed-point problems[END_REF]. The initial CMDP is represented in red. The discrete version of the CMDP is represented in green. In blue is a intermediary problem that is equivalent to the discrete CMDP (green) but has the same state space as the continuous problem (red).

[

  [START_REF] Arapostathis | Discrete-time controlled markov processes with average cost criterion: a survey[END_REF], this model is referred to as the partial state information model. Consequently it will be denoted by Partial State Information Markov Decision Process (PSI-MDP) in the sequel. Since PSI-MDPs are a special case for POMDPs, every results shown (in particular in [Hernández-Lerma, 1989, Chapter 6]) remains valid.The most common way for handling POMDP is to build an equivalent (completely observable) MDP(see[START_REF] Bertsekas | Stochastic optimal control: the discrete time case[END_REF], Chapter 10], [Hernández-Lerma, 1989, Chapter 6], [Arapostathis et al., 1993, Section 7], and references therein)

  X , Y and A are compact sets. (b) r and c are bounded and continuous functions. (c) Q is weak Feller (see Assumption 2.1(d)).

  .98) For every b x ∈ P(X ), the projection of b x on Ψ is given by Proj Ψ (b x ) = arg min g∈Ψ D KL (b x ||g), (2.99) or equivalently, considering the θ parameter θ(b x ) = arg min θ∈Θ0 D KL (b x ||f (•, θ)).

2

 2 Power allocation for the Type-I HARQ protocols 67 3.2.1 CMDP model associated with the Power allocation for the Type-I HARQ protocols . . . . . . . . . . . . 67 3.2.2 The Finite Linear Programming . . . . . . . . . . . 70 3.2.3 Simulation results . . . . . . . . . . . . . . . . . . . 72 3.3 Power allocation for the throughput maximization of Type-II HARQ protocols . . . . . . . . . . . . . 73 3.3.1 CMDP model associated with the Power allocation for the Type-II HARQ protocols . . . . . . . . . . . 74 3.3.2 The finite linear programming . . . . . . . . . . . . 77 3.3.3 Numerical results . . . . . . . . . . . . . . . . . . . . 79 3.3.4 The Partially Observable problem . . . . . . . . . . 80 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . 85

66 ChapterFigure 3 . 1 -

 6631 Figure 3.1 -CQI-based system model

Figure 3 . 2 -• 1 :• 2 :

 3212 Figure 3.2 -State Diagram of the Markov chain {K n } for a Type-I HARQ protocol with N T = 3.

  (2.3(a)) trivially holds. Since the short-term reward and cost functions given by equations (3.3) and (3.4) are respectively constant and linear in a, the Lipschitz continuity of these functions trivially holds and Assumptions 2.3(b) and 2.3(c) are verified. In case of Rayleigh fading channel, we show in Appendix C.1 that Assumption 2.3(d) holds. It finally remains to prove Assumption 2.3(e). We prove this Assumption by showing that Condition 2.1(a) holds. The accessible state needed by Condition 2.1(a) is s 0 = 0, indeed, for every s ∈ S we have

3. 3 .-Figure 3 . 3 -

 333 Figure 3.3 -Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for a Type-I HARQ. Simulations parameters: N T = 5, R = 3 bpcu, ᾱ = 1, P min = -10dBW , P max = 10dBW , and N a = 128.

Figure 3 . 4 -

 34 Figure 3.4 -Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for a Type-I HARQ. Simulations parameters: N T = 5, R = 1 bpcu, ᾱ = 1, P min = -10dBW , P max = 10dBW , and N a = 128.

3. 3 .-Figure 3 . 5 -

 335 Figure 3.5 -Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for a Type-I HARQ. Simulations parameters: N T = 5, ᾱ = 1, P min = -10dBW , P max = 10dBW , and N a = 128. The curves presented, are obtained by taking the maximum over values of R going from 0.75 bpcu to 5 bpcu

  (2.3(a)), Assumption 2.3(b), Assumption 2.3(c) holds. The verification of Assumption2.3(d) is done in Appendix C.2. It finally remains to verify Assumption 2.3(e). We again prove this Assumption by showing that Condition 2.1(a) holds. The accessible state needed by Condition 2.1(a) is s 0 = (0, 0), indeed, for every s ∈ S we have Q(s 0 |s, a) = P [x + Δ (aα) ≥ D T ] (3.13)

Figure 3 . 6 -

 36 Figure 3.6 -Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for an IR-HARQ protocol. Simulations parameters: N T = 5, R = 7 bpcu, ᾱ = 1, P min = -10dBW , P max = 10dBW , N I = 16, and N a = 64.

3. 3 .-Figure 3 . 7 -

 337 Figure 3.7 -Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for a CC-HARQ protocol. Simulations parameters: N T = 5, R = 3 bpcu, ᾱ = 1, P min = -10dBW , P max = 10dBW , N I = 16, and N a = 128.

Figure 3 . 8 -

 38 Figure 3.8 -Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for an IR-HARQ protocol. Simulations parameters: N T = 5, ᾱ = 1, P min = -10dBW , P max = 10dBW , N I = 16, and N a = 64. The curves presented, are obtained by taking the maximum over values of R going from 0.5 bpcu to 10 bpcu

3. 3 .-Figure 3 . 9 -

 339 Figure 3.9 -Comparison of the throughput of constant power allocation and variable power allocation as a function of Average SNR for an CC-HARQ protocol. Simulations parameters: N T = 5, ᾱ = 1, P min = -10dBW , P max = 10dBW , N I = 16, and N a = 128. The curves presented, are obtained by taking the maximum over values of R going from 0.1 bpcu to 5 bpcu

  y, a)b(dx) p (z, a) = X p(x, y, a)b(dx).(3.21) From the definitions of r and p, we get: , a) = p(s, a) = a.(3.23)

Figure 3 . 11 -

 311 Figure 3.11 -Comparison of the results presented in Figure 3.6 and the result obtained by solving the projected-CMDP for solving the PSI-MDP in the IR-HARQ case. The following simulations parameters has been considered: N T = 5, R = 7 bpcu, ᾱ = 1, P min = -10dB, P max = 10dB, N a = 16, and Θ mv discretized with a uniform grid of 100 values for m and 100 values for v.

Figure 3 . 12 -

 312 Figure 3.12 -Comparison of the results presented in Figure 3.7 and the result obtained by solving the projected-CMDP for solving the PSI-MDP in the CC-HARQ case. The following simulations parameters has been considered: N T = 5, R = 3 bpcu, ᾱ = 1, P min = -10dB, P max = 10dB, N a = 16, and Θ mv discretized with a uniform grid of 100 values for m and 100 values for v.

Figure 4 . 1 -

 41 Figure 4.1 -The Gaussian interference channel at the n th slot.

  the PU uses an IR-HARQ protocol, (b) the parameters p 1 , r 1 and N T,1 are constant over time, (c) the feedback channel is instantaneous and error-free, (d) T x 1 always has an information packet to transmit, (e) the PU sends its feedback bits over a common broadcast channel.

  (4.4) to stress the dependence of η 1 to the power allocation π 2 of the SU. This dependence, happens because of the Signal to Interference plus Noise Ratio (SINR), β 2,n given in equation (4.3).

  Rx 2 processes the PU signal as noise. (b) T x 2 has an information packet to transmit. (c) T x 2 has no CSIT but has SCSI. (d) Rx 2 has partial CSIR and complete SCSI.(e) Both T x 2 and Rx 2 know the IR-HARQ protocol of the PU, in particular, they know p 1 , r 1 and N T,1 . (f) Both T x 2 and Rx 2 can decode the instantaneous and error-free feedback of the PU; they can both infer k 1,n . Assumption 4.2 implies that Rx 2 does not use Successive Interference Cancellation (SIC) techniques. Assumption 4.2(b) is classically made and indicates that the queue of T x 2 is always non-empty so that it always has an information packet to transmit. Assumption 4.2(c) and Assumption 4.2(d) have been discussed at the beginning of this subsection. 4.2(e) often holds because parameters r 1 , p 1 and N T,1 are given in standards. Assumption 4.2(f) indicates that the SU can decode the feedback bits of the protocol of the PU. Assumption 4.2(f) is a direct consequence of Assumption 4.1(e).

100 Chapter 4 .

 4 Resource allocation for SU and HARQ PU From a solution m of the finite linear programming given in equation (4.27) we compute a policy for the optimization problem given in equation (4.9) as follows: φ(da|s) = ã m (s j , ã) s m (s, ã) δ ã(da), ∀s ∈ S j .(4.28)

Figure 4 . 2 Figure 4 . 2 -

 4242 Figure 4.2 highlights that the optimal SU throughput computed with ω = 0underestimates the simulated SU throughput. On the other hand the optimal SU throughput computed with ω close to 1 overestimates the simulated SU throughput. In addition to these results, we provide the same curves for ω = 0.5 where theoretical and simulated throughputs are close to each other.In addition to these results, we compare in Figure4.3 the simulated through-

Figure 4 . 3 -

 43 Figure 4.3 -Simulated throughput of the PU versus η 1T for ω ∈ {0, 0.5, 0.999}. φ has been computed with N I = 16 and N A = 16. The simulated values of η 1 ( φ) are computed using Monte-Carlo methods on 10 6 slots.

Figure 4 . 4 -Figure 4 . 5 -

 4445 Figure 4.4 -Comparison of the simulated average power P2 ( φ) and P 2A for different values of η 1T and ω ∈ {0, 0.5, 0.999}. φ has been computed with N I = 16 and N A = 16. The simulated values of η 1 ( φ) are computed using Monte-Carlo methods on 10 6 slots.

Figure 4 . 6 -

 46 Figure 4.6 -Throughput regions for different values of N I ∈ {4, 8, 16, 32, 64} with N A = 16 and ω = 0.999. We give two other curves as references. The first one is the simulated throughput region of (η 1 ( φ), η 2 ( φ)) where the φ are computed with N I = 64. The simulated values have been computed using Monte-Carlo method on 10 6 slots. The second reference is the throughput region obtained with N I = 64, N A = 16 and ω = 0.

4. 5 .Figure 4 . 7 -

 547 Figure 4.7 -Throughput regions for the completely observable problem and the partially observable problem, for N A .

η 1

 1 for η 1T = 0.9η 10 η 1 for η 1T = 0.7η 10 η 1 for η 1T = 0 η 2 for η 1T = 0 η 2 for η 1T = 0.7η 10 η 2 for η 1T = 0.9η 10

Figure 4 . 8 -P

 48 Figure 4.8 -η1 and η2 versus P2 for different values of η 1T .

Figure 4 . 9 -

 49 Figure 4.9 -Throughput regions for different values of P 2A . The throughput region obtained when considering an On/Off allocation and a constant power allocation are give as references. These curves have been obtained taking N A = 32, N I = 32, and ω = 0.5.

Figure 4 . 10 -

 410 Figure 4.10 -Comparison of the throughput regions with or without interference cancellation.

[Definition B. 2 .

 2 [START_REF] Hernández-Lerma | Discrete-Time Markov Control Processes: Basic Optimality Criteria[END_REF]. We first introduce the weak convergence concept. We say that m n converges weakly to m, if and only if for every continuous and bounded function v ∈ C(X ):lim n→∞ X v(x)m n (dx) = X v(x)m(dx). (B.3) that β λ + u λ (s) = max a∈A(s) r(s, a) + n C j=1 λ j (V jc j (s, a)) + S u λ (y)Q(dy|s, a). (B.9)Another consequence of the same theorem is that for every initial distribution ν 0 ,β λ = sup π∈Π R(ν 0 , π) + n C j=1 λ j (V j -C j (ν 0 , π)) (B.10)Furthermore, because of the measurable selection theorem, there exists ζ λ ∈ Π DS such that:β λ + u λ (s) = r(s, ζ λ (s)) + n C j=1 λ j (V jc j (s, ζ λ (s))) + S u λ (y)Q(dy|s, ζ λ (s)), (B.11)andβ λ = R(ζ λ ) + n C j=1 λ j (V j -C j (ζ λ )) .(B.12)

B. 4

 4 j -C j (ζ λ )) (B.13) ≤ || || ∞ nc j=1 |(V j -C j (ζ λ ))| (B.14) ≤ n c || || ∞ (||V|| ∞ + ||c M || ∞ ) , (B.15)where c M is the vector (c 1,M , c 2,M , . . . , c nc,M ). From the boundedness of n c , ||V|| ∞ , and ||c M || ∞ , we obtain that β λ is Lipschitz continuous and so continuous. Under Assumption 2.2, there exists ϕ 0 ∈ Π RS such that C(ϕ 0 ) < V. Using this ϕ 0 in (B.10) leads to lim ||λ|| ∞ →+∞ β λ = +∞. (B.16)There exists λ such thatβ λ = inf λ>0 β λ . (B.17)We finally prove that β λ = β . Since the triplet (u λ , β λ , λ ) is admissible for the dual LP (2.56), we have β ≤ β λ . Let (u, β, λ) be an admissible triplet for the dual LP (2.56). We have that for all s ∈ S and all a ∈ A(s)β + u(s) ≥ r(s, a) + n C j=1 λ j (V jc j (s, a)) + S u(y)Q(dy|s, a). (B.18)For every ϕ ∈ Π RS , integrating both sides by ϕ(da|s)Q ∞ ϕ (ds) givesβ ≥ R(ϕ) + n C j=1 λ j (V j -C j (ϕ)) . (B.19)Since it is true for every ϕ ∈ Π RS , it is also true for ζ λ henceβ ≥ R(ζ λ ) + n C j=1 λ j (V j -C j (ζ λ )) = β λ . (B.20) Taking now the infimum over all admissible triplet (u, β, λ) gives that β ≥ β λ . Proof of the convergence of discrete approximation To use properties shown for the unconstrained case in the constrained case, we will use Proposition 2.1 and Proposition 2.2. Proposition 2.1 shows that solving the infinite dimensional linear programming (2.50) is equivalent to solving the unconstrained MDP (S, A, U, Q, r + λ j (V jc j ))and taking the infimum over all values of λ. For every λ, let L(λ) be defined asL(λ) = sup ϕ∈Π RS ⎛ ⎝ R(ϕ) + nc j=1 λ j (V j -C j (ϕ)) ,Proposition 2.2 shows that there exists λ M such that λ ≤ λ M . This result implies that Ãh , Ũh , Qh , rh + λ j (V jcj,h )) B.5. Proof of equation (2is related to the optimal value of the discretized CMDP (S, Ãh , Ũh , Qh , rh , ch ) by the following relationship: R h = inf λ≥0 Lh (λ). (B.24) Suppose that Assumption 2.2 holds for the CMDP (S, Ãh , Ũh , Qh , rh , ch ). Proposition 2.2 shows that there exists λM such that λ ≤ λM . This result implies that R h = inf 0≤λ≤ λM Lh (λ). (B.25) From equations (B.22) and (B.25) we have ⎧ ⎨ ⎩ R = inf 0≤λ≤λ M L(λ).

R

  h = inf 0≤λ≤λ M L(λ). (B.26)

  Table of rules for the transitions from the state s n = k n to s n+1 when power Tx communicates at power p n . . . . . . . . . . . . . 1.2 Possible values for the state of the Type-II HARQ protocol at time (n + 1)T (S n+1 ) depending on s n = (k n , x n ) and on the value of Δ (α n , p n ). . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Table of rules for the transitions from the state s n = (k n , x n ) to s n+1 when power Tx takes action a n . . . . . . . . . . . . . . . . . 4.1 State transition Table . . . . . . . . . . . . . . . . . . . . . . . .

	xvi xviii	List of Tables List of Acronyms
	HSDPA High Speed Downlink Packet Access
	List of Acronyms i.i.d. independent and identically distributed
	IR Incremental Redundancy
	κ-ESM κ-Effective SNR Mapping LLN Law of Large Numbers
	ACK ACKnowledgement LP Linear Programming
	ACMI ACcumulated Mutual Information LTE Long Term Evolution
	AMC Adaptive Modulation and Coding MC Markov Chain
	MDP Markov Decision Process
	ARQ Automatic Repeat reQuest
	MIESM Mutual Information Effective SNR Mapping
	AWGN Additive White Gaussian Noise
	ML Maximum Likelihood
	BIC Backward Interference Cancellation
	MRC Maximum Ratio Combining
	BICM Bit Interleaved Coded-Modulation NACK Negative ACKnowledgement
	CC Chase Combining OCSI Outdated Channel Side Information
	CD Chain Decoding OSA Opportunistic Spectrum Access
	CMDP Constrained Markov Decision Process pdf probability density function
	CQI Channel Quality Indicator PHY Physical
	CR Cognitive Radio POMDP Partially Observable Markov Decision Process
	CRC Cyclic Redundancy Check PSI-MDP Partial State Information Markov Decision Process
	CSI Channel Side Information PU Primary User
	CSIR Channel Side Information at the Receiver QoS Quality of Service
	CSIT Channel Side Information at the Transmitter SCSI Statistical Channel Side Information
	EESM Exponential Effective SNR Mapping SDR Software Defined Radio
	FCC Federal Communications Commission SIC Successive Interference Cancellation
	FEC Forward Error Correction SINR Signal to Interference plus Noise Ratio
	FER Frame Error Rate SNR Signal to Noise Ratio
	GNR Gain to Noise Ratio SU Secondary User
	HARQ Hybrid Automatic Repeat reQuest
	xv xvii

TV-norm Total Variation norm

- An overview of HARQ-based telecommunication systems Contents 1

	IJ1 Romain Tajan, Charly Poulliat, Inbar Fijalkow. "Secondary Resource
	Allocation for Opportunistic Spectrum Sharing with IR-HARQ based Pri-
	mary Users". (submitted to Transactions on Signal Processing).
	International Conference Papers
	National Conference Papers

IC3 Romain Tajan, Charly Poulliat, Inbar Fijalkow. "Interference Management for Cognitive Radio Systems Exploiting Primary IR-HARQ: a Constrained Markov Decision Process Approach". IEEE Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, November 2012. IC2 Romain Tajan, Charly Poulliat, and Inbar Fijalkow. "Opportunistic Secondary Spectrum Sharing Protocols for Primary Implementing an IR Type Hybrid-ARQ protocol".In the IEEE proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, Japan, 15-30 March, 2012. IC1 Romain Tajan, Charly Poulliat, Rodrigue Imad, and Inbar Fijalkow. "A new trellis representation for source-channel rate allocation". In the IEEE proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP), Prague, Czech Republic, 22-27 May, 2011. NC2 Romain Tajan, Charly Poulliat, Inbar Fijalkow, "Allocation conjointe de puissance et rendement d'un utilisateur cognitif exploitant les retransmissions d'un utilisateur primaire : le cas du canal en Z", GRETSI, 2013. NC1 Romain Tajan, Charly Poulliat, Inbar Fijalkow, "Coexistence de protocoles a retransmissions incrémentales pour un canal cognitif", GRETSI, Bordeaux, France, September 2011. -Chapter 1 .1 Introduction . . . . . . . . . . . . . . . . . . . . . . 8 1.2 System Model . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Channel model . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 Channel State Information . . . . . . . . . . . . . . 10 1.2.3 Asymptotically optimal Channel Coding . . . . . . . 11 1.2.4 Automatic Repeat reQuest . . . . . . . . . . . . . . 12 1.3 HARQ Protocols . . . . . . . . . . . . . . . . . . . . 17 1.3.1 Type-I HARQ protocol . . . . . . . . . . . . . . . . 17

1.3.2 Type-II Chase Combining (CC) HARQ protocol . . 19 1.3.3 Type-II Incremental Redundancy (IR) HARQ protocol 21 1.4 A unified analysis based on Markov chains . . . . 22 1.4.1 Controlled Markov Chain associated with the Type-I HARQ protocol . . . . . . . . . . . . . . . . . . . . 23 1.4.2 The state of Type-II HARQ protocols . . . . . . . . 26 1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . .

. 28 1.1 Introduction

	In modern communication standards such as High Speed Downlink Packet Ac-
	cess (HSDPA) or Long Term Evolution (LTE), Hybrid Automatic Repeat re-
	Quest (HARQ) protocols are used in conjunction with Adaptive Modulation
	and Coding (AMC) to guarantee high reliability and high data rates for wire-
	less communications.

In the early 2000s, ACcumulated Mutual Information (ACMI) (see in particular

[START_REF] Caire | The throughput of hybrid-arq protocols for the gaussian collision channel[END_REF]

,

[START_REF] Cheng | Adaptive incremental redundancy [wcdma systems[END_REF]

,

[START_REF] Sesia | Incremental redundancy hybrid arq schemes based on low-density parity-check codes[END_REF]

,

  Table of rules for the transitions from the state s n = k n to s n+1 when power Tx communicates at power p n .

	0	1	2	3

Table 1 . 2 -

 12 Possible values for the state of the Type-II HARQ protocol at time (n + 1)T (S n+1 ) depending on s n = (k n , x n ) and on the value of Δ (α n , p n ).

  every t ∈ N, π t (da|h t ) is a stochastic kernel on A given H t . At decision epoch t ∈ N, the controller chooses an action within the set A ∈ B(U) with a probability π t (A|h t ). The set of all policies is denoted by Π.

• A policy π ∈ Π is said to be a Markov policy if and only if for all t ∈ N it verifies π t (•|h t ) = π t (•|s t ). The set of all Markov policies is denoted by Π M . For policies of Π M , there is no need to store the whole history but only the last state s t .

• A policy π ∈ Π M is a randomized stationary policy if for every t ∈ N,

π t (•|s t ) = π(•|s t ).

The set of all randomized stationary policies is denoted by Π RS .

• A policy π ∈ Π RS is a deterministic stationary policy if there exists a function from S to A denoted by ζ, such that for every n ∈ N, π(•|s n ) = δ ζ(sn) (•). In the last expression, δ stands for the Dirac measure. The set of all deterministic stationary policies is denoted by Π DS . Obviously, we have the inclusion:

  There are two important conclusions for this section. The first one is stated in Lemma 2.1: under Assumption 2.1, the optimization problem given in equation 2.20 can be solved in Π RS without loss of optimality. The second conclusion of this section is given by Theorem 2.1: under Assumption 2.1 and if the set of admissible policies is non-empty, there exists an optimal policy for the optimization problem given in equation 2.20.

	It remains to show that there exists ϕ ∈ Ω RS such that
	m (d(s, a)) = ϕ (da|s)Q ∞ ϕ (ds).	(2.41)
	The rest of this proof is the same as proposed in [Hernández-Lerma & Lasserre,
	1996] and is omitted here.
		B	ϕ t (C|s)Q ∞ ϕt (ds).	(2.39)
	By the same arguments of the proof of Lemma 2.1, we have that there exists a
	converging subsequence {m t1 } such that
	R ≤ lim sup t1	rdm t1 ≤ rdm .	(2.40)

Theorem 2.1. Under Assumption 2.1 and if Ω is non-empty, there exists a solution of the optimization problem (2.20) in Π RS .

Proof. By Assumption, we suppose the Ω is non-empty. From Lemma 2.1, it follows that Ω RS is also non-empty. Let { t } be a sequence of positive real numbers such that lim t→∞ t = 0. By equation (2.37), for every t ∈ N, there is

ϕ t in Ω RS such that R(ϕ t ) = rdm t ≥ R + t , (

2

.38) where for every t ∈ N, B ∈ B(S), and C ∈ B(S), m t (B × C) =

  2.4 in Appendix B.3. The second proposition is a bound on the value of λ .

	Proposition 2.2. Under Assumption 2.1 and Assumption 2.2,

  1, this optimization problem is solvable and that a solution can be found in Π RS . We have then shown that, under Assumption 2.1, solving the optimization problem in Π RS is equivalent to solving an infinite dimensional LP. Approximations of this LP are obtained Chapter 2. CMDP: an Introduction by discretizing the state and action spaces and solving a finite LP. Based on the infinite dimensional LP and on the relationship with its dual, we have provided Assumption 2.3 that guarantees the convergence of the finite approximations to the infinite solution. Finally, we have introduced the constrained POMDP and constrained PSI-MDP models. For the PSI-MDP model, we have shown that these problems can be reduced to CMDP with an infinite dimensional state space. Based on this new CMDP, we finally have presented a heuristic method to solve constrained PSI-MDPs. This method is inspired from the literature of the unconstrained PSI-MDP.The main contribution of this chapter has been to provide a new condition, Condition 2.2, for ensuring that the CMDP corresponding to the PSI-MDP model is solvable. This condition is verifiable in practice, for the applications with a completely observable state accessible from every other states.

Table 3 . 1 -

 31 Table of rules for the transitions from the state s n = (k n , x n ) to s n+1 when power Tx takes action a n .

  This allows us to use Remark 2.2, to verify that Condition 2.2(e) is checked.

		Transmitter (Tx)
			Power Allocation
			√ p n
	u n	Channel	x n
		Encoder	Channel
			h n
	ACK/NACK	z n
	ûn	Channel	y n
		Decoder
			Receiver (Rx)
		Figure 3.10 -System model and block fading channel
	We now prove that this CMDP is solvable. In fact, from the preceding
	subsection, we have already proved Condition 2.2 except Condition 2.2(d) and
	Condition 2.2(e). To check 2.2(d) we observe that Y is finite and we use Remark
	2.1. To check Condition 2.2(e), we observe that the state (0, 0) corresponds to
	observing ACK and in consequence is completely observable. Moreover, we have
	shown in equation (3.13) that this state is accessible from every other state of
	S.

  n and y 2,n respectively received in slot n by Rx 1 and Rx 2 are expressed as

		Chapter 4. Resource allocation for SU and HARQ PU
	The random variables defined as
		α ij,n = |h ij,n | 2		(4.2)
	are exponentially distributed with mean ᾱij . The instantaneous Signal to In-
	terference plus Noise Ratio (SINR) at Rx i in slot n is denoted by β i,n and is
	defined as:	β ,n =	p i,n α ii,n 1 + p j,n α ji,n	.	(4.3)
		⎧ ⎨ ⎩ y n 1 = h 11,n x 1,n + h 21,n x 2,n + z 1,n 2 = h 22,n x 2,n + h 12,n x 1,n + z 2,n , y n	(4.1)
	where the slot is assumed to last L symbols (as in Chapter 1), z i,n ∈ C L is a
	random vector of size L representing additive white Gaussian noise. The noise
	is a complex Gaussian random vector of size L. We consider, without loss of
	generality, that the vectors z i,n have i.i.d. components of zero mean and unit
	variance. The input signals x 1,n and x 2,n are of size L and are assumed to be
	complex circular white Gaussian random vectors of zero mean and respective
	transmit powers p 1,n and p 2,n .

•

  In slot n, the gains α 11,n , α 12,n , α 21,n and α 22,n are unknown by T x2 The system function g(•) is a deterministic function from S × A × W to S taking into account the evolution of the system from state s n ∈ S in slot n to state s n+1 ∈ S in slot n + 1 when the action p 2,n is performed and when the disturbance is w n . g(•) is globally defined asg(s n , p 2,n , w n ) = (k 1,n+1 , i 1,n+1 ) = s n+1 . (4.14)Similarly to what has been done in Chapter 1, we present the function g in a table representation given in Table4.1. This tabular can be interpreted as

	and are considered as disturbances (see Assumption 4.2(c)). In consequence, we
	consider the following disturbance space: W = R 4 + .
	• Section 1.2.3 so that
	Δ (w n , p 2,n ) = log 2 1 +	p 1 α 11,n 1 + p 2,n α 21,n	,	(4.15)

follows, if at time n, s

n = (k 1,n , i 1,n ) with 0 < k 1,n < N T -1, and if i 1,n + Δ (w n , p 2,n ) < D T ,

then s n+1 given by equation (4.14) will be (k n + 1, i 1,n + Δ (w n , p 2,n )). We consider that the PU uses the channel code described in

Table 4 . 1 -

 41 State transition Table• The evolution of the system is again statistically represented by the

	transition law Q defined, for a given measurable subset B ⊂ S and a pair
	(s, p 2,n ) ∈ S × A as follows:

Q(B|s, p 2,n ) = P s n+1 = g(s n , p 2,n , w n ) ∈ B|s n = s, a n = p 2,n .

(4.

16)

  1, Assumption 4.2 and assuming that i 1,n is known to T x 2 and Rx 2 , the optimization problem given in equation (4.9) is a CMDP that can be solved by discretizing the state and action spaces. In this section, we propose to tackle the initial problem which is given in equation(4.9) only under Assumption 4.1, Assumption 4.2.

  Proof of equation (2.91)Let X and Y be some random variables. For the sake of readability we use the notation f (x, y) instead of f X,Y (x, y) and similarly f (x|y) instead of f X|Y (x|y).We now prove equation (2.91).b x,t (x t ) is the a posteriori distribution of X t given H t = (H t-1 , A t-1 , Y t ).More formally, b x,t (x t ) is defined as

28) B.5 b x,t (x t ) = f (x t |h t-1 , a t-1 , y t ) .

(B.29)

Chapter 1. An overview of HARQ-based telecommunication systems

Chapter 2. CMDP: an Introduction

Remerciements

Constrained Markov Decision

In this chapter, we show that the CMDP framework is appropriate for studying the power allocation of a secondary user that exploits the HARQ rounds of a primary user to manage its interference.

Introduction

Recently, the number of wireless services has dramatically increased generating a growth in the demand on radio spectrum. Additionally, because of the command-and-control regulation, every service is allocated to a dedicated bandwidth. In consequence, the radio spectrum has become a scarce resource. On the other hand, It has been shown that the radio spectrum is underutilized (see [FCC, 2002]). By allowing Secondary Users (SUs) to opportunistically access the bandwidth dedicated to licensed users (also referred to as Primary Users

The expression of Q(B|s, a) is provided in Appendix (D.1) and we show that Q(B|s, a) verifies Assumption 2.3(d) in Appendix (D.2).

• In slot n, the definition of the primary instantaneous reward is given in Section 4.2 by equation (4.5). We remark here that R 1 is bounded and Lipschitz continuous so that it verifies Assumption 2.3(c).

• Similarly R n 2 can be written as function of (

The proof of Lipschitz continuity of R 2 is given in Appendix D.3. Consequently, R 2 is bounded and Lipschitz continuous so that it verifies Assumption 2.3(b).

• The instantaneous cost associated with the average power constraint is the following:

We remark here that P 2 is bounded and Lipschitz continuous so that it verifies Assumption 2.3(c).

We now briefly review, in our context, the concept of policy defined in Section 2.2.2.

Policy

Applying the definition given in Section 2.2.2 to the present case, the history up to time t is defined as follows,

The two main sets of policies that are of interest in this chapter are the following: Π: The general set of policies, every π 2 ∈ Π is defined as a sequence of stochastic kernels, π 2 = {π 2,t (dp 2,t |h t )}, Π RS : The set of randomized stationary policies, every π 2 ∈ Π is defined as a sequence of the form:

In the sequel, we will not distinguish between π 2 and ϕ.

Finally, the long-term reward and cost functions are given by equations (4.7), (4.4), and (4.8) (supposing without loss of generality that the initial state is (0, 0)). In consequence, we have completely described the CMDP framework associated with the optimization problem (4.9) when i 1,n is assumed to be known at T x 2 and Rx 2 . In the next subsection, we will show that we can discretize the state and action spaces to get approximate solutions of this CMDP.

Appendices

where 1 B (s) is the function that is equal to 1 if s n+1 ∈ B and 0 otherwise. In our case, the transition kernel has the following expression:

Where, for Rayleigh channel and in the case of CC-HARQ protocol we have

For Rayleigh channel and in the case of IR-HARQ protocol we have

and after some calculations we obtain

The weak convergence is denoted as follows

-→ m.

(B.4)

The second mode of convergence is the set-wise convergence.

Definition B.3. The set-wise convergence is defined as follows: for every B ∈ B(X ),

The last way of defining a convergence notion for m n considers the TV-norm defined for every signed measure μ on X as follows:

For two probability measures μ 1 and μ

We now introduce the convergence in TV-norm (sometimes referred to as the strong convergence).

The same reasoning can be done to write f (y t |h t-1 , a t-1 ) as follows:

Since X t-1 is non-observable and since A t-1 depends on the observable history H t-1 only, A t-1 and X t-1 are independent. This implies that f

. Using the definitions of b x,t-1 and q we have b

and q (x t , y

, a t-1 and y t thanks to the following relationship:

(B.34)

B.6 Proof of Theorem 2.6

To prove Theorem 2.6, we will show that Condition 2.2(e) implies that for every z ∈ Z and every a ∈ A, Q Z verifies that for every B ∈ B(P(X )) and every

This will prove that Condition 2.1(b) holds and in consequence that Assumption 2.1(e) holds.

We now show equation (B.35). From equation (2.95) and using C 0 defined in Condition 2.2(e)i), we have that for every B ∈ B(P(X )) and every C ∈ B(Y):

where the second inequality is obtained by using Condition 2.2(e) in equation (2.93). This in turn implies that Q Z verifies Assumption 2.1(e).

B.7 Proof of Remark 2.2

Let s 0 ∈ S be a state such that for every s ∈ S and every a ∈ A, Q({s 0 } |s, a) > and Q X (dx |x, y, a, y 0 ) = δ x0 (dx ). From the definition of Q Z we have

Moreover using the disintegration of Q we have that This finally proves that

where m 0 = δ x0 . To complete the proof note that δ y0 (Y) = 1.

-Appendix C -

Appendices of Chapter 3 C.1 Lipschitz continuity of Q, the Type-I HARQ case

In this appendix, we show that in the case of Rayleigh fading channel, Assumption 2.3(d) holds.

For two probability measures μ 1 and μ 2 on S (which is a discrete space), it is shown in [Hernández- [START_REF] Hernández-Lerma | Adaptive Markov control processes[END_REF]] that

We now apply this result to In the case s = s we have

The first inequality comes from triangular inequality and the second inequality

In the case s = s we have by direct calculations that We focus here on the IR-HARQ case, but this proof is the same (with obvious changes) for the case of CC-HARQ. Remark first that the definition of the total variation norm given in (2.29) implies that

We consider first the case k = k . Using the definition of Q of equation (A.3) and considering arbitrarily that i ≥ i, we bound

the triangle inequality as follows:

where F Δ|A and f Δ|A are defined in equations (A.6) and (A.7). Because we have assumed that A = [P min P max ] with P min > for some > 0, it follows from direct calculations from (A.6) and (A.7), that the function (x, a) → F Δ|A (x|a)

is K-Lipschitz for some K, the function (x, a) → f Δ|A (x, a) is bounded by some constant K and is K -Lipschitz. From these observations it follows that

To conclude the proof, it suffices to take

-Appendix D -Appendices of Chapter 4

where 1 B (s n+1 ) is the function that is equal to 1 if s n+1 ∈ B and 0 otherwise.

In our case, the transition kernel has the following expression:

By definition, we have

where, for Rayleigh channels, we have that α ij is exponentially distributed with 129 mean ᾱij . After tedious computations we get, F Δ|P (δ|p 2 ):

where the time indexes has been dropped. Let also f Δ|P (x|p 2 ) be the corresponding to pdf,

The proof of this Lipschitz continuity property is exactly the same as the one proposed in Appendix C.2 except that we consider the functions F Δ|P (x|p 2 ) and f Δ|P (x, p 2 ) from equations (D.4) and (D.5).

D.3 Proof of Lipschitz continuity of r 2

In this appendix we prove that the function defined as

is Lipschitz continuous.

We first study the function defined as follows

After some tedious calculations, v(r, p 2 ) can be expressed as follows:

v(r, p 2 ) = r p 2 ᾱ22 exp -

Abstract

Automatic Repeat Request protocols (ARQ) are widely implemented in current mobile wireless standards such as HSDPA and LTE. In general, ARQ protocols are combined with channel coding to overcome errors caused by the lack of channel knowledge at the transmitter side. These protocols are called Hybrid ARQ protocols (HARQ). HARQ protocols ensure a good reliability (at least a small packet error rate) of the physical layer for the OSI upper layers. The purpose of this thesis is to provide tools for the analysis and the optimization of HARQ communication systems with an emphasis on cognitive systems. Cognitive Radio (CR) is an approach aiming to increase the spectral efficiency of wireless networks. In a CR context, unlicensed users are allowed to communicate within the same frequency bands and at the same time as licensed users. Secondary users must however limit the amount of interference generated on the primary users signals. In this thesis, we consider a scenario in which the secondary user interferes a primary user employing a HARQ protocol. When the secondary user knows the state of the primary HARQ protocol, we show that a joint power and rate allocation can be performed to limit the interference.