---
abstract: 'In this paper we consider a simple cooperative network consisting of a source, a destination and a cluster of decode-and-forward half-duplex relays. At each time-slot, the source and (possibly) one of the relays transmit a packet to another relay and the destination, respectively, resulting in inter-relay interference (IRI). In this work, with the aid of buffers at the relays, we mitigate the detrimental effect of IRI through interference cancellation. More specifically, we propose the min-power scheme that minimizes the total energy expenditure per time slot under an IRI cancellation scheme. Apart from minimizing the energy expenditure, the min-power selection scheme, also provides better throughput and lower outage probability than existing works in the literature. It is the first time that interference cancellation is combined with buffer-aided relays and power adaptation to mitigate the IRI and minimize the energy expenditure. The new relay selection policy is analyzed in terms of outage probability and diversity, by modeling the evolution of the relay buffers as a Markov Chain (MC). We construct the state transition matrix of the MC, and hence obtain the steady state with which we can characterize the outage probability. The proposed scheme outperforms relevant state-of-the-art relay selection schemes in terms of throughput, diversity and energy efficiency, as demonstrated via examples.'
author:
- |
    Nikolaos Nomikos,  Themistoklis Charalambous,  Ioannis Krikidis, \
    Dimitrios Skoutas,  Demosthenes Vouyioukas, \
    and Mikael Johansson,  [^1] [^2] [^3]
title: 'A Buffer-aided Successive Opportunistic Relay Selection Scheme with Power Adaptation and Inter-Relay Interference Cancellation for Cooperative Diversity Systems'
---

Introduction
============

Cooperative relaying is an efficient technique to combat fading and path-loss effects in wireless systems. It enables multiple nodes to create virtual multiple-input multiple-output (MIMO) configurations in order to provide spatial transmit and/or receive diversity to single-antenna destinations [@LAN]. Traditional cooperative systems are characterized by the half-duplex constraint that relay nodes cannot receive and transmit data simultaneously, a fact that results to bandwidth loss. In order to overcome this bandwidth limitation, several techniques have been proposed in the literature [@DIN]. Among them, the successive relaying scheme in [@FAN] incorporates multiple relay nodes and proposes a transmission overlap (source-relay, relay-destination) in order to mimic an ideal full-duplex transmission. However, this scheme refers to scenarios with a long distance between the relays and thus inter-relay interference is not considered. An extension of this work is discussed in [@chao_ISIT], where the authors consider that IRI is strong (co-located or clustered relays) and can always be decoded at the affected nodes; this decoded IRI is exploited in a superposition coding scheme that significantly improves the diversity-multiplexing tradeoff (DMT) performance of the system. On the other hand, relay selection has been introduced as a promising practical solution that achieves full diversity by keeping the implementation complexity low. In earlier works in which relays were assumed to lack data buffers, relay selection was mainly based on the max-min criterion and its variations (see, for example, [@BLE; @KAR; @KRI_minmax; @BLE1] and references therein). As a result, based on either proactive or reactive criteria, the relay that received the source signal is the same with the one that is subsequently forwarding the signal towards the destination.

In the adoption of buffer-aided relays, this coupling is broken as different relays could be selected for transmission and reception. Buffering at the relay nodes is a promising solution for cooperative networks and motivates the investigation of new protocols and transmission schemes. Ikhlef *et al.* [@IKH2] propose a novel criterion based on the $\max-\max$ Relay Selection (MMRS), in which the relay with the best Source-Relay (SR) link is selected for reception and the relay with the best Relay-Destination (RD) link is selected for transmission. The MMRS implementation with buffers of finite size is subsequently also discussed. Another work that adopts MMRS is [@IKH3] which aims to recover the half-duplex loss by adopting successive transmissions. As the proposed topology aims to mimic full-duplex relaying, different relays are selected in the same time slot. However, relays are considered isolated and the effect of inter-relay interference is ignored, while relay buffers are never considered to be full or empty. Also, outage performance is examined for a fixed rate and the achieved capacity for adaptive rate. Krikidis *et al.* [@KRICHAR] proposed the $\maxlink$ protocol, which allows all the SR and RD links to enter the competition for the best link through which a signal will be transmitted, thus providing additional freedom in the scheduled transmissions at each time slot. Adaptive link selection, but for a single relay setup, is proposed by Zlatanov *et al.* in [@ZLAadapt]. The performance potentials of the buffer-aided relaying concept are further investigated in [@ZLA2], where the authors show that half-duplex relaying with storage capabilities outperforms ideal full-duplex relaying. Although most of the studies refer to one-way relaying, the work in [@LIU] studies the employment of buffers in a two-way relay network and investigates an opportunistic scheduling that maximizes the system sum-rate while ensuring buffer stability.

In the majority of the aforementioned works the main target is outage probability reduction or throughput improvement. Another characteristic that is of utmost importance in wireless cooperative networks is energy-efficiency. The proposed algorithm in [@NOMspringer] selects the end-to-end paths based on their achievable capacities and uses hierarchical and adaptive modulation. In this way the power of the source and the transmitting relay are adjusted according to the level required for successful reception. In various works (see, e.g., [@FENG; @ZHOU; @CHEN; @SHENG] and references therein) relays are assumed to be battery operated. Due to this practical assumption, the proposed algorithms select the best relays according to two factors. First, the selected relay will spend the minimum amount of energy that is required to surpass the outage threshold of the network. Second, by considering the remaining energy of each node, relays that were selected often will be protected in order to extend their operation and increase the network lifetime. A variation of this energy-efficiency metric is provided in [@AMIN], where circuit-energy consumption is considered and dynamic time allocation is implemented. Also in [@MOUS], by modeling the residual energy of each relay as an energy state, the transition probabilities among states are calculated and an expression of the average network lifetime is obtained in a variable gain amplify-and-forward relay network. Optimal energy allocation techniques are presented in [@IKKI], where the effects of co-channel interference at the relays and the destination are studied. Closed-form expression for the outage probability is derived and in addition, under different global and individual energy constraints, resource allocation algorithms are provided in a multi-relay network. Finally, in [@CHIEH], a multi-user network is investigated aiming to improve the energy efficiency per user, so that relays and subcarriers are selected and allocated accordingly for each user.

This work proposes a buffer-aided successive opportunistic relaying protocol with IRI cancellation. Through the successive nature of this protocol, we aim to recover the half-duplex constraint of cooperative relaying. In contrast to other works in the literature, we consider the arising IRI and with the aid of buffers we mitigate the detrimental effect of IRI through interference cancellation, if feasible. More specifically, we propose the $\minpow$ relay selection policy that acts in conjunction with interference cancellation and adjusts the power levels required accordingly to support the end-to-end communication. The $\minpow$ relay selection policy in terms of outage probability and diversity, is analyzed by modeling the evolution of the relay buffers as a MC. The construction of the state transition matrix and the related steady state of the MC are studied; then, the derivation of the outage probability is presented. The contribution of this work is twofold.

-   Buffer-aided relays and interference cancellation are combined for the first time, thus decoupling the necessity of the receiving relay to transmit in the next time slot, even if the channel is in outage. Hence, an extra degree of freedom is obtained for choosing which relay to transmit, so that IRI cancellation is also achieved, if it is feasible. Also, the current channel state is the deciding factor in choosing a relay rather than the prediction of the next channel state.

-   Power adjustment is also included in our scheme. In this way, the total energy expenditure in the network is minimized, as well as the inter-relay interference, thus reducing the outage probability of the network.

The $\minpow$ relay selection policy outperforms the current state-of-the-art schemes, with which it is compared. The outage, throughput and energy efficiency performance metrics considered are uniformly improved.

The structure of this paper is as follows. In Section \[sec:model\], we present the system model. Section \[policies\] reviews the most relevant relay selection schemes and Section \[sec:minpow\] introduces the $\minpow$ relay selection policy proposed herein. Then, a model of this communication scheme and an outage probability analysis is performed in Section \[sec:outage\], while illustrative examples and numerical results are provided in Sections \[sec:examples\] and \[sec:numerical\], respectively. Finally, conclusions are discussed in Section \[sec:conclusions\].

