# Transmit Beamforming Optimization Design for Broadband Multigroup Multicast System

Authors: Zilong Zhang; Xiaodong Xu; Yanan Wu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Spectral efficient transmission techniques are necessary and promising for future broadband wireless communications, where the quality of service (QoS) and/or max-min fair (MMF) of intended users are often considered simultaneously. In this paper, both the QoS problem and the MMF problem are investigated together for transmit beamforming in broadband multigroup multicast channels with frequency-selective fading characters. We first present a basic algorithm by directly using the results in frequency-flat multigroup multicast systems (Karipidis et al., 2008), namely, the approximation algorithms in this paper, for both problems, respectively. Due to high computational consumption nature of the approximation algorithms, two reduced-complexity algorithms for each of the two problems are proposed separately by introducing the time-frequency correlations. In addition, parameters in the new time-frequency formulations, such as the number of optimization matrix variables and the taps of the
beamformer with finite impulse response (FIR) structure, can be used to make a reasonable tradeoff between computational
burden and system performance. Insights into the relationship between the two problems and some analytical results of the
computational complexity of the proposed algorithms are also studied carefully. Numerical simulations indicate the efficiency
of the proposed algorithms.


---

## Body

## 1. Introduction

Targeting for supporting high throughput and link reliability, multiple-antenna transmission techniques have prevailed in the development of terrestrial wireless communication systems, such as Long Term Evolution Advanced (LTE-A) [1] and future mobile telecommunication networks [2]. Not surprisingly, when equipped with multiple antennas at the transmit side, physical-layer multicasting renders its great advantage in spectral efficiency over the other communication mechanisms, especially for some particular applications, including network video service and online gaming. In this regard, transmit beamforming has received enormous attentions in the literature, where perfect channel state information (CSI) is assumed available at both ends and the channel between each transmit antenna and receive antenna appears frequency-flat fading property.To provide performance assurance to each of the intended receivers in multicast systems, the quality of service (QoS) problem [3] and the max-min fair (MMF) problem [4] are usually formulated and investigated in the literature, where the criteria of minimizing the total transmission power under each user’s minimum signal-to-interference-plus-noise ratio (SINR) constraint and maximizing the minimum SINR among all users under the average transmit power constraint are considered, respectively. Due to the NP-hardness of the optimization problems, several efficient algorithms have been proposed to guarantee satisfactory performance in single-group multicast scenario. What is more, an analytical result of these two problems was extended to the case of multigroup multicasting in [5], where a solid algorithm based on both semidefinite relaxation (SDR) [6] and Gaussian randomization was proposed to solve the multigroup QoS problem and then an iterative algorithm based on a one-dimensional bisection search [7] was also adopted to handle the MMF problem. To achieve improved performance for the multigroup QoS problem, the authors of [8] proposed an iterative algorithm which solves an approximate second-order cone programming (SOCP) problem in each iteration. And in [9], an iterative algorithm with low complexity and superior performance was further investigated to cope with the multigroup MMF problem. Recently, contrary to the total transmission power constraints, transmit beamforming under per-antenna power constraints (PACs) was introduced in [10–12]. As an extending work of [5], the weighted multigroup multicast MMF problem with PACs was investigated in [12]. For the sake of clear expression, related works are listed in Table 1.Table 1
List of related works.
Problem description
Application scenarios
Solving approach
Source
QoS
Broadcast
SDR
[3]
MMF
Broadcast
Iterative algorithm
[4]
QoS
Multigroup multicast
SDR + Gaussian randomization
[5]
MMF
Multigroup multicast
SDR + Gaussian randomization + bisection
[5]
QoS
Multigroup multicast
Iterative algorithm
[8]
MMF
Multigroup multicast
Iterative algorithm
[9]
QoS
Broadcast with PACs
Iterative algorithm  +  duality
[10]
MMF
Broadcast with PACs
Iterative algorithm  +  duality
[11]
MMF
Multigroup multicast with PACs
SDR + Gaussian randomization + bisection
[12]As aforementioned, the design of transmit beamformer has been primarily studied over multiple-antenna multicasting and frequency-flat fading channels and, to the authors’ best knowledge, few works have been dedicated to the case of frequency-selective fading multicasting scenario. Motivated by the potential advantages of multiple-antenna transmission over the frequency-selective fading channels, we are concerned about the QoS and MMF problems in this paper for multigroup multicasting. The main contributions of this paper are listed in the following:(1)
For the QoS problem, an approximation algorithm is firstly derived for broadband systems based on the idea of narrowband multigroup multicasting in [5]. And two reduced-complexity algorithms are also proposed from the frequency-domain and the time-domain perspectives separately. Some parameters in correlation with the QoS problem are analyzed and computational consumption is comparatively computed to show more insights into the tradeoff between performance and complexity.
(2)
For the MMF problem, the corresponding approximation algorithm and its low-complexity modifications are also proposed in a similar way as that of QoS problem. Furthermore, the relationship between the QoS problem and the MMF problem is discussed carefully followed by a complexity analysis.
(3)
Simulation experiments demonstrate the effectiveness of the frequency-domain and the time-domain algorithms for both QoS problem and MMF problem. The main analysis results that the controlled parameters in the proposed algorithms could be used to make a tradeoff between complexity and performance are verified through the numerical examples.The remainder of this paper is structured as follows. In Section2, the system model and the QoS problem are introduced briefly. The approximation solution to the QoS problem is derived in Section 3. And Section 4 presents two beamforming algorithms. Section 5 formulates the MMF problem and solves it based on the proposed algorithms. Computational complexity analysis of proposed algorithms is given in Section 6. In Section 7, the performance of the proposed algorithms is evaluated and discussed. Finally, the conclusion is summarized in Section 8.Notations. In the remainder of this paper, boldface uppercase letters and math calligraphy uppercase letters denote matrices, and boldface lowercase letters denote vectors. (
·
)
†, E
(
·
), and t
r
(
·
) are the conjugate transpose, the expectation, and the trace operator, respectively. C indicates the set of complex numbers, while ⊗ is Kronecker product. · defines the floor function, A
1
/
2 is matrix square root function of A, and δ
(
·
) is the impulse function. A
~
C
N
(
0
,
I
) means that A is circularly symmetric complex Gaussian process with zero mean and unit variance matrix.


## 2. System Model and Problem Statement

### 2.1. System Model

Consider a multigroup multicast system with one transmitter (base station) andK receivers (users). Assume the transmitter has M
t antenna elements and each receiver is equipped with one antenna. The users are split into 1
≤
L
≤
K groups {
g
1
,
g
2
,
…
,
g
L
}, each containing K
g
l user indices. We assume that each user listens to a single multicast group; that is, g
l
∩
g
l
′
=
∅, where l
≠
l
′, and ∪
l
g
l
=
{
1
,
…
,
K
}. A frequency-selective fading channel with V effective paths is supposed between each transmit antenna and receive antenna, and full CSI is available a priori at the transmit side throughout this paper.With anO-tap FIR beamforming filter, the transmitted signal can be written as follows in space-time domain: (1)
s
n
=
∑
l
=
0
L
-
1
∑
o
=
0
O
-
1
w
l
,
o
x
l
,
n
-
o
,where w
l
,
o
∈
C
M
t
×
1 and x
l
,
o denote the beamforming vector and the discrete information sequence in association with the oth tap of FIR beamforming filter for the lth group, respectively. n stands for the time index. Figure 1 shows the schematic diagram of a multigroup multicast system. Without loss of generality (W.L.O.G.), assume the information sequence is zero mean with unit variance and mutually uncorrelated; that is, E
{
x
l
,
o
x
l
,
o
-
τ
}
=
δ
(
τ
)
·
δ
(
l
). Then for the mth user in the lth group, the received signal has the form as(2)
y
l
,
m
,
n
=
∑
v
=
0
V
-
1
H
l
,
m
,
v
s
n
-
v
+
u
l
,
m
,
n
=
∑
v
=
0
V
-
1
H
l
,
m
,
v
∑
o
=
0
O
-
1
w
l
,
o
x
l
,
n
-
v
-
o
︸
desired  signal  of  the
l
th  group
+
∑
v
=
0
V
-
1
H
l
,
m
,
v
∑
l
′
≠
l
∑
o
=
0
O
-
1
w
l
′
,
o
x
l
′
,
n
-
v
-
o
︸
hybrid  interference  signals  from  the  other  groups
+
u
l
,
m
,
n
,where H
l
,
m
,
v
∈
C
1
×
M
t is the channel impulse response of the vth path between the transmitter and the mth user in the lth group and u
l
,
m
,
n is an additive Gaussian noise at the mth user with zero mean and unit variance.Figure 1
The schematic diagram of a multigroup multicast system.For brevity purpose, (2) can be represented by Z-transform; that is,(3)
y
l
,
m
,
n
=
H
l
,
m
W
l
z
X
l
,
n
z
+
H
l
,
m
z
∑
l
′
≠
l
W
l
′
z
X
l
′
,
n
z
+
u
l
,
m
,
n
,where H
l
,
m
z
=
∑
v
=
0
V
-
1
H
l
,
m
,
v
z
-
v, W
l
z
=
∑
o
=
0
O
-
1
w
l
,
o
z
-
o, and X
l
,
n
z
=
∑
p
=
0
V
+
O
-
2
x
l
,
n
-
V
-
O
+
2
+
p
z
-
p.In this regard, the total transmission power of the multigroup multicast system becomes(4)
P
t
=
∑
l
=
0
L
-
1
∫
0
1
W
l
f
2
2
d
f
.Similarly, the SINR at the mth receiver in the lth group can be formulated as (5)
S
I
N
R
l
,
m
=
∫
0
1
H
l
,
m
f
W
l
f
W
l
†
f
H
l
,
m
†
f
d
f
∑
l
′
≠
l
∫
0
1
H
l
,
m
f
W
l
′
f
W
l
′
†
f
H
l
,
m
†
f
d
f
+
σ
l
,
m
2
,where σ
l
,
m
2
=
E
{
u
l
,
m
,
n
u
l
,
m
,
n
†
}, H
l
,
m
(
f
)
=
H
l
,
m
(
z
)
|
z
=
e
j
2
π
f, and W
l
(
f
)
=
W
l
(
z
)
|
z
=
e
j
2
π
f.


