---
abstract: 'In this paper, a point-to-point Orthogonal Frequency Division Multiplexing (OFDM) system with a decode-and-forward (DF) relay is considered. The transmission consists of two hops. The source transmits in the first hop, and the relay transmits in the second hop. Each hop occupies one time slot. The relay is half-duplex, and capable of decoding the message on a particular subcarrier in one time slot, and re-encoding and forwarding it on a different subcarrier in the next time slot. Thus each message is transmitted on a pair of subcarriers in two hops. It is assumed that the destination is capable of combining the signals from the source and the relay pertaining to the same message. The goal is to maximize the weighted sum rate of the system by jointly optimizing subcarrier pairing and power allocation on each subcarrier in each hop. The weighting of the rates is to take into account the fact that different subcarriers may carry signals for different services. Both total and individual power constraints for the source and the relay are investigated. For the situations where the relay does not transmit on some subcarriers because doing so does not improve the weighted sum rate, we further allow the source to transmit new messages on these idle subcarriers. To the best of our knowledge, such a joint optimization inclusive of the destination combining has not been discussed in the literature. The problem is first formulated as a mixed integer programming problem. It is then transformed to a convex optimization problem by continuous relaxation, and solved in the dual domain. Based on the optimization results, algorithms to achieve feasible solutions are also proposed. Simulation results show that the proposed algorithms almost achieve the optimal weighted sum rate, and outperform the existing methods in various channel conditions.'
author:
- Chih Ning Hsu
- '\'
bibliography:
- 'IEEEabrv.bib'
- 'aning\_thesis.bib'
title: 'Joint Subcarrier Pairing and Power Allocation for OFDM Transmission with Decode-and-Forward Relaying'
---

OFDM, decode-and-forward relay, power allocation, subcarrier pairing, optimization, continuous relaxation, Lagrange dual problem.

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

For an Orthogonal Frequency Division Multiplexing (OFDM) system with relay, identifying a proper way to allocate resources to the source and the relay is the main bottleneck for achieving good performance. In this paper, we consider a point-to-point OFDM system with a decode-and-forward (DF) half-duplex relay. Each message is transmitted in two hops each occupying one time slot. A message transmitted by the source on one subcarrier in the first time slot is, if successfully decoded by the relay, forwarded by the relay to the destination on one (not necessarily the same) subcarrier in the second time slot. With the assumption that the channel state information (CSI) is known at the source, many works have been done to make resource utilization of this system more efficient.

A general downlink Orthogonal Frequency Division Multiple Access (OFDMA) relay system with individual power constraints at one source and many relays was considered in [@DF_individual_downlink]. In that work, joint optimization of the subcarrier selection and power allocation was done. However, that work assumed that a message is received by a destination either directly from the source, or from a relay which forwarded the message. Destination combining of the signals directly from the source and forwarded by the relay pertaining to the same message was not considered. In addition, as each relay collectively uses its active subcarriers to forward messages to different destinations, a more complicated re-encoding scheme has to be used by the relay to fit the received message for a particular destination into the subcarriers designated to that destination. In [@DF_OFDM_total_individual_power; @relay_DF_individual_power_constraint; @Vandendorpe_J], optimal power allocation for OFDM with DF relaying and fixed source and relay subcarrier pairing was proposed. [@DF_OFDM_total_individual_power][@Vandendorpe_J] considered two kinds of power constraints: one is that the total transmit power is shared between the source and the relay; the other has individual power constraints for the source and the relay. In [@relay_eq_channel_gain; @relay_AF_DF_eq_channel_gain; @Li_AFDF_OFDM], both power allocation and subcarrier pairing were considered for OFDM systems with relaying under the total power constraint. However, power allocation and subcarrier pairing were optimized separately. [@relay_eq_channel_gain] proposed a subcarrier pairing method by sorting the subcarriers of the source-relay (SR) link and the relay-destination (RD) link, respectively, according to their channel gains. The SR subcarrier and the RD subcarrier with the same respective ranks are then paired together. The optimality of this sorted channel pairing (SCP) scheme, in the absence of the source-destination (SD) link, for both DF and amplify-and-forward (AF) relaying schemes were proved in [@relay_AF_DF_eq_channel_gain][@Li_AFDF_OFDM]. SCP was also proposed in [@Herdin; @wittneben; @AF_pairing_without_diversity; @relay_AF_OPT_SUBCHANNEL_ASSIGNMENT] for OFDM AF relaying systems without the SD link, and in [@AF_OFDM_total_individual_power] when the SD link and destination combining are present. Power allocation with total and individual power constraints for OFDM AF relaying systems were considered in [@AF_pairing_without_diversity] and [@AF_OFDM_total_individual_power], while [@wittneben] focused on only the total power constraint. The above works dealing with power allocation for the OFDM AF relaying systems usually used approximations to relax the problem into a solvable one. Without making any approximations, [@relay_AF_total_optimal_power] investigated the optimal power allocation problem for the OFDM AF relaying systems with fixed subcarrier pairing and total power constraint in the absence of the SD link. In view of the lack of joint optimization of power allocation and subcarrier pairing for OFDM systems with DF relaying in the literature, the goal of this paper is to solve this problem with the presence of the SD link and destination combining of signals from the source and the relay. Both the total power constrained system and the individual power constrained system are considered. For the total power constrained system, we formulate the joint power allocation and subcarrier pairing problem as a mixed integer programming problem whose optimal solution is hard to obtain. We then use some special properties of the system and the continuous relaxation [@DF_individual_downlink][@concave_function] to reform the problem and solve the dual problem by the subgradient method [@subgradient_method]. With both the power and subcarrier pairing constraints, the optimization problem becomes very complicated, and the duality gap may not be zero. However, as verified by [@Yu_dual][@zero_gap_SUB_infinity] and our own simulation, the duality gap is virtually zero when the number of subcarriers is reasonably large. Thus the dual optimum value becomes a very tight upper bound for the primal optimum for most practical systems. In addition to the duality gap, some other practical issues such as algorithm design and complexity comparison are also discussed. We then extend the formulation to have individual power constraints, and find that the complications caused by individual power constraints can be alleviated in the dual domain. The dual optimum value is again a very tight upper bound for the primal optimum. Finally, we relax the constraint that only the relay can transmit in the second time slot. Therefore, additional messages may be transmitted on the idle subcarriers in the SD link in the second time slot, when it is deemed that relaying on these subcarriers does not improve the weighted sum rate. Such a model was also considered in [@Vandendorpe_J]. However, [@Vandendorpe_J] optimized power allocation (and relaying modes) only for a particular subcarrier pairing scheme without weighting of the rates. These conditions made the problem easier to solve. In this paper, we consider joint optimization of power allocation and subcarrier pairing with weighted rates. The problem is more general and difficult. However, by defining an additional indicator, we can formulate the problem similarly as in the case without the second-slot SD transmission. The problem is then solved in the dual domain. Simulation shows that, for this problem, the duality gap is also nearly zero. Based on the optimization results, algorithms to achieve feasible subcarrier pairing and power allocation are also proposed. Simulation results show that the proposed algorithms almost achieve the optimal weighted sum rate, and outperform the SCP proposed in [@relay_eq_channel_gain] in various channel conditions.

The rest of this paper is organized as follows. Section \[Sec\_system\_model\] describes the system model. Section \[Sec\_maximization\_typeI\] solves the optimization problem under the total power constraint. Detailed discussions on the practical issues are also presented in this section. Section \[sec\_maximization\_individual\] solves the optimization problem under the individual power constraints. Section \[sec\_maximization\_total\_extra\_direct\] formulates and solves the optimization problem for the system with additional messages transmitted on the SD link in the second time slot, under both total and individual power constraints. Section \[Sec\_simulation\] summarizes our results and observations. Section \[Sec\_conclusion\] concludes this paper.

System Model {#Sec_system_model}
============

We consider a two-hop DF relay system consisting of one source, one relay, and one destination. OFDM with the same spectral occupancy is used for all links. The total frequency band is divided into $M$ subcarriers. To avoid interference, for each subcarrier, only one node (the source or the relay) transmits in a given time slot. All time slots are of the same duration. The source transmits in the first time slot while the relay and the destination receive. The relay is half-duplex that receives in the first time slot and transmits in the second time slot. Each subcarrier used by the source in the first time slot is paired with one subcarrier used by the relay in the second time slot to convey a message. Therefore the number of subcarrier pairs in transmission is $M$. If subcarrier $k$ in the first time slot and subcarrier $m$ in the second time slot are paired, we call them subcarrier pair (SP) $(k,m)$. It is assumed that the relay re-encodes the received message with the same codebook as the one used by the source. The destination maximum ratio combines (MRC) the signals from the source in the first time slot and from the relay in the second time slot pertaining to the same message to exploit the spatial diversity. The messages transmitted on different SPs are assumed to be independent.

The channel model associated with SP $(k,m)$ is shown in Fig. \[Fig\_channel\_model\]. We use $h^{SD}_{k}$, $h^{SR}_{k}$, and $h^{RD}_{m}$ to denote the channel gains of the SD link, SR link, and RD link on subcarriers $k$, $k$, and $m$, respectively. $\sigma^2_{SD,k}$, $\sigma^2_{SR,k}$, and $\sigma^2_{RD,m}$ are the variances of the additive white Gaussian noises (AWGN) in the corresponding channels. As shown in Fig. \[Fig\_channel\_model\], we use $a^{SD}_{k}=\frac{| h^{SD}_{k}|^2}{\sigma^2_{SD,k}}$, $a^{SR}_{k}=\frac{|h^{SR}_{k}|^2}{\sigma^2_{SR,k}}$, and $a^{RD}_{m}=\frac{|h^{RD}_{m}|^2}{\sigma^2_{RD,m}}$ to denote the normalized channel gains. The channels are assumed to remain constant in a two-slot period. All the normalized channel gains are assumed known at the source which will perform subcarrier pairing and power allocation. The source then informs the relay and the destination of the corresponding parameters via proper control signaling before the data transmission. These assumptions are reasonable for the situations where the channel coherence time is longer than the sum of the CSI measurement and feedback time, the control signaling time, and the data transmission duration.

In practical implementation, the channel gains can be measured at the relay and the destination during the training period preceding the data transmission period. The training period has a similar structure as the data transmission period in which the source transmits training signals during the first time slot while the relay and the destination measure the SR and SD channels, respectively. The relay then transmits training signals in the second time slot to let the destination measure the RD channel. A training slot could be shorter than a data transmission slot. The measured channel gains can be fed back to the source on dedicated reverse control channels. After the source has done subcarrier pairing and power allocation, it can embed the pairing and power allocation parameters in the beginning of the first-slot data transmission. This embedded control signal is transmitted with stronger power and/or more reliable coding. So it can be guaranteed that the relay and destination can successfully decode the relevant parameters to figure out how to receive (and for the relay, how to forward as well) the upcoming data.

Taking the same assumption as in [@DF_OFDM_total_individual_power; @relay_DF_individual_power_constraint; @relay_eq_channel_gain; @relay_AF_DF_eq_channel_gain; @Li_AFDF_OFDM], in Section \[Sec\_maximization\_typeI\] and Section \[sec\_maximization\_individual\] we first consider the scenario where for each SP $(k,m)$, the source only transmits in the first time slot. Even if it is decided that the relay will not transmit on subcarrier $m$, the source is not allowed to use this idle subcarrier in the second time slot. In Section \[sec\_maximization\_total\_extra\_direct\], this restriction is relaxed and the source is allowed to transmit additional messages in the second time slot on the subcarriers not used by the relay. This model has also been investigated in [@Vandendorpe_J] which assumed fixed subcarrier pairing with SPs $(k,k), k=1, 2, \ldots, M$. Together with unweighted rates, the $(k,k)$ subcarrier pairing makes determination of whether the relay will be active for SP $(k,k)$ and optimal power allocation among the SPs easier to solve. However, it is inferior and less general than the joint optimization of subcarrier pairing and power allocation considered in Section \[sec\_maximization\_total\_extra\_direct\].

For the sake of generality, we consider weighted sum rate as the performance metric. A weighting factor $w_{k} \geq 0$ is assigned to the rate transmitted by the source on subcarrier $k$ to reflect different priorities or quality-of-service (QoS) requirements.

Weighted Sum Rate Maximization under Total Power Constraint {#Sec_maximization_typeI}
===========================================================

In this section, we consider joint optimization of subcarrier pairing and power allocation to achieve the highest weighted sum rate under the total power constraint. We first give the problem formulation. Then a solution in the dual domain is given. The duality gap and achievability of the optimal solution, together with some practical algorithm design issues, will be discussed.

Primal Problem Formulation {#primal_total}
--------------------------

For a given SP $(k,m)$, let $R_{k,m}$ be its achievable weighted rate, and $p^{S}_{k,m}$ and $p^{R}_{k,m}$ be the source power in the first time slot and the relay power in the second time slot, respectively. Depending on whether the relay is active, this SP may work in either the relay mode or the direct-link mode. In the relay mode, the half-duplex relay forwards the message on subcarrier $m$ in the second time slot. In the direct-link mode, the relay does not forward, and only subcarrier $k$ of the SD link in the first time slot is used to transmit the message. Thus the weighted rate achievable with Gaussian codebooks for SP $(k,m)$ can be expressed as [@relay_capacity_theorem] $$\label{Eq_pair_rate_typeI}
R_{k,m}=\left\{
\begin{aligned}
&\frac{w_{k}}{2}\log(1+a^{SD}_{k}p^{S}_{k,m}), &\text{direct-link mode}\\
&\frac{w_{k}}{2}\min\left\{\log\left(1+a^{SR}_{k}p^{S}_{k,m}\right),\; \log\left(1+a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}\right)\right\}, &\text{relay mode}\\
\end{aligned}
\right.$$ where the rate is scaled by $\frac{1}{2}$ because the transmission takes two time slots.

Under the total power constraint of $p_{k,m}=p_{k,m}^S+p_{k,m}^R$ for the SP $(k,m)$, using relay is advantageous in terms of maximizing the achievable rate when [@DF_OFDM_total_individual_power] $$\label{relay_condition_total}
a^{SR}_{k}>a^{SD}_{k}~ \text{ and } ~a^{RD}_{m}>a^{SD}_{k}.$$ In addition, based on the fact that, for the relay mode, the achievable rate is maximized when the amounts of received information at the relay and the destination are the same, the expressions in (\[Eq\_pair\_rate\_typeI\]) can be unified as [@relay_eq_channel_gain] $$\label{unified_rate}
\begin{aligned}
R_{k,m}=\frac{w_k}{2}\log(1+a_{k,m}p_{k,m}).
\end{aligned}$$ This is obtained by letting $$\label{power_ratio}
\begin{aligned}
&p^{S}_{k,m}=\left\{
\begin{aligned}
&\frac{a^{RD}_{m}}{a^{SR}_{k}+a^{RD}_{m}-a^{SD}_{k}}p_{k,m},&\text{relay mode}\\
&p_{k,m},&\text{direct-link mode}\\
\end{aligned}
\right.\\
&p^{R}_{k,m}=\left\{
\begin{aligned}
&\frac{a^{SR}_{k}-a^{SD}_{k}}{a^{SR}_{k}+a^{RD}_{m}-a^{SD}_{k}}p_{k,m},&\text{relay mode}\\
&0,&\text{direct-link mode}
\end{aligned}
\right.
\end{aligned}$$ in (\[Eq\_pair\_rate\_typeI\]), and defining $a_{k,m}$ as the equivalent channel gain given by $$\label{Eq_ECG}
a_{k,m}=\left\{
\begin{aligned}
&\frac{a^{SR}_{k}a^{RD}_{m}}{a^{SR}_{k}+a^{RD}_{m}-a^{SD}_{k}},&\text{relay mode}\\
&a^{SD}_{k},&\text{direct-link mode}.
\end{aligned}
\right.$$ Thus, when the channel gains are known, for any possible pairing, whether a SP $(k,m)$ should be in the relay mode or the direct-link mode, and the maximum achievable weighted rate of this SP as a function of the total power $p_{k,m}$, can be derived immediately. Define an indicator $t_{k,m}$ which is 1 if SP $(k,m)$ is selected, and 0 otherwise. The weighted sum rate optimization problem can be formulated as $$\begin{aligned}
\label{objective_Rate_I_MIP}
\max_{{\bm p},{\bm t}}\text{ }&\sum^M_{k=1}\sum^M_{m=1}t_{k,m}\frac{w_{k}}{2}\log(1+a_{k,m}p_{k,m})
\\
\label{constraint_power_consumption}
\text{s.t.}\text{ }&\sum^M_{k=1}\sum^M_{m=1}p_{k,m}\leq P,
\\
\label{constraint_t_k}
&\sum^M_{k=1}t_{k,m}=1,\text{ }\forall m,
\\
\label{constraint_t_m}
&\sum^M_{m=1}t_{k,m}=1,\text{ }\forall k,
\\
\label{constraint_power_0}
&p_{k,m}\geq~0,\text{ }\forall k, m,
\\
\label{constraint_t_binary}
&t_{k,m}\in\{0,1\},\text{ }\forall k, m,\end{aligned}$$ where $P$ is the total power constraint, ${\bm p}\in \mathds{R}_+^{M \times M}$ (with $\mathds{R}_+$ denoting the set of nonnegative real numbers) and ${\bm t}\in\{0,1\}^{M \times M}$ are matrices with entries $p_{k,m}$ and $t_{k,m}$, respectively. Since the power allocated to the unselected SPs does not contribute to the weighted sum rate, it is obvious that the optimal solution will only allocate non-zero power to the selected SPs. Although similar in the approach, there are some significant differences between the above problem formulation and the ones in [@DF_individual_downlink] and [@relay_AF_OPT_SUBCHANNEL_ASSIGNMENT]. [@DF_individual_downlink] and [@relay_AF_OPT_SUBCHANNEL_ASSIGNMENT] both did not consider the SD link and destination combining when the relay is used. In [@relay_AF_OPT_SUBCHANNEL_ASSIGNMENT], the power allocated to each subcarrier is fixed. As mentioned in Section \[introduction\], the relays in [@DF_individual_downlink] have to use complicated re-encoders with codebooks different from that of the source. These differences make our optimization problem distinct from [@DF_individual_downlink] and [@relay_AF_OPT_SUBCHANNEL_ASSIGNMENT].

The above problem is a mixed integer programming (MIP) problem which is hard to solve. Therefore, as in [@concave_function][@multilevel_waterfilling], we relax the integer constraint of (\[constraint\_t\_binary\]) as $t_{k,m}\in \mathds{R}_+, \forall k, m$. This continuous relaxation makes $t_{k,m}$ the time sharing factor of each SP. The relaxed problem then becomes $$\begin{aligned}
\label{objective_Rate_I_relaxed}
\max_{{\bm p},{\bm t}} ~\frac{1}{2}\sum^M_{k=1}\sum^M_{m=1}t_{k,m}~w_{k}\log\left(1+a_{k,m}\frac{p_{k,m}}{t_{k,m}}\right)~~\text{s.t.}~~
(\ref{constraint_power_consumption}),
(\ref{constraint_t_k}), (\ref{constraint_t_m}),
(\ref{constraint_power_0}), ~\text{and}\\
\label{constraint_t_0}
t_{k,m}\geq 0,\text{ }\forall k, m.\end{aligned}$$ Note that the value of the objective function (\[objective\_Rate\_I\_relaxed\]) is the same as that of the original objective function (\[objective\_Rate\_I\_MIP\]) when $t_{k,m}\in\{0,1\}, \forall k, m$. This objective function is concave because it is a nonnegative weighted sum of concave functions in the form of $x\log(1+\frac{y}{x})$ which is concave in $(x, y)$ [@concave_function]. Since (\[objective\_Rate\_I\_relaxed\]) is a standard convex programming problem, it can be solved by numerical search algorithms such as the interior-point method [@Book_Boyd]. However, the optimal $t_{k,m}$ may not be integer-valued. Therefore, we opt to solve this problem by the dual method which can provide an upper bound for problem (\[objective\_Rate\_I\_relaxed\]) (by the weak duality [@Book_Boyd]). In Section \[sec\_dual\_type\_I\_total\], it will be shown that the solution obtained by the dual method has $t_{k,m}\in\{0,1\}, \forall k, m$.

Dual Problem {#sec_dual_type_I_total}
------------

By dualizing constraints (\[constraint\_power\_consumption\]) and (\[constraint\_t\_k\]), we obtain the Lagrangian as follows: $$\label{Lagrangian_typeI}
\begin{aligned}
L( {\bm p}, {\bm t},\mu, {\bm \alpha})=&\frac{1}{2}\sum_{k=1}^M\sum_{m=1}^Mt_{k,m}~w_{k}\log\left(1+a_{k,m}\frac{p_{k,m}}{t_{k,m}}\right)\\
&+\mu\left(P-\sum_{k=1}^M\sum_{m=1}^M~p_{k,m}\right)+\sum_{m=1}^M\alpha_m\left(1-\sum_{k=1}^M~t_{k,m}\right),
\end{aligned}$$ where $\mu\in \mathds{R}_+$ and ${\bm \alpha} ~(\text{the vector of} ~\alpha_m) \in\mathds{R}^M$ are the dual variables, with $\mathds{R}$ denoting the set of real numbers. The dual objective function is $$\label{P_Lagrange_typeI}
h(\mu, {\bm \alpha})=
\max_{{\bm p}, {\bm t}} ~L({\bm p},{\bm t},\mu, {\bm \alpha}) ~~\text{s.t.}~~ (\ref{constraint_t_m}),(\ref{constraint_power_0}),(\ref{constraint_t_0})$$ and the dual problem is $$\label{objective_dual}
\min_{\mu, {\bm \alpha}} ~h(\mu, {\bm \alpha})
~~\text{s.t.}~~ \mu\geq 0.$$ It is well known that a function can be maximized by first maximizing over some of the variables, and then maximizing over the remaining ones [@Book_Boyd Sec 4.1.3]. Thus we first solve $p_{k,m}$ for (\[P\_Lagrange\_typeI\]) by $$\label{Eq_L_partial_p_typeI}
\frac{\partial{L}}{\partial{p_{k,m}}}=\frac{t_{k,m}w_{k}}{2}\frac{\frac{a_{k,m}}{t_{k,m}}}{1+a_{k,m}\frac{p_{k,m}}{t_{k,m}}}-\mu=\frac{w_{k}}{2}\frac{1}{\frac{1}{a_{k,m}}+\frac{p_{k,m}}{t_{k,m}}}-\mu =0$$ with constraint (\[constraint\_power\_0\]). The optimal solution is $$\begin{aligned}
\label{optimal power_typeI}
p_{k,m}^\ast=t_{k,m}\left[\frac{w_{k}}{2\mu}-\frac{1}{a_{k,m}}\right]^+,\end{aligned}$$ where $x^+\triangleq\max\{x,0\}$. This is similar to the result of multi-level water-filling[@multilevel_waterfilling]. We then rewrite (\[Lagrangian\_typeI\]) as $$\begin{aligned}
L({\bm p}^*,{\bm t},\mu, {\bm \alpha})=\sum_{k=1}^M\sum_{m=1}^M~t_{k,m}X_{k,m}+K(\mu, {\bm \alpha}),
\end{aligned}$$ where $$\label{compute X}
X_{k,m}=\frac{w_{k}}{2}\log\left(1+a_{k,m}\left[\frac{w_{k}}{2\mu}-\frac{1}{a_{k,m}}\right]^+\right)-\alpha_m
-\mu\left(\left[\frac{w_{k}}{2\mu}-\frac{1}{a_{k,m}}\right]^+\right),$$ $$K(\mu, {\bm \alpha})=\mu P+\sum_{m=1}^M \alpha_m.$$ We give an intuitive explanation for each term in $X_{k,m}$. The first term can be viewed as the rate obtained by selecting subcarrier $m$ in the second time slot for subcarrier $k$ in the first time slot. $\alpha_m$ is the penalty of selecting subcarrier $m$ in the second time slot. The last term is the price of power consumption.

Due to the fact that $K(\mu, {\bm \alpha})$ and $X_{k,m}$ are independent of ${\bm t}$, we can easily find the optimal ${\bm t}$ for (\[P\_Lagrange\_typeI\]) with constraints (\[constraint\_t\_m\]) and (\[constraint\_t\_0\]) as $$\label{optimal_t_typeI}
t_{k,m}^\ast=\left\{
\begin{aligned}
&1,\text{ }m=\arg\max_{m=1,...,M}X_{k,m}\\
&0,\text{ otherwise}
\end{aligned}, ~~~~\forall k
\right. .$$ In operation, we first assume that $\mu$ and $\alpha_m$’s are given. Then the power allocation for every possible SP can be computed by (\[optimal power\_typeI\]) (with $t_{k,m}$ ignored). These power allocation values are used in (\[compute X\]) to compute $X_{k,m}$’s. After that, each subcarrier $k$ in the first time slot will independently select the subcarrier in the second time slot that gives the largest $X_{k,m}$ to maximize the the dual objective function (\[P\_Lagrange\_typeI\]).

The last step is to find the values of $\mu$ and ${\bm \alpha}$ which minimize $h(\mu,{\bm \alpha})$. Using the subgradient method [@subgradient_method], the values of $\mu$ and ${\bm \alpha}$ can be found iteratively as $$\label{sub_gradient_typeI_total}
\begin{aligned}
&\mu^{(i+1)}=\mu^{(i)}-y^{(i)}\left(P-\sum_{k=1}^M\sum_{m=1}^M~p^{(i)}_{k,m}\right),\\
&\alpha_m^{(i+1)}=\alpha_m^{(i)}-z^{(i)}\left(1-\sum_{k=1}^M~t_{k,m}^{(i)}\right)\text{, }m=1,...,M,
\end{aligned}$$ where the superscript $(i)$ denotes the iteration index, and $y^{(i)}$ and $z^{(i)}$ are the sequences of step sizes designed properly. With the new $\mu$ and ${\bm \alpha}$ in each iteration, the subcarrier pairing and power allocation can be updated with (\[optimal\_t\_typeI\]) and (\[optimal power\_typeI\]), respectively, for the next iteration. As the number of iterations increases, (\[sub\_gradient\_typeI\_total\]) will converge to the dual optimum variables [@subgradient_method]. The optimal ${\bm \alpha}$, together with (\[optimal\_t\_typeI\]), make $t_{k,m}^\ast$’s satisfy (\[constraint\_t\_k\]) and (\[constraint\_t\_m\]).

Note that with the optimal power allocation given in (\[optimal power\_typeI\]), the achievable rate for SP $(k, m)$ is $$\label{impact_weighting}
\begin{aligned}
\frac{1}{2}\log\left(1+a_{k,m}\left[\frac{w_{k}}{2\mu}-\frac{1}{a_{k,m}}\right]^+\right)=\frac{1}{2}\log\left(1+a_{k,m}w_{k}\left[\frac{1}{2\mu}-\frac{1}{w_{k}a_{k,m}}\right]^+\right).
\end{aligned}$$ From (\[impact\_weighting\]), the impact of the weighting factors can be viewed as weighting the channel gain of SP $(k, m)$ by $w_{k}$. A higher weighting factor results in more power allocated to the corresponding SP.

Discussion on the Duality Gap {#duality_gap_total}
-----------------------------

For problem (\[objective\_Rate\_I\_MIP\]), the optimal subcarrier pairing scheme may change as the total power constraint varies. Thus the maximum weighted sum rate as a function of the total power constraint may have discrete changes in the slope at the transition points where the optimal subcarrier pairing scheme changes. An example is shown in the circled region in Fig. \[Fig\_rate\_power\_concave\] for $M=2$ subcarriers. This phenomenon is similar to that observed in the optimal resource allocation for OFDMA downlink systems [@zero_gap_SUB_infinity]. However, in our case, this phenomenon is observed even when the weighting factors for all subcarriers are set to the same. As discussed in [@Yu_dual][@zero_gap_SUB_infinity], the nonconcavity shown in Fig. \[Fig\_rate\_power\_concave\] may result in nonzero duality gap. Let us denote the optimal values of the original problem (\[objective\_Rate\_I\_MIP\]), the relaxed problem (\[objective\_Rate\_I\_relaxed\]), and the relaxed dual problem (\[objective\_dual\]) by $R_B$, $R_R$, and $D_R$, respectively. The relationship between them is $R_B\leq~R_R\leq~D_R$. Since the optimal $t_{k,m}^\ast$’s found by solving (\[P\_Lagrange\_typeI\]) and (\[objective\_dual\]) satisfy (\[constraint\_t\_k\]), (\[constraint\_t\_m\]) and (\[constraint\_t\_binary\]), we conclude that $D_R$ is also the dual optimum value for problem (\[objective\_Rate\_I\_MIP\]).

According to [@Yu_dual][@Chiang_zero_gap][@zero_gap_SUB_infinity], the duality gap is zero if the optimal value of the optimization problem is a concave function of the constraints. [@Yu_dual] and [@zero_gap_SUB_infinity] also showed analytically and through simulations that the concavity will be satisfied as the number of subcarriers becomes large. In our case, we found that the concavity is mostly satisfied when the number of subcarriers is reasonably large. Specifically, when $M=2$, we have observed in simulation that only about $1\%$ of the possible channel realizations will result in the nonconcavity shown in Fig. \[Fig\_rate\_power\_concave\]. When $M=4$, the probability of nonconcavity is about $0.4\%$. For $M \geq 6$, the maximum weighted sum rate is almost always concave in the total power constraint. An example is shown in Fig. \[Fig\_rate\_power\_concave\] for $M=8$ subcarriers. Thus, for practical OFDM systems, the duality gap is virtually zero, and $R_B\approx D_R$. We can then conclude that $R_B\approx R_R\approx D_R$ for most practical OFDM systems. This will be verified by the simulation results in Section \[Sec\_simulation\].

Algorithm Design {#Sec_achieave_feasible}
----------------

Combining (\[optimal\_t\_typeI\]), (\[optimal power\_typeI\]) and (\[sub\_gradient\_typeI\_total\]), the algorithm to find the optimal subcarrier pairing and power allocation can be designed as in the upper part of Table \[Table\_algo\_obtain\_feasible\_typeI\]. However, through simulation, we have observed that although (\[optimal\_t\_typeI\]) guarantees that each row of ${\bm t}$ has only one “1", some of the “1"s may be on the same column. This corresponds to the situation where more than one source subcarriers select the same relay subcarrier. As a result, the constraint (\[constraint\_t\_k\]) is violated, and the solution is not feasible. This situation usually arises in two scenarios. The first is when there are more than one source subcarriers with very strong SD gains, such that no matter which relay subcarrier they are paired with, the direct-link mode will be selected. For any of these source subcarriers, the power related terms in $X_{k,m}$ (\[compute X\]) are the same for all relay subcarriers. Thus the relay subcarrier selection (\[optimal\_t\_typeI\]) depends only on $\alpha_m$. The source subcarriers with this property will select the same relay subcarrier. The other scenario is when a source subcarrier gets a low equivalent SP channel gain $a_{k,m}$ no matter which relay subcarrier it is paired with. All the possible SPs formed by this source subcarrier will be allocated very little power, thus their $X_{k,m}$’s are dominated by the corresponding $\alpha_m$’s. Similarly, the source subcarriers with this property will most likely select the same relay subcarrier.

To handle this situation, we include an amendment algorithm in the original algorithm as shown in the lower part of Table \[Table\_algo\_obtain\_feasible\_typeI\]. Based on the above discussion, the basic idea of the amendment algorithm is to each time move a “1" in a column of ${\bm t}$ with more than one “1"s to the column with no “1" that will cause the minimum change in the value of $\alpha_m$. By moving a “1" to another column with a similar $\alpha_m$ value, the weighted sum rate will not be lowered much. When doing so, the amendment algorithm will make sure to keep the “1" corresponding to the largest $X_{k,m}$ for each column with more than one “1"s. It will also move the redundant “1"s to the columns with no “1" that will result in as large $X_{k,m}$ values as possible. Thus the resultant weighted sum rate will be maximized. Eventually the pairing scheme ${\bm t}$ altered by the amendment algorithm will meet the constraints (\[constraint\_t\_k\]) and (\[constraint\_t\_m\]).

The amendment algorithm is triggered when the dual variables converge to a certain degree (for the example in Table \[Table\_algo\_obtain\_feasible\_typeI\], within 1%). Once the amendment algorithm is triggered, the algorithm will continue to run for another 10% of iterations. For example, if the amendment algorithm is triggered at the 1000th iteration, the algorithm will run another 100 iterations before it outputs the solution. For each of these 10% of iterations, a feasible pairing scheme will be obtained by the amendment algorithm. Using this pairing scheme, regular water-filling over parallel channels will be applied to obtain the optimal power allocation and the corresponding weighted sum rate. The best pairing scheme and power allocation among these iterations that achieve the highest weighted sum rate will be the outputs of this algorithm. As shown in Section \[Sec\_simulation\], the weighted sum rate obtained by the algorithm in Table \[Table\_algo\_obtain\_feasible\_typeI\] is quite close to the optimal.

Complexity Comparison
---------------------

The total number of all possible pairing schemes is $O(M!)$. With a fixed subcarrier pairing scheme, the complexity of computing the optimal power allocation (\[optimal power\_typeI\]) for the selected pairs is $O(M)$ in terms of multiplications. The complexity of computing the resulting weighted sum rate (weighted sum of (\[unified\_rate\])) is also $O(M)$ in terms of $\log(\cdot)$ operations and multiplications. Thus the complexity of exhaustive search is $O(M\cdot M!)$ which is prohibitively high.

On the other hand, in each iteration of the algorithm in Table \[Table\_algo\_obtain\_feasible\_typeI\], the complexity is dominated by the computation of $X_{k,m}, \forall k,m$, in (\[compute X\]). That complexity is $O(M^2)$ in terms of $\log(\cdot)$ operations and multiplications. For the amendment algorithm in the last 10% of iterations, alteration of the pairing scheme ${\bm t}$ takes only $O(M^2)$ additions and $\max(\cdot)$ and $\min(\cdot)$ operations. The complexity of computing the optimal power allocation and the resulting weighted sum rate is $O(M)$ multiplications and $\log(\cdot)$ operations. Therefore the overall complexity for the algorithm in Table \[Table\_algo\_obtain\_feasible\_typeI\] is $O(JM^2)$, where $J$ is the number of iterations. This complexity is much more feasible and tractable.

Weighted Sum Rate Maximization under Individual Power Constraints {#sec_maximization_individual}
=================================================================

When the source and the relay have individual power constraints, the weighted sum rate maximization problem becomes $$\begin{aligned}
\label{objective_Rate_I_individual}
\max_{{\bm p}_{S},{\bm p}_{R},{\cal S}_S,{\cal S}_R} & ~\frac{w_{k}}{2} \left(\sum_{(k,m) \in {\cal S}_S}\log\left(1+a^{SD}_{k}p^{S}_{k,m}\right) \right.\\
&\left.+\sum_{(k,m) \in {\cal S}_R} \min\left\{\log\left(1+a^{SR}_{k}p^{S}_{k,m}\right),\; \log\left(1+a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}\right)\right\} \right)
\\
\label{constraint_individual_power_0}
\text{s.t.}\text{ }&p^S_{k,m}, ~p^{R}_{k,m}\geq~0,\forall k, m
\\
\label{constraint_source_power_consumption}
&\sum_{(k,m) \in {\cal S}_S \cup {\cal S}_R} p^S_{k,m}\leq P_{S}
\\
\label{constraint_relay_power_consumption}
&\sum_{(k,m) \in {\cal S}_R} p^R_{k,m}\leq P_{R}\end{aligned}$$ where $P_{S}$ and $P_{R}$ are the source and the relay power constraints, respectively, and ${\bm p}_{S} \in \mathds{R}_+^{M\times M}$ and ${\bm p}_{R} \in \mathds{R}_+^{M\times M}$ are the matrices of $p^S_{k,m}$ and $p^R_{k,m}$, respectively. ${\cal S}_S$ and ${\cal S}_R$ denote the sets of SPs operating in the direct-link mode and the relay mode, respectively. If we let $t_{k,m}=1$ when $(k,m) \in {\cal S}_S \cup {\cal S}_R$ and $t_{k,m}=0$ otherwise, ${\cal S}_S$ and ${\cal S}_R$ must satisfy the additional constraints (\[constraint\_t\_k\]) and (\[constraint\_t\_m\]).

This problem is very complicated. Because the condition to use relay depends not only on the channel condition, but also indirectly on the source power and relay power constraints [@DF_OFDM_total_individual_power][@relay_DF_individual_power_constraint][@Vandendorpe_J], it is not possible to classify the SPs into the direct-link mode or the relay mode in advance to use the unified weighted rate formulation (\[unified\_rate\]) and the equivalent channel gain (\[Eq\_ECG\]). In Section \[unified\_rate\_individual\], we will first investigate optimal power allocation with fixed subcarrier pairing under individual power constraints considered in [@DF_OFDM_total_individual_power][@relay_DF_individual_power_constraint][@Vandendorpe_J]. Through some insightful observations on the results of [@relay_DF_individual_power_constraint], we will find that the unified weighted rate formulation (\[unified\_rate\]) and the equivalent channel gain (\[Eq\_ECG\]) can, in fact, be applied to the dual problem of (\[objective\_Rate\_I\_individual\]). After that, (\[objective\_Rate\_I\_individual\]) can be solved similarly as in the total power constrained case.

Unified Rate Formulation {#unified_rate_individual}
------------------------

For (\[objective\_Rate\_I\_individual\]), assuming fixed subcarrier pairing, a Lagrangian similar to [@relay_DF_individual_power_constraint eq. (8)] with slight changes can be obtained $$\label{Louveaux_Lagrange}
\begin{aligned}
L&=\sum_{(k,m) \in {\cal S}_S}\frac{w_{k}}{2}\log\left(1+a^{SD}_{k}p^{S}_{k,m}\right)\\
&+\sum_{(k,m) \in {\cal S}_R}\frac{w_{k}}{2}\log\left(1+a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}\right)\\
&+\mu_{S}\left(P_{S}-\sum_{k=1}^M p^{S}_{k,m}\right)+\mu_{R}\left(P_{R}-\sum_{(k,m) \in {\cal S}_R}
 p^{R}_{k,m}\right)\\
&+\sum_{(k,m) \in {\cal S}_R}\rho_{k,m}\left(a^{SR}_{k}p^{S}_{k,m}-a^{SD}_{k}p^{S}_{k,m}-a^{RD}_{m}p^{R}_{k,m}\right),
\end{aligned}$$ where $\mu_S\geq 0$ and $\mu_R \geq 0$ denote the Lagrange multipliers corresponding to the source power constraint $P_S$ and the relay power constraint $P_R$, respectively. The third Lagrange multiplier $\rho_{k,m} \geq 0$ corresponds to the condition $$\label{Louveaux_relay_condition}
a^{SR}_{k}p^{S}_{k,m} \geq a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}$$ for the SP $(k,m)$ to operate in the relay mode [@relay_DF_individual_power_constraint][@Vandendorpe_J]. If (\[Louveaux\_relay\_condition\]) is not valid for a relay mode SP, apparently some of that SP’s relay power can be reallocated, without reducing its rate, to other relay subcarriers to improve their rates, or simply to be conserved. Following the same procedures as in [@relay_DF_individual_power_constraint], a SP $(k,m)$ can be further classified into the following three modes given that $\mu_S$ and $\mu_R$ are fixed: $$\label{mode_conditions_individual}
\left\{
\begin{aligned}
&\text{Direct-link mode}:&&a^{SD}_{k}\geq~a^{SR}_{k}\text{ or
}a^{RD}_{m}<~a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}\\
&\text{Relay mode}:&&a^{SR}_{k}>a^{SD}_{k}\text{ and } a^{RD}_{m}>a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}\\
&\text{Intermediate mode}:&&a^{SR}_{k}>a^{SD}_{k}\text{ and } a^{RD}_{m}=a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}},\\
\end{aligned}
\right.$$ where the intermediate mode is a special case of the relay mode with the condition (\[Louveaux\_relay\_condition\]) satisfied with strict inequality (and the corresponding $\rho_{k,m}=0$). That is, the relay receives more information than the destination. Thus the relay mode here is redefined to include only the SPs that satisfy (\[Louveaux\_relay\_condition\]) with equality. That is, the amounts of received information are the same at the relay and the destination. According to [@relay_DF_individual_power_constraint], usually there is at most one SP in the intermediate mode. For both the relay mode and the intermediate mode SPs, the solutions that maximize the Lagrangian (\[Louveaux\_Lagrange\]) will make its last term zero.

The first condition $a^{SD}_{k}\geq a^{SR}_{k}$ for selecting the direct-link mode over the relay mode for SP $(k,m)$ is based on the fact that, in this situation, the destination will receive more information than the relay. Then there is no need to use the relay. The second condition $a^{RD}_{m}<a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}$ ensures that the direct-link mode will contribute more to the Lagrangian (\[Louveaux\_Lagrange\]) than the relay mode. For example, for SP $(k,m)$, if the power “cost" for selecting the direct-link mode, $\mu_S p^{S}_{k,m}$, in (\[Louveaux\_Lagrange\]) is kept the same as the power cost for selecting the relay mode, $\mu_S p^{S}_{k,m}+\mu_R p^{R}_{k,m}$, when $a^{RD}_{m}<a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}$, selecting the direct-link mode will result in a higher weighted rate (hence larger value of (\[Louveaux\_Lagrange\])) than selecting the relay mode. This is implied by the “single sum power constraint” approach in [@Vandendorpe_J eqs. (39) and (40)] with modified power and channel gain variables.

By solving (\[Louveaux\_Lagrange\]) for weighted sum rate maximization, the power allocation can be obtained $$\label{Louveaux_power_allocation}
\left\{
\begin{aligned}
&\text{Direct-link mode}:&& p^{S}_{k,m}=\left[\frac{w_{k}}{2\mu_{S}}-\frac{1}{a^{SD}_{k}}\right]^+, ~p^{R}_{k,m}=0\\
&\text{Relay mode}:&& p^{S}_{k,m}=\left[\frac{w_{k}}{2\left(\mu_{S}+\mu_{R}/\beta_{k,m}\right)}-\frac{1}{a^{SR}_{k}}\right]^+, ~p^{R}_{k,m}=\left[\frac{w_{k}}{2\left(\mu_{S}\beta_{k,m}+\mu_{R}\right)}-\frac{1}{a^{SR}_{k}\beta_{k,m}}\right]^+\\
&\text{Intermediate mode}:&& \text{According to } ~1+a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}=\frac{w_{k}a^{SD}_{k}}{2\mu_{S}}, ~~~a^{RD}_{m}=a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}},\\
&&&\text{and source and relay power constraints}, \\
\end{aligned}
\right.$$ where $$\beta_{k,m}=\frac{a^{RD}_m}{a^{SR}_k-a^{SD}_k}.$$ Power allocation for the intermediate mode SP can be computed after the power allocations for the direct-link mode and relay mode SPs are done. Note that since the relay mode SPs must satisfy (\[Louveaux\_relay\_condition\]) with equality, it is clear that $p^S_{k,m}=\beta_{k,m}p^R_{k,m}$. From (\[mode\_conditions\_individual\]) we know that for the relay mode, $\beta_{k,m}>0$. Thus $p^{S}_{k,m}$ and $p^{R}_{k,m}$ must be zero or positive simultaneously. This can also be seen from the relay mode power allocation in (\[Louveaux\_power\_allocation\]). This observation allows us to allocate total power $p_{k,m}=p^{S}_{k,m}+ p^{R}_{k,m}$ to the relay mode SPs first according to $$\label{power_allocation_relay_individual}
p_{k,m}=\left(\beta_{k,m}+1\right)\left[\frac{w_{k}}{2\left(\mu_{S}\beta_{k,m}+\mu_{R}\right)}-\frac{1}{a^{SR}_{k}\beta_{k,m}}\right]^+,$$ then obtain the corresponding $p^{S}_{k,m}$ and $p^{R}_{k,m}$ using the relay mode power distribution in (\[power\_ratio\]). To this end, the unified weighted rate expression in (\[unified\_rate\]) with (\[power\_ratio\]) and the equivalent channel gain (\[Eq\_ECG\]) can be applied here as well to the direct-link mode and relay mode SPs, when $\mu_S$ and $\mu_R$ are fixed.

As to the intermediate mode SP, we examine its contributions to the rate and cost in the Lagrangian (\[Louveaux\_Lagrange\]) and find that, with $\rho_{k,m}=0$ [@relay_DF_individual_power_constraint], they are $$\begin{aligned}
\text{rate}&=\frac{w_{k}}{2}\log\left(1+a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}\right)=\frac{w_{k}}{2}\log\left(\frac{w_{k}a^{SD}_{k}}{2\mu_{S}}\right)\\
\text{cost}&=\mu_{S}p^{S}_{k,m}+\mu_{R}p^{R}_{k,m}=\mu_{S}\left(p^{S}_{k,m}+\frac{\mu_{R}}{\mu_{S}}p^{R}_{k,m}\right)\\
&=\mu_{S}\left(p^{S}_{k,m}+\frac{a^{RD}_{m}}{a^{SD}_{k}}p^{R}_{k,m}\right)=\frac{\mu_{S}}{a^{SD}_{k}}\left(a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}\right)\\
&=\frac{\mu_{S}}{a^{SD}_{k}}\left(\frac{w_{k}a^{SD}_{k}}{2\mu_{S}}-1\right)=\mu_{S}\left(\frac{w_{k}}{2\mu_{S}}-\frac{1}{a^{SD}_{k}}\right)
\end{aligned}.$$ If the intermediate mode SP was classified as a direct-link mode SP, it would contribute to the Lagrangian (\[Louveaux\_Lagrange\]) with $$\begin{aligned}
\text{rate}&=\frac{w_{k}}{2}\log\left(1+a^{SD}_{k}p^{S}_{k,m}\right)=\frac{w_{k}}{2}\log\left(1+a^{SD}_{k}\left(\frac{w_{k}}{2\mu_{S}}-\frac{1}{a^{SD}_{k}}\right)\right)\\
&=\frac{w_{k}}{2}\log\left(\frac{w_{k}a^{SD}_{k}}{2\mu_{S}}\right)\\
\text{cost}&=\mu_{S}p^{S}_{k,m}=\mu_{S}\left(\frac{w_{k}}{2\mu_{S}}-\frac{1}{a^{SD}_{k}}\right)
\end{aligned}.$$ On the other hand, if it was classified as a relay mode SP, with $\rho_{k,m}=\frac{a^{RD}_{m}\mu_S-a^{SD}_{k}\mu_R}{a^{SR}_{k}a^{RD}_{m}}=0$, its contributions to the Lagrangian (\[Louveaux\_Lagrange\]) would be $$\begin{aligned}
\text{rate}&=\frac{w_{k}}{2}\log\left(1+a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}\right)\\
&=\frac{w_{k}}{2}\log\left(1+\frac{w_{k}a^{SD}_{k}}{2\left(\mu_{S}+\mu_{R}/\beta_{k,m}\right)}-\frac{a^{SD}_{k}}{a^{SR}_{k}}+\frac{w_{k}a^{RD}_{m}/\beta_{k,m}}{2\left(\mu_{S}+\mu_{R}/\beta_{k,m}\right)}-\frac{a^{RD}_{m}/\beta_{k,m}}{a^{SR}_{k}}\right)\\
&=\frac{w_{k}}{2}\log\left(\frac{w_{k}a^{SR}_{k}}{2\left(\mu_{S}+\mu_{S}\frac{a^{RD}_{m}}{a^{SD}_{k}\beta_{k,m}}\right)}\right)=\frac{w_{k}}{2}\log\left(\frac{w_{k}a^{SD}_{k}}{2\mu_{S}}\right)\\
\text{cost}&=\mu_{S}p^{S}_{k,m}+\mu_{R}p^{R}_{k,m}=\frac{\mu_{S}}{a^{SD}_{k}}\left(a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}\right)=\frac{\mu_{S}}{a^{SD}_{k}}\left(a^{SR}_{k}p^{S}_{k,m}\right)\\
&=\frac{\mu_{S}a^{SR}_{k}}{a^{SD}_{k}}\left(\frac{w_{k}}{2\left(\mu_{S}+\mu_{R}/\beta_{k,m}\right)}-\frac{1}{a^{SR}_{k}}\right)\\
&=\mu_{S}\left(\frac{w_{k}}{2\mu_{S}}-\frac{1}{a^{SD}_{k}}\right)
\end{aligned}.$$ Interestingly, with given $\mu_S$ and $\mu_R$, the intermediate mode SP’s contributions to the Lagrangian (\[Louveaux\_Lagrange\]) remain the same no matter it is classified to the direct-link mode or the relay mode. Thus, in terms of maximizing the Lagrangian, we can assign the intermediate mode SP to either mode without affecting the result. However, once the optimal $\mu_S$ and $\mu_R$ are obtained, we still need to identify the intermediate mode SP and allocate its powers according to (\[Louveaux\_power\_allocation\]).

