# An Enhanced OFDM Resource Allocation Algorithm in C-RAN Based 5G Public Safety Network

Authors: Lei Feng; Wenjing Li; Peng Yu; Xuesong Qiu
Journal: Mobile Information Systems
 (2016)

---

## Abstract

Public Safety Network (PSN) is the network for critical communication when disaster occurs. As a key technology in 5G, Cloud-Radio Access Network (C-RAN) can play an important role in PSN instead of LTE-based RAN. This paper firstly introduces C-RAN based PSN architecture and models the OFDM resource allocation problem in C-RAN based PSN as an integer quadratic programming, which allows the trade-off between expected bitrates and allocating fairness of PSN Service User (PSU). However, C-RAN based PSN needs to improve the efficiency of allocating algorithm because of a mass of PSU-RRH associations when disaster occurs. To deal with it, the resources allocating problem with integer variables is relaxed into one with continuous variables in the first step and an algorithm based on Generalized Bender’s Decomposition (GBD) is proposed to solve it. Then we use Feasible Pump (FP) method to get a feasible integer solution on the original OFDM resources allocation problem. The final experiments show the total throughput achieved by C-RAN based PSN is at most higher by 19.17% than the LTE-based one. And the average computational time of the proposed GBD and FP algorithm is at most lower than Barrier by 51.5% and GBD with no relaxation by 30.1%, respectively.


---

## Body

## 1. Introduction

With the rapid upgrading of emergency application, Public Safety Network (PSN) is getting increasingly popular. It is being recognized that wireless-based PSN is a key to a successful response to emergency situations. Article [1] provides a good introduction to the field by surveying public safety use cases, current status of the related standards activities within the 3rd Generation Partnership Project (3GPP), and challenges ahead. Several works [2–4] have pointed out a safety network is a basic guarantee in different industries. Article [5] analyzes the infrastructure of LTE-based PSN and examines the capacity of LTE to meet the requirements of critical communications. The researchers and standards organizations both firmly believe PSN can be further enhanced by 5G emerging technologies, such as D2D, massive-MIMO, and C-RAN [1, 6, 7].There are many PSN issues that needs to be settled by new B4G or 5G technologies. Article [8] uses D2D communication to extend the coverage for PSN communications. Although D2D improves the efficiency of wireless communication, the key or the basic guarantee in PSN is the utilization on the bandwidth spectrum. Article [9] proposes a spectrum allocation scheme to avoid the interference with commercial network. And the American FirstNet is assigned Band 14 on 700 MHz to run the PSN service. Actually, as the increasing demand for rich-content-based emergency applications, PSN needs not only a clean sharing spectrum, but also a flexible centralized bandwidth allocation scheme that can maximally satisfy the data-rate required by all PSN users. Cloud-Radio Access Network (C-RAN), as an important access architecture in 5G, provides a centralized manner of bandwidth management [10]. In C-RAN structure, the spectrum resource of a user associated with a certain RRH is processed by a centralized resource allocator. This integrated resource allocation mechanism enables the users to utilize the service resources more efficiently and makes the system allocate the user’s demanded bandwidth flexibly [11]. In addition, RRHs are always placed high above the ground, which means they are more difficult to be destroyed in disaster than the conventional BBU placed on the ground. In a consequence of that C-RAN lets BBU together to form a BBU pool in a position which is far away from RRHs; C-RAN is safer than LTE base-station infrastructure. It can be seen that these features of C-RAN are more suitable for the requirement of PSN service than LTE E-UTRAN.However, the PSN Service Users (PSUs) will produce a large amount of traffic in times of disaster. Hence, the ability of bandwidth allocation algorithm is a key to assure the critical communication. Article [12] compares the performance of different scheme disciplines for PSN service. But the work is only designed to LTE-based PSN which is in a distributed management scheme [13]. Therefore it is necessary to propose a more high-effective centralized bandwidth allocation algorithm if we introduce a C-RAN based PSN. The previous works concerning the resource allocation in C-RAN networkmainly involve the flexible RRH configuration [14, 15] and the application of the spatial multiplexing technologies in C-RAN [16, 17]. Although spectrum allocation in C-RAN is also discussed in some of them, it is merely treated as a simple constraint. In addition, compared with the normal C-RAN, C-RAN based PSN maybe serve more users when disaster occurs. That means more efficient algorithm to solve the resource allocation problem is required. On the basis of the aforesaid works, in particular for their demerits, this paper proposes a Generalized Benders Decomposition- (GBD-) based OFDM resource allocation algorithm in C-RAN based PSN to find out the solution on the system performance. This algorithm perfects the optimization through primal relaxation and the GBD algorithm that sufficiently enhances the efficiency of resource allocation.The contributions of this paper include two key aspects. The first is we introduce C-RAN based PSN architecture and propose the OFDM resources allocation model in this network. To the best of our knowledge, C-RAN based PSN has not been investigated in the previous works. We formulate OFDM resources allocation problem in C-RAN based PSN as a quadratic programming (QP) with integer variables of OFDM resource block that aims to maximize the emergency system performance. In the formulated problem, the objective system performance is affected by the expected bit-rates revenue and the allocation fairness among different PSUs. By analyzing the wireless channel model, we propose an objective function of the C-RAN based PSN system performance that allows trade-off between the expected bit-rates revenue and the PSU’s fairness when allocating resources.Second, we present an efficient solution for the problem facing the centralized resource allocation in C-RAN based PSN. We firstly relax the integer variable in this QP problem into the continuous one. And a GBD-based algorithm is proposed to address this relaxed problem. The traditional Bender’s Decomposition (BD) algorithm is used to solve the Mixed-Integer Nonlinear Programming (MINP) problem by decomposing the original problem into a master and a subproblem [18–21]. GBD extends the BD approach to a more general class of problems by adopting nonlinear duality theory, and some nonlinear problems are thereby brought into range, including QP we want to solve in this paper. Because of its high computational efficiency for solving the relaxed QP, the proposed algorithm is suitable in C-RAN based PSN which has many PSU associations. Proved by theory, the proposed algorithm is guaranteed to obtain the optimal solution on the relaxed problem. Then we use the Feasible Pump (FP) [22] method to guarantee we can find out a feasible integer solution on the original QP from the optimal solution on the relaxed problem with continuous variables. We also analyze the error tolerance as the algorithm terminated condition to allow the balance trade-off between the nice convergence properties and the system performance.The rest of the paper is organized as follows: In Section2, we describe the C-RAN based PSN architecture and formulate the OFDM resource allocation problem. In Section 3, we solve the formulated QP of integer variables by problem relaxation, Generalized Bender’s Decomposition, and Feasible Pump. The specific algorithm is also proposed and analyzed in this section. In Section 4, we firstly investigate the performance of C-RAN based PSN. And then the convergence and computing time of the proposed algorithm are analyzed. Finally, we drew some concluding remarks.


## 2. System Model

### 2.1. C-RAN Based PSN Architecture

Figure1 shows a schematic diagram of our introduced C-RAN based PSN architecture for public safety applications. Each PSU runs different PSN service covered by a RRH. C-RAN based PSN adopts a centralized processing manner, namely, the BBU processing pool. The spectrum resource of a PSU associated with a certain RRH is processed by a centralized resource allocator in C-RAN. This integrated resource allocation mechanism enables the PSU to utilize the dedicated PSN service bandwidth resources more effectively and on-demand.Figure 1
C-RAN based PSN architecture.Our C-RAN based PSN architecture allocates PSN spectrum resources centrally to improve the whole network performance. But to meet the critical communication requirement, this raises one important issue that needs to be considered: the assignment algorithm efficiency, especially for that there are a lot of PSU-RRH associations when disaster occurs. This is the key problem we want to solve in this paper. Since the OFDM is the dominant resource-multiplexing technology currently, in this paper, we focus on the OFDM resource allocation in C-RAN based PSN with a view to maximizing the system performance by optimally scheduling the centralized OFDM bandwidth resources.


### 2.2. PSU-RRH Association Model

Firstly, it needs to establish an association model between PSU and RRH. Assume that in a C-RAN based PSN system,U
=
{
u
n
∣
1,2
,
…
,
N
} expresses the PSUs set and B
=
{
b
m
∣
m
=
1,2
,
…
,
M
} the RRHs set. We consider the network is an OFDM system whose resource element is called Resource Block (RB). Let B
R
B denote the bandwidth of each RB and B
W the total bandwidth. Hence the total number of RBs is B
W
/
B
R
B. The RB scheduling matrix is denoted by Y
∈
Z
N
×
M
=
y
i
j
N
×
M, where y
i
j is the number of RBs allocated to PSU u
j by RRH b
i. Particularly, y
i
j
=
0 means PSU u
j is not served by RRH b
i, which also stands for no association between PSU u
j and RRH b
i.To facilitate analysis, we leave the reusable resource case to our further study, and temporarily in this section, the resource cannot be reused in the same C-RAN based PSN system. Then we get one of the constraints ofy
i
j that ∑
i
=
1
,
j
=
1
N
,
M
y
i
j
B
R
B
=
B
W. To make the model more convenient to solve, the RB allocation matrix Y should be transformed into a vector, the definition of which is given below.Definition 1 (RB allocation vector).
LetX
∈
R
M
N
=
x
i
j
M
N, where i
=
m
-
1
·
N
+
n, if (1)
x
m
-
1
·
N
+
n
=
y
n
m
.
ThenX is calledRB allocation vector for RB allocation matrix Y, where x
m
-
1
N
+
n stands for the amount of RBs allocated to PSU u
n from RRH b
m. Particularly, x
m
-
1
N
+
n
=
0 means PSU u
n is not served by RRH b
m. A simple illustration of the transformation from a RB scheduling matrix to a corresponding RB allocation vector is shown in Figure 2.Figure 2In Figure2, 2 RRHs and 3 PSUs make up the network, and the total number of RBs amounting to 100 is allocated by a C-RAN allocator uniformly. It can be seen from the RB allocation matrix in the above example that PSU 1 and PSU 3 are served by RRH 1 with 23 RBs and RRH 2 with 24 RBs bandwidth, respectively. As multiple RRHs can perform joint transmission such as CoMP [23], PSU 2 is served by RRH1 and RRH2 simultaneously, and the spectrum resources allocated to PSU 2 totals at 53 RBs. The matrix Y is transformed into a column vector X with the same 6 elements, following the rules illustrated in (1) that the columns in X are rearranged into one column. The column vector is the corresponding RB allocation vector.


### 2.3. System Bit-Rate Revenue

