Multiuser Resource Allocation Maximizing the Perceived Quality

In the considered shared wireless downlink the resources are divided into slots occupying a given bandwidth and time, which can be flexibly allocated to users. A scenario where mobile users travel with potentially high velocities is considered. The high dynamics of the time varying channel prohibit the utilization of instantaneous CSIT. However, long-term CSIT that includes distance dependent path loss and log-normal shadowing is assumed to be available. As the long-term CSIT is constant over the whole frequency band, multiuser scheduling corresponds to the well known packet-based generalized processor sharing (PGPS) [23]. A PGPS scheduler aims to assign slots to user proportionally to a coefficient , which serves as input parameter for the scheduler, as illustrated in Figure 1.

The long-term CSIT allows to extract the average signal-to-noise ratio (SNR) for user , which is used to select an appropriate modulation and coding scheme for the respective user. The spectral efficiency of the selected symbol mapping and coding scheme for user is denoted by in  [bit/s/Hz]. Denote the number of symbols per slot by ; the number of transmitted information bits per slot for user amounts to . Given user is assigned all available slots exclusively, the maximum achievable data rate yields . The actual data rate to user by the PGPS scheduler is then given by

Additionally, the constraints

need to be fulfilled with being the set of all users; that is, the amount of assigned resources cannot be negative and the sum of all assigned resources equals the available resources.

The objective MOS is recommended as utility metric for voice transmission by the ITU-T [18] as a measure for the user satisfaction. Practically, the MOS may take values between 1 (not acceptable) and 4.5 (very satisfied). In [15], the MOS is extended to other services like video streaming, file download, and web browsing. The obtained mathematical model of the user-perceived quality can be used as universal utility metric for CLO, allowing for joint optimization of different application classes.

The application characteristic is mainly influenced by data rate and packet losses, described by the applications' rate-loss distortion [24]. In this paper, the perceived quality is exclusively expressed as a function of the data rate , while packet losses are not considered as an explicit parameter. While this conveniently simplifies the analysis, this choice requires some further motivation, since certain kinds of source encoded bit-streams are sensitive to packet losses [11].

Packet losses may be caused by transmission errors over the mobile radio channel or by system overload. Regarding the wireless channel the link layer may compensate for packet losses by means of adaptive modulation and channel coding in combination with automatic repeat request (ARQ). While link adaptation ensures that transmission errors occur with low probability, low latency retransmissions of erroneous packets within the link layer [6] maintain reliable delivery of packets, at the expense of a certain rate reduction.

In an overloaded scenario, the offered load by the APP layer exceeds the capacity of the wireless link. Such an overload scenario can be effectively avoided by a fine grained adjustment of the offered data rate at the APP layer so as to match the capacity of the wireless link.

For instance, in case of video streaming, transcoding [9] or using the SVC extension of H.264/MPEG-4 AVC [7, 8] allows to vary the data rate in a rather fine granularity. As packets can be dropped at either the application server or the base station, a low latency rate adaption mechanism is feasible, at the same physical location as the scheduler in the MAC layer, effectively allowing to express perceived quality by data rate.

Moreover, the possibility to selectively drop packets offers one further opportunity to adjust the data rate. Likewise, for file downloads the data rate can also be adjusted in arbitrarily small steps. Hence, it is reasonable to assume that the application data rates can be adjusted continuously.

A major challenge in cross-layer design is the abstraction of parameters exchanged as control information. In order to limit the amount of control information, we introduce a layer model at the optimizer that emulates the relevant characteristics of the layer. The parameters of the layer model are determined at the corresponding layer, and only these parameters are sent as control information to the optimizer. The optimizer then tunes the model so as to identify the operating modes that maximize the chosen utility, which are then fed back to the system layers.

Figure 4 demonstrates the difference between the proposed model-based approach, and conventional parameter abstraction based on operating modes (crosses) and points (circles) [11, 12, 21, 22]. The X-axis indicates the choice of one parameter , and the Y-axis indicates the corresponding utility metric . Depending on the choice of and further parameters that cannot be determined from Figure 4 different operating modes of the utility metric are achieved.

For instance, applied to a video stream the local utility could be the PSNR or MOS, and according to (2) the parameters might represent source coding parameters such as the chosen codec, the frame rate, and the data rate . As a second example, applied to the PHY layer the local utility might be the sum throughput of all users, and are parameters such as the channel coefficients or the velocity of the mobile terminal.

Following the conventional idea of parameter exchange, an intralayer optimization might deliver the subset of operating modes that maximize the utility function , called efficient set in [22], also known as Pareto frontier. These operating modes are the crosses being located on the curve in Figure 4. A subset of operating modes is selected as operating points (circles). These are provided to the optimizer, which performs CLO by choosing the overall best operating point.

The proposed layer model is the curve in Figure 4, which represents an approximation of the utility metric as a continuous function. As demonstrated in the following the proposed parameter abstraction by a layer model exhibits a significant advantage for multiuser resource allocation, due to the potentially large number of available slots.

The objective is to maximize the sum MOS of all users. With the specific link model (1) and application model (4) the optimization problem (14) can be formulated as follows:

subject to

As the above optimization problem is neither convex nor concave, we first define an idealized utility that produces a concave optimization problem.

Removing the bounds in the application model (4) results in an unbounded logarithmic relation between utility metric and data rate. The unbounded optimization problem is formulated as:

subject to

The optimization (19a) can be simplified as:

with the equivalent utility function

The vector contains coefficients that characterize the applications as defined in (4b).

Note that and, hence, the solution of the unbounded optimization problem is independent on the physical radio channel, characterized by , and only depends on , which is determined by the ratio between and .

For finding a closed form solution of the optimum resource assignment in (19), in the following we prove the concavity of the optimization problem, derive the optimum share of resources between two users, and find a solution for the absolute resource share of a user.

Reformulating the constraint (19c) as:

and inserting the result into (21) yields

Now, the first and second partial derivatives in directions of and can be determined,

Considering (4b) and (4d), it follows that so that

and

This means that the graph is strictly concave downwards and any extremum not being located on the domain borders maximizes the utility. Therefore, provided for all the following condition is satisfied

the global maximum is found. Setting (24) to zero yields

Likewise, the optimum share for user , , when is fixed, is determined by differentiating (24) with respect to and setting the result to zero, which corresponds to swapping users and in (30). By combining the result with (30) the dependency to other users disappears. This means that the relation between the optimum resource assignments of any two users, and , is independent of all other users' utility functions. After some algebraic manipulations the relation

between the optimization coefficients of users and is obtained.

For finding an absolute value for the optimization coefficients the relation (31) is inserted into the constraint (19c), which yields

as the final solution of the unbounded optimization problem (19).

As a special case it can be easily seen from (32) that if all users have the same parameter , then the resources are distributed equally to the users,

Interestingly, given that all users use the same application, the optimum resource allocation for the unbounded problem results in an equal resource scheduler where all users are assigned the same number of slots. This implies that users experiencing a good channel receive higher data rates and therefore enjoy better QoS, as adaptive transmission is more bandwidth efficient in this case.

In summary, the optimum resource allocation for the unbounded optimization problem (32) is independent of the channel conditions; the number of assigned slots (the allocated bandwidth) is exclusively determined by the application characteristics; users with a good channel enjoy higher data rates. On the other hand, all users are given a fair share of the available resources. This is in a sharp contrast to a maximum throughput scheduler, which exclusively serves good users while users experiencing a poor channel starve for resources. The significance of this finding is that the maximized utility in (19) is an idealized measure of user-perceived quality.

For solving the bounded optimization problem (18), it is useful to solve the unbounded problem only for a subset of "variable" users . The remaining users have fixed optimization coefficients and are not subject to optimization. Here, the notation denotes the relative complement of set in set .

The constraint (19c) is rewritten as

Following the derivation in Section 4.2, inserting (31) gives

which finally yields

We define the upper bounded application characteristic by

which gives the upper bounded optimization problem

subject to

Let denote the optimum rate allocation of user of the unbounded problem (32). In case , the rate for user may be reduced to without sacrificing service quality, and the retained resources can be given to users with , . A solution of this concave problem is found by the iterative algorithm:

Step 1.

Initially, and .

Step 2.

Solve unbounded problem (36).

Step 3.

Users with are moved from to and set .

Step 4.

If any user has been moved in Step 3, continue with Step 2, otherwise stop.

If any of the application characteristics deviates from (4), Step 2 can be replaced by a conventional algorithm that solves the unbounded problem. Alternatively, appropriate values for and can be chosen to approximate the real application characteristic, giving rise to a certain deviation to the exact solution. Optionally, this approximation could be used as a starting point for an applicable conventional algorithm.