In the following, we will assign the intermediate mode SP to the relay mode. Together with the conclusion that the unified weighted rate and equivalent channel gain expressions can be applied when $\mu_S$ and $\mu_R$ are fixed, the dual problem of (\[objective\_Rate\_I\_individual\]) can be formulated with unified expressions.

Dual Problem {#sec_dual_type_I_individual}
------------

By dualizing (\[constraint\_t\_k\]), (\[constraint\_source\_power\_consumption\]), (\[constraint\_relay\_power\_consumption\]), (\[Louveaux\_relay\_condition\]), letting ${\bm t}$ and ${\bm \rho}$ be the matrices of $t_{k,m}$ and $\rho_{k,m}$, respectively, and applying continuous relaxation to $t_{k,m}$’s as in Section \[primal\_total\], we have the following Lagrangian $$\label{Lagrangian_individual_OK_typeI}
\begin{aligned}
L({\bm p},{\bm t},\mu_{S},\mu_{R}, {\bm \alpha}, {\bm \rho})=&\sum_{k=1}^M\sum_{m=1}^M~t_{k,m}\frac{w_{k}}{2}\log\left(1+a_{k,m}\frac{p_{k,m}}{t_{k,m}}\right)\\
&+\mu_{S}\left(P_{S}-\sum_{k=1}^M\sum_{m=1}^M~c^{S}_{k,m}~p_{k,m}\right)\\
&+\mu_{R}\left(P_{R}-\sum_{k=1}^M\sum_{m=1}^M~c^{R}_{k,m}~p_{k,m}\right)\\
&+\sum_{m=1}^M\alpha_m\left(1-\sum_{k=1}^M~t_{k,m}\right)\\
&+\sum_{(k,m) \in {\cal S}_R}\rho_{k,m}\left(a^{SR}_{k}p^{S}_{k,m}-a^{SD}_{k}p^{S}_{k,m}-a^{RD}_{m}p^{R}_{k,m}\right),
\end{aligned}$$ where $$\label{Eq_ECG_individual}
a_{k,m}=\left\{
\begin{aligned}
&\frac{a^{SR}_{k}a^{RD}_{m}}{a^{SR}_{k}+a^{RD}_{m}-a^{SD}_{k}},&&\text{when }a^{SR}_{k}>a^{SD}_{k} \text{ and } a^{RD}_{m}\geq~a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}\\
&a^{SD}_{k},&&\,\,\,\text{otherwise}
\end{aligned}
\right.$$ $$\label{source_power_ratio_individual}
c^{S}_{k,m}=\left\{
\begin{aligned}
&\frac{a^{RD}_{m}}{a^{SR}_{k}+a^{RD}_{m}-a^{SD}_{k}},&&\text{when }a^{SR}_{k}>a^{SD}_{k} \text{ and } a^{RD}_{m}\geq~a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}\\
&1,&&\,\,\,\text{otherwise}
\end{aligned}
\right.$$ $$\label{relay_power_ratio_individual}
c^{R}_{k,m}=\left\{
\begin{aligned}
&\frac{a^{SR}_{k}-a^{SD}_{k}}{a^{SR}_{k}+a^{RD}_{m}-a^{SD}_{k}},&&\text{when }a^{SR}_{k}>a^{SD}_{k} \text{ and } a^{RD}_{m}\geq~a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}\\
&0,&&\,\,\,\text{otherwise}
\end{aligned}
\right.$$ are the equivalent channel gain, the portions of $p_{k,m}$ distributed to source power and relay power, respectively, for the two modes specified in the conditions. Similar to (\[objective\_dual\]), the dual problem associated with (\[Lagrangian\_individual\_OK\_typeI\]) can be expressed as $$\label{objective_dual_typeI_indivudual}
\min_{\mu_{S},\mu_{R}, {\bm \alpha}} ~h(\mu_{S},\mu_{R}, {\bm \alpha})
~~\text{s.t.}~~ \mu_{S}\geq 0, ~\mu_{R}\geq 0$$ with $$\label{P_Lagrange_typeI_indivudial}
h(\mu_{S},\mu_{R}, {\bm \alpha})=
\max_{{\bm p},{\bm t},{\bm \rho}} ~L({\bm p},{\bm t},\mu_{S},\mu_{R}, {\bm \alpha}, {\bm \rho})
~~\text{s.t.}~~ (\ref{constraint_t_m}), (\ref{constraint_power_0}), (\ref{constraint_t_0}).$$ Note that the source and relay power distribution (\[source\_power\_ratio\_individual\]), (\[relay\_power\_ratio\_individual\]) satisfy the constraint $a^{SR}_{k}p^{S}_{k,m} = a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}$ for the relay mode. Thus the last term in (\[Lagrangian\_individual\_OK\_typeI\]) is always zero. Following the same procedure as in Section \[sec\_dual\_type\_I\_total\] and applying the results in Section \[unified\_rate\_individual\], the optimal power allocation for (\[P\_Lagrange\_typeI\_indivudial\]) can be solved as $$\label{optimal power_typeI_individual}
p_{k,m}^\ast=t_{k,m}\left[\frac{w_{k}}{2(c^{S}_{k,m}\mu_{S}+c^{R}_{k,m}\mu_{R})}-\frac{1}{a_{k,m}}\right]^+.$$ The optimal $t_{k,m}$ can be solved as $$\begin{aligned}
\label{optimal_t_typeI_individual}
t_{k,m}^\ast=&\left\{
\begin{aligned}
&1,\text{ }m=\arg\max_{m=1,...,M}Z_{k,m}\\
&0,\text{ otherwise}
\end{aligned}
\right., ~~~~\forall k.\end{aligned}$$ where $$\begin{aligned}\label{compute Z}
Z_{k,m}=&\frac{w_{k}}{2}\log\left(1+a_{k,m}\left[\frac{w_{k}}{2(c^{S}_{k,m}\mu_{S}+c^{R}_{k,m}\mu_{R})}-\frac{1}{a_{k,m}}\right]^+\right)-\alpha_m\\
&-\mu_{S}\left(c^{S}_{k,m}\left[\frac{w_{k}}{2(c^{S}_{k,m}\mu_{S}+c^{R}_{k,m}\mu_{R})}-\frac{1}{a_{k,m}}\right]^+\right)\\
&-\mu_{R}\left(c^{R}_{k,m}\left[\frac{w_{k}}{2(c^{S}_{k,m}\mu_{S}+c^{R}_{k,m}\mu_{R})}-\frac{1}{a_{k,m}}\right]^+\right).
\end{aligned}$$

Since assigning the intermediate mode SP to the relay mode does not change the dual value, we can approach the dual optimal value by the subgradient method. The Lagrange multipliers $\mu_{S}$, $\mu_{R}$, and ${\bm \alpha}$ are updated by $$\label{sub_gradient_typeI individual}
\begin{aligned}
&\mu_{S}^{(i+1)}=\mu_{S}^{(i)}-y_{S}^{(i)}\left(P_{S}-\sum_{k=1}^M\sum_{m=1}^M~c^{S}_{k,m}p_{k,m}^{(i)}\right),\\
&\mu_{R}^{(i+1)}=\mu_{R}^{(i)}-y_{R}^{(i)}\left(P_{R}-\sum_{k=1}^M\sum_{m=1}^M~c^{R}_{k,m}p_{k,m}^{(i)}\right),\\
&\alpha_m^{(i+1)}=\alpha_m^{(i)}-z^{(i)}\left(1-\sum_{k=1}^M~t_{k,m}^{(i)}\right)\text{, }m=1,...,M,
\end{aligned}$$ where $y^{(i)}_S$, $y^{(i)}_R$ and $z^{(i)}$ are the sequences of step sizes designed properly. When the optimal subcarrier pairing and power allocation do not include an intermediate mode SP, (\[sub\_gradient\_typeI individual\]) will converge to the optimal values. However, when an intermediate mode SP is present in the optimal solution, (\[sub\_gradient\_typeI individual\]) may oscillate around the optimal values. Specifically, due to assigning the intermediate mode SP to the relay mode with power allocation (\[optimal power\_typeI\_individual\]), the relay power for that SP is increased, while the source power is decreased, to make (\[Louveaux\_relay\_condition\]) satisfied with equality instead of strict inequality. Thus, even when $\mu_S$ and $\mu_R$ are already at their optimal, the total source power consumption will be smaller than the source power constraint, and the total relay power consumption will be larger than the relay power constraint. This will result in $\mu_S$ decreased and $\mu_R$ increased in the next iteration. Then $\mu_R/\mu_S$ will be increased, and the intermediate mode SP may fall in the direct-link mode according to (\[mode\_conditions\_individual\]). Similarly, this will make $\mu_R/\mu_S$ decreased, and the intermediate mode SP may fall in the relay mode in the next iteration. As a result, (\[sub\_gradient\_typeI individual\]) oscillates. Similar oscillation was also observed in [@relay_DF_individual_power_constraint]. Thus, like in [@relay_DF_individual_power_constraint Section 3.2], the zero-crossing of the difference between the total source power consumption and the source power constraint can be used to determine the optimal $\mu_R/\mu_S$ and the corresponding mode classification and power allocation. However, due to the issues discussed in Section \[Sec\_achieave\_feasible\], we have found that the optimal zero-crossing is very difficult to trace when subcarrier pairing, mode classification and power allocation are updated at the same time. In the algorithm given in Table \[Table\_algo\_obtain\_feasible\_typeI\_individual\], similar to Table \[Table\_algo\_obtain\_feasible\_typeI\], the amendment algorithm is used to obtain a feasible pairing scheme when the subgradient method converges to a ceratin degree. With diminishing step sizes, we found that the subgradient method will eventually be stuck at assigning the intermediate mode SP (if it exists in the optimal solution) to either the direct-link mode or the relay mode. In both cases, the obtained subcarrier pairing scheme is near optimal. With fixed subcarrier pairing, and $\mu_R/\mu_S$ given by the amendment algorithm which is already very close to the optimal, the zero-crossing method in [@relay_DF_individual_power_constraint Section 3.2] can be used to quickly obtain the optimal $\mu_R/\mu_S$. Then the corresponding mode classification and power allocation can be done according to (\[mode\_conditions\_individual\]) and (\[Louveaux\_power\_allocation\]), respectively.

The algorithm in Table \[Table\_algo\_obtain\_feasible\_typeI\_individual\] has the same order of complexity as that of the algorithm in Table \[Table\_algo\_obtain\_feasible\_typeI\]. Through simulation, we have also found that the duality gap for this problem approaches zero when the number of subcarriers is reasonably large.

Weighted Sum Rate Maximization with Extra Direct-Link Transmission {#sec_maximization_total_extra_direct}
==================================================================

In the previous sections, only the relay can transmit in the second time slot. Therefore, for the SPs operating in the direct-link mode, the second time slot is not used. It is possible to allow the source to transmit extra messages in the second time slot on these idle subcarriers. We consider this modified system with both total and individual power constraints.

Total Power Constraint {#sec_extraSD_total}
----------------------

Under the total power constraint, the achievable weighted sum rate for SP $(k,m)$ for this system is $$\label{Eq_pair_rate_typeII}
R_{k,m}=\left\{
\begin{aligned}
&\frac{w_{k}}{2}\log\left(1+a^{SD}_{k}p^{S}_{k,m}\right)+\frac{w_{m}}{2}\log\left(1+a^{SD}_{m}q^{S}_{k,m}\right),&\text{direct-link mode}\\
&\frac{w_{k}}{2}\min\left\{\log\left(1+a^{SR}_{k}p^{S}_{k,m}\right),\; \log\left(1+a^{SD}_{k}p^{S}_{k,m}+a^{RD}_{m}p^{R}_{k,m}\right)\right\}, &\text{relay mode},\\
\end{aligned}
\right.$$ where $p^{S}_{k,m}$, $p^{R}_{k,m}$, and $q^{S}_{k,m}$ represent the source power in the first time slot, relay power in the second time slot, and source power in the second time slot, respectively. By comparing the achievable weighted rate for these two modes, we find that the condition for using the relay depends not only on the channel gains but also on the power allocation. Thus we introduce an additional indicator $s_{k,m}$ related to the use of the relay as a variable to be jointly optimized. When $s_{k,m}=1$, the relay is used for SP $(k,m)$. When $s_{k,m}=0$, the relay is not used. In addition, we again make continuous relaxation for the indicators and the same adjustment to the sum rate function. The relaxed weighted sum rate maximization problem is expressed as follows $$\begin{aligned}
\label{objective_Rate_II_relaxed}
\max_{{\bm p},{\bm s},{\bm t}}\text{ }
&\frac{1}{2}\sum^M_{k=1}\sum^M_{m=1}t_{k,m}~\left\{s_{k,m}w_{k}\log\left(1+a_{k,m}\frac{p_{k,m,1}}{t_{k,m}s_{k,m}}\right)\right.\notag\\
&+(1-s_{k,m})\left[w_{k}\log\left(1+a^{SD}_{k}\frac{p_{k,m,2}}{t_{k,m}(1-s_{k,m})}\right)\right.\notag\\
&\left.\left.+w_{m}\log\left(1+a^{SD}_{m}\frac{p_{k,m,3}}{t_{k,m}(1-s_{k,m})}\right)\right]\right\}
\\
\text{s.t.}\text{ }&(\ref{constraint_t_k}), (\ref{constraint_t_m}), (\ref{constraint_t_0})
\notag\\
\label{constraint_power_k,m,r}
&\sum^M_{k=1}\sum^M_{m=1}\sum^3_{r=1}p_{k,m,r}\leq P
\\
\label{constraint_power_k,m,r_0}
&p_{k,m,r}\geq 0,\forall k, m, r
\\
\label{constraint_s_1_0}
&0\leq s_{k,m}\leq 1,\forall k, m,\end{aligned}$$ where $p_{k,m,1}$ and $a_{k,m}$ are the sum power and equivalent channel gain, respectively, of the relay mode SP $(k,m)$ taking the form of the relay mode expressions in (\[power\_ratio\]) and (\[Eq\_ECG\]). $p_{k,m,2}$ and $p_{k,m,3}$ are the powers used by the direct-link mode SP $(k,m)$ in the first and second time slots, respectively. ${\bm p}\in \mathds{R}_+^{M\times M\times3}$, ${\bm t}\in \mathds{R}_+^{M\times M}$, and ${\bm s}\in \mathds{R}_+^{M\times M}$ are the matrices of $p_{k,m,r}$, $t_{k,m}$, and $s_{k,m}$, respectively. $P$ is the total power constraint. Similarly, by dualizing constraints (\[constraint\_t\_k\]) and (\[constraint\_power\_k,m,r\]), we obtain the Lagrangian as $$\label{Lagrangian_typeII}
\begin{aligned}
L({\bm p},{\bm t},{\bm s},\mu, {\bm \alpha})=&\frac{1}{2}\sum^M_{k=1}\sum^M_{m=1}t_{k,m}~\left\{s_{k,m}w_{k}\log\left(1+a_{k,m}\frac{p_{k,m,1}}{t_{k,m}s_{k,m}}\right)\right.\\
&+(1-s_{k,m})\left[w_{k}\log\left(1+a^{SD}_{k}\frac{p_{k,m,2}}{t_{k,m}(1-s_{k,m})}\right)\right.\\
&\left.\left.+w_{m}\log\left(1+a^{SD}_{m}\frac{p_{k,m,3}}{t_{k,m}(1-s_{k,m})}\right)\right]\right\}\\
&+\mu\left(P-\sum_{k=1}^M\sum_{m=1}^M\sum_{r=1}^3~p_{k,m,r}\right)+\sum_{m=1}^M\alpha_m\left(1-\sum_{k=1}^M~t_{k,m}\right),
\end{aligned}$$ where $\mu\in \mathds{R}_+$ and ${\bm \alpha}\in\mathds{R}^M$ are the dual variables. Then the dual objective function is computed as $$\label{P_Lagrange_typeII}
h(\mu,{\bm \alpha})=
\max_{{\bm p},{\bm t},{\bm s}} ~L({\bm p},{\bm t},{\bm s},\mu,{\bm \alpha})
~~\text{s.t.}~~ (\ref{constraint_t_m}), (\ref{constraint_t_0}), (\ref{constraint_power_k,m,r_0}), (\ref{constraint_s_1_0}).$$ The dual problem is given as $$\label{objective_dual_typeII}
\min_{\mu,{\bm \alpha}} ~h(\mu, {\bm \alpha})
~~\text{s.t.}~~ \mu\geq 0.$$ The solution to (\[P\_Lagrange\_typeII\]) is $$\label{optimal power_typeII}
\begin{aligned}
&p_{k,m,1}^\ast=t_{k,m}s_{k,m}\left[\frac{w_{k}}{2\mu}-\frac{1}{a_{k,m}}\right]^+,\\
&p_{k,m,2}^\ast=t_{k,m}(1-s_{k,m})\left[\frac{w_{k}}{2\mu}-\frac{1}{a^{SD}_{k}}\right]^+,\\
&p_{k,m,3}^\ast=t_{k,m}(1-s_{k,m})\left[\frac{w_{m}}{2\mu}-\frac{1}{a^{SD}_{m}}\right]^+,
\end{aligned}$$ $$\label{Eq_s_choose}
s^\ast_{k,m}=\left\{
\begin{aligned}
1&,\text{ }a^{SR}_{k}>a^{SD}_{k}\text{ and }Y^{R}_{k,m}>Y^{D}_{k,m}\\
0&,\text{ otherwise},
\end{aligned}
\right.$$ where $$\label{compute Y_R}
Y^{R}_{k,m}=\frac{w_{k}}{2}\log\left(1+a_{k,m}\left[\frac{w_{k}}{2\mu}-\frac{1}{a_{k,m}}\right]^+\right)-\mu\left[\frac{w_{k}}{2\mu}-\frac{1}{a_{k,m}}\right]^+\\$$ $$\label{compute Y_D}
\begin{aligned}
Y^{D}_{k,m}=&\frac{w_{k}}{2}\log\left(1+a^{SD}_{k}\left[\frac{w_{k}}{2\mu}-\frac{1}{a^{SD}_{k}}\right]^+\right)\\
&+\frac{w_{m}}{2}\log\left(1+a^{SD}_{m}\left[\frac{w_{m}}{2\mu}-\frac{1}{a^{SD}_{m}}\right]^+\right)\\
&-\mu\left(\left[\frac{w_{k}}{2\mu}-\frac{1}{a^{SD}_{k}}\right]^+~+\left[\frac{w_{m}}{2\mu}-\frac{1}{a^{SD}_{m}}\right]^+\right)\\
\end{aligned}$$ are the SP $(k,m)$’s contribution to the Lagrangian when it is in the relay mode or the direct-link mode, respectively. The condition $a^{SR}_{k}>a^{SD}_{k}$ in (\[Eq\_s\_choose\]) is necessary. The reason is that the value of $Y^{R}_{k,m}$ is meaningless when $a^{SR}_{k}<a^{SD}_{k}$, since it is impossible to make the relay receive more information than the destination. The $s^\ast_{k,m}$ tells us whether it is better to use relay for the SP ($k,m$).

The SP selection variable is given as follows $$\label{optimal_t_typeII}
t_{k,m}^\ast=\left\{
\begin{aligned}
&1,\text{ }m=\arg\max_{m=1,...,M}Y_{k,m}\\
&0,\text{ }\text{otherwise}
\end{aligned}
\right., ~~~~\forall k$$ where $$\label{compute Y}
\begin{aligned}
Y_{k,m}=s^\ast_{k,m}Y^{R}_{k,m}+(1-s^\ast_{k,m})Y^{D}_{k,m}-\alpha_m.
\end{aligned}$$ Again, the dual optimal value is reached by the subgradient method. The Lagrange multipliers $\mu$ and ${\bm \alpha}$ are updated by $$\label{sub_gradient_typeII_total}
\begin{aligned}
&\mu^{(i+1)}=\mu^{(i)}-y^{(i)}\left(P-\sum_{k=1}^M\sum_{m=1}^M\sum_{r=1}^3~p^{(i)}_{k,m,r}\right),\\
&\alpha_m^{(i+1)}=\alpha_m^{(i)}-z^{(i)}\left(1-\sum_{k=1}^M~t_{k,m}^{(i)}\right)\text{, }m=1,...,M,
\end{aligned}$$ where $y^{(i)}$ and $z^{(i)}$ are the sequences of step sizes designed properly.

The algorithm to obtain feasible solutions is given in Table \[Table\_algo\_obtain\_feasible\_typeII\] where $s_{k,m}$’s found in an iteration are directly used, together with the subcarrier pairing scheme ${\bm t}$ obtained by the amendment algorithm, to compute the power allocation and weighted sum rate. Doing so is suboptimal, as $s_{k,m}$ in fact depends on the power allocation. However, this saves the complexity involved in joint optimization of $s_{k,m}$ and power allocation given fixed subcarrier pairing. The algorithm in Table \[Table\_algo\_obtain\_feasible\_typeII\] also has the same order of complexity as that of the algorithm in Table \[Table\_algo\_obtain\_feasible\_typeI\]. We have found that the duality gap for this problem is virtually zero when the number of subcarriers is reasonably large.

Individual Power Constraints {#sec_extraSD_individual}
----------------------------

With individual power constraints for the source and the relay, the problem can be solved by combining the results in Section \[sec\_maximization\_individual\] and Section \[sec\_extraSD\_total\] with some crucial modifications. Due to limited space, we will discuss only these crucial points.

As in Section \[sec\_maximization\_individual\], in addition to the direct-link mode and the relay mode, there may also be an intermediate mode in which the relay receives more information than the destination, and (\[Louveaux\_relay\_condition\]) is satisfied with strict inequality. On the other hand, the relay mode should satisfy (\[Louveaux\_relay\_condition\]) with equality. Note that given the same power, the rate of the direct-link mode in (\[Eq\_pair\_rate\_typeII\]) with extra second-slot SD transmission should be no less than the rate of the direct-link mode in (\[Eq\_pair\_rate\_typeI\]). This is because the latter is a special case of the former with the second time slot allocated zero power. Therefore, the necessary condition $a^{SR}_{k}>a^{SD}_{k}$ in (\[mode\_conditions\_individual\]) for the relay to be active (in both the relay and the intermediate modes) is also necessary in this case. The second necessary condition $a^{RD}_{m}=a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}$ in (\[mode\_conditions\_individual\]) for a SP to be in the intermediate mode, as derived in [@relay_DF_individual_power_constraint], is directly related to having (\[Louveaux\_relay\_condition\]) as a strict inequality. Thus it is also necessary in this case. The second condition $a^{RD}_{m}<a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}$ in (\[mode\_conditions\_individual\]) for selecting the direct-link mode over the relay mode was derived by comparing the achievable rates of the direct-link mode and the relay mode when they have the same power cost in the Lagragian (\[Louveaux\_Lagrange\]) (see the discussion after (\[mode\_conditions\_individual\]) and [@Vandendorpe_J]). With the extra second-slot SD transmission that can improve the rate for the direct-link mode, this condition may change. In fact, with the extra second-slot SD transmission, the direct-link mode may possibly be selected even when $a^{RD}_{m}>a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}$. For the special case with fixed $(k,k)$ subcarrier paring, [@Vandendorpe_J] has derived the exact condition which also depends on the allocated power. In our case, the subcarrier paring is variable and may not be the trivial $(k,k)$ pairing. Due to this reason and different weighting factors in the rate of the direct-link mode (\[Eq\_pair\_rate\_typeII\]), the exact condition based on having the same power cost is complicated and dependent also on the weighting factors. However, we may simplify the condition by comparing the contributions of the direct-link mode and the relay mode to the Lagrangian. This approach is similar to using (\[Eq\_s\_choose\]) to select modes to maximize the Lagrangian (\[P\_Lagrange\_typeII\]).

The fact that the direct-link mode may also be selected when $a^{RD}_{m}>a^{SD}_{k}\frac{\mu_{R}}{\mu_{S}}$ implies that the region for the intermediate mode to occur may be encompassed by the region for selecting the direct-link mode. That is, the intermediate mode may no longer exist, except in the special situation where the optimal power allocation for a direct-link mode SP results in zero power for the second-slot SD transmission. For a SP with this property, there will be no second-slot SD transmission if the direct-link mode is selected. Then the situation becomes the same as in Section \[sec\_maximization\_individual\]. Thus (\[mode\_conditions\_individual\]) can be used to select modes, and the unified rate formulation discussed in Section \[unified\_rate\_individual\] can be applied with the intermediate mode SP assigned to the relay mode.

In summary, we can assume that there are only the direct-link mode and the relay mode, and apply the results in Section \[sec\_extraSD\_total\] with the following changes. The relay mode power allocation $p_{k,m,1}^\ast$ in (\[optimal power\_typeII\]) takes the expression of the right-hand side (RHS) of (\[optimal power\_typeI\_individual\]) multiplied by $s_{k,m}$, where $c_{k,m}^S$ and $c_{k,m}^R$ are the portions of $p_{k,m,1}^\ast$ distributed to source power and relay power defined by the relay mode expressions in (\[source\_power\_ratio\_individual\]) and (\[relay\_power\_ratio\_individual\]), respectively. The RHS of (\[compute Y\_R\]) is replaced by the RHS of (\[compute Z\]) with $-\alpha_m$ removed. $\mu$ in (\[compute Y\_D\]) is replaced by $\mu_S$. In each iteration, $\mu_S$, $\mu_R$ and ${\bm \alpha}$ are updated as in (\[sub\_gradient\_typeI individual\]) using the power allocation computed in (\[optimal power\_typeII\]) ($p_{k,m,1}^\ast$ computed by the RHS of (\[optimal power\_typeI\_individual\]) multiplied by $s_{k,m}$). If there is an intermediate mode SP in the optimal solution, it must belong to the situation where the conditions (\[mode\_conditions\_individual\]) are applicable. Then, like in Section \[sec\_dual\_type\_I\_individual\], the zero-crossing method in [@relay_DF_individual_power_constraint Section 3.2] can be used to obtain the optimal $\mu_R/\mu_S$. The corresponding mode classification and power allocation can then be done accordingly.

Simulation Results {#Sec_simulation}
==================

This section provides the simulation results for the rates obtained by the proposed algorithms, and the dual optimum values which serve as the performance upper bounds. The performances with fixed subcarrier pairing and with the SCP proposed in [@relay_eq_channel_gain] are also presented for comparison. Note that the original SCP in [@relay_eq_channel_gain] considered only the unweighted sum rate. It first sorts the subcarriers of the SR link and the RD link, respectively, according to their normalized channel gains, then pairs the SR subcarrier with the RD subcarrier having the same rank. For weighted sum rate, according to (\[impact\_weighting\]) and the discussion right after it, we modify the SCP such that $w_{k}a^{SR}_{k}$ and $a^{RD}_{m}$ are sorted first. Then the SR subcarrier and the RD subcarrier with the same rank are paired. The RD link channel gains are not weighted for the reason that we do not know the actual subcarrier pairing scheme in advance.

The channels of different links are assumed to be independent of one another. The channels of the subcarriers are independent and identically distributed (i.i.d.) Rician fading channels with $K$-factor $=1$. They are assumed constant within each two-slot period, and varying independently from one period to another. The AWGN variance is assumed to be one. The total power constraint is set as $P=5$. As for the cases with individual power constraints, the source power constraint is $P_S=4$ and the relay power constraint is $P_R=1$. These constraints are set with the practical consideration that the relay usually plays the role of assisting the transmission and/or extending the coverage, and has a smaller power than the source. In addition, when the relay is allowed more power and the achievable rate becomes limited by the source power constraint, some of the relay power will not be used. Setting $P_S=4$ and $P_R=1$ reduces the occurrence of this situation and makes the comparison with the total power constrained case fairer. For all cases, the SD link is present, and the destination performs MRC whenever the relay is used. The SCP schemes first establish subcarrier pairing using SCP. Then, in the total power constrained cases (including the case with extra direct-link transmission), (\[relay\_condition\_total\]) is used as the condition to use relay. In the individual power constrained case without extra direct-link transmission, the method in [@relay_DF_individual_power_constraint] is used for mode classification and power allocation. For the individual power constrained case with extra direct-link transmission, the method in [@relay_DF_individual_power_constraint] cannot be used because the optimal mode classification conditions are no longer (\[mode\_conditions\_individual\]). Naively using (\[mode\_conditions\_individual\]) and (\[Louveaux\_power\_allocation\]) may result in invalid power allocation as they are not the solutions in this case, and will affect the $\mu_S$, $\mu_R$ values through the iterations. On the other hand, modifying the method in [@Vandendorpe_J] to accommodate weighted rates is tedious. Thus, the algorithm discussed in Section \[sec\_extraSD\_individual\] is used with fixed subcarrier pairing from the SCP. The fixed pairing schemes use the same mode classification and power allocation procedures as that of the SCP schemes. In Figs. \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\], \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\_extra\], \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\], \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\_extra\], \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\] and \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\_extra\], the unweighted sum rate is considered. That is, the all-one weighting factor is used. In Figs. \[Fig\_WSR\_channel\_3\_1\_3\_weight\], \[Fig\_WSR\_channel\_5\_1\_1\_weight\] and \[Fig\_WSR\_channel\_1\_1\_5\_weight\], the weighted sum rate is considered with $w_{k}=1+\frac{k-1}{M-1},\forall k$, which is used only as an example with a concise expression.

