# A Decentralized Method for Joint Admission Control and Beamforming in
Coordinated Multicell Downlink

Hoi-To Wai, Wing-Kin Ma
This work was supported by a Direct Grant by the Chinese University of Hong
Kong (Project ID 2050506). Department of Electronic Engineering,
The Chinese University of Hong Kong, Shatin, N.T., Hong Kong
Email: htwai<EMAIL_ADDRESS>
###### Abstract

In cellular networks, admission control and beamforming optimization are
intertwined problems. While beamforming optimization aims at satisfying users’
quality-of-service (QoS) requirements or improving the QoS levels, admission
control looks at how a subset of users should be selected so that the
beamforming optimization problem can yield a reasonable solution in terms of
the QoS levels provided. However, in order to simplify the design, the two
problems are usually seen as separate problems. This paper considers joint
admission control and beamforming (JACoB) under a coordinated multicell MISO
downlink scenario. We formulate JACoB as a user number maximization problem,
where selected users are guaranteed to receive the QoS levels they requested.
The formulated problem is combinatorial and hard, and we derive a convex
approximation to the problem. A merit of our convex approximation formulation
is that it can be easily decomposed for per-base-station decentralized
optimization, namely, via block coordinate decent. The efficacy of the
proposed decentralized method is demonstrated by simulation results.

###### Index Terms:

admission control, distributed optimization, downlink beamforming

##  I Introduction

Coordinated beamforming (CoBF) [1, 2] is a recently studied technique to
mitigate intercell interference (ICI) in the downlink of multicell cooperative
systems. In CoBF, the neighboring BSs share the same frequency band and employ
beamforming for data transmission. The transmit beamformers at different BSs
are coordinately designed according to the channel conditions and certain
design formulation, e.g., maximum system throughput, minimum transmit power,
to name a few. Compared to fully multicell cooperative techniques such as
network MIMO [1], CoBF has an advantage that the BS cooperation overheads are
not as significant, and yet appealing performance may be achieved.

Meanwhile, admission control also plays an important role in cellular systems.
As cellular systems are usually congested, with lots of users awaiting
service, it is necessary for the BSs to decide which user is served or not.
Admission control refers to methods of selecting users. While admission
control and beamforming are commonly seen as two separate problems, they are
fundamentally dependent on each other. Recent work has demonstrated that by
considering admission control and beamforming jointly, promising system
performance can be achieved [3, 4]. However, joint admission control and
beamforming (JACoB) is a challenging problem. It has been shown that JACoB is
NP-hard even under a single-cell scenario [3]. Hence, as a compromise, one may
consider approximation approaches.

This paper describes a JACoB approach to CoBF in multicell MISO downlink. A
distinguishing part of the present work is that our proposed JACoB formulation
can be easily decomposed for decentralized implementation, and the
decentralized process is considered even more straightforward than those in
CoBF (without admission control), e.g. [2, 5]. A key idea of our approach is
to use the now popularized $\ell_{1}$ approximation method. We very recently
note that in a concurrent work [4], the authors have studied $\ell_{1}$
approximation for joint admission control and power control (i.e., no
beamforming). Nevertheless, the work [4] does not investigate the multicell
CoBF scenario and, more importantly, decentralized optimization considered
here. It is also worthwhile to mention [3], which considers JACoB under a
single cell scenario. The formulation used there is based on a mixed-integer
program formulation, and is processed by semidefinite relaxation (SDR). While
it is not difficult to see that the idea of [3] can be extended to the
multicell scenario, one needs to assume centralized optimization and presently
there is no reported work on how the method in [3] can be decentralized. In
our simulations, we will show that our decentralized method yields a
performance quite on a par with the centralized method in [3].

##  II System model

Consider a cellular system with $M$ coordinating BSs. Each BS is equipped with
$N$ transmit antennas. In each cell, there are $K$ single-antenna user
terminals; thus the total number of users in the system is $KM$. The set of
users associated with the $i$th cell, or the $i$th BS, is denoted by
$\mathcal{K}_{i}\subset\mathcal{K}=\\{1,2,...,KM\\}$. We assume that
$\mathcal{K}=\mathcal{K}_{1}\cup\cdots\cup\mathcal{K}_{M}$ and
$\mathcal{K}_{i}\cap\mathcal{K}_{j}=\emptyset$ whenever $i\neq j$, i.e., each
user is served only by one BS. The scenario of interest is downlink, with an
emphasis on CoBF. Assuming that the BS-to-user channels are frequency-flat and
slow, and that the linear unicast transmit beamforming scheme is employed, we
can characterize the CoBF system performance by the received signal-to-
interference-and-noise ratios (SINRs) (for more complete system model
descriptions, see the literature, such as [2]):

