1

Throughput Maximization in Cloud Radio Access
Networks using Network Coding

arXiv:1801.05104v1 [] 16 Jan 2018

Mohammed S. Al-Abiad∗ , Ahmed Douik† , Sameh Sorour‡ , and MD Jahangir Hossain∗
∗ The University of British Columbia, Kelowna, BC, Canada
† California Institute of Technology, Pasadena, CA, United States of America
‡ University of Idaho, Moscow, ID, United States of America
∗ mohammed.saif@mail.ubc.ca,jahangir.hossain@ubc.ca † ahmed.douik@caltech.edu, ‡ samehsorour@uidaho.edu
Abstract—This paper is interested in maximizing the total
throughput of cloud radio access networks (CRANs) in which
multiple radio remote heads (RRHs) are connected to a central
computing unit known as the cloud. The transmit frame of each
RRH consists of multiple radio resources blocks (RRBs), and the
cloud is responsible for synchronizing these RRBS and scheduling
them to users. Unlike previous works that consider allocating
each RRB to only a single user at each time instance, this
paper proposes to mix the flows of multiple users in each RRB
using instantly decodable network coding (IDNC). The proposed
scheme is thus designed to jointly schedule the users to different
RRBs, choose the encoded file sent in each of them, and the
rate at which each of them is transmitted. Hence, the paper
maximizes the throughput which is defined as the number of
correctly received bits. To jointly fulfill this objective, we design
a graph in which each vertex represents a possible user-RRB
association, encoded file, and transmission rate. By appropriately
choosing the weights of vertices, the scheduling problem is shown
to be equivalent to a maximum weight clique problem over
the newly introduced graph. Simulation results illustrate the
significant gains of the proposed scheme compared to classical
coding and uncoded solutions.
Index Terms—Cloud Radio Access Networks, instantly decodable network coding, rate adaptation, coordinated scheduling.

I. I NTRODUCTION
The continuously increasing demand for high-speed data
transfer over the air imposes severe burdens on current wireless
networks, and thus calls for the design of extremely efficient
transmission solutions. Moreover, the scarcity of the radio resources raises extra challenges on the next generation wireless
networks to meet the expected quality of service requirements
by end-users. To address these issues, a revolution in the
network’s architecture design is required. The move towards
dense cellular architectures solved a component of the problem
but raised more problems regarding interference management.
The solution was recently proposed in [1] which gave birth
to cloud radio access networks (CRANs) [2], [3] in which
multiple remote radio heads (RRHs) are coordinated in a
centralized fashion by a computing unit known as the cloud.
With this new architecture, there is a need to design
scheduling schemes of RRHs and their associations to users in
order to fully utilize its benefits. Without cloud coordination,
RRH scheduling in heterogeneous networks was performed
using a preassigned association of mobile users and RRHs,
e.g., proportional fair scheduling [4], [5]. Recent works on
CRANs, e.g., [6], [7], suggested scheduling users to RRHs
in a coordinated fashion at the cloud so as to maximize
the network total ergodic capacity. These works, however,

view the network solely from the physical layer, e.g., [8].
Therefore, each radio resource block (RRB) serves only one
user in each transmission instant. Clearly, this does not take
into consideration upper layer facts. For instance, it has been
recently found that users tend to have a common interest in
downloading popular files (especially videos) within a small
interval of time, thus creating a pool of side information
in the network. This paper proposes to incorporate network
coding (NC) in the scheduling decisions of RRHs and RRBs
in order to utilize this side information in enhancing the system
throughput when other users request to download these same
files.
NC was introduced [9] as a new paradigm that performs
flow mixing (i.e., coding) at intermediate nodes in the network.
It has demonstrated great benefits to improve the performance
for numerous network metrics such as throughput improvement and delay minimization [10]. A particularly interesting
sub-class of NC is the instantly decodable network coding
(IDNC). Indeed, thanks to its instant decodability properties
and straightforward operations to encode/decode files, IDNC
was the subject of numerous studies, e.g., [11]-[14]. IDNC
uses XOR-based operations for encoding at the transmitters
and decoding at the receivers. These simple operations are
well-adapted to small and battery-powered devices.
Different studies on IDNC revealed various code construction schemes with excellent potential in minimizing various
system parameters for different applications and network
settings. For example, while the authors in [11] suggest
minimizing the total transmission time, i.e., the completion
time, reference [12] optimizes the decoding delay. Similarly,
the authors in [13] introduce a delay-based framework to
reduce the completion time. Recently, IDNC was employed in
a heterogeneous network setting to minimize the completion
time of the users by jointly selecting the message combinations
and transmission rates of each RRH [14]. This paper aims
to extend the study to the CRAN setting. By exploiting the
side information of each user, obtained from previous file
downloads, coded files can be multicast to several users to
increase the total received throughput in each transmission.
This work investigates the use of IDNC in CRANs in order
to maximize such received throughput.
Given the above facts, the overall received throughput
maximization problem of interest in this paper must consider
the joint scheduling of users to RRBs in RRHs, choice of the
encoded file sent in each of them, and the rate at which each of
them is transmitted. For practical CRANs design, e.g., limited
capacity backhaul links, the above joint problem should be