For the proposed algorithms, $\mu$, $\mu_R$, $\mu_S$ and $\alpha_m$’s were randomly initialized to be between 0 and 2 for each two-slot period. For each number of subcarriers $(\in \{4, 8, 16, 32, 64\})$, 1000 such two-slot periods were simulated, and the results averaged to avoid favoring certain initial conditions. The step sizes for the subgradient method were all set as $\frac{0.05}{\sqrt{i}}$, where $i$ is the iteration index. In the simulation, we observed that the number of iterations before the amendment algorithm was triggered depends on the number of subcarriers. The number of iterations needed ranged roughly from a few hundreds for small numbers of subcarriers ($<10$) to slightly more than 10000 for 64 subcarriers.

We investigate three system configurations corresponding to different scenarios. In Figs. \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\], \[Fig\_WSR\_channel\_3\_1\_3\_weight\] and \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\_extra\], the mean square channel gains of the SR, SD and RD links are 3, 1, 3, respectively. This corresponds to the situation where the relay is placed between the source and the destination. In Figs. \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\], \[Fig\_WSR\_channel\_5\_1\_1\_weight\] and \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\_extra\], the mean square channel gains of the SR, SD and RD links are 5, 1 and 1, respectively, which means that the relay is close to the source. In Figs. \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\], \[Fig\_WSR\_channel\_1\_1\_5\_weight\] and \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\_extra\], the mean square channel gains of the SR, SD and RD links are 1, 1 and 5, respectively, which means that the relay is close to the destination. In these figures, we find that, in all cases, the rates obtained by the proposed algorithms are almost equal to the corresponding dual optimum values. This validates the arguments in Section \[duality\_gap\_total\], Section \[sec\_dual\_type\_I\_individual\] and Section \[sec\_extraSD\_total\] that the duality gap is virtually zero when the number of subcarriers is reasonably large. Even when the number of subcarriers is 4, the duality gap is hardly noticeable from the averaged results, because it is zero with a very high probability. These results also show that the proposed algorithms can almost achieve the optimal weighted sum rates. There are some other general trends that can be observed from these figures. One of them is that fixed subcarrier pairing incurs a significant performance loss. In addition, the weighted and unweighted sum rates increase with the number of subcarriers due to frequency diversity and more flexibility in pairing. As to the performance under different constraints, the performance under total power constraint is better than the performance under individual power constraints, due to the flexibility in power allocation. By comparing Figs. \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\] and \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\_extra\], \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\] and \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\_extra\], \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\] and \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\_extra\], it is clear that extra direct-link transmission always improves the performance.