${\sf
SINR}_{q}=\displaystyle\frac{|{\bm{h}}_{i(q),q}^{H}{\bm{w}}_{q}|^{2}}{\displaystyle\sigma_{q}^{2}+\sum_{m\in\mathcal{K}_{i(q)}\setminus\\{q\\}}|{\bm{h}}_{i(q),q}^{H}{\bm{w}}_{m}|^{2}+\sum_{j\neq
i(q)}\sum_{m\in\mathcal{K}_{j}}|{\bm{h}}_{j,q}^{H}{\bm{w}}_{m}|^{2}},$ (1)

where $q\in\\{1,2,\ldots,KM\\}$ is the user index, $i(q)\in\\{1,...,M\\}$
denotes the BS with which the $q$th user is associated (i.e., $i(q)$ is such
that $q\in\mathcal{K}_{i(q)}$), ${\bm{h}}_{j,q}\in\mathbb{C}^{N}$ is the
channel response from the $j$th BS to the $q$th user, $\sigma_{q}^{2}$ is the
noise variance, and ${\bm{w}}_{q}\in\mathbb{C}^{N}$ is the beamforming vector
for the $q$th user.

The difference between the SINR model in (1) and a single-cell-based SINR
model is that the former explicitly models the ICI, which is given by the
third term in the denominator of (1). On the contrary, in the single-cell
case, the ICI is usually treated as a constant, and is absorbed by
$\sigma_{q}^{2}$. The idea of CoBF is therefore to ask the BSs to coordinately
design $\\{{\bm{w}}_{q}\\}_{q=1}^{KM}$, so that ICI may be jointly mitigated.

To motivate the study of JACoB, let us quickly review a CoBF design problem,
specifically, the design proposed in [2]. In that design, the BSs jointly
design the beamforming vectors $\\{{\bm{w}}_{q}\\}_{q=1}^{KM}$ such that the
SINR of each user is no less than a user-requested threshold $\gamma_{q}$.
Moreover, the design objective aims at minimizing the total transmit power.
This amounts to the following design optimization problem:

$\begin{array}[]{rl}\displaystyle\min_{\\{{\bm{w}}_{q}\\}_{q=1}^{KM}}&\sum_{q=1}^{KM}\|{\bm{w}}_{q}\|_{2}^{2}\\\
{\rm s.t.}&{\sf SINR}_{q}\geq\gamma_{q},~{}q=1,2,...,KM,\\\
&\sum_{q\in\mathcal{K}_{i}}\|{\bm{w}}_{q}\|_{2}^{2}\leq
P_{max,i},~{}i=1,...,M,\end{array}$ (2)

where the last constraints in (2) are per-BS power budget constraints, with
$P_{max,i}$ specifying the maximum transmit power of the $i$th BS111As a minor
point to note, the previous study [2] does not incorporate the per-BS power
budget constraints., and $\|\cdot\|_{2}$ is the $\ell_{2}$ norm. At first
glance problem (2) seems to be nonconvex, since the SINR constraints are
nonconvex in $\\{{\bm{w}}_{q}\\}_{q=1}^{KM}$. Actually, problem (2) can be
solved in a convex and tractable fashion, using either the second-order cone
programming formulation or the semidefinite relaxation (SDR) formulation; see
[2] and [6] for more detail.

Cellular systems are usually congested, with lots of users awaiting service. A
subsequent issue relevant to the CoBF problem (2) is that we may be unable to
find a beamforming solution $\\{{\bm{w}}_{q}\\}_{q=1}^{KM}$ that satisfies all
the users’ SINR requests. In other words, problem (2) may be infeasible. To
illustrate this issue, we simulated the feasibility rate of problem (2)
against the total number of users $KM$. The simulation result is plotted in
Figure 1. The feasibility rate was evaluated by counting the number of
instances for which (2) is feasible, under randomly generated channels. We
observe that problem (2) has a low feasibility rate when the number of users
is large.

Figure 1: The feasibility rate of the CoBF problem (2). $M=3$, $N=8$,
$\gamma_{q}=6$ dB, and $P_{max,i}$ = 46 dBm.

##  III Joint admission control and beamforming

This work considers joint admission control and beamforming (JACoB). The
problem is stated as follows:

Joint admission control and beamforming (JACoB): _Select a maximum number of
users, such that there exists a beamforming solution $\\{{\bm{w}}_{q}\\}$ that
satisfies all the selected users’ SINR requests._

