Quasi-Concavity for Gaussian Multicast Relay Channels

Abstract

Standard upper and lower bounds on the capacity of relay channels are cut-set (CS), decode-forward (DF), and quantize-forward (QF) rates. For real additive white Gaussian noise (AWGN) multicast relay channels with one source node and one relay node, these bounds are shown to be quasi-concave in the receiver signal-to-noise ratios and the squared source-relay correlation coefficient. Furthermore, the CS rates are shown to be quasi-concave in the relay position for a fixed correlation coefficient, and the DF rates are shown to be quasi-concave in the relay position. The latter property characterizes the optimal relay position when using DF. The results extend to complex AWGN channels with random phase variations.

1. Introduction

A multicast relay channel (MRC) is an information network with a source node, a relay node, and two or more destination nodes, and where one message originating at the source should be received reliably at the destinations. We consider additive white Gaussian noise (AWGN) MRCs and show that certain information rate expressions are quasi-concave in the receiver signal-to-noise ratios (SNRs), the squared source-relay correlation coefficient, and the relay position. In particular, we study cut-set (CS), decode-forward (DF), and quantize-forward (QF) rates. Quasi-concavity suggests that efficient algorithms can optimize signaling and the relay position. However, the main motivation of this work is not practicality, but simply to provide better understanding of the problem.

Relay positioning has been studied by many authors, with a focus on rate enhancement (e.g., [1,2]), range extension (e.g., [3,4]), and outage probability (e.g., [1,5,6]). We study the problem of placing a relay to maximize the multicast rate by extending results of [7,8,9,10]. A preliminary version of this paper without proofs appeared in [11]. Our focus is on real alphabet channels. However, our main results also apply to complex alphabet channels if there are random phase variations so that beamforming is not useful.

This paper is organized as follows. Section 2 presents the MRC model and reviews the CS, DF, and QF rates. Section 3 develops quasi-concavity results in the squared source-relay correlation coefficient ${\rho }^2$ and the channel SNRs. Section 4 introduces a distance dependence for the channel gains and shows that the CS rate is quasi-concave in the relay position when $\rho$ is fixed. We further show that the DF rate is quasi-concave in the relay position. Section 5 illustrates quasi-concavity for one-, two-, and three-dimensional networks, and compares the performance of two DF strategies. Section 6 discusses complex AWGN channels and a sum (source plus relay) power constraint. Section 7 concludes the paper. Appendix A and Appendix B review useful results on concavity and quasi-concavity, and prove a few new results.

2. Model and Information Rates

2.1. Model

An MRC has three types of nodes:

• a source node s that generates a message W and transmits the symbols $X_s^n=X_{s,1},X_{s,2},\dots ,X_{s,n}$;
• a relay node r that receives and forwards symbols $Y_{r,k}$ and $X_{r,k}$, respectively, for $k=1,2,\cdots ,n$;
• destination nodes $j=1,2,\dots ,N$ where node j receives $Y_j^n=Y_{j,1},Y_{j,2},\dots ,Y_{j,n}$ and estimates W as ${\widehat{W}}_j$.

We denote the destination node set as $\mathcal{T}=\{1,2,\dots ,N\}$. The classic relay channel has $N=1$ and Figure 1 shows an MRC with $N=2$.

A memoryless MRC has a function $h(·)$ and a noise random variable $\mathbf{Z}$ so that for every time instant the $N+1$ channel outputs $\mathbf{Y}=(Y_r{Y}_1\dots Y_N)$ are given by

$$\begin{array}{c}\hfill \mathbf{Y}=h(X_s,X_r,\mathbf{Z}).\end{array}$$

The noise $\mathbf{Z}$ is statistically independent of $X_s$ and $X_r$, and the noise variables at different times are statistically independent.

An encoding strategy for M messages has

• W uniformly distributed over $\{1,2,\dots ,M\}$;
• an encoding function $e_s(·)$ such that $X_s^n=e_s\left(W\right)$;
• relay functions $e_{r,k}(·)$ with $X_{r,k}=e_{r,k}(Y_{r,1},\dots ,Y_{r,k-1})$, where $k=1,2,\dots ,n$;
• decoding functions $d_j(·)$ such that $d_j(Y_j^n)={\widehat{W}}_j$, $j\in \mathcal{T}$.

The error probability at destination j is $P_{e,j}=\mathrm{Pr}\left[{\widehat{W}}_j\ne W\right]$. The multicast rate is $R=\left({\log }_{2}M\right)/n$ bits/use. The rate R is achievable if, for any $ϵ>0$ and sufficiently large n, there is an encoding strategy with $P_{e,j}\le ϵ$ for all $j\in \mathcal{T}$. The capacity C is the supremum of the achievable rates.

2.2. Information Rates

The following bounds were given in [12] for the relay channel ($N=1$). Their extensions to MRCs are straightforward.

• CS Rate: $C\le R_{CS}$ where

  $$\begin{array}{cc}\hfill R_{CS}=& max\left\{\underset{1\le j\le N}{min}min\left(I(X_s{X}_r;Y_j),I(X_s;Y_r{Y}_j|X_r)\right)\right\}\hfill \end{array}$$

  (1)

  and where the maximization is over all $X_s{X}_r$.
• Direct-Transmission (DT) Rate: $C\ge R_{DT}$ where

  $$\begin{array}{c}\hfill {\displaystyle R_{DT}=max\left\{\underset{1\le j\le N}{min}I(X_s;Y_j|X_r=x^{\ast })\right\}}\end{array}$$

  (2)

  and where the maximization is over all $x^{\ast }$ and $X_s$.
• DF Rate: $C\ge R_{DF}$ where

  $$\begin{array}{cc}\hfill R_{DF}=& max\left\{\underset{1\le j\le N}{min}min\left(I(X_s{X}_r;Y_j),I(X_s;Y_r|X_r)\right)\right\}\hfill \end{array}$$

  (3)

  and where the maximization is over all $X_s{X}_r$.
• QF Rate: $C\ge R_{QF}$ where

  $$\begin{array}{cc}\hfill R_{QF}=& max\left\{\underset{1\le j\le N}{min}min\left(I(X_s{X}_r;Y_j)-I(Y_r;{\widehat{Y}}_r|X_s{X}_r{Y}_j),I(X_s;{\widehat{Y}}_r{Y}_j|X_r)\right)\right\}\hfill \end{array}$$

  (4)

  where ${\widehat{Y}}_r$ is an auxiliary random variable, and where the maximization is over all $X_s{X}_r{\widehat{Y}}_r$ such that $X_s$ and $X_r$ are independent and $X_s-X_r{Y}_r-{\widehat{Y}}_r$ forms a Markov chain.

2.3. Real Alphabet AWGN MRC

The real alphabet AWGN MRC has real channel symbols and

$$\begin{array}{cc}\hfill Y_r& =a_{s,r}{X}_s+Z_r\hfill \end{array}$$

(5)

$$\begin{array}{cc}\hfill Y_j& =a_{s,j}{X}_s+a_{r,j}{X}_r+Z_j\hfill \end{array}$$

(6)

where $j\in \mathcal{T}$. The $a_{s,r}$, $a_{s,j}$, and $a_{r,j}$ are channel gains between the nodes (see Figure 2). We later relate these gains to distances between the nodes. The $Z_r$ and $Z_j$, $j=1,2,\dots ,N$, are independent and identically distributed Gaussian random variables with zero mean and unit variance. We may alternatively write (5) and (6) in vector form as

$$\begin{array}{c}\hfill {\mathbf{Y}}_j={\mathbf{A}}_j\mathbf{X}+{\mathbf{Z}}_j\end{array}$$

(7)

where $\mathbf{X}={\left(X_s{X}_r\right)}^T$, ${\mathbf{Y}}_j={\left(Y_r{Y}_j\right)}^T$, $\mathbf{Z}={\left(Z_r{Z}_j\right)}^T$, and

$$\begin{array}{c}\hfill {\mathbf{A}}_j=\left(\begin{array}{cc}{a}_{s,r}& 0\\ a_{s,j}& a_{r,j}\end{array}\right).\end{array}$$

(8)

We consider individual average block power constraints

$$\begin{array}{c}\hfill \mathrm{E}\left[\sum _{k=1}^n{X}_{s,k}^2\right]\le n{P}_s,\mathrm{E}\left[\sum _{k=1}^n{X}_{r,k}^2\right]\le n{P}_r.\end{array}$$

(9)

The SNR and the capacity of the link from node u (with transmit power $P_u$) to node v are the respective

$$\begin{array}{c}{\mathsf{SNR}}_{u,v}=a_{u,v}^2{P}_u\hfill \end{array}$$

(10)

$$\begin{array}{c}\mathsf{C}\left({\mathsf{SNR}}_{u,v}\right)=\frac{1}{2}log\left(1+{\mathsf{SNR}}_{u,v}\right).\hfill \end{array}$$

(11)

We simplify the above rate bounds for the AWGN MRC.

• CS Rate:

  $$\begin{array}{cc}\hfill R_{CS}& =\underset{\rho }{max}[{\displaystyle \underset{1\le j\le N}{min}min\left(\mathsf{C}\left({\mathsf{SNR}}_{s,j}+{\mathsf{SNR}}_{r,j}+2\rho \sqrt{{\mathsf{SNR}}_{s,j}{\mathsf{SNR}}_{r,j}}\right),\right.}\hfill \\ & \mathsf{C}\left((1-{\rho }^2)({\mathsf{SNR}}_{s,j}+{\mathsf{SNR}}_{s,r}))\right)]\hfill \end{array}$$

  (12)

  where the correlation coefficient $\rho$ satisfies $|\rho |\le 1$. One can restrict attention to non-negative $\rho$.
• DT Rate:

  $$\begin{array}{c}\hfill R_{DT}=\underset{1\le j\le N}{min}\mathsf{C}\left({\mathsf{SNR}}_{s,j}\right).\end{array}$$

  (13)
• DF Rate:

  $$\begin{array}{cc}\hfill & R_{DF}=\underset{\rho }{max}\left[\underset{1\le j\le N}{min}min\left(\mathsf{C}({\mathsf{SNR}}_{s,j}+{\mathsf{SNR}}_{r,j}+2\rho \sqrt{{\mathsf{SNR}}_{s,j}{\mathsf{SNR}}_{r,j}}),\mathsf{C}\left((1-{\rho }^2){\mathsf{SNR}}_{s,r}\right)\right)\right].\hfill \end{array}$$

  (14)
  One can again restrict attention to non-negative $\rho$.
• QF Rate: Optimizing $X_s{X}_r{\widehat{Y}}_r$ seems difficult. Instead, we choose $X_s$ and $X_r$ to be zero-mean Gaussian with variances $P_s$ and $P_r$, respectively. We further choose ${\widehat{Y}}_r=Y_r+Z_r$ where $Z_r$ is zero-mean Gaussian with variance $N_r$. Optimizing $N_r$ gives (see [13], pp. 336–337)

  $$\begin{array}{cc}\hfill {\tilde{R}}_{QF}=& \underset{1\le j\le N}{min}\mathsf{C}\left({\mathsf{SNR}}_{s,j}+\frac{{\mathsf{SNR}}_{r,j}{\mathsf{SNR}}_{s,r}}{{\mathsf{SNR}}_{s,j}+{\mathsf{SNR}}_{r,j}+{\mathsf{SNR}}_{s,r}+1}\right).\hfill \end{array}$$

  (15)

3. Quasi-Concavity in SNRs and ${\rho }^2$

3.1. CS Rate

We consider two characterizations of $R_{CS}$. First, let ${\mathbf{a}}_j^T=\left(a_{s,j}{a}_{r,j}\right)$ be the second row of ${\mathbf{A}}_j$, let ${\mathbf{Q}}_{\mathbf{X}}$ be the covariance matrix of $\mathbf{X}$ (see Appendix A), and let $det\mathbf{M}$ be the determinant of the square matrix $\mathbf{M}$. The CS rate (12) can be expressed as the maximum of

$$\begin{array}{cc}\hfill R_{CS}\left({\mathbf{Q}}_{\mathbf{X}}\right)=& \underset{1\le j\le N}{min}min\left(\frac{1}{2}log\left({\mathbf{a}}_j^T{\mathbf{Q}}_{\mathbf{X}}{\mathbf{a}}_j+1\right),\frac{1}{2}log\left(\frac{det{\mathbf{Q}}_{{\left({\mathbf{Y}}_j^T{X}_r\right)}^T}}{P_r}\right)\right)\hfill \end{array}$$

(16)

over the convex set of ${\mathbf{Q}}_{\mathbf{X}}$ with diagonal entries $P_s$ and $P_r$. The first logarithm in (16) is clearly concave in ${\mathbf{Q}}_{\mathbf{X}}$. The second logarithm is concave in ${\mathbf{Q}}_{{\left({\mathbf{Y}}_j^T{X}_r\right)}^T}$ (see Appendix A) and ${\mathbf{Q}}_{{\left({\mathbf{Y}}_j^T{X}_r\right)}^T}$ is linear in ${\mathbf{Q}}_{\mathbf{X}}$. To prove the latter claim, observe that

$$\begin{array}{c}\hfill {\mathbf{Q}}_{{\left({\mathbf{Y}}_j^T{X}_r\right)}^T}={\tilde{\mathbf{A}}}_j{\mathbf{Q}}_{\mathbf{X}}{\tilde{\mathbf{A}}}_j^T+\left(\begin{array}{cc}{\mathbf{I}}_2& \mathbf{0}\\ \mathbf{0}& 0\end{array}\right)\end{array}$$

(17)

where ${\tilde{\mathbf{A}}}_j^T=\left({\mathbf{A}}_j^T{\left[01\right]}^T\right)$ and ${\mathbf{I}}_2$ is the $2\times 2$ identity matrix. Hence $R_{CS}\left({\mathbf{Q}}_{\mathbf{X}}\right)$ is concave in (the convex set of) ${\mathbf{Q}}_{\mathbf{X}}$ because it is the minimum of $2N$ concave functions.

Suppose next that we wish to consider $\rho$ and the SNRs individually rather than via ${\mathbf{Q}}_{\mathbf{X}}$. Define the vector

$$\begin{array}{cc}\hfill \mathbf{S}& =({\mathsf{SNR}}_{s,r},{\mathsf{SNR}}_{s,1},\cdots ,{\mathsf{SNR}}_{s,N},{\mathsf{SNR}}_{r,1},\cdots ,{\mathsf{SNR}}_{r,N})\hfill \end{array}$$

(18)

and the functions

$$\begin{array}{c}{f}_j(\rho ,\mathbf{S})={\mathsf{SNR}}_{s,j}+{\mathsf{SNR}}_{r,j}+2\rho \sqrt{{\mathsf{SNR}}_{s,j}{\mathsf{SNR}}_{r,j}}\hfill \end{array}$$

(19)

$$\begin{array}{c}{g}_j(\rho ,\mathbf{S})=(1-{\rho }^2)\left({\mathsf{SNR}}_{s,j}+{\mathsf{SNR}}_{s,r}\right)\hfill \end{array}$$

(20)

$$\begin{array}{c}{R}_{CS}(\rho ,\mathbf{S})=\underset{1\le j\le N}{min}min\left(\mathsf{C}\left(f_j(\rho ,\mathbf{S})\right),\mathsf{C}\left(g_j(\rho ,\mathbf{S})\right)\right).\hfill \end{array}$$

(21)

We establish the following results. We restrict attention to $0\le \rho \le 1$ and positive $\mathbf{S}$.

Lemma 1.

$f_j(\rho ,\mathbf{S})$ and $g_j(\rho ,\mathbf{S})$ are concave in ρ, concave in $\mathbf{S}$, and quasi-concave in $({\rho }^2,\mathbf{S})$.

Proof. 

Concavity with respect to $\rho$ is established by observing that $f_j(\rho ,\mathbf{S})$ is linear in $\rho$, and $g_j(\rho ,\mathbf{S})$ is linear in $-{\rho }^2$ which is concave in $\rho$.

Consider next concavity with respect to $\mathbf{S}$. The Hessian of $f_j(\rho ,\mathbf{S})$ with respect to $\mathbf{S}$ has only one non-zero eigenvalue

$$\begin{array}{c}\hfill -\frac{\rho }{2}·\frac{{\mathsf{SNR}}_{s,j}^2+{\mathsf{SNR}}_{r,j}^2}{{\mathsf{SNR}}_{s,j}^{3/2}{\mathsf{SNR}}_{r,j}^{3/2}}.\end{array}$$

(22)

Thus, $f_j(\rho ,\mathbf{S})$ is concave in $\mathbf{S}$ for non-negative $\rho$ and positive $\mathbf{S}$. The function $g_j(\rho ,\mathbf{S})$ is linear in $\mathbf{S}$, and thus concave in $\mathbf{S}$.

Now consider quasi-concavity with respect to $({\rho }^2,\mathbf{S})$. Substituting $a={\mathsf{SNR}}_{s,j},b={\mathsf{SNR}}_{r,j},c={\rho }^2$ into the fifth function of Lemma A6 in Appendix B, we find that $f_j(\rho ,\mathbf{S})$ is quasi-concave in $({\rho }^2,\mathbf{S})$. For the $g_j(\rho ,\mathbf{S})$, observe that $ab$ is quasi-concave for non-negative $(a,b)$, see the first function of Lemma A6. This implies (see (A7))

$$\begin{array}{c}\hfill (\lambda a_1+\overline{\lambda }{a}_2)(\lambda b_1+\overline{\lambda }{b}_2)\ge min\left(a_1{b}_1,a_2{b}_2\right)\end{array}$$

(23)

for $0\le \lambda \le 1$, and where $\overline{\lambda }=1-\lambda$. Substituting $a_i=1-{\rho }_i^2$ and $b_i={\mathsf{SNR}}_{s,j,i}+{\mathsf{SNR}}_{s,r,i}$ for $i=1,2$, we find that $g_j(\rho ,\mathbf{S})$ is quasi-concave in $({\rho }^2,\mathbf{S})$. ☐

Theorem 1.

$R_{CS}(\rho ,\mathbf{S})$ is concave in ρ, concave in $\mathbf{S}$, and quasi-concave in $({\rho }^2,\mathbf{S})$.

Proof. 

$R_{CS}(\rho ,\mathbf{S})$ involves taking logarithms and minima of (quasi-) concave functions. The results thus follow by applying Lemma 1 above and Lemma A5, Parts 2 and 3, in Appendix B. ☐

Corollary 1.

Consider $\mathbf{S}$ as a function of $\mathbf{P}=(P_s,P_r)$. Then $R_{CS}(\rho ,\mathbf{S}\left(\mathbf{P}\right))$ is quasi-concave in $({\rho }^2,\mathbf{P})$.

Proof. 

The proof follows from the proof of Theorem 1 and because $\mathbf{S}$ is a linear function of $\mathbf{P}$. ☐

To illustrate the quasi-concavity, consider one relay and the channel gains $a_{s,r}=5/2$, $a_{s,1}=1$, and $a_{r,1}=5/3$. This scenario corresponds to the geometry in Section 5.1 with $\mathbf{r}=0.4$. Figure 3 shows a contour plot of $R_{CS}(\rho ,\mathbf{S}\left(\mathbf{P}\right))$ when $P_s=1$. Observe that the contour lines form convex regions, as predicted by Corollary 1.

3.2. DF Rate

Consider the functions

$$\begin{array}{c}{g}_j^{\ast }(\rho ,\mathbf{S})=(1-{\rho }^2){\mathsf{SNR}}_{s,r}\hfill \end{array}$$

(24)

$$\begin{array}{c}{R}_{DF}(\rho ,\mathbf{S})=\underset{1\le j\le N}{min}min\left(\mathsf{C}\left(f_j(\rho ,\mathbf{S})\right),\mathsf{C}\left(g_j^{\ast }(\rho ,\mathbf{S})\right)\right).\hfill \end{array}$$

(25)

As above, we restrict attention to $0\le \rho \le 1$ and positive $\mathbf{S}$.

Theorem 2.

$R_{DF}(\rho ,\mathbf{S})$ is concave in ρ, concave in $\mathbf{S}$, and quasi-concave in $({\rho }^2,\mathbf{S})$.

Proof. 

The proof is similar to that of Theorem 1. ☐

Corollary 2.

$R_{DF}(\rho ,\mathbf{S}\left(\mathbf{P}\right))$ is quasi-concave in $({\rho }^2,\mathbf{P})$.

Proof. 

See the proof of Corollary 1. ☐

3.3. DT Rate

The DT rate (13) is clearly concave in $\mathbf{S}$ and $\mathbf{P}$.

3.4. QF Rate

Consider the functions

$$\begin{array}{c}{h}_j\left(\mathbf{S}\right)={\mathsf{SNR}}_{s,j}+\frac{{\mathsf{SNR}}_{r,j}{\mathsf{SNR}}_{s,r}}{{\mathsf{SNR}}_{s,j}+{\mathsf{SNR}}_{r,j}+{\mathsf{SNR}}_{s,r}+1}\hfill \end{array}$$

(26)

$$\begin{array}{c}{\tilde{R}}_{QF}\left(\mathbf{S}\right)=\underset{1\le j\le N}{min}\mathsf{C}\left(h_j\left(\mathbf{S}\right)\right).\hfill \end{array}$$

(27)

We establish the following results. We restrict attention to non-negative $\mathbf{S}$.

Lemma 2.

$h_j\left(\mathbf{S}\right)$ is quasi-concave in $({\mathsf{SNR}}_{r,j},{\mathsf{SNR}}_{s,r})$.

Proof. 

Substitute $a={\mathsf{SNR}}_{r,j},b={\mathsf{SNR}}_{s,r},k={\mathsf{SNR}}_{s,j}+1$ into the second function of Lemma A6 in Appendix B, and apply Lemma A5, Part 1. ☐

Theorem 3.

${\tilde{R}}_{QF}\left(\mathbf{S}\right)$ is quasi-concave in $\mathbf{S}$ if the ${\mathsf{SNR}}_{s,j}$, $j=1,2,\dots ,n$, are held fixed.

Proof. 

Apply Lemma 2 above and Lemma A5, Parts 2 and 3, in Appendix B. ☐

4. Quasi-Concavity in Relay Position

Suppose the channel gain for the node pair $(i,j)$ is

$$\begin{array}{c}\hfill a_{i,j}=\sqrt{{\xi }_{i,j}}/D_{i,j}^{\alpha /2}\end{array}$$

(28)

where ${\xi }_{i,j}$ is a “fading” gain, $D_{i,j}=\parallel \mathbf{i}-\mathbf{j}\parallel$ is the Euclidean distance between the positions $\mathbf{i}$ and $\mathbf{j}$ of nodes i and j, respectively, and $\alpha \ge 2$ is a path-loss exponent. We thus have

$$\begin{array}{c}\hfill {\mathsf{SNR}}_{i,j}=\frac{{\xi }_{i,j}{P}_i}{D_{i,j}^{\alpha }}=\frac{{\xi }_{i,j}{P}_i}{{\parallel \mathbf{i}-\mathbf{j}\parallel }^{\alpha }}.\end{array}$$

We establish quasi-concavity results in ${\rho }^2$ and $\mathbf{r}$, where $\mathbf{r}$ is the position of the relay node.

4.1. CS Rate

Consider the functions (19)–(21) but relabeled as $f_j(\rho ,\mathbf{r})$, $g_j(\rho ,\mathbf{r})$, and $R_{CS}(\rho ,\mathbf{r})$ to emphasize the dependence on the considered parameters. We again consider $0\le \rho \le 1$ and positive $\mathbf{S}$.

Lemma 3.

$f_j(\rho ,\mathbf{r})$ and $g_j(\rho ,\mathbf{r})$ are quasi-concave in $\mathbf{r}$ for fixed ρ. Furthermore, $f_j(\rho ,\mathbf{r})$ is quasi-concave in $({\rho }^2,\mathbf{r})$.

Proof. 

Consider the functions

$$\begin{array}{c}{\tilde{f}}_j(\rho ,D^{\alpha })=\frac{{\xi }_{s,j}{P}_s}{D_{s,j}^{\alpha }}+\frac{{\xi }_{r,j}{P}_r}{D^{\alpha }}+2\rho \sqrt{\frac{{\xi }_{s,j}{P}_s}{D_{s,j}^{\alpha }}\frac{{\xi }_{r,j}{P}_r}{D^{\alpha }}}\hfill \end{array}$$

(29)

$$\begin{array}{c}{\tilde{g}}_j(\rho ,D^{\alpha })=(1-{\rho }^2)\left(\frac{{\xi }_{s,j}{P}_s}{D_{s,j}^{\alpha }}+\frac{{\xi }_{s,r}{P}_s}{D^{\alpha }}\right)\hfill \end{array}$$

(30)

which are quasi-linear in $D^{\alpha }$ for fixed $\rho$ since they are decreasing in $D^{\alpha }$. However, $D_{r,j}^{\alpha }$ is a convex function of $\mathbf{r}$ for $\alpha \ge 1$, and thus Lemma A5, Part 5, in Appendix B establishes that $f_j(\rho ,\mathbf{r})$ is quasi-concave in $\mathbf{r}$ for fixed $\rho$. Similarly, $D_{s,r}^{\alpha }$ is a convex function of $\mathbf{r}$ for $\alpha \ge 1$, and we find that $g_j(\rho ,\mathbf{r})$ is quasi-concave in $\mathbf{r}$ for fixed $\rho$.

Next, substitute $a=D^{\alpha }$ and $b={\rho }^2$ into the third function of Lemma A6, and use Lemma A5, Part 1, to show that ${\tilde{f}}_j(\rho ,D^{\alpha })$ is quasi-concave in $({\rho }^2,D^{\alpha })$. However, ${\tilde{f}}_j$ is decreasing in $D^{\alpha }$ and $D_{r,j}^{\alpha }$ is convex in $\mathbf{r}$, so Lemma A5, Part 5, establishes that $f_j(\rho ,\mathbf{r})$ is quasi-concave in $({\rho }^2,\mathbf{r})$. ☐