The SCP was proved in [@relay_AF_DF_eq_channel_gain][@Li_AFDF_OFDM] to be optimal for the unweighted system without the SD link under the total power constraint. When the SD link is present and/or when weighted sum rate is considered, the performance of the SCP depends on the link qualities. The SCP almost achieves the optimal unweighted sum rate for the cases with total power constraint and no extra direct-link transmission in Fig. \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\] and Fig. \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\], but becomes noticeably worse than the optimal in Fig. \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\]. For the scenario in Fig. \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\], this is reasonable because the SD link is relatively weak compared to the other two links. Thus the direct-link mode is rarely used, and the SCP is nearly optimal for the relay-mode SPs given that their SD subcarriers are weak. For the scenario in Fig. \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\], the RD link is the strongest and seldom becomes the bottleneck for mode selection. For the SCP as well as the proposed algorithm, mode selection is mainly determined by the SR and SD links. For the direct-link mode SPs, the SCP and the proposed algorithm have similar performances. For the relay mode SPs, the SCP is nearly optimal because the SD link is the weakest among the three links. Overall, the SCP has a very similar performance to that of the proposed algorithm which is almost optimal. As to the case of Fig. \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\], we can see that since the SR link is much stronger than the SD link, the condition for using relay (\[relay\_condition\_total\]) is dominated by the relation between the channel gains of the SD and the RD links. However, the SCP does not consider the SD link in establishing subcarrier pairing. As a result, the SCP is almost equivalent to random pairing in terms of optimizing the mode selection and sum rate. Thus its sum rate is smaller than that of the proposed algorithm. The SCP is still better than fixed pairing because it helps the SPs that are in the relay mode.