### 2.2. QoS Problem Statement

With the above-mentioned assumptions and definitions, the problem of minimizing the total transmission power under the SINR constraints of each userγ
l
,
m, namely, the QoS problem, can be expressed as (6)
P
1
:
min
⁡
W
l
f
P
t
s.t.
S
I
N
R
l
,
m
≥
γ
l
,
m
,
∀
m
,
∀
l
,
∀
m
∈
g
l and ∀
l
∈
{
0
,
…
,
L
-
1
}. To solve this problem, the following discrete-time form is usually adopted; that is, (7)
P
2
:
min
⁡
W
l
,
i
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
W
l
,
i
2
2
s.t.
S
I
N
R
′
l
,
m
≥
γ
l
,
m
,
∀
m
,
∀
l
,with (8)
S
I
N
R
′
l
,
m
=
1
/
I
∑
i
=
0
I
-
1
H
l
,
m
,
i
W
l
,
i
W
l
,
i
†
H
l
,
m
,
i
†
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
H
l
,
m
,
i
W
l
′
,
i
W
l
′
,
i
†
H
l
,
m
,
i
†
+
σ
l
,
m
2
,where I is a sufficiently large positive integer, H
l
,
m
,
i
=
H
l
,
m
z
|
z
=
e
j
2
π
i
/
I, and W
l
,
i
=
W
l
z
|
z
=
e
j
2
π
i
/
I.Note that problemP
2 is a discrete approximation of problem P
1, and its approximate accuracy increases as I approaches infinity. In fact, it is a quadratically constrained quadratic programming (QCQP) problem with nonconvex constraints. Moreover, as a special case of this problem, multigroup multicasting over frequency-flat fading channel (i.e., V
=
1) has been proven to be NP-hard in [5]. Therefore, problem P
2 is NP-hardness, which motivates us to pursue an approximate solution of it.


## 2.1. System Model

Consider a multigroup multicast system with one transmitter (base station) andK receivers (users). Assume the transmitter has M
t antenna elements and each receiver is equipped with one antenna. The users are split into 1
≤
L
≤
K groups {
g
1
,
g
2
,
…
,
g
L
}, each containing K
g
l user indices. We assume that each user listens to a single multicast group; that is, g
l
∩
g
l
′
=
∅, where l
≠
l
′, and ∪
l
g
l
=
{
1
,
…
,
K
}. A frequency-selective fading channel with V effective paths is supposed between each transmit antenna and receive antenna, and full CSI is available a priori at the transmit side throughout this paper.With anO-tap FIR beamforming filter, the transmitted signal can be written as follows in space-time domain: (1)
s
n
=
∑
l
=
0
L
-
1
∑
o
=
0
O
-
1
w
l
,
o
x
l
,
n
-
o
,where w
l
,
o
∈
C
M
t
×
1 and x
l
,
o denote the beamforming vector and the discrete information sequence in association with the oth tap of FIR beamforming filter for the lth group, respectively. n stands for the time index. Figure 1 shows the schematic diagram of a multigroup multicast system. Without loss of generality (W.L.O.G.), assume the information sequence is zero mean with unit variance and mutually uncorrelated; that is, E
{
x
l
,
o
x
l
,
o
-
τ
}
=
δ
(
τ
)
·
δ
(
l
). Then for the mth user in the lth group, the received signal has the form as(2)
y
l
,
m
,
n
=
∑
v
=
0
V
-
1
H
l
,
m
,
v
s
n
-
v
+
u
l
,
m
,
n
=
∑
v
=
0
V
-
1
H
l
,
m
,
v
∑
o
=
0
O
-
1
w
l
,
o
x
l
,
n
-
v
-
o
︸
desired  signal  of  the
l
th  group
+
∑
v
=
0
V
-
1
H
l
,
m
,
v
∑
l
′
≠
l
∑
o
=
0
O
-
1
w
l
′
,
o
x
l
′
,
n
-
v
-
o
︸
hybrid  interference  signals  from  the  other  groups
+
u
l
,
m
,
n
,where H
l
,
m
,
v
∈
C
1
×
M
t is the channel impulse response of the vth path between the transmitter and the mth user in the lth group and u
l
,
m
,
n is an additive Gaussian noise at the mth user with zero mean and unit variance.Figure 1
The schematic diagram of a multigroup multicast system.For brevity purpose, (2) can be represented by Z-transform; that is,(3)
y
l
,
m
,
n
=
H
l
,
m
W
l
z
X
l
,
n
z
+
H
l
,
m
z
∑
l
′
≠
l
W
l
′
z
X
l
′
,
n
z
+
u
l
,
m
,
n
,where H
l
,
m
z
=
∑
v
=
0
V
-
1
H
l
,
m
,
v
z
-
v, W
l
z
=
∑
o
=
0
O
-
1
w
l
,
o
z
-
o, and X
l
,
n
z
=
∑
p
=
0
V
+
O
-
2
x
l
,
n
-
V
-
O
+
2
+
p
z
-
p.In this regard, the total transmission power of the multigroup multicast system becomes(4)
P
t
=
∑
l
=
0
L
-
1
∫
0
1
W
l
f
2
2
d
f
.Similarly, the SINR at the mth receiver in the lth group can be formulated as (5)
S
I
N
R
l
,
m
=
∫
0
1
H
l
,
m
f
W
l
f
W
l
†
f
H
l
,
m
†
f
d
f
∑
l
′
≠
l
∫
0
1
H
l
,
m
f
W
l
′
f
W
l
′
†
f
H
l
,
m
†
f
d
f
+
σ
l
,
m
2
,where σ
l
,
m
2
=
E
{
u
l
,
m
,
n
u
l
,
m
,
n
†
}, H
l
,
m
(
f
)
=
H
l
,
m
(
z
)
|
z
=
e
j
2
π
f, and W
l
(
f
)
=
W
l
(
z
)
|
z
=
e
j
2
π
f.


## 2.2. QoS Problem Statement

With the above-mentioned assumptions and definitions, the problem of minimizing the total transmission power under the SINR constraints of each userγ
l
,
m, namely, the QoS problem, can be expressed as (6)
P
1
:
min
⁡
W
l
f
P
t
s.t.
S
I
N
R
l
,
m
≥
γ
l
,
m
,
∀
m
,
∀
l
,
∀
m
∈
g
l and ∀
l
∈
{
0
,
…
,
L
-
1
}. To solve this problem, the following discrete-time form is usually adopted; that is, (7)
P
2
:
min
⁡
W
l
,
i
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
W
l
,
i
2
2
s.t.
S
I
N
R
′
l
,
m
≥
γ
l
,
m
,
∀
m
,
∀
l
,with (8)
S
I
N
R
′
l
,
m
=
1
/
I
∑
i
=
0
I
-
1
H
l
,
m
,
i
W
l
,
i
W
l
,
i
†
H
l
,
m
,
i
†
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
H
l
,
m
,
i
W
l
′
,
i
W
l
′
,
i
†
H
l
,
m
,
i
†
+
σ
l
,
m
2
,where I is a sufficiently large positive integer, H
l
,
m
,
i
=
H
l
,
m
z
|
z
=
e
j
2
π
i
/
I, and W
l
,
i
=
W
l
z
|
z
=
e
j
2
π
i
/
I.Note that problemP
2 is a discrete approximation of problem P
1, and its approximate accuracy increases as I approaches infinity. In fact, it is a quadratically constrained quadratic programming (QCQP) problem with nonconvex constraints. Moreover, as a special case of this problem, multigroup multicasting over frequency-flat fading channel (i.e., V
=
1) has been proven to be NP-hard in [5]. Therefore, problem P
2 is NP-hardness, which motivates us to pursue an approximate solution of it.


## 3. Approximate Solution