System model {#sec:model}
============

We assume a simple cooperative network consisting of one source $S$, one destination $D$ and a cluster $\mathcal{C}$ with $K$ Decode-and-Forward (DF) relays $R_k \in \mathcal{C}$ ($1 \leq k\leq K$). All nodes are characterized by the half-duplex constraint and therefore they cannot transmit and receive simultaneously. A direct link between the source and the destination does not exist and communication can be established only via relays [@BLE]. Each relay $R_k$ holds a buffer (data queue) $Q_k$ of capacity $L$ (number of data elements) where it can store source data that has been decoded at the relay and can be forwarded to the destination. The parameter $l_k \in \mathbb{Z}_{+}$, $l_k \in[0, L]$ denotes the number of data elements that are stored in buffer $Q_k$; at the beginning, each relay buffer is empty (i.e., $l_k =0$ for all $k$) We denote by $\mathcal{T}$ all the relays for which their buffer is not empty, i.e., $\mathcal{T} = \{R_k: l_k>0 \}$, $\mathcal{T} \subseteq \mathcal{C}$.

Time is considered to be slotted and at each time-slot the source $S$ and (possibly) one of the relays $R_k$ transmit with power $P_S$ and $P_{R_k}$, respectively. The source node is assumed to be saturated (it has always data to transmit) and the information rate is equal to $r_0$ bits per channel use (BPCU). The retransmission process is based on an Acknowledgment/Negative-Acknowledgment (ACK/NACK) mechanism, in which short-length error-free packets are broadcasted by the receivers (either a relay $R_k$ or the destination $D$) over a separate narrow-band channel in order to inform the network of that packet’s reception status.

All wireless links exhibit fading and Additive White Gaussian Noise (AWGN). The fading is assumed to be stationary, with frequency non-selective Rayleigh block fading. This means that the fading coefficients $h_{ij}$ (for the $i\rightarrow j$ link) remain constant during one slot, but change independently from one slot to another according to a circularly symmetric complex Gaussian distribution with zero mean and unit variance. The channel gains are $g_{ij} = |h_{ij}|^2$ and exponentially distributed, taking values in the range $(0,1]$. The power level chosen by the transmitter $i$ is denoted by $P_{i}$. $n_{i}$ denotes the variance of thermal noise at the receiver $i$, which is assumed to be AWGN.

Since we implement successive relaying, we (may) have concurrent transmissions by the source and one relay taking place at the same time slot. This results in IRI and the source has to consider the interference power that the candidate relay for reception will receive by the transmitting relay.

![The system model: Source $S$ communicates with Destination $D$ via a cluster of relays $R_k \in \mathcal{C}$, $k\in[1,K]$.[]{data-label="overflow"}](Figures/relay_net){width="0.45\columnwidth"}

It is worth noting that our focus is to investigate the performance of a new buffer-aided successive opportunistic relay selection scheme under a global Channel State Information (CSI) assumption and hence, the implementation issues are beyond the scope of this work. Note, however, that conventional centralized/distributed half-duplex relay selection approaches can be applied for the implementation of the proposed scheme (e.g., [@BLE1; @NOS; @SHAH]).

The interference power at the $k$-[th]{} receiver, $I_{k}$, in its general case, includes the interference from all the transmitters (belonging in a set $\mathcal{S}$) in the network apart from the intended transmitter $i$ and the thermal noise, and is given by $$\begin{aligned}
\label{interference}
I_{k}=\sum_{j\neq i, j \in \mathcal{S}}{g_{jk}P_{j} + n_{k}}.\end{aligned}$$ Therefore, the Signal-to-Interference-and-Noise Ratio (SINR) at the receiver $k$ is given by $$\begin{aligned}
\label{SINR1}
\Gamma_{k}=\frac{g_{ik}P_{i}}{\sum_{j\neq i, j \in \mathcal{S}}{g_{jk}P_{j} + n_{k}}}\ .\end{aligned}$$ The Quality of Service (QoS) is measured in terms of SINR. Hence, independently of nodal distribution and traffic pattern, a transmission from transmitter to its corresponding receiver is successful (error-free) if the SINR of the receiver is greater or equal to the *capture ratio* $\gamma_0$. Therefore, we require that $$\begin{aligned}
\label{SINR_geq}
\frac{g_{ik}P_{i}}{\sum_{j\neq i, j \in \mathcal{S}}{g_{jk}P_{j} + n_{k}}} \geq \gamma_0.\end{aligned}$$ The value of $\gamma_0$ depends on the modulation and coding characteristics of the radio. Due to battery limitations, we assume that each transmitting node $i$ (source and relays) has a maximum power $P_{i}^{\max}$.

Relay selection policies {#policies}
========================

In this Section, we briefly review the main buffer-based relay selection policies used in the literature.

$\max-\min$ relay selection
---------------------------

The $\max-\min$ relay selection policy [@BLE], [@KAR] is considered as the optimal selection scheme for conventional DF relay setups without buffers and is used as our baseline relay selection strategy. The selected relay is the one that provides the “best” (strongest) end-to-end path between the source and the destination. The $\max-\min$ selection policy ensures a full diversity (equal to the number of the relays (e.g. $K$)) and refers to a standard cooperative protocol where communication is performed in two time slots: a) in the first time slot, the source transmits b) in the second time slot, the selected relay forwards the data received by the source towards the destination. The $\max-\min$ relay selection policy can be written as $$\begin{aligned}
R^*=\arg\max_{R_k\in \mathcal{C}} \min \{ g_{S,R_k} , g_{R_k,D}   \}.\end{aligned}$$ where $R^*$ denotes the selected relay. Although the $\max-\min$ selection scheme achieves a diversity equal to $K$, it does not take into account the fact that relays are equipped with buffers and their potential benefits. The selected relay forwards the received data (in case of a successful decoding) immediately in the next time slot to the destination and therefore the ability of the relays to store at least a limited number of data packets is not elaborated.

$\max-\min$ relay selection in successive relaying
--------------------------------------------------

The $\max-\min$ relay selection policy implemented in a successive relaying network takes a different form if the IRI can be canceled at the relays. In[@NOM], a reactive relay selection policy is proposed. More specifically, instead of considering only the [*SR*]{} and [*RD*]{} channel gains, the feasibility of IC is also examined. In this way, with a very simple IC condition the following two cases for relay selection are given.

-   If candidate relay $R_k$ can perform IC then it may be selected to receive from the source based on the following value: $$\begin{aligned}
    R^*=\arg\max_{R_k\in \mathcal{C}} \min \{ g_{S,R_k} , g_{R_k,D}   \}.\end{aligned}$$

-   On the other hand, if $R_k$ cannot perform IC then it can be selected after competing with the rest of the relays as below: $$\begin{aligned}
    R^*=\arg\max_{R_k\in \mathcal{C}} \min \left\{ \frac{g_{S,R_k}} {g_{R_t,R_k}} , g_{R_k,D}   \right\}.\end{aligned}$$

It is obvious that by having two simultaneous transmissions by the source and the transmitting relay reduces the diversity of the network as $R^*$ can not participate in the selection process due to the half-duplex constraint. On the other hand, if IRI is effectively mitigated, a full-duplex behavior can be achieved and the half-duplex loss is leveraged.

$\max-\max$ relay selection (bound)
-----------------------------------

The $\max-\max$ relay selection [@IKH2] is the first policy that exploits buffering capability at the relay nodes and is used as a reference selection scheme. Given that the relay nodes are equipped with buffers and thus can store the data received from the source, the $\max-\max$ policy splits the relay selection decision in two parts and selects the relay with the best source-relay link for reception and the relay with the best relay-destination link for transmission. The $\max-\max$ selection policy respects the conventional two-slot cooperative transmission where the first slot is dedicated for the source transmission and the second slot for the relaying transmission, but the relay node may not be the same for both phases of the protocol. The $\max-\max$ relay selection policy can be written as $$\begin{aligned}
&R_r^*=\arg\max_{R_k\in \mathcal{C}}\{ g_{S,R_k} \}, \\
&R_t^*=\arg\max_{R_k\in \mathcal{C}}\{ g_{R_k,D} \},\end{aligned}$$ where $R_r^*$ and $R_t^*$ denote the relay selected for the first phase and the second phase of the cooperative protocol, respectively. It has been proven that the $\max-\max$ relay selection policy also ensures full diversity equal to the number of the relays and it provides a significant coding gain in comparison to the conventional $\max-\min$ selection scheme. However, it is worth noting the the above selection strategy assumes that no relay’s buffer can be empty or full at any time and thus all relays have always the option of receiving or transmitting [@IKH2 Sec. III. C]. Therefore, the $\max-\max$ relay selection considered provides the optimal performance that can be achieved by such a scheme, thus yielding the lowest outage bound.

$\maxlink$ relay selection
--------------------------

The previous relay selection schemes are associated with a two-slot cooperative protocol where the schedule for the source and relay transmission is fixed a priori. Here, this limitation is relaxed and each slot is allowed to be allocated dynamically to the source or a relay transmission, according to the instantaneous quality of the links and the status of the relays’ buffers. More specifically, the proposed $\maxlink$ relay selection scheme exploits fully the flexibility offered by the buffers at the relay nodes and at each time selects the strongest link for transmission (source or relay transmission) among the available links. A source-relay link is considered to be available when the corresponding relay node is not full and therefore can receive data from the source, while a relay-destination link is considered to be available when the relay node is not empty and thus can transmit source’s data towards the destination. The proposed scheme compares the quality of the available links and adjust the relay selection decision and the time slot allocation to the strongest link. If a source-relay link is the strongest link, the source transmits and the corresponding relay is selected for reception; on the other hand, if a relay-destination link is the strongest link, the corresponding relay is selected for transmission. The $\maxlink$ relay selection policy can be analytically expressed as follows: $$\begin{aligned}
R^*=\arg\max_{R_k\in \mathcal{C}}\Bigg\{   \bigcup_{R_k\in \mathcal{C}: \Psi(Q_k)\neq L}\{g_{S,R_k} \} \bigcup_{R_k\in \mathcal{C}: \Psi(Q_k)\neq 0}\{g_{R_k,D} \}   \Bigg\},\end{aligned}$$ where $R^*$ denotes the selected relay (either for transmission or reception) and the function $0\leq\Psi(Q_k)\leq L$, gives the number of data elements that are stored in buffer $Q_k$.

$\minpow$ relay selection policy {#sec:minpow}
================================

In this section, we present a novel relay selection policy called $\minpow$. This relay selection scheme is associated with a one-slot cooperative protocol (similar to the $\maxlink$ relay selection policy [@KRICHAR] and the one in [@IKH3] where however, IRI and power minimization are not considered), rather than two-slot protocols (as in [@IKH2]). At each time slot, the source $S$ transmits data to a selected relay (denoted by $R_r \in \mathcal{K}$) with a non-full buffer, and another relay with a non-empty buffer (denoted by $R_t\in\mathcal{T}$, $R_t \neq R_r$) transmits data to the destination $D$.

A packet is successfully transmitted from the transmitting relay $R_t$ to the destination $D$ if the Signal-to-Noise Ratio (SNR), denoted by $\text{SNR}_{R_t D}$, is greater than or equal to the capture ratio $\gamma_0$, i.e., $$\begin{aligned}
\label{eq:SNR_RD}
\frac{g_{R_t D}P_{R_t}}{n_D} \geq  \gamma_0 \; , \quad R_t\in\mathcal{T}, R_t \neq R_r \; .\end{aligned}$$ A packet is successfully transmitted from source $S$ to the receiving relay $R_r$, if the Signal-to-Interference-and-Noise Ratio (SINR) at the receiving relay, denoted by $\text{SINR}_{S R_r}$ is greater than or equal to $\gamma_0$, i.e., $$\begin{aligned}
\label{eq:SNR_SR}
\frac{g_{S R_r}P_{S}}{g_{R_t R_r} P_{R_t} \mathbb{I}(R_t R_r)  +  n_{R_r}} \geq  \gamma_0 \; , \quad R_r\in\mathcal{C}, R_r \neq R_t \; ,\end{aligned}$$ where $ \mathbb{I}(R_t R_r)$ is a factor indicating whether interference cancellation is satisfied and it is described by $$\begin{aligned}
\label{eq:index}
\mathbb{I}(R_t R_r) = 
\begin{cases} 
0 , & \text{if } \displaystyle \frac{g_{R_t R_r} P_{R_t}}{g_{S R_r}P_{S} +  n_{R_r}} \geq  \gamma_0 \; ,   \\
1 , &\text{otherwise.}
\end{cases}\end{aligned}$$

The following proposition states that if the maximum powers $P_{S}^{\max}$ and $P_{R_t}^{\max}$ are large enough (thus not imposing any limitations/constraints), for each pair of relays $R_r$ and $R_t$, then we can always find power levels such that interference cancellation conditions are satisfied.

\[prop:1\] Let $P_{S}^{\max}=\infty$ and $P_{R_t}^{\max}=\infty$. For each pair of relays $R_r$ and $R_t$, there exist $P_{S}$ and $P_{R_t}$ such that $\mathbb{I}(R_t R_r) =0$, $\text{SNR}_{R_t D} \geq \gamma_0$ and $\text{SINR}_{S R_r} \geq \gamma_0$. The minimum power levels $P_{S}^*$ and $P_{R_t}^*$ are achieved when $\text{SNR}_{R_t D} = \text{SINR}_{S R_r} = \gamma_0$, and are given by

\[eq:P\_optimal\] $$\begin{aligned}
P_{S}^* &= \frac{ \gamma_0 n_{R_r}}{g_{S R_r}} \; , \label{eq:P_S_optimal} \\
P_{R_t}^* &=\max \left\{ \frac{\gamma_0 n_D}{g_{R_t D}} , \frac{n_{R_r}\gamma_0 (\gamma_0 + 1)}{g_{R_t R_r}} \right\} \; \label{eq:P_Rt_optimal}.\end{aligned}$$

For IC to take place, according to , we have $$\begin{aligned}
\label{eq:index2}
{g_{R_t R_r} P_{R_t}} \geq \gamma_0({g_{S R_r}P_{S} +  n_{R_r}})\end{aligned}$$ Given that $P_{R_t}$ is chosen such that is fulfilled, then becomes $$\frac{g_{S R_r}P_{S}}{n_{R_r}} \geq  \gamma_0\; ,$$ and since $P_S$ decreases monotonically with $P_{R_t}$ (see equation  for $\mathbb{I}(R_t R_r) =0$), while it requires a minimum value such that equation  is fulfilled, the minimum power of $S$ is given with equality; i.e., $$\begin{aligned}
P_{S}^* = \frac{ \gamma_0 n_{R_r}}{g_{S R_r}} \; .\end{aligned}$$ Substituting into we have ${g_{R_t R_r} P_{R_t}} \geq n_{R_r}\gamma_0 (\gamma_0 + 1)$. Hence, the minimum $P_{R_t}$ is given by $$\begin{aligned}
P_{R_t}^* =\max \left\{ \frac{\gamma_0 n_D}{g_{R_t D}} , \frac{n_{R_r}\gamma_0 (\gamma_0 + 1)}{g_{R_t R_r}} \right\} \; .\end{aligned}$$

Proposition \[prop:1\] provides the minimum power levels of $S$ and $R_t$, provided that their maximum power levels do not impose any constrain and hence the IC conditions are satisfied. In the next proposition, we find the conditions under which IC cannot take place and we find the optimal power levels of $S$ and $R_t$.

\[prop:2\] For each pair of relays $R_r$ and $R_t$, interference cancellation is feasible if and only if $$\begin{aligned}
\label{eq:Pmax_condition}
P_{R_t}^{\max} \geq \gamma_0 \left[ \gamma_0 \left(\frac{\gamma_0 n_D}{g_{R_t D}}   + \frac{n_{R_r}}{g_{R_t R_r}}   \right) + \frac{n_{R_r}}{g_{R_t R_r}}   \right] \; .\end{aligned}$$ When interference cancellation is infeasible, the signal from $R_t$ can be decoded successfully at $D$ if and only if $$\begin{aligned}
\frac{\gamma_0 n_D}{g_{R_t D}}&\leq  P_{R_t}^{\max} \; .\label{subeq:ineq1} \end{aligned}$$ In addition, the signal from $S$ can be decoded successfully at $R_r$ if and only if $$\begin{aligned}
\gamma_0 \left(\frac{g_{R_t R_r}}{g_{S R_r}} P_{R_t}  +  \frac{n_{R_r}}{g_{S R_r}}\right) &\leq P_{S}^{\max} \; . \label{subeq:ineq2}\end{aligned}$$ When , and hold, the minimum power levels $P_{S}^\dagger $ and $P_{R_t}^\dagger $ are achieved when $\text{SNR}_{R_t D} = \text{SINR}_{S R_r} = \gamma_0$, and are given by

\[eq:P\_optimal2\] $$\begin{aligned}
P_{S}^\dagger &= \gamma_0 \left(\frac{g_{R_t R_r}}{g_{S R_r}} P_{R_t}  +  \frac{n_{R_r}}{g_{S R_r}}\right) \; , \label{eq:P_S_optimal2} \\
P_{R_t}^\dagger &=\frac{\gamma_0 n_D}{g_{R_t D}} \; \label{eq:P_Rt_optimal2}.\end{aligned}$$

Interference cancellation cannot take place when the maximum power of $R_t$ is not high enough, such that its signal can be decoded by $R_r$, i.e., $$\begin{aligned}
\label{eq:P_R_t_max}
 \frac{g_{R_t R_r} P_{R_t}^{\max}}{g_{S R_r}P_{S} +  n_{R_r}} <  \gamma_0 \; .\end{aligned}$$ but it should definitely be high enough to be decoded at the destination, i.e., $$\begin{aligned}
\frac{\gamma_0 n_D}{g_{R_t D}}\leq P_{R_t} &\leq  P_{R_t}^{\max} \label{subeq:ineq11}.\end{aligned}$$ Then, $P_S$ should be high enough, so that the transmitting signal can be successfully decoded at $R_r$. Hence, $$\begin{aligned}
\gamma_0 \left(\frac{g_{R_t R_r}}{g_{S R_r}} P_{R_t}  +  \frac{n_{R_r}}{g_{S R_r}}\right) \leq P_{S} &\leq P_{S}^{\max} \label{subeq:ineq21}\end{aligned}$$ Substituting into we have $$\begin{aligned}
 \label{eq:condition}
\gamma_0 \left(\frac{g_{R_t R_r}}{g_{S R_r}} \frac{\gamma_0 n_D}{g_{R_t D}} +  \frac{n_{R_r}}{g_{S R_r}}\right) \leq P_{S} &\leq P_{S}^{\max} \; .\end{aligned}$$ Substituting into we obtain that $$\begin{aligned}
P_{R_t}^{\max} < \gamma_0 \left[ \gamma_0 \left(\frac{\gamma_0 n_D}{g_{R_t D}}   + \frac{n_{R_r}}{g_{R_t R_r}}   \right) + \frac{n_{R_r}}{g_{R_t R_r}}   \right] \; .\end{aligned}$$

Making use of Propositions \[prop:1\] and \[prop:2\], we will now describe the $\minpow$ relay selection algorithm. The algorithm is implemented in the following steps:\
1) First, for each possible pair of relays, we carry an *IC feasibility check*, i.e., we check through if interference cancellation is feasible.\
2) If IC is *feasible*, then

