Vincent Bouvatier
email: vbouvatier@u-paris10.fr

Laetitia Lepetit
email: laetitia.lepetit@unilim.fr

Carlos Bautista

Christian Bordes

Thérèse Chevallier-Farat

Falko Fetch

Antoine Faure-Grimaud

Andy Mullineux

Emmanuelle Nys

Alain Sauviat

Frank Strobel

Amine Tarazi

Clas Wihlborg

Provisioning Rules and Bank Lending: A Theoretical Model

Keywords: loan market, provisioning system, pro-cyclicality

This paper develops a partial equilibrium model of a banking …rm to analyze how provisioning rules in ‡uence loan market ‡uctuations. We show that a backwardlooking provisioning system ampli…es the pro-cyclicality of loan market ‡uctuations. We demonstrate that, in a forward-looking provisioning system where statistical provisions are used to smooth the evolution of total loan loss provisions, the issue of pro-cyclicality of loan market ‡uctuations does not exist. Our results support the recent call of the Basel Committee for the implementation of a forward-looking provisioning system to address procyclicality.

Introduction

An excessive cyclicality of bank lending can create a number of potential problems such as exacerbating the business cycle, increasing systemic risk and misallocating lending resources [START_REF] Berger | The institutional memory hypothesis and the procyclicality of bank lending behavior[END_REF]. As a result, all factors which amplify the cyclicality of bank lending may represent risks to both the macroeconomy and …nancial stability.

Several theories of bank behavior, such as disaster myopia [START_REF] Guttentag | Disaster myopia in international banking[END_REF], herd behavior [START_REF] Rajan | Why bank credit policies ‡uctuate: A theory and some evidence[END_REF] or the institutional memory hypothesis [START_REF] Berger | The institutional memory hypothesis and the procyclicality of bank lending behavior[END_REF], highlight the role of banks in the pro-cyclical variations in loan market conditions.

Empirical investigations [START_REF] Asea | Lending cycles[END_REF][START_REF] Lown | The credit cycle and the business cycle: new …ndings using the loan o¢ cer opinion survey[END_REF]) also show that changes in lending standards imposed by banks increase the cyclicality of bank lending and then amplify the business cycle. Some authors also show that the capital adequacy constraint may lead banks behavior to amplify the credit cycle [START_REF] Bikker | Cyclical patterns in pro…ts, provisioning and lending of banks[END_REF], Zicchino, 2005) 1 . However, the literature mentioned above provides only a partial explanation of the stylized facts about cyclicality because it disregards banks' provisioning practices and their links with the cyclicality of bank lending. In this paper, we focus on provisioning rules and their e¤ects on the loan market. In most countries, loan loss provisions are made up of general provisions and speci…c provisions. General provisions refer to probabilistic losses that cannot be supported by loan speci…c documentation. There are therefore highly judgmental and are in many countries subject of regulatory restrictions. Speci…c provisions refer instead to certain events (such as due payments or other defaultlike events) for which a speci…c documentation can be produced and they are tied by accounting rules to identi…ed problem loans. Such provisioning systems are therefore said to be backward-looking. Speci…c provisions are mainly linked to problem loans and are therefore counter-cyclical 2 . Stylized facts show that total loan loss provisions are negatively a¤ected by the output growth rate [START_REF] Cavallo | Do banks provision for bad loans in good time? Empirical evidence and policy implications[END_REF][START_REF] Laeven | Loan Loss Provisioning and Economic Slowdowns: Too Much, Too Late?[END_REF][START_REF] Bikker | Bank provisioning behavior and procyclicality[END_REF] and that the ratio of loan loss provisions to total loans is highly counter-cyclical [START_REF] Clerc | To what extent are prudential and accounting arrangements pro-or countercyclical with respect to overall …nancial conditions?[END_REF][START_REF] Arpa | The in ‡uence of macroeconomic developments on Austrian banks: implications for banking supervision[END_REF][START_REF] Fernandez De Lis | Credit growth, problem loans and credit risk provisioning in Spain[END_REF][START_REF] Pain | The provisioning experience of the major UK banks: A small panel investigation[END_REF]. This suggests that speci…c provisions are the main determinant of changes in total loan loss provisions 3 .

We consider that such a backward-looking provisioning system represents an unsatisfactory institutional arrangement over a business cycle because expected loan losses are inadequately taken into account, being mainly covered with speci…c provisions when loans turn bad. On the contrary, banks should rather cover their expected loan losses progressively as soon as loans are granted. The gap between loan loss provisions and expected loan losses could a¤ect loan market ‡uctuations, given that loan loss provisions directly a¤ect the cost of bank lending. If banks do not build up loan loss provisions during economic upswings, the cost of loans is understated. Banks have then incentives to ease lending standards. By contrast, during a downturn, the cost of loans is understated if banks had not accumulated loan loss reserves over prior periods to deal with contemporaneous problem loans. Banks can therefore tighten conditions on the loan market.

A forward-looking provisioning system, also called a dynamic or statistical provision-2 Indeed, speci…c provisions increase during an economic downturn when a signi…cant deterioration in credit quality occurs, and decrease during an economic upswing when the likelihood of loan default is low.

3 Banks can also develop a discretionary income smoothing behavior [START_REF] Cavallo | Do banks provision for bad loans in good time? Empirical evidence and policy implications[END_REF][START_REF] Laeven | Loan Loss Provisioning and Economic Slowdowns: Too Much, Too Late?[END_REF][START_REF] Bikker | Bank provisioning behavior and procyclicality[END_REF]. When earnings are expected to be low (high), loan loss provisions are deliberately understated (overstated) to mitigate adverse e¤ects of other factors on earnings. Such a behavior can reduce the cyclicality of loan loss provisions.

ing system4 , could provide a satisfactory institutional arrangement to cover expected loan losses. In such a system, a new element, called the statistical provisions, is introduced aside from speci…c and general provisions. These statistical provisions are de…ned by accounting rules to cover expected losses. Banks have to evaluate the latent risk over a whole business cycle of their loan portfolio. Statistical provisions are de…ned as the di¤erence between the estimation of latent losses and speci…c provisions. During an upswing phase, speci…c provisions are generally low and banks can therefore build up a fund of statistical provisions. Conversely, during a downturn, speci…c provisions increase and can be greater than latent losses, which means that the fund of statistical provisions previously accumulated is used to cope with numerous contemporaneous problem loans. As a result, statistical provisions o¤set the counter-cyclical evolutions of speci…c provisions, and total loan loss provisions are smoothed over time5 .