Bit-rate capacity is a key feature to the performance of future wideband PSN rich-content services. The typical aim of the resource allocation scheme is to maximize the total bit-rate capacity in the traditional cellular. Hence, in this paper we use the achievable bit-rate capacity of all PSUs as the C-RAN based PSN system’s revenue. This section analyzes the characteristics of the wireless fading channel to derive the outage probability of the system, based on which the achievable bit-rate capacity of a PSU in unit bandwidth can be resolved. Finally, the achievable PSU bit-rate per unit bandwidth is defined to represent the system revenue.LetP
m
t denote the transmit power of RRH b
m, G
m
a the antenna gain, and P
n
m
r the signal power received by u
n from RRH b
m. The fading channel is characterized by a matrix H
n
m, which is composed of 3 parts: path loss H
n
m
d, slow fading H
s, and fast fading H
n
f. H
n
m can be expressed by (2)
H
n
m
=
H
n
m
d
·
H
s
·
H
n
f
,where H
n
m
d
=
d
n
m
-
α, d
n
m is the physical distance between PSU u
n and RRH b
m, and α is the path loss exponent. Slow fading H
s
=
e
s, where S
~
N
μ
s
,
σ
2
2; that is, H
s follows lognormal distribution, and the Probability Distribution Function (PDF) is given in (3)
f
H
s
s
=
1
s
σ
2
π
e
-
ln
⁡
s
-
μ
s
2
/
2
σ
s
2
,
s
>
0
,
0
,
s
≤
0
.Assume that the PSU uses Maximal Ratio Combining (MRC) scheme to achieve full diversity gain, and the fast fadingH
n
f can be calculated by (4)
H
n
f
=
∑
l
=
1
L
n
h
n
l
2
,where h
n
l is the fast fading diversity gain from the lth antenna of PSU and h
n
l can be modeled as a random variable following standard normal distribution, that is, h
n
l
~
N
(
0,1
). L
n is the number of antennas in the PSU u
n. If l
≥
2, H
n
f
~
Γ
(
L
n
,
1
), and the PDF is given by (5)
f
H
n
f
v
=
v
L
n
-
1
e
-
v
L
n
-
1
!
,
v
>
0
,
0
,
v
≤
0then the received power of UEu
n from RRH b
m, P
n
m
r is given in (6)
P
n
m
r
=
P
m
t
G
m
a
H
n
m
=
P
m
t
G
m
a
H
s
H
n
f
d
n
m
-
α
.Supposing the threshold of the received power guaranteeing the basic communication service isT
r, the outage probability of PSU u
n to access RRH b
m at a distance d can be written as(7)
Pr
⁡
P
n
m
r
<
T
r
=
Pr
⁡
H
s
H
n
f
<
T
r
d
n
m
α
P
m
t
G
m
a
.In this paper, we take the impacts of two different scales of fading into consideration, which results in an outage probability resolving problem in elaborately modeled fading channel. Letβ
n
m
=
d
n
m
α
/
P
m
t
G
m
a, because H
s and H
n
f are independently and identically distributed; then(8)
Pr
⁡
H
s
H
n
f
<
T
r
γ
n
m
=
∫
0
+
∞
∫
0
T
r
β
n
m
/
s
f
H
s
s
f
H
n
f
v
d
v
d
s
=
1
-
∫
0
+
∞
f
H
s
s
∫
T
r
β
n
m
/
s
+
∞
f
H
n
f
v
d
v
d
s
.The cumulative distribution function of a gamma distributed variable with scale parameter being 1 can be written asγ
a
,
b
=
∫
b
+
∞
z
a
-
1
e
-
z
d
z, so the integral term of the slow fading can be written as(9)
∫
T
r
β
n
m
/
s
+
∞
f
H
n
f
v
d
v
=
∫
T
r
β
n
m
/
s
+
∞
v
L
n
-
1
e
-
v
L
n
-
1
!
d
v
=
γ
L
n
,
T
r
β
n
m
/
s
Γ
L
n
.Substituting (9) into (7), the outage probability of PSU u
n to access RRH b
m at a distance d can be rewritten as(10)
Pr
⁡
P
n
m
r
<
T
r
=
1
-
∫
0
+
∞
1
s
σ
2
π
γ
L
n
,
T
r
β
n
m
/
s
Γ
L
n
e
-
ln
⁡
s
-
μ
s
2
/
2
σ
s
2
d
s
.Then we can use the Gauss-Hermite quadrature to solve the numerical result of (10). Next, we are to derive the achievable bandwidth efficiency c
n
m of PSU u
n served by RRH b
m. Firstly, according to (10), the PDF of SNR is(11)
f
S
N
R
T
r
=
∂
Pr
⁡
T
r
>
P
n
m
r
∂
T
r
=
∑
k
=
1
k
H
A
k
H
π
Γ
L
n
∂
γ
L
n
,
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
∂
T
r
.Asγ
(
a
,
b
) is used to define CDF and its infinity integral is convergent, according to the derivation rule of the uncertain limit integral, we have(12)
∂
γ
L
n
,
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
∂
T
r
=
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
L
n
·
T
r
L
n
-
1
e
-
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
.The PDF of SNR in (12) can be rewritten as(13)
f
S
N
R
T
r
=
∑
k
=
1
k
H
A
k
H
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
L
n
π
Γ
L
n
·
T
r
L
n
-
1
e
-
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
.Let random variablec
n
m
=
log
2
⁡
1
+
T
r
/
N
0 denote the bit-rate capacity per unit bandwidth of PSU u
n served by RRH b
m, in which N
0 is the average power of Gauss white noise. The expectation of c
n
m, μ
n
m
c can be written as(14)
μ
n
m
c
=
E
c
n
m
=
∫
0
+
∞
f
S
N
R
T
r
l
o
g
2
1
+
T
r
N
0
d
T
r
.Then (14) can be rewritten as(15)
μ
n
m
c
=
∑
k
=
1
k
H
A
k
H
e
-
L
n
2
σ
s
ω
k
H
+
μ
s
β
n
m
L
n
π
Γ
L
n
·
∫
0
+
∞
e
-
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
T
r
L
n
-
1
l
o
g
2
1
+
T
r
N
0
d
T
r
.Then we can adopt the Gauss-Laguerre quadrature to solve the numerical result of (15). Based on (15), we give the definition of the expected revenue vector in C-RAN based PSN.Definition 2 (expected revenue vector).
LetR
∈
R
M
N
=
r
i
M
N. If (16) holds(16)
r
m
-
1
·
N
+
n
=
μ
n
m
c
,where i
=
m
-
1
·
N
+
n, then r
m
-
1
·
N
+
n is the average bit-rate capacity of PSU u
n in unit bandwidth served by RRH b
m, and R is called theexpected revenue vector of the system.In addition, the variance ofc
n
m denoted as σ
n
m
c
2 is(17)
σ
n
m
c
2
=
D
c
n
m
=
E
c
n
m
2
-
μ
n
m
c
2
=
∫
0
+
∞
f
S
N
R
T
r
l
o
g
2
1
+
T
r
N
0
2
d
T
r
-
μ
n
m
c
2
.The correlation coefficients ofc
n
m and c
n
′
m
′, ρ
n
m
,
n
′
m
′
c, is (18)
ρ
n
m
,
n
′
m
′
c
=
E
c
n
m
·
c
n
′
m
′
-
μ
n
m
c
μ
n
′
m
′
c
σ
n
m
c
σ
n
′
m
′
c
.As complete joint transmission technology is adopted in C-RAN and a PSU can be served by multiple RRHs simultaneously, in the case ofm
=
m
′ and n
=
n
′, ρ
n
m
,
n
′
m
′
c
=
1 and in other cases, ρ
n
m
,
n
′
m
′
c
=
0.


### 2.4. Resource Allocation Problem Formulation

This paper takes into account both expected revenue of the system and PSU’s fairness when allocating the RBs in C-RAN based PSN. Hence, for the sake of maximizing the system performance, the following quadratic programming (QP) is derived:(19)
m
a
x
X
z
=
B
R
B
X
T
R
-
κ
B
R
B
2
X
T
Q
X
s
.
t
.
∑
i
=
1
M
N
x
i
=
B
W
B
R
B
X
=
x
i
M
N
,
x
i
∈
0,1
,
…
,
B
W
B
R
B
,where Q
=
q
i
j
M
N
×
N
M is a matrix relative to the covariance of the system revenue. The element q
i
j
=
ρ
n
m
,
n
′
m
′
c
σ
m
n
c
σ
m
′
n
′
c, where i
=
m
-
1
·
N
+
r and j
=
m
′
-
1
·
N
+
n
′. It is noticed that the optimization problem aims at maximizing the system performance, where B
R
B
X
T
R stands for the expectation of the bit-rate capacity, that is, the average revenue of the radio access system with a RB allocation scheme X. Based on the definition of Q, the second term (
B
R
B
)
2
X
T
Q
X stands for the variance of the system performance. If the parameter κ
→
0, the model is inclined to allocate more resources to PSUs contributing more revenue to the system, which means poor fairness of PSUs. If κ increases, the model will care more about the allocation fairness of PSUs.Because of the integer decision variables of PSU, when having a large amount of PSU-RRH associations when disaster occurs, the time complexity of solving this NP problem will increase distinctly. Hence, this paper proposes a corresponding Generalized Bender’s Decomposition method on the basis of integer variable continuation, which satisfies the demand on efficiency of algorithm in PSN service.


## 2.1. C-RAN Based PSN Architecture

Figure1 shows a schematic diagram of our introduced C-RAN based PSN architecture for public safety applications. Each PSU runs different PSN service covered by a RRH. C-RAN based PSN adopts a centralized processing manner, namely, the BBU processing pool. The spectrum resource of a PSU associated with a certain RRH is processed by a centralized resource allocator in C-RAN. This integrated resource allocation mechanism enables the PSU to utilize the dedicated PSN service bandwidth resources more effectively and on-demand.Figure 1
C-RAN based PSN architecture.Our C-RAN based PSN architecture allocates PSN spectrum resources centrally to improve the whole network performance. But to meet the critical communication requirement, this raises one important issue that needs to be considered: the assignment algorithm efficiency, especially for that there are a lot of PSU-RRH associations when disaster occurs. This is the key problem we want to solve in this paper. Since the OFDM is the dominant resource-multiplexing technology currently, in this paper, we focus on the OFDM resource allocation in C-RAN based PSN with a view to maximizing the system performance by optimally scheduling the centralized OFDM bandwidth resources.


## 2.2. PSU-RRH Association Model

Firstly, it needs to establish an association model between PSU and RRH. Assume that in a C-RAN based PSN system,U
=
{
u
n
∣
1,2
,
…
,
N
} expresses the PSUs set and B
=
{
b
m
∣
m
=
1,2
,
…
,
M
} the RRHs set. We consider the network is an OFDM system whose resource element is called Resource Block (RB). Let B
R
B denote the bandwidth of each RB and B
W the total bandwidth. Hence the total number of RBs is B
W
/
B
R
B. The RB scheduling matrix is denoted by Y
∈
Z
N
×
M
=
y
i
j
N
×
M, where y
i
j is the number of RBs allocated to PSU u
j by RRH b
i. Particularly, y
i
j
=
0 means PSU u
j is not served by RRH b
i, which also stands for no association between PSU u
j and RRH b
i.To facilitate analysis, we leave the reusable resource case to our further study, and temporarily in this section, the resource cannot be reused in the same C-RAN based PSN system. Then we get one of the constraints ofy
i
j that ∑
i
=
1
,
j
=
1
N
,
M
y
i
j
B
R
B
=
B
W. To make the model more convenient to solve, the RB allocation matrix Y should be transformed into a vector, the definition of which is given below.Definition 1 (RB allocation vector).
LetX
∈
R
M
N
=
x
i
j
M
N, where i
=
m
-
1
·
N
+
n, if (1)
x
m
-
1
·
N
+
n
=
y
n
m
.
ThenX is calledRB allocation vector for RB allocation matrix Y, where x
m
-
1
N
+
n stands for the amount of RBs allocated to PSU u
n from RRH b
m. Particularly, x
m
-
1
N
+
n
=
0 means PSU u
n is not served by RRH b
m. A simple illustration of the transformation from a RB scheduling matrix to a corresponding RB allocation vector is shown in Figure 2.Figure 2In Figure2, 2 RRHs and 3 PSUs make up the network, and the total number of RBs amounting to 100 is allocated by a C-RAN allocator uniformly. It can be seen from the RB allocation matrix in the above example that PSU 1 and PSU 3 are served by RRH 1 with 23 RBs and RRH 2 with 24 RBs bandwidth, respectively. As multiple RRHs can perform joint transmission such as CoMP [23], PSU 2 is served by RRH1 and RRH2 simultaneously, and the spectrum resources allocated to PSU 2 totals at 53 RBs. The matrix Y is transformed into a column vector X with the same 6 elements, following the rules illustrated in (1) that the columns in X are rearranged into one column. The column vector is the corresponding RB allocation vector.