In the following, we will first provide an optimization formulation for JACoB,
and derive a convex approximation to the formulated problem. Then, a
decentralized method based on the convex approximation will be developed.

###  III-A Centralized method for JACoB

Our endeavor starts with formulating JACoB in a mathematically convenient
form. First of all, let

${\bm{W}}_{q}={\bm{w}}_{q}{\bm{w}}_{q}^{H},\quad q=1,\ldots,KM,$

and observe the following equivalence (cf. (1)):

${\sf SINR}_{q}\geq\gamma_{q}\Longleftrightarrow 0\geq
f_{q}(\\{{\bm{W}}_{m}\\}_{m=1}^{KM}),$ (3)

where we define

$\begin{array}[]{l}\displaystyle
f_{q}(\\{{\bm{W}}_{m}\\}_{m=1}^{KM})\triangleq 1+\sum_{j\neq i(q)}{\rm
Tr}\Big{(}{\bm{H}}_{j,q}\Big{(}\sum_{m\in\mathcal{K}_{j}}{\bm{W}}_{m}\Big{)}\Big{)}\\\
\displaystyle\hfill+{\rm
Tr}\Big{(}{\bm{H}}_{i(q),q}\Big{(}\sum_{m\in\mathcal{K}_{i(q)}\setminus\\{q\\}}{\bm{W}}_{m}-\frac{1}{\gamma_{q}}{\bm{W}}_{q}\Big{)}\Big{)},\end{array}$

and ${\bm{H}}_{j,q}\triangleq{\bm{h}}_{j,q}{\bm{h}}_{j,q}^{H}/\sigma_{q}^{2}$.
We claim that JACoB can be formulated as the following $\ell_{0}$ minimization
problem:

$\displaystyle\displaystyle\min_{{\bm{t}},\\{{\bm{W}}_{q}\\}_{q=1}^{KM}}$
$\displaystyle~{}~{}\|{\bm{t}}\|_{0}+\textstyle\epsilon\sum_{q=1}^{KM}{\rm
Tr}({\bm{W}}_{q})$ (4a) $\displaystyle{\rm s.t.}$
$\displaystyle~{}~{}\textstyle\sum_{q\in\mathcal{K}_{i}}{\rm
Tr}({\bm{W}}_{q})\leq P_{max,i},~{}i=1,...,M,$ (4b)
$\displaystyle~{}~{}{\bm{W}}_{q}\succeq{\bm{0}},~{}\forall~{}q,$ (4c)
$\displaystyle~{}~{}t_{q}=\max\\{0,f_{q}(\\{{\bm{W}}_{m}\\}_{m=1}^{KM})\\},~{}\forall~{}q,$
(4d) $\displaystyle~{}~{}{\rm rank}({\bm{W}}_{q})=1,~{}\hfill~{}\forall~{}q,$
(4e)

where $0<\epsilon<1/\sum_{i=1}^{M}P_{max,i}$ is a penalty parameter,
$\bm{W}_{q}\succeq\bm{0}$ means that $\bm{W}_{q}$ is positive semidefinite,
and $\|\bm{t}\|_{0}$ is the $\ell_{0}$ norm, which counts the number of
nonzero elements in $\bm{t}$.

Let us describe why problem (4) delivers the above defined JACoB goal.
Firstly, constraints (4c) and (4e) are equivalent to
${\bm{W}}_{q}={\bm{w}}_{q}{\bm{w}}_{q}^{H}$. Secondly, by substituting (4d)
into the first term of (4a), i.e., $\|{\bm{t}}\|_{0}$, and observing (3), we
can see that $\|{\bm{t}}\|_{0}$ is counting the number of unserved or
unadmitted users. Hence, if we ignore the second term of (4a), then problem
(4) minimizes the number of unadmitted users. Thirdly, the second term of
(4a), i.e, $\epsilon\sum_{q=1}^{KM}{\rm Tr}({\bm{W}}_{q})$, is a penalty term.
It is used to encourage more power-efficient beamforming solutions. It can be
shown that problem (4) with $\epsilon=0$ (i.e., direct unadmitted user
minimization) achieves the same number of unadmitted users as problem (4) with
$\epsilon<1/\sum_{i=1}^{M}P_{max,i}$.

Problem (4) is difficult to solve. As a remedy, we adopt a convex
approximation approach. Our approximation involves two steps. First, we
replace the hard $\ell_{0}$ norm function by the $\ell_{1}$ norm, which is now
a popularized trick in compressive sensing. Second, we remove the rank-one
constraints (4e), which is well known as SDR [6]. The above two approximations
lead us to the following $\ell_{1}$ approximate JACoB problem:

$\displaystyle\displaystyle\min_{{\bm{t}},\\{{\bm{W}}_{q}\\}_{q=1}^{KM}}$
$\displaystyle~{}~{}\textstyle\|{\bm{t}}\|_{1}+\epsilon\sum_{q=1}^{KM}{\rm
Tr}({\bm{W}}_{q})$ (5a) $\displaystyle{\rm s.t.}$
$\displaystyle~{}~{}\textstyle\sum_{q\in\mathcal{K}_{i}}{\rm
Tr}({\bm{W}}_{q})\leq P_{max,i},~{}i=1,...,M,$ (5b)
$\displaystyle\textstyle~{}~{}t_{q}\geq 0,~{}t_{q}\geq
f_{q}(\\{{\bm{W}}_{m}\\}_{m=1}^{KM}),$ (5c)
$\displaystyle~{}~{}{\bm{W}}_{q}\succeq{\bm{0}},~{}\forall~{}q,$ (5d)

where $\|\cdot\|_{1}$ is the $\ell_{1}$ norm. Note that in (5), we replace
(4d) by (5c), which can be easily verified to be equivalent.

The $\ell_{1}$ approximate JACoB problem (5) is convex. In fact, problem (5)
can be written as an SDP. Hence, for centralized implementation, we can solve
problem (5) by using a readily available SDP solver. Moreover, we show that
the second approximation, i.e., SDR, is a tight relaxation:

###### Proposition 1

For $\epsilon>0$, any optimal solution $\\{{\bm{W}}_{q}^{\star}\\}_{q=1}^{KM}$
of problem (5) must satisfy ${\rm rank}({\bm{W}}_{q}^{\star})\leq 1$ for all
$q$.

The proof of Proposition 1 is skipped here owing to the limit of space. The
idea behind the proof is to examine the KKT conditions and exploit the rank-
one structure of ${\bm{H}}_{i(q),q}$. We should also note that Proposition 1
is different from the SDR tightness results in [7], which may be seemingly
similar at first look. Simply speaking, [7] studies more general
${\bm{H}}_{j,q}$ (which may take any rank), but may not solve the problem in
Proposition 1. Proposition 1 means that solving problem (5) automatically
leads to a set of beamforming solutions (recall
$\bm{W}_{q}={\bm{w}}_{q}{\bm{w}}_{q}^{H}$ for rank-one positive semidefinite
$\bm{W}_{q}$), and there is no loss in applying SDR.

###  III-B Decentralized method for JACoB

A significant advantage of the $\ell_{1}$ approximate JACoB formulation in (5)
is that it can be easily decomposed for decentralized optimization. To see
this, let

$\bm{\mathcal{W}}_{i}\triangleq\\{{\bm{W}}_{m}\\}_{m\in\mathcal{K}_{i}},~{}i=1,...,M.$

Notice that $\bm{\mathcal{W}}_{i}$ corresponds to the beamforming vectors
controlled by the $i$th BS. Now, by substituting (5c) into (5a), we can
reformulate (5) as

$\begin{array}[]{rl}\displaystyle\min_{\\{{\bm{W}}_{q}\\}_{q=1}^{KM}}&\displaystyle\sum_{q=1}^{KM}\Big{(}\max\\{0,f_{q}(\bm{\mathcal{W}}_{1},...,\bm{\mathcal{W}}_{M})\\}+\epsilon{\rm
Tr}({\bm{W}}_{q})\Big{)}\vspace{-.0cm}\\\ {\rm
s.t.}&\sum_{q\in\mathcal{K}_{i}}{\rm Tr}({\bm{W}}_{q})\leq
P_{max,i},~{}i=1,...,M,\\\
&{\bm{W}}_{q}\succeq{\bm{0}},~{}q=1,...,KM.\end{array}$ (6)

A unique feature with problem (6) is that the constraints are per-BS decoupled
(note that this is not the case with the CoBF problem in (2)). As a result, we
can directly apply per-BS alternating optimization. To be specific, we employ
block coordinate descent (BCD). In BCD, we update only one beamforming block
$\bm{\mathcal{W}}_{i}$, while holding the other blocks fixed. This BCD update
is done cyclically with respect to the BSs, until some stopping rule is
satisfied.

A curious question is whether the above-described BCD method would converge to
the optimum of problem (6). Unfortunately, this may not be guaranteed—BCD may
not converge to the optimum for problems whose objective functions are not
continuously differentiable, even if the problem is convex [8]. The function
$\max\\{0,x\\}$ seen in problem (6) exactly falls into this case. To remedy
this, we apply a smooth approximation to (6) using the one-sided Huber
function