We approach the bounded optimization problem (18) by dividing it into two subproblems: first, a subset of users is determined who cannot be served and therefore get no resources, ; second, for the remaining users the upper bounded optimization problem from Section 5.1 is solved. In case dropped users are selected appropriately in the first step, the remaining served users will always achieve data rates so that the solution for the bounded problem is optimum.

The following iterative algorithm for the solution of the bounded problem is formulated as follows.

Step 1.

Initially, all users are served.

Step 2.

Drop users as detailed in Steps 2.1–2.4.

Step 2.1.

If is fulfilled, continue with Step 3.

Step 2.2.

Solve upper bounded problem for the served users as described in Section5.1.

Step 2.3.

User is dropped by setting .

Step 2.4.

Continue with Step 2.1.

Step 3.

Solve upper bounded problem for the served users as described in Section 5.1 and stop.

In this algorithm the determines how many users are served. When the objective is to maximize the sum of all users' MOS, referred to as "increase sum MOS", an appropriate strategy is to continue dropping users until this does not further improve the sum MOS.

An alternative is to check

where

This condition checks whether the MOS that would be achieved with the allocated resources exceeds a certain minimum . Setting ensures that only a minimum of users are dropped, while no resources are wasted to users that would anyhow experience unacceptable service quality of . On the other hand, higher values of enforce a certain minimum perceived quality. This variant of the algorithm is therefore termed "reduce outage".

As the above discussion touches upon the issue of admission control, other criteria that determine which users are admitted to the system might be introduced. For example, in a cellular system it might be desirable to give priority to users that hand over from a neighboring cell rather than to serve a user who wishes to enter the network.

An appealing feature is that the proposed optimization algorithm deterministically terminates after a certain time. To prove this the worst case run time is calculated in the following. Since in each iteration at least one user is dropped, there are at most iterations in the outer loop. The inner loop computes the solution of the upper bounded problem. In the worst case, one user is moved from to so that the number of iterations at most equals the number of served users. The total number of iterations is therefore upper bounded by .

An observation from the simulation results in Section 6 is that typically most users can transmit. Hence, the number of iterations for the outer loop is likely to be significantly smaller than . Likewise, trials suggest that for the inner loop it is rather unlikely that more than two iterations are required. Since the essential calculation within the inner loop is given by the closed form expression (36), the total complexity of the optimization algorithm is low.

In order to support different priority classes, the utility function is adjusted in the following.

Let be a real number that reflects the priority of user where, without loss of generality, indicates that user has a higher priority than user . Priority classes are incorporated to the utility function by substituting the application dependent constant in (19) by the function , that is,

In the calculation of the first and second partial derivatives in direction of and in (24), (25), and (26), is treated as a constant. Therefore, the derivation of the unbounded optimization problem in Section 4.2 also applies to the priority function , if the following condition holds

Likewise, (4b) and (4d) strictly require a positive constant , which translates to

Under these conditions, the conclusions from Section 4.2 apply: the utility function that supports priority classes (40) is strictly concave downwards, and the underlying optimization problem is solved by substituting with in (31), (32), and (36).

An intuitive realization of a priority function that satisfies the constraints (41) and (42) is given by

which is similar to the approach described in [19]. This function is applied for obtaining the numerical results presented in Section 6.5.

There are several possibilities how to further incorporate priority classes, for example, by adjusting the upper bound of the upper bounded optimization problem, the stop criterion or by using an alternative criterion for dropping users.

We consider an OFDMA downlink that occupies a bandwidth of . Due to the inherent orthogonality of orthogonal frequency division multiplexing (OFDM), each subcarrier in each OFDM symbol may be assigned to a different user without causing interference, so that users can be scheduled independently in time and frequency. Adjacent subcarriers and OFDM symbols are correlated and, therefore, experience a similar channel gain. In order to limit the signaling overhead symbols are grouped to form one slot.

The WINNER typical urban macrocell channel (model C2 [28]) is used, which models channel attenuation due to frequency selective fading, distance dependent path loss and log-normal shadowing [29]. Instantaneous channel variations due to velocities of mobile users are generated using Jakes' model [30]. The channel model is implemented such that the average SNR always allows transmission with the lowest supported modulation and coding scheme. This is motivated by the fact that users with lower SNR would not be able to establish a connection to the base station and, hence, cannot request to be served. While the average SNR always exceeds the given limit, the instantaneous SNR may be significantly lower due to frequency selective fading.