Unfortunately, ${\tilde{g}}_j$ is quasi-convex (and not quasi-concave) in $({\rho }^2,D^{\alpha })$. To see this, substitute $a=D^{\alpha }$ and $b={\rho }^2$ into the fourth function of Lemma A6. Quasi-concavity would have been useful since it would have permitted using Lemma A5, Parts 2 and 4, to establish the quasi-concavity of

$$\begin{array}{c}\hfill R_{CS}\left(\mathbf{r}\right)=\underset{\rho }{max}\left[\underset{1\le j\le N}{min}min\left(\mathsf{C}\left(f_j(\rho ,\mathbf{r})\right),\mathsf{C}\left(g_j(\rho ,\mathbf{r})\right)\right)\right].\end{array}$$

(31)

However, we have been unable to prove this, and our numerical results suggest that $R_{CS}(\rho ,\mathbf{r})$ is not quasi-concave in $({\rho }^2,\mathbf{r})$. Nevertheless, Lemma 3 suffices to establish an intermediate result which is useful in Section 5 when we study $\rho =0$.

Theorem 4.

$R_{CS}(\rho ,\mathbf{r})$ is quasi-concave in $\mathbf{r}$ for fixed ρ, $0\le \rho \le 1$.

Proof. 

$R_{CS}(\rho ,\mathbf{r})$ is the minimum of functions that are quasi-concave in $\mathbf{r}$. Lemma A5, Part 2, thus establishes the theorem. ☐

4.2. DF Rate

The quasi-convexity of ${\tilde{g}}_j(\rho ,D^{\alpha })$ relaxes for the DF rate (25). Consider the negative of the fourth function of Lemma A6 in Appendix B with $k_1=0$:

$$\begin{array}{c}\hfill f(a,b)=(1-b)k_2/a.\end{array}$$

(32)

This function is quasi-linear in $(a,b)$ since both its superlevel and sublevel sets are convex. This result implies the following theorem. We again consider the functions (24)–(25) but relabeled as $g_j^{\ast }(\rho ,\mathbf{r})$ and $R_{DF}(\rho ,\mathbf{r})$. We further define

$$\begin{array}{c}{\tilde{g}}_j^{\ast }(\rho ,D^{\alpha })=(1-{\rho }^2)\frac{{\xi }_{s,r}{P}_s}{D^{\alpha }}\hfill \end{array}$$

(33)

$$\begin{array}{c}{R}_{DF}\left(\mathbf{r}\right)=\underset{\rho }{max}\left[\underset{1\le j\le N}{min}min\left(\mathsf{C}\left(f_j(\rho ,\mathbf{r})\right),\mathsf{C}\left(g_j^{\ast }(\rho ,\mathbf{r})\right)\right)\right].\hfill \end{array}$$

(34)

As above, we consider $0\le \rho \le 1$ and positive $\mathbf{S}$.

Theorem 5.

$R_{DF}(\rho ,\mathbf{r})$ is quasi-concave in $({\rho }^2,\mathbf{r})$, and $R_{DF}\left(\mathbf{r}\right)$ is quasi-concave in $\mathbf{r}$.

Proof. 

${\tilde{g}}_j^{\ast }(\rho ,D^{\alpha })$ is quasi-linear in $({\rho }^2,D^{\alpha })$ and decreasing in $D^{\alpha }$. Furthermore, $D_{s,r}^{\alpha }$ is convex in $\mathbf{r}$, and thus Lemma A5, Part 5, in Appendix B establishes that $g_j^{\ast }(\rho ,\mathbf{r})$ is quasi-concave in $({\rho }^2,\mathbf{r})$. $R_{DF}(\rho ,\mathbf{r})$ is therefore quasi-concave in $\mathbf{r}$, as it is the minimum of quasi-concave functions (see Lemma A5, Part 2). Furthermore, $R_{DF}\left(\mathbf{r}\right)$ is concave in $\mathbf{r}$ by Lemma A5, Part 4. ☐

5. DF Performance

This section presents numerical results for the DF strategy and compares them to results from [7,8,9]. We consider 1-, 2-, and 3-dimensional MRCs with different numbers N of destination nodes. For simplicity, we consider the low SNR or broadband regime where

$$\begin{array}{c}\hfill \mathsf{C}\left(\mathsf{SNR}\right)=\frac{1}{2}log(1+\mathsf{SNR})\to \frac{1}{2}\mathsf{SNR}.\end{array}$$

(35)

In other words, we consider the CS and DF rates without the logarithms. This approach is valid not only in the limit of low SNR, but more generally because we proved our quasi-concavity results without taking logarithms. Furthermore, in the low SNR regime the rates of full-duplex and half-duplex transmission are the same under a block power constraint.

We choose $P_s=P_r=P=1$, $\alpha =2$, and ${\xi }_{u,v}=1$ for all node pairs $(u,v)$. We study both coherent transmission where $\rho$ is optimized and non-coherent transmission with $\rho =0$. The rates are in nats/channel use. Alternatively, suppose we use sync pulses sampled at $2W$ samples per second, where W is the (one-sided) signal bandwidth. Suppose further that the (one-sided) noise power spectral density is 1 Watt/Hz. Then at low SNR the rates in nats/channel use are the same as the rates in nats/sec.

5.1. One Dimension