The cyclicality of provisioning systems has already been investigated from an empirical point of view [START_REF] Borio | Procyclicality of the …nancial system and …nancial stability: issues and policy options[END_REF][START_REF] Clerc | To what extent are prudential and accounting arrangements pro-or countercyclical with respect to overall …nancial conditions?[END_REF][START_REF] Bikker | Bank provisioning behavior and procyclicality[END_REF] for example), as well as the impact of such cyclicality on bank lending (Bouvatier and[START_REF] Bouvatier | Banks' procyclicality behavior: does provisioning matter ?[END_REF]2010). However, there is no theoretical model, to our knowledge, which examines the e¤ects of loan loss provisions on the loan market. This paper is an attempt to …ll this gap in the literature. More precisely, we develop a partial equilibrium model of a banking …rm to analyze how provisioning rules in ‡uence loan market ‡uctuations.

We show that a backward-looking provisioning system ampli…es the pro-cyclicality of loan market ‡uctuations. We demonstrate that, in a forward-looking provisioning system where statistical provisions are used to smooth the evolution of total loan loss provisions, the issue of pro-cyclicality of loan market ‡uctuations does not exist. Our results support the recent call of the Basel Committee for the implementation of a forward-looking provisioning system to address procyclicality (Basel Committee on Banking Supervision, 2010).

The remainder of the paper is organized as follows. Section 2 presents the theoretical model. The optimal behavior of the bank under the di¤erent provisioning systems is presented in section 3. Section 4 concludes the paper.

The model

We develop a partial equilibrium model of a representative banking …rm. We assume that the representative bank i (i = 1; :::; N ) is specialized in loans of type i. Specialization can refer to a type of borrower, sector or to a geographical area [START_REF] Carletti | Bank mergers, competition and liquidity[END_REF]. The representative bank i supply therefore only loans of type i and operates in a monopolistic competition market. We also assume that the bank i faces an exogenous business cycle.

Our aim is to explicitly introduce bank provisioning behavior. Three provisioning systems are considered. Firstly, we consider a strict backward-looking provisioning system in which loan loss provisions are triggered by past due payments. In such a system, the bank evaluates its credit risk exposure over the short run (i.e. on current non performing loans) and then sets loan rates depending on economic conditions. Secondly, we examine a forward-looking provisioning system in which loan loss provisions consist of two components: one related to past due payments and another one related to expected losses in order to o¤set the counter-cyclical behavior of the …rst component. In this case, credit risk exposure is assessed over a whole business cycle. This implies that the determination of loan rates is less a¤ected by economic conditions. Finally, we consider the capital bu¤er system where the representative bank applies backward-looking provisioning rules and uses a capital bu¤er in order to cover expected losses which are not covered by loan loss provisions. The model allows comparison of the bank's behavior on the loan market in these three provisioning systems6 . As the loan rate depends on the provisioning rules, the Modigliani-Miller theorem breaks down and then the choice of accounting methods matters for real decisions.

Activities of the bank and pro…t function

The representative bank i performs an intermediation activity7 . We assume that banks supply long-term loans with a ‡exible interest rate8 . Its asset side is made up of loans (L i;t ) and a safe assets (S i;t ). As the loan portfolio contains expected loan losses, loan loss reserves (LLR i;t ) are deducted from assets. Loans minus loan loss reserves are called net loans [START_REF] Walter | Loan loss reserves[END_REF]. The liability side is made up of debts9 (D i;t ) and equity (K i;t ).

The bank balance sheet identity is

L i;t LLR i;t + S i;t = D i;t + K i;t : (1)
We assume that equity and loan loss reserves are invested in safe assets such as government bonds 10 , so that

S i;t = LLR i;t + K i;t : (2)
The safe asset is supposed to be a short term investment of one period. This assumption assures that equity and loan loss reserves are liquid and available to face losses.

The pro…t of bank i ( i;t ) comes from its intermediation activity

i;t = r L i;t L i;t (1 J(y t ) G(y t )) + r M t S i;t r M t D i;t LLP i;t L i;t G(y t ); (3)
where r L i;t is the interest rate on loans, r M t is the risk-free interest rate applied to debts and safe assets, y t is output, functions J(y t ) and G(y t ) represent respectively the fraction of non performing loans (i.e. problem loans) and the fraction of charged-o¤ loans 11 , LLP i;t represents loan loss provisions and L i;t G(y t ) represents unanticipated charge-o¤s (i.e.

charge-o¤s for which the bank did not set aside loan loss reserves) 12 . The fractions of 10 Not all government bonds can be considered as safe assets, particularly with the sovereign debt crisis undergone by some countries. But we consider that bonds underwriten by some countries such as Germany and the United-States can be considered as safer. However, the German euro denominated bonds can no longer be regarded as totally riskless given their exposure to the sovereign debt crisis of some European countries. The US dollar denominated bonds of the United-States are also not totally riskless due to the credit risk of the municipalities and the importance of national debt which exceeds 80% of GDP [START_REF] Reinhart | This time is di¤erent, eight centuries of …nancial folly[END_REF]. Further, non-in ‡ation indexed bonds face in ‡ation risks, and countries whose exchange rates are not pegged to the euro or the USD will also face exchange rate risks if they hold reserves in German or US bonds.

11 Charged-o¤ loans occur when debts are uncollectible and are removed from the balance sheet.

12 The loan portfolio is made up of three loan categories during period t: (i ) good loans, (ii ) problem loans and (iii ) charged-o¤ loans. As we will see during the calibration of the model based mainly on the database Bankscope Fitch IBCA, most loans are good loans. Loans judged likely to produce a loss are classi…ed as problem loans. Recognized losses are classi…ed as charged-o¤ loans. Most of these charged-o¤ loans were classi…ed as problem loans over prior periods. But some loans can directly move from category (i ) to category (iii ). If the bank did not make loan loss reserves on them, they are called unanticipated charge-o¤s. We assume for simplicity that is constant. We could consider that this parameter is a¤ected by a shock when numerous or few loans are directly move from category (i ) to category (iii ) but this point is out of the scope of the paper.

non performing loans and of charged-o¤ loans are de…ned by J(y t ) = j 0 (y t =y) ! z t ;

(4)

G(y t ) = g 0 (y t =y) v t ; (5)
where j 0 and g 0 are respectively the steady state fraction (or average fraction over a whole business cycle) of non performing loans and of charged-o¤ loans per period, y t =y represents the output gap (y is therefore the steady state output and y t the current output), > 0 and ! > 0 are the elasticities with respect to the output gap, and z t and v t represent shocks with mean one and standard deviation z and v 13 . The output gap a¤ects the …nancial situation of …rms and households and therefore negatively a¤ects the fraction of non performing loans and of charged-o¤ loans. The shocks z t and v t underline that non performing loans and charged-o¤ loans are not fully predictable even if the output gap is known. In addition, we do not assume that non performing loans and charged-o¤ loans depend on the interest rate charged by the bank. The model does not focus on problems of moral hazard or adverse selection in the loan market 14 .

Equation (3) states that the bank pro…t comes from the interest rate on loans. However, interest earnings accrued but not received on problem loans and on charged-o¤ loans during the period are subtracted from earnings. The bank receives therefore interest only on the proportion (1 J(y t ) G(y t )) of its loan portfolio: The fraction (1 ) of charged-o¤ loans had been provisioned over prior periods and does not a¤ect current earnings, whereas unanticipated charged-o¤ loans ( L i;t G(y t )) are subtracted from earnings since 13 These shocks will be speci…ed during the calibration of the model. 14 We can also note than we do not assume that charged-o¤ loans depend explicitly on last period's nonperforming loans because some loans can directly move from the good loans category to the charged-o¤ loans category and also because the fraction of nonperforming loans which move into the charged-o¤ loans category is not necessarily the same for each period. they represent recognized losses which had not been anticipated. The bank has to pay for debts (r M t D i;t ). In addition, loan loss provisions (LLP i;t ) are charged against earnings to account for expected losses covered during the current period 15 . We can therefore see from equation ( 3) that provisioning rules in ‡uence the bank's pro…t.

Pro…ts are shared between retained earnings (K i;t+1 K i;t ) used to modify the level of equity and dividends paid out to shareholders ( i;t )

i;t = K i;t+1 K i;t + i;t : (6)
Negatives dividends operate as equity issuing, and retained earnings are used to comply with the risk-based capital requirement which can be written as

K i;t+1 > k 0 L i;t+1 ; (7)
where k 0 is the regulatory threshold (the tier 1 requirement is 4% in Basel I) and we assume a risk weight on loans of one. We assume for simplicity that this regulatory constraint (equation ( 7)) is always binding; banks hold the minimum regulatory capital required 16 . Equation (6) shows that the choice between dividends and retained earnings is intertemporal. The level of capital at the beginning of the period K i;t is considered as given and the level of retained earnings chosen by the bank gives the level of capital available for the next period (K i;t+1 ). The risk-based capital requirement is therefore written for period t + 1.

15 Our variable LLP i;t has three di¤erent speci…cations according to the provisioning system considered (see section 2.2). 16 This simpli…cation allows us to focus on bank provisioning behavior. However, it could also be interesting in a further developement to examine the e¤ects of the capital requirement on the banks' lending behavior. For example, [START_REF] Fur…ne | Bank portfolio allocation: the impact of capital requirements, regulatory monitoring and economic conditions[END_REF] considers in his model the cost of equity issuing and the cost related to a binding capital constraint in order to specify how the bank sets its equities.

Provisioning rules

Provisioning rules are de…ned by the banking regulator. These rules can be backwardlooking, i.e. based on current non performing loans, or forward-looking, i.e. speci…ed in order to smooth provisions made by the bank over a whole business cycle. In addition, if the bank believes that not enough loan loss provisions have been done according to regulatory requirements, the bank can hold a capital bu¤er.

We consider three speci…cations of the model according to provisioning rules and practices : a strict backward-looking provisioning system, a forward-looking provisioning system and a capital bu¤er system17 .

The strict backward-looking provisioning system

The …rst provisioning system is a strict backward-looking provisioning system in which the bank strictly implements the backward-looking provisioning rules. The analysis of the bank's lending behavior in such a system will allow us to highlight the role of loan loss provisions in the pro-cyclical variation in loan market conditions. We therefore assume that the bank uses the accounting pro…t in its optimizing behavior and does not try to o¤set the weaknesses of the backward-looking accounting rules to determine the economic pro…t.

In a backward-looking provisioning system, loan loss provisions are driven by non performing loans. Loan loss reserves …t therefore identi…ed problem loans rather than expected loan losses 18 . Loan loss provisions are de…ned as following

LLP i;t = H B (L i;t ; y t ) = h 0 L i;t J(y t ) (8)
where L i;t reprents the loans, y t is the current output, h 0 is the steady state fraction (or average fraction over a whole business cycle) of non performing loans (L i;t J(y t )) which are covered by loan loss provisions during a period.

This speci…cation ensures a counter-cyclical evolution of loan loss provisions which is the main stylized fact in a backward-looking provisioning system (see [START_REF] Clerc | To what extent are prudential and accounting arrangements pro-or countercyclical with respect to overall …nancial conditions?[END_REF][START_REF] Arpa | The in ‡uence of macroeconomic developments on Austrian banks: implications for banking supervision[END_REF][START_REF] Fernandez De Lis | Credit growth, problem loans and credit risk provisioning in Spain[END_REF][START_REF] Pain | The provisioning experience of the major UK banks: A small panel investigation[END_REF]. Identi…ed problem loans underestimate expected loan losses during an economic expansion and the bank has to make numerous loan loss provisions during the downturn. This system has therefore a pro-cyclical e¤ect on bank pro…ts.

The forward-looking provisioning system

In the forward-looking provisioning system, the accounting rules require that the bank make loan loss provisions related both to past due payments and to expected losses. Total loan loss provisions are therefore smoothed over time and loan loss reserves …t expected losses of the loan portfolio. Loan loss provisions in the forward-looking provisioning system are de…ned as follow

LLP i;t = H F (L i;t ) = h 0 L i;t j 0 ; (9)
where H F (L i;t ) represents total loan loss provisions 19 . Loan loss provisions are smoothed around the steady state expected loss per period (h 0 L i;t j 0 ). The counter-cyclicality of non performing loans related to the business cycle is not relevant anymore to determine loan loss provisions. As a result, economic pro…t and accounting pro…t are the same in such a system, as expected losses are perfectly taken into account by accounting rules.

The capital bu¤er system

In the capital bu¤er system, backward-looking provisioning rules are implemented but the bank takes into account the weaknesses of this accounting practice and tries to evaluate its economic pro…t. We assume that the bank builds a capital bu¤er (KB t ) to cover the expected losses which are not covered by loan loss reserves 20 . The law of motion of the capital bu¤er is de…ned by

KB i;t+1 = KB i;t + (H F (L i;t ) H B (L i;t ; y t )): (10)
The amount ( H F (L i;t ) H B (L i;t ; y t )) represents the di¤erence between loan loss provisions in the forward-looking provisioning system and loan loss provisions in the backwardlooking provisioning system, i.e. provisions related to expected losses. A fraction 2 [0; 1] is added to the capital bu¤er. For example, if problem loans are low ( H F (L i;t ) > H B (L i;t ; y t )), expected losses over period t are understated in the backward-looking provi-19 H F (L i;t ) reprents the sum of the two components of loan loss provisions, one related to past due payments and the other one related to expected losses. The latter component is therefore equal to h 0 L i;t j 0 (1 (y t =y) ! z t ): As a result, provisions in the forward-looking system do not explicitly depend on statistical prediction of non performing loans at period t + 1. Rules are speci…ed in order to smooth provisions made by the bank over a whole business cycle. 20 Banks hold more prudential capital than that required by regulators, with a total capital bu¤ers (Tier 1 plus Tier 2) on average across the EU15 of 2.93 per cent over the period 1997[START_REF] Bikker | Cyclical patterns in pro…ts, provisioning and lending of banks[END_REF][START_REF] Jokipii | The cyclical behaviour of European bank capital bu¤ers[END_REF]. Several reasons have been put forward to explain why banks hold excess capital [START_REF] Jokipii | The cyclical behaviour of European bank capital bu¤ers[END_REF]. One of these explanations is that capital bu¤ers can be used to cover expected future losses. In the model we do not make the distinction between Tier 1 capital and general provisions (which are included in Tier 2 capital). They are considered as equivalent in the capital bu¤er hold by the bank.

sioning system and then the bank increases the capital bu¤er by ( H F (L i;t ) H B (L i;t ; y t ))

to obtain a better estimate of its economic pro…t21 . The capital bu¤er is added to standard equity (K i;t ). We de…ne therefore total capital (T K i;t ) as

T K i;t = K i;t + KB i;t : (11)
Then, the bank balance sheet becomes

L i;t + S i;t LLR i;t = D i;t + T K i;t : (12)
We assume that the capital bu¤er is invested in safe assets (S i;t ) so that

S i;t = LLR i;t + T K i;t : (13)
The bank's ‡ow budget constraint is given by

T K i;t+1 T K i;t + i;t = r L i;t L i;t (1 J(y t ) G(y t )) + r M t S i;t r M t D i;t LLP i;t L i;t G(y t ): (14)

Loan demand

We assumed that the representative bank i operates in a monopolistic competition market. Banks o¤er di¤erentiated loans and then each bank faces a speci…c demand for its type of loans. Based on [START_REF] Henzel | The price puzzle revisited: can the cost channel explain a rise in in ‡ation after a monetary policy shock?[END_REF] and [START_REF] Carletti | Bank mergers, competition and liquidity[END_REF], we de…ne this speci…c loan demand as

L i;t = r L i;t r L t ! L t ; (15)
where L t is the aggregated demand for loans, r L t is the average interest rate on loans, is the elasticity of L i;t with respect to the interest rate on loans and is the bank market share (with = 1=N ). The parameter represents therefore an inverse measure of the bank monopolistic power.

The bank maximization behavior

We assume that the bank maximizes the present discounted value of future dividends.

The bank's maximization problem consists of choosing the interest on loans (r L i;t ). In the backward-looking provisioning system, the maximization problem is written as

max r L i;t E t 1 X j=0 t+j t+j ; (16)
where

t = r L i;t L i;t (1 J(y t ) G(y t )) r M t D i;t LLP i;t L i;t G(y t ) + K i;t K i;t+1; (17)
subject to equations ( 1), ( 2), ( 4), ( 5), ( 7), ( 8), and ( 15), and where is a standard discount factor22 . In the forward-looking provisioning system, equation ( 8) is replaced with equation ( 9). In the capital bu¤er system, the bank maximization problem is the same than in the backward-looking provisioning system except that: (i) equations ( 10), ( 11) are added as constraints; (ii) equations ( 1) and ( 2) are replaced with equations ( 12) and ( 13); (iii) dividends are given by equation ( 14).

Optimal interest rate on loans

The …rst order condition (FOC) gives the optimal interest rate on loans. We obtain in the backward-looking provisioning system (details are available upon request)

r L i;t (1 J(y t ) G(y t )) = 1 r M t + h 0 J(y t ) + G(y t ) + (k 0 = k 0 ) : (18)
As the bank earns interest only on a fraction of their loans (1 J(y t ) G(y t )), the lefthand side of equation ( 18) represents the marginal return on loans. The right-hand side of equation ( 18) shows that several factors in ‡uence the bank when setting the loan interest rate. More precisely, the bank applies a mark-up ( =( 1)) on the marginal cost of its lending activity.

There are four components in the marginal cost of the bank's lending activity : the cost of debt (r M t ), the provisioning cost (h 0 J(y t )), the unanticipated charge-o¤s cost ( G(y t ))

and the cost related to the capital requirement ((k 0 = k 0 )). Anticipated recognized losses had been provisioned over prior periods and do not a¤ect the current pro…t. As a result, provisioning rules (i.e. the rules according to which losses are anticipated) matter in the optimal decision concerning the loan interest rate. In the strict backward-looking system, loan loss provisions depend mainly on problem loans and then the provisioning cost is negatively a¤ected by the business cycle.

This e¤ect of provisioning rules on the loan rate is di¤erent in the forward-looking provisioning system. The FOC is given by

r L i;t (1 J(y t ) G(y t )) = 1 r M t + h 0 j 0 + G(y t ) + (k 0 = k 0 ) : (19)
Provisions related to expected losses o¤set the counter-cyclical evolution of provisions related to past due payments, so that loan loss provisions are no more a¤ected by the counter-cyclical evolutions of problem loans. As a result, the marginal provisioning cost is given by h 0 j 0 .

In the capital bu¤er system, the bank applies backward-looking provisioning rules and creates a capital bu¤er to cover the expected loan losses which are not covered by loan loss reserves. The optimal decision regarding the interest rate on loans is given by

r L i;t (1 J(y t ) G(y t )) = 1 r M t + h 0 ( j 0 + (1 )J(y t )) + G(y t ) + (k 0 = k 0 ) : (20)
The di¤erences between equations ( 19) and ( 20) show that the bank's behavior is identical in the capital bu¤er system and the forward-looking provisioning system only if = 1.

Under this condition, the expected losses not covered by loan loss reserves are fully covered by the capital bu¤er. However, a high capital bu¤er requires that the bank uses retained earnings to increase its capitalization instead of increasing dividends during economic upswings. Shareholders may not appreciate such a strategy and may demand higher dividends (and then < 1). Banks may therefore not be able to completely o¤set the counter-cyclical evolution of loan loss provisions by building a capital bu¤er.

The forward-looking provisioning system presents the advantage to require banks to also make provisions related to expected losses that smooth the evolution of total loan loss provisions.

Business cycle and loan market

We can see with equations ( 18), ( 19) and ( 20) that the interest rate on loans is the same in the three provisioning systems when considering the steady state. It is given by23

r L (1 j 0 g 0 ) = 1 r M + h 0 j 0 + g 0 + (k 0 = k 0 ) ; (21)
where r L and r M represent respectively the steady state value of the loan interest rate and of the interest rate on debts.

However, the short term dynamics in the loan market are di¤erent for the three provisioning systems. These dynamics can be appreciated by log-linearizing the …rst order condition on the interest rate on loans (equations ( 18), ( 19) and ( 20)). We also introduce the aggregate loan demand. Based on the work of [START_REF] Calza | Credit in the euro area: An empirical investigation using aggregate data[END_REF], the aggregate loan demand is as following24

Lt = y ŷt r L (r L t E t f^ t+1 g); ( 22
)
where t is the in ‡ation rate. The aggregate loan demand increases when output increases, and decreases when the real loan rate increases.

In the backward-looking provisioning system, the log-linearization of equation ( 18) is given by (details are available upon request)

' 0 rL t = ' 1 rM t + ' 2 ẑt + ' 3 vt ' 4 ŷt ; (23)
where ' 0 r L (1 j 0 g 0 ); ' 1 Zr M ; ' 2 r L j 0 +Zh 0 j 0 ; ' 3 r L g 0 +Z g 0 ; ' 4 !' 2 + ' 3 and Z =( 1).

The loan market dynamics depend on several factors. First, deviations of the loan rate (r L t ) around its steady state depend on deviations of the interest rate on debt (r M t ).

Variations in …nancing costs are therefore passed on to the loan rate and lead to changes in loans ( Lt ) as we can see from equation ( 22).

Second, shocks on problem loans (ẑ t ) and on charged-o¤ loans (v t ) positively a¤ect the loan rate rL t . We have an increase in credit risk in case of positive shocks, which leads to an increase in the loan rate and then to a decrease in loans. The e¤ect of a charged-o¤ loans shock on rL t is measured by the parameter ' 3 . This parameter is made up of two components and suggests that an increase in the fraction of charged-o¤ loans impacts on rL t because the bank faces (i) a decrease in interest earnings (r L g 0 ) and (ii)

an unanticipated loss (Z g 0 ). Similarly, the e¤ect of a non performing loans shock is measured by the parameter ' 2 : An increase in the fraction of non performing loans leads to both a decrease in interest earnings (r L j 0 ) and to an increase of provisions (Zh 0 j 0 ), as suggested by the two components of the parameter ' 2 :

Third, the business cycle (ŷ t ) negatively a¤ects the loan rate rL t . This e¤ect is measured by the parameter ' 4 !' 2 + ' 3 . The business cycle a¤ects the bank's behavior through its impact on the levels of non performing loans and of charged-o¤ loans. An economic downturn implies an increase in problem loans and charged-o¤ loans, leading to an increase in the loan rate. This reinforces the direct e¤ect of the business cycle on loans, measured by the parameter y in equation ( 22).

Equations ( 22) and ( 23) show therefore that the provisioning system matters in the loan market dynamics. Provisions are driven by problem loans in a backward-looking provisioning system. These provisioning rules amplify the e¤ects of the business cycle (ŷ t ) and of a non performing loans shock (ẑ t ) on the loan market. This ampli…cation e¤ect is measured by Zh 0 j 0 in the parameter ' 2 .

Proposition 1:

A backward-looking provisioning system ampli…es the e¤ect of the business cycle on the loan market. The magnitude of this e¤ect depends on the impact of the business cycle on loan loss provisions.

This magnifying e¤ect of loan loss provisions on the loan market is no more relevant in a forward-looking provisioning system where loan loss provisions do not only depend on problem loans. The log-linearization of the FOC on the loan interest rate (equation ( 19)) is given by

' 0 rL t = ' 1 rM t + ' 0 2 ẑt + ' 3 vt ' 0 4 ŷt ; (24)
where ' 0 2 r L j 0 and ' 0 4 !' 0 2 + ' 3 .

The e¤ect of a non performing loans shock is smaller in the forward-looking provisioning system (' 0 2 < ' 2 ). The e¤ect of the business cycle is also smaller (' 0 4 < ' 4 ). The deviations of the loan rate as well as the ‡uctuations in the loan market are therefore less important in a forward-looking provisioning system where provisions related to past due payments do not longer a¤ect the bank's behavior since their variations are o¤set by provisionsmade to cover expected losses.

Proposition 2:

The provisioning rules do not amplify the e¤ect of the business cycle on the loan market in a forward-looking provisioning system.

The third provisioning system that we considered is the capital bu¤er system. The log-linearized FOC on the loan rate (equation ( 20)) is given by

' 0 rL t = ' 1 rM t + ' 00 2 ẑt + ' 3 vt ' 00 4 ŷt ; (25)
where ' 00 2 r L j 0 + Z(1 )h 0 j 0 and ' 00 4 !' 00 2 + ' 3 :

If is equal to 1, the capital bu¤er and loan loss reserves are mixed to fully cover expected losses. In this case, the behavior of the bank is the same as in the forwardlooking provisioning system (' 00 2 = ' 0 2 and ' 00 4 = ' 0 4 ) and provisioning rules do not amplify the e¤ect of the business cycle25 . However, the constraint = 1 requires the bank to accumulate a capital bu¤er during the economic expansion which will be used during the downturn.

Proposition 3:

The use of a capital bu¤er to cover the expected losses o¤sets the e¤ect of the business cycle on provisions; however, this might imply a high ‡uctuation in the capital of the bank.

Concluding remarks

Our model shows that accounting rules on loan loss provisions matter to explain loan market ‡uctuations. We …nd that a backward-looking provisioning system ampli…es the pro-cyclicality of bank lending. Such an e¤ect is removed in a forward-looking provisioning system where statistical provisions smooth total loan loss provisions over the business cycle. This e¤ect can also be removed with a capital bu¤er system, but this solution might imply large variations in banks' equity. Our work therefore shows that the capital requirement is not the only institutional constraint which may amplify the cyclicality of lending. Accounting rules on loan loss provisions are also a decisive factor to explain the pro-cyclicality of banks'behavior. A strict backward-looking provisioning system contributes to amplify the cyclicality of bank lending and a capital bu¤er cannot easily remove this e¤ect. In Europe, the provisioning system is backward-looking (excluding Spain) but banks do not implement these accounting rules strictly. Consequently, for practical purposes, European banks behave as if in a capital bu¤er system in which banks can try to o¤set weaknesses of backward-looking provisioning rules. [START_REF] Clerc | To what extent are prudential and accounting arrangements pro-or countercyclical with respect to overall …nancial conditions?[END_REF] highlight that such a system leads to a procyclical evolution of the ratio of loan loss provisions to total loans. It means that European banks do not succeed in o¤setting weaknesses of backward-looking provisioning rules by covering expected losses with equity or discretionary loan loss provisions.

The conclusions from this paper support the recent call of the Basel Committee for the implementation of a forward-looking provisioning system to address procyclicality. More precisely, the reform programme developed by the Basel Committee and referred as "Basel III" stresses the importance of implementing a capital bu¤er system and a forward-looking provisioning system as prudential measures to mitigate procyclicality in the banking sector (Basel Committee on Banking Supervision, 2010). But such a reform requires a change of accounting standards towards an expected loss approach. In this regard, the Committee is working closely with the International Accounting Standards Board (IASB)

to reform the Fair Value Accounting system based on IAS 39. The objective is to reform "the accounting model for provisioning to allow early identi…cation and recognition of losses by incorporating a broader ranger of available credit information than presently included in the incurred loss model" (Basel Committee on Banking Supervision, 2009).

The implementation of a such model that allows earlier recognition of credit losses will build up the level of provisions at an earlier point in time and will decrease the cyclicality of lending; this could help …nancial institutions to cope better with potential future crises.

Capital requirements is said to be procyclical because during a downturn capital becomes more expensive and banks often respond by cutting bank lending or shifting towards lower-risk customers. By contrast, in the boom phase, banks can obtain additional capital under more favorable terms, which may give further impetus to their lending.

See Fernandez de Lis et al. (2001),[START_REF] Mann | Dynamic provisioning: issues and application[END_REF] and[START_REF] Jiménez | Credit cycles, credit risk, and prudential regulation[END_REF] for more details about the forward-looking provisioning system. Such a system has been implemented in Spain since 2000.

Therefore, statistical provisions are an alternative to discretionary loan loss provisions made for income smoothing. Indeed,Pérez et al. (2008) show that the implementation of a dynamic provisioning system in Spain reduced the income smoothing behavior.

We do not include general provisions in our model, as they do not matter to modelize the countercyclicality of loan loss provisions[START_REF] Clerc | To what extent are prudential and accounting arrangements pro-or countercyclical with respect to overall …nancial conditions?[END_REF][START_REF] Arpa | The in ‡uence of macroeconomic developments on Austrian banks: implications for banking supervision[END_REF][START_REF] Fernandez De Lis | Credit growth, problem loans and credit risk provisioning in Spain[END_REF][START_REF] Pain | The provisioning experience of the major UK banks: A small panel investigation[END_REF].

 7 The model is written at time

t.8 We assume a ‡exible interest rate on loans for computational

simplicity.9 As in[START_REF] Van Den Heuvel | The bank capital channel of monetary policy[END_REF], bank's liabilities include deposits as well as market debt. Moreover, we assume that all debt liabilities are covered by deposit insurance and that the deposit insurance premium is equal to zero. Therefore, the banks'debt-funding costs do not depend on the debt equity ratio and probability of bankruptcy. The explicit introduction of a positive deposit insurance premium would not alter any result relative to the bank provisioning behavior.

A forward-looking provisioning system is based on the way that banks set loan loss provisions[START_REF] Fernandez De Lis | Credit growth, problem loans and credit risk provisioning in Spain[END_REF],[START_REF] Jiménez | Credit cycles, credit risk, and prudential regulation[END_REF]). We therefore focus on loan loss provisions rather than on loan loss reserves. In addition, we do not need to specify loan loss reserves to solve the model since they are invested in a safe asset. But by de…nition, variations in loan loss reserves are equal to loan loss provisions plus unanticipated charged-o¤ loans (subtracted from earnings) minus charged-o¤ loans[START_REF] Walter | Loan loss reserves[END_REF]. This implies that loan loss provisions are equal to anticipated charged-o¤ loans at the steady state.

An expected loss arises from the moment a loan is granted. Consequently, a future loss can be expected on a good loan. In addition, the bank can estimate its expected losses over a whole business cycle and deduce a constant expected losses per period.

The parameter is exogenous in the model. We do not specify the bank's incentive to build up a capital bu¤er. The capital bu¤er system is simply considered as an alternative to the forward-looking provisioning system.

We assume that the discount factor is constant and does not depend on the cost of equity.

We consider the symetric equilibrium to determine the steady state (r L i;t = r L t = r L ).

The variable Xt denotes the percentage (logarithmic) deviations of the variable X t from its steady state value X.

If = 0; we also note that ' 00 2 = ' 2 and ' 00 4 = ' 4 .


domain: math info spi

text:
Nikolaos Pappas
email: nikolaos.pappas@supelec.fr

Marios Kountouris
email: marios.kountouris@supelec.fr

Anthony Ephremides

Apostolos Traganitis

Relay-assisted Multiple Access with Full-duplex Multi-Packet Reception

Keywords: Full-duplex, relay, cooperative communications, network-level cooperation, multiple access, stability, random access networks

The effect of full-duplex cooperative relaying in a random access multiuser network is investigated here. First, we model the self-interference incurred due to full-duplex operation, assuming multi-packet reception capabilities for both the relay and the destination node. Traffic at the source nodes is considered saturated and the cooperative relay, which does not have packets of its own, stores a source packet that it receives successfully in its queue when the transmission to the destination has failed. We obtain analytical expressions for key performance metrics at the relay, such as arrival and service rates, stability conditions, and average queue length, as functions of the transmission probabilities, the self interference coefficient, and the links' outage probabilities. Furthermore, we study the impact of the relay node and the self-interference coefficient on the per-user and aggregate throughput, and the average delay per packet. We show that perfect self-interference cancelation plays a crucial role when the SINR threshold is small, since it may result to worse performance in throughput and delay comparing with the half-duplex case. This is because perfect self-interference cancelation can cause an unstable queue at the relay under some conditions.

I. INTRODUCTION

Driven by the exponential traffic growth and the ever-increasing demands for wider spectrum, the quest for higher spectral efficiency and enhanced reliability and coverage is creating a new impetus for cooperative communication systems. Cooperative communication aims at increasing the link data rates and the reliability of time-varying links, by overcoming fading and interference in wireless networks. Among the various cooperation techniques to increase throughput, full-duplex relaying has recently gained significant attention. The vast majority of research papers have considered half-duplex or out-of-band full-duplex systems, in which terminals cannot transmit and receive at the same time, or over the same frequency band. However, the use of nodes with in-band full-duplex capability, i.e. terminals that transmit and receive simultaneously over the same frequency band, is constantly increasing in current wireless networks as they can potentially double the network spectral efficiency. Moreover, full-duplex relay systems open a whole new spectrum of capabilities, such as collision detection in contention-based networks. In this work, we focus on a relay-assisted random access network and we analyze the effect of full-duplex cooperative relaying in the network performance, namely arrival and service rates, stability conditions, and average queue length at the relay.

The classical relay channel was originally introduced by van der Meulen [START_REF] Van Der Meulen | Three-terminal communication channels[END_REF], and earlier work on the relay channel was based on information-theoretic formulations, e.g. [START_REF] Cover | Capacity theorems for the relay channel[END_REF]. Most cooperative techniques that have been studied so far focus on the benefits of physical layer cooperation [START_REF] Kramer | Cooperative communications[END_REF]. Nevertheless, there is evidence that the same gains can be achieved with network layer cooperation, which is plain relaying without any physical layer considerations [START_REF] Sadek | Cognitive multiple access via cooperation: Protocol design and performance analysis[END_REF], [START_REF] Rong | Protocol-level cooperation in wireless networks: Stable throughput and delay analysis[END_REF]. Recently several works have investigated relaying performance at the MAC layer [START_REF] Sadek | Cognitive multiple access via cooperation: Protocol design and performance analysis[END_REF]- [START_REF] Pappas | Stability and performance issues of a relay assisted multiple access scheme[END_REF]. More specifically, in [START_REF] Sadek | Cognitive multiple access via cooperation: Protocol design and performance analysis[END_REF], the authors have studied the impact of cooperative communication at the medium access control layer with TDMA. They introduced a new cognitive multiple access protocol in the presence of a relay in the network. In [START_REF] Pappas | Wireless network-level partial relay cooperation[END_REF] the notion of partial network level cooperation is introduced by adding a flow controller at the relay, which regulates the amount of provided cooperation depending on the conditions of the network. The classical analysis of random multiple access schemes, like slotted ALOHA [START_REF] Bertsekas | Data networks[END_REF], has focused on the so-called collision model. Random access with multi-packet reception (MPR) has attracted attention recently [START_REF] Ghez | Stability properties of slotted aloha with multipacket reception capability[END_REF]- [START_REF] Pappas | Stability and performance issues of a relay assisted multiple access scheme with mpr capabilities[END_REF]. All the above approaches come together in the model that we consider.

In wireless networks, when a wireless node transmits and receives simultaneously in the same frequency, the problem of self-interference arises. Self-interference mitigation is a key challenge in in-band fullduplex systems. Information-theoretic aspects of this problem can be found in the pioneering work of Shannon [START_REF] Shannon | Two-way communication channels[END_REF], although the capacity region of the two-way channel is not known for the general case [START_REF] Cover | Elements of Information Theory 2nd Edition[END_REF]. The information-theoretic limits of in-band full-duplex relaying have been studied focusing on the idealistic case of perfect self-interference cancelation [START_REF] Somekh | Cellular systems with full-duplex amplify-and-forward relaying and cooperative base-stations[END_REF], [START_REF] Cadambe | Degrees of freedom of wireless networks with relays, feedback, cooperation, and full duplex operation[END_REF]. There exist several techniques that allow the possibility of perfect self-interference cancelation [START_REF] Cover | Elements of Information Theory 2nd Edition[END_REF]. However, in practice, there are several technological limitations and challenges [START_REF] Nikolaou | Pattern and frequency reconfigurable annular slot antenna using pin diodes[END_REF], [START_REF] Eliezer | A phase domain approach for mitigation of self-interference in wireless transceivers[END_REF], which may limit the accuracy and the effectiveness of self-interference cancelation. Various methods for performing self-interference cancelation at the receivers can be found in [START_REF] Suzuki | A booster configuration with adaptive reduction of transmitter-receiver antenna coupling for pager systems[END_REF] and [START_REF] Halperin | Taking the sting out of carrier sense: interference cancellation for wireless lans[END_REF]. The main result therein is that there is a tradeoff between transceiver complexity and self-interference cancelation accuracy. In [START_REF] Tsubouchi | Full duplex transmission operation of a 2.45-ghz asynchronous spread spectrum using a san convolver[END_REF], [START_REF] Chen | Division-free duplex for wireless applications[END_REF], it was demonstrated in practice real implementations of simultaneous transceivers, where the self-interference problem has been mitigated through RF isolators and echo cancellers, coupled with base-band digital filtering. Furthermore, some recent results have also shown that full duplex is possible, proposing specific designs, e.g. [START_REF] Choi | Achieving single channel, full duplex wireless communication[END_REF], [START_REF] Jain | Practical, real-time, full duplex wireless[END_REF], which mainly focus on the physical and the medium access control (MAC) layer design. Choi et al. in [START_REF] Choi | Achieving single channel, full duplex wireless communication[END_REF] designed a practical single-channel full-duplex wireless system, combining three self-interference cancellation schemes, as well as RF and digital interference cancellation. Jain et al. [START_REF] Jain | Practical, real-time, full duplex wireless[END_REF] presented a full-duplex radio design using signal inversion and adaptive cancellation. Unlike [START_REF] Choi | Achieving single channel, full duplex wireless communication[END_REF], the authors in [START_REF] Jain | Practical, real-time, full duplex wireless[END_REF] consider wideband and high power systems. In theory, this new design has no limitation in terms of bandwidth or power. Therefore, building full-duplex wireless networks (such as full-duplex 802.11n wireless networks) has started becoming feasible. Fang et al. [START_REF] Fang | Pathbook: Cross-layer optimization for full-duplex wireless networks[END_REF] proposed a collision-free full-duplex broadcast MAC and studied cross-layer optimization of MAC and routing in full-duplex wireless networks under various resource and social constraints.

In this work, we extend [START_REF] Pappas | Relay-assisted multiple access with multi-packet reception capability and simultaneous transmission and reception[END_REF] and study the operation of a cooperative node relaying packets from a number of users/sources to a destination node as shown in Fig. 1. We assume MPR capability for both the relay and the destination node. The relay node can transmit and receive at the same time over the same frequency band (in-band full duplex). We assume random medium access, slotted time, and that each packet transmission takes one time slot. The wireless channel is modeled as Rayleigh flat-fading channel with additive white Gaussian noise. A user transmission is successful if the received signal-to-interferenceplus-noise ratio (SINR) is above a certain threshold γ. We also assume that acknowledgements (ACKs) are instantaneous and error free. The relay does not have packets by itself and the source nodes are considered saturated with unlimited amount of traffic. The self-interference cancellation at the relay is modeled as a variable power gain, mainly because we are studying the impact on the network layer. Studying in detail the physical layer implementation of self-interference mitigation and considering specific self-interference cancelation mechanisms is beyond the scope of this paper. We obtain analytical expressions for key performance characteristics of the relay queue, such as arrival and service rates, and we derive conditions for stability and the average queue length as functions of the transmission probabilities, the self-interference coefficient, and the links' outage probabilities. In particular, we study the impact of the relay node and the self-interference coefficient on the per-user and the network-wide throughput, as well as the average delay per packet. Furthermore, we derive expressions for both the per-user and aggregate throughput when the queue at the relay is unstable, for which case we do not have though any guarantees for bounded delay.

The remainder of the paper is organized as follows: Section II describes the system model and in Section III we present the main characteristics of the relay queue, such as the average arrival and service rates. In Section IV, we provide expressions for the per-user and the aggregate throughput. The average delay per packet is obtained in Section V. Numerical results are presented in Section VI, and finally Section VII concludes the paper.

II. SYSTEM MODEL

A. Network Model

We consider a network with n sources, one relay node, and a single destination node. The sources transmit packets to the destination using a cooperative relay; the case of n = 2 is depicted in Fig. 1. We assume that the queues of both sources are saturated, i.e., no external arrivals and unlimited buffer size, and that the relay does not have packets of its own but only forwards the packets it has received from the two users. The relay node stores a source packet that it receives successfully in its queue when the direct transmission to the destination node has failed. We assume a random access channel where q 0 is the transmit probability of the relay given that it has packets in its queue, and q i for i = 0 is the transmit probability for the i-th user. The receivers at the relay and the destination nodes are equipped with multiuser detectors, hence they can decode packets from more than one transmitter at a time. Furthermore, the relay can simultaneously transmit and receive packets (full duplex).

B. Physical Layer Model

The MPR channel model used in this paper is a generalized form of the packet erasure model. We assume that a packet transmitted by node i is successfully received by node j if and only if SINR(i, j) ≥ γ j , where γ j is a threshold characteristic of node j. The wireless channel is subject to fading; let P tx (i) be the transmit power at node i and r(i, j) be the distance between i and j. The received power at j when i transmits is P rx (i, j) = A(i, j)h(i, j) where A(i, j) is a random variable representing small-scale fading. Under Rayleigh fading, A(i, j) is exponentially distributed [START_REF] Tse | Fundamentals of wireless communication[END_REF]. The received power factor h(i, j) is given by h(i, j) = P tx (i)(r(i, j)) -α where α is the path loss exponent with typical values between 2 and 6. We model the self-interference by a scalar g ∈ [0, 1]. We refer to the g as the self-interference coefficient. When g = 1, no self-interference cancelation technique is used, while g = 0 models perfect self-interference cancelation. The success probability in the link ij is given by

P j i/T = exp - γ j η j v(i, j)h(i, j) (1 + γ j (r(i, j)) α g) -m
k∈T \{i,j}

1 + γ j v(k, j)h(k, j) v(i, j)h(i, j) -1 , ( 1
)
where T is the set of transmitting nodes at the same time, v(i, j) is the parameter of the Rayleigh fading random variable, η j is the receiver noise power at j and m = 1 when j ∈ T and m = 0 else. The analytical derivation for this success probability can be found in [START_REF] Tse | Fundamentals of wireless communication[END_REF].

C. Queue Stability

We adopt the definition of queue stability used in [START_REF] Szpankowski | Stability conditions for some distributed systems: Buffered random access systems[END_REF]. Definition 1: Denote by Q t i the length of queue i at the beginning of time slot t. The queue is said to be stable if

lim t→∞ P r[Q t i < x] = F (x) and lim x→∞ F (x) = 1. (2)
If lim x→∞ lim t→∞ inf P r[Q t i < x] = 1, the queue is substable. If a queue is stable, then it is also substable. If a queue is not substable, then we say it is unstable.

Loynes' theorem [START_REF] Loynes | The stability of a queue with non-independent inter-arrival and service times[END_REF] states that if the arrival and service processes of a queue are strictly jointly stationary and the average arrival rate is less than the average service rate, then the queue is stable.

III. PERFORMANCE ANALYSIS FOR THE RELAY QUEUE

In this section, we derive expressions for key performance metrics for the relay queue, namely arrival and service rates, stability conditions, and average queue length. The analysis is provided for two cases:

(i) when the network consists of two non-symmetric in general users, (ii) for n > 2 symmetric users.

This section is an intermediate step before investigating the impact of the relay node in the per-user throughput, the aggregate throughput, and the average per packet delay. In order to study those quantities, we need to first compute the average arrival and service rate of the relay, the average queue length, and the stability conditions. The stability of a queue is translated to bounded queue size, which implies finite queuing delay.

A. Two-user Case

We study first the relay queue characteristics for the two-user case. In this network, at each timeslot, the relay can receive at most two packets (one per user) and to transmit at most one.

The probability that the relay receives i packets in a given timeslot when its queue is empty is denoted by r 0 i , and r 1 i otherwise (not empty). The expressions for the r j i are rather lengthy and are presented in Appendix A. The average arrival rate at the relay when its queue is empty is denoted by λ 0 , and by λ 1 when it is not (derived in Appendix A). The probability that the relay queue increases by i packets when is empty is denoted by p 0 i , and p 1 i when it is not; p i -1 is the probability that the queue decreases by one packet. Note that p j i and r j i are in general different quantities, however p j i = r j i in half-duplex relay systems.

The next theorem presents the main relay queue characteristics for the two-user case. Theorem 3.1: The key performance measures for the relay queue in a two-user network are provided below.

(i) The average service rate is µ = q 0 (1 -q 1 )(1 -q 2 )P d 0/0 + q 0 q 1 (1 -q 2 )P d 0/0,1 + q 0 q 2 (1 -q 1 )P d 0/0,2 + q 0 q 1 q 2 P d 0/0,1,2 ,

where P d 0/0,i,j is the success probability between the relay and the destination when the transmitting nodes are the relay and nodes i and j. P d 0/0,i,j can be computed from ( 1). (ii) The probability that the queue at the relay is empty is

P (Q = 0) = p 1 -1 -p 1 1 -2p 1 2 p 1 -1 -p 1 1 -2p 1 2 + λ 0 . (4)
(iii) The average arrival rate λ is

λ = p 1 -1 -p 1 1 -2p 1 2 p 1 -1 -p 1 1 -2p 1 2 + λ 0 λ 0 + λ 0 p 1 -1 -p 1 1 -2p 1 2 + λ 0 λ 1 . (5)
(iv) The average relay queue size Q is

Q = (p 1 1 + 2p 1 2 -p 1 -1 )(4p 0 1 + 10p 0 2 ) + λ 0 (2p 1 -1 -4p 1 1 -10p 1 2 ) 2(p 1 1 + 2p 1 2 -p 1 -1 )(p 1 -1 -p 1 1 -2p 1 2 + λ 0 ) . (6)
Proof: See Appendix A. Note: The values of q 0 for which the queue is stable are given by q 0min < q 0 < 1, where q 0min is given in (39) in Appendix A. Queue stability is an important parameter for QoS as it implies finite queue delay (due to bounded queue size). The queueing delay is computed in Section V.

B. Symmetric n-user Case

We now investigate the case of a symmetric n-user network. Each user attempts to transmit in a slot with probability q; the success probability to the relay and the destination when i nodes transmit are given by P 0,i and P d,i , respectively. There are two cases for the P d,i , i.e., P d,i,0 and P d,i,1 , denoting the success probability when relay remains silent or transmits, respectively. Those success probabilities for the symmetric case are given by P d,i,j = P d

1 1+γ d i-1 1 1+βγ 0 j , j = 0, 1 and β = v 0d h 0d v d h d > 1. P 0d,i = P 0d 1 1+ 1 β γ d i , P 0 = exp -γ 0 η 0 v 0 h 0 , P d = exp -γ d η d v d h d , P 0d = exp -γ 0 η 0 v 0 h 0 .
There are two cases for the P 0,i , i.e., P 0,i,0 and P 0,i,1 , denoting the success probability when the relay remains silent or transmits respectively. The success probabilities are given by P 0,i,0 = P 0

1 1+γ 0 i-1 and P 0,i,1 = P 0 (1 + γ 0 r α 0 g) -1 1 1+γ 0 i-1
, where r 0 is the distance between the users and the relay, α is the path loss exponent and g is the self-interference coefficient.

The next theorem summarizes the results for the characteristics of the relay queue for the symmetric n-user case.

Theorem 3.2: The key performance measures for the relay queue in the n-symmetric user network are provided below.

(i) The average service rate is

µ = n k=0 n k q 0 q k (1 -q) n-k P 0d,k . (7)
(ii) The probability that the queue at the relay is empty is

P (Q = 0) = p 1 -1 - n i=1 ip 1 i p 1 -1 - n i=1 ip 1 i + λ 0 . (8)
(iii) The average arrival rate λ is

λ = P (Q = 0) λ 0 + P (Q > 0) λ 1 . (9)
The expressions for λ 0 and λ 1 are given in Appendix B. (iv) The average relay queue size Q is

Q = n i=1 ip 1 i -p 1 -1 n i=1 i(i + 3)p 0 i + λ 0 2p 1 -1 - n i=1 i(i + 3)p 1 i 2 n i=1 ip 1 i -p 1 -1 p 1 -1 - n i=1 ip 1 i + λ 0 . ( 10
)
Proof: See Appendix B. The values of q 0 for which the queue is stable are given by q 0min < q 0 < 1, where q 0min is given in (53) in Appendix B.

IV. THROUGHPUT ANALYSIS

In the previous section, we provided the main results on the relay queue characteristics, including the empty queue probability and the average queue length. Here, we derive the per-user throughput and the network aggregate throughput with one cooperative relay and n users.

The per-user throughput, T i for the i-th user is given by T i = T D,i + T R,i , where T D,i denotes the direct throughput from user i to the destination, i.e., the transmitted packet reaches the destination directly, without using the relay. When the transmission to the destination is not successful, and at the same time the relay node receives the packet correctly, then it stores it to its queue, and the contributed throughput by the relay for the user i is denoted by T R,i . When the queue at the relay is stable, T R,i is the arrival rate from user i to the queue.

The term T D,i can also be interpreted as the probability that a transmitted packet from user i reaches the destination directly, and T R,i is the probability of unsuccessful transmission from user i to the destination while the packet is received at the relay.

The percentage of i-th user's traffic that is being relayed is

T R,i
T i . In the following subsection, we provide expressions for T D,i and T R,i for the two-user and the symmetric n-user cases.

A. Per-user and Aggregate Throughput: Two-user Case

The direct throughput to the destination for the i-th user, T D,i , is given by T D,i = q 0 P (Q > 0) q i (1 -q j )P d i/0,i + q j P d i/0,i,j + [1 -q 0 P (Q > 0)] q i (1 -q j )P d i/i + q j P d i/i,j . (

When the relay queue is stable, the contributed throughput to user i, T R,i , is the arrival rate from user i to the relay queue. Note that a packet from user i enters the relay queue when the transmission to the destination is not successful and at the same time the relay is able to decode that packet. The relayed throughput T R,i of user i is given by

T R,i = q 0 P (Q > 0) q i (1 -q j )(1 -P d i/0,i )P 0 i/0,i + q j (1 -P d i/0,i,j )P 0 i/0,i,j + + [1 -q 0 P (Q > 0)] q i (1 -q j )(1 -P d i/i )P 0 i/i + q j (1 -P d i/i,j )P 0 i/i,j . (12)
The throughput T i for the i-th user is given by

T i = T D,i + T R,i . (13)
In the above equations, the queue is assumed to be stable, hence the arrival rate from each user to the queue is a contribution to the overall throughput. The aggregate throughput is T aggr = T 1 + T 2 . Notice that the per-user throughput is independent of q 0 as long as it is in the stability region. This is due to the fact that the product q 0 P (Q > 0) is constant (does not depend on q 0 ). The proof is straightforward and thus is omitted.

B. Per-user and Aggregate Throughput: Symmetric n-user Case

In this subsection, we provide expressions for the direct and the relayed per-user and aggregate throughput. The notation used in Section III-B applies here as well. Furthermore, the per-user throughput is denoted by T , the direct throughput to the destination by T D , and the relayed throughput by T R .

The direct throughput T D is given by

T D = q 0 P (Q > 0) n-1 k=0 n -1 k q k+1 (1 -q) n-1-k P d,k+1,1 + + [1 -q 0 P (Q > 0)] n-1 k=0 n -1 k q k+1 (1 -q) n-1-k P d,k+1,0 . (14)
The throughput contributed by the relay (when the queue at the relay is stable), T R , is given by

T R = q 0 P (Q > 0) n-1 k=0 n -1 k q k+1 (1 -q) n-1-k (1 -P d,k+1,1 )P 0,k+1,1 + + [1 -q 0 P (Q > 0)] n-1 k=0 n -1 k q k+1 (1 -q) n-1-k (1 -P d,k+1,0 ) P 0,k+1,0 . (15)
The per-user throughput T for the cooperative relay network when the relay queue is stable is given by

T = T D + T R . ( 16
)
The aggregate throughput is T aggr = nT . Remark 1: When the queue is unstable, the aggregate throughput is the summation of the direct throughput among the users and the destination plus the service rate of the relay. However, when the queue is unstable, the queue size increases to infinity, therefore there is no guarantee for finite queueing delay.

V. DELAY ANALYSIS

In Section III, we studied the performance of the relay queue in terms of the probability of empty queue and the average queue length. That section was an intermediate step for our main goal, which is to study the impact of the relay node in the network in terms of throughput and the delay. In the previous section, we obtained the per-user and the aggregate throughput for a relay network with stable relay queue and commented on the case of unstable relay queue. In this section, we analyze an important network performance measure, the delay, and derive analytical expressions for the average delay required to deliver a packet from the source to the destination.

Theorem 5.1: The average delay for a packet received at the destination when it is in the head of the user queue is given by

D i = 1 + T R,i Q λ + 1 µ T i , (17)
where T R,i and T i is the i-th user relayed and per-user throughput, respectively. λ and µ is the average arrival and service rate of the relay, respectively, and Q is the average queue length of the relay. Proof: See Appendix C. The expressions for T R,i and T i are given in Section IV. The expressions for λ, µ, Q are summarized in Theorem 3.1 and 3.2 for the two-user and the symmetric n-user case, respectively.

Note that the term Q λ in ( 17) is the queueing delay, which is the time a packet spends in queue, the time the packet is assigned to the queue for transmission and the time it starts being transmitted. In the meantime, the packet waits while other packets in the queue are transmitted.

Remark 2: When the relay queue is unstable, the average queue length can be arbitrarily large, thus the average queueing delay tends to infinity. In [START_REF] Cover | Elements of Information Theory 2nd Edition[END_REF], when the queue is unstable, then the average delay also tends to infinity. In the case of unstable queues, flow control policies could be applied for packet dropping, however this is beyond the scope of our paper.

VI. NUMERICAL RESULTS

In this section, we provide numerical results to validate the above theoretical performance analysis. For exposition convenience, we consider the case where all users have the same link characteristics and transmission probabilities. The parameters used in the numerical results are as follows: distances are r d = 130, r 0 = 60, and r 0d = 80 in meters, the path loss exponent is α = 4, and the receiver noise power η = 10 -11 . The transmit power for the relay is P tx (0) = 10 mW and for the i-th user is P tx (i) = 1 mW.

A. Per user and Aggregate Throughput

Figs. 2(a) and 4(a) present the per-user throughput versus the number of users in the network for different values of q and g, and for γ = 0.2 and γ = 0.6, respectively. Figs. 2(b) and 4(b) show the aggregate throughput versus the number of users. When γ = 0.2, we observe that for g = 10 -10 and g = 10 -8 (almost perfect self-interference cancelation) the relay queue is unstable for relative small number of users. This is because for small values of γ, it is more likely to have more successful transmissions from the users to the relay, while at the same time the relay can transmit at most one packet per time slot. For γ = 0.6 the queue is never unstable for the selected set of parameters, while for g = 10 -10 and g = 10 -8 , throughput gains are evident as compared to no self-interference cancelation.

In Figs. 3 and5, we plot the percentage of traffic that is being relayed in the network (cf. Section IV) for γ = 0.2 and γ = 0.6 respectively, for the case of a stable queue.

Figs. 6(a) and 8(a) present the per-user throughput versus the number of users in the network for different values of q and g, and for γ = 1.2 and γ = 2.5, respectively. Figs. 6(b) and 8(b) show the aggregate throughput versus the number of users. Finally, Figs. 7 and9 show the percentage of traffic that is being relayed.

Note that when the percentage tends to 1 (or 100%), the contributed throughput by the relay tends to be the total network throughput.

The gains from the relay are more pronounced for large γ, whilst in the case of γ = 0.2 and quasi perfect self-interference cancelation, we tend to have an unstable queue, which affects the delay per packet as we will see in the next subsection.

B. Average Queue Length and Average Delay per Packet

In this subsection, we provide numerical results for two key performance metrics, namely the average relay queue size and the average delay per packet. For γ = 0.2 we included the per-packet delay for the network without the relay for comparison reasons. We observe that in that case the cooperative relay node does not provide any gains for increasing number of users, as the delay for the relay network is larger than the delay without using a relay. For γ = 0.6, the delay for the network without the relay is much larger, e.g., it starts with 50 timeslots for 1 users and goes up to 400 for 50 users. In that case, the use of a relay is beneficial in terms of throughput and per-packet delay. The delay for the network without the relay is significantly large, e.g., for γ = 1.2 the delay is greater than 500 timeslots and for γ = 2.5 the delay is more than 10000 timeslots. In those cases, the existence of the relay offers significant gains not only in terms of throughput but also in the delay performance.

When we have almost perfect self-interference cancelation (except the case of γ = 0.2), we observe significant gains in the delay performance compared to the case of the quasi half-duplex relay (g → 1).

VII. CONCLUSIONS

In this paper, we explored full-duplex communication in which a cooperative node relays packets from a number of sources to a common destination node in a random access network with multi-packet reception capability for both the relay and the destination node. Considering a multiple capture model and the self-interference due to full-duplex relay operation, a transmission is successful if the received SINR is above a certain threshold γ.

We provided analytical expressions for the performance of the relay queue, namely stability conditions, arrival and service rates, and average queue length. We studied the per-user and the aggregate throughput, and showed that the per-user throughput does not depend on the relay transmit probability under stability conditions. We also studied the impact of the self-interference coefficient g on the per-user throughput, the network-wide throughput, and the average per-packet delay. We showed that the self-interference coefficient plays a crucial role when γ is small (and g tends to zero) since it may result in an unstable queue. However, for large γ values and perfect self-interference cancelation, the gains in terms of throughput and delay are more pronounced.

Future extensions of this work may include users with non-saturated queues, i.e. sources with external random arrivals, as well as scenarios where the cooperative relay node has packets on its own and different service priorities.

APPENDIX A PROOF OF THEOREM 3.1

We provide here the proof of Theorem 3.1, which presents the main result for the relay queue characteristics for the two-user case.

Analysis of the average arrival and service rate:

The average service rate µ, is given by ( 3), where q 0 is the transmit probability of the relay given that it has packets in its queue, and q i for i = 0 is the transmit probability for the i-th user. The term P j i/i,k is the success probability of link ij when the transmitting nodes are i and k and can be calculated based on [START_REF] Pappas | Relay-assisted multiple access with multi-packet reception capability and simultaneous transmission and reception[END_REF]. Fig. 5. Percentage of traffic that is being relayed vs. the number of users γ = 0.6, q = 0.1, and q0 = 0.99.

The average arrival rate λ of the queue is given by λ = P (Q = 0) λ 0 + (Q > 0) λ 1 , where λ 0 is the average arrival rate at the relay queue when the queue is empty and λ 1 when it is not. λ 0 = r 0 1 +2r 0 2 , where r 0 i is the probability of receiving i packets given that the queue is empty. Accordingly, λ 1 = r 1 1 + 2r 1 2 , where r 1 i is the probability of receiving i packets when the queue is not empty. The expressions for r 0 i are given by

r 0 1 = q 1 (1 -q 2 )(1 -P d 1/1 )P 0 1/1 + q 2 (1 -q 1 )(1 -P d 2/2 )P 0 2/2 + q 1 q 2 (1 -P d 1/1,2 )P 0 1/1,2 P d 2/1,2 + +q 1 q 2 (1 -P d 2/1,2 )P 0 2/1,2 P d 1/1,2 + q 1 q 2 (1 -P d 1/1,2 )P 0 1/1,2 (1 -P d 2/1,2 )(1 -P 0 2/1,2 )+ +q 1 q 2 (1 -P d 2/1,2 )P 0 2/1,2 (1 -P d 1/1,2 )(1 -P 0 1/1,2 ), (18)
r 0 2 = q 1 q 2 (1 -P d 1/1,2 )(1 -P d 2/1,2 )P 0 1/1,2 P 0 2/1,2 . (19)
In order to compute for instance r 0 1 (i.e., the relay receives one packet), we have to take into account all the possible combinations, which are either the received packet is transmitted by the first or the second user (with all the possible combinations of active/idle users). When the relay queue is not empty, the expressions for the r 1 i are given by

r 1 1 = (1 -q 0 )q 1 (1 -q 2 )(1 -P d 1/1 )P 0 1/1 + q 0 q 1 (1 -q 2 )(1 -P d 1/0,1 )P 0 1/0,1 + (1 -q 0 )q 2 (1 -q 1 )(1 -P d 2/2 )P 0 2/2 + +q 0 q 2 (1 -q 1 )(1 -P d 2/0,2 )P 0 2/0,2 + (1 -q 0 )q 1 q 2 (1 -P d 1/1,2 )P 0 1/1,2 (1 -P d 2/1,2 )(1 -P 0 2/1,2 )+ +q 0 q 1 q 2 (1 -P d 1/0,1,2 )P 0 1/0,1,2 (1 -P d 2/0,1,2 )(1 -P 0 2/0,1,2 ) + (1 -q 0 )q 1 q 2 (1 -P d 1/1,2 )P 0 1/1,2 P d 2/1,2 + +q 0 q 1 q 2 (1 -P d 1/0,1,2 )P 0 1/0,1,2 P d 2/0,1,2 + (1 -q 0 )q 1 q 2 (1 -P d 2/1,2 )P 0 2/1,2 (1 -P d 1/1,2 )(1 -P 0 1/1,2 )+ +q 0 q 1 q 2 (1 -P d 2/0,1,2 )P 0 2/0,1,2 (1 -P d 1/0,1,2 )(1 -P 0 1/0,1,2 ) + (1 -q 0 )q 1 q 2 (1 -P d 2/1,2 )P 0 2/1,2 P d 1/1,2 + +q 0 q 1 q 2 (1 -P d 2/0,1,2 )P 0 2/0,1,2 P d 1/0,1,2 , (20)
r 1 2 = (1 -q 0 )q 1 q 2 (1 -P d 1/1,2 )P 0 1/1,2 (1 -P d 2/1,2 )P 0 2/1,2 + q 0 q 1 q 2 (1 -P d 1/0,1,2 )P 0 1/0,1,2 (1 -P d 2/0,1,2 )P 0 2/0,1,2 . (21)
In order to fully characterize the average arrival rate at the relay, we have to compute the probability the queue is empty. We model the queue at the relay as a discrete time Markov Chain (DTMC), which (b) Aggregate throughput vs. the number of users. Fig. 6. Per-user and aggregate throughput vs. the number of users for γ = 1.2, q = 0.1, and q0 = 0.99. describes the queue evolution and is presented in Fig. 14. Each state is denoted by an integer and represents the queue size at the relay node. The transition matrix of the above DTMC is a lower Hessenberg matrix given by Fig. 7. Percentage of traffic that is being relayed vs. the number of users γ = 1.2, q = 0.1, and q0 = 0.99.

P =            a 0 b 0 0 0 • • • a 1 b 1 b 0 0 • • • a 2 b 2 b 1 b 0 • • • 0 b 3 b 2 b 1 • • • 0 0 b 3 b 2 • • • . . . . . . . . . . . . . . .            . (22)

The elements of the matrix P, are a

0 = 1-p 0 1 -p 0 2 , a 1 = p 0 1 , a 2 = p 0 2 , b 0 = p 1 -1 and b i+1 = p 1 i i = 0, 1, 2, 3.
The quantity p 0 i (p 1 i ) is the probability that the queue size increases by i packets when the queue is empty (not empty). Note that p 0 i = r 0 i because when the queue is empty, the probability of i packets arriving is the same with the probability that the queue size increases by i packets; when the queue is not empty however, this is not true. For example the probability of two packets arriving is not the same with the probability of doubling the queue size; this is because both arrivals and departures can occur at the same time. The expressions for the p j i are given by p 1 -1 = q 0 (1 -q 1 )(1 -q 2 )P d 0/0 + q 0 (1 -q 1 )q 2 P d 0/0,2 P d 2/0,2 + q 0 (1 -q 1 )q 2 P d 0/0,2 (1 -P d 2/0,2 )(1 -P 0 2/0,2 )+ q 0 q 1 (1 -q 2 )P d 0/0,1 P d 1/0,1 + q 0 q 1 (1 -q 2 )P d 0/0,1 (1 -P d 1/0,1 )(1 -P 0 1/0,1 ) + q 0 q 1 q 2 P d 0/0,1,2 P d 1/0,1,2 P d 2/0,1,2 + +q 0 q 1 q 2 P d 0/0,1,2 (1 -P d 1/0,1,2 )(1 -P 0 1/0,1,2 )(1 -P d 2/0,1,2 )(1 -P 0 2/0,1,2 )+ +q 0 q 1 q 2 P d 0/0,1,2 P d 1/0,1,2 (1 -P d 2/0,1,2 )(1 -P 0 2/0,1,2 ) + q 0 q 1 q 2 P d 0/0,1,2 (1

-P d 1/0,1,2 )(1 -P 0 1/0,1,2 )P d 2/0,1,2 , (23)
p 1 0 = 1 -p 1 -1 -p 1 1 -p 1 2 , (24)
p 1 1 = (1 -q 0 )q 1 (1 -q 2 )(1 -P d 1/1 )P 0 1/1 + (1 -q 0 )q 1 q 2 (1 -P d 1/1,2 )P 0 1/1,2 P d 2/1,2 + +(1 -q 0 )q 1 q 2 (1 -P d 1/1,2 )P 0 1/1,2 (1 -P d 2/1,2 )(1 -P 0 2/1,2 ) + (1 -q 0 )(1 -q 1 )q 2 (1 -P d 2/2 )P 0 2/2 + +(1 -q 0 )q 1 q 2 (1 -P d 2/1,2 )P 0 2/1,2 P d 1/1,2 + (1 -q 0 )q 1 q 2 (1 -P d 2/1,2 )P 0 2/1,2 (1 -P d 1/1,2 )(1 -P 0 1/1,2
)+ +q 0 q 1 q 2 P d 0/0,1,2 (1 -P d 1/0,1,2 )P 0 1/0,1,2 (1 -P d 2/0,1,2 )P 0 2/0,1,2 + q 0 q 1 (1 -q 2 )(1 -P d 0/0,1 )(1 -P d 1/0,1 )P 0 1/0,1 + +q 0 q 1 q 2 (1 -P d 0/0,1,2 )(1 -P d 1/0,1,2 )P 0 1/0,1,2 P d 2/0,1,2 + +q 0 q 1 q 2 (1 -P d 0/0,1,2 )(1 -P d 1/0,1,2 )P 0 1/0,1,2 (1 -P d 2/0,1,2 )(1 -P 0 2/0,1,2 )+ +q 0 q 2 (1 -q 1 )(1 -P d 0/0,2 )(1 -P d 2/0,2 )P 0 2/0,2 + q 0 q 1 q 2 (1 -P d 0/0,1,2 )(1 -P d 2/0,1,2 )P 0 2/0,1,2 P d 1/0,1,2 + +q 0 q 1 q 2 (1 -

P d 0/0,1,2 )(1 -P d 2/0,1,2 )P 0 2/0,1,2 (1 -P d 1/0,1,2 )(1 -P 0 1/0,1,2 ), (25)
p 1 2 = (1 -q 0 )q 1 q 2 (1 -P d 1/1,2 )P 0 1/1,2 (1 -P d 2/1,2 )P 0 2/1,2 + +q 0 q 1 q 2 (1 -P d 0/0,1,2 )(1 -P d 1/0,1,2 )P 0 1/0,1,2 (1 -P d 2/0,1,2 )P 0 2/0,1,2 . (26)
Note that p j i and r j i are in general different quantities, however in half-duplex relay systems we have p j i = r j i . The difference equations that govern the evolution of the states are given by

P s = s ⇒ s i = a i s 0 + i+1 j=1 b i-j+1 s j . (27)
We apply the z-transform technique to compute the steady state distribution, i.e., we let Fig. 9. Percentage of traffic that is being relayed vs. the number of users γ = 2.5, q = 0.1 and q0 = 0.99.

A(z) = 2 i=0 a i z -i , B(z) = 3 i=0 b i z -i , S(z) = ∞ i=0 s i z -i . (28)
We know that [START_REF] Gebali | Analysis of Computer and Communication Networks[END_REF]

S(z) = s 0 z -1 A(z) -B(z) z -1 -B(z) . (29)
It is also known that the probability of the queue in the relay is empty is given by [START_REF] Gebali | Analysis of Computer and Communication Networks[END_REF] P

(Q = 0) = 1 + B (1) 1 + B (1) -A (1) . ( 30
)
The expressions of A (1) and B (1) are:

A (z) = 2 i=0 a i z -i = - 2 i=1 ia i z -(i+1) ⇒ A (1) = - 2 i=1 ia i ⇒ A (1) = - 2 i=1 ip 0 i = -λ 0 , (31)
B (z) = 3 i=0 b i z -i = - 3 i=0 ib i z -(i+1) ⇒ B (1) = - 3 i=0 ib i = -b 1 -2b 2 -3b 3 = -1 + p 1 -1 -p 1 1 -2p 1 2 , (32)
Then, the probability of the queue in the relay is empty is given by (4). Therefore, the average arrival rate λ is given by [START_REF] Sadek | Cognitive multiple access via cooperation: Protocol design and performance analysis[END_REF].

Average Queue Length: The average queue length is known to be Q = -S (1), where S (1) =

s 0 K (1)
L (1) [START_REF] Gebali | Analysis of Computer and Communication Networks[END_REF]. The expressions for K(z) and L(z) are given by Then K (1) and (1) are given by

K(z) = -z -2 A(z) + z -1 A (z) -B (z) z -1 -B(z) -z -1 A(z) -B(z) -z -2 -B (z) , (33)
L(z) = z -1 -B(z) 2 . (34)
K (1) = 2A(1) -2A (1) + A (1) -B (1) -1 -B (1) -2 -B (1) -A(1) + A (1) -B (1) , (35)
L (z) = 2 z -1 -B(z) -z -2 -B (z) ⇒ L (1) = 2 -1 -B (1) 2 . ( 36
)
The values of A (1) and B (1) are:

A (z) = - 2 i=1 ia i z -(i+1) = 2 i=1 i(i + 1)a i z -(i+2) ⇒ A (1) = 2p 0 1 + 6p 0 2 , (37)
B (z) = - 3 i=1 ib i z -(i+1) = 3 i=1 i(i + 1)b i z -(i+2) ⇒ B (1) = 2 -2p 1 -1 + 4p 1 1 + 10p 1 2 . ( 38
)
The average queue length is given by [START_REF] Rong | Protocol-level cooperation in wireless networks: Stable throughput and delay analysis[END_REF].

Condition for the stability of the queue: An important tool to determine stability is Loyne's criterion [START_REF] Loynes | The stability of a queue with non-independent inter-arrival and service times[END_REF], which states that if the arrival and service processes of a queue are jointly strictly stationary and ergodic, the queue is stable if and only if the average arrival rate is strictly less than the average service rate. If the queue is stable, the departure rate (throughput) is equal to the arrival rate, i.e., λ 1 < µ ⇔ r 1 1 +2r 1 2 < µ where r 1 1 = (1 -q 0 )A 1 + q 0 B 1 , r 1 2 = (1 -q 0 )A 2 + q 0 B 2 and µ = q 0 A. (b) Per-packet delay vs. the number of users Fig. 13. Average queue length and average per-packet delay vs. the number of users for γ = 2.5, q = 0.1, and q0 = 0.99

A = (1 -q 1 )(1 -q 2 )P d 0/0 + q 1 (1 -q 2 )P d 0/0,1 + q 2 (1 -q 1 )P d 0/0,2 + q 1 q 2 P d 0/0,1,2 .
Then the values of q 0 for which the queue is stable are given by q 0min < q 0 < 1, where

q 0min = A 1 + 2A 2 A + A 1 + 2A 2 -B 1 -2B 2 . ( 39
)
APPENDIX B PROOF OF THEOREM 3.2 In this appendix, we provide the proof of Theorem 3.2, which presents the relay's queue characteristics for the symmetric n-user case. Computation of the average arrival and service rate: The service rate is given by [START_REF] Rong | Cooperation above the physical layer: The case of a simple network[END_REF]. The average arrival rate λ of the queue is λ = P (Q = 0) λ 0 + P (Q > 0) λ 1 , with λ 0 = n k=1 kr 0 k , where the r 0 k is the probability that the relay received k packets when the queue is empty, given by

r 0 k = n i=k n i i k q i (1 -q) n-i P k 0,i,0 (1 -P d,i,0 ) k [1 -P 0,i,0 (1 -P d,i,0 )] i-k , 1 ≤ k ≤ n. (40)
λ 1 = n k=1 kr 1 k , where the r 1 k is the probability that the relay received k packets when the queue is not empty and is given by r 1 k = (1 -q 0 ) n i=k n i i k q i (1 -q) n-i P k 0,i,0 (1 -P d,i,0 ) k [1 -P 0,i,0 (1 -P d,i,0 )] i-k + +q 0 n i=k n i i k q i (1 -q) n-i P k 0,i,1 (1 -P d,i,1 ) k [1 -P 0,i,1 (1 -P d,i,1 )] i-k , 1 ≤ k ≤ n.

(41)

The elements of the transition matrix are given by a k = p 0 k , b 0 = p 1 -1 , b 1 = p 1 0 and b k+1 = p 1 k ∀k > 0 where

p 0 k = n i=k n i i k q i (1 -q) n-i P k 0,i,0 (1 -P d,i,0 ) k [1 -P 0,i,0 (1 -P d,i,0 )] i-k , 1 ≤ k ≤ n, (42)
p 1 -1 = q 0 n k=0 n k q k (1 -q) n-k P 0d,k [1 -P 0,k,1 (1 -P d,k,1 )] k , (43)
p 1 k = (1 -q 0 ) n i=k n i i k q i (1 -q) n-i P k 0,i,0 (1 -P d,i,0 ) k [1 -P 0,i,0 (1 -P d,i,0 )] i-k + +q 0 n i=k n i i k q i (1 -q) n-i (1 -P 0d,i )P k 0,i,1 (1 -P d,i,1 ) k [1 -P 0,i,1 (1 -P d,i,1 )] i-k + +q 0 n i=k+1 n i i k + 1 q i (1 -q) n-i P 0d,i P k+1 0,i,1 (1 -P d,i,1 ) k+1 [1 -P 0,i,1 (1 -P d,i,1 )] i-k-1 , (44)

p 1 0 = 1 -p 1 -1 - n i=1 p 1 i . (45)
The probability that the queue in the relay is empty is given by [START_REF] Szpankowski | Stability conditions for some distributed systems: Buffered random access systems[END_REF], where the expressions for A (1) and B (1) are

A (z) = n i=0 a i z -i = - n i=1 ia i z -(i+1) ⇒ A (1) = - n i=1 ia i ⇒ A (1) = - n i=1 ip 0 i = -λ 0 , (46)
B (z) = n+1 i=0 b i z -i = - n+1 i=i ib i z -(i+1) ⇒ B (1) = - n+1 i=i ib i = -b 1 - n+1 i=2 ib i = -1 + p 1 -1 - n i=1 ip 1 i . (47)
Then the probability that the queue in the relay is empty is given by [START_REF] Simeone | Stable throughput of cognitive radios with and without relaying capability[END_REF].

Average Queue Length: As we showed in Appendix A, the average queue length is given by Q = -S (1), where S (1) = s 0

K (1)
L (1) . The expressions for K (1) and L (1) are given by ( 35) and (36). The expressions for A (1) and B (1) are

A (z) = - n i=1 ia i z -(i+1) = n i=1 i(i + 1)a i z -(i+2) ⇒ A (1) = n i=1 i(i + 1)a i = n i=1 i(i + 1)p 0 i , (48)
B (z) = - n+1 i=i ib i z -(i+1) = n+1 i=1 i(i + 1)b i z -(i+2) ⇒ B (1) = n+1 i=1 i(i + 1)b i = 2 -2p 1 -1 + n i=1
i(i + 3)p 1 i . (49) Following the same methodology as in Appendix A, we obtain that the average queue length given by [START_REF] Pappas | Wireless network-level partial relay cooperation[END_REF].

Condition for the stability of the queue: As in Appendix A, the queue is stable if λ 1 < µ ⇔ n k=1 kr 1 k < µ, where r 1 k = (1 -q 0 )A k + q 0 B k and µ = q 0 A. The expressions for A, A k , B k are :

A k = n i=k n i i k q i
(1 -q) n-i P k 0,i,0 (1 -P d,i,0 ) k [1 -P 0,i,0 (1 -P d,i,0 )] i-k , (50)

B k = n i=k n i i k q i (1 -q) n-i P k 0,i,1 (1 -P d,i,1 ) k [1 -P 0,i,1 (1 -P d,i,1 )] i-k , (51)
A = n k=0 n k q k (1 -q) n-k P 0d,k . (52)
The values of q 0 for which the queue is stable are given by q 0min < q 0 < 1, where

q 0min =

2 Fig. 1 .

 21 Fig.1. The network model for the two-user case: users have saturated queues and the relay only forwards the packets received from both users, which failed to reach the destination.

  Per-user throughput vs. the number of users.

  Aggregate throughput vs. the number of users.

Fig. 2 .

 2 Fig.2. Per-user and aggregate throughput vs. the number of users for γ = 0.2, q = 0.1 and q0 = 0.95.

Figs. 10

 10 Figs. 10(a) and 11(a) present the average queue length of the relay for γ = 0.2 and γ = 0.6. The average queue length is among the factors that affect the average delay per packet as presented in (17) of Theorem 5.1. Figs. 10(b) and 11(b) illustrate the average delay per packet for γ = 0.2 and γ = 0.6.For γ = 0.2 we included the per-packet delay for the network without the relay for comparison reasons. We observe that in that case the cooperative relay node does not provide any gains for increasing number of users, as the delay for the relay network is larger than the delay without using a relay. For γ = 0.6, the delay for the network without the relay is much larger, e.g., it starts with 50 timeslots for 1 users and goes up to 400 for 50 users. In that case, the use of a relay is beneficial in terms of throughput and per-packet delay.

Fig. 3 .

 3 Fig.3. Percentage of traffic that is being relayed vs. the number of users γ = 0.2, q = 0.1, and q0 = 0.95.

Figs. 12

 12 Figs. 12(a) and13(a) show the average queue length for γ = 1.2 and γ = 2.5 respectively. In Figs. 12(b) and 13(b) and 13(b), we illustrate the average delay per packet.The delay for the network without the relay is significantly large, e.g., for γ = 1.2 the delay is greater than 500 timeslots and for γ = 2.5 the delay is more than 10000 timeslots. In those cases, the existence of the relay offers significant gains not only in terms of throughput but also in the delay performance.When we have almost perfect self-interference cancelation (except the case of γ = 0.2), we observe significant gains in the delay performance compared to the case of the quasi half-duplex relay (g → 1).

  Per-user throughput vs. the number of users. Aggregate throughput vs. the number of users.

Fig. 4 .

 4 Fig.4. Per-user and aggregate throughput vs. the number of users for γ = 0.6, q = 0.1, and q0 = 0.99.

  Per-user throughput vs. the number of users.

  Per-user throughput vs. the number of users.

  Aggregate throughput vs. the number of users.

Fig. 8 .

 8 Fig.8. Per-user and aggregate throughput vs. the number of users for γ = 2.5, q = 0.1, and q0 = 0.99.

Fig. 10 .

 10 Fig.10. Average queue length and average per-packet delay vs. the number of users for γ = 0.2, q = 0.1, and q0 = 0.95

Fig. 11 .

 11 Fig.11. Average queue length and average per-packet delay vs. the number of users for γ = 0.6, q = 0.1, and q0 = 0.99

  Average queue length vs. the number of users

Fig. 14 .

 14 Fig. 14. Markov Chain model for the two-user case.

This work was presented in part in This work was supported in part by MURI grant W911NF-08-1-0238, NSF grant CCF-0728966, and ONR grant N000141110127.

The expressions for A, A i , B i are given by

APPENDIX C PROOF OF THEOREM 5.1

We first present the analysis for the average delay D i required to deliver a packet from source i to the destination. That delay is the summation of the transmission delay from the source (to either the destination directly or the relay node), the queueing delay at the relay node, and the transmission delay from the relay to the destination.

When a packet is transmitted from the i-th source, there is a probability that this packet reaches the destination directly, which is T D,i . In the case that the transmission to the destination is not successful but is successful to the relay, the packet enters the relay queue, this is with probability T R,i . The total time that the packet entering the relay queue reaches the destination is denoted by D Q . If the transmission from the source to the destination is unsuccessful to both destination and relay nodes, then it remains at the source for future retransmission (with probability 1 -T D,i -T R,i ).

The average delay D i is given by

, which after some simplifications results in

The expressions for T R,i , T D,i , and T i , are given in Section IV. When the packet from source i that enters the queue waits, while other packets in the queue are transmitted, this waiting time is the queue delay and is denoted by D Q . When the packet that waits at the queue reaches the head of the queue, then it is transmitted from the relay with a probability (due to the random access assumption), the transmission delay from the relay to the destination is 1 µ , where µ is the service rate. The total delay in the relay node is denoted by D R . The expression for D R is

From Little's law, we obtain that D Q = Q λ , where Q is the average queue length for the relay and λ is the average arrival rate. The expressions for Q and λ are presented in Section III. After substituting (55) into (54), we obtain (17) in Theorem 5.1. Note that in our study we do not take into account the processing and the propagation delay.