-   assuming IC took place, $P_{R_t}^*$ and $P_{S}^*$ are as given in and , respectively. Note that since the feasibility criterion is satisfied, then $P_{R_t}^* \leq P_{R_t}^{\max}$. Nevertheless, we need to check separately whether $P_{S}^* \leq P_{S}^{\max}$.

-   assuming IC did not take place, $P_{R_t}^\dagger $ and $P_{S}^\dagger$ are as given in and , respectively. $P_{R_t}^\dagger \leq P_{R_t}^{\max}$ is satisfied by the feasibility check, but we need again to check separately whether $P_{S}^\dagger \leq P_{S}^{\max}$.

-   The minimum energy expenditure at a specific time slot for each pair is the minimum sum of the powers for the two cases, i.e., $\min \left\{ P_{S}^*+ P_{R_t}^*, P_{S}^\dagger + P_{R_t}^\dagger \right\}$. Note that if IC can take place, this might require $P_{R_t}^* > P_{R_t}^\dagger$, such that $P_{S}^*+ P_{R_t}^* > P_{S}^\dagger + P_{R_t}^\dagger$.

3\) If IC is *infeasible*, then we use case (ii) only from step 2).\
4) We compare the minimum energy expenditure for all possible relay pairs and we choose the minimum among them.

Note that in the worst case scenario (in which all the queues are neither empty nor full), there will be $K\times (K-1)$ combinations. Hence, the worst case complexity of the problem is $\mathcal{O}(K^2)$.

Model and outage probability analysis {#sec:outage}
=====================================

In this section, the outage probability behavior of the $\minpow$ relay selection scheme follows the theoretical framework of [@KRICHAR], which is also a relay network with finite buffers. The main differentiation compared to [@KRICHAR] is that we have additional ways of transmission through successive relaying; in other words, we have additional links from a certain buffer state to others. This will be more clearly reflected in the illustrative example.

Construction of the state transition matrix of the MC {#sec:outageA}
-----------------------------------------------------

We first formulate the state transition matrix of the Markov Chain (MC), denoted as $\mathbf{A}$, $\mathbf{A}\in \mathbb{R}^{{\left( {L + 1} \right)^K} \times {\left( {L + 1} \right)^K}}$. More specifically, ${{\bf{A}}_{i,j}} = {P}\left( {{s_i} \to {s_j}} \right) = {P}\left( {{X_{t + 1}} = {s_j}|{X_t} = {s_i}} \right)$ are the transition probabilities to move from a state $s_i$ to a state $s_j$. The transition probability depends on the number of relays that are available for cooperation.

As we consider finite buffers, relays that have full buffers cannot compete in the selection of the best relay that will receive the source’s signal. Also, relays with empty buffers are not able to transmit and as a result they are excluded from the best transmitting relay selection. Moreover, when there is no possibility of transmitting successively through two selected relays our system reduces to the $\maxlink$ relay selection scheme. The number of links that are available in this mode is reduced if the relays have full or empty buffers.

Let $N_i$ denote all the possible out-going links from state $s_i$. Among them, $n_i$ links are considered through non-successive (also referred to as *single-link*[^4]) transmissions, while $N_i-n_i$ through successive transmissions. These transmissions endure for one transmission phase. Since the source and one relay will transmit simultaneously, inter-relay interference will arise and the transmission power in each hop will be adjusted, according to Section \[sec:minpow\], depending on whether or not interference cancellation took place. In what follows, we denote with superscript $ns$ the non-successive (single-link) transmissions and with $s$ the successive ones. Since we have i.i.d fading channels, single link transitions can occur with equal probability. On the other hand, due to the inter-relay interference, the successive transitions will have equal probabilities in the high SNR regime as interference cancellation is always feasible there. Thus, the probability of a single link transition from state $s_i$ to a state $s_j$ is equal to: $$\label{eq:single_tr}
p^{\rm ns}_{ij} \buildrel \Delta \over = \frac{1}{n_i}\left[ {1 - {{\left( {1 - \exp \left( { - \frac{{{2^{2{r_0}}} - 1}}{P}} \right)} \right)}^{{D_{{\rm ns}}}}}} \right] \;.$$ On the other hand, single link outage will occur when $$\label{eq:single_out}
{\bar p}^{\rm{ns}}_{ij} \buildrel \Delta \over = 1 - \sum\limits_{k = 1}^{{D_{\rm{ns}}}} {p^{\rm{ns}}_{ij} = \frac{n_i}{N_i}{{\left( {1 - \exp \left( { - \frac{{{2^{2{r_0}}} - 1}}{P}} \right)} \right)}^{{D_{\rm{ns}}}}}} \;,$$ where $P$ is the transmission power, $r_0$ is the end-to-end spectral efficiency and ${D_{ns}}$ is the total number of links that the $K$ relays offer, i.e., ${D_{ns}} = \sum_{k = 1}^K {\Phi \left( {{Q_k}} \right)}$. More specifically, each relay will offer $$\label{eq:link_num}
\Phi \left( {{Q_k}} \right) = \left\{ \begin{array}{l l }
2 & {\rm{ \hspace{1 mm} if \hspace{1 mm} }} 0 < \Psi \left( {{Q_k}} \right) < L;\\
1 & {\rm{ \hspace{1 mm} elsewhere}}{\rm{.}}
\end{array} \right.$$

Furthermore, a successive transition, will be successful with a probability equal to $$\label{eq:succ_tr}
p^{\rm s} _{ij} \buildrel \Delta \over = \frac{1}{N_i - n_i}\left[ {1 - {{\left[ {\left( {1 - \exp \left( { - \frac{{{2^{2{r_0}}} - 1}}{{{P_{s}^*}}}} \right)} \right)\left( {1 - \exp \left( { - \frac{{{2^{2{r_0}}} - 1}}{P_{R_t}^*}} \right)} \right)} \right]}^{{D_{s}}}}} \right] \; ,$$ where $P_{s}^*$ is defined by if IC took place or if IC was not feasible. Similarly, $P_{R_t}^*$ is defined by or . By $D_{s}$ we denote the total number of possible end-to-end successive links as all the possible relay pairs are examined. $D_{s}$ is defined as $$\label{eq:succ_links}
{D_{s}} = \sum\limits_{k \ne l}^K {\Phi \left( {{Q_k}{Q_l}} \right)} \; ,$$ where $\Phi \left( {{Q_k}{Q_l}} \right)$ is equal to $$\begin{aligned}
\label{eq:succ_phi}
\Phi \left( {{Q_k}{Q_l}} \right) &= \prod\limits_{k = 1}^K {\Psi \left( {{Q_k}} \right)} \prod\limits_{l = 1}^K {\Psi \left( {{Q_l}} \right)}= \left\{ \begin{array}{l l}
1 &{\rm{ \hspace{1 mm} if \hspace{1 mm} }}0 < \Psi \left( {{Q_k}} \right) \le L \cap 0 \le \Psi \left( {{Q_l}} \right) < L \; ,\\
0 &{\rm{ \hspace{1 mm} elsewhere} \;.}
\end{array} \right.\end{aligned}$$ Moreover, an outage in the successive transitions will occur when $$\label{eq:succ_out}
{\bar p}^{\rm s}_{ij} \buildrel \Delta \over = 1 - \sum\limits_{k = 1}^{D_{\rm s}} p^{\rm s}_{ij} = \frac{{N_i - n_i}}{N_i}{{\left[ {\left( {1 - \exp \left( { - \frac{{{2^{2{r_0}}} - 1}}{{{P_{S}^*}}}} \right)} \right)\left( {1 - \exp \left( { - \frac{{{2^{2{r_0}}} - 1}}{P_{R_t}^*}} \right)} \right)} \right]}^{D_{\rm s}}}$$

Steady state distribution and outage probability {#steady_st}
------------------------------------------------

Since we have defined the entries of the transition matrix $\mathbf{A}$, the next step is to find the steady state distribution of the MC. In this way, the relationship among the different ways of leaving and reaching specific buffer states will be defined.

\[prop:3\] The state transition matrix $\mathbf{A}$ is Stochastic, Indecomposable[^5] and Aperiodic[^6] (SIA).

In order to prove that $\mathbf{A}$ is SIA, we have to show that it is (i) row stochastic, (ii) indecomposable, and (iii) aperiodic.\
(i) *Row Stochasticity*: For any MC the transition from state $s_i$ to a state $s_j$ for all possible states $s_i$ sums up to $1$, i.e., $$\label{eq:row_stoch}
\sum\limits_{i = 1}^{{{\left( {L + 1} \right)}^K}} {{{\bf{A}}_{i,j}}}  = 1.$$ In the MC that models the buffer states of the relays, if there exists a transition from state $s_i$ to $s_j$ then there exists a transition from $s_j$ to $s_i$. This fact applies to our scheme where transitions due to successive relaying, offer additional links from one state to another and vice versa. However, since the states are not symmetric and the number of links to other states is not the same, the transition probabilities are not the same. Thus, the transition matrix $\mathbf{A}$ is not symmetric. As a result the $\mathbf{A}$ is row stochastic, but not necessarily doubly stochastic.\
(ii) *Indecomposability*: Due to the structure of the problem all the possible states of the considered MC can communicate and hence its state space is a single communicating class; in other words, it is possible to get to any state from any state. Hence, the MC is indecomposable.\
(iii) *Aperiodicity*: Aperiodicity of a MC is easily established due to the fact that the diagonal entries that correspond to original (non-virtual) nodes are nonzero. All links receive nonnegative weights and the diagonals (outage probabilities) are strictly positive. Also, the probability of being at any state after $M$ and $M +1$ transitions is greater than zero; hence, all states are aperiodic and therefore, the MC is aperiodic.

\[lemma:1\] The stationary distribution of the row stochastic matrix [**A**]{.nodecor} of the MC that models the buffer states is given by $\bm{\pi}=(\mathbf{A}-\mathbf{I}+\mathbf{B})^{-1}\bf{b}$, where $\bm{\pi}$ is the stationary distribution, $\bm{b}=(1~1~\ldots~1)^T$ and $\mathbf{B}_{i,j}=1, ~\forall i,j$.

The proof is similar to that of [@KRICHAR Lemma 1, Lemma 2]. It is included in Appendix \[sec:proofs\] for completeness.

Derivation of the outage probability
------------------------------------

Using the steady state of the MC and the fact that an outage event occurs when there is no change in the buffer status, first for successive relaying and then for single link transmissions, the outage probability of the system can be expressed as [@KRICHAR] $$\label{eq:p_out}
{P_{out}} = \sum\limits_{i = 1}^{{{\left( {L + 1} \right)}^k}} {{{\bm{\pi }}_i}{{\bar p}_{ij}} = {\rm{diag}}\left( {\bf{A}} \right){\bm{\pi }}}$$ By constructing the state transition matrix **A** that captures in its diagonal the probabilities where no change in buffer states happened, and the corresponding steady state probabilities, we can easily compute the outage probability of the system.

Illustrative Examples {#sec:examples}
=====================

In the previous section, we have described the theoretical framework for the computation of the outage probability. In the following, we will present two illustrative examples that showcase the behavior of our approach for different parameters. The first example consists of two relays $(K=2)$ with finite buffer size equal to two $(L=2)$, while the second one examines the case of infinite buffers $(L\rightarrow\infty)$ at the relays.

Illustrative example of K=2 relays and L=2 buffer size
------------------------------------------------------

In what follows, we present an illustrative example that showcases the behavior of our approach for different parameters. Since we have a scheme that employs successive transmissions the simplest case is when two relays are available. Assuming that each relay has a buffer size equal to two, we show its state transition diagram in Fig. \[overflow\], with the nine possible states for the buffers of the two relays.

![State diagram of the Markov chain representing the states of the buffers and the transitions between them for a case with $K=2
$ and $L=2$. Compared to the $\maxlink$ scheme in [@KRICHAR], the $\minpow$ model includes extra transition states due to the successive nature of the protocol.[]{data-label="overflow"}](Figures/2x2_v2){width="0.65\columnwidth"}

The steady state of the system for different values of SNR can be found by using the method described in \[steady\_st\] and the corresponding state transition matrix **A** is as follows. $$\begin{aligned}
{\small
\mathbf{A} =  \left(\begin{array}{ccccccccc} 
   \bar{p}_{1} & p_{12} & p_{13} & {0}        & {0}        & {0}        & {0}        & {0}        & {0}  \\
   p_{21} & \bar{p}_{2} & p_{23} & p_{24} & p_{25} & {0}        & {0}        & {0}        & {0}  \\
   p_{31} & p_{32} & \bar{p}_{3} & {0}        & p_{35} & p_{36} & {0}        & {0}        & {0}  \\
   0           & p_{42} & {0}        & \bar{p}_{4} & p_{45} & {0}        & p_{47} & {0}        & {0}  \\
   0           & p_{52} & p_{53} & p_{54} & \bar{p}_{5} & p_{56} & p_{57} & p_{58} & {0}  \\
   0           & {0}        & p_{63} & {0}        & p_{65} & \bar{p}_{6} & {0}        & p_{66} & {0}  \\
   0           & {0}        & {0}        & p_{74} & p_{75} & {0}        & \bar{p}_{7} & p_{78} & p_{79}  \\
   0           & {0}        & {0}        & {0}        & p_{85} & p_{86} & p_{87} & \bar{p}_{8} & p_{89}  \\
   0           & {0}        & {0}        & {0}        & {0}        & {0}        & p_{97} & p_{98} & \bar{p}_{9} 
\end{array} \right) \; .}\end{aligned}$$

   Buffer State   $\bm{\pi}$ ($P=0$dB)   $\bm{\pi}$ ($P=10$dB)   $\bm{\pi}$ ($P=20$dB)   $\bm{\pi}$ ($P=30$dB)
  -------------- ---------------------- ----------------------- ----------------------- -----------------------
      $S_1$            0.0413774               0.0005918               0.0000055                   0
      $S_2$            0.1264042               0.1021872               0.1001714              0.05115971
      $S_3$            0.1263465               0.1021954               0.1001701              0.05115971
      $S_4$            0.1145455               0.1481283               0.1498316              0.19884035
      $S_5$            0.1826525               0.2937944               0.2996428              0.39768046
      $S_6$            0.1145455               0.1481283               0.1498316              0.19884035
      $S_7$            0.1263465               0.1021954               0.1001701              0.05115971
      $S_8$            0.1264042               0.1021872               0.1001714              0.05115971
      $S_9$            0.0413774               0.0005918               0.0000055                   0

  : Buffer states for $K=2$ relays and $L=2$ buffer size

\[K2L2\_pi\]

In Table \[K2L2\_pi\] we observe that when SNR increases, the steady state distribution decreases in buffer states $S_1$ and $S_2$, and eventually it becomes practically zero. That means that for high SNR, the probability of outage is zero. On the other hand, when SNR increases, the steady state distribution in state $S_5$ increases, which dominates the states for large SNRs.

In the numerical results (Section \[sec:numerical\]), we evaluate the theoretical framework for the case of $K=2$, $L=2$ in order to examine its behavior compared to obtained numerical results from simulations.

Example of $L\rightarrow\infty$ buffer size and $P\rightarrow\infty$ transmission power {#sec:examples2}
---------------------------------------------------------------------------------------

The asymptotic analysis yields interesting results due to the nature of the problem. In [@KRICHAR] it was shown that as the buffer size approaches infinity, the states where no full or empty relays exist are dominant[^7].

\[remark:1\] In the proposed scheme, we consider $K(K-1)$ possible relay pairs for transmission and reception in a successive way. When we are in a dominant state, each pair provides one possible transition to another state. Thus, the successive transmissions contribute $K(K-1)$ transitions. Moreover, we have the possibility of single link transmissions. A single link transmission can be either a transmission in a source-relay link or in relay-destination link. As a result, in a dominant state each relay offers 2 possible transitions and in total $K$ relays offer $2K$ transitions. In conclusion, in a dominant state the whole set of transitions is equal to $K(K-1)+2K=K(K+1)$.

From Remark \[remark:1\], the total number of transitions, denoted as $N_{i}$ in Section \[sec:outageA\], is equal to $K(K+1)$ when we are in a dominant state. Among them, single link transitions, denoted as $n_{i}$ in Section \[sec:outageA\], are equal to $2K$ so ${D_{{\rm{ns}}}} = 2K$. At the same time, successive transitions, denoted as $N_{i}-n_{i}$ in Section V.A, are equal to $K(K-1)$ possible ways of leaving the state; thus, ${D_{{\rm{s}}}} = K(K-1)$. Therefore, based on equation , the outage probability becomes $$\begin{aligned}
\label{eq:Pout}
{\bar p}^{\rm ns} = \frac{2K}{K\left( {K + 1} \right)}{\left( {1 - \exp \left( { - \frac{{{2^{2{r_0}}} - 1}}{P}} \right)} \right)^{2K}} \; .\end{aligned}$$

\[lemma:3\] The diversity order[^8] of $\minpow$ is equal to $2K$.

The outage probability of $\minpow$ is bounded by the outage probability of single link transmission, i.e., by considering each possible outage case we have that the outage probability $\mathbb{P}_{\rm out}$, is given by $\mathbb{P}_{\rm out}=\mathbb{P}({\bar p}^{\rm ns}=1|{\bar p}^{\rm s}=1)+\mathbb{P}({\bar p}^{\rm s}=1|{\bar p}^{\rm ns}=1)=\mathbb{P}({\bar p}^{\rm ns}=1|{\bar p}^{\rm s}=1)$, since the probability of having an outage when searching for a successive transmission is larger due to the requirement of simultaneously not having two links in outage. On the contrary, in single link, the same links are examined and if one of them fulfills the threshold for error-free transmission then the outage event is avoided.

The diversity order is derived using its definition and equation , i.e., $$\begin{aligned}
d &= -\lim_{P \rightarrow \infty} \frac{\log \mathbb{P}_{\rm out}(P)}{\log P} 
=-\lim_{P \rightarrow \infty} \frac{\log \frac{2K}{K\left( {K + 1} \right)}{\left( {1 - \exp \left( { - \frac{{{2^{2{r_0}}} - 1}}{P}} \right)} \right)^{2K}}}{\log P}\\
&\stackrel{(a)}{\approx}-\lim_{P \rightarrow \infty} \frac{\log \frac{2K}{K\left( {K + 1} \right)}{\left(\frac{2^{2{r_0}} - 1}{P} \right)^{2K}}}{\log P}=-\lim_{P \rightarrow \infty} \frac{\log  \frac {2K}{K\left(K + 1\right)}+\log\left( \frac{2^{2 r_0} - 1}{P} \right)^{2K}}{\log P} \\
&=-\lim_{P \rightarrow \infty} \frac{2K\log\left( \frac{2^{2 r_0} - 1}{P} \right)}{\log P} 
=-2K\lim_{P \rightarrow \infty} \frac{\log \left(2^{2{r_0}} - 1\right)}{\log P} + 2K\lim_{P \rightarrow \infty}  \frac{\log P}{\log P}
=2K \; .\end{aligned}$$ Note that approximation $(a)$ emerges from the fact that for $x \rightarrow 0$, then $1+e^{-x} \approx x$.

For non-infinite buffer sizes possible gains in outage probability, compared to [@KRICHAR], derive from better interconnection between the buffer states. In this way, the buffer states where relays are full or empty are often avoided and the states where increased diversity is offered, are more usual.

Numerical Results {#sec:numerical}
=================

In line with the previous discussion, we have developed a simulation setup for the $\minpow$ scheme to evaluate its performance with a spectral efficient target $r_0=1$ bps/Hz, in terms of: $1)$outage probability, $2)$average throughput and $3)$power reduction. Min-power is compared to best-relay selection (BRS) [@BLE], successive opportunistic relaying (SOR) [@NOM], hybrid relay selection ($\max-\max$) [@IKH2] and $\maxlink$ selection [@KRICHAR]. In addition, we provide a selection bound corresponding to the case presented in [@IKH3] where inter-relay interference is ignored and additionally all links are always available for selection i.e. buffers are never full or empty. Also, the selection bound scheme is coupled with single link transmissions when successive transmissions fail, in order to provide a fair comparison with $\minpow$.

Outage Probability
------------------

Fig. \[pout\_K2L2\], illustrates the outage probability results. Each scheme employs $K=2$ relays with buffer size $L=2$. The selection policy that offers the worst performance is SOR. The lack of buffers prohibits the combination with a more robust scheme such as $\maxlink$ and IRI degrades the outage performance. Max-min shows better behavior as IRI is not present. Furthermore, $\max-\max$ offers about 1.5 dB improvement due to the use of buffers, over BRS. Even better results are achieved by $\maxlink$ as outage performance is improved by almost 4 dB due to the flexibility in the link selection. As $\maxlink$ is a part of $\minpow$ when successive transmissions are not possible, we observe similar results between these two schemes. For $K=2$ and $L=2$, $\minpow$ exhibits a 0.5 dB gain for high SNR. The increased interconnection between buffer states guarantees that states $S_{1}$ (00) and $S_{9}$ (22) offering the least diversity, are more often avoided compared to $\maxlink$. Also, the theoretical curve of the outage probability matches the simulation results validating the analysis in Section IV.

![Outage probability for increasing transmit SNR for $K=L=2$. As $\maxlink$ is a part of $\minpow$ when successive transmissions are not possible, they exhibit similar behavior. Still, $\minpow$ exhibits a 0.5 dB gain for high SNR due to increased interconnection between buffer states, thus avoiding $S_{1}$ (00) and $S_{9}$ (22) offering the least diversity. Also, the theoretical curve of the outage probability matches the simulation results.[]{data-label="pout_K2L2"}](Figures/Outage/OutageVSSchemes/OutageProbabilityK2L2){width="0.5\columnwidth"}

In Fig. \[pout\_K2Lv\], we depict outage probability performance for increasing transmit SNR and varying $L$. As $L$ increases, the curves become steeper thus indicating the increase in diversity as more links are available for selection. For $L=100$ and $L=\infty$ the outage curves almost match but still retain a gap from the selection bound case. This is logical as inter-relay interference degrades the performance of $\minpow$, while for the selection bound we assumed that the relays are isolated and inter-relay interference is negligible. Still, the $\minpow$ curve follows closely the selection bound especially for high SNR as very strong interference increases the probability of interference cancellation.

![Outage probability for increasing transmit SNR for $K=2$ and varying $L$. For increased $L$, the curves become steeper thus indicating increased diversity as more links are available for selection. For $L = 100$ and $L=\infty$ the outage curves almost match but still retain a gap from the selection bound, as IRI degrades the performance of $\minpow$.[]{data-label="pout_K2Lv"}](Figures/Outage/OutageVSL/OutageK2Lvarious){width="0.5\columnwidth"}

Next, Fig. \[pout\_KvL4\], shows the results for varying $K$ while $L=4$. As we saw in the asymptotic analysis example, diversity increases with a rate twice the number of $K$. Here we have a fixed finite buffer size but still each relay addition obviously improves the achieved diversity of the network. This derives from the fact that the possibility of inter-relay interference cancellation increases with an order equal to $K(K-1)$ as we have more relay pairs to select from. It is interesting to note, whenever $K$ increases to three from two the improvement is bigger than the gain introduced by adding one more relay when $K=3$ as $r_0$ is fulfilled even for low $K$ values.

![Outage probability for increasing transmit SNR for varying $K$ and $L=4$. Each relay addition improves the diversity of the network as we have more relay pairs to select from, thus increasing the chances for IRI cancellation. The improvement when $K$ increases to three from two is larger than the gain introduced by adding one more relay when $K=3$ as $r_0$ is fulfilled even for low $K$ values.[]{data-label="pout_KvL4"}](Figures/Outage/OutageVSK/OutageKvariousL4){width="0.5\columnwidth"}

Average Throughput
------------------

For the second set of comparisons among relay selection schemes, we present in Fig. \[thr\_K2L2\] the average throughput performance, measured in bps/Hz. First, we see that the compared selection policies are divided in two groups. The first one consists of the half-duplex schemes, namely BRS, $\max-\max$ and $\maxlink$. Due to the constant transmission rate, equal to 1 bps/Hz, these schemes can achieve a maximum average throughput of 0.5 bps/Hz. In line with the outage probability performance, $\maxlink$ outperforms BRS and $\max-\max$ and reaches the upper bound nearly 2.5 dB prior to the others. In the second group we have SOR and $\minpow$. These schemes aim to lift the half-duplex constraint and increase the average throughput through successive transmissions. It is observed that the schemes of the second group reach the upper-limit more slowly than those of the first group. This is explained by the fact that in the low SNR regime, single-link transmissions are often performed, thus reducing the throughput by one-half in these cases. Min-power achieves the best performance reaching 1 bps/Hz for high SNR. SOR however, does not reach the upper bound even for high SNR as IRI causes many outages.

![Average throughput for increasing transmit SNR for $K=L=2$. It is observed that $\minpow$ reaches its upper-limit more slowly than the half-duplex schemes. In the low SNR regime, single-link transmissions are often performed, thus reducing the throughput by one-half in these cases.[]{data-label="thr_K2L2"}](Figures/Throughput/ThroughputVSSchemes/Throughput_K2L2only){width="0.5\columnwidth"}

Fig. \[thr\_K2Lv\] illustrates average throughput for $\minpow$ as $L$ and transmission power increase. From the results we see that $\minpow$ for buffer-size above eight, follows the selection bound and their performance gap becomes negligible at about 8 dB. It is important to note that when the SNR is low, interference cancellation does not take place often and the proposed scheme chooses half-duplex transmissions instead of successive ones. This explains the gap between the selection bound and the cases of $L=100, \infty$ in the low SNR regime. Note that in this comparison we have $K=2$ relays and there is no flexibility in pair selection when a successive transmission is performed.

![Average throughput for increasing transmit SNR for $K=2$ and varying $L$. For buffer-size above eight, $\minpow$, follows the selection bound and their gap becomes negligible at about 8 dB. When the SNR is low, IC does not take place often and the proposed scheme chooses half-duplex transmissions instead of successive ones, thus explaining the gap between the selection bound and the cases of $L=100, \infty$[]{data-label="thr_K2Lv"}](Figures/Throughput/ThroughputVSL/ThroughputK2Lvarious){width="0.5\columnwidth"}

The third parameter that we examine is the number of relays in the cluster. Fig. \[thr\_KvL4\] shows the gain in average throughput as both $K$ and the transmission power increase. From the analysis of the $\minpow$ relay selection scheme, for each transmission we check $K(K-1)$ pairs to see whether or not interference cancellation can be performed. As we add more relays, the number of possible relay pairs increases from 2 in the case of $K=2$ to 6 in the case of $K=3$, while for $K=4$ we have 12 possible pairs. As a result, even for low SNR, successive transmissions are more possible for increasing $K$ and throughput tends to reach its maximum value more rapidly.

![Average throughput for increasing transmit SNR for varying $K$ and $L=4$. As more relays are added, the possible relay pairs increase from 2 in the case of $K=2$ to 6 in the case of $K=3$, while for $K=4$ we have 12 possible pairs. So, even for low SNR, successive transmissions are more possible and throughput reaches its maximum value more rapidly.[]{data-label="thr_KvL4"}](Figures/Throughput/ThroughputVSK/ThroughputKvariousL4){width="0.5\columnwidth"}

Power Reduction
---------------

The third metric that we study is the power reduction achieved by $\minpow$. The value on y-axis refers to differential power gain i.e. the power in dB that is saved when the proposed scheme is employed. The reference scheme that is used to calculate the power gain is a buffer-aided relay selection scheme that does not employ power minimization in the selection process and transmits each time with the maximum available power. For example, if the fixed power scheme uses 6 dB to perform a transmission and $\minpow$ reduces this requirement to 2 dB we keep the difference of 4 dB and we calculate the average after the end of all transmissions for this step of maximum power value. As stated in Section \[sec:minpow\], when $\minpow$ relay selection is used, a search for the pair of relays that require the minimum sum of transmission powers starts for a given SNR threshold. Similarly, for the case of single link transmission, the link requiring the minimum power to achieve a successful transmission is selected. We note that when a successive transmission is feasible both the source and a relay transmit, resulting in increased power reduction margin as the most appropriate relay pair is selected. On the contrary, when a single-link transmission occurs, we calculate power reduction by comparing the power used by the transmitting node in the fixed power scheme to the power used by the transmitting node in the selected single-link.

The first parameter that influences power reduction performance is $L$. Fig. \[pow\_K2Lv\], contains the curves for $K=2$ and various buffer sizes. Here the limiting factor is inter-relay interference. We see that for increased values of $L$ greater than 8, differences in power are minor but still, the selection bound is not met. This comes as a consequence of the difficulty to cancel IRI since only two relays are employed in the transmission.

![Power reduction for increasing transmit SNR for varying $L$ and $K=2$. For increased values of $L$ greater than 8, power differences are minor, however the selection bound is not met. As only two relays are employed in the transmission IRI cancellation is difficult.[]{data-label="pow_K2Lv"}](Figures/Power/PowerVSL){width="0.5\columnwidth"}

In order to examine the effect of additional relays, we present corresponding results in Fig. \[pow\_KvL8\]. We see that adding more relays to the cluster, the relay selection alternatives increase, thus leading to improved power minimization. As fixed transmission rate is adopted, a saturation is observed since differences in the required power for successful transmissions are very close after $K=3$ relays.

![Power reduction for increasing transmit SNR for varying $K$ and $L=8$. Since fixed transmission rate is adopted, a saturation is observed as differences in the required power for transmission are very close after $K=3$ relays.[]{data-label="pow_KvL8"}](Figures/Power/PowerVSK){width="0.5\columnwidth"}

Conclusions {#sec:conclusions}
===========

In this paper we proposed an opportunistic relaying protocol that minimizes the total energy expenditure per time slot under an IRI cancellation scheme. By making use of power adaptation and buffer-aided relays, the detrimental effect of IRI through interference cancellation is mitigated. It is the first time that interference cancellation is combined with buffer aided relays to mitigate IRI and on top this is combined with power adaptation for minimizing the energy expenditure; the examples demonstrate the improvements achieved. For the evaluation of the performance of the $\minpow$ relay selection policy, we performed comparisons with other schemes and the results showed that by combining successive transmission and a buffer-aided half-duplex protocol, gains were achieved in both outage and throughput performance. Moreover, we studied the effect of changing the buffer sizes and relay numbers on the outage, throughput and power reduction metrics. When the number of buffers and relays becomes large enough, the gain obtained by our proposed scheme vanishes. This observation suggests the need for additional approaches that will offer new characteristics to $\minpow$, thus improving its potential. A future direction includes the study of network coding schemes for further throughput improvement in this network setup and exploitation of the inter-relay interference by using superposition coding schemes.

Proofs {#sec:proofs}
======

Proof of Lemma \[lemma:1\] {#appendix1}
--------------------------

Since the MC considered is SIA, then there exists a unique solution $\bm{\pi}=(\bm{\pi}_1 ~ \bm{\pi}_2 ~\ldots ~ \bm{\pi}_{(L+1)^K}  )^T$ such that $$\begin{aligned}
\mathbf{A}\bm{\pi}&=\bm{\pi}, \label{Api}  \\ 
\sum_{i=1}^{(L+1)^K} \bm{\pi}_i &=1.  \label{Bb}\end{aligned}$$ The solution can be easily found by solving the set of linear equations. In this case, is written as $$\begin{aligned}
\label{B1}
\mathbf{B}\bm{\pi}=\mathbf{b},\end{aligned}$$ where $\bm{b}=(1~1~\ldots~1)^T$ and $\mathbf{B}_{i,j}=1, ~\forall i,j$. Then, by adding and , we obtain that $$\begin{aligned}
\label{eq:p1}
\mathbf{A}\bm{\pi}-\bm{\pi}+\mathbf{B}\bm{\pi}=\mathbf{b} \Rightarrow (\mathbf{A}-\mathbf{I}+\mathbf{B})\bm{\pi}=\bf{b}\end{aligned}$$ Now, we have to show that the inverse of $(\mathbf{A}-\mathbf{I}+\mathbf{B})$ exists, and hence $\bm{\pi}=(\mathbf{A}-\mathbf{I}+\mathbf{B})^{-1}\bf{b}$. Let $\bf{y}$ be a row vector such that $$\begin{aligned}
\label{eq:p2}
\bf{y}(\mathbf{A}-\mathbf{I}+\mathbf{B})=0.\end{aligned}$$ It is sufficient to show that $\bf{y}=\bf{0}$. Multiplying by $\bm{\pi}$, we have $$\begin{aligned}
\bf{y}(\mathbf{A}-\mathbf{I}+\mathbf{B})\bm{\pi}=\bf{y}(\mathbf{A}\bm{\pi}-\bm{\pi}+\mathbf{B}\bm{\pi}) =\bf{y}\mathbf{b}=0.\end{aligned}$$ Since $\mathbf{b}$ has strictly positive entries and $\bf{y}\mathbf{b}=0$, we conclude that $\bf{y}=\bf{0}$. We have shown that there exists a unique solution and that it is given by $\bm{\pi}=(\mathbf{A}-\mathbf{I}+\mathbf{B})^{-1}\bf{b}$.

[1]{}

J. N. Laneman, D. N. C. Tse, and G. W. Wornell, “Cooperative diversity in wireless networks: Efficient protocols and outage behavior”, *IEEE Trans. Inform. Theory*, vol. 50, pp. 3062–3080, Dec. 2004.

Z. Ding, I. Krikidis, B. Rong, J. S. Thompson, C. Wang, and S. Yang, “On combating the half-duplex constraint in modern cooperative networks: protocols and techniques,” *IEEE Wireless Commun.*, vol. 19, pp. 20–27, Dec. 2012.

Y. Fan, C. Wang, J. S. Thompson, and H. V. Poor, “Recovering multiplexing loss through successive relaying using repetition coding,” *IEEE Trans. Wireless Commun.*, vol. 6, pp. 4484–4493, Dec. 2007.

C. Wang, Y. Fan, I. Krikidis, J. S. Thompson, and H. V. Poor, “Superposition-coded concurrent decode-and-forward relaying,” in *Proc. IEEE Int. Symp. Inf. Theory*, Toronto, Canada, July 2008, pp. 2390–2394.

A. Bletsas, A. Khisti, D. Reed, and A. Lippman, “A simple cooperative diversity method based on network path selection,” [*IEEE J. Select. Areas Commun.*]{}, vol. 24, pp. 659-672, March 2006.

D. S. Michalopoulos and G. K. Karagiannidis, “Performance analysis of single relay selection in Rayleigh fading,” [*IEEE Trans. Wireless Commun.*]{}, vol. 7, pp. 3718–3724, Oct. 2008.

I. Krikidis, J. S. Thompson, Steve McLaughlin and Norbert Goertz, “Max-min relay selection for legacy amplify-and-forward systems with intereference," [*IEEE Trans Wireless Commun.*]{}, vol. 8, pp. 3016-3027, June 2009.

A. Bletsas, H. Shin, and M. Z. Win, “Cooperative communications with outage-optimal opportunistic relaying,” [*IEEE Trans. Wireless Commun.*]{}, vol. 6, pp. 3450–3460, Sept. 2007.

A. Ikhlef, D. S. Michalopoulos, and R. Schober, “Max-max relay selection for relays with buffers," [*IEEE Trans. Wireless Commun.*]{}, vol. 11, pp. 1124–1135, March 2012.

A. Ikhlef, K. Junsu, and R. Schober, “Mimicking full-duplex relaying using half-duplex relays with buffers," [*IEEE Trans. Vehicular Tech.*]{}, vol. 61, pp. 3025–3037, Sept. 2012.

I. Krikidis, T. Charalambous, and J. S. Thompson, “Buffer-aided relay selection for cooperative diversity systems without delay constraints," [*IEEE Trans. Wireless Commun.*]{}, vol. 11, pp. 1957–1967, May 2012.

N. Zlatanov, R. Schober, and P. Popovski, “Buffer-aided relaying with adaptive link selection," [*IEEE J. Select. Areas in Commun.*]{}, vol. 31, pp. 1–13, Aug. 2012.

N. Zlatanov and R. Schober, “Buffer-aided half-duplex relaying can outperform ideal full-duplex relaying,” *IEEE Commun. Lett.*, accepted for publication, 2013.

H. Liu, P. Popovski, E. de Carvalho, and Y. Zhao, “Sum-rate optimization in a two-way relay network with buffering,” *IEEE Commun. Lett.*, vol. 17, pp. 95-98, Jan. 2013.

N. Nomikos, D. N. Skoutas, D. Vouyioukas, C. Verikoukis, and C. Skianis, “Capacity maximization through energy-aware multi-mode relaying", in [*Springer Wireless Pers. Commun.*]{} DOI 10.1007/s11277-012-0899-5, 2012.

Z. Zhou, S. Zhou, J.-H. Cui, S. Cui, “Energy-efficient cooperative communication based on power control and selective single-relay in wireless sensor networks," in [*IEEE Trans. Wireless Commun.*]{}, vol. 7, pp. 3066–3078, Aug 2008.

F. Ke, S. Feng, and H. Zhuang, “Relay selection and power allocation for cooperative network based on energy pricing," [*IEEE Commun. Letters*]{}, vol. 14, pp.396-398, May 2010.

W. J. Huang, Y. W. Peter Hong, and C. C. Jay Kuo, “Lifetime maximization for amplify-and-forward cooperative networks,” *IEEE Trans. Wireless Commun.*, vol. 7, pp. 1800–1805, May 2008.

Z. Sheng, B. J. Ko, and K. K. Leung, “Power efficient decode-and-forward cooperative relaying," [*IEEE Wireless Commun. Letters*]{}, vol. 1, pp. 444-447, Oct 2012.

O. Amin, and L. Lampe, “Opportunistic energy efficient cooperative communication," [*IEEE Wireless Commun. Letters*]{}, vol. 1, pp. 412–415, Oct 2012.

S. Mousavifar and C. Leung,“Lifetime analysis of a two-hop amplify-and-forward opportunistic wireless relay network," *IEEE Trans. Wireless Commun.*, accepted for publication, 2013.

S. Ikki and P. S. Aissa, “Regenerative cooperative diversity networks with co-channel interference: Performance analysis and optimal energy allocation," [*IEEE Trans. Vehicular Tech.*]{}, accepted for publication, 2012.

Y. H. Chieh, and H. Ching-Yao, “Energy efficient subcarrier-power allocation and relay selection scheme for OFDMA-based cooperative relay networks,” in [*Proc. IEEE Int. Conf. Commun.*]{}, Kyoto, Japan, June 2011, pp. 1–6.

N. Nomikos and D. Vouyioukas, “A successive opportunistic relaying protocol with inter-relay interference mitigation,” [*Proc. IEEE Wireless Commun. Mob. Comp. Conf*]{}, Limassol, Cyprus, Aug. 2012, pp. 1–5.

A. Nosratinia and T.E. Hunter, “Grouping and partner selection in cooperative wireless networks,” [*IEEE J. Select. Areas in Commun.*]{}, vol. 25, no. 2, pp. 369–378, Feb. 2007.

V. Shah, N. B. Mehta, and R. Yim, “Splitting algorithms for fast relay selection: Generalizations, analysis, and a unified view,” [*IEEE Trans. Wireless Commun.*]{}, vol. 9, pp. 1525–1535, Apr. 2010.

[^1]: N. Nomikos, D. Vouyioukas and D. Skoutas are with the Department of Information and Communications Systems Engineering, University of the Aegean,Karlovassi 83200, Samos, Greece (E-mail: [{nnomikos,dvouyiou,d.skoutas}@aegean.gr]{}).

[^2]: T. Charalambous and M. Johansson are with the Automatic Control Lab, Electrical Engineering Department and ACCESS Linnaeus Center, Royal Institute of Technology (KTH), Stockholm, Sweden (Emails: [{themisc,mikaelj}@kth.se]{}).

[^3]: I. Krikidis is with the ECE Department, University of Cyprus, Nicosia 1678 (E-mail: [krikidis@ucy.ac.cy]{}).

[^4]: By single-link, we define the transmissions that take place either between the source and a receiving relay or those between a transmitting relay and the destination.

[^5]: A stochastic matrix $P\in \mathbb{R}^{m\times m}$ is said to be decomposable if there exists a nonempty proper subset $\mathcal{S} \subset \{v_1,v_2, \ldots, v_m \}$ such that $p_{ji}=p_{ij}=0$ whenever $v_i\in \mathcal{S}$ and $v_j \notin \mathcal{S}$. $P$ is indecomposable if it is not decomposable.

[^6]: In a finite state Markov Chain, a state $i$ is aperiodic if there exists $k$ such that for all $k' \geq k$, the probability of being at state $i$ after $k'$ steps is greater than zero; otherwise, the state is said to be periodic. A stochastic matrix is aperiodic if every state of the Markov chain it describes is aperiodic.

[^7]: By dominant we mean the states for which the probability of being at that state, when steady state is reached, is greater than zero.

[^8]: The diversity order (or diversity gain), denoted herein by $d$, is the gain in spatial diversity, used to improve the reliability of a link and it is defined as follows: $d = -\lim_{\textrm{SNR} \rightarrow \infty} \frac{\log \mathbb{P}_{\rm out}(\textrm{SNR})}{\log \textrm{SNR}}$.