Consider a relay channel ($N=1$) where the source is at the origin ($\mathbf{s}=0$) and the destination is at point 1 ($\mathbf{1}=1$). Figure 4 shows the low SNR CS rates, DF rates, and the routing-based DF (RDF) rates developed in [7], which are given by

$$\begin{array}{c}{R}_{CS}\to \frac{1}{2}min\left(\frac{{\xi }_{s,1}{P}_s}{{\parallel \mathbf{s}-\mathbf{1}\parallel }^{\alpha }}+\frac{{\xi }_{r,1}{P}_r}{{\parallel \mathbf{r}-\mathbf{1}\parallel }^{\alpha }}+\frac{2\rho \sqrt{{\xi }_{s,1}{\xi }_{r,1}{P}_s{P}_r}}{{\parallel \mathbf{s}-\mathbf{1}\parallel }^{\alpha /2}{\parallel \mathbf{r}-\mathbf{1}\parallel }^{\alpha /2}},(1-{\rho }^2)\left(\frac{{\xi }_{s,1}{P}_s}{{\parallel \mathbf{s}-\mathbf{1}\parallel }^{\alpha }}+\frac{{\xi }_{s,r}{P}_s}{{\parallel \mathbf{s}-\mathbf{r}\parallel }^{\alpha }}\right)\right)\hfill \end{array}$$

(36)

$$\begin{array}{c}{R}_{DF}\to \frac{1}{2}min\left(\frac{{\xi }_{s,1}{P}_s}{{\parallel \mathbf{s}-\mathbf{1}\parallel }^{\alpha }}+\frac{{\xi }_{r,1}{P}_r}{{\parallel \mathbf{r}-\mathbf{1}\parallel }^{\alpha }}+\frac{2\rho \sqrt{{\xi }_{s,1}{\xi }_{r,1}{P}_s{P}_r}}{{\parallel \mathbf{s}-\mathbf{1}\parallel }^{\alpha /2}{\parallel \mathbf{r}-\mathbf{1}\parallel }^{\alpha /2}},(1-{\rho }^2)\frac{{\xi }_{s,r}{P}_s}{{\parallel \mathbf{s}-\mathbf{r}\parallel }^{\alpha }}\right)\hfill \end{array}$$

(37)

$$\begin{array}{c}{R}_{RDF}\to \underset{0\le \beta \le 1}{max}\frac{1}{2}\left[min\left(\frac{{\xi }_{r,1}{P}_r}{{\parallel \mathbf{r}-\mathbf{1}\parallel }^{\alpha }},\frac{\beta {\xi }_{s,r}{P}_s}{{\parallel \mathbf{s}-\mathbf{r}\parallel }^{\alpha }}\right)+\frac{(1-\beta ){\xi }_{s,1}{P}_s}{{\parallel \mathbf{s}-\mathbf{1}\parallel }^{\alpha }}\right].\hfill \end{array}$$

(38)

Observe that all curves are quasi-concave (but not concave) in $\mathbf{r}$. Theorems 4 and 5 predict the quasi-concavity for all curves except for the coherent CS rates. Observe also that the curves for the coherent and non-coherent rates merge for relay positions exceeding a certain value ($r=0.5$ and $r\approx 0.47$ for the respective CS and DF rates). The reason for this behavior is that $\rho =0$ is optimal for the coherent CS and DF rates beyond these positions, see the $\rho$ curve in [1] (Figure 16). Furthermore, the non-coherent CS rates coincide with the non-coherent DF rates for a large range of $\mathbf{r}$.

The best relay positions for the two strategies are different. For example, $\mathbf{r}=0.5$ maximizes $R_{RDF}$ while the $\mathbf{r}$ maximizing $R_{DF}$ is closer to the source. This is because when the source transmits, the relay and the destination listen, and the destination “collects” information. The relay can thus be positioned closer to the source while maintaining the same information rate from the source to the relay, and from the source-relay pair to the destination. At the optimal positions, we compute $R_{DF}\approx 2.26P$ nats/sec and $R_{RDF}=2P$ nats/sec, so the DF gain is ≈13%.

Finally, we illustrate that $R_{DF}(\rho ,\mathbf{r})$ is quasi-concave in $({\rho }^2,\mathbf{r})$ in Figure 5. The contour lines form convex regions, as predicted by Theorem 5.

5.2. Two Dimensions

Consider $N=5$ destinations positioned on a square in the two-dimensional Euclidean plane with the source node at the origin. Figure 6a plots the node positions as circles, and the non-coherent $R_{DF}$ as a function of the relay position. The best relay position is shown by a circle labeled ${\mathbf{r}}_{\mathrm{DF}}^{\ast }$ and the corresponding rate is $R_{DF}\approx 0.011P$ nats/sec. Figure 6c plots the low SNR two-hop rate

$$\begin{array}{c}\hfill R_{2H}\to \underset{1\le j\le 5}{min}\frac{1}{2}min\left(\frac{{\xi }_{s,r}{P}_s}{{\parallel \mathbf{s}-\mathbf{r}\parallel }^{\alpha }},\frac{{\xi }_{r,j}{P}_r}{{\parallel \mathbf{r}-\mathbf{j}\parallel }^{\alpha }}\right)\end{array}$$

(39)

as a function of the relay position. The best relay position is shown by a circle labeled ${\mathbf{r}}_{2H}^{\ast }$ and the corresponding two-hop rate is $R_{2H}=0.01P$ nats/sec. The non-coherent DF gain is thus ≈10%.

