# On optimal relay placement in directional networks

Mine Gokce Dogan, Yahya H. Ezzeldin, Christina Fragouli  UCLA, Los Angeles, CA
90095, USA
Email: {minedogan96, yahya.ezzeldin<EMAIL_ADDRESS>
###### Abstract

In this paper, we study the problem of optimal topology design in wireless
networks equipped with highly-directional transmission antennas. We use the
1-2-1 network model to characterize the optimal placement of two relays that
assist the communication between a source-destination pair. We analytically
show that under some conditions on the distance between the source-destination
pair, the optimal topology in terms of maximizing the network throughput is to
place the relays as close as possible to the source and the destination.

##  I Introduction

We consider a source that would like to transmit information to a destination
with the help of $N$ relays, using directional communication. A typical
network information theory question is, given a fixed network topology, what
is the maximum rate that the source can communicate to the destination
(network capacity)? We here look at the reverse question: assuming that we
have the freedom of arbitrarily placing the relays, where should we place
them, so that the capacity is maximized?

We focus this work on directional communication networks, which have
significant impact in next generation systems. Indeed, as we move towards
using higher and higher frequencies, communication increasingly becomes
directional, to combat the severe path-loss and improve the data rates. A
prominent example is millimeter-wave (mmWave) networks, that are anticipated
to play an integral role for the fifth-generation (5G) cellular systems due to
the large bandwidth they provide.

Understanding how to optimally place relays in such networks is a timely
question. There are currently a number of initiated projects that aim to
deploy infrastructure for directional communications, such as Terragraph [1].
Moreover, a number of applications envisage creating mobile backbones, such as
flexible UAV-assisted wireless networks [2], where adapting the topology has
low cost.

Finding the optimal topology is not a straightforward question to answer. The
main challenge is the ability of beam steering, which makes the capacity
calculation dependent on the schedule (which node transmits to which node and
for how long). We note that the optimal schedule depends on the underlying
configuration; thus for every network configuration, one would need to
calculate the associated optimal schedule to find the capacity.

On the other hand, finding the optimal topology can be worth the effort -
randomly placing relays, as Fig. 1 depicts, can result in underwhelming
performance.

Figure 1: Empirical distribution of the approximate capacity for relays placed
uniformly at random in space. The red line marks the approximate capacity of
the optimal topology.

This figure assumes that two relays are placed uniformly at random in the
space between a fixed source and destination location where the distance
between the source and the destination is $d=600\sqrt{2}$. The distribution
shown in the figure was computed over 1000 random topologies with the red line
indicating the performance of the optimal relay placement. We find that the
(approximate) capacity can vary significantly depending on where the two
relays are placed, and can be much lower (on average almost $50\%$ lower) than
the capacity of the optimal configuration.

Our approach to address this problem builds on the 1-2-1 network model which
was introduced in [3] to study the capacity of wireless networks with
steerable highly-directional antennas. In particular, in [3], it was proved
that for a predetermined topology, the capacity of the network can be
approximated to within a universal constant gap111Constant gap refers to a
quantity that is independent of the channel coefficients and operating SNR,
and only depends on the number of nodes. and its optimal beam schedule can be
found in polynomial-time.

Our main result in this paper is to characterize the optimal topology in terms
of the approximate capacity for a two relay Gaussian Full-Duplex (FD) 1-2-1
network under a path-loss propagation model. Surprisingly, we prove that when
the distance between the source and destination allows reasonable point-to-
point capacity between the two nodes using directional antennas, the optimal
topology concentrates relays at the source and destination positions, such
that one relay is as close as possible to the source and the other to the
destination. This understanding of the optimal topology for two relays, offers
a first step towards creating optimal topologies for larger directional
communication networks.

Related Work. Several works in the literature focus on the optimization of
relay locations in wireless networks that employ omnidirectional antennas.
Optimal relay placement is studied within a cellular system in [4]. The
authors in [5] and [6] characterize the optimal placement of a single amplify-
forward relay in a cooperative communication network with and without joint
optimization of power allocation. In [7], the authors find the best relay
location over a finite set of possible locations for bi-directional
transmission. However, they do not optimize the relay locations in a
continuous domain and their work does not include the scheduling aspects of
directional networks. In [8], the optimal placement of relay nodes is studied
for the linear deterministic network model for a wireless network. In
contrast, our work considers the relay placement problem in networks with
steerable directional antennas and does not put restrictions on the schemes
that are employed by the relays.

Perhaps the closest to our work are the results on relay placement in mmWave
networks [9, 10]. These approaches only consider picking the best topology
among a class of predetermined topologies and beamforming schedules or present
heuristic metrics based on link qualities in the network. Therefore, none of
these works identifies the optimal topology structure as we do. Our study
considers the unicast approximate capacity as defined by the 1-2-1
information-theoretic model and allows a more extensive topology search with
each topology operating with its optimal beam schedule.

Paper Organization. Section II provides background on the 1-2-1 network model
for mmWave networks and introduces our channel model. Section III introduces
our main theorem, that is proved in Section IV. Section V concludes the paper.

##  II System Model and Background

We consider the Gaussian Full-Duplex (FD) 1-2-1 model which was proposed in
[3] to study the information-theoretic capacity of multi-hop wireless networks
that utilize directional transmissions for communication. In an $N$-relay
Gaussian FD 1-2-1 network, $N$ relays assist the communication between a
source node (node 0) and a destination node (node $N+1$). Each node in the
network can transmit and receive simultaneously and is equipped with a single
highly-directional transmit beam and a single highly-directional receive beam.
At any particular instance, a node in a 1-2-1 network can only transmit to at
most one node and receive from at most one node by directing its transmit and
receive beam, respectively.
In order for two nodes to communicate, they need to activate the link between
them by steering their beams towards each other (thus, the name of the 1-2-1
model). In the following, we discuss capacity results for FD 1-2-1 networks.

Capacity of FD 1-2-1 networks. In [3], it was shown that the capacity of an
$N$-relay Gaussian FD 1-2-1 network can be approximated to within a constant
gap that only depends on the number of nodes in the network222The constant gap
is due to the fact that the choice of the optimal schedule can potentially be
used to relay information of the transmitted message. In case the schedule
cannot be used to convey information about the message, the characterization
is the exact capacity of the network.. In particular, it was shown in [3] that
the approximate capacity and its optimal schedule can be computed in
polynomial-time through the following Linear Program (LP),

$\displaystyle\ \rm{P1:}\ \macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}=\displaystyle\max\limits_{\lambda,F}\sum_{j=0}^{N}F_{N+1,j}$
$\displaystyle({\rm P1}a)\ 0\leq F_{j,i}\leq\lambda_{\ell_{j,i}}\ell_{j,i},$
$\displaystyle\forall(i,j){\in}[0\\!:\\!N]\\!\times\\![1{:}N{+}1],$
$\displaystyle({\rm
P1}b)\displaystyle\sum_{\begin{subarray}{c}j\in[1:N{+}1]\backslash\\{i\\}\end{subarray}}F_{j,i}=\\!\\!\\!\\!\\!\\!\\!\displaystyle\sum_{\begin{subarray}{c}k\in[0{:}N]\backslash\\{i\\}\end{subarray}}F_{i,k},$
$\displaystyle\forall i\in[1{:}N],$ $\displaystyle({\rm
P1}c)\\!\\!\\!\\!\displaystyle\sum_{\begin{subarray}{c}j\in[1:N{+}1]\backslash\\{i\\}\end{subarray}}\\!\\!\\!\\!\\!\\!\lambda_{\ell_{j,i}}\leq
1,$ $\displaystyle\forall i\in[0{:}N],$ (1) $\displaystyle({\rm
P1}d)\\!\\!\\!\\!\displaystyle\sum_{\begin{subarray}{c}i\in[0:N]\backslash\\{j\\}\end{subarray}}\\!\\!\\!\\!\lambda_{\ell_{j,i}}\leq
1,$ $\displaystyle\forall j\in[1{:}N+1],$ $\displaystyle({\rm P1}e)\
\lambda_{\ell_{j,i}}\geq 0,$
$\displaystyle\forall(i,j){\in}[0\\!:\\!N]\\!\times\\![1\\!:\\!N{+}1],$

where: (i) $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}$
is the approximate network capacity; (ii) $\ell_{j,i}$ denotes the point-to-
point link capacity from node $i$ to node $j$ when the respective transmit and
receive beams are aligned; (iii) $F_{j,i}$ represents the amount of
information flowing from node $i$ to node $j$; and (iv) $\lambda_{\ell_{j,i}}$
denotes the fraction of time for which the link of capacity $\ell_{j,i}$ is
active, based on the schedule used to operate/align the antenna beams in the
network.

Cut-set formulation of approximate capacity. We observe that for a fixed
feasible configuration of link activation times $\\{\lambda_{\ell_{ji}}\\}$,
the LP in (II) is the classical max-flow problem over a graph with edge
capacities $\lambda_{\ell_{j,i}}\ell_{j,i}$. Thus, we can rewrite (II) by
replacing the max-flow LP with its cut-set dual problem. In particular, we get
the following LP,

$\displaystyle\ \rm{P2:}\ \macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}=\max_{\lambda,\alpha}\alpha$ $\displaystyle({\rm
P2}a)\\!\\!\\!\\!\displaystyle\sum_{\begin{subarray}{c}j\in[1:N{+}1]\backslash\\{i\\}\end{subarray}}\\!\\!\\!\\!\\!\\!\lambda_{\ell_{j,i}}\leq
1,\hskip 75.88371pt\forall i\in[0{:}N],$ $\displaystyle({\rm
P2}b)\\!\\!\\!\\!\displaystyle\sum_{\begin{subarray}{c}i\in[0:N]\backslash\\{j\\}\end{subarray}}\\!\\!\\!\\!\lambda_{\ell_{j,i}}\leq
1,\hskip 65.04256pt\forall j\in[1{:}N+1],$ (2) $\displaystyle({\rm P2}c)\
\lambda_{\ell_{j,i}}\geq 0,\hskip
52.75679pt\forall(i,j){\in}[0\\!:\\!N]\\!\times\\![1\\!:\\!N{+}1],$
$\displaystyle({\rm
P2}d)\alpha\\!\leq\\!\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}(i,j):\\\
i\in\Omega,j\in\Omega^{c}\end{subarray}}\lambda_{\ell_{j,i}}\ell_{j,i},\ \
\forall\Omega\\!\subseteq\\![0{:}N\\!+\\!1],0{\in}\Omega,N\\!\\!+\\!1{\in}\Omega^{c},$