Mobile velocities up to are assumed, which implies that instantaneous CSIT may not be available. It is assumed that the average SNR over all simultaneously transmitted slots is available for link adaptation. Hence, the same modulation and coding scheme is applied to all subcarriers of one user during one slot duration. However, slots assigned to different users will typically use a different modulation and coding scheme.

The transmitter chooses the symbol mapping with cardinality and code rate of a convolutional code, based on the average SNR of each user (see Figure 6). Note that due to half-duplex transmission the average data rate is only half of the instantaneous data rates indicated in Figure 6. The modulation and coding scheme is selected that achieves the largest spectral efficiency at a frame error rate (FER) of . The SNR values for which are determined by reference simulations and are stored in a look-up table. It is assumed that an ARQ protocol at the link layer takes care of error events by retransmitting erroneously received packets. Due to the low occurrence of errors at retransmissions only have marginal impact on the throughput and will therefore not affect the perceived quality. Hence, simulations assume that packets are always received error free.

For CLO the long-term average data rate for each user indicates the link capacity and is the relevant abstraction of the link layer. Figure 7 shows the cumulative distribution function (CDF) of , which is averaged over a large number of randomly chosen channel realizations and user locations within a cell.

Simulations are executed as follows: every 100 milliseconds independent shapshots of path loss and shadowing realizations are generated for each user according to a uniform user distribution within the cell area. Then is estimated and passed to the optimizer. CLO is performed to determine the optimum share of resources , which is subsequently fed back to the PGPS scheduler at the MAC layer.

After the 100-millisecond snapshot, the actually achieved average data rates are determined. The actually achieved data rates may deviate from the optimizer's estimate . Each user's MOS is determined based on the user's application and the achieved data rate. Then, the CDF of the MOS averaged over all users is calculated.

In Figure 8, the CDF of the MOS is shown for the different resource allocation strategies and optimizer variants discussed in Section 5. The applications of all users are described by the same parameters and (compare Figure 5). As a reference equal resource allocation with for all 16 users is also plotted, which is the optimum resource assignment of the unbounded optimization problem (19) (see Section 4.2). Greedy resource allocation [19], as a conventional technique for solving optimization problems, is also included for comparison. From our experience the Greedy algorithm is significantly more computationally expensive than the proposed CLO algorithm. The other two curves show the performance of the proposed algorithm, the "increase sum MOS," and the "reduce outage" variants, where the stop criterion is set to .

As seen in Figure 8, both variants outperform equal resource allocation and achieve a comparable average MOS as greedy resource allocation. Compared to equal resource allocation, any performance improvement of the considered optimization algorithms is due to the bounds in the MOS trajectory, since users with perceive the same QoS as if they were served with the reduced rate . Likewise, users with perceive the same QoS as a user who is not served at all. The "reduce outage" variant serves practically all users, although some perceive a poor service quality. In contrast, the "increase sum MOS" variant tends to drop users with poor quality and assigns the freed resources to served users. This is due the objective, which aims to maximize the sum MOS of all users: a user will be dropped, if the increase in MOS of the served users outweighs the decrease in MOS of dropping a certain user.

In Section6.2, the application is characterized by the idealized bounded logarithmic relationship (4), so that the APP layer model at the optimizer perfectly matches the application characteristics. In order to assess the benefits of CLO in a real system with real applications running, a video streaming example is chosen where the user-perceived quality is approximated as described in Section 2.2.1. Eight different H.264/MPEG-4 AVC videos in common intermediate format (CIF) resolution at frame rate are cut into snippets containing one group of pictures (GOP) each. With a GOP size of 32 frames the snippets contain approximately 1 second of video. Further parameters of the videos are summarized in Tables 3 and 4. The snippets are subsequently analyzed to extract the parameters , , and for each snippet.

In order to assess the effect of rate variations of the video stream over time, for each 100-millisecond PHY channel snapshot a new (random) snippet of the respective video stream is used. For the proposed optimization algorithm from Section5 the parameters and are estimated by the application server for each video snippet and provided to the CLO. Because the optimization algorithm is based on the bounded logarithmic relationship (4), which deviates from the actually used video model (3), the decided resource distribution will be suboptimum. For comparison CLO with greedy optimization using the exact video model (3) is also simulated.

As seen in Figure 9, for the considered real video streams similar conclusions as for the generic applications from Section 6.2 can be drawn. The considered optimizers exhibit similar performance, achieving a significantly superior MOS with respect to equal resource allocation.

