This paper is concerned with the problem of joint resource allocation and userpairing in virtual MIMO SCFDMA systems to improve service quality of experience (QoE). Noreference logarithmic model is introduced to quantify service experience for each user and the objective is to maximize sum of all user’s mean of score (MOS). We firstly formulate the optimal problem into an Sdimensional (SD) assignment problem. Then, to solve this problem, the modified Lagrangian relaxation algorithm is deduced to obtain the suboptimal result of joint userparing and subchannel allocation. The merits of this solution are as follows. First, the gap between its results and the global optimal one can be quantified and controlled by balancing the complexity and accuracy, which merit the other suboptimal algorithms do not have. Secondly, it has the polynomial computational complexity and the worst case complexity is O(3
LN
^{3}
), where
L
is the maximum iteration time and
N
is the number of subchannels. Simulations also prove that our proposed algorithm can effectively improve quality of experience and the gap between our proposed and the optimal algorithms can be controlled below 8%.
1. Introduction
I
n the Third Generation Partnership Project Long Term Evolution (3GPPLTE) standard, the proposed uplink transmitting scheme is Single Carrier Frequency Division Multiplexing Address (SCFDMA)
[1]
. MultiInput MultiOutput (MIMO) technique, which increases the spectral efficiency by using multiple transmitting and receiving antennas, has also been widely applied in LTE system. Nevertheless, due to the high hardware complexity and cost, implementation of multiple transmitting antennas sometimes cannot be available, especially in a small handset. Fortunately, LTE spectral efficiency can also be increased by virtual multiinput multioutput (VMIMO) technique
[2]
. In the VMIMO system, two or more users can be served on the same radio timefrequency resource and multiuser equalizer is applied to separate the signal of each user. Therefore, VMIMO combined with SCFDMA has been discussed in the LTE uplink system.
The critical issue in VMIMO SCFDMA system is how to jointly group VMIMO user pairs and allocate radio resource to each pair. However, this problem is usually very complex to solve for the following reasons. First, the allocated frequency resource to each user pair should be adjacent for SCFDMA technique
[3]
. Traditional resource allocation algorithms based on individual subcarrier in OFDMA systems should not be applied any more. Secondly, since it is impossible in reality for all users having orthogonal channels, the system performance improvement by pairing the former users may be immediately degraded for severe cochannel interference between the latter paired users. As a result, joint userpairing and resource allocation algorithms should be considered. On the other hand, to achieve global optimization is very complex, especially when either user number or subchannel number is large.
In order to solve the above problem, there are few works focused on the joint problem in VMIMO SCFDMA systems
[4

6]
. A greedy heuristic proportional fair (PF) scheduling algorithm is proposed in
[4]
. In this algorithm, user pairing is made randomly and each resource block (RB) is allocated by the first chosen user of each pair. Therefore, system performance cannot be global optimal. The combination of Hungarian and binary switching algorithms is presented in
[5]
. Hungarian algorithm is applied to complete the initial userpairing and resource allocation and binary switching algorithm is used to adjust the userpairing. However, each user pair is allocated the same number of RBs and different requirements of quality of service (QoS) among users are ignored. Later, a joint userpairing and resource allocation algorithm based on branchandbound search (BBS) is presented in
[6]
, which can achieve the global optimal solution. And some suboptimal algorithms are also proposed by exploiting the characteristic of BBS. However, the computational complexity of all the algorithms in
[6]
are exponential and will be very high with the increased number of users and RBs. Furthermore, the objectives of all the above aforementioned algorithms are not to improve the quality of experience (QoE) for different traffics. In the other hand, as we all know, improving QoE of endusers become very important for providers to maintain and increase their customs
[7]
. Also, the QoEdriven resource allocation schemes, which enhance the performance of a network from the user perspective, are drawing more and more attentions in the recent years
[8

14]
. How to improve the minimum MOS in the OFDMA systems was discussed in
[8]
and three different classes of data flows: video streamers, audio streamers and best effort were considered.
[9]
and
[10]
respectively discussed how to guarantee QoE of web browser and video in the OFDMA systems. In
[11]
, energy efficiency was added as a factor to balance QoE for each service in the OFDM systems. A general framework for improving QoE in LTE downlink systems presented and system parameters of each protocol layer in the causation of QoE were also discussed in detail
[12]
. The joint power and resource allocation in OFDMA systems was discussed in
[13]
and two different QoE objectives were applied. However, all of these works are focused on the improving of QoE in LTE downlink systems.
[14]
is one of the representative studies on QoE improvement of the LTE uplink systems and it mainly focused on the carrier aggregation systems. So far as we know, there is no work on a QoEdriven joint user pairing and resource allocation scheme in Virtual MIMO SCFDMA Systems
Therefore, in this paper, we dedicated to solve the joint userpairing and resource allocation problem with low computational complexity while maximizing the system QoE. Compared to the previous works, our contributions are as follows. First, the noreference logarithmic QoE model is described to give quantitative metrics for service experience and the mathematical optimal objective can be achieved by this model. Secondly, the joint resource allocation and userpairing problem is converted into an Sdimensional (SD) assignment problem and the mathematical formulation for the joint optimal problem is also presented. Thirdly, the modified Lagrangian relaxation algorithm is deduced to solve the SD algorithm. Compared with BBS algorithm in
[6]
, it can obtain the solutions with polynomial complexity. Compared with other suboptimal algorithms, it can control the gap between the suboptimal solution and the global optimal solution.
The rest of this paper is organized as follows. In section 2, system model is detailed. And then, how to convert the joint userpairing and resource allocation problem into a SD assignment problem is described and the mathematical expressions for this problem is presented in section 3. The Lagrangian relaxation algorithm to solve the SD assignment problem is presented in section 4. In order to prove the performance of our proposed algorithm, simulation results in Matlab are shown in section 5. Finally, some conclusions about our algorithm are given in section 6.
2. System Model
We investigate an uplink virtual MIMO SCFDMA system in a single cell scenario. The transmitter and receiver structures are shown in
Fig. 1
. The base station has
N_{r}
receiving antennas and each user has one transmitting antenna. The transmission bandwidth B is constituted by
KN
orthogonal subcarriers. And all subcarriers are divided into
N
subchannels indexed by N ={1,2,...,
N
} and each subchannel includes
K
subcarriers. There are
M
users belonging to the set of
M
={1,2,...,
M
}.
U
(
U
≤
N_{r}
) users are chosen to form one virtual MIMO user pair and simultaneously transmit their data on the same timefrequency resources.
The proposed system of virtual MIMO SCFDMA
At the receiver, SCFDMA signals are firstly demodulated and then MMSE detection is applied to separate each user’s data. Channel side information (CSI) is estimated by channel estimation algorithm. Then, CSI is sent to the link level performance model and be applied to evaluate the achievable throughput for each application in a certain resource allocation scenario. In this paper, the achievable throughput defined as the number of bits successively transmitted. Since QoE is the subjective experience, it is necessary to introduce a method to assess it with mathematical expression and hence the noreference objective QoE model is introduced to convert the achievable throughput to QoE for each application. Finally, the QoEdriven joint user pairing and subchannel allocation model gives out how to group user pair and allocate each subchannel to these user pair. Since the uplink scheme is SCFDMA, subchannel allocation for each user pair should obey the follow restrictions. First, only one user pair can occupy a certain subchannel. Secondly, all subchannels allocated to each user pair should be consecutive.
In order to make the statement more clear, the link level performance model and the noreference quality of experience (QoE) model are elaborated in the following.
 2.1 Link Level Performance Model