$h(x)=\begin{cases}0&,~{}{\sf if}~{}x\leq 0,\\\ \displaystyle
0.5x^{2}&,~{}{\sf if}~{}0<x\leq 1,\\\ \displaystyle x-0.5&,~{}{\sf
if}~{}x>1.\end{cases}$

The Huber function $h(x)$ is continuously differentiable in $x$. Applying the
approximation $\max\\{0,x\\}\approx h(x)$, we obtain the Huber approximate
JACoB problem:

$\begin{array}[]{rl}\displaystyle\min_{\\{{\bm{W}}_{q}\\}_{q=1}^{KM}}&\displaystyle\sum_{q=1}^{KM}\Big{(}h(f_{q}(\bm{\mathcal{W}}_{1},...,\bm{\mathcal{W}}_{M}))+\epsilon{\rm
Tr}({\bm{W}}_{q})\Big{)}\\\ {\rm s.t.}&\sum_{q\in\mathcal{K}_{i}}{\rm
Tr}({\bm{W}}_{q})\leq P_{max,i},~{}i=1,...,M,\\\
&{\bm{W}}_{q}\succeq{\bm{0}},~{}q=1,...,KM.\end{array}$ (7)

From this point on, we will concentrate on the BCD of problem (7).

Let us consider the BCD update of problem (7) with respect to the $i$th block
$\bm{\mathcal{W}}_{i}$, holding the other blocks
$\\{\hat{\bm{\mathcal{W}}}_{j}\\}_{j\neq
i}\triangleq\\{\hat{\bm{W}}_{m}\\}_{m\notin\mathcal{K}_{i}}$ fixed. The
respective problem is

$\begin{array}[]{rl}\displaystyle\min_{\\{{\bm{W}}_{m}\\}_{m\in\mathcal{K}_{i}}}&\displaystyle\sum_{q=1}^{KM}h(f_{q}(\bm{\mathcal{W}}_{i},\\{\hat{\bm{\mathcal{W}}_{j}}\\}_{j\neq
i}))+\sum_{m\in\mathcal{K}_{i}}\epsilon{\rm Tr}({\bm{W}}_{m})\vspace{.2cm}\\\
{\rm s.t.}&\sum_{m\in\mathcal{K}_{i}}{\rm Tr}({\bm{W}}_{m})\leq
P_{max,i},~{}{\bm{W}}_{m}\succeq{\bm{0}},~{}m\in\mathcal{K}_{i},\\\
\end{array}$

which can be expressed as a convex problem (see, e.g., [9]):

$\displaystyle\displaystyle\min$
$\displaystyle~{}~{}\displaystyle\sum_{q=1}^{KM}\left(\frac{1}{2}u_{q}^{2}+v_{q}\right)+\sum_{m\in\mathcal{K}_{i}}\epsilon{\rm
Tr}({\bm{W}}_{m})\vspace{.2cm}$ (8a) $\displaystyle{\rm s.t.}$
$\displaystyle~{}~{}u_{q}+v_{q}\geq
f_{q}(\bm{\mathcal{W}}_{i},\\{\hat{\bm{\mathcal{W}}}_{j}\\}_{j\neq
i}),~{}\forall~{}q,$ (8b) $\displaystyle~{}~{}u_{q},~{}v_{q}\geq
0,~{}\forall~{}q,$ (8c) $\displaystyle\sum_{m\in\mathcal{K}_{i}}{\rm
Tr}({\bm{W}}_{m})\leq
P_{max,i},~{}{\bm{W}}_{m}\succeq{\bm{0}},~{}m\in\mathcal{K}_{i}.$ (8d)

Constraints (8b) seems to indicate that full knowledge of
$\\{\hat{\bm{\mathcal{W}}}_{j}\\}_{j\neq i}$ is required, in order to solve
the BCD update (8). Actually, this may be not necessary. Notice that for
$q\in\mathcal{K}_{i}$, constraint (8b) can be expressed as:

$u_{q}+v_{q}\geq 1+\sum_{j\neq i}\hat{\Omega}_{j,q}+{\rm
Tr}\Big{(}{\bm{H}}_{i,q}\Big{(}\sum_{m\in\mathcal{K}_{i}\setminus\\{q\\}}{\bm{W}}_{m}-\frac{{\bm{W}}_{q}}{\gamma_{q}}\Big{)}\Big{)},$

and for $q\notin\mathcal{K}_{i}$,

$u_{q}+v_{q}\geq 1+\sum_{j\neq i}\hat{\Omega}_{j,q}+{\rm
Tr}\Big{(}{\bm{H}}_{i,q}\Big{(}\sum_{m\in\mathcal{K}_{i}}{\bm{W}}_{m}\Big{)}\Big{)},$