where for each constraint $({\rm P2}d)$, the right-hand side (RHS) represents
the cut value for that particular cut $\Omega$ given the link activations
$\\{\lambda_{\ell_{j,i}}\\}$. Thus, the LP P2 maximizes the minimum cut by
optimizing the link activation times that satisfy the constraints $({\rm
P2}a-c)$.

If we specialize the LP P2 to the case where there are $N=2$ relays in a
network, we get that

$\displaystyle\ \rm{P3:}\ \macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}=\max_{\lambda,\alpha}\alpha$ $\displaystyle({\rm
P3}a)\\!\\!\\!\\!\displaystyle\sum_{\begin{subarray}{c}j\in[1:3]\backslash\\{i\\}\end{subarray}}\\!\\!\\!\\!\\!\\!\lambda_{\ell_{j,i}}\leq
1,\qquad\qquad\qquad\ \forall i\in[0{:}2],$ $\displaystyle({\rm
P3}b)\\!\\!\\!\\!\displaystyle\sum_{\begin{subarray}{c}i\in[0:2]\backslash\\{j\\}\end{subarray}}\\!\\!\\!\\!\lambda_{\ell_{j,i}}\leq
1,\qquad\qquad\qquad\forall j\in[1{:}3],$ (3) $\displaystyle({\rm P3}c)\
\lambda_{\ell_{j,i}}\geq 0,\qquad\qquad\
\forall(i,j){\in}[0\\!:\\!2]\\!\times\\![1\\!:\\!3],$ $\displaystyle({\rm
P3}d)\
\alpha\leq\lambda_{\ell_{3,1}}\ell_{3,1}+\lambda_{\ell_{3,2}}\ell_{3,2}+\lambda_{\ell_{3,0}}\ell_{3,0},$
$\displaystyle({\rm P3}e)\
\alpha\leq\lambda_{\ell_{1,0}}\ell_{1,0}+\lambda_{\ell_{2,0}}\ell_{2,0}+\lambda_{\ell_{3,0}}\ell_{3,0},$
$\displaystyle({\rm P3}f)\
\alpha\leq\lambda_{\ell_{2,1}}\ell_{2,1}+\lambda_{\ell_{3,1}}\ell_{3,1}+\lambda_{\ell_{2,0}}\ell_{2,0}+\lambda_{\ell_{3,0}}\ell_{3,0},$
$\displaystyle({\rm P3}g)\
\alpha\leq\lambda_{\ell_{1,0}}\ell_{1,0}+\lambda_{\ell_{3,2}}\ell_{3,2}+\lambda_{\ell_{1,2}}\ell_{1,2}+\lambda_{\ell_{3,0}}\ell_{3,0}.$

Our main results in this paper for Gaussian 1-2-1 networks with $N=2$ relays,
which are presented in the following section, will rely heavily on the cut-set
formulation for the approximate capacity shown in (II).

Network topology and propagation model. Throughout the remainder of the paper,
we consider a Gaussian 1-2-1 network with $N=2$ relays as illustrated in Fig.
2.

Figure 2: An example of the considered network topology.

Without loss of generality, we assume that the source is at coordinates
$(0,0)$, the destination is at $(d,0)$ and the two relays are at
$(x_{1},y_{1})$ and $(x_{2},y_{2})$, respectively. The x- coordinates $x_{1}$
and $x_{2}$, and y-coordinates $y_{1}$ and $y_{2}$ can be arbitrarily
different.

For the point-to-point link capacity between any two nodes with aligned
transmit/receive beams, we use a path-loss model while assuming that all nodes
follow a uniform transmission power constraint. In particular, we have that

$\ell_{j,i}=\log\left(1+\frac{\gamma}{d_{j,i}^{a}}\right)\stackrel{{\scriptstyle(a)}}{{\approx}}\log\left(\frac{\gamma}{d_{j,i}^{a}}\right)$
(4)

where: (i) $d_{j,i}$ is the distance between node $i$ and node $j$; (ii) $a>1$
is the path loss exponent; (iii) the arbitrary parameter $\gamma>0$ subsumes
the effects of the transmission power, the aligned transmit and receive
antenna beams and communication wavelength. The approximation in $(a)$ assumes
that $\gamma/d_{j,i}^{a}\gg 1,\forall(i,j)\in[0:N]\times[1:N+1]$.

######  Remark 1.

Note that from (4), it follows that

$\displaystyle\frac{\gamma}{d_{j,i}^{a}}>1\ \ \implies\ \
\ell_{j,i}=\log\left(1+\frac{\gamma}{d_{j,i}^{a}}\right)\leq\log\left(\frac{\gamma}{d_{j,i}^{a}}\right)+1.$

As a result, it is not difficult to see that working with the approximation of
$\ell_{j,i}$ in computing the approximate capacity using LP P1 in (II), can at
most reduce the approximate capacity by a single bit. Thus, with a slight
abuse of notation, we take $\ell_{j,i}=\log\left(\gamma/d_{j,i}^{a}\right)$
for the remainder of the paper.

In the following section, we present our key result in this paper that
characterizes the best topology among the class of 2-relay Gaussian 1-2-1
networks described above.

##  III Optimal Topology for the Two Relay Network

In this section, we answer the question: what is the optimal placement of two
relays in a Gaussian 1-2-1 FD network that maximizes the rate transferred
between a source and a destination? Our key result is summarized by the
following theorem which is proved in Section IV.

######  Theorem 1.

Consider a $2$-relay Gaussian FD 1-2-1 network with a topology and propagation
model as described in Section II. For distance $d$ such that
$\frac{\gamma}{d^{a}}>3^{a}$, the optimal topology in terms of maximizing the
approximate capacity is to place one of the relays as close to the source as
possible and the other relay as close to the destination as possible.

A careful computation of the optimal solution of LP P3 in (II) when the two
relays approach the source and destination, respectively, gives the following
corollary.

######  Corollary 1.

For the 2-relay Gaussian 1-2-1 network with conditions satisfying Theorem 1,
the best approximate capacity achievable by any topology is given by

$\displaystyle{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}=2\log\left(\frac{\gamma}{d^{a}}\right).$ (5)

###### Proof.

Setting the two relays at the source and destination positions, respectively,
the link capacities $\ell_{10}$ and $\ell_{32}$ in LP P3 in (II) grow
infinitely large. Thus, only the constraint $(\rm{P3}f)$ remains as an upper
bound on $\alpha$. Additionally, we have
$\ell_{20}=\ell_{21}=\ell_{31}=\ell_{30}=\log\left(\gamma/d^{a}\right)$.
Setting two non-conflicting $\lambda$’s to unity (for example
$\lambda_{20}=\lambda_{31}=1$) maximizes the RHS of $(\rm{P3}f)$ and proves
the corollary. ∎

######  Remark 2.

The results in Theorem 1 and Corollary 1 suggest that in the absence of
potential blockage between the source and destination, the optimal relay
placement is for the network to concentrate two nodes (source and one relay)
at the source location, and similarly at the destination location, in order to
virtually increase the number of transmit and receive beams at the disposal of
the source and destination, respectively. Our simulation in Fig. 3 also
suggests that, for $d=200\sqrt{2}$ (it satisfies the condition in Theorem 1),
the approximate capacity increases as $\beta$ decreases (the relays approach
the source and the destination). We note that the reason for the change of the
slope in Fig. 3 is due to the change in the optimal schedule. When
$\beta>1/3$, the optimal schedule becomes a routing schedule, i.e., the source
sends all the information to relay $1$, relay $1$ sends it to relay $2$ and
relay $2$ sends it to the destination.

Figure 3: Change in the approximate capacity with respect to $\beta$, for
$d=200\sqrt{2}$ and $a=2$.

######  Remark 3.

Intuitively, one would expect that as the distance between the source and
destination increases, the relays would try to form a route (line network)
between the source and destination in order to mitigate the effect of path-
loss. Theorem 1 can be viewed as a sufficient condition on the distance for
which such an approach is no longer the optimal. In fact it is not difficult
to show analytically that for $d\geq\gamma^{1/a}/3$, the single route (line
network) with $d_{10}=d_{21}=d_{32}=d/3$ shown in Fig. 4 outperforms the
topology suggested by Theorem 1. Our evaluations at different distances, shown
in Fig. 5, also suggest that this critical bound on $d$ holds even when the
approximate capacity is found without the approximation in (4).

Figure 4: The line network with equal spacing.

Figure 5: Comparison between the approximate capacity of the topology proposed
in Theorem 1 and the line network with equal spacing between nodes when $a=2$.

##  IV Proof of Theorem 1

We start this section by giving an outline of the key steps in the proof of
Theorem 1, before delving into the details of the proof in the following
subsections.

###  IV-A Proof Outline

[1. Projected Topologies] The first step in proving Theorem 1 is to observe
that for any network topology, projecting the topology on the axis connecting
the source and destination, can only improve the approximate capacity since
the distance between any two nodes in the network does not increase and as a
result the approximate capacity from LP P3 cannot decrease. Thus in the
remainder of the proof, we will focus our attention on the network topologies
where the y-coordinates of the two relays are set to zero. For the example
topology shown in Fig. 2, its projected counterpart is shown in Fig. 6.

Figure 6: Projected topology for the topology shown in Fig. 2.

To ease the representation of such topologies, we define the distances between
the nodes in the network using fractions $\beta_{1}$ and $\beta_{2}$ of the
distance $d$ between the source and destination where
$\beta_{1},~{}\beta_{2}\in[0,1]$. In particular, the two relays are assumed to
be located at the coordinates $(\beta_{1}d,0)$ and $(d(1-\beta_{2}),0)$,
respectively where $\beta_{1}d\leq d-\beta_{2}d$. For the example topology in
Fig. 6, $d=100$, $\beta_{1}d=20$ and $\beta_{2}d=25$.

[2. Symmetric Networks] The next step in proving Theorem 1 is to leverage the
following lemma.

######  Lemma 1.

For a projected asymmetric network as in Fig. 6, we can always find a
projected symmetric network ($\beta_{1}^{\prime}=\beta_{2}^{\prime}=\beta$)
that achieves at least the same approximate capacity.

###### Proof.

The proof is delegated to Appendix A. ∎

Therefore in the remainder of the proof of Theorem 1, we will focus on
projected symmetric network topologies where we use fraction $\beta\in[0,1/2]$
of the distance $d$ to define the distances between nodes as follows.

$\displaystyle d_{1,0}=d_{3,2}$ $\displaystyle=\beta d,$ (6) $\displaystyle
d_{2,0}=d_{3,1}$ $\displaystyle=(1-\beta)d,$ $\displaystyle d_{1,2}=d_{2,1}$
$\displaystyle=(1-2\beta)d,$ $\displaystyle d_{3,0}$ $\displaystyle=d.$

From this, it follows that the link capacities can be written as follows by
using the channel model in (4).

$\displaystyle\ell_{1,0}=\ell_{3,2}=\ell_{1}$
$\displaystyle=\log\left(\frac{\gamma}{\beta^{a}d^{a}}\right),$ (7)
$\displaystyle\ell_{2,0}=\ell_{3,1}=\ell_{2}$
$\displaystyle=\log\left(\frac{\gamma}{(1-\beta)^{a}d^{a}}\right),$
$\displaystyle\ell_{1,2}=\ell_{2,1}=\ell_{3}$
$\displaystyle=\log\left(\frac{\gamma}{(1-2\beta)^{a}d^{a}}\right),$
$\displaystyle\ell_{3,0}=\ell_{4}$
$\displaystyle=\log\left(\frac{\gamma}{d^{a}}\right).$

[3. Properties of optimal solution for each topology] Next, we prove that for
the class of projected symmetric topologies described in the previous step,
there always exists an optimal solution for the LP P3 in (II) where: $(i)$ the
link activation times are symmetric; and $(ii)$ the source and destination do
not need to directly communicate. This is presented by the following lemma.

######  Lemma 2.

Consider a 2-relay Gaussian FD 1-2-1 network, with source and destination at
$(0,0)$ and $(d,0)$, respectively. Assume that for some $\beta\in[0,1/2]$, the
two relays are located at the coordinates $(\beta d,0)$ and $((1-\beta)d,0)$,
respectively, then there exists an optimal solution for LP P3 that satisfies
the following properties:

$\displaystyle(a)\quad\begin{aligned}
\lambda_{\ell_{1,0}}=\lambda_{\ell_{3,2}}=\lambda_{1},\\\
\lambda_{\ell_{2,0}}=\lambda_{\ell_{3,1}}=\lambda_{2},\end{aligned}$ (8)
$\displaystyle(b)\quad\begin{aligned} \lambda_{\ell_{1,2}}=0,\\\
\lambda_{2}+\lambda_{\ell_{2,1}}=1,\end{aligned}$ (9)
$\displaystyle(c)\quad\begin{aligned} \lambda_{\ell_{3,0}}=0,\\\
\lambda_{1}+\lambda_{2}=1.\end{aligned}$ (10)

###### Proof.

The proof is delegated to Appendix B. ∎

Based on Lemma 2 and the definition of link capacities in (7), it follows that
LP P3 is equivalent to the following LP.

$\displaystyle\ \rm{P4:}\ \macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}=\max_{\lambda,\alpha}\alpha$ $\displaystyle({\rm P4}a)\
\lambda_{1}+\lambda_{2}=1,$ $\displaystyle({\rm P4}b)\
\lambda_{2}+\lambda_{3}=1,$ $\displaystyle({\rm P4}c)\
\lambda_{1},\lambda_{2},\lambda_{3}\geq 0,$ (11) $\displaystyle({\rm P4}d)\
\alpha\leq\lambda_{2}\ell_{2}+\lambda_{1}\ell_{1}=\lambda_{2}\ell_{2}+(1-\lambda_{2})\ell_{1},$
$\displaystyle({\rm P4}e)\
\alpha\leq\lambda_{1}\ell_{1}+\lambda_{2}\ell_{2}=(1-\lambda_{2})\ell_{1}+\lambda_{2}\ell_{2},$
$\displaystyle({\rm P4}f)\
\alpha\leq\lambda_{3}\ell_{3}+2\lambda_{2}\ell_{2}=(1-\lambda_{2})\ell_{3}+2\lambda_{2}\ell_{2},$
$\displaystyle({\rm P4}g)\ \alpha\leq
2\lambda_{1}\ell_{1}=2(1-\lambda_{2})\ell_{1},$

where $\ell_{1}$, $\ell_{2}$ and $\ell_{3}$ are defined as in (7), and
$\lambda_{3}=\lambda_{\ell_{2,1}}$.

[4. Proving Theorem 1 for different ranges of $\beta$] The LP P4 will be the
central starting point for the remainder of the proof. We will consider
further sub-classes of our projected topologies depending on the value of
$\beta\in(0,1/2]$. In particular, we consider the following two categories:

$\displaystyle{\rm\bf(Category\ 1)}$
$\displaystyle:\quad\frac{d}{\gamma^{\frac{1}{a}}}<\beta\leq 1/2,$ (12)
$\displaystyle{\rm\bf(Category\ 2)}$ $\displaystyle:\quad
0<\beta\leq\frac{d}{\gamma^{\frac{1}{a}}}.$

For each of these two categories, we will follow a different approach in order
to show that there does not exist a feasible solution for LP P4 such that its
objective function is greater than or equal to ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}=2\log\left(\gamma/d^{a}\right)$.

The details of the proof for each category are described in the following
subsections.

###  IV-B Proof for Category 1

To prove that Theorem 1 for Category 1 of $\beta$ values in (12), it is
sufficient to show that for $\beta>d/(\gamma^{1/a})$, the RHS of $({\rm P4}d)$
in (IV-A) is smaller than ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$.

We prove this by contradiction. Let us assume that there does exist a value of
$\beta>d/(\gamma^{1/a})$ and $\lambda_{2}\in[0,1]$ such that the RHS of $({\rm
P4}d)$ is greater than or equal to ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$, i.e., $\exists\beta$ such that

$\displaystyle{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}\leq\text{RHS $({\rm P4}d)$
}=\lambda_{2}\ell_{2}+(1-\lambda_{2})\ell_{1}$
$\displaystyle=\lambda_{2}\log\left(\frac{\gamma}{(1-\beta)^{a}d^{a}}\right)+(1-\lambda_{2})\log\left(\frac{\gamma}{\beta^{a}d^{a}}\right)$
$\displaystyle=\log\left(\frac{\gamma}{d^{a}}\right)-\lambda_{2}\log\left((1-\beta)^{a}\right)-(1-\lambda_{2})\log\left(\beta^{a}\right),$
(13)

With rearrangement of terms (recall the definition of ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$ in Corollary 1), and exploiting the fact that the logarithm
function is monotonically increasing, the above constraint can be equivalently
rewritten as

$\displaystyle
d\geq\underbrace{\gamma^{\frac{1}{a}}\beta(1-\beta)^{\lambda_{2}}\beta^{-\lambda_{2}}}_{g(\lambda_{2})}.$
(14)

From basic calculus, it is not difficult to verify that the derivative of the
function $g(\lambda_{2})$ is non-negative, for all $\beta\in(0,1/2]$, and thus
$g(\lambda_{2})$ is monotonically increasing in $\lambda_{2}$. Additionally,
since $\lambda_{2}$ is a non-negative variable in LP P4 (see the constraint
$({\rm P4}c)$), then (14) would imply that

$\displaystyle d\geq g(0)=\gamma^{\frac{1}{a}}\beta,$ (15)

which contradicts our assumption that $\beta>d/(\gamma^{1/a})$.

Thus, we conclude that for all values of $\beta>d/(\gamma^{1/a})$, there does
not exist a feasible solution in LP P4, such that the RHS of $({\rm P4}d)$ is
greater than or equal to ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$. Thus, we have that

$\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}\leq\max_{\lambda_{2}}\text{RHS $({\rm P4}d)$}<{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}.$

The concludes the proof for Category 1.

###  IV-C Proof for Category 2

To prove Theorem 1 for Category 2 topologies, we aim to show that for
$0<\beta\leq d/\gamma^{\frac{1}{a}}$, any feasible solution for P4 will have
either the RHS of $({\rm P4}d)$ or the RHS of $({\rm P4}f)$ less than
${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$. This statement is summarized by the following lemma which is
proved in Appendix C.

######  Lemma 3.

If $\frac{\gamma}{d^{a}}>3^{a}$ and $0<\beta\leq d/\gamma^{\frac{1}{a}}$, then
$\forall\lambda_{2}\in[0,1]$, we have that

$\displaystyle{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}>\min\left\\{\underbrace{\lambda_{2}\ell_{2}+(1-\lambda_{2})\ell_{1}}_{\text{RHS
$({\rm
P4}d)$}},\underbrace{(1-\lambda_{2})\ell_{3}+2\lambda_{2}\ell_{2}}_{\text{RHS
(${\rm P4}f)$}}\right\\}$ (16)

where ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$ is given in Corollary 1 and $\ell_{1}$, $\ell_{2}$ and
$\ell_{3}$ are as in (7).

The result for Category 2 is the direct consequence of Lemma 3 since the
approximate capacity in P4 is equal to the minimum of RHS of the constraints
$({\rm P4}d-{\rm P4}g)$. This concludes the proof of Theorem 1.

##  V Conclusion

In this paper, we studied the optimization of relay placement in a 1-2-1 FD
network with $2$ relay nodes in order to maximize the approximate capacity of
the network. Through our analysis, we observed that the approximate capacity
is maximized by placing the relay nodes as close as possible to the source and
the destination, respectively. This serves as a first step in understanding
optimal topology design in directional networks and can pave the way towards
understanding and optimizing relay placement for more complex directional
networks.

## References

  * [1] A. Nordrum, “Facebook pushes networking tech: The company’s terragraph technology will soon be available in commercial gear - [news],” _IEEE Spectrum_ , vol. 56, pp. 8–9, 04 2019.
  * [2] L. Zhang, H. Zhao, S. Hou, Z. Zhao, H. Xu, X. Wu, Q. Wu, and R. Zhang, “A survey on 5g millimeter wave communications for uav-assisted wireless networks,” _IEEE Access_ , vol. 7, pp. 117 460–117 504, 2019\.
  * [3] Y. H. Ezzeldin, M. Cardone, C. Fragouli, and G. Caire, “Gaussian 1-2-1 networks: Capacity results for mmwave communications,” _IEEE Transactions on Information Theory_ , vol. 67, no. 2, pp. 961–990, 2021.
  * [4] L. Wang, W. Su, J. Huang, A. Chen, and C. Chang, “Optimal relay location in multi-hop cellular systems,” in _2008 IEEE Wireless Communications and Networking Conference_ , 2008, pp. 1306–1310.
  * [5] L. Xu, H.-W. Zhang, X.-h. Li, and X.-L. Wu, “Optimum relay location in cooperative communication networks with single af relay,” _IJCNS_ , vol. 4, pp. 147–151, 06 2011.
  * [6] H. A. Ara, M. R. Zahabi, and V. Meghdadi, “Joint power and location optimization of relay for amplify-and-forward cooperative relaying,” in _2018 International Conference on Internet of Things, Embedded Systems and Communications (IINTEC)_ , 2018, pp. 97–102.
  * [7] S. A. K. Tanoli, S. A. Shah, M. B. Khan, F. Nawaz, A. Hussain, A. Y. Al-Dubai, I. Khan, S. Y. Shah, and A. Alsarhan, “Impact of relay location of stanc bi-directional transmission for future autonomous internet of things applications,” _IEEE Access_ , vol. 8, pp. 29 395–29 406, 2020\.
  * [8] R. Appuswamy, E. Atsan, C. Fragouli, and M. Franceschetti, “On relay placement for deterministic line networks,” in _2010 Third IEEE International Workshop on Wireless Network Coding_ , 2010, pp. 1–9.
  * [9] G. Zheng, C. Hua, R. Zheng, and Q. Wang, “A robust relay placement framework for 60ghz mmwave wireless personal area networks,” in _2013 IEEE Global Communications Conference (GLOBECOM)_ , 2013, pp. 4816–4822.
  * [10] L. Kong, L. Ye, F. Wu, M. Tao, G. Chen, and A. V. Vasilakos, “Autonomous relay for millimeter-wave wireless communications,” _IEEE Journal on Selected Areas in Communications_ , vol. 35, no. 9, pp. 2127–2136, 2017\.

##  Appendix A Proof of Lemma 1

Here, we prove that for an asymmetric network as in Fig. 6, we can find a
symmetric network that gives at least the same capacity. The proof consists of
three main steps.

In the first step, we prove that the following result holds in asymmetric
networks.

$\displaystyle\lambda_{\ell_{3,1}}+\lambda_{\ell_{2,1}}=1,$ (17)
$\displaystyle\lambda_{\ell_{2,0}}+\lambda_{\ell_{2,1}}=1.$

As it was described in the first step of the proof outline, we define the
distances between the nodes in the network using fractions $\beta_{1}$ and
$\beta_{2}$ of the distance $d$ between the source and destination where
$\beta,~{}\beta_{1}\in[0,1]$. In the second step, we prove that when
$\beta_{1}<\beta_{2}$, $F_{3,1}<F_{2,0}$ in the optimal solution and through
using this property, we show that there exists a symmetric network that gives
at least the same capacity as the asymmetric network.

In the third step, we prove that when $\beta_{1}>\beta_{2}$, $F_{3,1}>F_{2,0}$
in the optimal solution and through leveraging this property, we again show
that there exists a symmetric network that achieves at least the same capacity
as the asymmetric network.

We start with the first step by considering an optimal solution where both
$\lambda_{\ell_{3,1}}+\lambda_{\ell_{2,1}}<1$ and
$\lambda_{\ell_{2,0}}+\lambda_{\ell_{2,1}}<1$. In this case, we can increase
$\lambda_{\ell_{2,1}}$ until one of these summations becomes equal to $1$
while fixing all other variables from the optimal solution. This new set of
variables satisfies the constraints in LP P1 and the same capacity is
achieved. Therefore, there exists an optimal solution where one of these
summations is equal to $1$. Now, consider the case where an optimal solution
satisfies $\lambda_{\ell_{3,1}}+\lambda_{\ell_{2,1}}=1$ and
$\lambda_{\ell_{2,0}}+\lambda_{\ell_{2,1}}<1$. We can represent these
activation times as follows.

$\displaystyle\lambda_{\ell_{3,1}}=\lambda,$ (18)
$\displaystyle\lambda_{\ell_{2,1}}=1-\lambda,$
$\displaystyle\lambda_{\ell_{2,0}}<\lambda.$

We note that in the optimal solution, $\lambda_{\ell_{1,2}}=0$ since there
exists an optimal solution where $F_{1,2}=0$. Consider an optimal solution
where $F_{1,2}\neq 0$. Due to the constraint $({\rm P1}b)$ in (II) for the
second relay,

$F_{1,2}=F_{2,1}+F_{2,0}-F_{3,2},$

While keeping other variables same, we can decrease $F_{1,2}$ to zero by
reducing $F_{2,1}+F_{2,0}$ by the same amount without affecting $F_{3,2}$. In
this case, we obtain another feasible solution that achieves the same
capacity.

Now, for the activation times given in (18), there are two possible cases:
$\lambda_{\ell_{30}}\geq\lambda-\lambda_{\ell_{2,0}}$ or
$\lambda_{\ell_{30}}<\lambda-\lambda_{\ell_{2,0}}$.

In the first case, we can perform the following modifications on the
activation times.

$\displaystyle\lambda^{\prime}_{\ell_{2,0}}=\lambda,\qquad\lambda^{\prime}_{\ell_{3,0}}=\lambda_{\ell_{3,0}}-(\lambda-\lambda_{\ell_{2,0}}),$
(19)
$\displaystyle\lambda^{\prime}_{\ell_{1,0}}=\lambda_{\ell_{1,0}},\qquad\lambda^{\prime}_{\ell_{3,2}}=\lambda_{\ell_{3,2}}+(\lambda-\lambda_{\ell{2,0}}),$
$\displaystyle\lambda^{\prime}_{\ell_{3,1}}=\lambda,\qquad\lambda^{\prime}_{\ell_{1,2}}=0,\qquad\lambda^{\prime}_{\ell_{2,1}}=1-\lambda.$

This new set of activation times satisfy the constraints in LP P1. If
$F_{3,0}\leq\lambda^{\prime}_{\ell_{3,0}}\ell_{3,0}$, we can send the same
flows and reach the same capacity. If
$F_{3,0}>\lambda^{\prime}_{\ell_{3,0}}\ell_{3,0}$, we can modify the flows as
follows.

$\displaystyle F^{\prime}_{3,0}=\lambda^{\prime}_{\ell_{3,0}}\ell_{3,0},$ (20)
$\displaystyle
F^{\prime}_{2,0}=F_{2,0}+F_{3,0}-\lambda^{\prime}_{\ell_{3,0}}\ell_{3,0},$
$\displaystyle
F^{\prime}_{3,2}=F_{3,2}+F_{3,0}-\lambda^{\prime}_{\ell_{3,0}}\ell_{3,0}.$

The remaining flows stay same and the same capacity in LP P1 is achieved. We
note that since the decrease in $\lambda_{\ell_{3,0}}$ is equal to the
increase in $\lambda_{\ell_{2,0}}$ and $\lambda_{\ell_{3,2}}$, and the link
capacity $\ell_{3,0}$ is the smallest link capacity in the network, these
modified flows still satisfy the capacity constraints $({\rm P1}a)$ in LP P1.

In the second case, we have
$\lambda_{\ell_{3,0}}<\lambda-\lambda_{\ell_{2,0}}$. Therefore, we can modify
the activation times as follows.

$\displaystyle\lambda^{\prime}_{\ell_{2,0}}=\lambda_{\ell_{2,0}}+\lambda_{\ell_{3,0}},$
(21)
$\displaystyle\lambda^{\prime}_{\ell_{3,1}}=\lambda_{\ell_{2,0}}+\lambda_{\ell_{3,0}},$
$\displaystyle\lambda^{\prime}_{\ell_{3,2}}=\lambda_{\ell_{3,2}}+\lambda_{\ell_{3,0}}+\lambda_{\ell_{3,1}}-\lambda^{\prime}_{\ell_{3,1}},$
$\displaystyle\lambda^{\prime}_{\ell_{1,0}}=\lambda_{\ell_{1,0}}\qquad\lambda^{\prime}_{\ell_{3,0}}=0,$
$\displaystyle\lambda^{\prime}_{\ell_{1,2}}=0\qquad\lambda^{\prime}_{\ell_{2,1}}=1-\lambda^{\prime}_{\ell_{3,1}}.$

If $F_{3,0}\leq\lambda^{\prime}_{\ell_{3,0}}\ell_{3,0}$ and
$F_{3,1}\leq\lambda^{\prime}_{\ell_{3,1}}\ell_{3,1}$, we can use the same flow
variables and achieve the same capacity. Otherwise, the flows through the
paths $p_{1}$ and/or $p_{2}$ need to decrease, respectively where $p_{1}$ is
the direct path between the source and destination and $p_{2}$ is the path
going from the source to the destination while passing through relay $1$.
However, we can compensate the decrease in paths $p_{1}$ and $p_{2}$ by
sending additional flows through the paths $p_{3}$ and $p_{4}$, respectively
where $p_{3}$ is the path that goes from the source to the destination while
passing through relay $2$ and $p_{4}$ is the path that goes from the source to
the destination while passing through both relays. For example, if we have
$F_{3,0}>\lambda^{\prime}_{\ell_{3,0}}\ell_{3,0}$ and
$F_{3,1}>\lambda^{\prime}_{\ell_{3,1}}\ell_{3,1}$, we can modify the flows as
follows.

$\displaystyle F^{\prime}_{3,0}=0,\qquad
F^{\prime}_{3,1}=\lambda^{\prime}_{\ell_{3,1}}\ell_{3,1},$ (22) $\displaystyle
F^{\prime}_{1,0}=F_{1,0},\qquad F^{\prime}_{2,0}=F_{2,0}+F_{3,0},$
$\displaystyle F^{\prime}_{1,2}=0,\qquad
F^{\prime}_{2,1}=F_{2,1}+F_{3,1}-F^{\prime}_{3,1}$ $\displaystyle
F^{\prime}_{3,2}=F_{3,2}+F_{3,0}+F_{3,1}-F^{\prime}_{3,1}$

This new set of variables satisfies the constraints in LP P1 and achieve the
same capacity. Therefore, in one of the optimal solutions, the equalities in
(17) holds. We can perform similar steps for the case
$\lambda_{\ell_{3,1}}+\lambda_{\ell_{2,1}}<1$ and
$\lambda_{\ell_{2,0}}+\lambda_{\ell_{2,1}}=1$, and arrive the same conclusion.
Therefore, in asymmetric networks, the following holds.

$\displaystyle\lambda_{\ell_{3,1}}=\lambda_{\ell_{2,0}}.$ (23)

This completes the proof of the first step.

In the second step, we leverage the property in (23) to show that
$F_{3,1}<F_{2,0}$ in the optimal solution when $\beta_{1}<\beta_{2}$ in an
asymmetric network. We represent the activation times as follows.

$\displaystyle\lambda_{\ell_{3,1}}=\lambda_{\ell_{2,0}}=\lambda,$
$\displaystyle\lambda_{\ell_{2,1}}=1-\lambda,$
$\displaystyle\lambda_{\ell_{1,2}}=0.$

It is not difficult to see that in the optimal solution,
$\lambda_{\ell_{3,0}}+\lambda_{\ell_{3,1}}+\lambda_{\ell_{3,2}}=1$ and
$\lambda_{\ell_{3,0}}+\lambda_{\ell_{2,0}}+\lambda_{\ell_{1,0}}=1$. Consider
there exists an optimal solution such that
$\lambda_{\ell_{3,0}}+\lambda_{\ell_{3,1}}+\lambda_{\ell_{3,2}}<1$ and
$\lambda_{\ell_{3,0}}+\lambda_{\ell_{2,0}}+\lambda_{\ell_{1,0}}<1$. While
fixing other variables, if we increase $\lambda_{\ell_{3,2}}$ and
$\lambda_{\ell_{1,0}}$ until the summations become equal to $1$, this will
give another feasible solution that achieves the same capacity. As a result,
there exists an optimal solution where
$\lambda_{\ell_{3,0}}+\lambda_{\ell_{3,1}}+\lambda_{\ell_{3,2}}=1$ and
$\lambda_{\ell_{3,0}}+\lambda_{\ell_{2,0}}+\lambda_{\ell_{1,0}}=1$. Therefore,

$\lambda_{\ell_{3,2}}=\lambda_{\ell_{1,0}}=1-\lambda-\lambda_{\ell_{3,0}}.$

In order to show that $F_{3,1}<F_{2,0}$ in the optimal solution, we will show
that $F_{2,0}$ satisfies the capacity constraint $({\rm P1}a)$ in (II) with
equality in the optimal solution, i.e., $F_{2,0}=\lambda\ell_{2,0}$. Since
$\ell_{2,0}>\ell_{3,1}$ and $F_{3,1}\leq\lambda\ell_{3,1}$, this guarantees
that $F_{3,1}<F_{2,0}$ in the optimal solution.

We start with considering an optimal solution where
$F_{2,0}<\lambda\ell_{2,0}$. In order to prove the argument, we will evaluate
two cases. In the first case,
$F_{3,2}+b_{1}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{3,2}$ and in the
second case, $F_{3,2}+b_{1}>(1-\lambda-\lambda_{\ell_{3,0}})\ell_{3,2}$ where
$b_{1}=\lambda\ell_{2,0}-F_{2,0}$.

In the first case, we can use contradiction to prove the argument. Consider
$F_{2,0}<\lambda\ell_{2,0}$ in the optimal solution. We can modify the flow
variables as follows.

$\displaystyle F^{\prime}_{2,0}=\lambda\ell_{2,0},$ (24) $\displaystyle
F^{\prime}_{3,2}=F_{3,2}+b_{1}.$

where $b_{1}=\lambda\ell_{2,0}-F_{2,0}$ and the remaining variables stay same.

With this new set of variables, we have another feasible solution that
achieves a higher capacity than the optimal solution since $F_{3,2}$
increases, $F_{3,1}$ and $F_{3,0}$ stay same. This creates a contradiction,
therefore, we argue that an optimal solution satisfies
$F_{2,0}=\lambda\ell_{2,0}$ if $F^{\prime}_{3,2}$ satisfies the capacity
constraint $({\rm P1}a)$ in (II), i.e.,

$F_{3,2}+b_{1}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{3,2}.$

In the second case, we have
$F_{3,2}+b_{1}>(1-\lambda-\lambda_{\ell_{3,0}})\ell_{3,2}$. We can decrease
$\lambda$ to $\lambda^{\prime}_{1}$ where $\lambda^{\prime}_{1}$ satisfies

$\displaystyle
F_{3,2}+b^{\prime}_{1}=(1-\lambda^{\prime}_{1}-\lambda_{\ell_{3,0}})\ell_{3,2},$
(25)
$\displaystyle\implies\lambda^{\prime}_{1}=\frac{\ell_{3,2}-\lambda_{\ell_{3,0}}\ell_{3,2}+F_{2,0}-F_{3,2}}{\ell_{2,0}+\ell_{3,2}}.$

where $b^{\prime}_{1}=\lambda^{\prime}_{1}\ell_{2,0}-F_{2,0}>0$. We should
note that $\lambda^{\prime}_{1}$ in (25) is a feasible activation time since
$F_{3,2}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{3,2}$. Now, we need to
consider two cases: $F_{3,1}\leq\lambda^{\prime}_{1}\ell_{3,1}$ and
$F_{3,1}>\lambda^{\prime}_{1}\ell_{3,1}$.

In the first case, we can use contradiction to prove our argument. First, we
modify the flow variables as follows.

$\displaystyle F^{\prime}_{2,0}=\lambda^{\prime}_{1}\ell_{2,0},$ (26)
$\displaystyle F^{\prime}_{3,2}=F_{3,2}+b^{\prime}_{1}.$

When the remaining flow variables stay same, this new set of variables is a
feasible solution and achieves a higher capacity than the optimal solution
since $F_{3,2}$ increases, $F_{3,1}$ and $F_{3,0}$ stay same. Therefore, this
creates a contradiction and we argue that $F_{2,0}$ satisfies capacity
constraint $({\rm P1}a)$ in LP P1 in an optimal solution if
$F_{3,1}\leq\lambda^{\prime}_{1}\ell_{3,1}$.

In the second case ($F_{3,1}>\lambda^{\prime}_{1}\ell_{3,1}$), we modify the
flow variables as follows.

$\displaystyle F^{\prime}_{3,1}=\lambda^{\prime}_{1}\ell_{3,1},$ (27)
$\displaystyle F^{\prime}_{2,0}=\lambda^{\prime}_{1}\ell_{2,0},$
$\displaystyle F^{\prime}_{1,0}=F_{2,1}+F^{\prime}_{3,1},$ $\displaystyle
F^{\prime}_{3,2}=F_{3,2}+b^{\prime}_{1}.$

The remaining flow variables stay same. This new set of variables still
satisfies the constraints in LP P1 and achieves a higher capacity since the
increase in $F_{3,2}$ is higher than the decrease in $F_{3,1}$.

$\displaystyle
F_{3,1}-F^{\prime}_{3,1}\leq(\lambda-\lambda^{\prime}_{1})\ell_{3,1}$ (28)
$\displaystyle
F^{\prime}_{3,2}-F_{3,2}\geq(\lambda-\lambda^{\prime}_{1})\ell_{3,2}$

Since $\ell_{3,2}>\ell_{3,1}$, this new set of variables achieve a higher
capacity and again, this creates a contradiction. Therefore, we argue that in
an optimal solution, $F_{2,0}$ satisfies the capacity constraint with
equality. As a result, we claim that

$F_{3,1}<F_{2,0}\qquad\text{if}~{}\beta_{1}<\beta_{2}$ (29)

Through using the property in (29), we can prove that there exists a symmetric
network that achieves at least the same capacity as the asymmetric network.
Consider we have an asymmetric network as in Fig. 6 and $\beta_{1}<\beta_{2}$.
Now, we bring relay $1$ closer to relay $2$ such that
$\beta^{\prime}_{1}=\beta_{2}$. We next show that with this symmetric network,
we can achieve the same capacity. Towards this end, we first write the
relationships between variables in an optimal solution for the asymmetric
network based on constraints in LP P1, proofs given above and the property in
(29).

$\displaystyle\lambda_{\ell_{3,1}}=\lambda_{\ell_{2,0}}=\lambda,$ (30)
$\displaystyle\lambda_{\ell_{1,0}}=\lambda_{\ell_{3,2}}=1-\lambda-\lambda_{\ell_{3,0}},$
$\displaystyle\lambda_{\ell_{2,1}}=1-\lambda,$
$\displaystyle\lambda_{\ell_{1,2}}=0.$ $\displaystyle
F_{3,1}<F_{2,0}=\lambda\ell_{2,0},$ (31) $\displaystyle
F_{1,0}=F_{3,1}+F_{2,1}<F_{3,2},$ $\displaystyle
F_{3,2}=F_{2,0}+F_{2,1}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{3,2}.$

Now, we bring relay $1$ closer to relay $2$ such that
$\beta^{\prime}_{1}=\beta_{2}$. In this case, the distances between nodes are
modified as follows.

$\displaystyle d^{\prime}_{3,1}=d_{2,0},$ $\displaystyle
d^{\prime}_{1,0}=d_{3,2},$ $\displaystyle d^{\prime}_{2,1}=d-2\beta_{2}d.$

Through the path loss model in (4),

$\displaystyle\ell^{\prime}_{3,1}=\ell_{2,0},$
$\displaystyle\ell^{\prime}_{1,0}=\ell_{3,2},$
$\displaystyle\ell^{\prime}_{2,1}>\ell_{2,1}.$

Now, we use the same activation times $\lambda_{\ell_{j,i}}$ as in the
asymmetric network. Thus, we have the following capacity constraints on
$F_{3,1}$ and $F_{1,0}$ in the symmetric network.

$\displaystyle F_{3,1}\leq\lambda\ell_{2,0},$ (32) $\displaystyle
F_{1,0}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{3,2},$ $\displaystyle
F_{2,1}\leq(1-\lambda)\ell^{\prime}_{2,1}.$

These capacity constraints are satisfied due to the relationship given in
(31). Therefore, we can use the same activation times and flow variables in
this symmetric network, and this gives a feasible solution that achieves the
same capacity as the asymmetric network. This concludes the proof for the case
where $\beta_{1}<\beta_{2}$.

In the third step, we show that $F_{3,1}>F_{2,0}$ in the optimal solution of
an asymmetric network when $\beta_{1}>\beta_{2}$. Then, by leveraging this
property, we show that there exists a symmetric network that achieves at least
the same capacity as the asymmetric network.

We first represent the optimal activation times in an asymmetric network as
follows based on our result in (23).

$\displaystyle\lambda_{\ell_{3,1}}=\lambda_{\ell_{2,0}}=\lambda,$ (33)
$\displaystyle\lambda_{\ell_{1,0}}=\lambda_{\ell_{3,2}}=1-\lambda-\lambda_{\ell_{3,0}},$
$\displaystyle\lambda_{\ell_{2,1}}=1-\lambda,$
$\displaystyle\lambda_{\ell_{1,2}}=0.$

In order to show that $F_{3,1}>F_{2,0}$ in the optimal solution, we will show
that $F_{3,1}$ satisfies the capacity constraint $({\rm P1}a)$ in LP P1 with
equality in the optimal solution, i.e., $F_{3,1}=\lambda\ell_{3,1}$. Since
$\ell_{2,0}<\ell_{3,1}$ and $F_{2,0}\leq\lambda\ell_{2,0}$, this guarantees
that $F_{2,0}<F_{3,1}$ in the optimal solution.

Consider there is an optimal solution where $F_{3,1}<\lambda\ell_{3,1}$.
Through using contradiction, we show that $F_{3,1}=\lambda\ell_{3,1}$. Now, we
consider two cases:
$F_{1,0}+b_{2}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{1,0}$ and
$F_{1,0}+b_{2}>(1-\lambda-\lambda_{\ell_{3,0}})\ell_{1,0}$ where
$b_{2}=\lambda\ell_{3,1}-F_{3,1}$.

In the first case, we modify the flow variables as follows.

$\displaystyle F^{\prime}_{3,1}=\lambda\ell_{3,1},$ (34) $\displaystyle
F^{\prime}_{1,0}=F_{1,0}+b_{2}.$

The remaining variables stay same. This new set of variables is still feasible
in LP P1 and it achieves a higher capacity than the optimal solution due to
increase in $F_{3,1}$ and $F_{1,0}$. Since this creates a contradiction, we
argue that an optimal solution satisfies $F_{3,1}=\lambda\ell_{3,1}$ if
$F^{\prime}_{1,0}$ satisfies the capacity constraint, i.e.,
$F_{1,0}+b_{2}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{1,0}$.

In the second case, we have
$F_{1,0}+b_{2}>(1-\lambda-\lambda_{\ell_{3,0}})\ell_{1,0}$. We can decrease
$\lambda$ to $\lambda^{\prime}_{2}$ where $\lambda^{\prime}_{2}$ satisfies

$\displaystyle
F_{1,0}+b^{\prime}_{2}=(1-\lambda^{\prime}_{2}-\lambda_{\ell_{3,0}})\ell_{1,0},$
(35)
$\displaystyle\implies\lambda^{\prime}_{2}=\frac{\ell_{1,0}-\lambda_{\ell_{3,0}}\ell_{1,0}+F_{3,1}-F_{1,0}}{\ell_{3,1}+\ell_{1,0}}.$

where $b^{\prime}_{2}=\lambda^{\prime}_{2}\ell_{3,1}-F_{3,1}>0$.

We should note that $\lambda^{\prime}_{2}$ in (35) is a feasible activation
time since $F_{1,0}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{1,0}$. Now, we
consider two cases: $F_{2,0}\leq\lambda^{\prime}_{2}\ell_{2,0}$ and
$F_{2,0}>\lambda^{\prime}_{2}\ell_{2,0}$.

In the first case, we modify the following flow variables.

$\displaystyle F^{\prime}_{3,1}=\lambda^{\prime}_{2}\ell_{3,1},$ (36)
$\displaystyle F^{\prime}_{1,0}=F_{1,0}+b^{\prime}_{2}.$

When the remaining flow variables stay same, this new set of variables gives a
feasible solution for LP P1 and achieves a higher capacity than the optimal
solution due to increase in $F_{3,1}$. Therefore, this causes a contradiction
again and shows that $F_{3,1}$ satisfies the capacity constraint $({\rm P1}a)$
in (II) in an optimal solution.

In the second case, we modify the following flow variables.

$\displaystyle F^{\prime}_{2,0}=\lambda^{\prime}_{2}\ell_{2,0},$ (37)
$\displaystyle F^{\prime}_{3,1}=\lambda^{\prime}_{2}\ell_{3,1},$
$\displaystyle F^{\prime}_{3,2}=F^{\prime}_{2,0}+F_{2,1},$ $\displaystyle
F^{\prime}_{1,0}=F^{\prime}_{3,1}+F_{2,1}.$

The remaining variables stay same. This new set of variables gives a feasible
solution and achieves a higher capacity since the increase in $F_{1,0}$ is
larger than decrease in $F_{2,0}$.

$\displaystyle
F_{2,0}-F^{\prime}_{2,0}\leq(\lambda-\lambda^{\prime}_{2})\ell_{2,0},$ (38)
$\displaystyle
F^{\prime}_{1,0}-F_{1,0}\geq(\lambda-\lambda^{\prime}_{2})\ell_{1,0}.$

Since $\ell_{1,0}>\ell_{2,0}$, the capacity
$F_{3,0}+F_{3,1}+F_{3,2}=F_{1,0}+F_{2,0}+F_{3,0}$ increases. This creates a
contradiction because this new set of variables achieve a higher capacity than
the optimal solution for the asymmetric network. As a result, we claim that
the following holds in an asymmetric network when $\beta_{1}>\beta_{2}$.

$\displaystyle F_{2,0}<F_{3,1}.$ (39)

Through using the property in (39), we can prove that there exists a symmetric
network that gives at least the same capacity as the asymmetric network.
Consider we have an asymmetric network as in Fig. 6 and $\beta_{1}>\beta_{2}$.
Now, we bring relay $2$ closer to relay $1$ such that
$\beta_{1}=\beta^{\prime}_{2}$. We next show that with this symmetric network,
we can achieve the same capacity. Towards this end, we first write the
relationships between variables in an optimal solution for the asymmetric
network based on constraints in LP P1, proofs given above and the property in
(39).

$\displaystyle\lambda_{\ell_{3,1}}=\lambda_{\ell_{2,0}}=\lambda,$ (40)
$\displaystyle\lambda_{\ell_{1,0}}=\lambda_{\ell_{3,2}}=1-\lambda-\lambda_{\ell_{3,0}},$
$\displaystyle\lambda_{\ell_{2,1}}=1-\lambda,$
$\displaystyle\lambda_{\ell_{1,2}}=0.$ $\displaystyle
F_{2,0}<F_{3,1}=\lambda\ell_{3,1},$ (41) $\displaystyle
F_{3,2}=F_{2,0}+F_{2,1}<F_{1,0},$ $\displaystyle
F_{1,0}=F_{3,1}+F_{2,1}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{1,0}.$

Now, we bring relay $2$ closer to relay $1$ such that
$\beta_{1}=\beta^{\prime}_{2}$. In this case, the distances between nodes are
modified as follows.

$\displaystyle d^{\prime}_{2,0}=d_{3,1},$ $\displaystyle
d^{\prime}_{3,2}=d_{1,0},$ $\displaystyle d^{\prime}_{2,1}=d-2\beta_{1}d.$

Through the path loss model in (4),

$\displaystyle\ell^{\prime}_{2,0}=\ell_{3,1},$
$\displaystyle\ell^{\prime}_{3,2}=\ell_{1,0},$
$\displaystyle\ell^{\prime}_{2,1}>\ell_{2,1}.$

Now, we use the same activation times $\lambda_{\ell_{j,i}}$ as in the optimal
solution of the asymmetric network. Thus, we have the following capacity
constraints on $F_{2,0}$ and $F_{3,2}$ in the symmetric network.

$\displaystyle F_{2,0}\leq\lambda\ell_{3,1}$ (42) $\displaystyle
F_{3,2}\leq(1-\lambda-\lambda_{\ell_{3,0}})\ell_{1,0}$

These capacity constraints are satisfied due to the relationship given in
(41). Therefore, we can use the same activation times and flow variables in
this symmetric network, and this gives a feasible solution that achieves the
same capacity as the asymmetric network. This concludes the proof for the case
where $\beta_{1}>\beta_{2}$.

##  Appendix B Proof of Lemma 2

###  B-A Proof of the properties in (8)

Here, we prove this property for the symmetric projected networks, considered
in Lemma 2. From the symmetry property of the network, it is not difficult to
see that for any optimal solution $\\{\lambda_{\ell_{j,i}}\\}$ of the LP P3 in
(II), we can construct another optimal solution
$\\{\lambda^{\prime}_{\ell_{j,i}}\\}$ by setting

$\displaystyle\lambda^{\prime}_{\ell_{1,0}}$
$\displaystyle=\lambda_{\ell_{3,2}},\qquad\lambda^{\prime}_{\ell_{3,2}}=\lambda_{\ell_{1,0}},$
$\displaystyle\lambda^{\prime}_{\ell_{2,0}}$
$\displaystyle=\lambda_{\ell_{3,1}},\qquad\lambda^{\prime}_{\ell_{3,1}}=\lambda_{\ell_{2,0}},$
$\displaystyle\lambda^{\prime}_{\ell_{2,1}}$
$\displaystyle=\lambda_{\ell_{2,1}},\qquad\lambda^{\prime}_{\ell_{1,2}}=\lambda_{\ell_{1,2}},$
$\displaystyle\lambda^{\prime}_{\ell_{3,0}}$
$\displaystyle=\lambda_{\ell_{3,0}}.$

Now since the LP P4 has an affine objective function, then the midpoint
between $\lambda^{\prime}$ and $\lambda$ is also optimal. Thus, there exists
an optimal solution that satisfies the property in (8).

###  B-B Proof of the properties in (9)

We first note that the LP P3 and the LP P1 share the same $\lambda_{j,i}$
variables for the case $N=2$. Now, we focus on the case where $F_{1,2}\neq 0$
in the LP P3, since otherwise $\lambda_{1,2}$ can be pushed to zero without
consequence on the objective function is trivial. From the condition $({\rm
P1}b)$ in (II), we have the following for any feasible point

$F_{1,2}=F_{2,1}+F_{2,0}-F_{3,2},$

thus, we can reduce the flow $F_{1,2}$ to zero and equally reduce the flow of
the sum $F_{2,1}+F_{2,0}$ without affecting $F_{3,2}$. Thus, we arrive at
another feasible point with the same objective value while having $F_{1,2}=0$.
Reducing $\lambda_{1,2}$ subsequently still maintains a feasible point and
doesn’t affect the objective function.

For the proof of $\lambda_{2}+\lambda_{\ell_{2,1}}=1$, we assume that we have
an optimal solution for P3 in (II) satisfying the property (8) and that
$\lambda_{\ell_{1,2}}=0$ as proved above. From (8), we have that

$\displaystyle\lambda_{1}=\lambda_{\ell_{1,0}}=\lambda_{\ell_{3,2}},$
$\displaystyle\lambda_{2}=\lambda_{\ell_{3,1}}=\lambda_{\ell_{2,0}}.$

Now given the aforementioned optimal solution for P3, the only upper bounding
constraint we have on $\lambda_{\ell_{2,1}}$, is given by

$\lambda_{\ell_{2,1}}+\lambda_{2}\leq 1.$

While fixing all other variables from the optimal solution, it is not
difficult to see that increasing $\lambda_{\ell_{2,1}}$ (if needed) so that
the inequality is satisfied with equality leads to a feasible point with the
same objective function value as the optimal. Thus there exists an optimal
solution satisfying that $\lambda_{\ell_{2,1}}+\lambda_{2}=1$.

###  B-C Proof of the properties in (10)

In order to prove that the optimal solution satisfies $\lambda_{\ell_{3,0}}=0$
and $\lambda_{1}+\lambda_{2}=1$, we consider two cases:
$\ell_{2,1}\geq\ell_{1}$ and $\ell_{2,1}<\ell_{1}$ where $\ell_{1}$ is defined
in (7).

In the first case, we consider that there is an optimal solution
$\left\\{\lambda^{(1)}_{\ell_{j,i}}\right\\}$ and
$\left\\{F^{(1)}_{j,i}\right\\}$ for LP P1 in (II) such that

$\displaystyle\lambda_{1}^{(1)}+\lambda_{2}^{(1)}+\lambda_{\ell_{3,0}}^{(1)}=1,$
$\displaystyle\lambda_{2}^{(1)}+\lambda_{\ell_{2,1}}^{(1)}=1.$

where $\lambda_{1}$ and $\lambda_{2}$ are defined in (8), and we use the
properties in (8) and (9).

We note that there exists an optimal solution that satisfies
$\lambda_{1}^{(1)}+\lambda_{2}^{(1)}+\lambda_{\ell_{3,0}}^{(1)}\leq 1$
constraint in LP P1 with equality. Otherwise, we can increase
$\lambda^{(1)}_{\ell_{3,0}}$ until the constraint is satisfied with equality
while fixing other variables. In this case, it is clear that all constraints
in LP P1 are still satisfied by this new solution and the same capacity is
achieved.

Now, if we assume that there is an optimal solution where
$\lambda^{(1)}_{\ell_{3,0}}>0$, we can modify the activation times as follows.

$\displaystyle\lambda_{\ell_{3,0}}^{(2)}=0,$ (43)
$\displaystyle\lambda_{1}^{(2)}=\lambda_{1}^{(1)}+\lambda_{\ell_{3,0}}^{(1)}.$

The remaining activation times stay same. Moreover, we modify the flow
variables $F_{j,i}^{(1)}$ as follows.

$\displaystyle F_{1,0}^{(2)}=F_{1,0}^{(1)}+F_{3,0}^{(1)},$ (44) $\displaystyle
F_{2,1}^{(2)}=F_{2,1}^{(1)}+F_{3,0}^{(1)},$ $\displaystyle
F_{3,2}^{(2)}=F_{3,2}^{(1)}+F_{3,0}^{(1)},$ $\displaystyle F_{3,0}^{(2)}=0.$

The remaining flow variables stay same.

Through this modification, we reduce the flow of the direct link from the
source to the destination to zero and send the flow $F^{(1)}_{3,0}$ through
the path $p$ where $p$ is the path from the source to the destination and it
passes through both of the relays. It is not difficult to see that the
modified activation times still satisfy the constraints in (II) and the flow
conservation constraints $({\rm P1}b)$ are satisfied as well. We next show
that the following capacity constraints in $({\rm P1}a)$ for the modified flow
variables are still satisfied when $\ell_{2,1}\geq\ell_{1}$.

$\displaystyle
F_{1,0}^{(2)}=F_{1,0}^{(1)}+F_{3,0}^{(1)}\leq\lambda_{1}^{(1)}\ell_{1}+\lambda_{\ell_{3,0}}^{(1)}\ell_{3,0}\leq\lambda_{1}^{(2)}\ell_{1},$
(45) $\displaystyle
F_{3,2}^{(2)}=F_{3,2}^{(1)}+F_{3,0}^{(1)}\leq\lambda_{1}^{(1)}\ell_{1}+\lambda_{\ell_{3,0}}^{(1)}\ell_{3,0}\leq\lambda_{1}^{(2)}\ell_{1},$
$\displaystyle F_{2,1}^{(2)}=F_{2,1}^{(1)}+F_{3,0}^{(1)}\leq
F_{1,0}^{(1)}+F_{3,0}^{(1)}\leq\lambda_{1}^{(2)}\ell_{1}\leq\lambda_{\ell_{2,1}}^{(2)}\ell_{3}.$

where $\ell_{3}=\ell_{2,1}$.

In the first two constraints, we use the fact that $\ell_{3,0}$ is the
smallest link capacity in the network. In the last one, we first use
$F_{2,1}^{(1)}\leq F_{1,0}^{(1)}$ due to the constraint in $({\rm P1}b)$ and
then, we use the fact that
$\lambda_{\ell_{2,1}}^{(1)}=\lambda_{\ell_{2,1}}^{(2)}=\lambda_{1}^{(2)}$.
Since this new set of variables provides a feasible solution that achieves the
same capacity as the optimal solution, we claim that at least one of the
optimal solutions will satisfy $\lambda_{\ell_{3,0}}=0$ and
$\lambda_{1}+\lambda_{2}=1$ if $\ell_{3}\geq\ell_{1}$.

In the second case, we assume that $\ell_{3}<\ell_{1}$ and we use the
following linear program proposed in [3].

$\displaystyle\begin{array}[]{llll}&\ \rm{P5:}\ \macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}={\rm max}\displaystyle\sum_{p\in\mathcal{P}}x_{p}\mathsf{C}_{p}&&\\\
&({\rm P5}a)\ x_{p}\geq 0&\forall p\\!\in\\!\mathcal{P},&\\\ &({\rm P5}b)\
\displaystyle\sum_{p\in\mathcal{P}_{i}}x_{p}f^{p}_{p.\textit{nx}(i),i}\\!\leq\\!1&\forall
i\\!\in\\![0\\!:\\!N],&\\\ &({\rm P5}c)\
\displaystyle\sum_{p\in\mathcal{P}_{i}}x_{p}f^{p}_{i,p.\textit{pr}(i)}\\!\leq\\!1&\forall
i\\!\in\\![1\\!:\\!N\\!+\\!1],&\end{array}$ (50)

where $\mathcal{P}$ is the collection of all paths going from the source to
the destination, $C_{p}$ is the capacity of path $p$,
$\mathcal{P}_{i}\subseteq\mathcal{P}$ is the collection of paths passing
through node $i$ where $i\in[0:N+1]$, $p.\textit{nx}(i)$ (respectively,
$p.\textit{pr}(i)$) is the node that follows (respectively, precedes) node $i$
in path $p$, the variable $x_{p}$ is the fraction of time path $p$ is used and
$f^{p}_{j,i}$ is the optimal activation time for the link of capacity
$\ell_{j,i}$ when path $p$ is operated, i.e.,

$f^{p}_{j,i}=\frac{C_{p}}{\ell_{j,i}}.$

In [3], it is proved that this program is an equivalent program to the one in
(II). We can particularly write this program for our symmetric and projected
network under the condition $\ell_{3}<\ell_{1}$. There are four paths $p_{1}$,
$p_{2}$, $p_{3}$ and $p_{4}$ in our network where $p_{1}$ is the direct path
between the source and the destination, $p_{2}$ (respectively, $p_{3}$) is the
path going from the source to the destination while passing through relay $1$
(respectively, relay $2$) and path $p_{4}$ is the path going from the source
to the destination while passing through both relays.

$\displaystyle\begin{array}[]{llll}&\ \rm{P6:}\ \macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}={\rm max}\displaystyle\
x_{1}\ell_{3,0}+2x_{2}\ell_{2}+x_{4}\ell_{3}&&\\\ &({\rm P6}a)\
x_{1}+x_{2}\left(\frac{\ell_{2}}{\ell_{1}}+1\right)+x_{4}\frac{\ell_{3}}{\ell_{1}}\leq
1&\\\ &({\rm P6}b)\ x_{2}+x_{4}\leq 1&\\\ &({\rm P6}c)\ x_{1},x_{2},x_{4}\geq
0&\end{array}$ (55)