2

RRH 1 transmission frame

. . . .

P1,1

. . . .

P2,1
RRH B transmission frame

PB,1

P2,Z

...

Wireless Network Cloud

RRH 3

...

RRH 2 transmission frame
RRH 1

P1,Z

. . . .

PB,Z

RRH 2

Fig. 2: Frame structure of the B RRHs each containing Z RRBs.
Fig. 1: A CRAN composed of 5 users, and 3 RRHs.

solved under the constraint that each user can be scheduled
to a single RRH, but possibly to multiple RRBs within it.
Furthermore, each RRH should transmit at a rate less than
the ergodic capacity of all the scheduled users for each RRB.
Consequently, increasing the number of multiplexed users in
each RRB can easily decrease the transmission rate, and thus
the overall system throughput.
The main contribution of this paper is to solve the above
received throughput maximization problem. To that end, the
paper introduces a graph, called herein the CRAN-IDNC
graph, in which vertices represent a 5-tuple combination
of RRH, RRB, user, file, and transmission rate. A one-toone correspondence between the cliques of the graph and
the solutions of the scheduling problem is established. By
carefully designing the weights of the vertices, the problem
of interest is shown to be equivalent to a maximum weight
clique problem over the CRAN-IDNC graph.
The rest of this paper is organized as follows: Section II
introduces the system model. The network coding model and
the problem formulation are illustrated in section III. Section
IV designs the graph and presents the proposed solution.
Finally, before concluding in Section VI, Section V plots and
discusses the simulation results.
II. S YSTEM M ODEL AND PARAMETERS
A. Network Model
This paper considers the use of IDNC in the downlink of
a CRAN as the one shown in Figure 1. The network consists
of a set B of B remote radio heads (RRHs), which are
distributed in different geographic locations within the cell.
These B RRHs are connected to a central computing unit,
i.e., the cloud controller, which is responsible for the dynamic
scheduling, control decisions, and synchronization of all the
RRHs’ transmit frames. For instance, in Fig. 1, RRHs 1, 2 and
3 cooperate to serve all mobile users in their joint coverage
range. Each RRH’s transmit frame consists of Z orthogonal
time/frequency RRBs as shown in figure 2.
Let Z be the set of RRBs in the frame of each RRH.
The transmit power Pbz of the z-th RRB in the b-th RRH
can be typically different from those of other RRBs, and is
maintained at a fixed value within the RRB’s duration. The
RRB power levels are typically updated in an outer loop, but
this falls outside the scope of this paper and is left of future

investigations. The total number of available RRBs is the total
number of RRH times the number of RRBs in each RRH, that
is Ztot = BZ.
The network serves a set U of U mobile users possessing
side information. The cloud thus exploits this side information
to allocate users, which can be simultaneously satisfied by
one coded transmission to the same RRBs of one RRH
(See Section III.A for more details). To reduce handover
complexities, each user can be assigned to at most a single
RRH, but possible to many RRBs within it. The use of coding
in the scheduling decisions allows the mixing of multiple
users’ requests in one RRB, provided that their requests can
be all served by one coded file, and that file is transmitted at a
suitable rate, given the RRB’s transmit power, for all of them
to receive it correctly.
B. Physical Layer Model
Let hubz be the complex channel gain from the z-th RRB in
the b-th RRH to the u-th user. The channel gain is assumed
to remain constant during the transmission time of a single
file. This paper considers a general model for the channels
without restrictions on their distribution. However, it uses the
standard assumption that these values are perfectly estimated
and available at the cloud. The ergodic capacity of the uth user assigned to the z-th RRB in the b-th RRH can be
expressed as:
u
Rbz
(t) = log2 (1 + SINRubz ),

(1)

wherein SINRubz is the corresponding signal-to-interference
plus noise-ratio experienced by the u-th user when it is
associated with RRB z of the b-th RRH. This SINR can be
expressed by the following formula:
SINRubz =

Pbz |hubz |2
P
,
σ2 +
Pb0 z |hub0 z |2

(2)

b0 6=b

