Printer Friendly

QoE-driven joint resource allocation and user-paring in virtual MIMO SC-FDMA systems.

1. Introduction

In 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 Vorthogonal subcarriers. And all subcarriers are divided into N subchannels indexed by N = {1, 2, ..., N}and each subchannel includes K subcarriers. There areMusers belonging to the set of M = {1, 2, ..., M}. U (U [less than or equal to] [N.sub.r]) users are chosen to form one virtual MIMO user pair and simultaneously transmit their data on the same time-frequency resources.

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 [N.sub.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 [n.sub.0], the receiving signal vector for the selected user pair on the subcarrier k (k [member of] [([n.sub.0] - 1) x K + 1, ([n.sub.0] + [N.sub.0] - 1) x K]) can be presented as [6],

[y.sub.k] = [H.sub.k][[square root of Px].sub.k] + [n.sub.k] (1)

where [x.sub.k] is the U x 1 transmitting signal vector, P = diag ([p.sub.1], [p.sub.2], ... [p.sub.U]) is a diagonal matrix and each diagonal elements denotes the transmitting power of each user, [H.sub.k] is the [N.sub.r] x U equivalent channel response matrix, [n.sub.k] is the [N.sub.r] x 1 additive white Gaussian noise vector and each element with zero mean and [[sigma].sup.2.sub.n] variance.

In the analysis of [6], the post-processing SINR [[gamma].sub.u] for user u(u = 1, 2, ..., U) can be described as


where [[GAMMA].sub.u,k] is the post-processing SINR for user u on subcarrier k and can be presented as follows,


Here, [[A].sub.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 [gamma] represents the post-processing SINR for each user and can be obtained by Eq.(2). Parameter [alpha] is defined as 0.4 in [15] for LTE uplink sytem. [[gamma].sub.min], [[gamma].sub.max] and [SE.sub.max] are respectively -10dB, 15dB and 2bps/HZ. Therefore, the achievable throughput R can be deduced by the spectrum efficiency and described as,

R = [[BN.sub.0]/N] SE (5)

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 of Mean 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],


where R is the achievable throughput for each application and can be obtained by Eq.(5). [R.sub.1.0] is the minimum achievable throughput corresponding to QoE is bad and MOS is equal to 1. While [R.sub.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.sub.1.0] may result in bad user experience and the achievable throughput larger than [R.sub.4.5] cannot further improve user experience. Values of [R.sub.1.0] and [R.sub.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.sub.1.0] and [R.sub.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.sub.1.0] and [R.sub.4.5] are totally different among applications. Once [R.sub.1.0] and [R.sub.4.5] are set, we can obtain a and b by the following equations,

a = [1/3.5] ln [R.sub.4.5] + 1/15.75 [R.sub.1.0]; (7)

b = [R.sub.4.5.sup.1/3.5] x [R.sub.1.0.sup.1/15.75] (8)

It is obviously that achievable throughput larger than [R.sub.4.5] or smaller than [R.sub.1.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,


here, each columns of the matrix represents one possible subchannel allocation pattern for each user pair and there are total C = ([N.sup.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.

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 = [[[x.sub.m,m',c]].sub.M x M x C] is a M x M x C three dimension matrix. If the cth subchannel allocation pattern is allocated for user pair (m, m'), then [x.sub.m,m',c] = [x.sub.m',m,c] = 1; otherwise [x.sub.m,m',c] = [x.sub.m',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,

max [M.summation over (m=1)] [M.summation over (m'=1)] [C.summation over (c=1)] [MOS.sub.m,m',c] [x.sub.m,m',c] (10)

Subject to:



[M.summation over (m-1)] [M.summation over (m'-1) [C.summation over (c-1)]] [a.sub.n,c] [x.sub.m,m',c] = 2 [for all]n = 1, 2, ..., N (10c)

where [MOS.sub.m, m', c] is the sum of MOS of user pair (m,m') when user m and m' is paired and the cth subchannel pattern is chosen; [a.sub.n,c] represents the element of matrix A in the nth row and cth 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.sub.1], [m.sub.2], ..., [m.sub.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 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 [[lambda].sup.(l).sub.n] (n = 1, 2, ..., N) are introduced to the constraint (10c). Let [[lambda].sup.(0).sub.n] = 0 (n = 1, 2, ..., N) and the dual function for the problem (7) can be presented as,


Subject to :


[M.summation over (m'=1)] [C.summation over (c=1)] [x.sub.m,m',c] = 1 (11b)

For a given Lagrangian multiplier vector [[lambda].sup.(l)] = [[[lambda].sup.(l).sub.1], [[lambda].sup.(l).sub.2], ..., [[lambda].sup.(l).sub.N]], we convert the dual problem into a 2-D assignment problem by Lagrangian relaxation. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then the optimal objective function can be relaxed as follows,


Let [C.summation over (c=1)] [x.sub.m,m',c] = [[omega].sub.m,m'], then the modified dual function can be presented as,


Subject to:

[M.summation over (m=1)] [[omega].sub.m,m'] = 1 (13a)

[[omega].sub.m,m'], = [[omega].sub.m',m] (13b)

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 (m, [[eta].sup.(l).sub.m]).

Secondly, update the Lagrangian multipliers by the subgradient algorithm. We define [g.sup.(l)] as an N-dimensional subgradient vector with components given by,




The Lagrangian multipliers [[lambda].sup.(l+1).sub.n] (n = 1,2, ..., N) are updated via the following and the deduced process are not presented in this paper for the limited page.

[[lambda].sup.(l+1).sub.n] = [[lambda].sup.(l).sub.n] + ([beta]+1/[beta])([J.sub.[eta]] - J([[lambda].sup.(l)])/[parallel]g[[parallel].sup.2.sub.2]) [p.sup.(l).sub.n] (15)


[p.sup.(l).sub.n] = [p.sup.(l)] (n); [p.sup.(l)] = [H.sup.(l)][g.sup.(l)]; (16)


[J.sub.[eta]] = [1 + e/[[eta].sup.f]] [J.sup.*(l)] (18)

[J.sup.*(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 [less than or equal to] e [less than or equal to] 0.3 and 1.1 [less than or equal to] f [less than or equal to] 1.6. The parameter [eta]([eta] [greater than or equal to] 1) is incremented by 1 whenever J ([[lambda].sup.(l)]) < [J.sup.*(l-1)]. Otherwise, [eta] is updated via [eta] = max ([eta] - 1, 1). The parameter [beta] balances the convergence speed and solution accuracy and it is found that the iteration process works well when [beta] 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,


Subject to:




Finally, the converged conditions are examined to see whether the iteration should be terminated as the following rule,

gap = [absolute value ([[??].sup.*(l)] - [q.sup.*(l)])]/[[??].sup.*(l)] [greater than or equal to] min gap or l > L (20)

where mingap is the relative approximate duality gap; L is the maximum iteration time. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the optimal solution of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] problem (19). If Eq. (20) is satisfied, then the algorithm is terminated, the solutions of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 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.

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 [C.sup.U.sub.M] elements, where [C.sup.U.sub.M] represents the combination number of U taken from M. The number of columns of the 2-D matrix is ([N.sup.2] + N + 2)/2. Hence, it takes O(([N.sup.2] + N + 2) [C.sup.U.sub.M]/2) operations to solve the 2-D assignment problem. The storage capacity is at least O(([N.sup.2] + N + 2) [C.sup.U.sub.M]/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.sup.2] ([N.sup.2] + N + 2)/2), where L is the maximum iteration time. The storage capacity requirement in worst case is O ((U - 1)[M.sup.2] ([N.sup.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.

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 andM=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.

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.

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 > 16db 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.

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.

This research is supported by the National Natural Science Foundation of China (No.61201232,No. 61303251 and No.61302090) and Strategic Priority Research Program of the Chinese Academy of Sciences under grant XDA06010200.


[1] G. L. Nemhauser, L. A. Wolsey, Integer and Combinatorial Optimization, New York, Wiley-Interscience, 1988. Article(CrossRefLink)

[2] Ian C. Wong, Oghenekome Oteri and Wes McCoy, "Optimal Resource Allocation in Uplink SC-FDMA Systems," IEEE Transactions On Wireless Communications, vol. 8, no. 5, May, 2009. Article(CrossRefLink)

[3] Moray Rumney, 3GPP LTE: Introducing Single-Carrier FDMA, Agilent Measurement Journal, 2008. Article( CrossRefLink)

[4] J. W. Kim, I. S. Hwang and C. G. Kang, "Scheduling for virtual MIMO in single carrier FDMA (SC-FDMA) system," in Proc. Of 2010 Inf. Commun. Technol. Convergence Conf, pp. 115-119. Article(CrossRefLink)

[5] M. A. Ruder, D. Ding, U. L. Dang and W. H. Gerstacker, "Combined user pairing and spectrum allocation for multiuser SC-FDMA transmission," in Proc. of 2011 IEEE International Conf. Commun., pp. 1-6. Article(CrossRefLink)

[6] Jiancun Fan, Geoffrey Ye Li, Qinye Yin, Bingguang Peng and Xiaolong Zhu, "Joint User Pairing and Resource Allocation for LTE Uplink Transmission," IEEE Transactions On Wireless Communications, vol. 11, no. 8, August, 2012. Article(CrossRefLink)

[7] J. Torres, V. Morillo-Velarde, B. Soret, M. C. Aguayo-Torres and J. T. Entrambasaguas, "Cross-layer user multiplexing algorithms evaluation in MIMO OFDM wireless systems," in Proc. of IEEE 16th IST, pp. 1 - 5, July, 2007. Article(CrossRefLink)

[8] C. Sacchi, F. Granelli, C. Schlegel, "A QoE-Oriented Strategy for OFDMA Radio Resource Allocation Based on Min-MOS Maximization," IEEE Communications Letters, vol.15, no.5, pp. 494-496, 2011. Article( CrossRefLink)

[9] Pablo Ameigeiras , Juan J. Ramos-Munoz, Jorge Navarro-Ortiz a, Preben Mogensen and Juan M. Lopez-Soler, "QoE oriented cross-layer design of a resource allocation algorithm in beyond 3G systems," Computer Communications, vol.33, pp. 571-582, 2010. Article(CrossRefLink)

[10] M. Nasimi, Serdang Malaysia, M. Kousha and F. Hashim, "QoE-oriented cross-layer downlink scheduling for heterogeneous traffics in LTE networks," in Proc. of 2013 IEEE Communications Conf., pp. 292 - 297, Nov. 2013. Article(CrossRefLink)

[11] Bingquan Li, Shuo Li, Chengwen Xing, Zesong Fei, Jingming Kuan, "A QoE-based OFDM Resource Allocation Scheme for Energy Efficiency and Quality Guarantee in Multiuser-Multiservice System," in Proc. of 2013 IEEE GC Workshop, pp.1293-1297,Dec. 2012. Article( CrossRefLink)

[12] Gerardo Gomez, Javier Lorca, Raquel Garcia and Quiliano Perez, "Towards a QoE-Driven Resource Control in LTE and LTE-A Networks," Journal of Computer Networks and Communications,vol.2013,2013. Article(CrossRefLink)

[13] Miha Rugelj, Urban Sedlar, Mojca Volk, Janez Sterle, Melita Hajdinjak, and Andrej Kos, "Novel Cross-Layer QoE-Aware Radio Resource Allocation Algorithms in Multiuser OFDMA Systems," IEEE Transactions On Communications, vol. 62, no. 9, Sep. 2014. Article(CrossRefLink)

[14] Yujae Song, Daejeon, Youngnam Han and Yonghoon Choi, "A QoE-aware joint resource allocation algorithm for uplink carrier aggregation in LTE-Advanced systems," in Proc. of 2014 IEEE ICC, pp.1-5, Jun. 2014. Article(CrossRefLink)

[15] 3GPP TR 36.942 V.8.1.0, "E-UTRA: Radio Frequency (RF) system scenarios," December, 2008. Article(CrossRefLink)

[16] ITU-T SG12, "Definition of Quality of Experience," COM12-LS 62-E, TD 109rev2 (PLEN/12), Geneva, Switzerland, January 16-25, 2007. Article(CrossRefLink)

[17] P. Reichl, S. Egger, R. Schatz and A. D. Alconzo, "The Logarithmic Nature of QoE and the Role of the Weber-Fechner Law in QoE Assessment," in Proc. of IEEE ICC 2010, pp. 1-5. Article(CrossRefLink)

[18] M. Fiedler, T. Hossfeld and T.-G. Phuoc, "A generic quantitative relationship between quality of experience and quality of service," IEEE Network, vol.24, no.2, pp. 36-41, 2010. Article(CrossRefLink)

[19] F.Chen, X.W.Qin and G.Wei, "QoE optimized resource allocation in multiuser OFDM systems," przeglqd elektrotechniczny, pp.328-331, 2012. Article(CrossRefLink)

[20] S. Deb, M. Y. K. PATTIPATI and Y. BAR-SHALOM, "A Generalized S-D Assignment Algorithm for Multisensor-Multitarget State Estimation," IEEE Transactions on Aerospace and Electronic Systems, vol.33, pp. 523 - 538, 1997. Article(CrossRefLink)

[21] Krishna R. Pattipati, Somnath Deb,Yaakov Bar-Shalom and Jr . Robert B. Washburn, "A New Relaxation Algorithm and Passive Sensor Data Association," IEEE Transactions On Automatic Control, vol. 31, no. 2, February, 1992. Article(CrossRefLink)

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.

YaHui Hu (1), Song Ci (2)

(1) State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences Beijing, China 100190 [e-mail:]

(2) Dep. of Computer and Electronics Engineering, University of Nebraska-Lincoln 200B Peter Kiewit Institute, Omaha, NE 68182 [e-mail:]

* Corresponding author: YaHui Hu

Received January 7, 2015; revised April 12, 2015; accepted May 6, 2015; published October 31, 2015

Table 1. The modified Lagrangian relaxation algorithm

01: Input: P, [H.sub.n] (n [member of] [1, NK]), [alpha], B,
[SE.sub.max], [[gamma].sub.min] [[gamma].sub.max];
           [R.sup.(m).1.0], [R.sup.(m).sub.4.5], m [member of]
           [1, M], i [member of] [1, NK];
           e, f, [eta], [beta], min gap, L.

02: Output: Optimal allocation outcome [x.sub.m,m',c*];

Procedure of obtaining [a.sup.(m)] and [b.sup.(m)]
03: for( m = 1; m [less than or equal to] M; m + +)
04:    Obtaining [a.sup.(m)] by Eq.(5);
05:    Obtaining [b.sup.(m)] by Eq.(6);
Procedure of obtaining [MOS.sub.m,m',c] and [MOS.sub.m',m,c]
07:for( m = 1; m [less than or equal to] M; m + +)
08:   for(m' = m; m' [less than or equal to] M; m' + +)
09:     for (c = 1; c [less than or equal to] C; c + +)
10:        obtaining [[gamma].sub.m,c] and [[gamma].sub.m',c] by
11:        obtaining [R.sub.m,c] and [R.sub.m',c] by Eq.(3);
12:        obtaining [MOS.sub.m,m',c] and [MOS.sub.m',m,c] by Eq(4);
13:     end
14:  end
Procedure of The modified Lagrangian relaxation algorithm
16:Initiating [[lambda].sup.(0).sub.n] = 0, (n [member of][1, N]), e,
f, L, min gap, [beta].
17:While (gap = [absolute value of [f.sup.(l)] - J([[lambda].sup.(1)])
   ]/[[??].sup.(l)] > min gap or l [less than or equal to] L)
18: Getting the dual solutions J([[lambda].sup.(l)]), (m,[m.sup.(l)])
    of problem (8) by the processing of Eqs.(13)-(13b)
19: Updating the Lagrangian multipliers [[lambda].sub.n.sup.(l)] (n
    [member of][1,N])by the processing of Eqs.(15)-(15c)
20: Getting the feasible solutions [MATHEMATICAL EXPRESSION NOT
    REPRODUCIBLE IN ASCII] *by the processing of Eqs.(16)-(16c)

Table 2. Applications in each class

Simulation parameters                    Value

Transmit power on each subcarrier          1w
Carrier frequency                         2GHz
Sampling frequency                      1.92GHz
Transmit time interval duration           1ms
System bandwidth                         1.4MHz
Subcarrier spacing                       15kHZ
FFT size                                  128
Subcarrier number                          72
K                                          12
N                                          6
UE antenna number                          1
BS antenna number                          2
[[R.sup.(vs).sub.1.0],               [400,1100]kpbs
[[R.sup.(vs).sub.1.0],               [100,500]kpbs
[[R.sup.voice.sub.1.0],               [6.4,64]kpbs
[[R.sup.(FTP).sub.1.0],              [200,800]kpbs
[[gamma].sub.min]                        -10db
[[gamma].sub.max]                         15db
[SE.sub.max]                            2bps/HZ
COPYRIGHT 2015 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Hu, YaHui; Ci, Song
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Oct 1, 2015
Previous Article:Prediction-based routing methods in opportunistic networks.
Next Article:A novel jamming detection technique for wireless sensor networks.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |