Advanced
QoE-driven Joint Resource Allocation and User-paring in Virtual MIMO SC-FDMA Systems
QoE-driven Joint Resource Allocation and User-paring in Virtual MIMO SC-FDMA Systems
KSII Transactions on Internet and Information Systems (TIIS). 2015. Oct, 9(10): 3831-3851
Copyright © 2015, Korean Society For Internet Information
  • Received : January 07, 2015
  • Accepted : May 06, 2015
  • Published : October 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
YaHui Hu
State Key Laboratory of Information Security, Institute of Information Engineering,Chinese Academy of Sciences Beijing, China 100190
Song Ci
Dep. of Computer and Electronics Engineering,University of Nebraska-Lincoln 200B Peter Kiewit Institute,Omaha, NE 68182

Abstract
This paper is concerned with the problem of joint resource allocation and user-pairing in virtual MIMO SC-FDMA systems to improve service quality of experience (QoE). No-reference 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 S-dimensional (S-D) assignment problem. Then, to solve this problem, the modified Lagrangian relaxation algorithm is deduced to obtain the suboptimal result of joint user-paring 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%.
Keywords
1. Introduction
I n the Third Generation Partnership Project Long Term Evolution (3GPP-LTE) standard, the proposed uplink transmitting scheme is Single Carrier Frequency Division Multiplexing Address (SC-FDMA) [1] . Multi-Input Multi-Output (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 hand-set. Fortunately, LTE spectral efficiency can also be increased by virtual multi-input multi-output (VMIMO) technique [2] . In the VMIMO system, two or more users can be served on the same radio time-frequency resource and multiuser equalizer is applied to separate the signal of each user. Therefore, VMIMO combined with SC-FDMA has been discussed in the LTE uplink system.
The critical issue in VMIMO SC-FDMA 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 SC-FDMA 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 co-channel interference between the latter paired users. As a result, joint user-pairing 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 SC-FDMA 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 user-pairing and resource allocation and binary switching algorithm is used to adjust the user-pairing. 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 user-pairing and resource allocation algorithm based on branch-and-bound 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 end-users become very important for providers to maintain and increase their customs [7] . Also, the QoE-driven 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 QoE-driven joint user pairing and resource allocation scheme in Virtual MIMO SC-FDMA Systems
Therefore, in this paper, we dedicated to solve the joint user-pairing 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 no-reference 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 user-pairing problem is converted into an S-dimensional (S-D) 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 S-D 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 user-pairing and resource allocation problem into a S-D assignment problem is described and the mathematical expressions for this problem is presented in section 3. The Lagrangian relaxation algorithm to solve the S-D 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 SC-FDMA system in a single cell scenario. The transmitter and receiver structures are shown in Fig. 1 . The base station has Nr 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 Nr ) users are chosen to form one virtual MIMO user pair and simultaneously transmit their data on the same time-frequency resources.
PPT Slide
Lager Image
The proposed system of virtual MIMO SC-FDMA
At the receiver, SC-FDMA 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 no-reference objective QoE model is introduced to convert the achievable throughput to QoE for each application. Finally, the QoE-driven 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 SC-FDMA, 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 no-reference quality of experience (QoE) model are elaborated in the following.
- 2.1 Link Level Performance Model
Assuming that N0 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] ,
PPT Slide
Lager Image
where x k is the U ×1 transmitting signal vector, p = diag ( p 1 , p 2 ,… pU ) is a diagonal matrix and each diagonal elements denotes the transmitting power of each user, H k is the Nr × U equivalent channel response matrix, n k is the Nr ×1 additive white Gaussian noise vector and each element with zero mean and
PPT Slide
Lager Image
variance.
In the analysis of [6] , the post-processing SINR γu for user u ( u =1, 2,…, U ) can be described as
PPT Slide
Lager Image
where Γ u,k is the post-processing SINR for user u on subcarrier k and can be presented as follows,
PPT Slide
Lager Image
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,
PPT Slide
Lager Image
where γ represents the post-processing 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,
PPT Slide
Lager Image
- 2.2 The No-Reference Objective QoE Model
QoE is defined as the overall acceptability of an application or a service [16] . It is a subjective measurement of end-to-end 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 time-consuming. 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 source-coded information at the user experiment, it is not practical to use them in the band-limited 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] ,
PPT Slide
Lager Image
where R is the achievable throughput for each application and can be obtained by Eq.(5). R1.0 is the minimum achievable throughput corresponding to QoE is bad and MOS is equal to 1. While R4.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 R1.0 may result in bad user experience and the achievable throughput larger than R4.5 cannot further improve user experience. Values of R1.0 and R4.5 have relationships with application categories and can be determined by empirical test in real systems. However, how to obtain the values for R1.0 and R4.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 R1.0 and R4.5 are totally different among applications. Once R1.0 and R4.5 are set, we can obtain a and b by the following equations,
PPT Slide
Lager Image
PPT Slide
Lager Image
It is obviously that achievable throughput larger than R4.5 or smaller than R1.0 has no contributions to improve user experience and this will result in the QoE-driven resource allocation algorithms are different from the conditional QoS-driven ones, i.e. throughput-driven algorithm.
3. Problem Statement
In this section, the problem of QoE-driven user-paring and subchannel allocation are jointly considered. The motivation of converting the joint problem to an S-D assignment one is firstly declared. Then, we introduce how to convert the joint user-paring and subchannel allocation problem into an S-D assignment problem. Finally, the mathematical expressions for the optimal joint user-pairing and subchannel allocation problem is given.
- 3.1 Motivation for problem conversion
The joint problem of user-pairing 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 QoE-driven problem. Actually, the QoE-driven 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 QoE-driven algorithms since MOS is the final result after user-pairing 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 user-pairing 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 S-D assignment algorithm can satisfied our requirements. The S-D assignment problem is firstly described in [21] to solve mutlisensor-multitarget 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 user-pairing and subchannel allocation problem is the same as the mutlisensor-multitarget problem and can be translated as firstly users are paired and then the subchannel allocation tasks are chosen for each pair. Once, the joint user-pairing and subchannel allocation problem is converted into an S-D assignment problem, we can obtain a suboptimal solution with quantifiable accuracy in polynomial time and space complexities.
- 3.2 S-D assignment problem description for joint user-pairing and subchannel allocation problem
In order to convert the joint problem into an S-D 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,
PPT Slide
Lager Image
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 user-pairing 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 user-pairing 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 x-axis and y-axis respectively presents the user index and z-axis presents the pattern index. The circles in Fig. 2 present the outcome of joint user-pairing and subchannel allocation. From Fig. 2 , it is obviously that the joint user-pairing and subchannel allocation problem can be converted into a 3-D assignment problem if U= 2. As an alternative, if U>2, the joint user-pairing and subchannel allocation problem can be converted into an S-D assignment problem, where S equals to U +1.
PPT Slide
Lager Image
3-D assignment problem for jointly user pairing and subchannel allocation when Nu=2
- 3.3 Mathematical expressions for QoE-driven joint user-pairing 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 user-pairing and subchannel allocation matrix and X =[ xm,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 xm,m′,c = xm′,m,c =1; otherwise xm,m′,c = xm′,m,c =0. If m = m ′, it means that user m is paired with itself. The mathematical expression for QoE-driven joint user-paring and resource allocation in virtual MIMO SC-FDMA systems can be described as follows,
PPT Slide
Lager Image
Subject to:
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
where MOSm,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; an,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 3-D assignment one and is NP-hard 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 3-D 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 ,…. mU , 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 3-D 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 3-D 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 user-pairing 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 approximating-optimal one since the object values of dual problem and feasible problem are respectively the upper bound and lower bound of the primary problem. The approximating-optimal 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 3-D 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
PPT Slide
Lager Image
are introduced to the constraint (10c). Let
PPT Slide
Lager Image
and the dual function for the problem (7) can be presented as,
PPT Slide
Lager Image
Subject to :
PPT Slide
Lager Image
PPT Slide
Lager Image
For a given Lagrangian multiplier vector
PPT Slide
Lager Image
, we convert the dual problem into a 2-D assignment problem by Lagrangian relaxation. Let
PPT Slide
Lager Image
then the optimal objective function can be relaxed as follows,
PPT Slide
Lager Image
Let
PPT Slide
Lager Image
then the modified dual function can be presented as,
PPT Slide
Lager Image
Subject to:
PPT Slide
Lager Image
PPT Slide
Lager Image
The optimal solution of problem (13) is a classical 2-D algorithm and can be achieved by auction algorithm. The optimal user pairing outcomes are denoted as
PPT Slide
Lager Image
Secondly, update the Lagrangian multipliers by the subgradient algorithm. We define g(l) as an N-dimensional subgradient vector with components given by,
PPT Slide
Lager Image
where
PPT Slide
Lager Image
The Lagrangian multipliers
PPT Slide
Lager Image
are updated via the following and the deduced process are not presented in this paper for the limited page.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
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 ∗(l-1) . 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 2-D assignment problem (19) which can also be solved by auction algorithm,
PPT Slide
Lager Image
Subject to:
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Finally, the converged conditions are examined to see whether the iteration should be terminated as the following rule,
PPT Slide
Lager Image
where ming ap is the relative approximate duality gap; L is the maximum iteration time. Let
PPT Slide
Lager Image
denote the optimal solution of xm ,m(l),c of problem (19). If Eq.(20) is satisfied, then the algorithm is terminated, the solutions of
PPT Slide
Lager Image
is the final user-pairing 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
PPT Slide
Lager Image
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 user-pairing rules which remains unchangeable during the joint user-paring and subchannel allocation progress.
In [6] , the mathematical expression for the joint user-pairing 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 2-D assignment problem. The number of rows of the 2-D matrix is
PPT Slide
Lager Image
elements, where
PPT Slide
Lager Image
represents the combination number of U taken from M. The number of columns of the 2-D matrix is ( N 2 + N +2)/2. Hence, it takes O (( N 2 + N +2)
PPT Slide
Lager Image
/2) operations to solve the 2-D assignment problem. The storage capacity is at least O (( N 2 + N +2)
PPT Slide
Lager Image
/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 QoE-driven joint user-pairing and resource allocation algorithms for VMIMO SC-FDMA 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 ITU-Ped-B 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
PPT Slide
Lager Image
Applications in each class
In these simulations, we compare five different algorithms which are presented as follows:
1), Throughput-BBS: finding the optimal solutions based on BBS to maximize the system throughput [4] ;
2), Throughput-UPRA: finding the suboptimal solutions based on UP-RA Alg. to maximize the system throughput [4] ;
3), MOS-BBS: finding the optimal solutions based on BBS to maximize the sum of MOS;
4), MOS-SD: finding the suboptimal solution based on S-D Alg. to maximize the sum of MOS;
5), MOS-UPRA: finding the suboptimal solution based on UP-RA 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.
PPT Slide
Lager Image
Throughput versus frame number for all algorithms
PPT Slide
Lager Image
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 MOS-BBS algorithm can obtain the maximum system MOS. This is because Throughput-BBS 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 QoE-driven algorithms if the objective of resource allocation is to improve user experience.
PPT Slide
Lager Image
Throughput versus SNR for all algorithms
PPT Slide
Lager Image
Sum of MOS versus SNR for all algorithms
In Fig.6 , with the SNR increase, sum of MOS of MOS-BBS and MOS-SD algorithms increase rapidly and finally to a constant value when SNR ≥16 db while sum of MOS of other throughput-driven algorithms grow very slowly. This phenomenon presents that QoE-diven joint user-pairing and subchannel allocation algorithms can improve user experience under various channel fading conditions while throughput-driven algorithms fail to do so. Furthermore, MOS-UPRA 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 MOS-SD and MOS-BBS algorithms for each SNR-value 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 user-pairing at each time. However, the gap between MOS-BBS and MOS-SD is still small.
PPT Slide
Lager Image
Throughput versus user number for all algorithms
PPT Slide
Lager Image
Sum of MOS versus user number for all algorithms
For MOS-UPRA algorithm, this tend becomes more obvious. This phenomenon reflects that doing user-pairing 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 user-pairing and subchannel allocation together in the MOS-driven resource allocation in VMIMO SC-FDMA systems.
5. Conclusion
In this paper, we investigate the joint resource allocation and user-pairing 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 S-D assignment problem in this paper. However, S-D assignment problem is also NP-hard. Then, a modified Lagrangian relaxation algorithm is proposed to solve the S-D assignment problem. So far as we know, it is the first time to research the QoE-driven joint resource allocation and user-pairing problem. Compared with all the previous works either giving the branch-and-bound 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 (MOS-BBS) 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 Nebraska-Lincoln. He is the Director of the Intelligent Ubiquitous Computing Lab (iUbi-Comp 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, content-aware quality-driven cross-layer optimized multimedia over wireless, cognitive network management and service-oriented architecture, and cyber-enable e-health care.
References
Nemhauser G. L. , Wolsey L. A. 1988 Integer and Combinatorial Optimization Wiley-Interscience New York
Wong Ian C. , Oteri Oghenekome , McCoy Wes 2009 “Optimal Resource Allocation in Uplink SC-FDMA Systems,” IEEE Transactions On Wireless Communications 8 (5)    DOI : 10.1109/TWC.2009.061038
Rumney Moray 3GPP LTE: Introducing Single-Carrier FDMA Agilent Measurement Journal 2008
Kim J. W. , Hwang I. S. , Kang C. G. “Scheduling for virtual MIMO in single carrier FDMA (SC-FDMA) 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 SC-FDMA 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. , Morillo-Velarde V. , Soret B. , Aguayo-Torres M. C. , Entrambasaguas J. T. “Cross-layer 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 QoE-Oriented Strategy for OFDMA Radio Resource Allocation Based on Min-MOS Maximization,” IEEE Communications Letters 15 (5) 494 - 496    DOI : 10.1109/LCOMM.2011.031411.101672
Ameigeiras Pablo , Ramos-Munoz Juan J. , Navarro-Ortiza Jorge , Mogensen Preben , Lopez-Soler Juan M. 2010 “QoE oriented cross-layer 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. “QoE-oriented cross-layer 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 QoE-based OFDM Resource Allocation Scheme for Energy Efficiency and Quality Guarantee in Multiuser-Multiservice 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 QoE-Driven Resource Control in LTE and LTE-A 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 Cross-Layer QoE-Aware 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 QoE-aware joint resource allocation algorithm for uplink carrier aggregation in LTE-Advanced systems,” in Proc. of 2014 IEEE ICC Daejeon Jun. 2014 1 - 5
2008 3GPP TR 36.942 V.8.1.0, “E-UTRA: Radio Frequency (RF) system scenarios,”
ITU-T SG12, “Definition of Quality of Experience,”COM12 – LS 62 – E, TD 109rev2 (PLEN/12) Geneva, Switzerland January 16-25, 2007
Reichl P. , Egger S. , Schatz R. , Alconzo A. D. “The Logarithmic Nature of QoE and the Role of the Weber-Fechner 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. , BAR-SHALOM Y. 1997 “A Generalized S-D Assignment Algorithm for Multisensor-Multitarget State Estimation,” IEEE Transactions on Aerospace and Electronic Systems 33 523 - 538    DOI : 10.1109/7.575891
Pattipati Krishna R. , Deb Somnath , Bar-Shalom Yaakov , Washburn Jr. Robert B. 1992 “A New Relaxation Algorithm and Passive Sensor Data Association,” IEEE Transactions On Automatic Control 31 (2)