where σ 2 is the complex Gaussian noise variance. Note that
this paper assumes orthogonal RRBs within the same RRH.
As a result, interference at the z-th block is only seen from
RRBs that have the same index z across the other RRHs.
The reception of an encoded file sent in the z-th RRB of
the b-th RRH is successful at the u-th mobile user if the
transmission rate Rbz is less than or equal the user’s capacity,
u
i.e., Rbz 6 Rbz
. In other words, the z-th RRB of b-th RRH
can transmit at a rate at most equal to the minimum ergodic

3

u1
2

P1,1

1

2

3

3

u2
1

3

u3

P2,1

1

2

3

1

2

Fig. 3: A CRAN composed of 3 users, 3 files, 2 remote radio heads,
and 1 RRB in each RRH’s transmit frame.

capacity of its assigned users. It is important to note that this
paper assumes perfect channel estimation scenario so that the
t-th file transmission by z-th RRB of b-th RRH to its assigned
users is received successfully without any erasures.
The set of achievable capacities of all users in all RRBs
across all RRHs can be represented by the set:
O
u
R=
Rbz
,
(3)
(b,z,u)∈ B×Z×U

N

wherein the symbol
represents the product of the set of the
achievable capacities.
III. N ETWORK C ODING AND P ROBLEM F ORMULATION
This section first introduces the side information model
and IDNC. Afterward, the overall throughput maximization
problem in CRANs is formulated.

IDNC allows the cloud to generate XOR-encoded files
using the source files in F. Therefore, users that receive a
combination that contains only one file from its Wants sets
are able to decode the combination and retrieve their wanted
file. A combination that can be used to extract a new wanted
file by any user is said to be instantly decodable for that user.
Consider Figure 3 which illustrates an example of a CRAN
system composed of 3 users, 3 files, 2 RRHs, and 1 RRB
per RRH frame. Assuming that the achievable capacities of
all users to the RRB is 1 bit/second. The file combination
1 ⊕ 2 is instantly decodable for users 1 and 2 but not for 3.
The optimal achievable overall throughput in this scenario is
3 bits/s. Indeed, the first RRH targets users 1 and 2 with 1 ⊕ 2
and the second serves user 3 with 3. Such approach improves
upon the achievable 2 bits/s throughput without coding.
B. Problem Formulation
This paper considers maximizing the throughput in the
aforementioned CRAN setting by assigning users to the RRBs
in the RRHs under the following network connectivity constraints (CC):
• CC: Each mobile user can connect to at most a single
RRH, but possibly to many RRBs in that RRH.
Let κbz be the transmitted (encoded) file in the z-th RRB of
the b-th RRH, i.e, κbz is an element of the power set P(F). Let
u
Xbz
be a binary variable that is set to 1 if user u is assigned
to the z-th RRB of the b-th RRH, and zero otherwise. Let
Ybu be a binary variable that is set to 1 if user u is assigned
to the b-th RRH, and zero otherwise. The overall throughput
maximization problem can be formulated as follows:
XX X
u
max
Xbz
Rbz
(4a)
b∈B z∈Z u∈τbz (κbz )

A. Instantly Decodable Network Coding
The paper assumes that the users are interested in receiving
one or more files out of a set of F of F files, which are
deemed popular due to their previous multiple downloads by
different subsets of the users. All files in F are assumed to
have the same size of N bits, and thus, an XOR encoding of
any number of files (that we will refer to as an encoded file) is
also N bits. The different prior downloads of the users from F
creates an asymmetric side information in the network. Indeed,
in each scheduling epoch, the files of F can be classified for
each user u as follows:
• The Has set Hu containing the files previously downloaded by the u-th user.
• The Wants set Wu ⊆ F\Hu containing the file(s) requested by the u-th user in the current scheduling frame.
It is typical in this scenario that the cloud keeps a log of all
downloaded files by the users, and thus the side information
is perfectly available to the cloud. This side information can
be thus exploited to transmit encoded files instead of sending
simple uncoded files. Consequently, the cloud controller is thus
required to jointly perform the users-RRH/RRB scheduling,
encoded file selection, and rate selection for each RRB, in
order to maximize the number of received decodable bits, i.e.,
the throughput, in each scheduling frame.

!
s.t.

Ybu

= min

X

u
Xbz
,1

, ∀ (b, u) ∈ B × U,

(4b)

z

X

Ybu 6 1, ∀ u ∈ U,

(4c)

b


τbz (κbz ) =


u
u ∈ U κbz ∩ Wu = 1 & Rbz 6 Rbz
, (4d)