Assuming that
N_{0}
consecutive subchannels are allocated to the selected user pair. For convenience, the indexes of user pairs are omitted in the following text. If the first allocated subchannel index is n0, the receiving signal vector for the selected user pair on the subcarrier
k
(
k
∈[(
n
_{0}
−1)×
K
+1,(
n
_{0}
+
N
_{0}
−1)×
K
]) can be presented as
[6]
,
where
x
_{k}
is the
U
×1 transmitting signal vector,
p
=
diag
(
p
_{1}
,
p
_{2}
,…
p_{U}
) is a diagonal matrix and each diagonal elements denotes the transmitting power of each user,
H
_{k}
is the
N_{r}
×
U
equivalent channel response matrix,
n
_{k}
is the
N_{r}
×1 additive white Gaussian noise vector and each element with zero mean and
variance.
In the analysis of
[6]
, the postprocessing SINR
γ_{u}
for user
u
(
u
=1, 2,…,
U
) can be described as
where Γ
_{u,k}
is the postprocessing SINR for user
u
on subcarrier
k
and can be presented as follows,
Here, [
A
]
_{u,u}
means the uth diagonal element of matrix
A
.
The link level performance model proposed in
[21]
is introduced to evaluate the spectrum efficiency. In this paper, the spectrum efficiency is the number of data bits that can be successfully transmitted per hertz (HZ). The effectives of both adaptive modulation and coding and HARQ on the spectrum efficiency in LTE uplink systems are also considered. For convenience, the user index
“u”
is omitted in the following texts of this subsection and the spectrum efficiency is presented as follows,
where
γ
represents the postprocessing SINR for each user and can be obtained by Eq.(2). Parameter
α
is defined as 0.4 in
[15]
for LTE uplink sytem.
γ
_{min}
,
γ
_{max}
and
SE
_{max}
are respectively 10dB, 15dB and 2bps/HZ. Therefore, the achievable throughput
R
can be deduced by the spectrum efficiency and described as,
 2.2 The NoReference Objective QoE Model