where $\ell_{1}$, $\ell_{2}$ and $\ell_{3}$ are given in (7). Here, we take
$x_{2}$ = $x_{3}$ due to the symmetric nature of our network. Our aim is to
show that the optimal solution of this linear program satisfies $x_{1}=0$.
Hence, the optimal solution does not send information through the direct path
between the source and the destination. Since the linear program in (55) is
equivalent to the program in (II), the corresponding $\lambda_{\ell_{3,0}}$ is
equal to zero in this case.

Towards this end, we first find the dual of the primal program given in (55).
Then, we show that the feasible point
$x=(x_{1},x_{2},x_{4})=(0,\frac{\ell_{1}-\ell_{3}}{\ell_{1}+\ell_{2}-\ell_{3}},\frac{\ell_{2}}{\ell_{1}+\ell_{2}-\ell_{3}})$
satisfies the KKT conditions, therefore, it is an optimal solution to the
program in (55).

It is not difficult to derive the following dual program of the linear program
in (55).

$\displaystyle\begin{array}[]{llll}\displaystyle&\ \rm{D1:}\ {\rm
min}\displaystyle\ v_{1}+v_{2}\\\ &({\rm D1}a)\ -\ell_{3,0}+v_{1}-s_{1}=0\\\
&({\rm D1}b)\ -2\ell_{2}+\frac{v_{1}\ell_{2}}{\ell_{1}}+v_{1}+v_{2}-s_{2}=0\\\
&({\rm D1}c)\ -\ell_{3}+\frac{v_{1}\ell_{3}}{\ell_{1}}+v_{2}-s_{3}=0\\\ &({\rm
D1}d)\ v_{1},v_{2},s_{1},s_{2},s_{3}\geq 0\end{array}$ (61)