Figure 6b,d shows contour plots for $R_{DF}$ and $R_{2H}$. The contours form convex regions, as predicted by Theorem 5. Again, the relay position maximizing $R_{DF}$ lies closer to the source than the relay position maximizing $R_{2H}$.

5.3. Three Dimensions

Consider $N=5$ destinations positioned in 3-dimensional Euclidean space as in Figure 7. The figure also shows the convex hull (a polyhedron) of the points. The points ${\mathbf{r}}_{\mathrm{DF}}^{\ast }$ and ${\mathbf{r}}_{2\mathrm{H}}^{\ast }$ denote the relay positions that maximize the non-coherent $R_{DF}$ and $R_{2H}$, respectively. We remark that ${\mathbf{r}}_{\mathrm{DF}}^{\ast }$ and ${\mathbf{r}}_{2\mathrm{H}}^{\ast }$ remain unchanged if more destinations are positioned inside the polyhedron. This is because the points in the polyhedron receive at least the same rate as the worst of the five nodes at the corner points.

6. Discussion

6.1. Complex AWGN Channels

For complex-alphabet AWGN channels, we could replace (5) and (6) by adding phases ${\varphi }_{i,j}$ for $i=s,r$ and $j=1,2,\dots ,N$ as follows:

$$\begin{array}{cc}\hfill Y_r& =a_{s,r}{e}^{j{\varphi }_{s,r}}{X}_s+Z_r\hfill \end{array}$$

(40)

$$\begin{array}{cc}\hfill Y_j& =a_{s,j}{e}^{j{\varphi }_{s,j}}{X}_s+a_{r,j}{e}^{j{\varphi }_{r,j}}{X}_r+Z_j\hfill \end{array}$$

(41)

where the noise variables $Z_r$ and $Z_j$, $j=1,2,\dots ,N$, are independent, identically distributed, circularly symmetric, complex, Gaussian random variables with zero mean and unit variance. The distance dependence of $a_{i,j}$ can be chosen as in (28) and the phase dependence as

$$\begin{array}{c}\hfill {\varphi }_{i,j}=2\pi D_{i,j}/\lambda \end{array}$$

(42)

where $\lambda =c/f_o$ is the wavelength, c is the speed of light, and $f_o$ is the carrier frequency.

For example, the DF rate (14), normalized by the number of real dimensions, is

$$\begin{array}{c}{R}_{DF}=\underset{\rho }{max}\left[\underset{1\le j\le N}{min}min\left(\mathsf{C}({\mathsf{SNR}}_{s,j}+{\mathsf{SNR}}_{r,j}+\right.\right.\hfill \\ \left.\left.\left.2\Re \left\{\rho e^{j({\varphi }_{s,j}-{\varphi }_{r,j})}\right\}\sqrt{{\mathsf{SNR}}_{s,j}{\mathsf{SNR}}_{r,j}}\right),\mathsf{C}\left(\right(1-{|\rho |}^2\left){\mathsf{SNR}}_{s,r}\right)\right)\right]\hfill \end{array}$$

(43)

where the complex correlation coefficient $\rho$ satisfies $0\le |\rho |\le 1$. Observe that for a classic relay channel, with $N=1$ destination, one can choose $\rho$ to make $\Re \left\{\rho e^{j({\varphi }_{s,1}-{\varphi }_{r,1})}\right\}$ real and non-negative, as for real alphabet AWGN channels. However, for $N\ge 2$ one must choose complex $\rho$ in general. Furthermore, the quasi-concavity in $\mathbf{r}$ will not be valid in general because the phases ${\varphi }_{r,j}$ change with $\mathbf{r}$, and we cannot optimize $\rho$ for each destination node separately. However, we remark that this effect is “local" in the sense that for large carrier frequencies the phase variations are sensitive to changes in $\mathbf{r}$. A pragmatic approach would then be to optimize $\mathbf{r}$ for non-coherent transmission ($\rho =0$) even if beamforming is permitted. Furthermore, if the channel exhibits random phase variations, then the best approach is to choose $\rho =0$ (see [1], Figure 18) in which case we have quasi-concavity for both the CS and DF rates. Finally, we remark that it might be interesting to consider quasi-concavity in the correlation coefficients for problems where the source and relay have sufficiently many antennas to overcome the problem outlined above.

6.2. Sum-Power Constraint

For some applications, it is interesting to consider a sum-power constraint

$$\begin{array}{c}\hfill \mathrm{E}\left[\sum _{k=1}^n{|X|}_{s,k}^2+{|X|}_{r,k}^2\right]\le n{P}_T.\end{array}$$

(44)

As is usually done, we set $P_r=P_T-P_s$ and consider $P_s$, $0\le P_s\le P_T$ as a new optimization parameter. One might now hope that $R_{CS}(P_s,\mathbf{r})$ or $R_{DF}(P_s,\mathbf{r})$ are quasi-concave in $(P_s,\mathbf{r})$ for fixed $\rho$, or at least for $\rho =0$. Unfortunately, we have found counterexamples that show this is not the case. The rate functions do seem to have interesting properties, however, and these deserve further exploration.

7. Conclusions

Various quasi-concavity results were established for AWGN MRCs. In particular, the CS rates are quasi-concave in the relay position for a fixed correlation coefficient (Theorem 4) and the DF rates are quasi-concave in the relay position (Theorem 5).