For the individual power constrained cases, or when weighted sum rate is considered, as shown in Figs. \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\], \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\], and \[Fig\_WSR\_channel\_3\_1\_3\_weight\], \[Fig\_WSR\_channel\_5\_1\_1\_weight\], the gaps between the SCP and the proposed algorithms become larger. This is due to the mismatches between the SCP and these scenarios. To show that our modification to the original SCP is meaningful, we show the performance of the original (unweighted) SCP together with that of the “weighted SCP" in Fig. \[Fig\_WSR\_channel\_3\_1\_3\_weight\] and Fig. \[Fig\_WSR\_channel\_5\_1\_1\_weight\]. These two figures clearly show that the original SCP is not suitable when weighted sum rate is considered. The performance gap between the “weighted SCP" and the proposed algorithm in Fig. \[Fig\_WSR\_channel\_5\_1\_1\_weight\] is due to the aforementioned “random pairing" effect of the SCP (as in the total power constrained case in Fig. \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\]). However, these trends do not appear in Fig. \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\] and Fig. \[Fig\_WSR\_channel\_1\_1\_5\_weight\]. For Fig. \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\], this is because the strong RD link makes the sum rate not limited by the low relay power constraint. Therefore, for the SCP, the situation is very similar to that with the total power constraint. As a result, the SCP is almost optimal. For Fig. \[Fig\_WSR\_channel\_1\_1\_5\_weight\], the strong RD link makes mode selection dependent almost only on the channel gains of the SR and SD links. Thus, mode selection is almost independent of the pairing scheme and weighting factors. For the source subcarriers that have relatively lower SR gains and are in the direct-link mode, all schemes yield similar performances. On the other hand, for the subcarriers in the relay mode, pairing better RD subcarriers with SR subcarriers having higher weighted channel gains can improve the weighted sum rate. Both the original SCP and the weighted SCP can do that for the SR subcarriers that are strong enough. Thus they both perform well and almost optimally.