where $\hat{\Omega}_{j,q}$ are scalar constants defined as:

$\hat{\Omega}_{j,q}=\begin{cases}\displaystyle{\rm
Tr}\Big{(}{\bm{H}}_{j,q}\Big{(}\sum_{m\in\mathcal{K}_{j}\setminus\\{q\\}}\hat{\bm{W}}_{m}-\frac{\hat{\bm{W}}_{q}}{\gamma_{q}}\Big{)}\Big{)}&,~{}q\in\mathcal{K}_{j},\\\
\displaystyle{\rm
Tr}\Big{(}{\bm{H}}_{j,q}\Big{(}\sum_{m\in\mathcal{K}_{j}}\hat{\bm{W}}_{m}\Big{)}\Big{)}&,~{}q\notin\mathcal{K}_{j}.\end{cases}$

Hence, if the $i$th BS knows i) the matrices
$\\{{\bm{H}}_{i,q}\\}_{q=1}^{KM}$, i.e., the channel response from the $i$th
BS to the users in the system; and ii) the scalar constants
$\\{\hat{\Omega}_{j,q}\\}_{j\neq i,q\in\mathcal{K}}$, then problem (8) can be
solved independently at the $i$th BS. In fact, the first premise can be
satisfied automatically as it can be assumed that each BS knows the channel
response from itself to the users in the system [2]. To satisfy the second
premise, we can utilize the backhaul link between the BSs. Specifically, the
scalars $\\{\hat{\Omega}_{i,q}\\}_{q\in\mathcal{K}}$ can be computed and
broadcast to the other BSs after the $i$th BCD update is solved. There are
$KM$ real numbers to be broadcast at each iteration. This justifies our claim
that the $i$th BS can solve (8) alone. The BCD method for (7) is summarized in
Algorithm 1.

Recall that the reason for employing the Huber function in (7) is to provide a
smooth approximation to JACoB, avoiding the original nondifferentiable
objective function which may result in BCD non-convergence problems. But can
the smooth approximation guarantee convergence to the optimum? By invoking an
available BCD convergence analysis result [10], we have the following claim:

###### Fact 1

[10] The sequence $\\{\\{{\bm{W}}_{q}^{(k)}\\}_{q=1}^{KM}\\}_{k}$ generated by
Algorithm 1 has limit points and every limit point of the sequence
$\\{\\{{\bm{W}}_{q}^{(k)}\\}_{q=1}^{KM}\\}_{k}$ is an optimal solution to (7).

Readers are referred to Proposition 6 in [10] for more detail. We should note
that the important premises for us to use this available result are that the
objective function of (7) is convex, continuously differentiable in
$\\{\bm{\mathcal{W}}_{i}\\}_{i=1}^{M}$ and the constraint set for each
$\bm{\mathcal{W}}_{i}$ is convex and compact. Furthermore, by extending
Proposition 1, we can prove that the intermediate solutions
$\\{{\bm{W}}_{q}^{(k)}\\}_{q\in\mathcal{K}_{i}}$ in Algorithm 1 at the $i$th
BCD update are always of rank-one:

###### Proposition 2

For $\epsilon>0$ and for each $i$, any optimal solution
$\\{{\bm{W}}_{q}^{(k)}\\}_{q\in\mathcal{K}_{i}}$ of the $i$th BCD update in
Algorithm 1 must satisfy ${\rm rank}({\bm{W}}_{q}^{(k)})\leq 1$ for all $q$ in
$\mathcal{K}_{i}$.

Algorithm 1 Block coordinate descent method for (7)

0: initialization - $\\{{\bm{W}}_{q}^{(0)}\\}_{q\in\mathcal{K}}$.

1: $k=1$;

2: For each $i=1,2,...,M$, the $i$th BS computes
$\\{\hat{\Omega}_{i,q}\\}_{q\in\mathcal{K}}$ and broadcasts them to the other
BSs;

3: repeat

4: for $i=1$ to $M$ do

5: The $i$th BS solves (8) given $\\{\hat{\Omega}_{j,q}\\}_{j\neq
i,q\in\mathcal{K}}$ to obtain
$\\{{\bm{W}}_{q}^{(k)}\\}_{q\in\mathcal{K}_{i}}$. The scalars
$\\{\hat{\Omega}_{i,q}\\}_{q\in\mathcal{K}}$ are computed and broadcast to the
other BSs;

6: end for

7: $k=k+1$;

8: until convergence.

9: return an optimal solution to (7) -
$\\{{\bm{W}}_{q}^{(k)}\\}_{q\in\mathcal{K}}$.