where $v_{1},v_{2},s_{1},s_{2},s_{3}$ are dual variables. Then, we find the
following complementary slackness conditions.

$\displaystyle
v_{1}\left(x_{1}+x_{2}\left(\frac{\ell_{2}}{\ell_{1}}+1\right)+x_{4}\frac{\ell_{3}}{\ell_{1}}-1\right)=0$
(62) $\displaystyle v_{2}(x_{2}+x_{4}-1)=0$ $\displaystyle s_{1}x_{1}=0,\
s_{2}x_{2}=0,\ s_{3}x_{4}=0$

In order point
$x=(x_{1},x_{2},x_{4})=(0,\frac{\ell_{1}-\ell_{3}}{\ell_{1}+\ell_{2}-\ell_{3}},\frac{\ell_{2}}{\ell_{1}+\ell_{2}-\ell_{3}})$
to be optimal, we need to find a feasible dual solution such that point $x$
and the dual solution satisfy the Karush-Kuhn-Tucker (KKT) conditions
together. In the primal program, point $x$ satisfies three constraints with
equality, therefore, the corresponding dual variables $v_{1},v_{2},s_{1}$ can
take nonzero values. The remaining dual variables are zero to satisfy the
complementary slackness conditions. It is not difficult to see that feasible
$v_{1},v_{2},s_{1}$ values for the dual program can be found if the following
condition holds.