With possible extra direct-link transmission, the SCP is worse than the proposed algorithm for not considering the benefits of the extra direct-link transmission (such as more diversity from the additional independent channels, and more flexibility in water-filling) in subcarrier pairing and mode selection. Under the total power constraint, we find that the SCP is similar and even slightly worse than fixed pairing in Fig. \[Fig\_WSR\_channel\_5\_1\_1\_noweight\_total\_individual\_extra\] and Fig. \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\_extra\]. This is because, without considering the possible extra direct-link transmission, the SCP’s pairing of strong SR subcarrier with strong RD subcarrier tends to satisfy (\[relay\_condition\_total\]) more than fixed pairing, and make more SPs use the relay. Thus it loses the opportunities to transmit more messages with the extra direct-link. This phenomenon does not appear in Fig. \[Fig\_WSR\_channel\_3\_1\_3\_noweight\_total\_individual\_extra\], for which the benefits of the extra direct-link transmission are not significant due to the weak SD link. Under individual power constraints, both the SCP and the fixed pairing schemes use the algorithm in Section \[sec\_extraSD\_individual\] for optimal joint mode selection and power allocation. The SCP always performs better than fixed pairing due to its better subcarrier pairing. In Fig. \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\_extra\], the advantage of the SCP over fixed pairing is smaller than in Fig. \[Fig\_WSR\_channel\_1\_1\_5\_noweight\_total\_individual\] because the optimal mode selection assigns more SPs to the direct-link mode for which better SR-RD subcarrier pairing does not improve the rate.