##  IV Deflation heuristic

Both $\ell_{1}$ and Huber approximate JACoB problems (cf. problems (5) and
(7), respectively) can be seen as some kind of “soft decision” formulations
for handling admission control. In order to select more users for service, we
can apply a hard decision using the deflation heuristic. Similar to [3, 4],
the heuristic is initialized by considering all users in the system, then the
users are dropped one-by-one. At first the BSs solve (5) or (7) either
centrally or using the BCD method. Our user dropping rule is based on the
value of $t_{q}^{\star}\triangleq\max\\{0,f_{q}(\cdot)\\}$ which relates
directly to the satisfiability of the SINR threshold for user $q$. The user
with the largest $t_{q}^{\star}$ will be dropped.

When the number of users in the system is too large, we may encounter cases
where the optimal solution to (5) or (7) is trivial, i.e.,
${\bm{W}}_{q}={\bm{0}}$ for all $q$. Here we state an easy-to-check condition
for identifying such cases.

###### Fact 2

(Prescreening condition)222A similar condition has been discovered recently in
[4] for the joint power and admission control problem. Our results applies to
the case with CoBF. If

$\bm{\Phi}_{q}(\\{{\bm{H}}_{i(q),m}\\}_{m\in\mathcal{K}}))\succeq{\bm{0}},~{}\forall~{}q\in\mathcal{K},$
(9)

then solving (5) or (7) gives a trivial solution, i.e.,
${\bm{W}}_{q}={\bm{0}}$ for all $q$ in $\mathcal{K}$, where

$\bm{\Phi}_{q}(\\{{\bm{H}}_{i(q),m}\\}_{m\in\mathcal{K}}))\triangleq\epsilon{\bm{I}}+\sum_{m\neq
q}{\bm{H}}_{i(q),m}-\frac{1}{\gamma_{q}}{\bm{H}}_{i(q),q}.$

The proof is omitted due to space limitation. Inspired by fact 2, we now adopt
a _prescreening procedure_ where we drop the users gradually until condition
(9) gets violated. Specifically, at each time, we remove user $q$ with
$\bm{\Phi}_{q}(\cdot)$ that gives the largest minimum eigenvalue As condition
(9) can be checked in closed-form, the prescreening procedure can be run at a
low complexity. The deflation heuristic, together with prescreening, are
summarized as follows333Note that both the deflation heuristic and
prescreening procedure can be operated in a decentralized manner.:

Deflation heuristic: $\bullet$ Initialize: a set of users requesting service -
$\mathcal{K}=\\{1,2,...,KM\\}$. 1. (Prescreening) Check condition (9). If it
holds, then remove user $m$ from $\mathcal{K}$ according to
$m=\arg\max_{q}\lambda_{min}(\bm{\Phi}_{q}(\cdot))$ and repeat 1). Otherwise,
go to 2). 2. (Deflation) Solve (5) or (7) for
$\\{t_{q}^{\star},{\bm{W}}_{q}^{\star}\\}_{q\in\mathcal{K}}$. If
$t_{q}^{\star}=0$ for all $q\in\mathcal{K}$, terminate. Otherwise remove user
$m$ from $\mathcal{K}$ according to $m=\arg\max_{q}t_{q}^{\star}$, repeat 2).
$\bullet$ Return: a set of selected users $\mathcal{K}$ and rank-one matrices
$\\{{\bm{W}}_{q}^{\star}\\}_{q\in\mathcal{K}}$ that decomposes into
beamforming vectors satisfying the SINR requirements.

##  V Numerical results

This section presents numerical results for the proposed JACoB methods. The
simulation environment is similar to [2]. We focus on a multicell scenario
with 3 coordinating BSs where each BS is separated from the others by 2.8 km.
For each simulation trial, the users’ positions and their respective channels
are randomly generated. The users are separated from their respective BS by at
least 0.7 km and are assigned to the nearest BS. The channel is assumed to
experience both small-scale and large-scale fading. The noise variance
$\sigma_{q}^{2}$ is -92 dBm and the receive antenna gain is 5 dBi. There are 8
transmit antennas and 15 users are assigned to each BS (i.e., 45 users
awaiting service in total).

Here, the centralized method and the decentralized method refer to the
deflation heuristic which uses a centralized solver for (5) and the
decentralized BCD method for (7), respectively. The scalar $\epsilon$ is
chosen as $10^{-5}$ and the BCD method terminates when the relative change in
objective value is less than $10^{-2}$.

Figure 2: Total no. of users admitted, $M=3$, $N=8$, $K=15$.