LetQ
l
,
i
=
W
l
,
i
W
l
,
i
†, and we can get the equivalent form of problem P
2
(9)
P
3
:
min
⁡
Q
l
,
i
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
Q
l
,
i
s.t.
S
I
N
R
l
,
m
r
≥
γ
l
,
m
Q
l
,
i
⪰
0
rank
⁡
Q
l
,
i
=
1
,
∀
i
,
∀
m
,
∀
l
,where (10)
S
I
N
R
l
,
m
r
=
1
/
I
∑
i
=
0
I
-
1
H
l
,
m
,
i
Q
l
,
i
H
l
,
m
,
i
†
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
H
l
,
m
,
i
Q
l
′
,
i
H
l
,
m
,
i
†
+
σ
l
,
m
2
,
∀
i
∈
{
0
,
…
,
I
-
1
}, ∀
m
∈
g
l, and ∀
l
∈
{
0
,
…
,
L
-
1
} in this section.Due to the nonconvex nature of problemP
3, we drop the L
·
I rank-one constraints and obtain a semidefinite programming (SDP) variation(11)
P
4
:
min
⁡
Q
l
,
i
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
tr
⁡
⁡
Q
l
,
i
s
.
t
.
S
I
N
R
l
,
m
r
≥
γ
l
,
m
Q
l
,
i
⪰
0
,
∀
i
,
∀
m
,
∀
l
.It is noteworthy that problemP
4 can be handled by interior point method (IPM) [13] and the feasible set of this problem is actually a superset of that of problem P
3. As a consequence, the optimum objective value of problem P
4 is certainly equal or less than that of problem P
3.Proposition 1.
The optimal solution{
Q
l
,
i
} of problem P
4 satisfies(12)
rank
⁡
Q
l
,
i
≤
K
g
l
,
∀
i
,
∀
l
,
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
rank
2
⁡
Q
l
,
i
≤
K
.Proof.
In order to prove this proposition, the dual problem of problemP
4 is first considered and formulated as(13)
D
1
:
max
⁡
θ
l
,
m
∑
l
=
0
L
-
1
∑
m
∈
g
l
θ
l
,
m
γ
l
,
m
σ
l
,
m
2
s.t.
Y
l
,
i
⪰
0
θ
l
,
m
≥
0
,
∀
i
,
∀
m
,
∀
l
,where Y
l
,
i
=
I
+
∑
l
′
≠
l
‍
∑
m
∈
g
l
′
θ
l
′
,
m
γ
l
′
,
m
H
l
′
,
m
,
i
†
H
l
′
,
m
,
i
-
∑
m
∈
g
l
θ
l
,
m
H
l
,
m
,
i
†
H
l
,
m
,
i and θ
l
,
m is the dual variable associated with SINR constraints in problem P
4. Based on the complementarity conditions which are part of the Karush-Kuhn-Tucker (KKT) conditions, we have(14)
Y
l
,
i
Q
l
,
i
=
I
+
∑
l
′
≠
l
∑
m
∈
g
l
′
θ
l
′
,
m
γ
l
′
,
m
H
l
′
,
m
,
i
†
H
l
′
,
m
,
i
-
∑
m
∈
g
l
θ
l
,
m
H
l
,
m
,
i
†
H
l
,
m
,
i
Q
l
,
i
=
0and then we can calculate the rank of Θ
l
,
i
Q
l
,
i by defining Θ
l
,
i
=
I
+
∑
l
′
≠
l
‍
∑
m
∈
g
l
′
θ
l
′
,
m
γ
l
′
,
m
H
l
′
,
m
,
i
†
H
l
′
,
m
,
i
≻
0, which immediately leads to(15)
rank
⁡
Θ
l
,
i
Q
l
,
i
=
rank
⁡
Q
l
,
i
=
rank
⁡
∑
m
∈
g
l
θ
l
,
m
H
l
,
m
,
i
†
H
l
,
m
,
i
Q
l
,
i
≤
∑
m
∈
g
l
rank
⁡
θ
l
,
m
H
l
,
m
,
i
†
H
l
,
m
,
i
Q
l
,
i
≤
K
g
l
.
On the other hand, according to Theorem 3.2 in [14], it is readily to verify that the optimal solution to problem P
4 satisfies ∑
l
=
0
L
-
1
‍
∑
i
=
0
I
-
1
‍
r
a
n
k
2
(
Q
l
,
i
)
≤
K.From Proposition1, it appears that when each group has only one user, that is, K
g
l
=
1, we have r
a
n
k
(
Q
¯
l
,
i
)
≤
1, which means problem P
4 is actually equivalent to problem P
3 in this case, which will obviously result in a frequency-selective fading extension of the work in [3]. In general, if the solution of problem P
4 meets the rank-one constraint, that is, r
a
n
k
(
Q
l
,
i
)
=
1, an eigenvalue decomposition (EVD) of Q
l
,
i
=
U
l
,
i
Λ
l
,
i
U
l
,
i
† may help to generate the frequency-domain beamforming vectors, where W
l
,
i
=
U
l
,
i
Λ
l
,
i
1
/
2
(
:
,
1
). Otherwise, the Gaussian randomization technique [5] is used to obtain candidates of the beamforming vector; that is, {
W
l
,
i
q
=
U
l
,
i
Λ
l
,
i
1
/
2
V
l
,
i
q
}, q
=
1,2
,
…
,
Q, where Q is the maximum number of the randomizations and V
l
,
i
q
∈
C
M
t
×
1
~
C
N
(
0
,
I
).Note that although these processed candidates satisfyE
{
W
l
,
i
q
W
l
,
i
q
†
}
=
Q
l
,
i and r
a
n
k
(
W
l
,
i
q
W
l
,
i
q
†
)
=
1, they may still violate SINR constraints. For each candidate, a feasible allocated power should thus be figured out by solving a multigroup multicast power control (MMPC) problem; that is,(16)
M
1
:
min
⁡
p
l
,
i
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
p
l
,
i
β
l
,
i
s.t.
1
/
I
∑
i
=
0
I
-
1
p
l
,
i
α
l
,
m
,
i
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
p
l
′
,
i
α
l
′
,
m
,
i
+
σ
l
,
m
2
≥
γ
l
,
m
p
l
,
i
≥
0
,
∀
i
,
∀
m
,
∀
l
,where p
l
,
i denotes the power factor for the beamformer W
l
,
i
q. β
l
,
i
=
W
l
,
i
q
2
2, α
l
,
m
,
i
=
H
l
,
m
,
i
W
l
,
i
q
W
l
,
i
q
†
H
l
,
m
,
i
†, and α
l
′
,
m
,
i
=
H
l
,
m
,
i
W
l
′
,
i
q
W
l
′
,
i
q
†
H
l
,
m
,
i
†. Problem M
1 is of linear program (LP) and can be easily solved by basic convex tools if the optimal solution exists. The resulting frequency-domain beamformer can thus be generated by p
l
,
i
W
l
,
i
q, and the associated objective value (
1
/
I
)
∑
l
=
0
L
-
1
‍
∑
i
=
0
I
-
1
‍
p
l
,
i
β
l
,
i is recorded.Whenq reaches Q, the beamformer corresponding to the best candidate with minimum objective value can be selected as the optimal one. The detailed process of the approximation algorithm is summarized in Algorithm 1.Algorithm 1:Approximation algorithm.
(1)Input: H
l
,
m
,
i, σ
l
,
m, γ
l
,
m, Q;
(2) solve SDP problem P
4 by IPM;
(3) if  rank
⁡
(
Q
l
,
i
)
=
1
,
∀
i
,
∀
l  then
(4)  W
l
,
i
=
U
l
,
i
Λ
l
,
i
1
/
2
(
:
,
1
);
(5)  break;
(6) else
(7)  calculate EVD: Q
l
,
i
=
U
l
,
i
Λ
l
,
i
U
l
,
i
†;
(8)  for  q
=
1 to Q  do
(9)    generate candidates W
l
,
i
q
=
U
l
,
i
Λ
l
,
i
1
/
2
V
l
,
i
q;
(10)  solve MMPC problem M
1 to obtain p
l
,
i
W
l
,
i
q;
(11) end
(12) choose {
W
l
,
i
}
=
arg
⁡
min
{
p
l
,
i
W
l
,
i
q
}
⁡
∑
l
=
0
L
-
1
‍
∑
i
=
0
I
-
1
p
l
,
i
β
l
,
i;
(13) end
(14) Output: {
W
l
,
i
}.More clearly, the approximation algorithm can be treated as a direct use of the algorithm in [5] on every frequency bin for frequency-selective multigroup multicast system. The higher approximation accuracy is, the larger I may be introduced. For example, an I
=
128 or larger is often needed for practical systems, which will lead to extremely high computational complexity. A computing-strong ability is thus required at the transmitter; otherwise we may not figure out the exact beamformers by the approximation algorithm when the channel coefficients change with rapid fluctuation.


## 4. Proposed Beamforming Algorithms

To combat the heavy computation burden of the approximation algorithm, new beamforming algorithms which can make tradeoff between performance and complexity are eagerly demanded in these situations. Towards this end, two beamforming algorithms are proposed from perspectives of frequency domain and time-domain, respectively, in this section.


### 4.1. Beamforming Design in Frequency Domain

In fact, the channel coefficient vectorH
l
,
m
,
i has certain correlation with H
l
,
m
,
i
′ when i and i
′ are close to each other. It follows that we can reduce the complexity of solving the SDP problem P
4 by reducing the number of optimization variables. More clearly, the frequency-domain channel vectors {
H
l
,
m
,
i
}
i
=
0
I
-
1 can now be divided into several groups. Assume each group has F vectors (here I should be divisible by F), and there are I
/
F groups for {
H
l
,
m
,
i
}
i
=
0
I
-
1. In this way, we only need to optimize {
Q
l
,
i
}
i
=
0
I
/
F
-
1 and the optimization problem can be converted to(17)
P
5
:
min
⁡
Q
l
,
i
i
=
0
I
/
F
-
1
F
I
∑
l
=
0
L
-
1
∑
i
=
0
I
/
F
-
1
t
r
Q
l
,
i
s.t.
S
I
N
R
l
,
m
r
1
≥
γ
l
,
m
Q
l
,
i
⪰
0
rank
⁡
Q
l
,
i
=
1
,
∀
i
,
∀
m
,
∀
l
,where (18)
S
I
N
R
l
,
m
r
1
=
1
/
I
∑
i
=
0
I
-
1
H
l
,
m
,
i
Q
l
,
i
/
F
+
1
H
l
,
m
,
i
†
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
H
l
,
m
,
i
Q
l
′
,
i
/
F
+
1
H
l
,
m
,
i
†
+
σ
l
,
m
2
,
∀
i
∈
{
0
,
…
,
I
/
F
-
1
}, ∀
m
∈
g
l, and ∀
l
∈
{
0
,
…
,
L
-
1
} in this subsection. Similarly, by dropping the L
I
/
F rank-one constraints, an SDP problem can then be obtained as(19)
P
6
:
min
⁡
Q
l
,
i
i
=
0
I
/
F
-
1
F
I
∑
l
=
0
L
-
1
∑
i
=
0
I
/
F
-
1
t
r
Q
l
,
i
s.t.
S
I
N
R
l
,
m
r
1
≥
γ
l
,
m
Q
l
,
i
⪰
0
,
∀
i
,
∀
m
,
∀
l
,and the corresponding MMPC problem follows that(20)
M
2
:
min
⁡
p
l
,
i
i
=
0
I
/
F
-
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
p
l
,
i
/
F
+
1
β
l
,
i
s.t.
1
/
I
∑
i
=
0
I
-
1
p
l
,
i
/
F
+
1
α
l
,
m
,
i
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
p
l
′
,
i
/
F
+
1
α
l
′
,
m
,
i
+
σ
l
,
m
2
≥
γ
l
,
m
p
l
,
i
≥
0
,
∀
i
,
∀
m
,
∀
l
,where p
l
,
i denotes the power factor for the beamformer W
l
,
i
q, and β
l
,
i
=
W
l
,
i
/
F
+
1
q
2
2. Accordingly, we have α
l
,
m
,
i
=
H
l
,
m
,
i
W
l
,
i
/
F
+
1
q
W
l
,
i
/
F
+
1
q
†
H
l
,
m
,
i
†, and α
l
′
,
m
,
i
=
H
l
,
m
,
i
W
l
′
,
i
/
F
+
1
q
W
l
′
,
i
/
F
+
1
q
†
H
l
,
m
,
i
†. Thanks to similar randomization process as Algorithm 1, the frequency-domain algorithm is summarized in Algorithm 2.Algorithm 2:Frequency-domain algorithm.
(1) Input: H
l
,
m
,
i, σ
l
,
m, γ
l
,
m, F, Q;
(2) solve SDP problem P
6 by IPM;
(3) if  rank
⁡
(
Q
l
,
i
)
=
1
,
∀
i
,
∀
l  then
(4)   W
l
,
i
=
U
l
,
i
Λ
l
,
i
1
/
2
(
:
,
1
);
(5)   b
r
e
a
k;
(6) else
(7)   calculate EVD: Q
l
,
i
=
U
l
,
i
Λ
l
,
i
U
l
,
i
†;
(8)   for  q
=
1 to Q  do
(9)    generate candidates W
l
,
i
q
=
U
l
,
i
Λ
l
,
i
1
/
2
V
l
,
i
q;
(10)  solve MMPC problem M
2 to obtain p
l
,
i
W
l
,
i
q;
(11) end
(12) choose
W
l
,
i
=
arg
⁡
min
{
p
l
,
i
W
l
,
i
q
}
⁡
∑
l
=
0
L
-
1
‍
∑
i
=
0
I
-
1
p
l
,
i
/
F
+
1
β
l
,
i;
(13) end
(14) Output: {
W
l
,
i
}.As a matter of convenience, denoteP
5
(
γ
,
F
) as the frequency-domain problem with parameters γ and F. Here γ
≜
[
γ
0,0
,
γ
0,1
,
…
,
γ
0
,
m
,
…
,
γ
l
,
m
]. Obviously, the proposed beamforming design in frequency-domain can be treated as a special case of the approximate solution presented in the previous section. In other words, if the parameter F is set to be 1, the frequency-domain QoS problem P
5
(
γ
,
1
) is equivalent to the QoS problem P
3
(
γ
).The following results shed more lights on the influence of the controlling parameterF.Proposition 2.
Assume problemP
5
(
γ
,
F
1
) is feasible with a fixed set of channel vectors, SINR constraints, and noise powers; the sufficient condition for problem P
5
(
γ
,
F
2
) to be also feasible is that F
1 can be divisible by F
2.Proof.
Assume{
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 denotes the optimal solution to problem P
5
(
γ
,
F
1
). For any F
2 which satisfies that F
1 is divisible by F
2, {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 can be expanded as {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1, where {
Q
l
,
i
e
x
p
}
i
=
i
′
F
1
/
F
2
(
i
′
+
1
)
F
1
/
F
2
-
1
=
Q
l
,
i
′. It can be verified that {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1 is a feasible solution to problem P
5
(
γ
,
F
2
) by substituting it.Proposition 3.
AssumeP
5
(
γ
,
F
1
) is feasible with a fixed set of channel vectors, SINR constraints, and noise powers with optimal value P
1. If F
1 is divisible by F
2, the optimal value of problem P
5
(
γ
,
F
2
), defined as P
2, is less than or equal to P
1; that is, P
2
≤
P
1, and the equality holds up if and only if the solutions of these two problems are the same.Proof.
Define the optimal solution to problemP
5
(
γ
,
F
1
) to be {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 with optimal value P
1. From the proof of Proposition 2, {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 can be expanded to {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1 which is a feasible solution to problem P
5
(
γ
,
F
2
) with optimal value P
1. Assume the optimal solution to problem P
5
(
γ
,
F
2
) is {
Q
l
,
i
o
p
t
}
i
=
0
I
/
F
2
-
1 with optimal value P
2. Due to the optimality, {
Q
l
,
i
o
p
t
}
i
=
0
I
/
F
2
-
1 is at least a good solution as {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1; thus we have P
2
≤
P
1. And if the {
Q
l
,
i
o
p
t
}
i
=
0
I
/
F
2
-
1 can be obtained by {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1, P
2
=
P
1 holds.


### 4.2. Beamforming Design in Time-Domain

Besides reducing the number of optimization variables in frequency-domain immediately, an alternative way can also benefit the complexity reduction by cutting down the number of the FIR filter taps from time-domain perspective. Assume the time-domain FIR filter hasC taps, where C is far less than I; the transmitted signal in (1) changes to (21)
s
n
=
∑
l
=
0
L
-
1
∑
c
=
0
C
-
1
w
l
,
c
x
l
,
n
-
c
.Define (22)
W
l
,
i
=
∑
c
=
0
C
-
1
w
l
,
c
e
-
2
π
i
c
/
I
,which can be converted into an equation in Kronecker form (23)
W
l
,
i
=
1
e
-
j
2
π
i
/
N
⋮
e
-
j
2
π
i
C
-
1
/
N
T
⊗
I
M
t
︸
K
i
·
w
l
,
0
w
l
,
1
⋮
w
l
,
C
-
1
︸
W
¯
l
,with K
i
∈
C
M
t
×
C
M
t and W
¯
l
∈
C
C
M
t
×
1. In the sequel, the total transmission power is reformulated accordingly as (24)
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
tr
⁡
Q
l
,
i
=
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
W
l
,
i
W
l
,
i
′
=
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
K
i
W
¯
l
W
¯
l
†
K
i
†
.By defining Q
¯
l
=
W
¯
l
W
¯
l
†, the QoS problem thus becomes(25)
P
7
:
min
⁡
Q
¯
l
l
=
0
L
-
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
K
i
Q
¯
l
K
i
†
s.t.
S
I
N
R
l
,
m
r
2
≥
γ
l
,
m
Q
¯
l
⪰
0
rank
⁡
Q
¯
l
=
1
,
∀
m
,
∀
l
,with (26)
S
I
N
R
l
,
m
r
2
=
1
/
I
∑
i
=
0
I
-
1
t
r
H
l
,
m
,
i
K
i
Q
¯
l
K
i
†
H
l
,
m
,
i
†
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
t
r
H
l
,
m
,
i
K
i
Q
¯
l
′
K
i
†
H
l
,
m
,
i
†
+
σ
l
,
m
2
,and ∀
m
∈
g
l, ∀
l
∈
{
0
,
…
,
L
-
1
} in this subsection. Similar to previous two algorithms, an SDP problem is obtained after dropping L rank-one constraints:(27)
P
8
:
min
⁡
Q
¯
l
l
=
0
L
-
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
K
i
Q
¯
l
K
i
†
s.t.
S
I
N
R
l
,
m
r
2
≥
γ
l
,
m
Q
¯
l
⪰
0
,
∀
m
,
∀
l
,and the corresponding MMPC problem can be represented as(28)
M
3
:
min
⁡
p
l
l
=
0
L
-
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
p
l
β
l
,
i
s.t.
1
/
I
∑
i
=
0
I
-
1
p
l
α
l
,
m
,
i
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
p
l
′
α
l
′
,
m
,
i
+
σ
l
,
m
2
≥
γ
l
,
m
p
l
≥
0
,
∀
m
,
∀
l
,where p
l is the power factor for the beamformer W
¯
l
q, and β
l
,
i
=
t
r
(
K
i
Q
¯
l
q
K
i
†
). Accordingly, we have α
l
,
m
,
i
=
H
l
,
m
,
i
K
i
Q
¯
l
q
K
i
†
H
l
,
m
,
i
†, and α
l
′
,
m
,
i
=
H
l
,
m
,
i
K
i
Q
¯
l
′
q
K
i
†
H
l
,
m
,
i
†. Again, we can summarize the detailed procedure of the time-domain algorithm in Algorithm 3.Algorithm 3:Time-domain algorithm.
(1) Input: H
l
,
m
,
i, σ
l
,
m, γ
l
,
m, C, Q;
(2) solve SDP problem P
8 by IPM;
(3) if  rank
⁡
(
Q
¯
l
)
=
1
,
∀
l  then
(4)  W
¯
l
=
U
¯
l
Λ
¯
l
1
/
2
(
:
,
1
);
(5)  break;
(6) else
(7)  calculate EVD: Q
¯
l
=
U
¯
l
Λ
¯
l
U
¯
l
†;
(8)  for  q
=
1 to Q  do
(9)    generate candidates W
¯
l
q
=
U
¯
l
Λ
¯
l
1
/
2
V
¯
l
q;
(10)  solve MMPC problem M
3 to obtain p
l
W
¯
l
q;
(11) end
(12) choose {
W
¯
l
}
=
arg
⁡
min
{
p
l
W
¯
l
q
}
⁡
∑
l
=
0
L
-
1
‍
∑
i
=
0
I
-
1
p
l
β
l
,
i;
(13) end
(14) Output: {
W
¯
l
}.From Algorithm3, it is clear that if the parameter C is set to be I, the time-domain QoS problem P
7
(
γ
,
C
) is equivalent to the QoS problem P
3
(
γ
). The following propositions state some further results according to this problem.Proposition 4.
If problemP
7
(
γ
,
C
1
) is feasible with a fixed set of channel vectors, SINR constraints, and noise powers, the sufficient condition for problem P
7
(
γ
,
C
2
) to be also feasible is that C
2 should be greater than C
1.Proof.
Assume{
Q
¯
l
o
p
t
}
l
=
0
L
-
1 denotes the optimal solution to problem P
7
(
γ
,
C
1
). For any C
2 which satisfies that C
2 is greater than C
1, the solution {
Q
¯
l
o
p
t
}
l
=
0
L
-
1 to problem P
7
(
γ
,
C
1
) can be expanded as {
Q
¯
l
e
x
p
}
l
=
0
L
-
1, where (29)
Q
¯
l
e
x
p
l
=
0
L
-
1
=
Q
¯
l
o
p
t
l
=
0
L
-
1
0
C
1
M
t
×
C
2
-
C
1
M
t
0
C
2
-
C
1
M
t
×
C
1
M
t
0
C
2
-
C
1
M
t
×
C
2
-
C
1
M
t
.It can be confirmed that {
Q
¯
l
e
x
p
}
l
=
0
L
-
1 is also a feasible solution to problem P
7
(
γ
,
C
2
) by substituting it.Proposition 5.
AssumeP
7
(
γ
,
C
1
) is feasible with a fixed set of channel vectors, SINR constraints, and noise powers with optimal value P
3. If C
2 is greater than C
1, the optimal value of problem P
7
(
γ
,
C
2
), defined as P
4, is less than or equal to P
3; that is, P
4
≤
P
3, and the equality holds up if and only if the solutions of these two problems are the same.The basic idea of the proof process is similar to that of Proposition3 and thus omitted here. We can replace {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 and {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1 by {
Q
¯
l
o
p
t
}
l
=
0
L
-
1 and {
Q
¯
l
e
x
p
}
l
=
0
L
-
1, and then the result can be reached.


## 4.1. Beamforming Design in Frequency Domain

In fact, the channel coefficient vectorH
l
,
m
,
i has certain correlation with H
l
,
m
,
i
′ when i and i
′ are close to each other. It follows that we can reduce the complexity of solving the SDP problem P
4 by reducing the number of optimization variables. More clearly, the frequency-domain channel vectors {
H
l
,
m
,
i
}
i
=
0
I
-
1 can now be divided into several groups. Assume each group has F vectors (here I should be divisible by F), and there are I
/
F groups for {
H
l
,
m
,
i
}
i
=
0
I
-
1. In this way, we only need to optimize {
Q
l
,
i
}
i
=
0
I
/
F
-
1 and the optimization problem can be converted to(17)
P
5
:
min
⁡
Q
l
,
i
i
=
0
I
/
F
-
1
F
I
∑
l
=
0
L
-
1
∑
i
=
0
I
/
F
-
1
t
r
Q
l
,
i
s.t.
S
I
N
R
l
,
m
r
1
≥
γ
l
,
m
Q
l
,
i
⪰
0
rank
⁡
Q
l
,
i
=
1
,
∀
i
,
∀
m
,
∀
l
,where (18)
S
I
N
R
l
,
m
r
1
=
1
/
I
∑
i
=
0
I
-
1
H
l
,
m
,
i
Q
l
,
i
/
F
+
1
H
l
,
m
,
i
†
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
H
l
,
m
,
i
Q
l
′
,
i
/
F
+
1
H
l
,
m
,
i
†
+
σ
l
,
m
2
,
∀
i
∈
{
0
,
…
,
I
/
F
-
1
}, ∀
m
∈
g
l, and ∀
l
∈
{
0
,
…
,
L
-
1
} in this subsection. Similarly, by dropping the L
I
/
F rank-one constraints, an SDP problem can then be obtained as(19)
P
6
:
min
⁡
Q
l
,
i
i
=
0
I
/
F
-
1
F
I
∑
l
=
0
L
-
1
∑
i
=
0
I
/
F
-
1
t
r
Q
l
,
i
s.t.
S
I
N
R
l
,
m
r
1
≥
γ
l
,
m
Q
l
,
i
⪰
0
,
∀
i
,
∀
m
,
∀
l
,and the corresponding MMPC problem follows that(20)
M
2
:
min
⁡
p
l
,
i
i
=
0
I
/
F
-
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
p
l
,
i
/
F
+
1
β
l
,
i
s.t.
1
/
I
∑
i
=
0
I
-
1
p
l
,
i
/
F
+
1
α
l
,
m
,
i
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
p
l
′
,
i
/
F
+
1
α
l
′
,
m
,
i
+
σ
l
,
m
2
≥
γ
l
,
m
p
l
,
i
≥
0
,
∀
i
,
∀
m
,
∀
l
,where p
l
,
i denotes the power factor for the beamformer W
l
,
i
q, and β
l
,
i
=
W
l
,
i
/
F
+
1
q
2
2. Accordingly, we have α
l
,
m
,
i
=
H
l
,
m
,
i
W
l
,
i
/
F
+
1
q
W
l
,
i
/
F
+
1
q
†
H
l
,
m
,
i
†, and α
l
′
,
m
,
i
=
H
l
,
m
,
i
W
l
′
,
i
/
F
+
1
q
W
l
′
,
i
/
F
+
1
q
†
H
l
,
m
,
i
†. Thanks to similar randomization process as Algorithm 1, the frequency-domain algorithm is summarized in Algorithm 2.Algorithm 2:Frequency-domain algorithm.
(1) Input: H
l
,
m
,
i, σ
l
,
m, γ
l
,
m, F, Q;
(2) solve SDP problem P
6 by IPM;
(3) if  rank
⁡
(
Q
l
,
i
)
=
1
,
∀
i
,
∀
l  then
(4)   W
l
,
i
=
U
l
,
i
Λ
l
,
i
1
/
2
(
:
,
1
);
(5)   b
r
e
a
k;
(6) else
(7)   calculate EVD: Q
l
,
i
=
U
l
,
i
Λ
l
,
i
U
l
,
i
†;
(8)   for  q
=
1 to Q  do
(9)    generate candidates W
l
,
i
q
=
U
l
,
i
Λ
l
,
i
1
/
2
V
l
,
i
q;
(10)  solve MMPC problem M
2 to obtain p
l
,
i
W
l
,
i
q;
(11) end
(12) choose
W
l
,
i
=
arg
⁡
min
{
p
l
,
i
W
l
,
i
q
}
⁡
∑
l
=
0
L
-
1
‍
∑
i
=
0
I
-
1
p
l
,
i
/
F
+
1
β
l
,
i;
(13) end
(14) Output: {
W
l
,
i
}.As a matter of convenience, denoteP
5
(
γ
,
F
) as the frequency-domain problem with parameters γ and F. Here γ
≜
[
γ
0,0
,
γ
0,1
,
…
,
γ
0
,
m
,
…
,
γ
l
,
m
]. Obviously, the proposed beamforming design in frequency-domain can be treated as a special case of the approximate solution presented in the previous section. In other words, if the parameter F is set to be 1, the frequency-domain QoS problem P
5
(
γ
,
1
) is equivalent to the QoS problem P
3
(
γ
).The following results shed more lights on the influence of the controlling parameterF.Proposition 2.
Assume problemP
5
(
γ
,
F
1
) is feasible with a fixed set of channel vectors, SINR constraints, and noise powers; the sufficient condition for problem P
5
(
γ
,
F
2
) to be also feasible is that F
1 can be divisible by F
2.Proof.
Assume{
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 denotes the optimal solution to problem P
5
(
γ
,
F
1
). For any F
2 which satisfies that F
1 is divisible by F
2, {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 can be expanded as {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1, where {
Q
l
,
i
e
x
p
}
i
=
i
′
F
1
/
F
2
(
i
′
+
1
)
F
1
/
F
2
-
1
=
Q
l
,
i
′. It can be verified that {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1 is a feasible solution to problem P
5
(
γ
,
F
2
) by substituting it.Proposition 3.
AssumeP
5
(
γ
,
F
1
) is feasible with a fixed set of channel vectors, SINR constraints, and noise powers with optimal value P
1. If F
1 is divisible by F
2, the optimal value of problem P
5
(
γ
,
F
2
), defined as P
2, is less than or equal to P
1; that is, P
2
≤
P
1, and the equality holds up if and only if the solutions of these two problems are the same.Proof.
Define the optimal solution to problemP
5
(
γ
,
F
1
) to be {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 with optimal value P
1. From the proof of Proposition 2, {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 can be expanded to {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1 which is a feasible solution to problem P
5
(
γ
,
F
2
) with optimal value P
1. Assume the optimal solution to problem P
5
(
γ
,
F
2
) is {
Q
l
,
i
o
p
t
}
i
=
0
I
/
F
2
-
1 with optimal value P
2. Due to the optimality, {
Q
l
,
i
o
p
t
}
i
=
0
I
/
F
2
-
1 is at least a good solution as {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1; thus we have P
2
≤
P
1. And if the {
Q
l
,
i
o
p
t
}
i
=
0
I
/
F
2
-
1 can be obtained by {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1, P
2
=
P
1 holds.


## 4.2. Beamforming Design in Time-Domain

Besides reducing the number of optimization variables in frequency-domain immediately, an alternative way can also benefit the complexity reduction by cutting down the number of the FIR filter taps from time-domain perspective. Assume the time-domain FIR filter hasC taps, where C is far less than I; the transmitted signal in (1) changes to (21)
s
n
=
∑
l
=
0
L
-
1
∑
c
=
0
C
-
1
w
l
,
c
x
l
,
n
-
c
.Define (22)
W
l
,
i
=
∑
c
=
0
C
-
1
w
l
,
c
e
-
2
π
i
c
/
I
,which can be converted into an equation in Kronecker form (23)
W
l
,
i
=
1
e
-
j
2
π
i
/
N
⋮
e
-
j
2
π
i
C
-
1
/
N
T
⊗
I
M
t
︸
K
i
·
w
l
,
0
w
l
,
1
⋮
w
l
,
C
-
1
︸
W
¯
l
,with K
i
∈
C
M
t
×
C
M
t and W
¯
l
∈
C
C
M
t
×
1. In the sequel, the total transmission power is reformulated accordingly as (24)
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
tr
⁡
Q
l
,
i
=
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
W
l
,
i
W
l
,
i
′
=
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
K
i
W
¯
l
W
¯
l
†
K
i
†
.By defining Q
¯
l
=
W
¯
l
W
¯
l
†, the QoS problem thus becomes(25)
P
7
:
min
⁡
Q
¯
l
l
=
0
L
-
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
K
i
Q
¯
l
K
i
†
s.t.
S
I
N
R
l
,
m
r
2
≥
γ
l
,
m
Q
¯
l
⪰
0
rank
⁡
Q
¯
l
=
1
,
∀
m
,
∀
l
,with (26)
S
I
N
R
l
,
m
r
2
=
1
/
I
∑
i
=
0
I
-
1
t
r
H
l
,
m
,
i
K
i
Q
¯
l
K
i
†
H
l
,
m
,
i
†
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
t
r
H
l
,
m
,
i
K
i
Q
¯
l
′
K
i
†
H
l
,
m
,
i
†
+
σ
l
,
m
2
,and ∀
m
∈
g
l, ∀
l
∈
{
0
,
…
,
L
-
1
} in this subsection. Similar to previous two algorithms, an SDP problem is obtained after dropping L rank-one constraints:(27)
P
8
:
min
⁡
Q
¯
l
l
=
0
L
-
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
K
i
Q
¯
l
K
i
†
s.t.
S
I
N
R
l
,
m
r
2
≥
γ
l
,
m
Q
¯
l
⪰
0
,
∀
m
,
∀
l
,and the corresponding MMPC problem can be represented as(28)
M
3
:
min
⁡
p
l
l
=
0
L
-
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
p
l
β
l
,
i
s.t.
1
/
I
∑
i
=
0
I
-
1
p
l
α
l
,
m
,
i
1
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
p
l
′
α
l
′
,
m
,
i
+
σ
l
,
m
2
≥
γ
l
,
m
p
l
≥
0
,
∀
m
,
∀
l
,where p
l is the power factor for the beamformer W
¯
l
q, and β
l
,
i
=
t
r
(
K
i
Q
¯
l
q
K
i
†
). Accordingly, we have α
l
,
m
,
i
=
H
l
,
m
,
i
K
i
Q
¯
l
q
K
i
†
H
l
,
m
,
i
†, and α
l
′
,
m
,
i
=
H
l
,
m
,
i
K
i
Q
¯
l
′
q
K
i
†
H
l
,
m
,
i
†. Again, we can summarize the detailed procedure of the time-domain algorithm in Algorithm 3.Algorithm 3:Time-domain algorithm.
(1) Input: H
l
,
m
,
i, σ
l
,
m, γ
l
,
m, C, Q;
(2) solve SDP problem P
8 by IPM;
(3) if  rank
⁡
(
Q
¯
l
)
=
1
,
∀
l  then
(4)  W
¯
l
=
U
¯
l
Λ
¯
l
1
/
2
(
:
,
1
);
(5)  break;
(6) else
(7)  calculate EVD: Q
¯
l
=
U
¯
l
Λ
¯
l
U
¯
l
†;
(8)  for  q
=
1 to Q  do
(9)    generate candidates W
¯
l
q
=
U
¯
l
Λ
¯
l
1
/
2
V
¯
l
q;
(10)  solve MMPC problem M
3 to obtain p
l
W
¯
l
q;
(11) end
(12) choose {
W
¯
l
}
=
arg
⁡
min
{
p
l
W
¯
l
q
}
⁡
∑
l
=
0
L
-
1
‍
∑
i
=
0
I
-
1
p
l
β
l
,
i;
(13) end
(14) Output: {
W
¯
l
}.From Algorithm3, it is clear that if the parameter C is set to be I, the time-domain QoS problem P
7
(
γ
,
C
) is equivalent to the QoS problem P
3
(
γ
). The following propositions state some further results according to this problem.Proposition 4.
If problemP
7
(
γ
,
C
1
) is feasible with a fixed set of channel vectors, SINR constraints, and noise powers, the sufficient condition for problem P
7
(
γ
,
C
2
) to be also feasible is that C
2 should be greater than C
1.Proof.
Assume{
Q
¯
l
o
p
t
}
l
=
0
L
-
1 denotes the optimal solution to problem P
7
(
γ
,
C
1
). For any C
2 which satisfies that C
2 is greater than C
1, the solution {
Q
¯
l
o
p
t
}
l
=
0
L
-
1 to problem P
7
(
γ
,
C
1
) can be expanded as {
Q
¯
l
e
x
p
}
l
=
0
L
-
1, where (29)
Q
¯
l
e
x
p
l
=
0
L
-
1
=
Q
¯
l
o
p
t
l
=
0
L
-
1
0
C
1
M
t
×
C
2
-
C
1
M
t
0
C
2
-
C
1
M
t
×
C
1
M
t
0
C
2
-
C
1
M
t
×
C
2
-
C
1
M
t
.It can be confirmed that {
Q
¯
l
e
x
p
}
l
=
0
L
-
1 is also a feasible solution to problem P
7
(
γ
,
C
2
) by substituting it.Proposition 5.
AssumeP
7
(
γ
,
C
1
) is feasible with a fixed set of channel vectors, SINR constraints, and noise powers with optimal value P
3. If C
2 is greater than C
1, the optimal value of problem P
7
(
γ
,
C
2
), defined as P
4, is less than or equal to P
3; that is, P
4
≤
P
3, and the equality holds up if and only if the solutions of these two problems are the same.The basic idea of the proof process is similar to that of Proposition3 and thus omitted here. We can replace {
Q
l
,
i
′
}
i
′
=
0
I
/
F
1
-
1 and {
Q
l
,
i
e
x
p
}
i
=
0
I
/
F
2
-
1 by {
Q
¯
l
o
p
t
}
l
=
0
L
-
1 and {
Q
¯
l
e
x
p
}
l
=
0
L
-
1, and then the result can be reached.


## 5. Max-Min Fair Problem

In addition to the QoS problem, another problem always considered in a multigroup multicast system is the MMF problem. The original problem of maximizing the minimum SINR of all users under the total transmission power constraint can be written as(30)
Q
1
:
max
⁡
Q
l
,
i
,
t
∈
R
t
s.t.
S
I
N
R
l
,
m
r
γ
l
,
m
≥
t
Q
l
,
i
⪰
0
rank
⁡
Q
l
,
i
=
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
tr
⁡
Q
l
,
i
≤
P
,
∀
m
,
∀
l
,
∀
i
.In fact, this problem contains a special case with multicast over frequency-flat fading channel (V
=
1), which has been proven to be NP-hard in [5]; therefore problem Q
1 is also NP-hard. By virtue of the idea for solving QoS problem, it can be relaxed by dropping the rank constraints(31)
Q
2
:
max
⁡
Q
l
,
i
,
t
∈
R
t
s.t.
S
I
N
R
l
,
m
r
γ
l
,
m
≥
t
Q
l
,
i
⪰
0
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
t
r
Q
l
,
i
≤
P
,
∀
m
,
∀
l
,
∀
i
.However, contrary to the QoS problem P
4, problem Q
2 cannot be transformed into an SDP problem due to the existence of K nonlinear inequality constraints. The causes of these nonlinear inequality constraints is that the SINR target t for all users is no longer a constant but a variable in the MMF problem.Fortunately, problemQ
2 can be relaxed and its K inequality constraints can be changed into linear constraints for a given t. Thus the bisection search method [5, 15] can be used to deal with this problem. Note that after getting some beamforming candidates, an MMPC problem is considered here(32)
M
4
:
max
⁡
p
l
,
i
,
t
∈
R
t
s.t.
1
/
I
∑
i
=
0
I
-
1
p
l
,
i
α
l
,
m
,
i
γ
l
,
m
/
I
∑
l
′
≠
l
∑
i
=
0
I
-
1
p
l
′
,
i
α
l
′
,
m
,
i
+
γ
l
,
m
σ
l
,
m
2
≥
t
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
p
l
,
i
β
l
,
i
=
P
t
≥
0
,
p
l
,
i
≥
0
,
∀
i
,
∀
m
,
∀
l
,where all variables have been defined in Section 3. Due to the variation property of t, problem M
4 cannot be solved as an equivalent LP. Therefore, we continue to rely on bisection search method to solve this problem.Alike the QoS problem, the reduced-complexity MMF problem can also be considered both in frequency domain and in time-domain, where the frequency-domain version can be formulated as(33)
Q
3
:
max
⁡
Q
l
,
i
i
=
0
I
/
F
-
1
,
t
∈
R
t
s.t.
S
I
N
R
l
,
m
r
1
γ
l
,
m
≥
t
Q
l
,
i
⪰
0
rank
⁡
Q
l
,
i
=
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
/
F
-
1
tr
⁡
Q
l
,
i
≤
P
,
∀
m
,
∀
l
,
∀
i
.Drop the rank constraints and we can obtain the relaxed problem as follows:(34)
Q
4
:
max
⁡
Q
l
,
i
i
=
0
I
/
F
-
1
,
t
∈
R
t
s.t.
S
I
N
R
l
,
m
r
1
γ
l
,
m
≥
t
Q
l
,
i
⪰
0
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
/
F
-
1
tr
⁡
Q
l
,
i
≤
P
,
∀
m
,
∀
l
,
∀
i
.Similarly, the time-domain version of the MMF problems looks like(35)
Q
5
:
max
⁡
Q
¯
l
l
=
0
L
-
1
,
t
∈
R
t
s.t.
S
I
N
R
l
,
m
r
2
γ
l
,
m
≥
t
Q
¯
l
⪰
0
rank
⁡
Q
¯
l
=
1
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
tr
⁡
K
i
Q
¯
l
K
i
†
≤
P
,
∀
m
,
∀
l
,
Q
6
:
max
⁡
Q
¯
l
l
=
0
L
-
1
,
t
∈
R
t
s.t.
S
I
N
R
l
,
m
r
2
γ
l
,
m
≥
t
Q
¯
l
⪰
0
1
I
∑
l
=
0
L
-
1
∑
i
=
0
I
-
1
tr
⁡
K
i
Q
¯
l
K
i
†
≤
P
,
∀
m
,
∀
l
,before and after rank relaxation, respectively. To solve problems Q
3 and Q
5, the same idea can be found when solving problem Q
1. To illustrate the procedure of the proposed algorithms, a general solving framework for QoS and MMF problems is shown in Figure 2.Figure 2
Block-diagram of the solving framework.DenoteQ
1
(
γ
,
P
), Q
3
(
γ
,
P
,
F
), and Q
5
(
γ
,
P
,
C
) as for problem Q
1, problem Q
3, and problem Q
5, respectively, with particular parameters γ, P, F, and C. It can be seen that if the parameter F is set to be 1, the frequency-domain MMF problem Q
3
(
γ
,
P
,
F
) is equivalent to the MMF problem Q
1
(
γ
,
P
). Also, the time-domain MMF problem Q
5
(
γ
,
P
,
C
) is equivalent to problem Q
1
(
γ
,
P
) too, if C
=
I.The following analytical results demonstrate the relationship between the MMF problems with different parameters.Proposition 6.
Assume{
Q
l
,
i
o
p
t
1
}
i
=
0
I
/
F
1
-
1 is the optimal solution to the frequency-domain MMF problem Q
3
(
γ
,
P
,
F
1
) with optimal value t
1 and {
Q
l
,
i
o
p
t
2
}
i
=
0
I
/
F
2
-
1 is the optimal solution to problem Q
3
(
γ
,
P
,
F
2
) with optimal value t
2. The sufficient condition for t
2
≥
t
1 is that F
1 is divisible by F
2, and the equality holds up if and only if the solutions of these two problems are the same.Proposition 7.
Assume{
Q
¯
l
o
p
t
1
}
l
=
0
L
-
1 is the optimal solution to the time-domain MMF problem Q
5
(
γ
,
P
,
C
1
) with optimal value t
3 and {
Q
¯
l
o
p
t
2
}
l
=
0
L
-
1 is the optimal solution to problem Q
5
(
γ
,
P
,
C
2
) with optimal value t
4. The sufficient condition for t
4
≥
t
3 is that C
2 is greater than C
1 and the equality holds up if and only if the solutions of these two problems are the same.Furthermore, from the problem formulation, it appears that the MMF problems are always feasible, while things could be different for the QoS problem. The relationship between QoS and MMF problems for narrowband multigroup multicast case is discussed in [5]. Results therein can be also extended to the broadband multigroup multicast case (i.e., V
>
1). For completeness, several valuable conclusions are drawn here.Proposition 8.
For a fixed set of channel vectors and noise powers, the QoS problemP
3 is parameterized by γ, where γ
=
[
γ
0,0
,
γ
0,1
,
…
,
γ
0
,
m
,
…
,
γ
l
,
m
]. Then it can be represented as P
3
(
γ
). Likewise, the MMF problem Q
1 is parameterized by γ and P, that is, Q
1
(
γ
,
P
). The QoS problem P
3 and the MMF problem Q
1 have the relationship as (36)
P
=
P
3
Q
1
γ
,
P
γ
,
(37)
t
=
Q
1
γ
,
P
3
t
γ
.Proof.
Define{
Q
l
,
i
o
p
t
} as the optimal solution to problem Q
1
(
γ
,
P
), and its corresponding optimal value is t
o
p
t. It is easy to verify that {
Q
l
,
i
o
p
t
} is a feasible solution to problem P
3
(
t
o
p
t
γ
) and the corresponding optimal value is P. Assume there is a feasible solution {
Q
l
,
i
f
e
a
} to problem P
3
(
t
o
p
t
γ
) and P
f
e
a is the associated optimal value which satisfies P
f
e
a
<
P, and we can distribute the power P
-
P
f
e
a to all {
Q
l
,
i
f
e
a
} evenly to obtain a larger optimal value t
f
e
a than t
o
p
t under the same power constraint. It contradicts the optimality of {
Q
l
,
i
o
p
t
} for problem Q
1
(
γ
,
P
) which means that the assumption of {
Q
l
,
i
f
e
a
} is wrong and (36) has been proved.In order to prove (37), a similar process could be applied. Define {
Q
l
,
i
′
o
p
t
} as the optimal solution and P
′
o
p
t as the associated optimal value to problem P
3
(
t
γ
) (if P
3
(
t
γ
) is feasible). Note that {
Q
l
,
i
′
o
p
t
} is a solution to problem Q
1
(
γ
,
P
′
o
p
t
) with optimal value t. Assume there is a feasible solution {
Q
l
,
i
′
f
e
a
} to problem Q
1
(
γ
,
P
′
o
p
t
) with optimal value t
′
f
e
a
>
t. Thus there exists a constant 0
<
μ
<
1 which can be multiplied by {
Q
l
,
i
′
f
e
a
}, and the new solution set {
μ
Q
l
,
i
′
f
e
a
} also satisfies the SINR constraints. Obviously, the solution set {
μ
Q
l
,
i
′
f
e
a
} has a lower transmission power μ
P
′
o
p
t
<
P
′
o
p
t which contradicts the optimality of {
Q
l
,
i
′
o
p
t
} for problem P
3
(
t
γ
); thus the assumption is invalid.Proposition 9.
The QoS and MMF problem pairs, that is, problemsP
4 and Q
2, problems P
5 and Q
3, problems P
6 and Q
4, problems P
7 and Q
5, and problems P
8 and Q
6 all have the same relationship between problems P
3 and Q
1. Also, corresponding QoS MMPC and MMF MMPC problem pairs have the same relationship too.


## 6. Complexity Analysis

First of all, the computational complexities of solving the QoS problems are discussed in this section. For the approximation algorithm derived in Section3, the SDP problem P
4 has L
I matrix variables with size M
t
×
M
t and K linear inequality constraints. Based on the results in [13], it takes O
(
L
0.5
I
0.5
M
t
0.5
l
o
g
(
1
/
ϵ
)
) iterations, and each iteration needs O
(
L
3
I
3
M
t
6
+
K
L
I
M
t
2
) arithmetic operations. ϵ is the accuracy of the solution here. When solving MMPC problem M
1 it takes O
(
L
0.5
I
0.5
l
o
g
(
1
/
ϵ
)
) iterations, and each iteration needs O
(
L
3
I
3
+
K
L
I
) arithmetic operations. Assuming the parameter ϵ is same for all algorithms for the sake of simplicity, the total computational complexity for solving the QOS problem P
2 is thus O
(
(
L
3.5
I
3.5
M
t
6.5
+
K
L
1.5
I
1.5
M
t
2.5
+
Q
L
3.5
I
3.5
+
Q
K
L
1.5
I
1.5
)
l
o
g
(
1
/
ϵ
)
).For the frequency-domain beamforming algorithm, the SDP problemP
6 has L
I
/
F matrix variables with size M
t
×
M
t and K linear inequality constraints. Therefore the interior point method will take O
(
L
0.5
I
0.5
F
-
0.5
M
t
0.5
l
o
g
(
1
/
ϵ
)
) iterations, and each iteration needs O
(
L
3
I
3
M
t
6
F
-
3
+
K
L
I
F
-
1
M
t
2
) arithmetic operations. After that, it takes O
(
L
0.5
I
0.5
F
-
0.5
l
o
g
(
1
/
ϵ
)
) iterations to solve the MMPC problem M
2, and each iteration requires O
(
L
3
I
3
F
-
3
+
K
L
I
F
-
1
) arithmetic operations. Thus the total computational complexity for solving the QOS problem P
5 can be calculated as O
(
(
L
3.5
I
3.5
M
t
6.5
F
-
3.5
+
K
L
1.5
I
1.5
M
t
2.5
F
-
1.5
+
Q
L
3.5
I
3.5
F
-
3.5
+
Q
K
L
1.5
I
1.5
F
-
1.5
)
l
o
g
(
1
/
ϵ
)
).For the time-domain beamforming algorithm, the SDP problemP
8 has L matrix variables with size C
M
t
×
C
M
t and K linear inequality constraints. According to above results, it takes O
(
L
0.5
C
0.5
M
t
0.5
l
o
g
(
1
/
ϵ
)
) iterations, and each iteration needs O
(
L
3
C
6
M
t
6
+
K
L
C
2
M
t
2
) arithmetic operations. When solving MMPC problem M
3 it takes O
(
L
0.5
l
o
g
(
1
/
ϵ
)
) iterations, and each iteration needs O
(
L
3
+
K
L
) arithmetic operations. Therefore the total computational complexity for solving the QOS problem P
7 is O
(
(
L
3.5
C
6.5
M
t
6.5
+
K
L
1.5
C
2.5
M
t
2.5
+
Q
L
3.5
+
Q
K
L
1.5
)
l
o
g
(
1
/
ϵ
)
).Next, we will analyze the computational complexities of solving the MMF problems which are analyzed. DefineB
S and B
L as the number of the bisection iterations for solving the relaxed MMF problems and corresponding MMPC problems separately. As mentioned in Section 5, the solving process of the MMF problem includes solving B
S times the SDP problem and Q
B
L times the LP problem. Thus the complexities of the proposed algorithms can be easily figured out based on the result of the QoS problems. For the approximation algorithm, the frequency-domain beamforming algorithm, and the time-domain beamforming algorithm, the overall computational complexities are O
(
(
B
S
L
3.5
I
3.5
M
t
6.5
F
-
3.5
+
B
S
K
L
1.5
I
1.5
M
t
2.5
F
-
1.5
+
Q
B
L
L
3.5
I
3.5
F
-
3.5
+
Q
B
L
K
L
1.5
I
1.5
F
-
1.5
)
l
o
g
(
1
/
ϵ
)
), O
(
(
B
S
L
3.5
I
3.5
M
t
6.5
F
-
3.5
+
B
S
K
L
1.5
I
1.5
M
t
2.5
F
-
1.5
+
Q
B
L
L
3.5
I
3.5
F
-
3.5
+
Q
B
L
K
L
1.5
I
1.5
F
-
1.5
)
l
o
g
(
1
/
ϵ
)
), and O
(
(
B
S
L
3.5
C
6.5
M
t
6.5
+
B
S
K
L
1.5
C
2.5
M
t
2.5
+
Q
B
L
L
3.5
+
Q
B
L
K
L
1.5
)
l
o
g
(
1
/
ϵ
)
), respectively.For both QoS problem and MMF problem, it is important to point out that the computational complexities of the corresponding frequency-domain algorithm and the time-domain algorithm are always much lower than that of the approximation one in practical wireless communication systems, because the parameterI is usually much larger than I
/
F and C. For example, when the parameters of the system are set as I
=
128, L
=
2, K
=
8, and Q
=
300 while the l
o
g
(
1
/
ϵ
) is assumed to be 1, the total arithmetic operations for QoS problems are plotted in Figure 3. It can be verified from the figure that with the decrease of F the computational complexity of solving the frequency-domain algorithm increases, and larger C leads to higher computational complexity for the time-domain algorithm. Meanwhile, the two proposed algorithms reduced the computational complexity efficiently.Figure 3
The total arithmetic operations for QoS problems.Since for MMF problems, the computational consumption for both the frequency-domain algorithm and the time-domain algorithm are linear with those of QoS problems, we ignore the illustrative comparison in this section.


## 7. Simulation Results

In this section, several numerical examples are illustrated to demonstrate the effectiveness of proposed beamforming algorithms. For simplicity, the frequency-selective fading channel between each receiver and the transmitter is built as a discrete channel model with 3 effective paths; that is,V
=
3, and each path is assumed to be independent and identically distributed (i.i.d.) Rayleigh fading channel. The SINR constraints for all users are the same. All experimental results are averaged over 1000 independent Monte Carlo runs, and the number of randomizations of the SDR-based method is set to be Q
=
300 for all algorithms used in our simulations. All SDP problems and LP problems are solved by CVX box [16]. To measure the performance, the approximation algorithm with I
=
128 is chosen to be a comparable goal.


### 7.1. Feasible Rate of SDP Problems

The first step of the proposed algorithms is solving the relaxed SDP problems. From the relaxation process we can see that the feasible set of the relaxed SDP problems is indeed a superset of one of the original QCQP problems, which leads to the following conclusions: If the relaxed problems are not feasible, the original ones are not feasible either. Rather, if the relaxed problems are feasible, the original ones may be not feasible. Therefore, the feasibility of the SDP problems is a necessary condition for the validity of proposed algorithms. In this subsection, the feasibility of the SDP problems is evaluated under conditions of different number of multigroupsL, transmit antennas M
t, and users K. All users are equally distributed into the groups, which means that each group has K
/
L users in the simulation.Figure4 shows the feasibility of SDP problems in different cases. Because the approximation algorithm works well in all situations, which has all 100 percent feasibility for all SINR constraints, we just use one red line marked “approximation” to present it. By comparing the line pairs, some conclusions can be obtained. For example, with all other things being equal, we can get that the frequency-domain SDP problem with less users is feasible with higher probability by comparing the “L
=
2
M
t
=
6
K
=
8
F
=
8” line and “L
=
2
M
t
=
6
K
=
12
F
=
8” line (for time-domain SDP problem we can use “L
=
2
M
t
=
6
K
=
8
C
=
4” line and “L
=
2
M
t
=
6
K
=
12
C
=
4” line). The reason lies in that the more the users are, the more the interuser interference exists in multigroup system. By comparing different line pairs, results can be concluded as follows:(i)
The frequency-domain (or time-domain) SDP problem with less users is feasible with higher probability (just mentioned above).
(ii)
The frequency-domain (or time-domain) SDP problem with less groups is feasible with higher probability. That is, because the more the groups are, the more the intergroup interference exists.
(iii)
The frequency-domain (or time-domain) SDP problem with more transmit antennas is feasible with higher probability, since the more the transmit antennas are, the more the spatial degrees of freedom can be exploited.
(iv)
The frequency-domain SDP problem with smallerF is feasible with higher probability. The reason has been proved in Proposition 2 and the simulation results verify it.
(v)
The time-domain SDP problem with largerC is feasible with higher probability. The reason has been proved in Proposition 4 and the simulation results verify it.Figure 4
The feasible probability of SDP problems.


### 7.2. Performance for QoS Problems

Next, the performances of the proposed algorithms solving QoS problems are compared. The system parameters are set asL
=
2, M
t
=
6, and K
=
8. Other cases with different system parameters are also evaluated, and almost same results are obtained; thus they are omitted here. Note that only instances with feasible solutions are counted and averaged. Figure 5 displays the transmission power performance under various SINR constraints of proposed algorithms, and the cumulative distribution function (CDF) under γ
l
,
m
=
6dB, ∀
m
∈
g
l, ∀
l
∈
{
0
,
…
,
L
-
1
}, is given in Figure 6. It can be seen from Figure 5 that the frequency-domain algorithm with smaller F value has better performance and the time-domain algorithm with larger C value achieves lower transmission power. Meanwhile, we can get that these results are not only on average but also in each of the trials from Figure 6. The validities of Propositions 3 and 5 are verified. When transmission power performance and computational complexity are considered together, the time-domain algorithm with C
=
6 seems to be the best choice based on Figures 3 and 5. Taking approximation algorithm as a standard, the complexity of solving the QoS problem has been reduced to 1/100 by the time-domain algorithm with C
=
6, while the SINR loss is approximately equal to 1 dB.Figure 5
The transmission power performance for QoS problems.Figure 6
The cumulative distribution function for QoS problems.


### 7.3. Performance for MMF Problems

Finally, the proposed algorithms are adopted to solve the MMF problems. We setL
=
2, M
t
=
6, and K
=
12 as the system parameters. The performances are investigated and shown in Figure 7. As discussed in Section 5, because the MMF problem is closely related with the QoS problem, the simulation results are very similar to the ones of the QoS problems.Figure 7
The performance for MMF problems.From Figure7, we can see that smaller F for the frequency-domain algorithm and larger C for the time-domain algorithm improve the SINR performance, respectively. Likewise, the proposed algorithms make a great tradeoff between the system performance and computational complexity. Same as previous subsection, the time-domain algorithm with C
=
6 is the best choice when taking both performance and complexity into consideration.


## 7.1. Feasible Rate of SDP Problems

The first step of the proposed algorithms is solving the relaxed SDP problems. From the relaxation process we can see that the feasible set of the relaxed SDP problems is indeed a superset of one of the original QCQP problems, which leads to the following conclusions: If the relaxed problems are not feasible, the original ones are not feasible either. Rather, if the relaxed problems are feasible, the original ones may be not feasible. Therefore, the feasibility of the SDP problems is a necessary condition for the validity of proposed algorithms. In this subsection, the feasibility of the SDP problems is evaluated under conditions of different number of multigroupsL, transmit antennas M
t, and users K. All users are equally distributed into the groups, which means that each group has K
/
L users in the simulation.Figure4 shows the feasibility of SDP problems in different cases. Because the approximation algorithm works well in all situations, which has all 100 percent feasibility for all SINR constraints, we just use one red line marked “approximation” to present it. By comparing the line pairs, some conclusions can be obtained. For example, with all other things being equal, we can get that the frequency-domain SDP problem with less users is feasible with higher probability by comparing the “L
=
2
M
t
=
6
K
=
8
F
=
8” line and “L
=
2
M
t
=
6
K
=
12
F
=
8” line (for time-domain SDP problem we can use “L
=
2
M
t
=
6
K
=
8
C
=
4” line and “L
=
2
M
t
=
6
K
=
12
C
=
4” line). The reason lies in that the more the users are, the more the interuser interference exists in multigroup system. By comparing different line pairs, results can be concluded as follows:(i)
The frequency-domain (or time-domain) SDP problem with less users is feasible with higher probability (just mentioned above).
(ii)
The frequency-domain (or time-domain) SDP problem with less groups is feasible with higher probability. That is, because the more the groups are, the more the intergroup interference exists.
(iii)
The frequency-domain (or time-domain) SDP problem with more transmit antennas is feasible with higher probability, since the more the transmit antennas are, the more the spatial degrees of freedom can be exploited.
(iv)
The frequency-domain SDP problem with smallerF is feasible with higher probability. The reason has been proved in Proposition 2 and the simulation results verify it.
(v)
The time-domain SDP problem with largerC is feasible with higher probability. The reason has been proved in Proposition 4 and the simulation results verify it.Figure 4
The feasible probability of SDP problems.


## 7.2. Performance for QoS Problems

Next, the performances of the proposed algorithms solving QoS problems are compared. The system parameters are set asL
=
2, M
t
=
6, and K
=
8. Other cases with different system parameters are also evaluated, and almost same results are obtained; thus they are omitted here. Note that only instances with feasible solutions are counted and averaged. Figure 5 displays the transmission power performance under various SINR constraints of proposed algorithms, and the cumulative distribution function (CDF) under γ
l
,
m
=
6dB, ∀
m
∈
g
l, ∀
l
∈
{
0
,
…
,
L
-
1
}, is given in Figure 6. It can be seen from Figure 5 that the frequency-domain algorithm with smaller F value has better performance and the time-domain algorithm with larger C value achieves lower transmission power. Meanwhile, we can get that these results are not only on average but also in each of the trials from Figure 6. The validities of Propositions 3 and 5 are verified. When transmission power performance and computational complexity are considered together, the time-domain algorithm with C
=
6 seems to be the best choice based on Figures 3 and 5. Taking approximation algorithm as a standard, the complexity of solving the QoS problem has been reduced to 1/100 by the time-domain algorithm with C
=
6, while the SINR loss is approximately equal to 1 dB.Figure 5
The transmission power performance for QoS problems.Figure 6
The cumulative distribution function for QoS problems.


## 7.3. Performance for MMF Problems

Finally, the proposed algorithms are adopted to solve the MMF problems. We setL
=
2, M
t
=
6, and K
=
12 as the system parameters. The performances are investigated and shown in Figure 7. As discussed in Section 5, because the MMF problem is closely related with the QoS problem, the simulation results are very similar to the ones of the QoS problems.Figure 7
The performance for MMF problems.From Figure7, we can see that smaller F for the frequency-domain algorithm and larger C for the time-domain algorithm improve the SINR performance, respectively. Likewise, the proposed algorithms make a great tradeoff between the system performance and computational complexity. Same as previous subsection, the time-domain algorithm with C
=
6 is the best choice when taking both performance and complexity into consideration.


## 8. Conclusion

In this paper, the downlink beamforming designs for the broadband multigroup multicast QoS and MMF problems are investigated. By means of the traditional SDR and Gaussian randomization methods, two algorithms designed in frequency and time-domains are proposed to solve the QoS problem. Then we extend these algorithms to handle the MMF problem through an iterative bisection search process. Several Monte Carlo simulations indicate the proposed beamforming designs reduce the computational complexity considerably with slight performance loss: the complexity of solving the QoS problem could be reduced to 1/100 by the time-domain algorithm withC
=
6, while the SINR loss is approximately equal to 1 dB, and similar conclusion can be given for the MMF problem.



---

*Source: 563863-2015-06-07.xml*