Conclusion {#Sec_conclusion}
==========

In this paper we investigated OFDM point to point transmission, enhanced with a DF relay. We jointly optimized subcarrier pairing and power allocation to maximize the weighted sum rate with consideration of the source-destination link and destination combining. To the best of our knowledge, this problem has not been solved before. Both total power constraint and individual power constraints for the source and the relay were considered. The system that allows additional messages to be transmitted on the idle subcarriers not used by the relay, in the source-destination link in the second time slot, was also investigated. We solved the optimization problems by using some special properties of the systems, as well the continuous relaxation and the dual method. The subgradient method was adopted to find the Lagrange multipliers which also helped us to find the primal feasible solutions. Based on the optimization results, algorithms with tractable complexities to obtain feasible subcarrier pairing schemes and the corresponding power allocations were proposed. Simulation results showed that the proposed algorithms can achieve nearly optimal weighted sum rates, and outperform the method proposed in [@relay_eq_channel_gain] under various channel conditions.

![Channel model for subcarrier pair $(k,m)$.[]{data-label="Fig_channel_model"}](channel_model.eps){width="55.00000%"}

![Concavity of rate versus power constraint for systems with 2 and 8 subcarriers.[]{data-label="Fig_rate_power_concave"}](rate_power_2_8.eps){width="80.00000%"}

![Unweighted sum rates for the systems with $\mathbb{E}[|h^{SR}|^2]=3$, $\mathbb{E}[|h^{SD}|^2]=1$ and $\mathbb{E}[|h^{RD}|^2]=3$.[]{data-label="Fig_WSR_channel_3_1_3_noweight_total_individual"}](channel_3_1_3_noWeighting_total_individual.eps){width="77.00000%"}

![Weighted sum rates for the systems with total power constraint, and $\mathbb{E}[|h^{SR}|^2]=3$, $\mathbb{E}[|h^{SD}|^2]=1$, $\mathbb{E}[|h^{RD}|^2]=3$.[]{data-label="Fig_WSR_channel_3_1_3_weight"}](channel_3_1_3_Weighting_total.eps){width="77.00000%"}

![Unweighted sum rates for the systems with extra direct-link transmission, and $\mathbb{E}[|h^{SR}|^2]=3$, $\mathbb{E}[|h^{SD}|^2]=1$, $\mathbb{E}[|h^{RD}|^2]=3$.[]{data-label="Fig_WSR_channel_3_1_3_noweight_total_individual_extra"}](channel_3_1_3_noWeighting_total_individual_extra.eps){width="77.00000%"}

![Unweighted sum rates for the systems with $\mathbb{E}[|h^{SR}|^2]=5$, $\mathbb{E}[|h^{SD}|^2]=1$ and $\mathbb{E}[|h^{RD}|^2]=1$.[]{data-label="Fig_WSR_channel_5_1_1_noweight_total_individual"}](channel_5_1_1_noWeighting_total_individual.eps){width="77.00000%"}

![Weighted sum rates for the systems with total power constraint, and $\mathbb{E}[|h^{SR}|^2]=5$, $\mathbb{E}[|h^{SD}|^2]=1$, $\mathbb{E}[|h^{RD}|^2]=1$.[]{data-label="Fig_WSR_channel_5_1_1_weight"}](channel_5_1_1_Weighting_total.eps){width="77.00000%"}

![Unweighted sum rates for the systems with extra direct-link transmission, and $\mathbb{E}[|h^{SR}|^2]=5$, $\mathbb{E}[|h^{SD}|^2]=1$, $\mathbb{E}[|h^{RD}|^2]=1$.[]{data-label="Fig_WSR_channel_5_1_1_noweight_total_individual_extra"}](channel_5_1_1_noWeighting_total_individual_extra.eps){width="77.00000%"}

![Unweighted sum rates for the systems with $\mathbb{E}[|h^{SR}|^2]=1$, $\mathbb{E}[|h^{SD}|^2]=1$ and $\mathbb{E}[|h^{RD}|^2]=5$.[]{data-label="Fig_WSR_channel_1_1_5_noweight_total_individual"}](channel_1_1_5_noWeighting_total_individual.eps){width="77.00000%"}

![Weighted sum rates for the systems with total power constraint, and $\mathbb{E}[|h^{SR}|^2]=1$, $\mathbb{E}[|h^{SD}|^2]=1$, $\mathbb{E}[|h^{RD}|^2]=5$.[]{data-label="Fig_WSR_channel_1_1_5_weight"}](channel_1_1_5_Weighting_total.eps){width="77.00000%"}

![Unweighted sum rates for the systems with extra direct-link transmission, and $\mathbb{E}[|h^{SR}|^2]=1$, $\mathbb{E}[|h^{SD}|^2]=1$, $\mathbb{E}[|h^{RD}|^2]=5$.[]{data-label="Fig_WSR_channel_1_1_5_noweight_total_individual_extra"}](channel_1_1_5_noWeighting_total_individual_extra.eps){width="77.00000%"}

[lll]{}\
\
&*Compute* $X_{k,m}^{(i)}, \forall k, m$, *using* $\mu^{(i)}$, ${\bm \alpha}^{(i)}$ *in* (\[compute X\])\
&$\textit{Compute }{\bm t}^{(i)}\textit{ using }X_{k,m}^{(i)} \textit{ in } (\ref{optimal_t_typeI})$\
&$\textit{Compute }{\bm p}^{(i)}\textit{ using }\mu^{(i)}, ~{\bm t}^{(i)} \textit{ in }(\ref{optimal power_typeI})$\
&$\textit{Compute }\mu^{(i+1)}, ~{\bm \alpha}^{(i+1)}\textit{ using }\mu^{(i)}, ~{\bm \alpha}^{(i)}, ~{\bm t}^{(i)}, ~{\bm p}^{(i)} \textit{ in }(\ref{sub_gradient_typeI_total})$\
&*If* (amendment = *false*) *and* $\left(\frac{\lvert\mu^{(i+1)}-\mu^{(i)}\rvert}{\lvert \mu^{(i+1)} \rvert}<\epsilon\right)$ *and* $\left(\frac{\lVert{\bm \alpha}^{(i+1)}-{\bm \alpha}^{(i)}\rVert}{\lVert {\bm \alpha}^{(i+1)} \rVert}<\epsilon\right)$\
&amendment = *true*\
&max\_it = $\lfloor 1.1 \times i \rfloor$\
&*End*\
&*If* (amendment = *true*)        *(\*\* amendment algorithm \*\*)*\
&$\hat{{\bm t}} = {\bm t}^{(i)}$, $c_m=\sum_{k=1}^M\hat{t}_{k,m}, \forall m$\
&*For (j = 1 to M)*&\
&*If* $(c_j>1)$,   $s^*=\arg\max_{\left\{s|\hat{t}_{s,j}=1\right\}}X_{s,j}^{(i)}$,   *End*\
&*While* ($c_j>1$)\
&$m^*=\arg\min_{\{m|c_m=0\}}\left|\alpha^{(i)}_j-\alpha^{(i)}_m\right|$\
&$r^*=\arg\max_{\left\{r|\hat{t}_{r,j}=1, ~r\neq s^*\right\}}X_{r,m^*}^{(i)}$\
&$\hat{t}_{r^*,j}=0$,  $\hat{t}_{r^*,m^*}=1$\
&$c_{j}=c_{j}-1, ~c_{m^*}=c_{m^*}+1$\
&*End*\
&*End*\
&*With fixed subcarrier pairing* $\hat{{\bm t}},$ *apply water-filling on the subcarrier pairs with equivalent*\
&  *channel gains in (\[Eq\_ECG\]) to compute power allocation* $\hat{{\bm p}}$ *and the weighted sum rate* $R$ *as in (\[objective\_Rate\_I\_MIP\])*.\
&*If* ($R>$ sum\_rate),   sum\_rate $=R$,  $\check{{\bm t}}=\hat{{\bm t}}$,  $\check{{\bm p}}=\hat{{\bm p}}$,   *End*\
&*End        (\*\* amendment algorithm \*\*)*\
&$i=i+1$\
\

[lll]{}\
\
&*Determine modes for all possible subcarrier pairs, and obtain* $a_{k,m}$, $c^S_{k,m}$ and $c^R_{k,m}$\
&  *by using* $\mu_S^{(i)}$, $\mu_R^{(i)}$ *in* (\[Eq\_ECG\_individual\]), (\[source\_power\_ratio\_individual\]) and (\[relay\_power\_ratio\_individual\])\
&*Compute* $Z_{k,m}^{(i)}, \forall k, m$, *using* $\mu_S^{(i)}$, $\mu_R^{(i)}$, ${\bm \alpha}^{(i)}$, $a_{k,m}$, $c^S_{k,m}$, $c^R_{k,m}$ *in* (\[compute Z\])\
&$\textit{Compute }{\bm t}^{(i)}\textit{ using }Z_{k,m}^{(i)} \textit{ in } (\ref{optimal_t_typeI_individual})$\
&$\textit{Compute }{\bm p}^{(i)}\textit{ using }\mu_S^{(i)}, ~\mu_R^{(i)}, ~{\bm t}^{(i)}, ~a_{k,m}, ~c^S_{k,m}, ~c^R_{k,m} \textit{ in }(\ref{optimal power_typeI_individual})$\
&$\textit{Compute }\mu_S^{(i+1)}, ~\mu_R^{(i+1)}, ~{\bm \alpha}^{(i+1)}\textit{ using }\mu_S^{(i)}, ~\mu_R^{(i)}, ~{\bm \alpha}^{(i)}, ~{\bm t}^{(i)}, ~{\bm p}^{(i)}, ~c^S_{k,m}, ~c^R_{k,m} \textit{ in }(\ref{sub_gradient_typeI individual})$\
&*If* (amendment = *false*) *and* $\left(\frac{\lvert\mu_S^{(i+1)}-\mu_S^{(i)}\rvert}{\lvert \mu_S^{(i+1)} \rvert}<\epsilon\right)$ *and* $\left(\frac{\lvert\mu_R^{(i+1)}-\mu_R^{(i)}\rvert}{\lvert \mu_R^{(i+1)} \rvert}<\epsilon\right)$ *and* $\left(\frac{\lVert {\bm \alpha}^{(i+1)}-{\bm \alpha}^{(i)}\rVert}{\lVert {\bm \alpha}^{(i+1)} \rVert}<\epsilon\right)$\
&amendment = *true*\
&max\_it = $\lfloor 1.1 \times i \rfloor$\
&*End*\
&*If* (amendment = *true*)        *(\*\* amendment algorithm \*\*)*\
&$\hat{{\bm t}} = {\bm t}^{(i)}$, $c_m=\sum_{k=1}^M\hat{t}_{k,m}, \forall m$\
&*For (j = 1 to M)*&\
&*If* $(c_j>1)$,   $s^*=\arg\max_{\left\{s|\hat{t}_{s,j}=1\right\}}Z_{s,j}^{(i)}$,   *End*\
&*While* ($c_j>1$)\
&$m^*=\arg\min_{\{m|c_m=0\}}\left|\alpha^{(i)}_j-\alpha^{(i)}_m\right|$\
&$r^*=\arg\max_{\left\{r|\hat{t}_{r,j}=1, ~r\neq s^*\right\}}Z_{r,m^*}^{(i)}$\
&$\hat{t}_{r^*,j}=0$,  $\hat{t}_{r^*,m^*}=1$\
&$c_{j}=c_{j}-1, ~c_{m^*}=c_{m^*}+1$\
&*End*\
&*End*\
&*With fixed subcarrier pairing* $\hat{{\bm t}},$ *and letting* $\hat{\mu}_S=\mu_S^{(i)}$, $\hat{\mu}_R=\mu_R^{(i)}$, *use the zero-crossing method in [@relay_DF_individual_power_constraint Section 3.2]*\
&  *to update $\hat{\mu}_S$, $\hat{\mu}_R$ to their optimal.*\
&*Use $\hat{\mu}_S$, $\hat{\mu}_R$ in (\[mode\_conditions\_individual\]) and (\[Louveaux\_power\_allocation\]) to obtain mode classification and power allocation* $\hat{{\bm p}}_{S}$, $\hat{{\bm p}}_{R}$,\
&  *and compute the weighted sum rate $R$*.\
&*If* ($R>$ sum\_rate),   sum\_rate $=R$,  $\check{{\bm t}}=\hat{{\bm t}}$,  $\check{{\bm p}}_{S}=\hat{{\bm p}}_{S}$,  $\check{{\bm p}}_{R}=\hat{{\bm p}}_{R}$,   *End*\
&*End        (\*\* amendment algorithm \*\*)*\
&$i=i+1$\
\

[lll]{}\
\
&*Compute* $\left(Y^R_{k,m}\right)^{(i)}, \left(Y^D_{k,m}\right)^{(i)}, ~\forall k, m$, *using* $\mu^{(i)}$ *in* (\[compute Y\_R\]) *and* (\[compute Y\_D\]).\
&$\textit{Obtain }{\bm s}^{(i)}\textit{ using }\left(Y^R_{k,m}\right)^{(i)}, \left(Y^D_{k,m}\right)^{(i)} \textit{ in } (\ref{Eq_s_choose})$\
&*Compute* $Y_{k,m}^{(i)}, ~\forall k, m$, *using* $\left(Y^R_{k,m}\right)^{(i)}$, $\left(Y^D_{k,m}\right)^{(i)}$, ${\bm s}^{(i)}$, ${\bm \alpha}^{(i)}$ *in* (\[compute Y\])\
&$\textit{Compute }{\bm t}^{(i)}\textit{ using }Y_{k,m}^{(i)} \textit{ in } (\ref{optimal_t_typeII})$\
&$\textit{Compute }{\bm p}^{(i)}\textit{ using }\mu^{(i)}, ~{\bm t}^{(i)}, ~{\bm s}^{(i)} \textit{ in }(\ref{optimal power_typeII})$\
&$\textit{Compute }\mu^{(i+1)}, ~{\bm \alpha}^{(i+1)}\textit{ using }\mu^{(i)}, ~{\bm \alpha}^{(i)}, ~{\bm t}^{(i)}, ~{\bm p}^{(i)} \textit{ in }(\ref{sub_gradient_typeII_total})$\
&*If* (amendment = *false*) *and* $\left(\frac{\lvert\mu^{(i+1)}-\mu^{(i)}\rvert}{\lvert \mu^{(i+1)} \rvert}<\epsilon\right)$ *and* $\left(\frac{\lVert {\bm \alpha}^{(i+1)}- {\bm \alpha}^{(i)}\rVert}{\lVert {\bm \alpha}^{(i+1)} \rVert}<\epsilon\right)$\
&amendment = *true*\
&max\_it = $\lfloor 1.1 \times i \rfloor$\
&*End*\
&*If* (amendment = *true*)        *(\*\* amendment algorithm \*\*)*\
&$\hat{{\bm t}} = {\bm t}^{(i)}$, $\hat{{\bm s}} = {\bm s}^{(i)}$, $c_m=\sum_{k=1}^M\hat{t}_{k,m}, \forall m$\
&*For (j = 1 to M)*&\
&*If* $(c_j>1)$,   $s^*=\arg\max_{\left\{s|\hat{t}_{s,j}=1\right\}}Y_{s,j}^{(i)}$,   *End*\
&*While* ($c_j>1$)\
&$m^*=\arg\min_{\{m|c_m=0\}}\left|\alpha^{(i)}_j-\alpha^{(i)}_m\right|$\
&$r^*=\arg\max_{\left\{r|\hat{t}_{r,j}=1, ~r\neq s^*\right\}}Y_{r,m^*}^{(i)}$\
&$\hat{t}_{r^*,j}=0$,  $\hat{t}_{r^*,m^*}=1$\
&$c_{j}=c_{j}-1, ~c_{m^*}=c_{m^*}+1$\
&*End*\
&*End*\
&*With fixed subcarrier pairing* $\hat{{\bm t}}$ *and* mode selection $\hat{{\bm s}},$ *apply water-filling on the direct-link, extra direct-link*\
&  *subcarriers and the relay mode subcarrier pairs with equivalent channel gains in (\[Eq\_ECG\]), to compute*\
&  *power allocation* $\hat{{\bm p}}$ *and the weighted sum rate* $R$.\
&*If* ($R>$ sum\_rate),   sum\_rate $=R$,  $\check{{\bm t}}=\hat{{\bm t}}$,  $\check{{\bm s}}=\hat{{\bm s}}$,  $\check{{\bm p}}=\hat{{\bm p}}$,   *End*\
&*End        (\*\* amendment algorithm \*\*)*\
&$i=i+1$\
\