## 2.3. System Bit-Rate Revenue

Bit-rate capacity is a key feature to the performance of future wideband PSN rich-content services. The typical aim of the resource allocation scheme is to maximize the total bit-rate capacity in the traditional cellular. Hence, in this paper we use the achievable bit-rate capacity of all PSUs as the C-RAN based PSN system’s revenue. This section analyzes the characteristics of the wireless fading channel to derive the outage probability of the system, based on which the achievable bit-rate capacity of a PSU in unit bandwidth can be resolved. Finally, the achievable PSU bit-rate per unit bandwidth is defined to represent the system revenue.LetP
m
t denote the transmit power of RRH b
m, G
m
a the antenna gain, and P
n
m
r the signal power received by u
n from RRH b
m. The fading channel is characterized by a matrix H
n
m, which is composed of 3 parts: path loss H
n
m
d, slow fading H
s, and fast fading H
n
f. H
n
m can be expressed by (2)
H
n
m
=
H
n
m
d
·
H
s
·
H
n
f
,where H
n
m
d
=
d
n
m
-
α, d
n
m is the physical distance between PSU u
n and RRH b
m, and α is the path loss exponent. Slow fading H
s
=
e
s, where S
~
N
μ
s
,
σ
2
2; that is, H
s follows lognormal distribution, and the Probability Distribution Function (PDF) is given in (3)
f
H
s
s
=
1
s
σ
2
π
e
-
ln
⁡
s
-
μ
s
2
/
2
σ
s
2
,
s
>
0
,
0
,
s
≤
0
.Assume that the PSU uses Maximal Ratio Combining (MRC) scheme to achieve full diversity gain, and the fast fadingH
n
f can be calculated by (4)
H
n
f
=
∑
l
=
1
L
n
h
n
l
2
,where h
n
l is the fast fading diversity gain from the lth antenna of PSU and h
n
l can be modeled as a random variable following standard normal distribution, that is, h
n
l
~
N
(
0,1
). L
n is the number of antennas in the PSU u
n. If l
≥
2, H
n
f
~
Γ
(
L
n
,
1
), and the PDF is given by (5)
f
H
n
f
v
=
v
L
n
-
1
e
-
v
L
n
-
1
!
,
v
>
0
,
0
,
v
≤
0then the received power of UEu
n from RRH b
m, P
n
m
r is given in (6)
P
n
m
r
=
P
m
t
G
m
a
H
n
m
=
P
m
t
G
m
a
H
s
H
n
f
d
n
m
-
α
.Supposing the threshold of the received power guaranteeing the basic communication service isT
r, the outage probability of PSU u
n to access RRH b
m at a distance d can be written as(7)
Pr
⁡
P
n
m
r
<
T
r
=
Pr
⁡
H
s
H
n
f
<
T
r
d
n
m
α
P
m
t
G
m
a
.In this paper, we take the impacts of two different scales of fading into consideration, which results in an outage probability resolving problem in elaborately modeled fading channel. Letβ
n
m
=
d
n
m
α
/
P
m
t
G
m
a, because H
s and H
n
f are independently and identically distributed; then(8)
Pr
⁡
H
s
H
n
f
<
T
r
γ
n
m
=
∫
0
+
∞
∫
0
T
r
β
n
m
/
s
f
H
s
s
f
H
n
f
v
d
v
d
s
=
1
-
∫
0
+
∞
f
H
s
s
∫
T
r
β
n
m
/
s
+
∞
f
H
n
f
v
d
v
d
s
.The cumulative distribution function of a gamma distributed variable with scale parameter being 1 can be written asγ
a
,
b
=
∫
b
+
∞
z
a
-
1
e
-
z
d
z, so the integral term of the slow fading can be written as(9)
∫
T
r
β
n
m
/
s
+
∞
f
H
n
f
v
d
v
=
∫
T
r
β
n
m
/
s
+
∞
v
L
n
-
1
e
-
v
L
n
-
1
!
d
v
=
γ
L
n
,
T
r
β
n
m
/
s
Γ
L
n
.Substituting (9) into (7), the outage probability of PSU u
n to access RRH b
m at a distance d can be rewritten as(10)
Pr
⁡
P
n
m
r
<
T
r
=
1
-
∫
0
+
∞
1
s
σ
2
π
γ
L
n
,
T
r
β
n
m
/
s
Γ
L
n
e
-
ln
⁡
s
-
μ
s
2
/
2
σ
s
2
d
s
.Then we can use the Gauss-Hermite quadrature to solve the numerical result of (10). Next, we are to derive the achievable bandwidth efficiency c
n
m of PSU u
n served by RRH b
m. Firstly, according to (10), the PDF of SNR is(11)
f
S
N
R
T
r
=
∂
Pr
⁡
T
r
>
P
n
m
r
∂
T
r
=
∑
k
=
1
k
H
A
k
H
π
Γ
L
n
∂
γ
L
n
,
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
∂
T
r
.Asγ
(
a
,
b
) is used to define CDF and its infinity integral is convergent, according to the derivation rule of the uncertain limit integral, we have(12)
∂
γ
L
n
,
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
∂
T
r
=
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
L
n
·
T
r
L
n
-
1
e
-
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
.The PDF of SNR in (12) can be rewritten as(13)
f
S
N
R
T
r
=
∑
k
=
1
k
H
A
k
H
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
L
n
π
Γ
L
n
·
T
r
L
n
-
1
e
-
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
.Let random variablec
n
m
=
log
2
⁡
1
+
T
r
/
N
0 denote the bit-rate capacity per unit bandwidth of PSU u
n served by RRH b
m, in which N
0 is the average power of Gauss white noise. The expectation of c
n
m, μ
n
m
c can be written as(14)
μ
n
m
c
=
E
c
n
m
=
∫
0
+
∞
f
S
N
R
T
r
l
o
g
2
1
+
T
r
N
0
d
T
r
.Then (14) can be rewritten as(15)
μ
n
m
c
=
∑
k
=
1
k
H
A
k
H
e
-
L
n
2
σ
s
ω
k
H
+
μ
s
β
n
m
L
n
π
Γ
L
n
·
∫
0
+
∞
e
-
T
r
β
n
m
e
-
2
σ
s
ω
k
H
+
μ
s
T
r
L
n
-
1
l
o
g
2
1
+
T
r
N
0
d
T
r
.Then we can adopt the Gauss-Laguerre quadrature to solve the numerical result of (15). Based on (15), we give the definition of the expected revenue vector in C-RAN based PSN.Definition 2 (expected revenue vector).
LetR
∈
R
M
N
=
r
i
M
N. If (16) holds(16)
r
m
-
1
·
N
+
n
=
μ
n
m
c
,where i
=
m
-
1
·
N
+
n, then r
m
-
1
·
N
+
n is the average bit-rate capacity of PSU u
n in unit bandwidth served by RRH b
m, and R is called theexpected revenue vector of the system.In addition, the variance ofc
n
m denoted as σ
n
m
c
2 is(17)
σ
n
m
c
2
=
D
c
n
m
=
E
c
n
m
2
-
μ
n
m
c
2
=
∫
0
+
∞
f
S
N
R
T
r
l
o
g
2
1
+
T
r
N
0
2
d
T
r
-
μ
n
m
c
2
.The correlation coefficients ofc
n
m and c
n
′
m
′, ρ
n
m
,
n
′
m
′
c, is (18)
ρ
n
m
,
n
′
m
′
c
=
E
c
n
m
·
c
n
′
m
′
-
μ
n
m
c
μ
n
′
m
′
c
σ
n
m
c
σ
n
′
m
′
c
.As complete joint transmission technology is adopted in C-RAN and a PSU can be served by multiple RRHs simultaneously, in the case ofm
=
m
′ and n
=
n
′, ρ
n
m
,
n
′
m
′
c
=
1 and in other cases, ρ
n
m
,
n
′
m
′
c
=
0.


## 2.4. Resource Allocation Problem Formulation

This paper takes into account both expected revenue of the system and PSU’s fairness when allocating the RBs in C-RAN based PSN. Hence, for the sake of maximizing the system performance, the following quadratic programming (QP) is derived:(19)
m
a
x
X
z
=
B
R
B
X
T
R
-
κ
B
R
B
2
X
T
Q
X
s
.
t
.
∑
i
=
1
M
N
x
i
=
B
W
B
R
B
X
=
x
i
M
N
,
x
i
∈
0,1
,
…
,
B
W
B
R
B
,where Q
=
q
i
j
M
N
×
N
M is a matrix relative to the covariance of the system revenue. The element q
i
j
=
ρ
n
m
,
n
′
m
′
c
σ
m
n
c
σ
m
′
n
′
c, where i
=
m
-
1
·
N
+
r and j
=
m
′
-
1
·
N
+
n
′. It is noticed that the optimization problem aims at maximizing the system performance, where B
R
B
X
T
R stands for the expectation of the bit-rate capacity, that is, the average revenue of the radio access system with a RB allocation scheme X. Based on the definition of Q, the second term (
B
R
B
)
2
X
T
Q
X stands for the variance of the system performance. If the parameter κ
→
0, the model is inclined to allocate more resources to PSUs contributing more revenue to the system, which means poor fairness of PSUs. If κ increases, the model will care more about the allocation fairness of PSUs.Because of the integer decision variables of PSU, when having a large amount of PSU-RRH associations when disaster occurs, the time complexity of solving this NP problem will increase distinctly. Hence, this paper proposes a corresponding Generalized Bender’s Decomposition method on the basis of integer variable continuation, which satisfies the demand on efficiency of algorithm in PSN service.


## 3. GBD Based Resource Allocation Algorithm

### 3.1. Relaxation and Generalized Bender’s Decomposition

Firstly, relax problem (19) into
(20)
m
a
x
X
z
=
B
R
B
X
T
R
-
κ
B
R
B
2
X
T
Q
X
s
.
t
.
∑
i
=
1
M
N
x
i
=
B
W
B
R
B
X
=
x
i
M
N
,
x
i
∈
0
,
B
W
B
R
B
.It can be seen that (20) is a typical QP problem with continuous variables X after relaxing. Based on the definition of Q, it is easy to know Q is positive definite matrix. Therefore, the relaxed problem is a convex quadratic programming problem. However, this kind of problem is also hard to solve directly where there are a large number of quadratic variables. So in this paper, an algorithm based on Generalized Bender’s Decomposition is adopted to resolve the complex quadratic variables, resulting in a much simplified two-stage solving process.LetX in R
-
κ
B
R
B
Q
X be defined as X
≜
X
b. Then the other X can be taken as the main variable. As X
b is taken as an auxiliary variable, it can be regarded as a constant parameter in resolving main variable X. And (20) can be rewritten as(21)
m
a
x
X
B
R
B
R
-
κ
B
R
B
Q
X
b
T
X
s
.
t
.
B
R
B
e
T
X
=
B
W
X
=
x
i
M
N
,
x
i
∈
0
,
B
W
B
R
B
.Problem in (21) is called the slave-problem of GBD, and the dual of (21) can be written as(22)
m
i
n
ω
B
W
ω
s
.
t
.
ω
e
≥
R
-
κ
B
R
B
Q
X
b
.From (22), it can be seen that due to the limit of the total bandwidth resources in the C-RAN based PSN, the main variable X conforms an equality constraint. Therefore the dual problem turned out to be a simple variable ω
∈
R, though (22) the optimal solution ω
∗ of the dual problem can be computed by simply finding the maximum element in vector R
-
κ
B
R
B
Q
X
b. Because there are only a limited number of optimal solutions on the dual problem, according to the strong duality theorem [24], there are also a limited number of optimal solutions on (20) and we have(23)
B
R
B
R
-
κ
B
R
B
Q
X
b
T
X
∗
=
B
W
ω
∗
.Letθ
≥
1 denote the current number of Bender’s Decomposition iteration steps. Equation (20) can be written as a two-stage optimization problem, composed of a Benders Decomposition slave-problem as (24) and a relaxed Benders Decomposition master-problem as (25):(24)
m
i
n
ω
B
W
ω
θ
s
.
t
.
ω
θ
e
≥
R
-
κ
B
R
B
Q
X
θ
b
(25)
m
a
x
X
θ
,
η
θ
η
θ
B
W
B
R
B
-
1
R
-
κ
B
R
B
Q
X
θ
T
R
-
κ
B
R
B
Q
X
θ
b
T
-
1
s
.
t
.
e
T
X
θ
=
B
W
B
R
B
-
1
X
θ
≥
0
η
θ
≤
ω
l
∗
∀
l
=
0,1
,
2
,
…
,
θ
-
1
,where X
θ
b
=
X
θ
-
1
∗ (X
θ
-
1
∗ is the optimal solution in (θ
-
1)th iteration).Lemma3 will prove the convergence of the above algorithm by demonstrating that the gap between the upper bound B
Uand lower bound B
L of the optimal objective function value z
∗ in (20) can be tightened, where B
U is the value of objective function in (25); B
L is the maximum value of problem in (24) in all the iterations, that is, the maximum element in B
W
ω
l
∣
l
=
1,2
,
…
,
θ.Lemma 3.
Each iteration in Generalized Bender’s Decomposition will narrow the gap between the upper boundB
U and the lower bound B
L of the value of objective function z
∗, where at θth iteration, B
U is z
θ
U
=
η
θ
∗
B
W
(
B
R
B
)
-
1
(
R
-
κ
B
R
B
Q
X
θ
∗
)
T and B
L is z
θ
L
=
max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗.Proof.
Firstly, we prove the upper bound ofz
∗ being z
θ
U. Based on the strong duality theorem, we know problem in (21) is equivalent to the problem in (26) according to (22):(26)
m
a
x
X
,
X
b
ω
∗
B
W
B
R
B
-
1
R
-
κ
B
R
B
Q
X
T
R
-
κ
B
R
B
Q
X
b
T
-
1
s
.
t
.
e
T
X
=
B
W
B
R
B
-
1
e
T
X
b
=
B
W
B
R
B
-
1
X
≥
0
,
X
b
≥
0
.
So with the optimal solution of problem in (20) being X
∗, the value of the objective function is B
R
B
X
∗
T
R
-
κ
(
B
R
B
)
2
X
∗
T
Q
X
∗. As (25) is the relaxation of (26), there should be(27)
z
∗
=
B
R
B
X
∗
T
R
-
κ
B
R
B
2
X
∗
T
Q
X
∗
≤
z
θ
U
=
η
θ
∗
B
W
B
R
B
-
1
R
-
κ
B
R
B
Q
X
θ
∗
T
R
-
κ
B
R
B
Q
X
θ
-
1
∗
T
-
1
,where η
θ
∗
,
X
θ
∗ is the optimal solution to question in (25). Therefore, the upper bound of the optimal solution B
U is z
θ
U.
Then, we prove the lower bound ofz
∗is z
θ
L. Because of the asymmetry in constraints of two dual problems, ω
t
∗ can be bounded or unbounded. If ω
t
∗
=
-
∞, ∀
l
∈
1
,
θ, ∃
z
θ
L
=
max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗
=
-
∞. In this case, the proposition that the bound of z
∗is z
θ
L holds. If ω
t
∗
>
-
∞, let B
W
ω
l
∗
=
max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗. Suppose z
θ
L
>
z
∗, and according to the above assumptions and strong duality properties, there should be an X
′ that conforms the following constraint:(28)
B
W
ω
l
~
∗
=
B
R
B
R
-
κ
B
R
B
Q
X
′
T
X
′
>
z
∗
=
B
R
B
X
∗
T
R
-
κ
B
R
B
2
X
∗
T
Q
X
∗
.Equation (28) indicates that X
′ makes the objective function get a larger value to the objective function, which conflicts with the precondition that X
∗ is the optimal solution of (20). Therefore, z
θ
L
=
max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗ is the lower bound of the value to the problem in (19).According to Lemma3, the system can find the optimal solution of problem (20), as B
U
-
B
L
=
0. Hence, the relaxation problem can be solved by Algorithm 1, and the specific solution is as follows: firstly, in the first iteration, that is, θ
=
1, the total system performance is greater than 0. According to the duality property, let X
0
b
=
0 and ω
0
∗
=
δ, where δ indicates a great enough value. These preconditions will ensure (25) can be feasibly constrained and the solution (
X
1
∗
,
η
1
∗
) on the master-problem in (25) can be resolved. Then let X
1
b
=
X
1
∗ and solve the slave-problem in (24). As slave-problem in (24) is a Linear Programming (LP), the result B
W
ω
1
∗ should be an extreme point in the feasible domain of the problem. Afterwards, let iterations plus 1, and go on with the iterations to obtain an X
θ
∗, until B
U
-
B
L
=
0, which means the gap between the upper bound and lower bound is narrowed to 0. The extreme point corresponds to the optimal solution to the problem. The Generalized Bender’s Decomposition algorithm needs to obtain the channel information from all PSUs to construct a system revenue matrix, so it is a centralized algorithm and it is suitable to perform the system like C-RAN based PSN, which pools all resources in a computing center.Algorithm 1:Generalized bender’s decomposition-based resource allocation algorithm to solve relaxed problem (20).
(
1) Initialization: θ
=
1, X
0
b
=
X
0
∗
=
0, ω
0
∗
=
δ, where δ is big enough.
(2) Repeat:
(3) Work out (25) to obtain optimal solution (
X
θ
∗
,
η
θ
∗
), and compute the upper bound
η
θ
∗
B
W
(
B
R
B
)
-
1
(
R
-
κ
B
R
B
Q
X
θ
∗
)
T
(
(
R
-
κ
B
R
B
Q
X
θ
-
1
∗
)
T
)
-
1
(4) X
θ
b
=
X
θ
∗
(5) Work out (24) to obtain ω
θ
∗, and compute the lower bound B
L
=
m
a
x
1
≤
l
≤
θ
B
W
ω
l
∗
(6) θ
=
θ
+
1
(7) Until B
U
-
B
L
=
0
(8) Return X
∗
=
X
θ
-
1
∗ as the optimal solution to problem (20), and compute the value
of the objective functionz
∗ by (24).The proposed GBD algorithm takes the difference betweenB
L and B
U as the criteria to judge the termination of the iteration. When the difference between B
L and B
U becomes 0, the whole algorithm terminates and the optimal solution to the problem in (19) is retrieved. The convergence of the algorithm will be proved by Theorem 4.Theorem 4.
The Generalized Bender’s Decomposition-based Algorithm1 converges to an optimal solution after finite iterations.Proof.
As an optimization problem with continuous variables and linear constraints [24], there exists a polyhedral convex cone Ω to make problems in (24) and (25) equivalent to(29)
m
a
x
X
θ
,
η
θ
η
θ
B
W
B
R
B
-
1
R
-
κ
B
R
B
Q
X
θ
T
R
-
κ
B
R
B
Q
X
θ
b
T
-
1
s.t.
e
T
X
θ
=
B
W
B
R
B
-
1
X
θ
≥
0
X
θ
,
η
θ
∈
Ω
,where the convex cone Ω is composed of finite radials along with extreme directions. In each iteration, the set of (
X
,
η
) in (25) will be tighten eventually, because a new radial will be added as a new extreme directions to refine the solution region; namely, η
θ
≤
ω
l
∗. In addition, it is considered that Ω is a convex hull composed of finite radials in extreme directions, and the newly introduced radial is different from the existing ones, so the Ω, which is determined by a complete set of constraints, can be obtained after finite iterations. This suggests that the optimal resource allocation vector X
∗ and the value of the objective function in (24), that is, the upper bound B
U, can be obtained after finite iterations. So the optimal objective function value z
∗ of relaxed problem (20) can also be obtained after finite iterations. Because the sequence {
z
l
U
,
l
=
1,2
,
3
,
…
,
θ
} is not increasing, z
∗
=
B
U
=
z
θ
U can be obtained after Ω is completely determined by the constraints η
θ
≤
ω
l
∗, ∀
l
=
0,1
,
2
,
…
,
θ. Additionally, due to z
θ
L
=
max
1
≤
l
≤
θ
⁡
{
B
W
ω
l
∗
}, the sequence {
z
l
L
,
l
=
1,2
,
3
,
…
,
θ
} is nondecreasing. After retrieving X
∗ for the problem in (25), we have z
∗
=
B
U
=
z
θ
L. According to the properties of the two sequences, terminated condition B
U
-
B
L
=
0 can be satisfied and the global optimal solution to the problem (20) can be obtained after finite iterations.


### 3.2. Feasible Pump (FP)

GBD algorithm can solve the solution of relaxation problem (20). Nevertheless, the vector X
θ
∗ solved by each iteration is not the integer vector, and it is not a feasible solution for problem (19). Therefore, it needs to find the actual feasible integer vector solution. There is a kind of simple method to find the integer vector solution; that is, the general vector solution X
θ
∗ is taken as the starting point to look for its nearest integer vector solution in the solution space. Article [22] proposes a kind of FP way which was taken as the standard to look for the integer vector solution. Specifically, the calculation x
~
i
=
[
x
i
∗
] is carried on each element x
i
∗ in the optimal solution of θth iteration in the relaxation problem (20), where [
·
] signifies that the nearest integer is taken for the scalar. So the new integer vector X
~
θ
=
(
x
~
i
)
M
N is obtained. The function Δ
(
·
) is defined as the sum of L
1 norm distance of various elements between a general vector and an integer vector; then(30)
Δ
X
θ
∗
,
X
~
θ
=
∑
i
=
1
M
N
x
i
∗
-
x
~
i
.The principle of FP adopts a heuristic way to find the feasible integer solutionX
~
θ. The determination standard of FP is that there exists a certain point X
θ
′
∗ in the general feasible region after relaxation and this point meets Δ
(
X
θ
′
∗
,
X
~
θ
)
=
0. In this case, X
θ
′
∗ is the integer vector and meets X
θ
′
∗
=
X
~
θ. Aiming at the relaxed problem (20), the FP standard is equivalent to the following minimum optimization problem:(31)
m
i
n
X
θ
Δ
X
θ
,
X
~
θ
=
∑
i
=
1
M
N
x
i
-
x
~
i
∑
i
=
1
M
N
x
i
=
B
W
B
R
B
X
θ
=
x
i
M
N
,
x
i
∈
0
,
B
W
B
R
B
.It is clearly observed that ifX
θ
=
X
~
θ exists in the feasible region, then Δ
(
X
θ
,
X
~
θ
)
=
0. This is equivalent to a fact that X
~
θ
=
[
X
θ
∗
] is a feasible solution. The entire execution flow of FP is as follows. Initially, optimal solution X
θ
∗, which was obtained by the relaxed problem (20), carried on [
·
] operator to obtain the initial integer solutions X
~
θ, and X
~
θ may not be the feasible integer vector solution. If X
~
θ is not the feasible solution, X
~
θ is fixed, and then the general vector solution closest to the L
1 norm distance of X
~
θ is looked for in the feasible region of relaxation. This process is called as a Pumping Cycling. Afterwards, FP standard (i.e., whether the norm distance is 0) was used to verify this solution. If the norm distance is equal to 0, the solution is X
θ
′
∗. Otherwise, operator [
·
] is carried on the newly obtained general vector solution to update X
~
θ and the Pumping Cycling iteration is continually carried on until X
θ
′
∗ is finally found.


### 3.3. OFDM RBs Allocation Algorithm Based on GBD and FP

Thus, this paper proposes the allocation algorithm on the basis of taking the OFDM RB as basic allocated unit, which is shown in Algorithm2. The characteristic of this algorithm is that, firstly, the original allocation problem with integer RB is simplified by relaxing into one with continuous variable. And GBD method is used to solve this relaxed problem in each iteration. Then, the FP-based distance criterion is used to find the feasible integer solution. Afterwards, terminated condition 0
≤
B
U
-
B
L
≤
τ is used to judge whether this solution is the acceptable approximate optimal solution.Algorithm 2:Generalized bender’s decomposition and FP-based RB allocation algorithm to solve problem (23).
(
1) Relax problem (19) into problem (20)
(2) Initialization: θ
=
1, X
0
b
=
X
0
∗
=
0, ω
0
∗
=
δ, where δ is big enough.
(3) Repeat:
(4) By Algorithm 1, decompose the problem (20) into master problem (25) and slave problem (24).
(5) Work out (25) to obtain optimal solution (
X
θ
∗
,
η
θ
∗
), and compute the upper bound
η
θ
∗
B
W
(
B
R
B
)
-
1
(
R
-
κ
B
R
B
Q
X
θ
∗
)
T
(
(
R
-
κ
B
R
B
Q
X
θ
-
1
∗
)
T
)
-
1
(6) Let X
~
θ
=
[
X
θ
∗
], by FP standard expressed by (31) to find the feasible integer solution X
θ
′
∗, and then X
θ
b
=
X
θ
∗
(7) Work out (24) to obtain ω
θ
∗, and compute the lower bound B
L
=
m
a
x
1
≤
l
≤
θ
B
W
ω
l
∗
(8) θ
=
θ
+
1
(9) Until B
U
-
B
L
=
0
(10) Return X
∗
=
X
θ
-
1
∗ as the approximate optimum solution to problem (19), and compute the value
of the objective functionz
∗ by (24).


### 3.4. Trade-Off between Performance and Convergence Time

It can be seen that0
≤
B
U
-
B
L
≤
τ is used as the terminated condition of Algorithm 2. Therefore the value of τ will determine the accuracy of approximately-optimal solution. And it is not surprising that when τ is small the accuracy of the solution is higher, however with a greater computing time. Hence we use Theorem 5 to illustrate the proper value of τ as a reference to the implemented system.Theorem 5.
As for problem (19) and Algorithm 2, the system performance is at most τ
<
1
/
ϖ less than the maximum system performance when τ
=
0 (the operator · signifies that the nearest integer is taken downward.), and as τ
<
1
/
ϖ the difference between the system performance of Algorithm 2 and the maximum one is 0 where ϖ is a constant that is greater than 0 and can be expressed as(32)
ϖ
=
r
i
′
r
i
B
R
B
=
q
i
j
′
q
i
j
B
R
B
2
,
∀
i
=
1,2
…
,
M
N
,
∀
j
=
1,2
…
,
M
N
,where r
i
′, ∀
i
=
1,2
…
,
M
N and q
i
j
′, ∀
i
,
j
=
1,2
…
,
M
N are all integersProof.
For problem (19), there exist B
L
=
Z
(
X
′
) and z
∗
≤
B
U; hence, the difference between the maximum system performance and the actual system performance of Algorithm 2 is(33)
z
∗
-
Z
X
′
≤
B
U
-
B
L
≤
τ
.
Becauseϖ is an integer that is greater than 0, then(34)
ϖ
z
∗
-
Z
X
′
=
ϖ
B
R
B
∑
i
=
1
M
N
x
i
∗
r
i
-
∑
j
=
1
M
N
∑
i
=
1
M
N
B
R
B
x
i
∗
q
i
j
x
j
∗
-
∑
i
=
1
M
N
x
i
′
r
i
-
∑
j
=
1
M
N
∑
i
=
1
M
N
B
R
B
x
i
′
q
i
j
x
j
′
=
∑
i
=
1
M
N
x
i
∗
-
x
i
′
r
i
′
-
∑
j
=
1
M
N
∑
i
=
1
M
N
x
i
∗
x
j
∗
-
x
i
′
x
j
′
q
i
j
′
≤
ϖ
τ
.
Sincer
i
′, q
i
j
′, and x
i are all the integers, there exists(35)
z
∗
-
Z
X
′
≤
1
ϖ
ϖ
τ
.
Because the operator· signifies that the nearest integer is taken downward, when ϖ
τ
=
0, namely, τ
<
1
/
ϖ, then z
∗
=
Z
(
X
′
). In this case, the result obtained from Algorithm 2 is the original approximately-optimal solution on the integer programming (19).


## 3.1. Relaxation and Generalized Bender’s Decomposition

Firstly, relax problem (19) into
(20)
m
a
x
X
z
=
B
R
B
X
T
R
-
κ
B
R
B
2
X
T
Q
X
s
.
t
.
∑
i
=
1
M
N
x
i
=
B
W
B
R
B
X
=
x
i
M
N
,
x
i
∈
0
,
B
W
B
R
B
.It can be seen that (20) is a typical QP problem with continuous variables X after relaxing. Based on the definition of Q, it is easy to know Q is positive definite matrix. Therefore, the relaxed problem is a convex quadratic programming problem. However, this kind of problem is also hard to solve directly where there are a large number of quadratic variables. So in this paper, an algorithm based on Generalized Bender’s Decomposition is adopted to resolve the complex quadratic variables, resulting in a much simplified two-stage solving process.LetX in R
-
κ
B
R
B
Q
X be defined as X
≜
X
b. Then the other X can be taken as the main variable. As X
b is taken as an auxiliary variable, it can be regarded as a constant parameter in resolving main variable X. And (20) can be rewritten as(21)
m
a
x
X
B
R
B
R
-
κ
B
R
B
Q
X
b
T
X
s
.
t
.
B
R
B
e
T
X
=
B
W
X
=
x
i
M
N
,
x
i
∈
0
,
B
W
B
R
B
.Problem in (21) is called the slave-problem of GBD, and the dual of (21) can be written as(22)
m
i
n
ω
B
W
ω
s
.
t
.
ω
e
≥
R
-
κ
B
R
B
Q
X
b
.From (22), it can be seen that due to the limit of the total bandwidth resources in the C-RAN based PSN, the main variable X conforms an equality constraint. Therefore the dual problem turned out to be a simple variable ω
∈
R, though (22) the optimal solution ω
∗ of the dual problem can be computed by simply finding the maximum element in vector R
-
κ
B
R
B
Q
X
b. Because there are only a limited number of optimal solutions on the dual problem, according to the strong duality theorem [24], there are also a limited number of optimal solutions on (20) and we have(23)
B
R
B
R
-
κ
B
R
B
Q
X
b
T
X
∗
=
B
W
ω
∗
.Letθ
≥
1 denote the current number of Bender’s Decomposition iteration steps. Equation (20) can be written as a two-stage optimization problem, composed of a Benders Decomposition slave-problem as (24) and a relaxed Benders Decomposition master-problem as (25):(24)
m
i
n
ω
B
W
ω
θ
s
.
t
.
ω
θ
e
≥
R
-
κ
B
R
B
Q
X
θ
b
(25)
m
a
x
X
θ
,
η
θ
η
θ
B
W
B
R
B
-
1
R
-
κ
B
R
B
Q
X
θ
T
R
-
κ
B
R
B
Q
X
θ
b
T
-
1
s
.
t
.
e
T
X
θ
=
B
W
B
R
B
-
1
X
θ
≥
0
η
θ
≤
ω
l
∗
∀
l
=
0,1
,
2
,
…
,
θ
-
1
,where X
θ
b
=
X
θ
-
1
∗ (X
θ
-
1
∗ is the optimal solution in (θ
-
1)th iteration).Lemma3 will prove the convergence of the above algorithm by demonstrating that the gap between the upper bound B
Uand lower bound B
L of the optimal objective function value z
∗ in (20) can be tightened, where B
U is the value of objective function in (25); B
L is the maximum value of problem in (24) in all the iterations, that is, the maximum element in B
W
ω
l
∣
l
=
1,2
,
…
,
θ.Lemma 3.
Each iteration in Generalized Bender’s Decomposition will narrow the gap between the upper boundB
U and the lower bound B
L of the value of objective function z
∗, where at θth iteration, B
U is z
θ
U
=
η
θ
∗
B
W
(
B
R
B
)
-
1
(
R
-
κ
B
R
B
Q
X
θ
∗
)
T and B
L is z
θ
L
=
max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗.Proof.
Firstly, we prove the upper bound ofz
∗ being z
θ
U. Based on the strong duality theorem, we know problem in (21) is equivalent to the problem in (26) according to (22):(26)
m
a
x
X
,
X
b
ω
∗
B
W
B
R
B
-
1
R
-
κ
B
R
B
Q
X
T
R
-
κ
B
R
B
Q
X
b
T
-
1
s
.
t
.
e
T
X
=
B
W
B
R
B
-
1
e
T
X
b
=
B
W
B
R
B
-
1
X
≥
0
,
X
b
≥
0
.
So with the optimal solution of problem in (20) being X
∗, the value of the objective function is B
R
B
X
∗
T
R
-
κ
(
B
R
B
)
2
X
∗
T
Q
X
∗. As (25) is the relaxation of (26), there should be(27)
z
∗
=
B
R
B
X
∗
T
R
-
κ
B
R
B
2
X
∗
T
Q
X
∗
≤
z
θ
U
=
η
θ
∗
B
W
B
R
B
-
1
R
-
κ
B
R
B
Q
X
θ
∗
T
R
-
κ
B
R
B
Q
X
θ
-
1
∗
T
-
1
,where η
θ
∗
,
X
θ
∗ is the optimal solution to question in (25). Therefore, the upper bound of the optimal solution B
U is z
θ
U.
Then, we prove the lower bound ofz
∗is z
θ
L. Because of the asymmetry in constraints of two dual problems, ω
t
∗ can be bounded or unbounded. If ω
t
∗
=
-
∞, ∀
l
∈
1
,
θ, ∃
z
θ
L
=
max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗
=
-
∞. In this case, the proposition that the bound of z
∗is z
θ
L holds. If ω
t
∗
>
-
∞, let B
W
ω
l
∗
=
max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗. Suppose z
θ
L
>
z
∗, and according to the above assumptions and strong duality properties, there should be an X
′ that conforms the following constraint:(28)
B
W
ω
l
~
∗
=
B
R
B
R
-
κ
B
R
B
Q
X
′
T
X
′
>
z
∗
=
B
R
B
X
∗
T
R
-
κ
B
R
B
2
X
∗
T
Q
X
∗
.Equation (28) indicates that X
′ makes the objective function get a larger value to the objective function, which conflicts with the precondition that X
∗ is the optimal solution of (20). Therefore, z
θ
L
=
max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗ is the lower bound of the value to the problem in (19).According to Lemma3, the system can find the optimal solution of problem (20), as B
U
-
B
L
=
0. Hence, the relaxation problem can be solved by Algorithm 1, and the specific solution is as follows: firstly, in the first iteration, that is, θ
=
1, the total system performance is greater than 0. According to the duality property, let X
0
b
=
0 and ω
0
∗
=
δ, where δ indicates a great enough value. These preconditions will ensure (25) can be feasibly constrained and the solution (
X
1
∗
,
η
1
∗
) on the master-problem in (25) can be resolved. Then let X
1
b
=
X
1
∗ and solve the slave-problem in (24). As slave-problem in (24) is a Linear Programming (LP), the result B
W
ω
1
∗ should be an extreme point in the feasible domain of the problem. Afterwards, let iterations plus 1, and go on with the iterations to obtain an X
θ
∗, until B
U
-
B
L
=
0, which means the gap between the upper bound and lower bound is narrowed to 0. The extreme point corresponds to the optimal solution to the problem. The Generalized Bender’s Decomposition algorithm needs to obtain the channel information from all PSUs to construct a system revenue matrix, so it is a centralized algorithm and it is suitable to perform the system like C-RAN based PSN, which pools all resources in a computing center.Algorithm 1:Generalized bender’s decomposition-based resource allocation algorithm to solve relaxed problem (20).
(
1) Initialization: θ
=
1, X
0
b
=
X
0
∗
=
0, ω
0
∗
=
δ, where δ is big enough.
(2) Repeat:
(3) Work out (25) to obtain optimal solution (
X
θ
∗
,
η
θ
∗
), and compute the upper bound
η
θ
∗
B
W
(
B
R
B
)
-
1
(
R
-
κ
B
R
B
Q
X
θ
∗
)
T
(
(
R
-
κ
B
R
B
Q
X
θ
-
1
∗
)
T
)
-
1
(4) X
θ
b
=
X
θ
∗
(5) Work out (24) to obtain ω
θ
∗, and compute the lower bound B
L
=
m
a
x
1
≤
l
≤
θ
B
W
ω
l
∗
(6) θ
=
θ
+
1
(7) Until B
U
-
B
L
=
0
(8) Return X
∗
=
X
θ
-
1
∗ as the optimal solution to problem (20), and compute the value
of the objective functionz
∗ by (24).The proposed GBD algorithm takes the difference betweenB
L and B
U as the criteria to judge the termination of the iteration. When the difference between B
L and B
U becomes 0, the whole algorithm terminates and the optimal solution to the problem in (19) is retrieved. The convergence of the algorithm will be proved by Theorem 4.Theorem 4.
The Generalized Bender’s Decomposition-based Algorithm1 converges to an optimal solution after finite iterations.Proof.
As an optimization problem with continuous variables and linear constraints [24], there exists a polyhedral convex cone Ω to make problems in (24) and (25) equivalent to(29)
m
a
x
X
θ
,
η
θ
η
θ
B
W
B
R
B
-
1
R
-
κ
B
R
B
Q
X
θ
T
R
-
κ
B
R
B
Q
X
θ
b
T
-
1
s.t.
e
T
X
θ
=
B
W
B
R
B
-
1
X
θ
≥
0
X
θ
,
η
θ
∈
Ω
,where the convex cone Ω is composed of finite radials along with extreme directions. In each iteration, the set of (
X
,
η
) in (25) will be tighten eventually, because a new radial will be added as a new extreme directions to refine the solution region; namely, η
θ
≤
ω
l
∗. In addition, it is considered that Ω is a convex hull composed of finite radials in extreme directions, and the newly introduced radial is different from the existing ones, so the Ω, which is determined by a complete set of constraints, can be obtained after finite iterations. This suggests that the optimal resource allocation vector X
∗ and the value of the objective function in (24), that is, the upper bound B
U, can be obtained after finite iterations. So the optimal objective function value z
∗ of relaxed problem (20) can also be obtained after finite iterations. Because the sequence {
z
l
U
,
l
=
1,2
,
3
,
…
,
θ
} is not increasing, z
∗
=
B
U
=
z
θ
U can be obtained after Ω is completely determined by the constraints η
θ
≤
ω
l
∗, ∀
l
=
0,1
,
2
,
…
,
θ. Additionally, due to z
θ
L
=
max
1
≤
l
≤
θ
⁡
{
B
W
ω
l
∗
}, the sequence {
z
l
L
,
l
=
1,2
,
3
,
…
,
θ
} is nondecreasing. After retrieving X
∗ for the problem in (25), we have z
∗
=
B
U
=
z
θ
L. According to the properties of the two sequences, terminated condition B
U
-
B
L
=
0 can be satisfied and the global optimal solution to the problem (20) can be obtained after finite iterations.


## 3.2. Feasible Pump (FP)

GBD algorithm can solve the solution of relaxation problem (20). Nevertheless, the vector X
θ
∗ solved by each iteration is not the integer vector, and it is not a feasible solution for problem (19). Therefore, it needs to find the actual feasible integer vector solution. There is a kind of simple method to find the integer vector solution; that is, the general vector solution X
θ
∗ is taken as the starting point to look for its nearest integer vector solution in the solution space. Article [22] proposes a kind of FP way which was taken as the standard to look for the integer vector solution. Specifically, the calculation x
~
i
=
[
x
i
∗
] is carried on each element x
i
∗ in the optimal solution of θth iteration in the relaxation problem (20), where [
·
] signifies that the nearest integer is taken for the scalar. So the new integer vector X
~
θ
=
(
x
~
i
)
M
N is obtained. The function Δ
(
·
) is defined as the sum of L
1 norm distance of various elements between a general vector and an integer vector; then(30)
Δ
X
θ
∗
,
X
~
θ
=
∑
i
=
1
M
N
x
i
∗
-
x
~
i
.The principle of FP adopts a heuristic way to find the feasible integer solutionX
~
θ. The determination standard of FP is that there exists a certain point X
θ
′
∗ in the general feasible region after relaxation and this point meets Δ
(
X
θ
′
∗
,
X
~
θ
)
=
0. In this case, X
θ
′
∗ is the integer vector and meets X
θ
′
∗
=
X
~
θ. Aiming at the relaxed problem (20), the FP standard is equivalent to the following minimum optimization problem:(31)
m
i
n
X
θ
Δ
X
θ
,
X
~
θ
=
∑
i
=
1
M
N
x
i
-
x
~
i
∑
i
=
1
M
N
x
i
=
B
W
B
R
B
X
θ
=
x
i
M
N
,
x
i
∈
0
,
B
W
B
R
B
.It is clearly observed that ifX
θ
=
X
~
θ exists in the feasible region, then Δ
(
X
θ
,
X
~
θ
)
=
0. This is equivalent to a fact that X
~
θ
=
[
X
θ
∗
] is a feasible solution. The entire execution flow of FP is as follows. Initially, optimal solution X
θ
∗, which was obtained by the relaxed problem (20), carried on [
·
] operator to obtain the initial integer solutions X
~
θ, and X
~
θ may not be the feasible integer vector solution. If X
~
θ is not the feasible solution, X
~
θ is fixed, and then the general vector solution closest to the L
1 norm distance of X
~
θ is looked for in the feasible region of relaxation. This process is called as a Pumping Cycling. Afterwards, FP standard (i.e., whether the norm distance is 0) was used to verify this solution. If the norm distance is equal to 0, the solution is X
θ
′
∗. Otherwise, operator [
·
] is carried on the newly obtained general vector solution to update X
~
θ and the Pumping Cycling iteration is continually carried on until X
θ
′
∗ is finally found.


## 3.3. OFDM RBs Allocation Algorithm Based on GBD and FP

Thus, this paper proposes the allocation algorithm on the basis of taking the OFDM RB as basic allocated unit, which is shown in Algorithm2. The characteristic of this algorithm is that, firstly, the original allocation problem with integer RB is simplified by relaxing into one with continuous variable. And GBD method is used to solve this relaxed problem in each iteration. Then, the FP-based distance criterion is used to find the feasible integer solution. Afterwards, terminated condition 0
≤
B
U
-
B
L
≤
τ is used to judge whether this solution is the acceptable approximate optimal solution.Algorithm 2:Generalized bender’s decomposition and FP-based RB allocation algorithm to solve problem (23).
(
1) Relax problem (19) into problem (20)
(2) Initialization: θ
=
1, X
0
b
=
X
0
∗
=
0, ω
0
∗
=
δ, where δ is big enough.
(3) Repeat:
(4) By Algorithm 1, decompose the problem (20) into master problem (25) and slave problem (24).
(5) Work out (25) to obtain optimal solution (
X
θ
∗
,
η
θ
∗
), and compute the upper bound
η
θ
∗
B
W
(
B
R
B
)
-
1
(
R
-
κ
B
R
B
Q
X
θ
∗
)
T
(
(
R
-
κ
B
R
B
Q
X
θ
-
1
∗
)
T
)
-
1
(6) Let X
~
θ
=
[
X
θ
∗
], by FP standard expressed by (31) to find the feasible integer solution X
θ
′
∗, and then X
θ
b
=
X
θ
∗
(7) Work out (24) to obtain ω
θ
∗, and compute the lower bound B
L
=
m
a
x
1
≤
l
≤
θ
B
W
ω
l
∗
(8) θ
=
θ
+
1
(9) Until B
U
-
B
L
=
0
(10) Return X
∗
=
X
θ
-
1
∗ as the approximate optimum solution to problem (19), and compute the value
of the objective functionz
∗ by (24).


## 3.4. Trade-Off between Performance and Convergence Time