Figure 2 shows the performance of different JACoB methods in terms of the
total number of users selected for service. Here, two benchmarking methods are
compared. The “SDR deflation method” is adopted from [3] and modified to
operate in the multicell scenario. Note that it is a centralized method which
may not be decomposed straightforwardly. The “single cell deflation method” is
a modified algorithm from [11], which is originally proposed as a suboptimal
alternative to the CoBF problem (2). The main feature of [11] is that the ICI
levels are always constrained below a fixed threshold, and therefore the
beamforming design can be done independently at each BS. The subsequent
single-cell beamforming design is processed by our JACoB method. Note that the
resultant method can be implemented in a per-BS decentralized manner _without_
any BS coordination.

Turning back to Figure 2, we compare the performance of [3] with the proposed
centralized method. We observe that there are some performance gains with the
proposed method in the high SINR regime. Furthermore, the proposed
decentralized method achieves a performance on a par with its centralized
counterpart. The decentralized method should also be compared to the single
cell deflation method, where the numerical results has clearly demonstrated
the benefits of allowing BSs coordination.

Table I demonstrates the efficacies of the proposed decentralized BCD method
with prescreening procedure in terms of the total number of iterations. The
total number of iterations is defined as the total number of BCD iterations
consumed _throughout_ the deflation heuristic, where multiple instances of (7)
are solved. Note that the load on the backhaul link is directly proportional
to the iteration count. The iteration counts reported in Table I confirms that
significant reduction in the number of iterations can be achieved _with_ the
prescreening procedure.

##  VI Conclusion

The contributions of this paper are twofold. First, we have developed a
formulation of joint admission control and beamforming (JACoB) for coordinated
multicell downlink, wherein an efficient convex approach is proposed. Second,
we have built a decentralized JACoB method via a simple BCD procedure.
Simulation results have shown that the decentralized method achieves a
performance on a par with the centralized method with fast convergence.

TABLE I: Total no. of iterations, $M=3,N=8,K=15$. Threshold ($\gamma$) | With prescreening | Without prescreening
---|---|---
12 dB | 53.080 | 61.790
20 dB | 31.030 | 59.290

## References

  * [1] D. Gesbert, S. Hanly, H. Huang, S. Shamai Shitz, O. Simeone, and W. Yu, “Multi-Cell MIMO cooperative networks: a new look at interference,” _IEEE J. Sel. Areas Commun._ , vol. 28, no. 9, pp. 1380–1408, Dec. 2010.
  * [2] H. Dahrouj and W. Yu, “Coordinated beamforming for the multicell multi-antenna wireless system,” _IEEE Trans. Wireless Commun._ , vol. 9, no. 5, pp. 1748–1759, May 2010.
  * [3] E. Matskani, N. Sidiropoulos, L. Tassiulas, and Z.-Q. Luo, “Convex approximation techniques for joint multiuser downlink beamforming and admission control,” _IEEE Trans. Wireless Commun._ , vol. 7, no. 7, pp. 2682–2693, Jul. 2008.
  * [4] Y.-F. Liu, Y.-H. Dai, and Z.-Q. Luo, “Joint power and admission control via linear programming deflation,” in _ICASSP2012’_ , pp. 2873–2876.
  * [5] A. Tolli, H. Pennanen, and P. Komulainen, “Decentralized minimum power multi-cell beamforming with limited backhaul signaling,” _IEEE Trans. Wireless Commun._ , vol. 10, no. 2, pp. 570–580, Feb. 2011.
  * [6] A. Gershman, N. Sidiropoulos, S. Shahbazpanahi, M. Bengtsson, and B. Ottersten, “Convex optimization-based beamforming,” _IEEE Signal Process. Mag._ , vol. 27, no. 3, pp. 62–75, May 2010.
  * [7] Y. Huang and D. Palomar, “Rank-constrained separable semidefinite programming with applications to optimal beamforming,” _IEEE Trans. Signal Process._ , vol. 58, no. 2, pp. 664–678, Feb. 2010.
  * [8] D. P. Bertsekas, _Nonlinear Programming_ , 2nd ed. Athena Scientific, Sep. 1999.
  * [9] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, 2004.
  * [10] L. Grippo and M. Sciandrone, “On the convergence of the block nonlinear gauss-seidel method under convex constraints,” _Operations Research Letters_ , vol. 26, no. 3, pp. 127 – 136, 2000.
  * [11] H. Huh, H. C. Papadopoulos, and G. Caire, “Multiuser MISO transmitter optimization for intercell interference mitigation,” _IEEE Trans. Signal Process._ , vol. 58, no. 8, pp. 4272–4285, Aug. 2010.