u
Xbz
, Ybu ∈ {0, 1}, κbz ∈ P(F), (u, b, z) ∈ U × B × Z, (4e)
u
The optimization is carried over the variables Xbz
, Ybu , κbz ,
u
u
and Rbz . The variables Yb and Xbz are discrete optimization
parameters that represent the user-RRH and user-RRB associations, respectively. On the other hand, the variables κbz
and Rbz account for the file combination and the transmission
rate for the z-th RRB of the b-th RRH, respectively. Constraints (4b) and (4c) translate the system condition CC, i.e.,
each user must connect to at most one RRH. The variable
τbz (κbz ) denotes the targeted set of users benefiting from the
encoded file transmitted in the z-th RRB of the b-th RRH.
Consequently, Constraint (4d) ensures that all users belonging
to these targeted sets τbz (κbz ) ∀ b ∈ B and z ∈ Z must
receive an instantly decodable transmission. In other words,
the targeted users can retrieve and decode a new file from the
combination κbz when transmitted at the rate Rbz .

4

TABLE I: Variables and Parameters of the System

U
F
B
Z
R
Wu
Rbz
κbz
τbz (κbz )
A
Abz

Set of U mobile users
Set of F files
Set of B Radio Remote Heads (RRH)
Set of Z Radio Resource Blocks (RRBs)
Set of all achievable capacities
Set of wanted files by user u
Transmission rate of z RRB in b RRH
The encoded file of the z-th RRB
in the b-th RRH
Set of targeted users by κbz
Set of all possible associations
The association of z RRB in b RRH

Being a mixed discrete-continuous optimization problem,
the throughput maximization problem expressed in (4a) may
require an extensive search over all possible user-RRH/RRB
associations, file combinations, and determining the achievable
capacities for every possible association in each RRB across
all RRHs. The rest of this paper proposes a more efficient
algorithm to solve the optimization problem in (4a).
IV. P ROPOSED T HROUGHPUT M AXIMIZATION S OLUTION
In order to efficiently solve the mixed integer-continuous
problem, this paper uses graph theory techniques to map the
feasible points to cliques in a newly introduced CRAN-IDNC
graph. The graph is formed by several clusters (called herein
RRB-IDNC subgraphs) each corresponding to one RRB in
the network. Furthermore, by carefully designing the weights
of the vertices, the joint optimization problem is shown to
be equivalent to finding the maximum weight clique over the
CRAN-IDNC graph. Finally, the optimal and low-complexity
graph-theoretic algorithms available in the literature, e.g., [16],
[17], [18], [19], can be exploited to find the solution.
In order to construct the CRAN-IDNC graph, this section
first creates its building block known as the RRB-IDNC
subgraph. Such subgraph is generated for each RRB z in each
RRH b with a total of Ztot = B × Z local subgraphs to be
created. The CRAN-IDNC graph is constructed by taking the
union of all these subgraphs and appropriately determining the
edges between their vertices.
Let A be the set of all possible associations between RRHs,
RRBs, users, files, and achievable capacities, i.e., A = B×Z ×
U ×F ×R. Let ϕb , ϕz , ϕu , ϕf , and ,ϕr be mappings from the
set A to the set of RRHs B, the set of RRBs Z, the set of users
U, the set of files F, and the set of achievable capacities R.
In other words, given the element y = (b, z, u, f, R) ∈ A, the
mappings are defined as ϕb (y) = b, ϕz (y) = z, ϕu (y) = u,
ϕf (y) = f and ϕr (y) = R, respectively. Finally, let P(A)
represent all possible schedules of associations between RRHs,
RRBs, users, files, and the achievable capacities regardless of
the feasibility of each, i.e., whether each schedule satisfy CC
or not. Similarly, let Abz represent the association relative to
the z-th RRB in the b-th RRH, i.e., y ∈ Abz ⇒ ϕb (y) = b,
and ϕz (y) = z.

A. Construction of the RRB-IDNC Subgraphs
Let the RRB-IDNC subgraph of RRB z in RRH b be
denoted by G bz (V bz , E bz ) wherein V bz and E bz refer to the
set of vertices and edges of this subgraph, respectively. This
RRB-IDNC subgraph is constructed by generating a vertex v
for each possible association s ∈ Abz . Two vertices v ∈ V bz
associated with s ∈ Abz and v 0 ∈ V bz associated with
s0 ∈ Abz are adjacent by an edge, if both following local
conditions (LC) are true:

• LC1:
ϕf (s) ∈ Hϕu (s0 ) and ϕf (s0 ) ∈ Hϕu (s)
or
(ϕf (s) = ϕf (s0 )). This condition shows that the
file combination is immediately decodable for both
users ϕu (s) and ϕu (s0 ) as they either have each other’s
requested file or are requesting the same file, respectively.
0
• LC2: ϕr (s) = ϕr (s ). This condition guarantees that
all adjacent vertices in the subgraph have the same
transmission rate.
B. Construction of the CRAN-IDNC Graph
As stated earlier, the CRAN-IDNC graph G(V, E) is constructed by first generating all the Ztot RRB-IDNC subgraphs.
The vertex set of the CRAN-IDNC graph is simply the union
of theSvertices of all the RRB-IDNC subgraphs; i.e., V =
S
bz
b∈B
z∈Z V . The edges between vertices within the same
RRB-IDNC subgraph are already described in the previous
subsection. Two different vertices belongs to two different
subgraphs are then set adjacent if their combination results
in a feasible schedule, i.e., it satisfies the system constraint
CC. To express this fact mathematically, let vertex v ∈ G bz be
0 0
corresponding to the association s ∈ Abz and vertex v 0 ∈ G b z
corresponding to the association s0 ∈ Ab0 z0 . The vertices v,
v 0 are adjacent if they satisfy one of the following general
conditions:
0
0
0
• GC1: ϕu (s) = ϕu (s ) and ϕb (s) = ϕb (s ), ∀ (s, s ) ∈
Abz × Ab0 z0 . This condition translates the fact that the
same user can be served with multiple RRBs within the
same RRH.
• GC2:
(ϕb (s) = ϕb (s0 ) and ϕf (s) = ϕf (s0 ))
OR
ϕb (s) = ϕb (s0 ) and ϕf (s) ∈ Hϕu (s0 ) and ϕf (s0 ) ∈
Hϕu (s) . This condition guarantees that the encoded
combinations of the same users can be served by
multiple RRBs within the same RRH.
• GC3: ϕu (s)
6=
ϕu (s0 ) and (ϕb (s), ϕz (s)) 6=
0
0
(ϕb (s ), ϕz (s )). This condition completes the adjacencies in the graph for any two vertices not opposing the
CC constraint for any two different users.
An example of the CRAN-IDNC graph is shown in Fig. 4
for a simple network consisting of 3 users, 3 files, 2 RRHs,
and 1 RRB in each RRH frame, i.e., the system in figure 3. In
this example, each vertex is labeled bzuf r, where b, z, u, f ,
and r represent the indices of RRHs, RRBs, users, files, and
achievable capacities respectively. The Dashed and solid lines
in Fig. 4 represent the edges generated by the aforementioned
conditions, and the potential maximal cliques in this example
represented in the graph by slid lines are: {11111, 21221},
{21332, 11111}, {21221, 11332}, {21111, 21221, 21331},
{11111, 11221, 11331},
{21112, 11222, 11332},
and

5

TABLE II: Simulation Parameters
21111

11222

Cellular Layout
Cell Diameter
Number of Users
Number of RRBs
Channel Model
Channel Estimation
High Power
Background Noise Power
Bandwidth

21332
21331
21112
11332
11111
11221
11223
1
2
3
R11
= 1, R11
= 3, R11
=2
1
2
3
R21
= 2, R21
= 1, R21
=2

21221

Hexagonal
500 meters
Variable
Variable
SUI-Terrain type B
Perfect
-42.60 dBm/Hz
-168.60 dBm/Hz
10 MHz

11331
180

CRAN-IDNC Graph

CRAN-IDNC Scheme
HEU-SHD Scheme
RLNC Scheme
Classical-IDNC Scheme

Fig. 4: The CRAN-IDNC graph of the network presented in Figure
3.

{11223, 21112, 21332}, achieving a total throughputs of
2, 3, 3, 3, 3, 6, and 7 bits/sec, respectively. Clearly, the last
maximal clique should be the one selected as it maximizes
the throughput of the entire CRAN for this scheduling frame.

Average Throughput in bits/user/Hz

160
140
120
100
80
60
40
20

C. Optimal Assignment Solution
0

Given the above construction of the CRAN-IDNC graph
G(V, E), it can be established that any maximal clique in the
graph satisfies the following criterion:
• All users with vertices in the maximal clique can decode
a new file from the transmission schedule of all RRBs
and RRHs.
• The transmission rate of each RRB identified by the
vertices in a maximal clique is less than or equal to the
channel capacities of all the users having vertices with
the same RRB in that clique.
The following theorem characterizes the solution to the
throughput maximization problem of interest in this paper.
Theorem 1: The CRAN throughput maximization problem
in (4a) is equivalent to a maximum weight clique problem
over the CRAN-IDNC graph, wherein the weight of a vertex
v ∈ V corresponding to the association s = (b, z, u, f, r) ∈ A
is given by:
w(v) = r.

(5)