It can be seen that0
≤
B
U
-
B
L
≤
τ is used as the terminated condition of Algorithm 2. Therefore the value of τ will determine the accuracy of approximately-optimal solution. And it is not surprising that when τ is small the accuracy of the solution is higher, however with a greater computing time. Hence we use Theorem 5 to illustrate the proper value of τ as a reference to the implemented system.Theorem 5.
As for problem (19) and Algorithm 2, the system performance is at most τ
<
1
/
ϖ less than the maximum system performance when τ
=
0 (the operator · signifies that the nearest integer is taken downward.), and as τ
<
1
/
ϖ the difference between the system performance of Algorithm 2 and the maximum one is 0 where ϖ is a constant that is greater than 0 and can be expressed as(32)
ϖ
=
r
i
′
r
i
B
R
B
=
q
i
j
′
q
i
j
B
R
B
2
,
∀
i
=
1,2
…
,
M
N
,
∀
j
=
1,2
…
,
M
N
,where r
i
′, ∀
i
=
1,2
…
,
M
N and q
i
j
′, ∀
i
,
j
=
1,2
…
,
M
N are all integersProof.
For problem (19), there exist B
L
=
Z
(
X
′
) and z
∗
≤
B
U; hence, the difference between the maximum system performance and the actual system performance of Algorithm 2 is(33)
z
∗
-
Z
X
′
≤
B
U
-
B
L
≤
τ
.
Becauseϖ is an integer that is greater than 0, then(34)
ϖ
z
∗
-
Z
X
′
=
ϖ
B
R
B
∑
i
=
1
M
N
x
i
∗
r
i
-
∑
j
=
1
M
N
∑
i
=
1
M
N
B
R
B
x
i
∗
q
i
j
x
j
∗
-
∑
i
=
1
M
N
x
i
′
r
i
-
∑
j
=
1
M
N
∑
i
=
1
M
N
B
R
B
x
i
′
q
i
j
x
j
′
=
∑
i
=
1
M
N
x
i
∗
-
x
i
′
r
i
′
-
∑
j
=
1
M
N
∑
i
=
1
M
N
x
i
∗
x
j
∗
-
x
i
′
x
j
′
q
i
j
′
≤
ϖ
τ
.
Sincer
i
′, q
i
j
′, and x
i are all the integers, there exists(35)
z
∗
-
Z
X
′
≤
1
ϖ
ϖ
τ
.
Because the operator· signifies that the nearest integer is taken downward, when ϖ
τ
=
0, namely, τ
<
1
/
ϖ, then z
∗
=
Z
(
X
′
). In this case, the result obtained from Algorithm 2 is the original approximately-optimal solution on the integer programming (19).


## 4. Simulation Results

This paper evaluates the performance from both C-RAN based PSN architecture and proposed GBD algorithm. The throughput and PSU’s allocation fairness in C-RAN based PSN are investigated in Section4.1. The convergence properties and computational time of the proposed GBD algorithm are investigated in Sections 4.2 and 4.3, respectively. In Section 4.4, the trade-off between the performance and the terminated parameter τ is discussed. We select CPLEX as the experimental solver and write the problem model and GBD and FP algorithm script into the CPLEX solver. The computational time evaluation is based on a Lenovo desktop with 3.7 GHz dual-core processors and 4 Gb of RAM. All corresponding results are averaged over 500 different simulation runs. The basic channel and radio parameters are shown in Table 1.Table 1
Simulation parameters.
Parameter
Value (unites)
Transmitting power of each RRHP
t
20 W
Antenna gainG
a
15 dBi
Slow fading meanμ
s
3 dB
Slow fading standard deviationσ
s
1.5 dB
Number of UE’s antennaL
2
Gauss-Laguerre phasek
L
5
Gauss Hermite phasek
N
5
Path loss exponentα
4.5
Bandwidth of each resource blockB
R
B
0.2 MHz
Fairness factorκ
0.3 and 0.6


### 4.1. Performance Evaluation on C-RAN Based PSN

Our experiment assumes a C-RAN based PSN architecture of 10 RRHs of 20 W transmitting power with a fixed position placed in a 2000 m by 2000 m area. Each RRH serves 20 PSUs. These PSUs are randomly placed in each run and satisfies that 50% of them have average SNRs lower than 3 dB. In the simulation a variable bandwidth value per RRH is assumed (5, 10, 15, 20) MHz in both downlink and uplink. These bandwidths per RRH are equivalent to 25, 50, 75, and 100 OFDM RBs, respectively. The fairness factor of Algorithm2  κ
=
0.3 and κ
=
0.6 is selected. On the base of the previous analysis, when κ is small, the allocator pursues to a high network performance revenue rather than PSU’s fairness of allocation. It is opposite when κ is large. This paper assumes all the RBs (Num. of R
R
H
s
∗
N
u
m. of RBs per RRH) can be allocated centrally without interference in the C-RAN based architecture because all the channel information can be collected by the allocator; the interference pair of RBs can be arranged to the users who are far away enough to avoid the signal interference. We choose LTE-based PSN architecture as comparison with a typical allocation algorithm Proportional Fair (PF) [25] and an improved one called PS which is dedicatedly proposed for the PSN service [12]. The interference between PSUs in LTE-based PSN can also be ignored by the interference notice signaling message that communicated on the LTE X2 interfaces. We compare C-RAN based PSN and LTE-based PSN from two perspectives: system total throughput and Jain’s Fairness Index (<1) [26]. Jain’s Fairness Index is used to measure the fairness among the PSUs. The ideal case of fairness is achieved when the index is equal to 1 reflecting all users receive equal resources while decreasing fairness is reflected with decreasing value of the index.From Figures3 and 4, we can see in C-RAN based PSN architecture the system total throughput with the case of κ
=
0.3 is better than κ
=
0.6 while Jain’s Fairness Index with the case of κ
=
0.6 is higher, which is consistent with the aim of the proposed algorithm discussed in Section 2.3. In the LTE-based PSN, PF can obtain a better throughput performance than PS while PS reveals better PSU’s allocation fairness. The results in LTE-based PSN are similar with the work [12]. This is because PS, which prioritizes the users with bad channel condition, is dedicatedly designed for the PSN situation with a considerable ratio of bad SNR users. PS scheduler provides a compromise in allocating the RBs among PSUs with good and bad channel conditions, which results in that the system throughput achieved using PS scheduler is lower than PF. From these two figures, it can be seen that the performance of C-RAN based PSN is commonly better than LTE based. Particularly, if considering the PSU’s allocating fairness less, the system total throughput in C-RAN based PSN of GBD scheduler with κ
=
0.3 is higher than in LTE-based PSN of PF scheduler by 19.17% with 20 MHz ∗ 10 RRHs. Meanwhile, average Jain’s Fairness Index in C-RAN based PSN of GBD scheduler with κ
=
0.6 is also higher than in LTE-based PSN of PF scheduler by 0.045. If considering the PSU’s allocating fairness more, the system total throughput in C-RAN based PSN of GBD scheduler with κ
=
0.6 is at most higher than in LTE-based PSN of PS scheduler by 12.79% and average Jain’s Fairness Index is also higher by 0.03. We find out that C-RAN based PSN has a better throughput performance than LTE-based without a reduction of Jain’s Fairness Index if having the same consideration on the PSU’s allocating fairness. The reason is that C-RAN based architecture owns the capability of scheduling available RBs globally, which brings out a more obvious advantage of user-on-demand allocating. Meanwhile, since introducing the fairness factor as an important part of objective function model, C-RAN based PSN with GBD algorithm can also obtain a good PSU’s allocating fairness. However, it can also be seen that Jain’s Fairness Index in C-RAN based PSN of GBD scheduler with κ
=
0.3 is lower than LTE-based with PS although the throughput is much better. This implies a suitable κ value can allow a well-balanced trade-off between the maximal throughput and the allocation fairness among each PSU.Figure 3
System total throughput versus total resources with C-RAN based and LTE-based PSN.Figure 4
Jain’s Fairness Index versus total resources with C-RAN based and LTE-based PSN.


### 4.2. Convergence of GBD and FP-Based RB Allocation Algorithm

In Section4.1, the performance of C-RAN based PSN with GBD scheduler has been investigated. Then we move on to the algorithm’s convergence and efficiency. Figure 5 shows the convergence of proposed Generalized Bender’s Decomposition and FP-based algorithm compared with one only on the basis of Bender’s Decomposition with no relaxation. We assume a C-RAN based PSN consisting of 10 RRHs and 60 PSUs. Firstly, this figure implies that difference between the upper bound and lower bound is tightened by Bender’s Decomposition so that an approximately-optimal solution of problem (19) can be obtained after finite iterations. This change is consistent with Lemma 3 and Theorem 4 in Section 3. And secondly, it can also be seen that the proposed algorithm needs 14 iterations to obtain the approximately- optimal solution of the system, which is less than the other one of only Bender’s Decomposition. The acceleration is brought by the relaxation to the original problem (19). We use continuation to deal with the integer variable and then find the feasible integer solution by FP whose converged speed is faster than the method that directly search for the integer solution in the regional feasible set constrained by max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗ in each iteration.Figure 5
Upper and lower bound value versus iteration step with different algorithms.Figure6 illustrates the convergence of proposed Generalized Bender’s Decomposition algorithm with different-sized network consisting of 10 RRHs × 50 PSUs, 10 RRHs × 60 PSUs, and 10 RRHs × 70 PSUs. It can be seen that the algorithms in any assumptions converge to the approximately-optimal solution quickly. The figure also implies that the iterations in large-sized network are less than a small-sized one. The reason is that when the RRH’s position and simulation area are assumed and PSUs are in large quantity, it is more likely to place more center users who are nearby the RRHs. Hence, the system performance in large-sized network is generally higher than it in small-sized one. Judging from the same upper bound the algorithm started from and analysis in Section 3, it can be concluded that the iterations to a great value of approximately-optimal solution in a large-sized network are less than to a small one in a small-sized network. One can conclude that the iteration of the proposed GBD and FP based-algorithm is more relevant to the achievable optimal solution rather than the size of the network. This result on convergence features the applicability of the proposed algorithm in the centralized scheduling system like C-RAN based PSN in this paper.Figure 6
Upper and lower bound value versus iteration step with different-sized networks.


### 4.3. Computational Time of GBD and FP-Based RB Allocation Algorithm

The average computational time of proposed GBD algorithm is expressed against the different-sized network in Figure7. We select Simplex, Barrier and Bender’s Decomposition with no relaxation for comparison. Simplex is a general method to search for the (approximately-) optimal solution of programming problem. Barrier is a commonly used way to solve QP problem. It is not surprising that the computational time needed in proposed GBD and FP-based algorithm is much less than that in Simplex and Barrier. And the time of Barrier and Simplex algorithms tends to increase in a nearly linear and exponential fashion, respectively, along with the network size while that of GBD algorithm has a more flatted one. Since the analysis on Figure 3, iterations of the proposed algorithm are less than that of one based on Bender’s Decomposition with no relaxation for an assumed network size. So the average computational of the proposed algorithm is least. It is reasonable that the average computational time of Simplex tends to increase in a nearly exponential fashion along with the network size. However the computational time of the proposed GBD algorithm increases in a more smooth fashion. The reason is that the computational time of Bender’s Decomposition depends on two factors: total iterations and the computing time in each iteration by the experimental desktop. The iterations decrease as the size of network increases as shown in Figure 6. But the experimental observation shows that the computing time in each iteration increases almost in a linear way along with the increased network size. Associated with the iteration steps, the average computational time of the proposed GBD and FP-based algorithm has a smoothly increasing fashion along the network size.Figure 7
Computational time versus size of C-RAN based PSN.The similar results are obtained from the perspective of the jitter of the computational time which is shown in Figure8. GBD converts the relaxed master QP problem into a dual problem as analyzed in Section 3.1 so that the jitter mainly depends on the experimental desktop performance rather than the solution-searching method in each iteration on which the Simplex and Barrier depends.Figure 8
Positive jitter of computational time versus size of C-RAN based PSN.