QoE is defined as the overall acceptability of an application or a service
[16]
. It is a subjective measurement of endtoend performance from the point of view of the end user. QoE can be quantified in terms ofMean Opinion Score (MOS) including five levels: Excellent, Good, Fair, Poor and Bad. However, subjective assessment process that asks people to mark the score is very complex and timeconsuming. Some researchers have proposed objective QoE estimation methods. The objective QoE estimation methods include three categories, full reference (FR), reduced reference (RR) and no reference (NR)
[17]
. Since FR and RR methods need to know all or some parts of sourcecoded information at the user experiment, it is not practical to use them in the bandlimited wireless networks. Therefore, in this paper, NR method is applied to estimate QoE of different applications from some available quality of service (QoS) parameters.
Some generic relationships between QoS and QoE have been investigated. Two most famous ones are exponent and logarithm
[18
,
19]
. The logarithmic mapping between QoS and QoE is found by using either subjective test (
[7]
,
[18]
) or the theories of economic and psychology
[19]
. Furthermore, the mathematical logarithmic relationship is simple and easily tractable. In this paper, we choose logarithmic function to describe relationship of QoS and QoE for three common categories of services, such as voice, video and best effort service.
For different applications, many lower or radio link layer QoS parameters, e.g., rate or throughput, power, bandwidth, packet loss rate, ect, can have impact on QoE. It is demonstrated that QoE can be described as a function of transmission data rate and packet loss rate
[20]
and QoE is measured by MOS in these works. When all packets are transmitted successfully, the transmission data is actually the achievable throughput described in subsection A. In other words, if packet error rate is equal to zero, it is obviously that QoE only has relationship with the achievable throughput described in subsection A. Therefore, MOS for different applications can be simplified as a function of achievable throughput as below
[20]
,
where
R
is the achievable throughput for each application and can be obtained by Eq.(5).
R_{1.0}
is the minimum achievable throughput corresponding to QoE is bad and MOS is equal to 1. While
R_{4.5}
corresponds to the maximum achievable throughput if QoE for application is excellent and MOS is assigned by 4.5. Any achievable throughput smaller than
R_{1.0}
may result in bad user experience and the achievable throughput larger than
R_{4.5}
cannot further improve user experience. Values of
R_{1.0}
and
R_{4.5}
have relationships with application categories and can be determined by empirical test in real systems. However, how to obtain the values for
R_{1.0}
and
R_{4.5}
is not our focus in this paper and some previous works can be found in
[20]
.
a
and
b
are coefficients and specific by different applications since
R_{1.0}
and
R_{4.5}
are totally different among applications. Once
R_{1.0}
and
R_{4.5}
are set, we can obtain
a
and
b
by the following equations,
It is obviously that achievable throughput larger than
R_{4.5}
or smaller than
R_{1.0}
has no contributions to improve user experience and this will result in the QoEdriven resource allocation algorithms are different from the conditional QoSdriven ones, i.e. throughputdriven algorithm.
3. Problem Statement
In this section, the problem of QoEdriven userparing and subchannel allocation are jointly considered. The motivation of converting the joint problem to an SD assignment one is firstly declared. Then, we introduce how to convert the joint userparing and subchannel allocation problem into an SD assignment problem. Finally, the mathematical expressions for the optimal joint userpairing and subchannel allocation problem is given.
 3.1 Motivation for problem conversion
The joint problem of userpairing and subchannel allocation has been elaborated in
[6]
and is converted into an integral programming problem. Then, the optimal solution is found by brand and bound algorithm (B&B). By changing the optimal cost function, the mathematical expression in
[6]
can also been applied with QoEdriven problem. Actually, the QoEdriven B&B algorithm is also realized in this paper. Although the details are not presented for it is not our focus, simulations and performance analyses of this algorithm are made in section V. However, time and space complexities of the B&B algorithm to solve the integral programming problem are exponential and impractical for LTE uplink systems. Besides, some suboptimal algorithms are proposed in
[6]
and other previous works. The cost accuracies of these algorithms and the optimal one cannot be quantified and hence it is hard to evaluate the benefits of these algorithms. Furthermore, user pairing and subchannel allocation in all the suboptimal algorithms are firstly made according to throughput or SNR on one subchannel. Nevertheless, it cannot be applied in QoEdriven algorithms since MOS is the final result after userpairing and subchannel allocation. Take an easy case for example. User pair with the largest throughput may not have the largest MOS because for undemanding users too much throughput will result in resource waste for the system MOS performance. Therefore, it is necessary to find an algorithm obtaining the final result of joint userpairing and subchannel allocation. And, it will be better if the time and space complexity of this suboptimal algorithm can be polynomial and its accuracy can be quantifiable.
Fortunately, the relaxation Lagrangian algorithm to solve the SD assignment algorithm can satisfied our requirements. The SD assignment problem is firstly described in
[21]
to solve mutlisensormultitarget problem. The objective is to divide mutlisensors into groups and each group constitutes S sensors to finish a multitarget surveillance. In other words, sensors are firstly paired and then each surveying task is chosen for each pair. Obviously, our joint userpairing and subchannel allocation problem is the same as the mutlisensormultitarget problem and can be translated as firstly users are paired and then the subchannel allocation tasks are chosen for each pair. Once, the joint userpairing and subchannel allocation problem is converted into an SD assignment problem, we can obtain a suboptimal solution with quantifiable accuracy in polynomial time and space complexities.
 3.2 SD assignment problem description for joint userpairing and subchannel allocation problem
In order to convert the joint problem into an SD assignment problem, the subchannel allocation pattern matrix for each user pair is introduced from
[2]
. If there are 3 subchannels in the system, the subchannel allocation pattern matrix A can be represented as,
here, each columns of the matrix represents one possible subchannel allocation pattern for each user pair and there are total C=(
N
^{2}
+
N
+2)/2 columns. In the following, the meaning of the cth subchannel allocation pattern is selected is that the cth column is chosen. Then, the joint userpairing and subchannel allocation problem can be converted into firstly choose a pair for each user and then each pair choose one column of matrix A.
In order to make the above clarification more clear, we would like to give an example in the case of
U
=2,
M
=6,
N
=3. The joint userpairing and subchannel allocation problem is to divide 6 users into 3 groups and allocate 3 subchannels to 3 groups. One possible solution for user pairing set is {(1,2) ,(3,4) ,(5,6)}and subchannel allocation pattern set is {(1, 0, 0) ,(0, 1, 0) ,(0, 0, 1)}. Here, (1, 2) and (1, 0, 0) respectively presents user 1 and 2 are paired and subchannel 1 is allocated to them. The outcome can be presented in
Fig. 2
. The xaxis and yaxis respectively presents the user index and zaxis presents the pattern index. The circles in
Fig. 2
present the outcome of joint userpairing and subchannel allocation. From
Fig. 2
, it is obviously that the joint userpairing and subchannel allocation problem can be converted into a 3D assignment problem if U= 2. As an alternative, if U>2, the joint userpairing and subchannel allocation problem can be converted into an SD assignment problem, where S equals to
U
+1.
3D assignment problem for jointly user pairing and subchannel allocation when N_{u}=2
 3.3 Mathematical expressions for QoEdriven joint userpairing and subchannel allocation problem
In this paper, we would like to concentrate on the condition that two users are grouped into one user pair. However, the expressions and following solutions can be easily extended to the case of U >2.
Our objective in this paper is to maximize the total MOS of all services by jointly pairing users and allocating subchannels. Let X denotes the joint userpairing and subchannel allocation matrix and
X
=[
x_{m,m′,c}
]
_{M×M×C}
is a
M
×
M
×
C
three dimension matrix. If the cth subchannel allocation pattern is allocated for user pair (
m
,
m
′), then
x_{m,m′,c}
=
x_{m′,m,c}
=1; otherwise
x_{m,m′,c}
=
x_{m′,m,c}
=0. If
m
=
m
′, it means that user
m
is paired with itself. The mathematical expression for QoEdriven joint userparing and resource allocation in virtual MIMO SCFDMA systems can be described as follows,
Subject to:
where
MOS_{m,m′,c}
is the sum of MOS of user pair (
m
,
m
′) when user
m
and
m
′ is paired and the
c
th subchannel pattern is chosen;
a_{n,c}
represents the element of matrix
A
in the
n
th row and
c
th column. Constraint (10a) means that the user pairing and subchannel allocation matrix is symmetrical. Constraint (10b) guarantees that each user can only be selected by one user and one subchannel allocation pattern. Constraint (10c) guarantees that subchannels which have been allocated by one user pairing in one channel allocation pattern will not be occupied by other user pairs. Obviously, the above problem is a verified 3D assignment one and is NPhard with exponential complexity
[19]
. Hence, it is necessary to find a suboptimal solution with quantifiable accuracy.
As illustrated above, if
U
>2, the problem can be described as a (
U
+1)D assignment problem. Like the mathematical descriptions in the above 3D assignment problem, the previous
U
dimensions presents user dimension and the final dimension present subchannel dimension. The mathematical expressions for the (
U
+1)D assignment problem just needs to expand the number of user dimension from 2 to
U
. And accordingly, the index of variables
MOS
and
x
should be changed from (
m
,
m
′,
c
) to (
m
_{1}
,
m
_{2}
,….
m_{U}
,
c
). By doing this and keeping the constraints unchanged, it is easy to obtain the mathematical expressions in the case of
U
>2. The solution for the case of
U
>2 is mainly through reducing dimensions from (
U
+1) to 2 and the details about dimension reduction can be referred as
[21]
. Once the dimension is reduced, the following solution for 3D assignment problem can be applied. Since the case of
U
>2 is not our focus in this paper and can be further studied, the details of the mathematical expressions of this case is not listed and the solution process is not illustrated here.
4. The Modified Lagrangian Relaxation Algorithm
 4.1 Details of the modified Lagrangian relaxation algorithm
The Lagrangian relaxation algorithm to solve the 3D assignment is firstly proposed in
[21]
, which has two advantages over other suboptimal algorithms. First, the Lagrangian relaxation algorithm can provide a measurement of how close the feasible solution is to the (perhaps unknowable) optimal solution. Secondly, the computational complexity is polynomial. Therefore, in this paper, the Lagrangian relaxation algorithm is applied to solve the joint userpairing and subchannel allocation problem.
The principle of the Lagrangian relaxation algorithm in [22] is that, if one solution can make the gap between the dual problem and the feasible problem very small, this solution can be seemed as approximatingoptimal one since the object values of dual problem and feasible problem are respectively the upper bound and lower bound of the primary problem. The approximatingoptimal solution is achieved by iterating the Lagrange Multipliers and finding the dual and feasible solutions until the duality gap or maximum iteration times arrives. Each iteration includes four steps: first, convert the optimal problem into a dual problem and find the dual solution of the dual problem; secondly, update the Lagrangian multipliers by the subgradient algorithm; thirdly, based on the updated Lagrangian multipliers , find the feasible solution for the primal optimal problem to obtain the upper bound; fourthly, check whether the duality gap between the feasible solution and the dual solutions achieve some value or the maximum iteration time arrives.
However, the proposed relaxation algorithm in [22] cannot be directly used since constraint (10c) has a little difference with the classical 3D assignment problem. This difference makes the formats of the dual problem, the feasible problem and the subgradient operator are all different from the problem in [22]. Therefore, it is necessary to deduce new mathematical expressions at each step. In the following, we give the modified Lagrangian relaxation algorithm for each step.
First, the dual solution for problem (10) is achieved. Assuming that l is the iteration time. The unconstrained Lagrangian multipliers
are introduced to the constraint (10c). Let
and the dual function for the problem (7) can be presented as,
Subject to :
For a given Lagrangian multiplier vector
, we convert the dual problem into a 2D assignment problem by Lagrangian relaxation. Let
then the optimal objective function can be relaxed as follows,
Let
then the modified dual function can be presented as,
Subject to:
The optimal solution of problem (13) is a classical 2D algorithm and can be achieved by auction algorithm. The optimal user pairing outcomes are denoted as
Secondly, update the Lagrangian multipliers by the subgradient algorithm. We define
^{g(l)}
as an Ndimensional subgradient vector with components given by,
where
The Lagrangian multipliers
are updated via the following and the deduced process are not presented in this paper for the limited page.
where
J
^{∗(l)}
is the best dual cost found until and including iteration 1. The parameters
e
and
f
are tuning parameters with typical values 0.05≤
e
≤0.3 and 1.1≤
f
≤1.6. The parameter
η
(
η
≥1) is incremented by 1 whenever
J
(
λ
^{(l)}
)<
J
^{∗(l1)}
. Otherwise,
η
is updated via
η
=max(
η
−1,1). The parameter
β
balances the convergence speed and solution accuracy and it is found that the iteration process works well when
β
equals to 2 for the proposed problem [22].
Then, we need to find the feasible solution to achieve the upper bound of the optimal problem. The optimal dual solution along with Eqs.(11)  (11b) may not satisfy the constraint (10c). Based on the solution from Eqs.(11)  (11b), the feasible solution can be obtained by solve the following 2D assignment problem (19) which can also be solved by auction algorithm,
Subject to:
Finally, the converged conditions are examined to see whether the iteration should be terminated as the following rule,
where ming
ap
is the relative approximate duality gap;
L
is the maximum iteration time. Let
denote the optimal solution of
x_{m}
_{,m(l),c}
of problem (19). If Eq.(20) is satisfied, then the algorithm is terminated, the solutions of
is the final userpairing and subchannel allocation outcome; otherwise, using the new Lagrangian multipliers obtained in step two to implement new turn of the above four steps. The details of the modified Lagrangian relaxation algorithm are shown in
Table 1
.
The modified Lagrangian relaxation algorithm
The modified Lagrangian relaxation algorithm
 4.2 Complexity and Accuracy Analyses