The set of targeted users and the file combination of the z-th
RRB in the b-th RRH is obtained by combining the vertices of
the maximum weight clique corresponding to the local RRBIDNC graph G bz .
Proof: This theorem is proved by demonstrating the
following facts: The first fact establishes a one-to-one mapping
between the feasible schedules and the cliques in the CRANIDNC graph. Afterwards, the weight of each vertex is set to
be the contribution of the corresponding user to the network.
Therefore, the maximum weight clique is a feasible solution
with the maximum received-throughput. In other words, the
maximum weight clique is the solution to (4a). The complete
proof can be found in Appendix A.


5

10

15

20

25

Number of Users U

Fig. 5: Average Throughput in bits/user/Hz. Vs the number of users
U.

Recall that a clique in a graph is a set of vertices such that
each pair is connected. The maximum weight clique problem
is the one of finding the clique with the maximum weight.
The maximum weight clique problem is an NP-complete
problem, and even its approximation is hard [15]. However,
it can be optimally solved with a reduced complexity as
compared to the naive search, e.g., the optimal algorithms
in [16], [17]. Furthermore, multiple efficient polynomial time
heuristics [18], [19] are proposed in the literature. This paper
uses the simple quadratic complexity heuristic proposed in [8].
V. S IMULATION R ESULTS
This section illustrates the performance of the proposed
solution in the CRAN described in Section II. The RRHs
are uniformly placed in a hexagonal cell. Users are randomly
distributed within the cell whose distance is set to 500 meters.
The number of users, number of RRBs and distribution of
the side information varies so as to study multiple scenarios.
The total number of remote radio heads is fixed to 3. Table II
summarized the additional simulation parameters.
The performance of the proposed solution is compared to
state-of-the-art coded and uncoded methods. In particular, this
section adopts the following schemes (in a similar manner as
[20],[21]) as a baseline algorithms for comparison:
• Classical IDNC (rate-unaware scheme): This scheme
jointly optimizes the selection of an XOR file combination for each RRB in each RRH without considering the

6

104

CRAN-IDNC Scheme
HEU-SHD Scheme
RLNC Scheme
Classical-IDNC Scheme

Average Throughput in bits/user/Hz

Average Throughput in bits/user/Hz

150

100

50

0
1

1.5

2

2.5

3

3.5

4

4.5

5

Number of Radio Resource Blocks per RRH

Fig. 6: Average Throughput in bits/user/Hz. Vs the number of Radio
Resource Blocks Z.

•

•

achievable capacities of users. After the file selection process, the CRAN’s physical-layer employs the minimum
achievable capacity of all users targeted by each RRB as
its transmitting rate.
RLNC (rate-greedy scheme): In this scheme, each user is
associated with a single RRB to which it has the maximum capacity. If more than one user is associated with
the same RRB, random linear network coding (RLNC)
is employed. The encoding is done irrespectively of the
side information. Indeed, as stated earlier, RLNC mixes
all files with different random coefficients. The selected
transmission rate in each RRB is the capacity of users
having the minimum achievable capacity in that RRB.
HEU SHD scheme (uncoded scheme): In this scheme,
only one user is served in each RRB, each user can be
assigned to more than one RRBs from the same RRH.
This scheme is proposed in [8].

Figure 5 depicts the average throughput in bits/user/Hz
achieved by our proposed and the aforementioned schemes for
different numbers of users U , given 4 RRBs per RRH, a file
size N = 1 Mb. From the figure, we note that our proposed
CRAN-IDNC scheme greatly outperforms all other schemes.
In particular, HEU-SHD only focuses on the high achievable
rate at the expense of transmitting at most one message to
a single user from each RRB in all RRHs, i.e., a maximum
number of targeted users is Ztot . On the other hand, RLNC
scheme serves a large number of users in each transmission
but sacrifices the rate optimality. One can also notice that
the gap between our proposed scheme and the HEU-SHD
scheme increases as the number of users increases. This can be
explained by the fact that the maximum number of targeted
users in HEU-SHD is Ztot , so increasing number of users
beyond the Ztot would not largely improve the performance
of the scheme. The proposed scheme, however, benefits from
increasing number of users by mixing the flows of more and
more users to the same RRB given their instant decodability
of their required files due to their side information.
Figure 6 shows the average throughput in bits/user/Hz

CRAN-IDNC Scheme
HEU-SHD Scheme
RLNC Scheme
Classical-IDNC Scheme

102

100

10-2

10-4
103

104

105

106

107

Files Size N in bits

Fig. 7: Average Throughput in bits/user/Hz. Vs the file’s size N in
bits.