$\displaystyle\frac{\ell_{1}(2\ell_{2}-\ell_{3})}{\ell_{1}+\ell_{2}-\ell_{3}}\geq\ell_{3,0}$
(63)

We next show that when $\frac{\gamma}{d^{a}}>3^{a}$ and $\ell_{3}<\ell_{1}$,
this condition is satisfied. Towards this end, we first write the condition in
(63) through using the link capacities in (7) and obtain the following
inequality.

$f=\log\left(\frac{\gamma}{\beta^{a}d^{a}}\right)\log\left(\frac{\gamma(1-2\beta)^{a}}{(1-\beta)^{2a}d^{a}}\right)\\\
-\log\left(\frac{\gamma(1-2\beta)^{a}}{(1-\beta)^{a}\beta^{a}d^{a}}\right)\log\left(\frac{\gamma}{d^{a}}\right)\geq
0$ (66)

We should note that the condition $\ell_{3}<\ell_{1}$ can be equivalently
written as $\beta<\frac{1}{3}$. We then find a condition on $\log(s)$ such
that the condition in (66) is satisfied where $s=\gamma/d^{a}$.

$\displaystyle log(s)\geq
a\frac{log(\beta)}{log(1-\beta)}\log\left(\frac{(1-\beta)^{2}}{1-2\beta}\right)$
(67)

We can denote the function on the RHS of the inequality as $\hat{f}$. Through
using basic calculus, it is not difficult to see that the derivative of the
function $\hat{f}$ is non-negative when $\beta<\frac{1}{3}$. Therefore, the
function $\hat{f}$ is a monotonically increasing function in $\beta$. At
$\beta=\frac{1}{3}$, $\hat{f}\approx 1.13a$. Hence, $s$ should be greater than
or equal to $2^{1.13a}$. Since we assume that $s>3^{a}$, this condition is
satisfied. As a result, point
$x=(0,\frac{\ell_{1}-\ell_{3}}{\ell_{1}+\ell_{2}-\ell_{3}},\frac{\ell_{2}}{\ell_{1}+\ell_{2}-\ell_{3}})$
is one of the optimal solutions and the corresponding
$\lambda_{\ell_{3,0}}=0$. In order to show that $\lambda_{1}+\lambda_{2}=1$,
we can use the same argument as in the proof of
$\lambda_{2}+\lambda_{\ell_{2,1}}=1$. We can start with an optimal solution
such that $\lambda_{1}+\lambda_{2}$ < 1 and $\lambda_{\ell_{3,0}}=0$, then we
can increase $\lambda_{1}$ until the inequality is satisfied with equality. If
we use the same flow variables as in the optimal solution, all constraints
will be satisfied and we reach the same objective value. This concludes the
proof of the equality in (10) and Lemma 2.

##  Appendix C Proof of Lemma 3

Here, we prove Lemma 3 by showing that when $0<\beta\leq d/\gamma^{1/a}$, then
for any fixed $\lambda_{2}\in[0,1]$ either the RHS of $({\rm P4}d)$ or the RHS
of $({\rm P4}f)$ is smaller than ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$.

We start off by finding a condition on $\lambda_{2}$ such that the RHS of
$({\rm P4}d)$ becomes greater than or equal to ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$.

$\displaystyle\log\left(\frac{\gamma}{d^{a}}\right)-\lambda_{2}\log\left((1-\beta)^{a}\right)-(1-\lambda_{2})\log\left(\beta^{a}\right)\geq{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$
$\displaystyle\implies\lambda_{2}\left(\log\left(\beta^{a}\right)-\log\left((1-\beta)^{a}\right)\right)\geq\log\left(\frac{\gamma}{d^{a}}\right)+\log\left(\beta^{a}\right)$
$\displaystyle\implies\lambda_{2}\leq\frac{\log\left(\frac{\gamma}{d^{a}}\right)+\log\left(\beta^{a}\right)}{\log\left(\left(\frac{\beta}{1-\beta}\right)^{a}\right)}$
(68)

When the condition on $\lambda_{2}$ in (C) holds, the first bound becomes
greater than or equal to ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$.

We next observe that in order for the RHS of $({\rm P4}f)$ to be greater than
or equal to ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$, we get the following condition on $\lambda_{2}$.

$\displaystyle(1-\lambda_{2})\left(\log\left(\frac{\gamma}{d^{a}}\right)-\log\left(\left(1-2\beta\right)^{a}\right)\right)$
$\displaystyle\qquad+2\lambda_{2}\left(\log\left(\frac{\gamma}{d^{a}}\right)-\log\left(\left(1-\beta\right)^{a}\right)\right)\geq{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}}^{\star}$
$\displaystyle\implies\lambda_{2}\left(\log\left(\frac{\gamma}{d^{a}}\right)-2\log\left(\left(1-\beta\right)^{a}\right)+\log\left(\left(1-2\beta\right)^{a}\right)\right)$
$\displaystyle\qquad\qquad-\log\left(\left(1-2\beta\right)^{a}\right)\geq\log\left(\frac{\gamma}{d^{a}}\right)$
$\displaystyle\implies\lambda_{2}\geq\frac{\log\left(\frac{\gamma}{d^{a}}\right)+\log\left(\left(1-2\beta\right)^{a}\right)}{\log\left(\frac{\gamma\left(1-2\beta\right)^{a}}{d^{a}(1-\beta)^{2a}}\right)}.$
(69)

We will now show that for all $0<\beta\leq d/\gamma^{1/a}$ and assuming that
$\frac{\gamma}{d^{a}}>3^{a}$, both inequalities (C) and (C) cannot be
satisfied simultaneously by showing that the RHS of (C) is greater than the
RHS of (C) for this range of $\beta$, thus proving our lemma. We would like to
show that

$\displaystyle\frac{\log\left(\frac{\gamma(1-2\beta)^{a}}{d^{a}}\right)}{\log\left(\frac{\gamma(1-2\beta)^{a}}{d^{a}(1-\beta)^{2a}}\right)}>\frac{\log\left(\frac{\gamma\beta^{a}}{d^{a}}\right)}{\log\left(\left(\frac{\beta}{1-\beta}\right)^{a}\right)}$
(70)

This condition can be rewritten by organizing terms as showing that
$0<\beta\leq d/\gamma^{1/a}$, we have that

$f(\beta)=\log\left((1-\beta)^{2a}\right)\log\left(\frac{\gamma\beta^{a}}{d^{a}}\right)\\\
-\log\left(\frac{\gamma(1-2\beta)^{a}}{d^{a}}\right)\log\left(\frac{\gamma(1-\beta)^{a}}{d^{a}}\right)<0.$
(73)

Note that at $\beta=d/\gamma^{1/a}$, $f(\beta)<0$ for $\gamma/d^{a}>3^{a}$.
Thus, it is sufficient to show that the function is monotonically increasing
over our range of interest. Taking the derivative, we get that

$\frac{df(\beta)}{d\beta}=\frac{-2}{1-\beta}\log\left(s\beta^{a}\right)+\frac{2}{\beta}\log\left((1-\beta)^{a}\right)\\\
+\frac{2}{1-2\beta}\log\left(s(1-\beta)^{a}\right)+\frac{1}{1-\beta}\log\left(s(1-2\beta)^{a}\right),$
(76)

where $s=\gamma/d^{a}$. If we show that the derivative is positive, then we
are done as the function is by consequence monotonically increasing.

Note that, when $\frac{\gamma}{d^{a}}>3^{a}$ and $0<\beta\leq d/\gamma^{1/a}$,
it is not difficult to see that the only negative term in (76) is
$\frac{2}{\beta}\log\left((1-\beta)^{a}\right)$. Therefore, we next find a
condition on $s$ that makes
$\frac{2}{1-2\beta}\log\left(s(1-\beta)^{a}\right)+\frac{2}{\beta}\log\left((1-\beta)^{a}\right)>0$.
This can be rewritten as aiming to show that

$\log(s)>\log\left((1-\beta)^{a}\right)\frac{\beta-1}{\beta}.$

It is not difficult to verify through basic calculus that given that
$\frac{\gamma}{d^{a}}>3^{a}$, then the RHS above is monotonically decreasing
and is less than $\log(s)$ at $\beta=0$. Thus, we have shown that constraints
(C) and (C) cannot be satisfied simultaneously and thus concluding the proof
of Lemma 3.