### 4.4. Trade-Off between Objective Function Value and Computational Time

Algorithm2 is also run with different terminated parameter τ. We assume a C-RAN based PSN network consisting of 10 RRHs and 60 PSUs. In Figure 9, the objective function value of the proposed algorithm is plotted against τ. It is not surprising to see that the objective function value degrades as the terminated parameter decreases. Moreover, the objective function value obtained is not sensitive to the value of τ  when it is small enough, namely, smaller than 100 in our instance, which is consistent with Theorem 5 in Section 3. And the degradations of the objective function value with each τ are also not greater than the value proposed by Theorem 5. It is easy to know the greater τ is, the less computation is time-consuming. Therefore we can select on-demand value of error tolerance τ that considers the trade-off between the computational time and the objective function value in the C-RAN based PSN system.Figure 9
Objective function value versus terminated parameterτ.


## 4.1. Performance Evaluation on C-RAN Based PSN

Our experiment assumes a C-RAN based PSN architecture of 10 RRHs of 20 W transmitting power with a fixed position placed in a 2000 m by 2000 m area. Each RRH serves 20 PSUs. These PSUs are randomly placed in each run and satisfies that 50% of them have average SNRs lower than 3 dB. In the simulation a variable bandwidth value per RRH is assumed (5, 10, 15, 20) MHz in both downlink and uplink. These bandwidths per RRH are equivalent to 25, 50, 75, and 100 OFDM RBs, respectively. The fairness factor of Algorithm2  κ
=
0.3 and κ
=
0.6 is selected. On the base of the previous analysis, when κ is small, the allocator pursues to a high network performance revenue rather than PSU’s fairness of allocation. It is opposite when κ is large. This paper assumes all the RBs (Num. of R
R
H
s
∗
N
u
m. of RBs per RRH) can be allocated centrally without interference in the C-RAN based architecture because all the channel information can be collected by the allocator; the interference pair of RBs can be arranged to the users who are far away enough to avoid the signal interference. We choose LTE-based PSN architecture as comparison with a typical allocation algorithm Proportional Fair (PF) [25] and an improved one called PS which is dedicatedly proposed for the PSN service [12]. The interference between PSUs in LTE-based PSN can also be ignored by the interference notice signaling message that communicated on the LTE X2 interfaces. We compare C-RAN based PSN and LTE-based PSN from two perspectives: system total throughput and Jain’s Fairness Index (<1) [26]. Jain’s Fairness Index is used to measure the fairness among the PSUs. The ideal case of fairness is achieved when the index is equal to 1 reflecting all users receive equal resources while decreasing fairness is reflected with decreasing value of the index.From Figures3 and 4, we can see in C-RAN based PSN architecture the system total throughput with the case of κ
=
0.3 is better than κ
=
0.6 while Jain’s Fairness Index with the case of κ
=
0.6 is higher, which is consistent with the aim of the proposed algorithm discussed in Section 2.3. In the LTE-based PSN, PF can obtain a better throughput performance than PS while PS reveals better PSU’s allocation fairness. The results in LTE-based PSN are similar with the work [12]. This is because PS, which prioritizes the users with bad channel condition, is dedicatedly designed for the PSN situation with a considerable ratio of bad SNR users. PS scheduler provides a compromise in allocating the RBs among PSUs with good and bad channel conditions, which results in that the system throughput achieved using PS scheduler is lower than PF. From these two figures, it can be seen that the performance of C-RAN based PSN is commonly better than LTE based. Particularly, if considering the PSU’s allocating fairness less, the system total throughput in C-RAN based PSN of GBD scheduler with κ
=
0.3 is higher than in LTE-based PSN of PF scheduler by 19.17% with 20 MHz ∗ 10 RRHs. Meanwhile, average Jain’s Fairness Index in C-RAN based PSN of GBD scheduler with κ
=
0.6 is also higher than in LTE-based PSN of PF scheduler by 0.045. If considering the PSU’s allocating fairness more, the system total throughput in C-RAN based PSN of GBD scheduler with κ
=
0.6 is at most higher than in LTE-based PSN of PS scheduler by 12.79% and average Jain’s Fairness Index is also higher by 0.03. We find out that C-RAN based PSN has a better throughput performance than LTE-based without a reduction of Jain’s Fairness Index if having the same consideration on the PSU’s allocating fairness. The reason is that C-RAN based architecture owns the capability of scheduling available RBs globally, which brings out a more obvious advantage of user-on-demand allocating. Meanwhile, since introducing the fairness factor as an important part of objective function model, C-RAN based PSN with GBD algorithm can also obtain a good PSU’s allocating fairness. However, it can also be seen that Jain’s Fairness Index in C-RAN based PSN of GBD scheduler with κ
=
0.3 is lower than LTE-based with PS although the throughput is much better. This implies a suitable κ value can allow a well-balanced trade-off between the maximal throughput and the allocation fairness among each PSU.Figure 3
System total throughput versus total resources with C-RAN based and LTE-based PSN.Figure 4
Jain’s Fairness Index versus total resources with C-RAN based and LTE-based PSN.


## 4.2. Convergence of GBD and FP-Based RB Allocation Algorithm

In Section4.1, the performance of C-RAN based PSN with GBD scheduler has been investigated. Then we move on to the algorithm’s convergence and efficiency. Figure 5 shows the convergence of proposed Generalized Bender’s Decomposition and FP-based algorithm compared with one only on the basis of Bender’s Decomposition with no relaxation. We assume a C-RAN based PSN consisting of 10 RRHs and 60 PSUs. Firstly, this figure implies that difference between the upper bound and lower bound is tightened by Bender’s Decomposition so that an approximately-optimal solution of problem (19) can be obtained after finite iterations. This change is consistent with Lemma 3 and Theorem 4 in Section 3. And secondly, it can also be seen that the proposed algorithm needs 14 iterations to obtain the approximately- optimal solution of the system, which is less than the other one of only Bender’s Decomposition. The acceleration is brought by the relaxation to the original problem (19). We use continuation to deal with the integer variable and then find the feasible integer solution by FP whose converged speed is faster than the method that directly search for the integer solution in the regional feasible set constrained by max
1
≤
l
≤
θ
⁡
B
W
ω
l
∗ in each iteration.Figure 5
Upper and lower bound value versus iteration step with different algorithms.Figure6 illustrates the convergence of proposed Generalized Bender’s Decomposition algorithm with different-sized network consisting of 10 RRHs × 50 PSUs, 10 RRHs × 60 PSUs, and 10 RRHs × 70 PSUs. It can be seen that the algorithms in any assumptions converge to the approximately-optimal solution quickly. The figure also implies that the iterations in large-sized network are less than a small-sized one. The reason is that when the RRH’s position and simulation area are assumed and PSUs are in large quantity, it is more likely to place more center users who are nearby the RRHs. Hence, the system performance in large-sized network is generally higher than it in small-sized one. Judging from the same upper bound the algorithm started from and analysis in Section 3, it can be concluded that the iterations to a great value of approximately-optimal solution in a large-sized network are less than to a small one in a small-sized network. One can conclude that the iteration of the proposed GBD and FP based-algorithm is more relevant to the achievable optimal solution rather than the size of the network. This result on convergence features the applicability of the proposed algorithm in the centralized scheduling system like C-RAN based PSN in this paper.Figure 6
Upper and lower bound value versus iteration step with different-sized networks.


## 4.3. Computational Time of GBD and FP-Based RB Allocation Algorithm

The average computational time of proposed GBD algorithm is expressed against the different-sized network in Figure7. We select Simplex, Barrier and Bender’s Decomposition with no relaxation for comparison. Simplex is a general method to search for the (approximately-) optimal solution of programming problem. Barrier is a commonly used way to solve QP problem. It is not surprising that the computational time needed in proposed GBD and FP-based algorithm is much less than that in Simplex and Barrier. And the time of Barrier and Simplex algorithms tends to increase in a nearly linear and exponential fashion, respectively, along with the network size while that of GBD algorithm has a more flatted one. Since the analysis on Figure 3, iterations of the proposed algorithm are less than that of one based on Bender’s Decomposition with no relaxation for an assumed network size. So the average computational of the proposed algorithm is least. It is reasonable that the average computational time of Simplex tends to increase in a nearly exponential fashion along with the network size. However the computational time of the proposed GBD algorithm increases in a more smooth fashion. The reason is that the computational time of Bender’s Decomposition depends on two factors: total iterations and the computing time in each iteration by the experimental desktop. The iterations decrease as the size of network increases as shown in Figure 6. But the experimental observation shows that the computing time in each iteration increases almost in a linear way along with the increased network size. Associated with the iteration steps, the average computational time of the proposed GBD and FP-based algorithm has a smoothly increasing fashion along the network size.Figure 7
Computational time versus size of C-RAN based PSN.The similar results are obtained from the perspective of the jitter of the computational time which is shown in Figure8. GBD converts the relaxed master QP problem into a dual problem as analyzed in Section 3.1 so that the jitter mainly depends on the experimental desktop performance rather than the solution-searching method in each iteration on which the Simplex and Barrier depends.Figure 8
Positive jitter of computational time versus size of C-RAN based PSN.


## 4.4. Trade-Off between Objective Function Value and Computational Time

Algorithm2 is also run with different terminated parameter τ. We assume a C-RAN based PSN network consisting of 10 RRHs and 60 PSUs. In Figure 9, the objective function value of the proposed algorithm is plotted against τ. It is not surprising to see that the objective function value degrades as the terminated parameter decreases. Moreover, the objective function value obtained is not sensitive to the value of τ  when it is small enough, namely, smaller than 100 in our instance, which is consistent with Theorem 5 in Section 3. And the degradations of the objective function value with each τ are also not greater than the value proposed by Theorem 5. It is easy to know the greater τ is, the less computation is time-consuming. Therefore we can select on-demand value of error tolerance τ that considers the trade-off between the computational time and the objective function value in the C-RAN based PSN system.Figure 9
Objective function value versus terminated parameterτ.


## 5. Conclusion

This paper researches on the C-RAN based PSN architecture and OFDM resources allocation problem in it. Firstly, we design the C-RAN based PSN and then by formulating the OFDM RB resources allocation problem into a QP with integer variable, we work out a solution considering both the expected system revenue and the PSU’s allocation fairness. To solve this complicated QP with integer variable, the continuation of integer variable is used to relax the original problem into a general QP problem. The relaxed problem is optimally solved by a proposed Generalized Bender’s Decomposition algorithm after finite iterations. Then FP standard is adopted to obtain the actual integer solution on the original problem. The trade-off between the system degradation and the error tolerance of the proposed algorithm is given theoretically. The numerical results finally show the C-RAN based PSN obtains a good throughput performance without a cost of PSU’s allocation fairness and the proposed GBD and FP based algorithm has the fine convergence and low computational time.One achievement of this paper is to propose a PSN architecture based on C-RAN and model the resource allocation problem in this centralized allocation system. In addition, OFDM resource allocation problem in C-RAN based PSN is complicated because of the integer variables and a large amount of PSU-RRH associations when disaster occurs. However, the allocating efficiency is more important in PSN than commercial network. Hence, another achievement is that we use a corresponding GBD and FP method to solve resources allocating problem efficiently in the proposed C-RAN based PSN, which is referential to the future works on the similar problem.



---

*Source: 9586287-2016-08-25.xml*