achieved by different schemes for different numbers of RRBs
Z, for U = 15 users and a file size N = 1 Mb. Again, the figure
shows that our proposed CRAN-IDNC scheme outperforms
all other schemes. The gap in performance increases as the
number of RRBs per frame grows. It can also be easily seen
from the figure that the performances of both the proposed and
the HEU-SHD schemes increase linearly with the increasing
number of RRBs and a fixed number of users. In fact, both
schemes meet in serving the same user in different RRBs
of the same RRH. Therefore, increases the number of RRBs
increases the total received throughput.
Figure 7 plots the average throughput as a function of the
file size N in a network composed of 15 users and 4 RRBs
per RRH’s transmit frame. As the file’s size increases, the
performance of all schemes increases. The figure shows that
all schemes increase linearly with the size of the file. This
can be explained by the fact that, as the size of the file
increases, more and more bits are received, thus increasing the
average received throughput. Finally, despite its great merits in
reducing the completion time of a frame of files in many prior
works, Classical IDNC exhibits a very poor performance from
a physical layer perspective, thus voiding its upper layer gains.
This clearly shows the importance of rate-awareness in IDNC
code design to achieve gains on both the upper and physical
layers, thus leading to a real reduction in file delivery times.
VI. C ONCLUSION
This paper addresses the throughput maximization problem
in cloud-enabled networks. Unlike previous studies that only
considered the system from a physical layer point of view,
we proposed to use the information available in the network
to combine files using instantly decodable network coding.
Therefore, the throughput maximization problem becomes
same as the problem of assigning users to the available
resource blocks and choosing the file combination and the
transmission rate of each under the constraint that a user can
connect to at most a single remote radio head. We have used a
graph theoretical approach to solve the problem by introducing
the CRAN-IDNC graph formed by several RRB-IDNC graphs.

7

By establishing a correspondence between the feasible solution
to the problem and the cliques in the graph, the problem is
shown to be equivalent to a maximum-weight clique which can
be efficiently solved using state of the art methods. Simulation
results show the performance of the proposed scheme and
reveal that it largely outperforms coding free solutions.
A PPENDIX A
P ROOF OF THEOREM 1
This theorem is proofed by showing a one-to-one mapping
between C (i.e., the set of cliques) in the CRAN-IDNC graph
and the S ∈ P(A), i.e., feasible schedule that satisfy CC.
Afterward, the weight of the clique is shown to be equivalent
to the optimization problem (4a). Therefore, we first show
that, for each maximal clique in CRAN DNC graph, there is
a unique feasible schedule. Then, we show the converse. The
authors in [20] show that there exists a one-to-one mapping
between the set of feasible transmissions and the set of
maximal cliques in the RRB-IDNC graph, i.e., satisfy LC1
and LC2. Hence, to extend the results of [20] to the CRANIDNC graph, we only need to show the following:
• The feasible transmissions from different RRHs are adjacent, i.e., the constraint GC1.
• The same user can be targeted from different RRBs within
the same RRH frame, i.e., the constraint GC2.
• Two different users with two different RRBs should be
connected, i.e., the constraint GC3.
From the general condition GC1 of the CRAN-IDNC graph,
the same user cannot be targeted by distinct RRHs. Thus,
the vertices representing RRH b in the RRB-IDNC graphs
are connected to the vertices in the RRB-IDNC graphs of
RRH b0 , as long as the targeted users are different. From the
general condition GC2 of the CRAN-IDNC graph, the same
user can connect to multiple RRBs within the same RRH
transmit frame. Moreover, from the general condition GC3
of the C-RAN graph, two different users with two different
RRBs should be connected. That is, the vertices in the z-th
RRB-IDNC are connected to the z 0 -th RRB-IDNC as long as
users are not the same. Therefore, each feasible association of
users, RRHs, RRBs, file combinations, and their transmission
rates is represented by a clique C ∈ C within the CRAN-IDNC
graph.
On the other hand, it can readily be seen that each clique
represents a feasible schedule S as it does not violate the
conditions LC1, LC2, GC1, GC2 and GC3. Indeed, for the
maximum
Lclique C ∈ C, the transmission of the combination
κbz =
s∈C ϕf (s) in radio resource block z in remote
radio head S
b at rate r is instantly decodable for all users
τbz (κbz ) = s∈C ϕu (s).
To conclude the proof, the solution of the optimization
problem (4a) is the maximum-weight clique, where the weight
of each vertex can be given by:
w(v) = r.

(A.1)

R EFERENCES
[1] J. G. Andrews, S. Buzzi, W. Choi, S. V. Hanly, A. Lozano, A. C. K.
Soong, and J. C. Zhang, “What will 5g be?“ IEEE Journal on Selected
Areas in Communications, vol. 32, no. 6, pp. 1065–1082, jun 2014.

[2] Park, Seok-Hwan, et al. “Robust and efficient distributed compression
for cloud radio access networks”, IEEE Transactions on Vehicular
Technology 62.2 (2013): 692-703.
[3] Cai, Yegui, F. Richard Yu, and Shengrong Bu. “Cloud computing
meets mobile wireless communications in next generation cellular networks.“ IEEE Network 28.6 (2014): 54-59.
[4] W. Yu, T. Kwon, and C. Shin, “Joint scheduling and dynamic power
spectrum optimization for wireless multicell networks,” in Proc. 44th
Annu. Conf. Inf. Sci. Syst. (CISS’10), Princeton, NJ, USA, Mar. 2010,
pp. 1-6.
[5] W. Yu, T. Kwon, and C. Shin, “Multicell coordination via joint scheduling, beamforming, and power spectrum adaptation,“ IEEE Transactions
on Wireless Communications, vol. 12, no. 7, pp. 1-14, Jul. 2013.
[6] S.-H. Park, O. Simeone, O. Sahin, and S. Shamai, “Joint precoding
and multivariate backhaul compression for the downlink of cloud radio
access networks,” IEEE Transactions on Signal Processing, vol. 61,
no. 22, pp. 5646–5658, 2013.
[7] Y. Shi, J. Zhang, and K. B. Letaief, “Group sparse beamforming
for green cloud-ran,“ IEEE Transactions on Wireless Communications,
vol. 13, no. 5, pp. 2809–2823, 2014.
[8] A. Douik, H. Dahrouj, T. Y. Al-Naffouri, and M.-S. Alouini, “Coordinated scheduling for the downlink of cloud radio-access networks”,
in Proc. IEEE Int. Conf. Commun. (ICC’15), London, U.K.,2014, pp.
2906-2911.
[9] R. Ahlswede, N. Cai, S.-Y. Li, and R. Yeung, “Network information flow,“ IEEE Transactions on Information Theory, vol. 46, no. 4,
pp.1204–1216, Jul. 2000.
[10] T. Ho and D. Lun, Network Coding: An Introduction. New York, NY,
USA: Cambridge University Press, 2008.
[11] S. Sorour and S. Valaee, “Completion delay minimization for instantly
decodable network codes,” IEEE/ACM Transaction on networking, vol.
23, no. 5, pp. 1553-1567, Oct. 2015.
[12] S. Sorour and S. Valaee, “Minimum broadcast decoding delay for generalized instantly decodable network coding,“ in Proc. of IEEE Global
Telecommunications Conference (GLOBECOM’10), Miami, Florida,
USA, Dec 2010, pp. 1-5.
[13] A. Douik, S. Sorour, M.-S. Alouini, and T. Y. Al-Naffouri, “Completion
time reduction in instantly deocdable network coding through decoding
delay control,” in Proc. of IEEE Global Telecommunications Conference
(GLOBECOM’14), Austin, Texas, USA, Dec. 2014.
[14] M. Saif, A. Douik, and S. Sorour, “Rate aware network codes for coordinated multi Base-Station networks,“ in Proc. of IEEE International
Conference on Communications (ICC’16), Kuala Lumpur, Malaysia,
May 2016.
[15] M. Garey and D. Johonson, “Computers and Intractability - A Guide to
the Theorey of NP-Completeness.” Freeman, New York, 1979.
[16] Fomin, Fedor V., Fabrizio Grandoni, and Dieter Kratsch. “A measure &
conquer approach for the analysis of exact algorithms.“ Journal of the
ACM (JACM) 56.5 (2009): 25.
[17] Bourgeois, Nicolas, et al., “A Bottom-Up Method and Fast Algorithms
for max independent set.” SWAT. Vol. 6139. 2010.
[18] Wan, Peng-Jun, et al., “Fast and simple approximation algorithms for
maximum weighted independent set of links.“ IEEE 2014 Proceedings
of INFOCOM, 2014.
[19] Esfahani, Navid Nasr, et al., “A note on the p-time algorithms for solving
the maximum independent set problem.” IEEE 2nd Conference on. Data
Mining and Optimization, 2009. DMO’09. 2009.
[20] A. Douik, S. Sorour, T. Y. Al-Naffouri, and M.-S. Alouini, “Rate aware
instantly decodable network codes,“ IEEE Global Telecommunications
Conference (GLOBECOM’15), San Diego, California, USA, Dec. 2015.
[21] M. S. Karim, A. Douik, S. Sorour, P. Sadeghi, “Rate-Aware Network
Codes for Completion Time Reduction in Device-to-Device Communications,” in Proc. of IEEE International Conference on Communications
(ICC’16), Kuala Lumpur, Malaysia, May 2016.