It may be desirable to support the demand for minimum QoS. This may be accomplished by tuning the parameter of the stop criterion in the "reduce outage" variant of the proposed optimization algorithm. As the stop criterion controls which users are dropped from the list of active users (see Section5.2), setting to a value in the range ensures that all served users achieve at least a minimum perceived quality of .

Figure 10 shows the CDF of the achieved sum MOS for and . The higher the less users achieve the required data rates due to poor channel conditions and are therefore not served. On the other hand, the served users with better channels benefit from freed resources of the dropped users, which improves their perceived quality.

Figure 11 shows the MOS, averaged over all users and channel realizations, against . The choice of affects the overall perceived quality and the maximum is approached for . In case , users with poor channels are served, which have only a marginal contribution to the overall sum MOS. On the other hand, if , an increasing number of users are denied service, which cannot be compensated by the enhanced QoS of the remaining active users. The perceived quality achieved by the "increase sum MOS" variant, which approximates the maximum sum MOS, is also indicated in Figure 10.

The performance of CLO supporting different traffic priority classes developed in Section 5.4 is examined in Figure 12. The users, all running the same applications, are split up into two priority groups of 8 users each; premium and ordinary users are given a priority of and , respectively.

Figure 12 shows the CDF of the sum MOS. Premium users exhibit a significantly better MOS than ordinary users and are more likely to be served.

In order to identify for which application characteristics CLO is most effective, different generic application classes are examined, characterized by their relationship between data rate and perceived quality as described by the parameters and (see Figure 5), for the "increase sum MOS" variant of the proposed optimization algorithm. The application characteristics are the same for all users and is chosen. Figure 13 shows the average MOS against the required data rate for a maximum perceived quality of , for a system with users.

As seen from Figure 13, the attainable gains of CLO maximizing the sum MOS (solid lines) over equal resource allocation (dashed lines) are dependent on both and the ratio . For low data rate requirements the CLO gain diminishes, as there is an excess of available resources to serve all users with excellent quality . For increasing data rate requirements the CLO gain depends on the ratio , in the way that the CLO gain increases with decreasing . This is explained by the fact that for an increasing ratio the MOS characteristic as a function of the data rate, in (4), approaches the unbounded problem addressed in Section 4.2, for which according to (33) equal resource allocation is optimum. In other words, the attainable CLO gains over equal resource allocation with are due to users whose rates are outside the logarithmic range of . As the logarithmic range is specified by the ratio , the lower the higher the gains to be achieved by optimization.

In Figures 14–16 a scenario with two user groups is investigated. Each of the two user groups run applications of a different service class, characterized by different data rate requirements, as illustrated in Figure 14. Low- and high-rate users request a minimum data rate and , respectively.

Figure 15 shows the CLO gain in sum MOS relative to equal resource allocation against the number of users in each group. Results are plotted for different values of and , for a total number of users and . Interestingly, in some cases the overall MOS gain for scenarios with mixed service classes exceeds the case when all users are within either of the service classes. This is due to the freed resources by replacing a high-rate user by a less demanding low-rate user, which allows the remaining users to fetch some of the freed resources.

The relationship between low- and high-rate users is further investigated in Figure 16, which shows the CDF of the sum MOS for both user groups. Corresponding to the maximum in Figure 15, there are 4 users with and 12 users with . An appealing observation is that both user groups gain from CLO. While the average gain is , low- and high-rate users gain and in overall perceived quality, respectively.

In order to assess the attainable MOS gains from a system level perspective, the average sum MOS is plotted against the number of users in Figure 17. Two scenarios are investigated. In scenario 1, there are two groups with equal number of users, where low- and high-rate users request the rate and , respectively. It can be deduced from Figure 17 that CLO maximizing the sum MOS (solid lines) increases the number of users being served with the same average perceived quality by more than , compared to equal resource allocation (dashed lines). In scenario 2, all users run the same application with a desired data rate of and , which achieves a comparably small MOS gain of at most , as reported in Section6.6 for users. In scenario 2, CLO also enables to serve more users with the same perceived quality, although in this case the gains diminish for increasing number of users. In line with the discussion in Section 6.6, for scenario 2 gains of CLO over equal resource allocation are mainly in the region where the sum MOS is high, since then users, whose rate is outside the logarithmic range of in (4), are more likely. Otherwise, equal resource allocation tends to approach the optimum resource allocation strategy, leading to diminishing CLO gains.