Cross-Layer Optimization of MIMO-Based Mesh Networks with Gaussian
  Vector Broadcast Channels
Cross-Layer Optimization of MIMO-Based Mesh
Networks with Gaussian Vector Broadcast Channels
Jia Liu and Y. Thomas Hou
The Bradley Department of Electrical and Computer Engineering
Virginia Polytechnic Institute and State University, Blacksburg, VA 24061
Email: {kevinlau, thou}@vt.edu
Abstract— MIMO technology is one of the most significant
advances in the past decade to increase channel capacity and has
a great potential to improve network capacity for mesh networks.
In a MIMO-based mesh network, the links outgoing from each
node sharing the common communication spectrum can be
modeled as a Gaussian vector broadcast channel. Recently, re-
searchers showed that “dirty paper coding” (DPC) is the optimal
transmission strategy for Gaussian vector broadcast channels. So
far, there has been little study on how this fundamental result will
impact the cross-layer design for MIMO-based mesh networks.
To fill this gap, we consider the problem of jointly optimizing
DPC power allocation in the link layer at each node and
multihop/multipath routing in a MIMO-based mesh networks.
It turns out that this optimization problem is a very challenging
non-convex problem. To address this difficulty, we transform
the original problem to an equivalent problem by exploiting
the channel duality. For the transformed problem, we develop
an efficient solution procedure that integrates Lagrangian dual
decomposition method, conjugate gradient projection method
based on matrix differential calculus, cutting-plane method, and
subgradient method. In our numerical example, it is shown that
we can achieve a network performance gain of 34.4% by using
I. INTRODUCTION
Since Telatar’s [1] and Foschini’s [2] pioneering works
predicting the potential of high spectral efficiency provided
by multiple antenna systems, the last decade has witnessed
a soar of research activity on Multiple-Input Multiple-Output
(MIMO) technologies. The benefits of substantial improve-
ments in wireless link capacity at no cost of additional
spectrum and power have quickly positioned MIMO as one
of the breakthrough technologies in modern wireless com-
munications, rendering it as an enabling technology for next
generation wireless networks. However, applying MIMO in
wireless mesh networks (WMNs) is not a trivial technical
extension. With the increased number of antennas at each
node, interference is likely to become stronger if power level
at each node, power allocation to each antenna element, and
routing are not managed wisely. As a result, cross-layer design
is necessary for MIMO-based WMNs.
In a MIMO-based WMN, the set of outgoing links from
a node sharing a common communication spectrum can be
modeled as a nondegraded Gaussian vector broadcast channel,
for which the capacity region is notoriously hard to analyze
[3]. In the networking literature, most works considering
links sharing a common communication spectrum are con-
cerned with how to allocate frequency sub-bands/time-slots
and schedule transmissions to efficiently share the common
communication spectrum. As an example, Fig. 1(a) shows a
simple broadcast channel where there are three uncoordinated
users and a single transmitting node. Suppose that messages
x, y, and z need to be delivered to user 1, user 2, and user 3,
respectively. Also, suppose that the received signals subject to
ambient noise are x̂, ŷ, and ẑ, and the decoding functions are
f1(·), f2(·), and f3(·), respectively. The conventional strategy
is to divide a unit time frame into three time slots (or divide
a unit band into three sub-bands) τ1, τ2, and τ3, and then
find the optimal scheduling for transmissions to users 1, 2
and 3, accordingly. The major benefit of this strategy is that
interference can be eliminated.
Link 3
User 1
Transmitter
User 2
User 3
( )1 ˆf x in 1τ
( )2 ˆf y in 2τ
( )3 ˆf z in 3τ
(a) Time or frequency division
Link 3
User 1
Transmitter
User 2
User 3
ˆy y x′ = −
′ = −
( )1 1 1ˆ ˆ ˆf x y z+ +
( )2 2ˆ ˆf y z+
( )3 ˆf z
(b) DPC transmission strategy
Fig. 1. A 3-user broadcast channel example.
Although the time or frequency division schemes are simple
and effective, they are not necessarily the smartest strategy.
In fact, Cover had shown in his classical paper [4] that the
transmission scheme jointly encoding all receivers’ informa-
tion at the transmitter can do strictly better in broadcast chan-
nels. However, the capacity achieving transmission signaling
scheme for general nondegraded Gaussian vector broadcast
channels is very difficult to determine and has become one
of the most basic questions in network information theory
[3]. Very recently, significant progress has been made in
this area. Most notably, Weigarten et. al. finally proved the
long-open conjecture that the “dirty paper coding” strategy
(DPC) [5] is the optimal transmission scheme for Gaussian
vector broadcast channels [6] in the sense that the DPC rate
region CDPC of a broadcast channel is equal to the broadcast
channel’s capacity region CBC, i.e., CBC = CDPC. However,
this fundamental result is still not adequately exposed to the
networking research community. So far, how to exploit DPC’s
http://arxiv.org/abs/0704.0967v1
benefits in the cross-layer design for wireless mesh networks
has not yet been studied in the literature. The main objective
of this study is to fill this gap and to obtain a rigorous and
systematic understanding of the impact of applying DPC to
the cross-layer optimization for MIMO-based mesh networks.
To begin with, it is beneficial to introduce the basic idea
of DPC, which turns out to be very simple. For the same
3-user example, consider the following strategy as shown
in Fig. 1(b). We first jointly encode the messages for all
the users in a certain order and then broadcast the resulting
codeword simultaneously. Suppose that we pick user 1 to be
encoded first, then followed by user 2, and finally user 3.
We choose the codeword x for user 1 as before. Then, the
interference seen by user 2 due to user 1 (denoted by x̂2)
is known at the transmitter. So, the transmitter can subtract
the interference and encode user 2 as y′ = y − x̂2 rather
than y itself. As a result, user 2 does not see any interference
from the signal intended for user 1. Likewise, after encoding
user 2, the interferences seen by user 3 due to user 1 and 2
(denoted by x̂3 and ŷ3) are known at the transmitter. Then, the
transmitter can subtract the interferences and encode user 3 as
z′ = z− x̂3− ŷ3 rather than z itself. Therefore, user 3 does not
see any interferences from the signals intended for user 1 and
2. In the end, the transmitter adds all the codewords together
and broadcasts the sum to all users simultaneously. As a result,
it is easy to see from Fig. 1(b) that the received signal at user
1 is x̂ + ŷ1 + ẑ1, i.e., user 1 will experience the interference
from the signals intended for users 2 and 3; the received
signal at user 2 is ŷ + ẑ2, i.e., user 2 only experiences the
interference from the signal intended for user 3; and finally, the
received signal at user 3 is ẑ, i.e., user 3 does not experience
any interference. This process operates like writing on a dirty
paper, hence the name. Although counterintuitive, the capacity
region of DPC that allows interference is strictly larger than
those of time or frequency division schemes.
After understanding what DPC is, one may ask two very
natural and interesting questions:
1) How will the enlarged capacity region at each node due
to DPC impact the network performance in the upper
layers?
2) Are there any new challenges if DPC is employed in a
MIMO-based networking environment?
Notice that, when DPC is employed, the encoding order
plays a critical role. For a K-user broadcast channel, there
exists K! permutations. Also, since DPC allows interference
among the users, power allocation among different users
along with the encoding order has a significant impact on
the system performance. As we show later, the DPC link
rates in a broadcast channel are non-connvex functions. Thus,
even the optimization for a single K-user Gaussian vector
broadcast channel is a very challenging combinatorial non-
convex problem, not to mention the cross-layer design in a
networking environment with multiple broadcast channels.
In this paper, we aim to solve the problem of jointly
optimizing DPC per-antenna power allocation at each node
in the link layer and multihop/multipath routing in a MIMO-
based WMN. Our contributions are three-fold. First, this paper
is the first work that studies the impacts of applying DPC
to the cross-layer design for MIMO-based WMNs. In our
numerical example, it is shown that we can achieve a network
performance gain of 34.4% by using DPC in MIMO-based
WMNs. Also, since the traditional single-antenna systems can
be viewed as a special case of MIMO systems, the findings
and results in this paper are also applicable to conventional
WMNs with single-antenna. Second, to address the non-
convex difficulty, we transform the original problem to an
equivalent problem under the dual MIMO multiple access
channel (MIMO-MAC) and show that the transformed prob-
lem is convex with respect to the input covariance matrices. We
simplify the maximum weighted sum rate problem for the dual
MIMO-MAC such that enumerating different encoding order
is unnecessary, thus paving the way to efficiently solve the
link layer subproblem in Lagrangian dual decomposition. Last,
for the transformed problem, we develop an efficient solu-
tion procedure that integrates Lagrangian dual decomposition
method, conjugate gradient projection method based on matrix
differential calculus, cutting-plane method, and subgradient
method.
The remainder of this paper is organized as follows. In
Section II, we discuss the network model and problem for-
mulation. Section III discusses how to reformulate the non-
connvex original problem by exploiting channel duality. In
Section IV, we introduce the key components for solving
the challenging link layer subproblem in the Lagrangian
decomposition. Numerical results are provided in Section V
to illustrate the efficacy of our proposed solution procedure
and to study the network performance gain by using DPC.
Section VI reviews related work and Section VII concludes
this paper.
II. NETWORK MODEL
We first introduce notations for matrices, vectors, and com-
plex scalars in this paper. We use boldface to denote matrices
and vectors. For a matrix A, A† denotes the conjugate trans-
pose, Tr{A} denotes the trace of A, and |A| denotes the deter-
minant of A. Diag{A1, . . . ,An} represents the block diagonal
matrix with matrices A1, . . . ,An on its main diagonal. We let
I denote the identity matrix with dimension determined from
context. A � 0 represents that A is Hermitian and positive
semidefinite (PSD). 1 and 0 denote vectors whose elements
are all ones and zeros, respectively, and their dimensions are
determined from context. (v)m represents the m
th entry of
vector v. For a real vector v and a real matrix A, v ≥ 0
and A ≥ 0 mean that all entries in v and A are nonnegative,
respectively. We let ei be the unit column vector where the i
entry is 1 and all other entries are 0. The dimension of ei is
determined from context as well. The operator “〈, 〉” represents
the inner product operation for vectors or a matrices.
A. Network Layer
In this paper, the topology of a MIMO-based wireless
mesh network is represented by a directed graph, denoted
by G = {N ,L}, where N and L are the set of nodes
and all possible MIMO-based links, respectively. By saying
“possible” we mean the distance between a pair of nodes is
less than or equal to the maximum transmission range Dmax,
i.e., L = {(i, j) : Dij ≤ Dmax, i, j ∈ N , i 6= j}, where
Dij represents the distance between node i and node j. Dmax
can be determined by a node’s maximum transmission power.
We assume that G is always connected. Suppose that the
cardinalities of the sets N and L are |N | = N and |L| = L,
respectively. For convenience, we index the links numerically
(e.g., link 1, 2, . . . , L) rather than using node pairs (i, j).
The network topology of G can be represented by a node-
arc incidence matrix (NAIM) [7] A ∈ RN×L, whose entry
anl associating with node n and arc l is defined as
anl =
1 if n is the transmitting node of arc l
−1 if n is the receiving node of arc l
0 otherwise.
We define O (n) and I (n) as the sets of links that are
outgoing from and incoming to node n, respectively. We use
a multicommodity flow model for the routing of data packets
across the network. In this model, several nodes send different
data to their corresponding destinations, possibly through
multipath and multihop routing. We assume that the flow
conservation law at each node is satisfied, i.e., the network
is a flow-balanced system.
Suppose that there are F sessions in total in the network,
representing F different commodities. The source and des-
tination nodes of session f , 1 ≤ f ≤ F , are denoted as
src(f) and dst(f), respectively. For the supply and demand
of each session, we define a source-sink vector sf ∈ RN ,
whose entries, other than at the positions of src(f) and dst(f),
are all zeros. In addition, from the flow conservation law, we
must have (sf )src(f) = −(sf )dst(f). Without loss of generality,
we let (sf )src(f) ≥ 0 and simply denote it as a scalar sf .
Therefore, we can further write the source-sink vector of flow
sf = sf
· · · 1 · · · −1 · · ·
, (2)
where the dots represent zeros, and 1 and −1 are in the
positions of src(f) and dst(f), respectively. Note that for the
source-sink vector of a session f , 1 does not necessarily appear
before −1 as in (2), which is only for an illustrative purpose.
Using the notation “=x,y” to represent the component-wise
equality of a vector except at the xth and the yth entries,
we have sf =src(f),dst(f) 0. In addition, using the matrix
s1 s2 . . . sF
∈ RN×F to denote the collection
of all source-sink vectors, we further have
Sef =src(f),dst(f) 0, 1 ≤ f ≤ F, (3)
〈1,Sef 〉 = 0, 1 ≤ f ≤ F, (4)
(Sef )src(f) = sf , 1 ≤ f ≤ F, (5)
where ef is the f
th unit column vector.
On link l, we let t
≥ 0 be the amount of flow of session
f in link l. We define t(f) ∈ RL as the flow vector for
session f . At node n, components of the flow vector and
source-sink vector for the same commodity satisfy the flow
conservation law as follows:
l∈O(n) t
l∈I(n) t
(sf )n, 1 ≤ n ≤ N , 1 ≤ f ≤ F . With NAIM, the flow
conservation law across the whole network can be compactly
written as At(f) = sf , 1 ≤ f ≤ F . We use matrix T ,
t(1) t(2) . . . t(F )
∈ RL×F to denote the collection
of all flow vectors. With T and S, the flow conservation law
can be further compactly written as AT = S.
B. Channel Capacity of a MIMO Link
In this section, we first briefly introduce some background
of MIMO. We use a matrix Hl ∈ Cnr×nt to represent
the MIMO channel gain matrix from the transmitting node
to the receiving node of link l, where nt and nr are the
numbers of transmitting and receiving antenna elements of
each node, respectively. Hl captures the effect of the scattering
environment between the transmitter and the receiver of link
l. In an additive white Gaussian noise (AWGN) channel, the
received complex base-band signal vector for a MIMO link
l with nt transmitting antennas and nr receiving antennas is
given by
ρlHlxl + nl. (6)
where yl and xl represent the received and transmitted signal
vector; nl is the normalized additive white Gaussian noise
vector; ρl captures the path-loss effect, which is usually
modeled as ρl = G ·D−αl , where G is some system specific
constant, Dl denotes the distance between the transmitting
node and the receiving node of link l, and α denotes the path
loss exponent. Let matrix Ql represent the covariance matrix
of a zero-mean Gaussian input symbol vector xl at link l,
i.e., Ql = E
xl · x†l
. This implies that Ql is Hermitian
and Ql � 0. Physically, Ql represents the power allocation
in different antenna elements in link l’s transmitter and the
correlation between each pair of the transmit and receive
antenna elements. Tr{Ql} is the total transmission power at
the transmitter of link l. The capacity of a MIMO link l in an
AWGN channel with a unit bandwidth can be computed as
Rl(Ql) = log2
I+ ρlHlQlH
, (7)
It can be seen that different power allocations to the antennas
will have different impacts on the link capacity. Therefore, the
optimal input covariance matrix Q∗l needs to be determined.
In a single link environment, the optimal input covariance
matrix can be computed by water-filling the total power over
the eigenmodes (signaling direction) of the MIMO channel
matrix [1]. However, in a networking environment, finding
the optimal input covariance matrices is a substantially more
challenging task. Determining the optimal input covariance
matrices is one of the major goals in our cross-layer opti-
mization.
C. MIMO-BC Link Layer
A communication system where a single transmitter sends
independent information to multiple uncoordinated receivers is
referred to as a broadcast channel. If the channel gain of each
link in the broadcast channel is a matrix and the noise to each
link is a Gaussian random vector, the channel is termed “Gaus-
sian vector broadcast channel”. Fig. 2 illustrates a K-user
Gaussian vector broadcast channel, where independent mes-
sages W1, . . . ,WK are jointly encoded by the transmitter, and
the receivers are trying to decode W1, . . . ,WK , respectively.
A (n, 2nR1 , . . . , 2nRK )BC codebook for a broadcast channel
consists of an encoding function xn(W1, . . . ,WK) where
Wi ∈ {1, . . . , 2nRi}, i = 1, 2, . . . ,K . The decoding function
of receiver i is Ŵi(y
i ) . An error occurs when Ŵi 6= Wi.
A rate vector R = [R1, . . . , RK ]
T is said to be achievable if
there exists a sequence of (n, 2nR1 , . . . , 2nRK )BC codebooks
for which the average probability of error Pe → 0 as the code
length n→ ∞. The capacity region of a broadcast channel is
defined as the union of all achievable rate vectors [3]. Gaussian
vector broadcast channel can be used to model many different
types of systems [3]. Due to the close relationship between
Gaussian vector broadcast channel and MIMO, we will call
the Gaussian vector broadcast channel in the MIMO case as
MIMO-BC throughout the rest of this paper.
nRW ∈
nRW ∈
2 KnRKW ∈
( )1, ,n KW Wx �
( )1 1ˆ nW y
( )2 2ˆ nW y
( )ˆ nK KW y
Transmitter
Receivers
Fig. 2. A Gaussian vector broadcast channel.
For clarity, we use Γi to specifically denote the input
covariance matrix of link i in a MIMO-BC, and Qj to denote
an input covariance matrix in other types of MIMO channels.
From the encoding process of DPC, the achievable rate in DPC
scheme can be computed as follows:
Rπ(i) = log
I+Hπ(i)
j≥i Γπ(j)
I+Hπ(i)
Γπ(j)
, (8)
where π denotes a permutation of the set {1, . . . ,K}, π(i)
represents the ith position in permutation π. One important
observation of the dirty paper rate equation in (8) is that the
rate equation is neither a concave nor a convex function of the
input covariance matrices Γi, i = 1, 2, . . . ,K .
Let H = [H1, . . . ,HK ]
T be the collection of K channel
gain matrices in the MIMO-BC, and Γ = [Γ1 . . . ,ΓK ] be
the collection of K input covariance matrices. We define the
dirty paper region CDPC(P,H) as the convex hull of the
union of all such rates vectors over all positive semidefinite
covariance matrices Γ1, . . . ,ΓK satisfying Tr{
i=1 Γi} ≤ P
(the maximum transmit power constraint at the transmitter)
and over all K! permutations:
CDPC(P,H) , Cov
∪π,ΓRBC(π,Γ)
where Cov(·) represents the convex hull operation.
D. Problem Formulation
In this paper, we aim to solve the problem of jointly
optimizing DPC per-antenna power allocation at each node
in the link layer and multihop/multipath routing in a MIMO-
based WMN. Suppose that each node in the network has
been assigned a certain (possibly reused) frequency band that
will not cause interference to any other node in the network.
Also, the incoming and outgoing bands of each node are
non-overlapping such that each node can transmit and receive
simultaneously. How to perform channel assignments is a huge
research topic on its own merits, and there are a vast amount
of literature that discuss channel assignment problems. Thus,
in this paper, we focus on how to jointly optimize routing
in the network layer and the DPC power allocation in the
link layer for each node when a channel assignment is given.
We adopt the well-known proportional fairness utility function,
i.e., ln(sf ) for flow f . In CRPA, we wish to maximize the sum
of all utility functions. In the link layer, since the total transmit
power of each node is subject to a maximum power constraint,
we have
l∈O(n) Tr{Γl} ≤ P
max, 1 ≤ n ≤ N , where P (n)max
represents the maximum transmit power of node n. Since the
total amount of flow in each link l cannot exceed its capacity
limit, we must have
f=1 t
≤ Rl(Γ), 1 ≤ l ≤ L. This can
be further compactly written using matrix-vector notations as
〈1,TTel〉 ≤ Rl(Γ), 1 ≤ l ≤ L. Coupling the network layer
model in Section II-A and MIMO-BC link layer model in
Section II-C, we have the problem formulation for CRPA as
in (9).
CRPA:
Maximize
f=1 ln(sf )
subject to AT = S
T ≥ 0
Sef =src(f),dst(f) 0 ∀ f
〈1,Sef〉 = 0 ∀ f
(Sef )src(f) = sf ∀ f
〈1,TTel〉 ≤ Rl(Γ) ∀ l
Rl(Γ) ∈ C(n)DPC(P
max,H
(n)) ∀l ∈ O (n)
l∈O(n) Tr{Γl} ≤ P
max ∀n
Γl � 0 ∀ l
Variables: S, T, Γ
III. REFORMULATION OF CRPA
As we pointed out earlier, the DPC rate equation in (8) is
neither a concave nor a convex function of the input covariance
matrices. As a result, the cross-layer optimization problem in
(9) is a non-convex optimization problem, which is very hard
to solve numerically, let alone analytically. However, in the
following, we will show that (9) can be reformulated as an
equivalent convex optimization problem by projecting all the
MIMO-BC channels onto their dual MIMO multiple-access
channels (MIMO-MAC). We first provide some background
of Gaussian vector multiple access channels and the channel
duality between MIMO-BC and MIMO-MAC.
A. MIMO-MAC Channel Model
A communication system where multiple uncoordinated
transmitters send independent information to a single receiver
is referred to as a multiple access channel. If the channel
gain of each link in the multiple access channel is a matrix
and the noise is a Gaussian random vector, the channel is
termed “Gaussian vector multiple access channel”. Fig. 3
illustrates a K-user Gaussian vector multiple access chan-
nel, where independent messages W1, . . . ,WK , are encoded
by transmitters 1 to K , respectively, and the receiver is
trying to decode W1, . . . ,WK . A (n, 2
nR1 , . . . , 2nRK )MAC
codebook for a multiple access channel consists of encoding
functions xn1 (W1), . . . ,x
K(WK) where Wi ∈ {1, . . . , 2nRi},
i = 1, 2, . . . ,K . The decoding functions at the receiver are
Ŵi(y
i ), i = 1, 2, . . . ,K . An error occurs when Ŵi 6= Wi.
A rate vector R = [R1, . . . , RK ]
T is said to be achievable if
there exists a sequence of (n, 2nR1 , . . . , 2nRK )MAC codebooks
for which the average probability of error Pe → 0 as the
code length n → ∞. The capacity region of a multiple
access channel, denoted by CMAC is defined as the union of
all achievable rate vectors [3]. We call the Gaussian vector
multiple access channel in the MIMO case as MIMO-MAC
throughout the rest of this paper.
nRW ∈
nRW ∈
2 KnRKW ∈
( )1ˆ nW y
( )2ˆ nW y
( )ˆ nKW y
Transmitters Receiver
( )1 1n Wx
( )2 2n Wx
( )nK KWx
Fig. 3. A Gaussian vector multiple access channel.
B. Duality between MIMO-BC and MIMO-MAC
The dual MIMO-MAC of a MIMO-BC can be constructed
by changing the receivers in the MIMO-BC into transmitters
and changing the transmitter in the MIMO-BC into the re-
ceiver. The channel gain matrices in dual MIMO-MAC are the
conjugate transpose of the channel gain matrices in MIMO-
BC. The maximum sum power in the dual MIMO-MAC is the
same maximum power level as in MIMO-BC. The relationship
between a MIMO-BC and its dual MIMO-MAC is illustrated
in Fig. 4. Similar to MIMO-BC, We denote the capacity region
of the dual MIMO-MAC as CMAC(P,H†). The following
Lemma states the relationship between the capacity regions
of a MIMO-BC and its dual MIMO-MAC.
Receiver
Transmitter 1
Transmitter 2
Transmitter K
Transmitter
Receiver 1
Receiver 2
Receiver K
MIMO-BC MIMO-MAC
Fig. 4. The relationship between MIMO-BC and its dual MIMO-MAC
Lemma 1: The DPC region of a MIMO-BC channel with
maximum power constraint P is equal to the capacity region
of the dual MIMO MAC with sum power constraint P
CDPC(P,H) = CMAC(P,H†).
Proof: The proof of this theorem can be arrived in various
ways [8]–[10]. The most straightforward approach is to show
that any MIMO-BC achievable rate vector is also achievable
in its dual MIMO-MAC and vice versa. The MAC-to-BC and
BC-to-MAC mappings can be found in [8]. It is also shown
in [8] that any rate vector in a MIMO-BC with a particular
encoding order can be achieved in its dual MIMO-MAC with
the reversed successive decoding order.
C. Convexity of MIMO-MAC Capacity Region
From Lemma 1, we know that the capacity region of a
MIMO-BC and its dual MIMO-MAC is exactly the same.
Therefore, we can replace CDPC(·) in (9) by the capacity
regions of the dual MIMO-MAC channels CMAC(·). The
benefits of such replacements is due to the following theorem.
Theorem 1: The capacity region of a K-user MIMO-MAC
channel with a sum power constraint
i=1 Tr(Qi) ≤ Pmax
is convex with respect to the input covariance matrices
Q1, . . . ,QK .
Proof: Denote the input signals of the K users by
x1, . . . ,xK , respectively, and denote the output of the MIMO-
MAC channel by y. Since ρi is a scalar, we absorb ρi into Hi
in this proof for notation convenience. Theorem 14.3.5 in [3]
states that the capacity region of a MIMO-MAC is determined
CMAC(Q1, . . . ,QK) =
(R1, . . . , RK)
i∈S Ri(Q) ≤
I(xi, i ∈ S;y|xi, i ∈ Sc),
∀S ⊆ {1, . . . ,K}
i=1 Tr(Qi) ≤ Pmax
, (10)
where the mutual information expression I(; ) can be bounded
as follows:
I(xi, i ∈ S;y|xi, i ∈ Sc) ≤ log
iQiHi
. (11)
To show that the capacity region of the MIMO-MAC with
a sum power constraint is convex, it is equivalent to show
that the convex hull operation in (10) is unnecessary. To show
this, consider the convex combination of two arbitrarily cho-
sen achievable rate vectors [R1, . . . , RK ] and [R̂1, . . . , R̂K ]
determined by two feasible power vectors [Q1, . . . ,QK ] and
[Q̂1, . . . , Q̂K ], respectively, i.e., we have
i=1 Tr(Qi) ≤
Pmax and
i=1 Tr(Q̂i) ≤ Pmax. Let 0 ≤ α ≤ 1 and consider
the convex combination
[R̄1, . . . , R̄K ] = α[R1, . . . , RK ] + (1− α)[R̂1, . . . , R̂K ].
Also, let Q̄i = αQi + (1− α)Q̂i, i = 1, . . . ,K . It is easy to
verify that
i=1 Tr(Q̄i) ≤ Pmax, i.e., the convex combination
of two feasible power vectors is also feasible. Now, consider
Ri + (1− α)
R̂i ≤ α log
iQiHi
+(1− α) log
iQ̂iHi
Since the function log |A| is a concave function for any
positive semidefinite matrix variable A [3], it follows from
Jensen’s inequality that
Ri + (1− α)
R̂i ≤
iQ̄iHi
which means that the convex combination of rate vectors
[R1, . . . , RK ] and [R̂1, . . . , R̂K ] can also be achieved by using
the feasible power vector [Q̄1, . . . , Q̄K ] directly. As a result,
the convex hull operation is unnecessary.
D. Maximum Weighted Sum Rate Problem of the Dual MIMO-
Now, we consider the maximum weighted sum rate problem
of the dual MIMO-MAC. We simplify this problem such
that we do not have to enumerate all possible successive
decoding order in the dual MIMO-MAC, thus paving the way
to efficiently solve the link layer subproblem we discuss in
Section IV.
Theorem 2: Associate each rate Ri in MIMO-MAC a non-
negative weight ui, i = 1, . . . ,K , the maximum weighted
sum max
i=1 Ri(Q) can be solved by the following convex
optimization problem:
Maximize
i=1(uπ(i) − uπ(i−1))×
j=i ρπ(j)H
Qπ(j)Hπ(j)
subject to
i=1 Tr(Qi) ≤ Pmax
Qi � 0, i = 1, . . . ,K,
where uπ(0) , 0, π(i), i = 1, . . . ,K is a permutation on
{1, . . . ,K} such that uπ(1) ≤ . . . ≤ uπ(K). In particular,
suppose that (Q∗
, . . . ,Q∗
) solves (12), then the optimal
rates of (12) are given by
R∗π(K) = log
I+ ρπ(K)H
π(K)HK
π(i) = log
j=i ρπ(j)H
π(j)Hj
− log
j=i+1 ρπ(j)H
, (14)
for i = 1, 2, . . . ,K − 1.
Proof: For convenience, we let
Φ(S) = log
Qπ(i)Hπ(i)
Since π(i) is simply a permutation on {1, . . . ,K}, from (10)
and (11) we have the maximum weighted sum rate problem
can be written as
Maximize
i=1 uπ(i)Rπ(i)
subject to
i∈S Rπ(i) ≤ Φ(S), ∀S ⊆ {1, . . . ,K}.
Also from (10) and (11), it is easy to derive that Rπ(i) ≤
Φ({π(i)}) = log
I+ ρπ(i)H
Qπ(i)Hπ(i)
. Since uπ(1) ≤
. . . ≤ uπ(K), from KKT condition, we must have that the
constraint Rπ(K) = Φ({π(K)}) must be tight at optimality.
That is,
Rπ(K) = log
I+ ρπ(K)H
Qπ(K)Hπ(K)
. (15)
Again, from (10) and (11), we have
Rπ(K−1) +Rπ(K) ≤ log
I+ ρπ(K)H
Qπ(K)Hπ(K)
+ρπ(K−1)H
π(K−1)
Qπ(K−1)Hπ(K−1)
Rπ(K−1) ≤ log
I+ ρπ(K)Hπ(K)Qπ(K)H
+ρπ(K−1)Hπ(K−1)Qπ(K−1)H
π(K−1)
I+ ρπ(K)Hπ(K)Qπ(K)H
Since uπ(K−1) is the second largest weight, again from KKT
condition, we must have that (16) must be tight at optimality.
This process continues for all K users. Subsequently, we have
Rπ(i) = log
j=i ρπ(j)H
Qπ(j)Hj
− log
j=i+1 ρπ(j)H
Qπ(j)Hj
, (17)
for i = 1, . . . ,K − 1. Summing up all uπ(i)Rπ(i) and after
rearranging the terms, it is readily verifiable that
uπ(i)Rπ(i) =
(uπ(i) − uπ(i−1))×
ρπ(j)H
Qπ(j)Hπ(j)
. (18)
It then follows that the maximum weighted sum rate problem
of MIMO-MAC is equivalent to maximizing (18) subject to
the sum power constraint, i.e., the optimization problem in
(12). Since log |·| is a concave function of positive semidefinite
matrices, (18) is a convex optimization problem with respect to
Qπ(1), . . . ,Qπ(K). After we obtain the optimal solution power
solution (Q∗
π(1), . . . ,Q
π(K)), the corresponding link rates can
be computed by simply following (15) and (17).
E. Problem Reformulation
We now reformulate CRPA by replacing CDPC in (9) with
CMAC, and we denote the equivalent problem by CRPA-E.
After solving CRPA-E, we can recover the corresponding
MIMO-BC covariance matrices Γ∗ from the optimal solution
Q∗ of CRPA-E by the MAC-to-BC mapping provided in [8].
CRPA-E:
Maximize
f=1 ln(sf )
subject to AT = S
T ≥ 0
Sef =src(f),dst(f) 0 ∀ f
〈1,Sef〉 = 0 ∀ f
(Sef )src(f) = sf ∀ f
〈1,TTel〉 ≤ Rl(Q) ∀ l
Rl(Q) ∈ C(n)MAC(P
max,H
†(n)) ∀l ∈ O (n)
l∈O(n) Tr{Ql} ≤ P
max ∀n
Ql � 0 ∀ l
Variables: S, T, Q
IV. SOLUTION PROCEDURE
Since CRPA-E is a convex programming problem, we can
solve CRPA-E exactly by solving its Lagrangian dual problem.
Introducing Lagrangian multipliers ui to the link capacity
coupling constraints 〈1,TTel〉 ≤ Rl(Q), Hence, we can write
the Lagrangian as
Θ(u) = sup
S,T,Q
{L(S,T,Q,u)|(S,T,Q) ∈ Ψ} , (20)
where
L(S,T,Q,u) =
ln (sf ) +
Rl(Q)− 〈1,TTel〉
and Ψ is defined as
(S,T,Q)
AT = S
T ≥ 0
Sef =src(f),dst(f) 0 ∀ f
〈1,Sef 〉 = 0 ∀ f
(Sef )src(f) = sf ∀ f
l∈O(n) Tr{Ql} ≤ P
max ∀n
Ql � 0 ∀ l
Rl(Q) ∈ CMAC(P
max,H
†(n)) ∀n
The Lagrangian dual problem of CRPA can thus be written
DCRPA−E : Minimize Θ(u)
subject to u ≥ 0.
It is easy to recognize that, for a given u, the Lagrangian in
(20) can be rearranged and separated into two terms:
Θ(u) = Θnet(u) + Θlink(u),
where, for a given Lagrangian multiplier u, Θnet and Θlink
are corresponding to network layer and link layer variables,
respectively:
CRPA−E
net : Θnet(u) , Maximize
ln (sf )
ul〈1,TTel〉
subject to AT = S
T ≥ 0
Sef =src(f),dst(f) 0 ∀ f
〈1,Sef 〉 = 0 ∀ f
(Sef )src(f) = sf ∀ f
Variables: S, T
CRPA−E
link : Θlink(u) , Maximize
ulRl(Q)
subject to
l∈O(n) Tr{Ql} ≤ P
max ∀n
Ql � 0 ∀ l
Rl(Q) ∈ CMAC(P (n)max,H†(n)),
∀ l ∈ O (n) , n ∈ N
Variables: Q
The CRPA-E Lagrangian dual problem can thus be written
as the following master dual problem:
CRPA−E : Minimize Θnet(u) + Θlink(u)
subject to u ≥ 0
Notice that Θlink(u) can be further decomposed on a node-
by-node basis as follows:
Θlink(u) = max
ulRl(Q)
l∈O(n)
ulRl(Q)
link(u
(n)). (21)
It is seen that Θ
link(u
(n)) , max
l∈O(n) ulRl(Q) is a
maximum weighted sum rate problem of the dual MIMO-
MAC for some given dual variables u(n) as weights. Without
loss of generality, suppose that node n has K outgoing links,
which are indexed as 1, . . . ,K and are associated with dual
variables u1, . . . , uK , respectively. Let π(i) ∈ {1, . . . ,K} be
the permutation such that 0 ≤ uπ(1) ≤ . . . ≤ uπ(K) and define
uπ(0) = 0. Θ
link(u
(n)) can be written as follows:
Maximize
i=1(uπ(i) − uπ(i−1))×
j=i ρπ(j)H
Qπ(j)Hπ(j)
subject to
i=1 Tr(Qi) ≤ P
Qi � 0, i = 1, . . . ,K.
Note that in the network layer subproblem Θnet(u), the
objective function is concave and all constraints are affine.
Therefore, Θnet(u) is readily solvable by many polynomial
time convex programming methods. However, even though
link(u
(n)) is also a convex problem, generic convex pro-
gramming methods are not efficient because the structures of
its objective function and constraints are very complex. In the
following subsections, we will discuss in detail how to solve
link(u
(n)).
A. Conjugate Gradient Projection for Solving Θ
link(u
We propose an efficient algorithm based on conjugate gradi-
ent projection (CGP) to solve (22). CGP utilizes the important
and powerful concept of Hessian conjugacy to deflect the
gradient direction appropriately so as to achieve the superlinear
convergence rate [11], which is similar to that of the well-
known quasi-Newton methods (e.g., BFGS method). In each
iteration, CGP projects the conjugate gradient direction to find
an improving feasible direction. The framework of CGP for
solving (22) is shown in Algorithm 1.
Algorithm 1 Gradient Projection Method
Initialization:
Choose the initial conditions Q(0) = [Q
2 , . . . ,Q
]T . Let
k = 0.
Main Loop:
1. Calculate the conjugate gradients G
, i = 1, 2, . . . ,K .
2. Choose an appropriate step size sk . Let Q
+ skG
for i = 1, 2, . . . , K .
3. Let Q̄(k) be the projection of Q
′(k) onto Ω+(P
max).
4. Choose an appropriate step size αk . Let Q
(k+1)
αk(Q̄
), i = 1, 2, . . . ,K .
5. k = k+1. If the maximum absolute value of the elements in Q
(k−1)
< ǫ, for i = 1, 2, . . . , L, then stop; else go to step 1.
We adopt the “Armijo’s Rule” inexact line search method
to avoid excessive objective function evaluations, while still
enjoying provable convergence [11]. For convenience, we
use F (Q) to represent the objective function in (22), where
Q = (Q1, . . . ,QK) denotes the set of covariance matrices at
a node. According to Armijo’s Rule, in the kth iteration, we
choose σk = 1 and αk = β
mk (the same as in [12]), where
mk is the first non-negative integer m that satisfies
F (Q(k+1))− F (Q(k)) ≥ σβm〈G(k), Q̄(k) −Q(k)〉
= σβm
, (23)
where 0 < β < 1 and 0 < σ < 1 are fixed scalars.
B. Computing the Conjugate Gradients
The gradient Ḡπ(j) , ∇Qπ(j)F (Q) depends on the partial
derivatives of F (Q) with respect to Qπ(j). By using the
formula ∂ ln|A+BXC|
C(A+BXC)−1B
[12], [13],
we can compute the partial derivative of the ith term in the
summation of F (Q) with respect to Qπ(j), j ≥ i, as follows:
∂Qπ(j)
(uπ(i) − uπ(i−1))×
ρπ(k)H
Qπ(k)Hπ(k)
= ρπ(j)
uπ(i) − uπ(i−1)
Hπ(j)
ρπ(k)H
Qπ(k)Hπ(k)
To compute the gradient of F (Q) with respect to Qπ(j), we
notice that only the first j terms in F (Q) involve Qπ(j). From
the definition ∇zf(z) = 2(∂f(z)/∂z)∗ [14], we have
Ḡπ(j) = 2ρπ(j)Hπ(j)
uπ(i) − uπ(i−1)
ρπ(k)H
Qπ(k)Hπ(k)
. (24)
Remark 1: It is important to point out that we can exploit
the special structure in (24) to significantly reduce the com-
putation complexity in the implementation of the algorithm.
Note that the most difficult part in computing Ḡπ(j) is the
summation of the terms in the form of H†
Qπ(k)Hπ(k).
Without careful consideration, one may end up computing
such additions j(2K + 1 − j)/2 times for Ḡπ(j). However,
notice that when j varies, most of the terms in the summation
are still the same. Thus, we can maintain a running sum for
k=i ρπ(k)H
Qπ(k)Hπ(k), start out from j = K , and
reduce j by one sequentially. As a result, only one new term
is added to the running sum in each iteration, which means
we only need to do the addition once in each iteration.
The conjugate gradient direction in the mth iteration can
be computed as G
+ κmG
(m−1)
. We adopt the
Fletcher and Reeves’ choice of deflection [11], which can be
computed as
‖Ḡ(m)
‖Ḡ(m−1)
. (25)
The purpose of deflecting the gradient using (25) is to find
, which is the Hessian-conjugate of G
(m−1)
. By doing
so, we can eliminate the “zigzagging” phenomenon encoun-
tered in the conventional gradient projection method, and
achieve the superlinear convergence rate [11] without actually
storing a large Hessian approximation matrix as in quasi-
Newton methods.
C. Projection onto Ω+(P
Noting from (24) that Gπ(j) is Hermitian, we have that
+ skG
is Hermitian as well. Then, the
projection problem becomes how to simultaneously project
|O (n) | Hermitian matrices onto the set
max) ,
Tr{Ql} ≤ P (n)max,
Ql � 0, l ∈ O (n)
This problem belongs to the class of “matrix nearness prob-
lems” [15], [16], which are not easy to solve in general.
However, by exploiting the special structure in Θ
link(u), we
are able to design a polynomial-time algorithm.
We construct a block diagonal matrix D =
Qπ(1) . . .Qπ(K)
∈ C(K·nr)×(K·nr). It is easy to
recognize that Qπ(j) ∈ Ω+(P
max), j = 1, . . . ,K , only if
Tr(D) =
j=1 Tr
Qπ(j)
≤ P (n)max and D � 0. We use
Frobenius norm, denoted by ‖ · ‖F , as the matrix distance
criterion. The distance between two matrices A and B is
defined as ‖A − B‖F =
(A−B)†(A−B)
2 . Thus,
given a block diagonal matrix D, we wish to find a matrix
D̃ ∈ Ω+(P (n)max) such that D̃ minimizes ‖D̃ − D‖F . For
more convenient algebraic manipulations, we instead study
the following equivalent optimization problem:
Minimize 1
‖D̃−D‖2F
subject to Tr(D̃) ≤ P (n)max, D̃ � 0.
In (26), the objective function is convex in D̃, the constraint
D̃ � 0 represents the convex cone of positive semidefinite
matrices, and the constraint Tr(D̃) ≤ P (n)max is a linear
constraint. Thus, the problem is a convex minimization prob-
lem and we can exactly solve this problem by solving its
Lagrangian dual problem. Associating Hermitian matrix Π to
the constraint D̃ � 0 and µ to the constraint Tr(D̃) ≤ P (n)max,
we can write the Lagrangian as g(Π, µ) = min
{(1/2)‖D̃−
D‖2F − Tr(Π†D̃) + µ(Tr(D̃) − P
max)}. Since g(Π, µ) is
an unconstrained convex quadratic minimization problem, we
can compute the minimizer of the Lagrangian by simply
setting its first derivative (with respect to D̃) to zero, i.e.,
(D̃ − D) − Π† + µI = 0. Noting that Π† = Π, we have
D̃ = D − µI+Π. Substituting D̃ back into the Lagrangian,
we have
g(Π, µ) = −1
‖D− µI+Π‖2F − µP
max +
‖D‖2.
Therefore, the Lagrangian dual problem can be written as
Maximize − 1
‖D− µI+Π‖2
− µP (n)max + 12‖D‖
subject to Π � 0, µ ≥ 0.
After solving (27), we can have the optimal solution to (26)
∗ = D− µ∗I+Π∗,
where µ∗ and Π∗ are the optimal dual solutions to Lagrangian
dual problem in (27). We now consider the term D − µI +
Π, which is the only term involving Π in the dual objective
function. From Moreau Decomposition [17], we immediately
‖D− µI+Π‖
= (D− µI)+ ,
where the operation (A)+ means performing eigenvalue de-
composition on matrix A, keeping the eigenvector matrix
unchanged, setting all non-positive eigenvalues to zero, and
then multiplying back. Thus, the matrix variable Π in the
Lagrangian dual problem can be removed and the Lagrangian
dual problem can be rewritten as
Maximize ψ(µ) , − 1
∥(D− µI)+
− µP (n)max
subject to µ ≥ 0.
Suppose that after performing eigenvalue decomposition on D,
we have D = UΛU†, where Λ is the diagonal matrix formed
by the eigenvalues of D, U is the unitary matrix formed by
the corresponding eigenvectors. Since U is unitary, we have
(D− µI)+ = U (Λ− µI)+ U
It then follows that
∥(D− µI)+
∥(Λ− µI)+
We denote the eigenvalues in Λ by λi, i = 1, 2, . . . ,K · nr.
Suppose that we sort them in non-increasing order such that
Λ = Diag{λ1 λ2 . . . λK·nr}, where λ1 ≥ . . . ≥ λK·nr . It
then follows that
∥(Λ− µI)+
(max {0, λj − µ})2 .
So, we can rewrite ψ(µ) as
ψ(µ) = −1
(max {0, λj − µ})2 − µP (n)max. (29)
It is evident from (29) that ψ(µ) is continuous and (piece-wise)
concave in µ. Due to this special structure, we can search the
optimal value of µ as follows. Let Î index the pieces of ψ(µ),
Î = 0, 1, . . . ,K · nr. Initially we set Î = 0 and increase Î
subsequently. Also, we introduce λ0 = ∞ and λK·nr+1 =
−∞. We let the endpoint objective value ψ
(λ0) = 0, φ
(λ0), and µ
∗ = λ0. If Î > K · nr, the search stops. For a
particular index Î , by setting
(ν) ,
(λi − µ)2 − µP (n)max
 = 0,
we have
i=1 λi − P
Now we consider the following two cases:
1) If µ∗
∩ R+, where R+ denotes the set
of non-negative real numbers, then µ∗
is the optimal
solution because ψ(µ) is concave in µ. Thus, the point
having zero-value first derivative, if exists, must be the
unique global maximum solution. Hence, we can let
µ∗ = µ∗
and the search is done.
2) If µ∗
∩ R+, we must have that the local
maximum in the interval
∩R+ is achieved at
one of the two endpoints. Note that the objective value
has been computed in the previous iteration
because from the continuity of the objective function,
we have ψ
. Thus, we only need to
compute the other endpoint objective value ψ
= φ∗, then we know µ∗ is the
optimal solution; else let µ∗ = λ
, φ∗ = ψ
Î = Î + 1 and continue.
Since there are K ·nr+1 intervals in total, the search process
takes at most K ·nr +1 steps to find the optimal solution µ∗.
Hence, this search is of polynomial-time complexity O(nrK).
After finding µ∗, we can compute D̃∗ as
∗ = (D− µ∗I)+ = U (Λ− µ
I)+ U
†. (30)
The projection of D onto Ω+(P
max) is summarized in Algo-
rithm 2.
Algorithm 2 Projection onto Ω+(P
Initiation:
1. Construct a block diagonal matrix D. Perform eigenvalue decompo-
sition D = UΛU†, sort the eigenvalues in non-increasing order.
2. Introduce λ0 = ∞ and λK·nt+1 = −∞. Let Î = 0. Let the
endpoint objective value ψ
(λ0) = 0, φ∗ = ψÎ (λ0), and µ
∗ = λ0.
Main Loop:
1. If Î > K ·nr , go to the final step; else let µ∗
j=1 λj −P )/Î .
2. If µ∗
]∩R+, then let µ∗ = µ∗
and go to the final step.
3. Compute ψ
). If ψ
) < φ∗, then go to the final step;
else let µ∗ = λ
, φ∗ = ψ
), Î = Î + 1 and continue.
Final Step: Compute D̃ as D̃ = U (Λ− µ∗I)+ U
D. Solving the Master Dual Problem
1) Cutting-Plane Method for Solving Θ(u): The attractive
feature of the cutting-plane method is its robustness, speed of
convergence, and its simplicity in recovering primal feasible
optimal solutions. The primal optimal feasible solution can be
exactly computed by averaging all the primal solutions (may or
may not be primal feasible) using the dual variables as weights
[11]. Letting z = Θ(u), the dual problem is equivalent to
Minimize z
subject to z ≥
ln (sf ) +
Rl(Q)− 〈1,TTel〉
u ≥ 0,
where (S,T,Q) ∈ Ψ. Although (31) is a linear program with
infinite constraints not known explicitly, we can consider the
following approximating problem:
Minimize z
subject to z ≥
(j))−
〈1,T(j)T el〉
u ≥ 0,
where the points (S(j),T(j),Q(j)) ∈ Ψ, j = 1, . . . , k − 1.
The problem in (32) is a linear program with a finite number
of constraints and can be solved efficiently. Let (z(k),u(k))
be an optimal solution to the approximating problem, which
we refer to as the master program. If the solution is feasible
to (31), then it is an optimal solution to the Lagrangian dual
problem. To check the feasibility, we consider the following
subproblem:
Maximize
ln (sf ) +
Rl(Q)− 〈1,TTel〉
subject to (S,T,Q) ∈ Ψ
Suppose that (S(k),T(k),Q(k)) is an optimal solution to the
subproblem (33) and Θ∗(u(k)) is the corresponding optimal
objective value. If zk ≥ Θ∗(u(k)), then u(k) is an optimal
solution to the Lagrangian dual problem. Otherwise, for u =
u(k), the inequality constraint in (31) is not satisfied for
(S(j),T(j),Q(j)). Thus, we can add the constraint
(k))− 〈1,T(k)T el〉
to (32), and re-solve the master linear program. Obviously,
(z(k),u(k)) violates (34) and will be cut off by (34). The
cutting plane algorithm is summarized in Algorithm 3.
Algorithm 3 Cutting Plane Algorithm for Solving DCRPA
Initialization:
Find a point (S(0),T(0),Q(0)) ∈ Ψ. Let k = 1.
Main Loop:
1. Solve the master program in (32). Let (z(k),u(k)) be an optimal
solution.
2. Solve the subproblem in (33). Let (S(k),T(k),Q(k)) be an optimal
point, and let Θ∗(u(k)) be the corresponding optimal objective value.
3. If z(k) ≥ Θ(u(k)), then stop with u(k) as the optimal dual solution.
Otherwise, add the constraint (34) to the master program, replace k
by k + 1, and go to step 1.
2) Subgradient Algorithm for Solving Θ(u): Since the
Lagrangian dual objective function is piece-wise differentiable,
subgradient method can also be applied. For Θ(u), starting
with an initial u(1) and after evaluating subproblems Θnet(u)
and Θlink for u
(k) in the kth iteration, we update the dual
variables by u(k+1) =
uk − λ(k)d(k)
, where the operator
[·]+ projects a vector on to the nonnegative orthant, and λk
denotes a positive scalar step size. d(k) is a subgradient of
the Lagrangian at point u(k). It is proved in [11] that the
subgradient algorithm converges if the step size λk satisfies
λk → 0 as k → ∞ and
k=0 λk = ∞. A simple and useful
step size selection strategy is the divergent harmonic series
k=1 β
= ∞, where β is a constant. The subgradient for
the Lagrangian dual problem can be computed as
∗(u)) − 〈1,T∗(u)T el〉, l = 1, 2, . . . , L. (35)
Specifically, the subgradient method has the following proper-
ties which make it possible to be implemented in a distributed
fashion:
1) Subgradient computation only requires local traffic in-
formation 〈1,TTel〉 and the available link capacity
information Rl(Q) at each link l. As a result, it can
be computed locally.
2) The choice of step size λk = β
depends only upon the
iteration index k, and does not require any other global
knowledge. In conjunction with the first property, the
dual variable, in the iterative form of u
(k+1)
λk(∂Θ(u)/∂ul), can also be computed locally.
3) The objective functions Θlink can be decomposed on a
node-by-node basis such that each node in the network
can perform the computation in parallel. Likewise, the
network layer subproblem Θnet can be decomposed on
a source-by-source basis such that each source node can
perform the routing computation locally after receiving
the dual variable information of each link in the network.
It is worth to point out that care must be taken when recov-
ering the primal feasible optimal solution in the subgradient
method. Generally, the primal variables in the dual optimal
solution are not primal feasible unless the dual optimal solu-
tion happens to be the saddle point. Fortunately, since CRPA-E
is convex, its primal feasible optimal solution can be exactly
0 200 400 600 800 1000 1200
N5 N6N7
N10 N11
Fig. 5. A 15-node network example.
0 20 40 60 80 100 120 140 160
Number of Iterations
Lagrangian Dual UB
Primal Feasible Solution
Fig. 6. Convergence behavior of the cutting-plane method
computed by solving a linear programming problem (see [11]
for further details). However, such a recovery approach cannot
be implemented in a distributed fashion. In this paper, we
adopt a variant of Shor’s rule to recovery primal optimal
feasible solution. Due to space limitation, we refer readers
to [18] for more details.
V. NUMERICAL RESULTS
In this section, we present some numerical results through
simulations to provide further insights on solving CRPA.
N randomly-generated MIMO-enabled nodes are uniformly
distributed in a square region. Each node in the network is
equipped with two antennas. The maximum transmit power for
each node is set to Pmax = 10dBm. Each node in the network
is assigned a unit bandwidth. We illustrate a 15-node network
example, as shown in Fig. 5, to show the convergence process
of the cutting-plane and the subgradient methods for solving
DCRPA−E. In this example, there are three flows transmitting
across the network: N14 to N1, N6 to N10, and N5 to N4,
respectively.
A. Cutting-Plane Method
For the 15-node example in Fig. 5, the convergence process
for the cutting-plane method is illustrated in Fig. 6. The
optimal objective value for this 15-node example is 6.72. The
optimal flows for sessions N14 to N1, N6 to N10, and N5 to
0 200 400 600 800 1000 1200 1400 1600
Number of Iterations
Lagrangian Dual UB
Pimal Feasible Solution
Fig. 7. Convergence behavior of the subgradient method
N4 are 9.17 bps/Hz, 9.30 bps/Hz, and 9.93 bps/Hz, respec-
tively. It can be observed that the cutting-plane algorithm is
very efficient: It converges with approximately 160 cuts. As
expected, the duality gap is zero because the convexity of the
transformed equivalent problem based on dual MIMO-MAC.
B. Subgradient Method
For the 15-node example in Fig. 5, the convergence process
for the subgradient method is illustrated in Fig. 7. The step
size selection is λk = 0.1/k. The subgradient method also
achieves the same optimal solution and objective value when
it converges. However, it is seen that the subgradient algorithm
takes approximately 1600 iterations to converge, which is
much slower than the cutting-plane method. This is partially
due to the heuristic nature in step size selection (cannot be too
large or too small at each step). It is also partially due to the
cumbersomeness in recovering the primal feasible solution in
the subgradient method. In this example, the dual upper bound
takes approximately 1050 iterations to reach near the optimal.
However, the near-optimal primal feasible solution cannot be
identified until after 1500 iterations.
C. Comparison between BC and TDM
We now study how much performance gain we can get by
using Gaussian vector broadcast channel technique as opposed
to the conventional time-division (TDM) scheme. The cross-
layer optimization problem of MIMO-based mesh networks
over TDM scheme is also a convex problem. Thus, the
basic Lagrangian dual decomposition framework and gradient
projection technique for the link layer subproblem are still
applicable. The only difference is in the gradient computation,
which is simpler in TDM case. For the same 15-node network
with TDM, we plot the convergence process of the cutting-
plane algorithm in Fig. 8. In TDM case, the optimal objective
value is 5.01. For this example, we have 34.4% improvement
by using DPC.
VI. RELATED WORK
Despite significant research progress in using MIMO for
single-user communications, research on multi-user multi-hop
0 10 20 30 40 50 60 70 80
Number of Iterations
Lagrangian Dual UB
Primal Feasible Solution
Fig. 8. The convergence behavior in TDM case
MIMO networks is still in its inception stage. There are many
open problems, and many areas are still poorly understood
[19]. Currently, the relatively well-studied research area of
multi-user MIMO systems are cellular systems, which are
single-hop and infrastructure-based. For multi-hop MIMO-
based mesh networks, research results remain limited. In [20],
Hu and Zhang studied the problem of joint medium access
control and routing, with a consideration of optimal hop
distance to minimize end-to-end delay. In [21], Sundaresan and
Sivakumar used simulations to study various characteristics
and tradeoffs (multiplexing gain vs. diversity gain) of MIMO
links that can be leveraged by routing layer protocols in rich
multipath environments to improve performance. In [22], Lee
et al. proposed a distributed algorithm for MIMO-based multi-
hop ad hoc networks, in which diversity and multiplexing
gains of each link are controlled to achieve the optimal rate-
reliability tradeoff. The optimization problem assumes fixed
SINRs and fixed routes between source and destination nodes.
However, in these works, there is no explicit consideration of
per-antenna power allocation and their impact on upper layers.
Moreover, DPC in cross-layer design has never been studied
either.
VII. CONCLUSIONS
In this paper, we investigated the cross-layer optimization
of DPC per-antenna power allocation and multi-hop multi-
path routing for MIMO-based wireless mesh networks. Our
contributions are three-fold. First, this paper is the first work
that studies the impacts of applying dirty paper coding, which
is the optimal transmission scheme for MIMO broadcast
channels (MIMO-BC), to the cross-layer design for MIMO-
based wireless mesh networks. We showed that the network
performance has dramatic improvements compared to that
of the conventional time-division/frequency division schemes.
Second, we solved the challenging non-connvex cross-layer
optimization problem by exploiting the channel duality be-
tween MIMO-MAC and MIMO-BC, and we showed that
transformed problem under dual MIMO-MAC is convex. We
simplified the maximum weighted sum rate problem, thus
paving the way for solving the link layer subproblem in
the Lagrangian dual decomposition. Last, for the transformed
problem, we develop an efficient solution procedure that
integrates Lagrangian dual decomposition, conjugate gradient
projection based on matrix differential calculus, cutting-plane,
and subgradient methods. Our results substantiate the impor-
tance of cross-layer optimization for MIMO-based wireless
mesh networks with Gaussian vector broadcast channels.
REFERENCES
[1] I. E. Telatar, “Capacity of multi-antenna Gaussian channels,” European
Trans. Telecomm., vol. 10, no. 6, pp. 585–596, Nov. 1999.
[2] G. J. Foschini and M. J. Gans, “On limits of wireless communications in
a fading environment when using multiple antennas,” Wireless Personal
Commun., vol. 6, pp. 311–355, Mar. 1998.
[3] T. M. Cover and J. A. Thomas, Elements of Information Theory. New
York-Chichester-Brisbane-Toronto-Singapore: John Wiley & Sons, Inc.,
1991.
[4] T. M. Cover, “Broadcast channels,” IEEE Trans. Inf. Theory, vol. 18,
no. 1, pp. 2–14, Jan. 1972.
[5] M. Costa, “Writing on dirty paper,” IEEE Trans. Inf. Theory, vol. 29,
no. 3, pp. 439–441, May 1983.
[6] H. Weingarten, Y. Steinberg, and S. Shamai (Shitz), “The capacity region
of the Gaussian multiple-input multiple-output broadcast channel,” IEEE
Trans. Inf. Theory, vol. 52, no. 9, pp. 3936–3964, Sep. 2006.
[7] M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali, Linear Programming and
Network Flows. New York-Chichester-Brisbane-Toronto-Singapore:
John Wiley & Sons Inc., 1990.
[8] S. Vishwanath, N. Jindal, and A. Goldsmith, “Duality, achievable rates,
and sum-rate capacity of MIMO broadcast channels,” IEEE Trans. Inf.
Theory, vol. 49, no. 10, pp. 2658–2668, Oct. 2003.
[9] P. Viswanath and D. N. C. Tse, “Sum capacity of the vector Gaussian
broadcast channel and uplink-downlink duality,” IEEE Trans. Inf. The-
ory, vol. 49, no. 8, pp. 1912–1921, Aug. 2003.
[10] W. Yu, “Uplink-downlink duality via minimax duality,” IEEE Trans. Inf.
Theory, vol. 52, no. 2, pp. 361–374, Feb. 2006.
[11] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming:
Theory and Algorithms, 3rd ed. New York, NY: John Wiley & Sons
Inc., 2006.
[12] S. Ye and R. S. Blum, “Optimized signaling for MIMO interference
systems with feedback,” IEEE Trans. Signal Process., vol. 51, no. 11,
pp. 2839–2848, Nov. 2003.
[13] J. R. Magnus and H. Neudecker, Matrix Differential Calculus with
Applications in Statistics and Economics. New York: Wiley, 1999.
[14] S. Haykin, Adaptive Filter Theory. Englewood Cliffs, NJ: Prentice-Hall,
1996.
[15] S. Boyd and L. Xiao, “Least-squares covariance matrix adjustment,”
SIAM Journal on Matrix Analysis and Applications, vol. 27, no. 2, pp.
532–546, Nov. 2005.
[16] J. Malick, “A dual approach to semidefinite least-squares problems,”
SIAM Journal on Matrix Analysis and Applications, vol. 26, no. 1, pp.
272–284, Sep. 2005.
[17] J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Anal-
ysis. Berlin: Springer-Verlag, 2001.
[18] H. D. Sherali and G. Choi, “Recovery of primal solutions when using
subgradient optimization methods to solve Lagrangian duals of linear
programs,” Operations Research Letters, vol. 19, no. 3, pp. 105–113,
Sep. 1996.
[19] A. Goldsmith, S. A. Jafar, N. Jindal, and S. Vishwanath, “Capacity limits
of MIMO channels,” IEEE J. Sel. Areas Commun., vol. 21, no. 1, pp.
684–702, Jun. 2003.
[20] M. Hu and J. Zhang, “MIMO ad hoc networks: Medium access control,
saturation throughput, and optimal hop distance,” Special Issue on
Mobile Ad Hoc Networks, Journal of Communications and Networks,
pp. 317–330, Dec. 2004.
[21] K. Sundaresan and R. Sivakumar, “Routing in ad hoc networks with
MIMO links,” in Proc. IEEE ICNP, Boston, MA, U.S.A., Nov. 2005,
pp. 85–98.
[22] J.-W. Lee, M. Chiang, and A. R. Calderbank, “Price-based distributed
algorithms for rate-reliability tradeoff in network utility maximization,”
IEEE J. Sel. Areas Commun., vol. 24, no. 5, pp. 962–976, May 2006.
	Introduction
	Network Model
	Network Layer
	Channel Capacity of a MIMO Link
	MIMO-BC Link Layer
	Problem Formulation
	Reformulation of CRPA
	MIMO-MAC Channel Model
	Duality between MIMO-BC and MIMO-MAC
	Convexity of MIMO-MAC Capacity Region
	Maximum Weighted Sum Rate Problem of the Dual MIMO-MAC
	Problem Reformulation
	Solution Procedure
	Conjugate Gradient Projection for Solving link(n)(u(n))
	Computing the Conjugate Gradients
	Projection onto +(Pmax(n))
	Solving the Master Dual Problem
	Cutting-Plane Method for Solving (u)
	Subgradient Algorithm for Solving (u)
	Numerical Results
	Cutting-Plane Method
	Subgradient Method
	Comparison between BC and TDM
	Related Work
	Conclusions
	References