In this subsection, analyses about the time and space complexities of the proposed algorithm and the joint optimal algorithm proposed in
[6]
which is based on the branch and bound (B&B) algorithm. All other suboptimal algorithms in
[6]
and other works are not considered in this paper. Through this analyses, we would like to present how much computational and storage capacities are reduced by our proposed algorithm and how proximity of the algorithm can achieve the optimal algorithm.
Before making the analyses, it is assumed that the user number of each pair, i.e. U, is a constant once the LTE uplink system model is designed. The subchannel number and user number can be variable. This assumption is reasonable since the user number multiplexed on the same resource blocks is determined by userpairing rules which remains unchangeable during the joint userparing and subchannel allocation progress.
In
[6]
, the mathematical expression for the joint userpairing and subchannel allocation is presented as an integral programming problem. B&B algorithm is applied to find the optimal solution. The searching algorithm is proposed which may has exponential computational complexity. Actually, this problem can be converted into a 2D assignment problem. The number of rows of the 2D matrix is
elements, where
represents the combination number of U taken from M. The number of columns of the 2D matrix is (
N
^{2}
+
N
+2)/2. Hence, it takes
O
((
N
^{2}
+
N
+2)
/2) operations to solve the 2D assignment problem. The storage capacity is at least
O
((
N
^{2}
+
N
+2)
/2). The computational and storage complexities are polynomial with subchannel N and exponential with user number M. Therefore, it is an impractical algorithm in real LTE uplink systems.
According to the computational complexity analyses in [22], the worst case of Lagrangian relaxation algorithm is
O
(
L
(
U
1)
M
^{2}
(
N
^{2}
+
N
+2)/2), where
L
is the maximum iteration time. The storage capacity requirement in worst case is
O
((
U
1)
M
^{2}
(
N
^{2}
+
N
+2)/2). Hence, the proposed algorithm in this paper has polynomial time and space complexity.
Furthermore, the quantifiable accuracy of our proposed suboptimal solution can be controlled by the minimum duality gap min
gap
and the maximum iteration number [22]. By simulation, we can see that the suboptimal solutions can be controlled below 8% in the following section.
5. Performance Analysis
In this section, we validate QoEdriven joint userpairing and resource allocation algorithms for VMIMO SCFDMA systems. It is reasonable to assume perfect power control for each user in the LTE uplink system. Therefore, pathloss and shadowing fading are compensated. The small scale fading is modeled as Rayleigh flat fading on each subchannel. Each user is in 5km/h movement speed. Actually, since channel estimation is not our focus in this paper and perfect channel side information is assumed, the effective of user velocity on these algorithms can be ignored and not discussed in this paper. The ITUPedB channel model is applied for each user and channel fading of each user are independent. Four service categories are considered, i.e. voice, video streaming, FTP and video conference. Their maximum and minimum transmit rates and other simulation parameters are listed in
Table 2
.
Applications in each class
Applications in each class
In these simulations, we compare five different algorithms which are presented as follows:
1), ThroughputBBS: finding the optimal solutions based on BBS to maximize the system throughput
[4]
;
2), ThroughputUPRA: finding the suboptimal solutions based on UPRA Alg. to maximize the system throughput
[4]
;
3), MOSBBS: finding the optimal solutions based on BBS to maximize the sum of MOS;
4), MOSSD: finding the suboptimal solution based on SD Alg. to maximize the sum of MOS;
5), MOSUPRA: finding the suboptimal solution based on UPRA Alg. to maximize the system MOS, i.e. firstly choosing all user pairs according to the maximum MOS for each subchannel and then allocating all subchannels to the chosen user pairs.
 5.1 Effects of Simulation Frame Number
Since wireless channel varies from frame to frame, the performance outcome of one frame, no matter sum of MOS or system throughput, will also vary all the time. Therefore, it is more accurate to compare the average performance in several frames which is named as smoothing window and its length is
F
in this simulation. Along with this consideration is how to choose an appropriate value of
F
. This is because too small
F
cannot reflect the accurate performance and too large
F
will unnecessarily waste the simulation time. In this subsection, we determine
F
by simulations. And, in the following simulation part, the terms of sum of MOS and system throughput refers to the statistical average performance over
F
.
Fig. 3
and
Fig. 4
respectively show the throughput and sum of MOS performance versus the simulation frame number when
SNR
=10db and
M
=8. Each service category includes two users. From these two figures, we can see that when
F
=150, the performances of throughput and sum of MOS reach a steady state. Hence, in the following simulations, the length of smoothing window
F
is set to be 150.
Throughput versus frame number for all algorithms
Sum of MOS versus frame number for all algorithms
 5.2 Effects of SNR
In
Fig. 5
and
Fig. 6
, throughput and system MOS versus SNR are respectively shown when
M
=8. Each service category includes two users. From these two figures, we can see that Throughput BBS algorithm can obtain the maximum system throughput while MOSBBS algorithm can obtain the maximum system MOS. This is because ThroughputBBS algorithm may allocate subchannels to user pairs with good channel fading as much as possible while subchannels more than in demand cannot improve their QoE. On the other hand, users with worse channel conditions cannot obtain enough subchannels to improve QoE and hence the system QoE will not be good even SNR is high. The performances of throughput and sum of MOS versus SNR further prove that it is necessary to choose the QoEdriven algorithms if the objective of resource allocation is to improve user experience.
Throughput versus SNR for all algorithms
Sum of MOS versus SNR for all algorithms
In
Fig.6
, with the SNR increase, sum of MOS of MOSBBS and MOSSD algorithms increase rapidly and finally to a constant value when
SNR
≥16
db
while sum of MOS of other throughputdriven algorithms grow very slowly. This phenomenon presents that QoEdiven joint userpairing and subchannel allocation algorithms can improve user experience under various channel fading conditions while throughputdriven algorithms fail to do so. Furthermore, MOSUPRA algorithm also cannot improve user experience even with SNR increasing since it may incorrectly remove some demanding users when doing user pairing at the first step. Another interesting phenomenon in
Fig.6
is that all MOS gaps between MOSSD and MOSBBS algorithms for each SNRvalue are below 8% which demonstrate that our proposed algorithm can control the accuracy of the gap from the optimal algorithm. Gap becomes smaller with the SNR increases. This is mainly because channel fading on different subchannels become almost the same when SNR becomes very large and all users can obtain satisfied experience in these two algorithms.
 5.3 Effects of User Number
In
Fig .7
and
Fig. 8
, the performances of throughput and sum of MOS versus user number
M
are respectively presented when SNR is 10dB. The category of sequentially adding users to system is FTP, voice, video conference and video steaming. From these two figures, we find that performance gaps of sum of MOS between these five algorithms become larger and larger with the increase of user number. The main reason is that the amount of resources allocated to each user pair decrease with user number increasing and hence user experience becomes more sensitive to the outcome of subchannel allocation and userpairing at each time. However, the gap between MOSBBS and MOSSD is still small.
Throughput versus user number for all algorithms
Sum of MOS versus user number for all algorithms
For MOSUPRA algorithm, this tend becomes more obvious. This phenomenon reflects that doing userpairing firstly according to their sum of MOS on one subchannel will result in very inaccurate resource allocation outcome. Thereafter, it further demonstrates the necessity of considering the joint userpairing and subchannel allocation together in the MOSdriven resource allocation in VMIMO SCFDMA systems.
5. Conclusion
In this paper, we investigate the joint resource allocation and userpairing problem to improve quality of experience (QoE) in the Virtual MIMO SCFDMA system. QoE is quantified by mapping quality of service parameters into mean of score (MOS) and our objective is to maximize sum of MOS for all users. The joint optimal problem is converted and formulated into an SD assignment problem in this paper. However, SD assignment problem is also NPhard. Then, a modified Lagrangian relaxation algorithm is proposed to solve the SD assignment problem. So far as we know, it is the first time to research the QoEdriven joint resource allocation and userpairing problem. Compared with all the previous works either giving the branchandbound search algorithm with exponential complexity or some suboptimal algorithms which cannot demonstrate how close the suboptimal solutions to the global optimal ones, the Lagrangian relaxation algorithm can achieve the suboptimal results in polynomial time complexity and control the gap between suboptimal and optimal outcomes under a quantifiable level. Performance comparisons between our proposed algorithm and another four conventional algorithms are further made by simulations. The results demonstrate that the gap of sum of MOS achieved by our proposed algorithm and the optimal algorithm (MOSBBS) is below 8%. This means that our proposed algorithm can effectively improve system quality of experience.
BIO
Yahui Hu achieved her doctor degree from School of Information and Communication Engineering, Beijing University of Posts and Telecommunications and is currently working in the institute of information engineering Chinese Academy of Sciences as an associate professor. Her main research interests include user’s QoS/QoE for different applications , cognitive radio network, wireless communications and wireless sensor network.
Song Ci (S’99–M’02–SM’06) is an Assistant Professor of computer and electronics engineering at the University of NebraskaLincoln. He is the Director of the Intelligent Ubiquitous Computing Lab (iUbiComp Lab) and holds a courtesy appointment of UNL Ph.D. in the Biomedical Engineering Program. He is also affiliated with Nebraska Biomechanics Core Facility at the University of Nebraska at Omaha and Center for Advanced Surgical Technology (CAST) at University of Nebraska Medical Center, Omaha, NE. His research interests include dynamic complex system modeling and optimization, green computing and power management, contentaware qualitydriven crosslayer optimized multimedia over wireless, cognitive network management and serviceoriented architecture, and cyberenable ehealth care.
Nemhauser G. L.
,
Wolsey L. A.
1988
Integer and Combinatorial Optimization
WileyInterscience
New York
Wong Ian C.
,
Oteri Oghenekome
,
McCoy Wes
2009
“Optimal Resource Allocation in Uplink SCFDMA Systems,”
IEEE Transactions On Wireless Communications
8
(5)
DOI : 10.1109/TWC.2009.061038
Rumney Moray
3GPP LTE: Introducing SingleCarrier FDMA
Agilent Measurement Journal
2008
Kim J. W.
,
Hwang I. S.
,
Kang C. G.
“Scheduling for virtual MIMO in single carrier FDMA (SCFDMA) system,”
in Proc. Of 2010 Inf. Commun. Technol. Convergence Conf
115 
119
Ruder M. A.
,
Ding D.
,
Dang U. L.
,
Gerstacker W. H.
“Combined user pairing and spectrum allocation for multiuser SCFDMA transmission,”
in Proc. of 2011 IEEE International Conf. Commun.
1 
6
Fan Jiancun
,
Li Geoffrey Ye
,
Yin Qinye
,
Peng Bingguang
,
Zhu Xiaolong
2012
“Joint User Pairing and Resource Allocation for LTE Uplink Transmission,”
IEEE Transactions On Wireless Communications
11
(9)
Torres J.
,
MorilloVelarde V.
,
Soret B.
,
AguayoTorres M. C.
,
Entrambasaguas J. T.
“Crosslayer user multiplexing algorithms evaluation in MIMO OFDM wireless systems,”
in Proc. of IEEE 16th IST
July, 2007
1 
5
Sacchi C.
,
Granelli F.
,
Schlegel C.
2011
“A QoEOriented Strategy for OFDMA Radio Resource Allocation Based on MinMOS Maximization,”
IEEE Communications Letters
15
(5)
494 
496
DOI : 10.1109/LCOMM.2011.031411.101672
Ameigeiras Pablo
,
RamosMunoz Juan J.
,
NavarroOrtiza Jorge
,
Mogensen Preben
,
LopezSoler Juan M.
2010
“QoE oriented crosslayer design of a resource allocation algorithm in beyond 3G systems,”
Computer Communications
33
571 
582
DOI : 10.1016/j.comcom.2009.10.016
Nasimi M.
,
Malaysia Serdang
,
Kousha M.
,
Hashim F.
“QoEoriented crosslayer downlink scheduling for heterogeneous traffics in LTE networks,”
in Proc. of 2013 IEEE Communications Conf.
Nov. 2013
292 
297
Li Bingquan
,
Li Shuo
,
Xing Chengwen
,
Fei Zesong
,
Kuan Jingming
“A QoEbased OFDM Resource Allocation Scheme for Energy Efficiency and Quality Guarantee in MultiuserMultiservice System,”
in Proc. of 2013 IEEE GC Workshop
Dec. 2012
1293 
1297
Gómez Gerardo
,
Lorca Javier
,
García Raquel
,
Pérez Quiliano
2013
“Towards a QoEDriven Resource Control in LTE and LTEA Networks,”
Journal of Computer Networks and Communications
2013
DOI : 10.1155/2013/505910
Rugelj Miha
,
Sedlar Urban
,
Volk Mojca
,
Sterle Janez
,
Hajdinjak Melita
,
Kos Andrej
2014
“Novel CrossLayer QoEAware Radio Resource Allocation Algorithms in Multiuser OFDMA Systems,”
IEEE Transactions On Communications
62
(9)
DOI : 10.1109/TCOMM.2014.2347288
Song Yujae
,
Han Youngnam
,
Choi Yonghoon
“A QoEaware joint resource allocation algorithm for uplink carrier aggregation in LTEAdvanced systems,”
in Proc. of 2014 IEEE ICC
Daejeon
Jun. 2014
1 
5
2008
3GPP TR 36.942 V.8.1.0, “EUTRA: Radio Frequency (RF) system scenarios,”
ITUT SG12, “Definition of Quality of Experience,”COM12 – LS 62 – E, TD 109rev2 (PLEN/12)
Geneva, Switzerland
January 1625, 2007
Reichl P.
,
Egger S.
,
Schatz R.
,
Alconzo A. D.
“The Logarithmic Nature of QoE and the Role of the WeberFechner Law in QoE Assessment,”
in Proc. of IEEE ICC 2010
1 
5
Fiedler M.
,
Hossfeld T.
,
Phuoc T.G.
2010
“A generic quantitative relationship between quality of experience and quality of service,”
IEEE Network
24
(2)
36 
41
DOI : 10.1109/MNET.2010.5430142
Chen F.
,
Qin X.W.
,
Wei G.
2012
“QoE optimized resource allocation in multiuser OFDM systems,”
przegląd elektrotechniczny
328 
331
Deb S.
,
PATTIPATI M. Y. K.
,
BARSHALOM Y.
1997
“A Generalized SD Assignment Algorithm for MultisensorMultitarget State Estimation,”
IEEE Transactions on Aerospace and Electronic Systems
33
523 
538
DOI : 10.1109/7.575891
Pattipati Krishna R.
,
Deb Somnath
,
BarShalom Yaakov
,
Washburn Jr. Robert B.
1992
“A New Relaxation Algorithm and Passive Sensor Data Association,”
IEEE Transactions On Automatic Control
31
(2)