1 Introduction

Resource allocation in wireless networks has been an active research topic in recent years (see, for example [4, 5, 10, 13, 14, 16, 23, 24, 26, 31]). This issue is still an open challenge due to its complexity nature that, in a wireless network the available resource is limited, the channel quality of each user may be various, the traffic type is of being diverse, and all these factors must be taken into account in any workable resource allocation scheme. If the channel quality, the total available resource are known in prior, the wireless system resource can be allocated among users according to some performance metrics, such as throughput and fairness [4, 5, 10, 13, 14] or according to the traffic types [7, 19, 24]. For the aim of maximizing the system throughput, the wireless system may allocate more resource to users with better channel quality. In contrast to this, if the system attempts to provide fair treatment to all users, the wireless system tends to allocate more resource to users with worse channel quality, so as to compensate for the resource loss due to their poor channel conditions [27]. Correspondingly, there are throughput-oriented [4, 32] or fairness-oriented [10, 27] algorithms recently being proposed, which allow the system to behave either in throughput enhanced or fairness enhanced manner.

In a wireless network with a single source, a single destination and an arbitrary number of relay nodes, the paper [2] proposes a two-step approach to maximize the wireless network capacity. In [9], the authors consider the problem of maximizing wireless network capacity (a.k.a. one-shot scheduling) in both the protocol and physical models. In [22], it is pointed out that Wi-Fi clients can obtain much better performance at some commercial hot spots than others. Unfortunately, there is currently no way for users to determine which hot spot access points (APs) will be sufficient to run their applications before purchasing access. In order to quantify the energy efficiency of a wireless network, the power consumption of the entire system needs to be captured. In [1], the necessary extensions with respect to the existing performance evaluation frameworks are presented. Other relevant work on the subject of resource allocation and management in wireless networks includes [11, 15, 17, 18, 25, 29, 30].

The currently served traffic in networks including the Internet can be classified into three groups, they are the best effort (BE) traffic, the Hard quality of service (QoS) traffic and the Soft QoS traffic. Further, we often group the last two types into one, i.e. the QoS traffic. In [19], the authors propose a method to find the resource allocation in a wireless network, where only the BE traffic and the Hard QoS traffic are assumed to appear in the network. Unfortunately the Soft QoS traffic is not considered in that approach. In [20] and [21], the authors discuss the issue of resource allocation among Soft QoS traffic. However, the proposed method is applicable to the scenario where only Soft QoS traffic alone appears in the network. Nevertheless, the obtained solution therein is sub-optimal not optimal. The recent paper [28] proposes a scheme to the utility-based resource allocation for Soft QoS traffic in a wireless network, where the approach gives the optimal solution. Again, the considered scenario is only applicable to Soft QoS traffic alone.

The paper [8] discussed the resource allocation problem in a network utility optimization model with mixture traffic, however the algorithm reported there is heuristic. Given all the above progress in this matter, it is seen to be an open challenge how to optimally allocate the resource among all user’s types including the BE traffic, the Hard QoS traffic and the Soft QoS traffic.

In this paper, to face the above challenge we use a unified utility function to describe all traffic types, in which the BE traffic, the Hard QoS traffic and the Soft QoS traffic are specified by a number of relevant parameters. We discuss the relation between the Hard QoS and Soft QoS in the utility form. The studied problem of resource allocation is then casted into a network utility maximization (NUM) model. We formulate fairness index explicitly in terms of users’ utility and traffic type parameters, and then study their relationships. We establish an important approach, namely PEDMU: principle of equality and diminishing marginal utility for deriving the desired optimal solution to the NUM model. We propose some crucial theorems and algorithms to find the optimal solution both for the case where the total resource is sufficient and for the case where the total resource is insufficient. The efficacy and efficiency of the proposed algorithm are validated by numerical examples. Our theoretical analysis and numerical results disclose the relationship between the optimal resource allocation and the factors of traffic types, total available resource and user’s channel quality. The relations between the fairness index and the users’ utility are discussed as well under the specific resource allocation schemes in the numerical examples.

The rest of the paper is organized as follows. Section 2 analyzes the utility function and the marginal utility function. Section 3 deduces the explicit formula of fairness index in terms of user’s utility and flow’s parameters. Section 4 presents the main results and the algorithm for solving the problem. Section 5 validates the proposed allocation schemes via simulation. Finally, the paper is concluded in Sect. 6.

2 Utility Function and Marginal Utility Function

Let us consider a wireless network consisting of a base station and a set of BE flows (users) and QoS flows (users). The set of all flows is denoted by \({\mathfrak {R}}\). Let \(R\) denote the total amount of resource available at the base station. Resource herein refers to the capacity used to transmit data, and is allocated by the base-stations controller. Such resource can be time-slots, codes, frequency and so on, depending on the type of the wireless network in use. Let \(r_m\) denote the amount of resource allocated to Flow \(m, m \in {\mathfrak {R}}\). Because in any wireless user its channel often varies over time due to fading and dynamically changing interference conditions [3], the efficiency of taking advantage of the allocated resource from its base station varies from flow to flow. We thus have the parameter \(q_m\) denote the channel quality of Flow \(m\), which represents the ratio of the actual amount of resource received by this user to the amount of resource allocated by its base station to it. Therefore, we have \(0 \le {q_m} \le 1\). The smaller the value of \(q_m\), the worse the channel quality and vise versa.

The resource requirement of each flow is described by a utility function \(U(.)\), which represents a degree of user’s satisfaction when being allocated by a certain amount of resource. It is a non-decreasing function as more resource is allocated to a user, it gains more satisfaction. The utility function can be derived from some metrics that depend on the type of traffic, the user’s perception or the content quality. In particular, for wireless multimedia stream users, the utility function depends on perceived signal-noise ratio or mean opinion score besides other QoS metrics.

The BE traffic includes the traditional data applications such as E-mail, file transfer and remote login. There is no minimum bandwidth (resource) requirement as it can tolerate relatively large delays. The Hard QoS traffic has audio/video phone, video conference and tele-medicine as its examples while Soft QoS traffic has interactive multimedia services and video on demand as its examples. The former has strict requirement on bandwidth while the latter has flexible requirement on bandwidth. For users with BE (BE) traffic, the utility function should be monotonically increasing since the system pursues the maximum aggregate utility. The derived function of the utility function should be decreasing function, which prevents assigning too much resource to the users and get little gain from the resource allocation of them. That is to say the utility function for BE users should be a convex function. The utility function of QoS traffic can be modeled on the basis of the following observation. When the amount of resource \(r_m\) is given insufficiently and too small, it is useless for real-time traffic; as \(r_m\) approaches the requested amount, the flow is gradually operational, and thus the marginal utility increases dramatically. Once the allocated resource \(r_m\) has exceeded the requested resource, allocating more resource makes little difference for operation, and thus the marginal utility drops hence forth. Consequently, a sigmoid function can be used to model the dynamics of the utility function for QoS users with respect to the allocated resource.

Suppose that \(r\) denotes the resource for the user, and \(U(r)\) denotes the utility of this resource. The base station will use \(U(r)\) to measure the utility of the user. The utility function for the BE traffic, the Hard QoS traffic and the Soft QoS traffic can be described by the following unified form.

The unified utility function for all traffic types is given [8] by

$$\begin{aligned} U(r)=\frac{1}{1+Be^{-C(r-r_0)}}+D. \end{aligned}$$
(1)

where \(B, C\) and \(D\) are the parameters to be determined for a specific traffic type. Parameter \(C\) determines the slope of the curve of the utility function. What’s more, \(C\) can be used to classify the Hard QoS traffic and the Soft QoS traffic. Parameters \(B\) and \(D\) mainly affect the range of the utility function. Through adjusting \(B\) and \(D\), the utility values of different traffic are comparable, which is helpful to the implementation of the resource allocation in the mixed traffic scenario. The point \(r_0\) between \([0, R]\) is of special interest, which is the inflexion point of the utility function and denotes the bottom resource requirement for resource. When the resource allocated to users is smaller than \(r_0\), the utility function is concave, which means that the user relies on that amount of resource strongly for normal operation; whereas when the resource allocated to users is larger than \(r_0\), the utility function is convex, which means that the user requires the resource of \(r_0\) weakly. For the users with QoS traffic, we have \(r_0 > 0 \). For the users with BE traffic, we have \(r_0 = 0\).

Fig. 1
figure 1

Utility functions of mixed traffic

Full size image

For any QoS traffic, if its inflexion point of resource requirement is \(r_{m_0}\), the derived function of the utility function \(u(r)= dU(r)/dr\) is called the marginal utility function, by denoting \(u'=d^2U(r)/dr^2\), one has [8]

$$\begin{aligned}&0 < {r_m} < {r_{{m_0}}},\quad u\left( {{r_m}} \right) > 0,u'\left( {{r_m}} \right) > 0,\nonumber \\&{r_{{m_0}}} \le {r_m} < R,\quad u\left( {{r_m}} \right) > 0,u'\left( {{r_m}} \right) \le 0. \end{aligned}$$
(2)

In economics, diminishing returns (also called diminishing marginal returns) is the decrease in the marginal (per-unit) output of a production process as the amount of a single factor of production is increased, while the amounts of all other factors of production stay constant.

The law of diminishing marginal utility (also law of diminishing marginal returns or law of increasing relative cost) states that in all productive processes, adding more of one factor of production, while holding all others constant (“ceteris paribus”), will at some point yield lower per-unit returns [6].

It is thus noted for the above QoS traffic, starting from the point \(r_m = r_{m_0}\), its marginal utility becomes diminishing. This is seen mathematically from, when \(r_{m_0}< r_m < R, u'\left( {{r_m}} \right) \le 0.\)

For any QoS traffic, the utility function takes the value between \([0, 1]\) and satisfies the following restrictions

$$\begin{aligned} U(0) \approx 0, U(R) \approx 1. \end{aligned}$$
(3)

For the BE traffic, its inflexion point of resource requirement is \(r_{m_0}=0\). The utility function has the following characteristics [8]

$$\begin{aligned}&u\left( {{r}} \right) > 0,u'\left( {{r}} \right) < 0, \quad \hbox{when} \, 0 < r < R,\end{aligned}$$
(4)
$$\begin{aligned}&U(0) \approx 0. \end{aligned}$$
(5)

For the BE traffic, it is noted that at any point its marginal utility is always diminishing.

According to the characteristics of different traffic type, the parameters \(B, C\) and \(D\) can be determined in the following manner. For the BE traffic, we can set \(B=1.5\) and \(D=-0.4\). This ensures that the utility of BE users is lower than that of QoS users when \(r > r_0\). The parameter \(C\) will be used to decide the explicit curve of the utility function of BE traffic, as discussed earlier. For the QoS traffic, to guarantee its utility function is larger than that of the BE traffic when \(r \gg {r_0}\), we set \(B = 1\) and \(D = 0\) hereafter. The parameter \(C\) can be determined by users.

Considering the general utility function given by (1), as an example we plot the utility function of six flows into Fig. 1 with three being the QoS traffic and the other three being the BE traffic. The parameters for the QoS traffic are set as \(B1=1, C1= 0.2, D1=0; B2=1, C2= 1, D2=0; B3=1, C3= 5, D3=0\), while the parameters for the BE traffic are set as \(B4=1.5, C4= 0.1, D4=-0.4; B5=1.5, C5= 0.4, D5=-0.4; B6=1.5, C6= 0.8, D6=-0.4\).

Based on above discussions, we are now able to give the utility function of QoS and BE traffic as follows. For the QoS traffic, the utility function can have the following form

$$\begin{aligned} U(r)=\frac{1}{1+e^{-C(r-r_0)}}. \end{aligned}$$
(6)

For the BE traffic, the utility function takes the following form

$$\begin{aligned} U\left( r \right) = \frac{1}{{1 + 1.5{e^{ - Cr}}}} - 0.4. \end{aligned}$$
(7)

Note that among the QoS traffic, the utility function of Hard QoS traffic is the extreme case of the general form

$$\begin{aligned} U\left( r \right) = \mathop {\lim }\limits _{C \rightarrow \infty } \frac{1}{{1 + {e^{ - C\left( {r - r_0} \right) }}}} = \left\{ \begin{array}{l} 1,\quad r \ge {r_0}\\ 0,\quad r < {r_0} \end{array} \right. \end{aligned}$$
(8)

Figure 1 shows the utility function with various parameter \(C\). When \( C > 18 \), the utility function be very close to the step function. Therefore, we will use Eq. (6) to model the utility of Hard QoS traffic.

Further to Figs. 1, 2 depicts their marginal utility function of the three BE traffic users and the three QoS traffic users under the specific setting of parameters. Observing from them, we see that Eqs. (2) and (4) are satisfied. That is, for QoS traffic when

$$\begin{aligned} 0 \le {r_m} < {r_{{m_0}}}, \end{aligned}$$

we have

$$\begin{aligned} u\left( {{r_m}} \right) \ge 0, u'\left( {{r_m}} \right) > 0; \end{aligned}$$

when

$$\begin{aligned} {r_{{m_0}}} \le {r_m} \le R, \end{aligned}$$

we have

$$\begin{aligned} u\left( {{r_m}} \right) \ge 0,u'\left( {{r_m}} \right) \le 0. \end{aligned}$$

For BE traffic, when

$$\begin{aligned} 0 \le {r} \le R, \end{aligned}$$

we have

$$\begin{aligned} u\left( {{r}} \right) \ge 0,u'\left( {{r}} \right) \le 0. \end{aligned}$$
Fig. 2
figure 2

Marginal utility function of mixed traffic

Full size image

3 Tradeoff Between Fairness and Utility

Fairness measures or metrics are used in network engineering to determine whether users or applications are receiving a fair share of system resources. There are several mathematical and conceptual definitions of fairness. Jain’s fairness index [12] is often used to determine the fairness of allocation scheme. Assuming there are \(M\) users and \(r_m\) is the rate of the \(m\)th user, the fairness index for the set of allocation ranges from \(1/M\) (the worst case) to \(1\) (the best case), and it is maximum when all users receive the same allocation.

Jain’s fairness index \(F\) can be described [12] as

$$\begin{aligned} F({r_1},{r_2},\ldots ,{r_m}) = \frac{{{{\left( {\sum \nolimits _{m = 1}^M {{r_m}} } \right) }^2}}}{{\left( {M\sum \nolimits _{m = 1}^M {{{\left( {{r_m}} \right) }^2}} } \right) }}. \end{aligned}$$
(9)

Due to the wireless communication loss, if the base station allocates an amount of \(r_m\) resource to User \(m\), it will only obtain the amount of the throughput \(r_m q_m\), where \(q_m\) is the channel quality of this user. Subsequently the fairness index should be modified as following

$$\begin{aligned} F({r_1},{r_2},\ldots ,{r_m}) = \frac{{{{\left( {\sum \nolimits _{m = 1}^M {{r_m}{q_m}} } \right) }^2}}}{{\left( {M\sum \nolimits _{m = 1}^M {{{\left( {{r_m}{q_m}} \right) }^2}} } \right) }}. \end{aligned}$$
(10)

The above equation gives us the formulation of the fairness index in terms of the resource allocation while Eq. (1) links the user’s utility value with the flow’s parameters. In the following, we will formulate the fairness index in terms of all users’ utility and their flow parameters. To this end, consider a wireless network with \(M\) users, their utility functions are in the same form, which are given by

$$\begin{aligned} {U_m} \buildrel \Delta \over = U({r_m}{q_m}) = \frac{1}{{1 + {B_m}{e^{ - {C_m}({r_m}{q_m} - {r_{{m_0}}})}}}} + {D_m}. \end{aligned}$$
(11)

By solving the above equation for the variable \(r_m q_m\) we arrive at

$$\begin{aligned} {r_m}{q_m} = {r_{{m_0}}} - \frac{1}{{{C_m}}}\ln \left[ {\frac{{\left( {1 - {U_m} + {D_m}} \right) }}{{{B_m}\left( {{U_m} - {D_m}} \right) }}} \right] . \end{aligned}$$
(12)

By substituting the above into (10), we have

$$\begin{aligned} F = \frac{{{{\left( {\sum \nolimits _{m = 1}^M {\left( {{r_{{m_0}}} - \frac{1}{{{C_m}}}\ln \left[ {\frac{{\left( {1 - {U_m} + {D_m}} \right) }}{{{B_m}\left( {{U_m} - {D_m}} \right) }}} \right] } \right) } } \right) }^2}}}{{\left( {M\sum \nolimits _{m = 1}^M {{{\left( {{r_{{m_0}}} - \frac{1}{{{C_m}}}\ln \left[ {\frac{{\left( {1 - {U_m} + {D_m}} \right) }}{{{B_m}\left( {{U_m} - {D_m}} \right) }}} \right] } \right) }^2}} } \right) }}. \end{aligned}$$
(13)

The importance of the above equation is that it relates fairness with utility. Given the fact that, it is usually difficult to achieve a satisfactory fairness level among various users with various channel quality under the utility optimal scheme, the above equation specifically gives us some guidelines in seeking a trade-off between the fairness and the system total utility.

As the first example, assuming in a wireless system there are three QoS flows with the same type of utility function given by (11) and with the following parameter settings: \(B_1 = B_2 = B_3 = 1, C_1 = 0.2, C_2 = 2, C_3 = 10, D_1 = D_2 = D_3 = 0, r_{1_0} = r_{2_0} = r_{3_0} = 20\). Using Eq. (13), we plot the relationship between the utility value \((U_1=U_2=U_3 \buildrel \Delta \over = U)\) and the fairness index into Fig. 3. From this plot, one observes the following interesting facts: first the fairness index approximates the maximum value when all the utility value of the three flows takes the value around the half; and second the fairness index goes around the minimum value when all the utility value of the three flows takes the maximum value.

Fig. 3
figure 3

Relationship between utility and fairness (only QoS)

Full size image

As the second example, assuming in a wireless system there are three BE flows with the same type of utility function given by (11) and with the following parameter settings: \(r_{1_0} = r_{2_0} = r_{3_0} = 0, B_1 = B_2 = B_3 =1.5, D_1 = D_2 = D_3 = -0.4\). We obtain the following relationship between the fairness index and the utility value \((U_1=U_2=U_3 \buildrel \Delta \over =U)\)

$$\begin{aligned} F = \frac{{{{\left( {\sum \nolimits _{m = 1}^3 {\frac{1}{{{C_m}}}} } \right) }^2}}}{3{\sum \nolimits _{m = 1}^3 {\left( {\frac{1}{{{C_m}^2}}} \right) } }}. \end{aligned}$$
(14)

It is interesting to note that, the fairness index becomes an constant between \([1/3, 1]\) independent of the slope parameter \(C\) for the three BE flows. That is to say, the fairness index is always kept at an constant for any resource allocation of a set BE flows with various slope parameters but with the same other remaining parameters. For example, when \(C_1 = 0.2, C_2 = 2, C_3 = 10\), we have \(F=0.4138\). If the slope parameter \(C\) for the three BE flows takes the same value, the fairness index will be equal to \(1\). This is to say, if in a wireless network there is only BE flow with the same parameter settings, the fairness index will achieve its maximum independent of the utility value of the users.

As the third example, assuming in a wireless system there are three BE flows and three QoS flows with the same type of utility function given by (11) and with the following parameter settings: three QoS users’ with parameter \(C_1 = 0.2, C_2 = 2, C_3 = 10, r_{1_0} = r_{2_0} = r_{3_0} = 20\); three BE users’ with parameter \(C_4 = 0.2, C_5 = 2, C_6 = 10, r_{4_0} = r_{5_0} = r_{6_0} = 0, B=1.5, D=-0.4\). We plot the relationship between the utility value \((U_1 = U_2 = U_3 = U_4 = U_5 = U_6 \buildrel \Delta \over = U)\) and the fairness index into Fig. 4.

Fig. 4
figure 4

Relationship between utility and fairness index (QoS and BE)

Full size image

4 The Num Model and its Solution

4.1 System Model

Let us consider in a wireless network there are a base station serving with \(M\) flows. We assume the first \(M_1\) flows are QoS flows and the remaining are BE flows. Let \(R\) denote the total amount of resource available at the base station. Let \(r_m\) denote the amount of resource allocated to Flow \(m\) and \(q_m\) denote the channel quality of it, where \(0 \le {q_m} \le 1\). The parameter \(C\) in Eq. (1) is specific to every flow and is denoted by \(C_m\) for Flow \(m\). The variable \(r_{m_0}\) denotes the inflexion point of the utility function of Flow \(m\). Note that for BE flows the inflexion point of the utility function equals to zero. The problem at hand is how to allocate the total resource among all users with the aim of maximizing the aggregate utility of users, which can be described into the following NUM model

$$\begin{aligned}&\max \left\{ O = {\sum \limits _{m = 1}^{M}} U\left( {r_m},{q_m},{C_m},{r_{m_0}} \right) \right. \nonumber \\&\qquad \qquad = {\sum \limits _{m = 1}^{M_1}} \left( \frac{1}{1 + e^{- {C_m}({r_m}{q_m} - {r_{m_0}})}} \right) \nonumber \\&\qquad \qquad \left. + \sum \limits _{m = {M_1} + 1}^M {\left( \frac{1}{1 + 1.5{e^{-{C_m}{r_m}{q_m}}}} - 0.4 \right) } \right\} \end{aligned}$$
(15)
$$\begin{aligned}&s.t.\sum \limits _{m = 1}^M {{r_m} \le R} ,\nonumber \\&{r_m} \ge 0,m = 1,2,\ldots ,M. \end{aligned}$$
(16)

Suppose that \({\mathfrak {R}}=\{r_1, r_2, \dots , r_m\}\) denotes a set of resource allocation for the users, \({R_{residue}}\) is the residue resource which is not allocated to the users (For all notations, refer to Table 1). That is to say, \( {R_{residue}} = R - \sum \nolimits _{{r_m} \in {\mathfrak {R}}}{{r_m}}\ge 0.\)

Table 1 Nomenclature
Full size table

Definition 4.1

A resource allocation \({\mathfrak {R}^*} = \left\{ {{r_1},{r_2},\ldots , {r_m}} \right\} (m=1,2, \dots , M)\) for \(M\) users is an optimal allocation if for all feasible allocations \({\mathfrak {R}_a} = \left\{ {{r_1}^\prime ,{r_2}^\prime ,\ldots {r_m}^\prime } \right\} , U\left( {{\mathfrak {R}^*}} \right) \ge U\left( {{\mathfrak {R}_a}} \right) \), where \(U\left( {{\mathfrak {R}^*}} \right) = \sum \nolimits _{i = 1}^m {{U}\left( {{r_i}, {q_i},{C_i},{r_{{i_0}}}} \right) }, U\left( {{\mathfrak {R}_a}} \right) = \sum \nolimits _{i = 1}^m {{U}\left( {{r_i}^\prime , {q_i} ,{C_i} ,{r_{{i_0}}} } \right) }\).

Definition 4.2

An allocation \({\mathfrak {R}}= \left\{ {{r_1},{r_2},\ldots ,{r_m}} \right\} \) is a full allocation if

$$\begin{aligned} \sum \limits _{\forall {r_i} \in {\mathfrak {R}}} {{r_i}} = R. \end{aligned}$$

Remark 1

If the allocation \({\mathfrak {R}^*}\) is the optimal one, it must be the full allocation [21]. The optimal allocation yielding the maximized total utility must be a full allocation, while on the contrary a full allocation is not necessarily the optimal allocation. Therefore, in the inequality (16), one can write the constraint as \( \sum \nolimits _{m = 1}^M {{r_m} = R}.\)

Based on the above discussions and the law of diminishing marginal utility that is widely accepted in economics, we set up the following important rule for utility optimized resource allocation in wireless networks.

Principle of equality and diminishing marginal utility (PEDMU): An allocation \({\mathfrak {R}}=\left\{ {{r_1},{r_2},\ldots ,{r_m}}\right\} \) satisfies PEDMU if the following three conditions hold

  1. (1)

    For each QoS user, we must give them the resource they basically request at the inflexion point, if the base station can satisfy their request;

  2. (2)

    For each unallocated BE user \(j\) in \({\mathfrak {R}}\), it’s marginal utility value should satisfy \({u_j}\left( 0 \right) \le {u_i}\left( {{r_i}} \right) \), where \({u_i}\left( {{r_i}} \right) \) is the marginal utility of each allocated user \(i\);

  3. (3)

    For each allocated user \(i\) and \(j\) in \({\mathfrak {R}}\), it should be satisfied \({u_i}({r_i}) = {u_j}({r_j}).\)

Remark 2

In PEDMU, the first two conditions are required by the law of diminishing marginal utility while the third one is a requirement on the equality of marginal utility. Specifically the first condition tells us, when the total resource of base station can satisfy the basic request of all QoS users, we should firstly allocate the resource to the QoS users. That is, when \(\sum \nolimits _{i = 1}^M {\left( {{r_i}_0/{q_i}} \right) } \le R,\) we must allocate \({r_i}_0/{q_i}\) to User \(i \, (i=1, 2, \ldots , M_1)\). This is based on the consideration that starting from the inflexion point, the QoS user becomes marginal utility diminishing. The condition (2) in in PEDMU poses the restriction on the unallocated user with \(r_m = 0.\) This takes into account that for BE user, at any point its marginal utility is always diminishing. The condition (3) in PEDMU tells one that the allocated user must have the equality of the marginally utility value. We will validate this condition later on.

In the following we will discuss two cases: where the total resource is sufficient and where the total resource is insufficient correspondingly.

4.2 The Total Resource is Sufficient

The total resource is sufficient, if the following inequality is satisfied

$$\begin{aligned} \sum \limits _{i = 1}^M {\left( {{r_i}_0/{q_i}} \right) } \le R. \end{aligned}$$
(17)

By noticing that, for the BE users r i0 = 0 (i = M 1 + 1,…, M), this case is actually the situation where the total resource is more than the QoS users requested. For this case, the principle for resource allocation is to allocate the total amount of resource \(\sum \nolimits _{i = 1}^{{M_1}} {{r_i}_0} /{q_i}\) to the \(M_1\) QoS users firstly, and then to allocate the residue resource among the QoS and BE users according to the marginal utility equality.

If the allocation set \({\mathfrak {R}}\) is the optimal one and \(u_j(r_j)\ne u_i(r_i)\). Assuming \(u_j(r_j) < u_i(r_i)\), because of the concavity of the utility function, its marginal utility function \(u(r)\) is decreasing. That is, we have \(r_j > r_i\). We should have \({r_j}^\prime , u_j({r_j}^\prime ) = u_i({r_i})\) and \({r_j}^\prime < {r_j}\). If we give \({r_j}-{r_j}^\prime \) to \(i\)th user, we have

$$\begin{aligned} \int _{{r_j}^\prime }^{{r_j}} {{u_j}\left( r \right) } dr < \int _r^{{r_i} + {r_j} - {r_j}^\prime } {{u_i}\left( {r_i} \right) } dr. \end{aligned}$$
(18)

Because for the User \(i\) and User \(j\), in the range of \([r_i,r_i+r_j-r_j^\prime ]\) and \([r_j^\prime ,r_j]\) we have \( u_i(r) > u_j(r) \). Equation (18) can be explained as follows. Suppose there are two allocation sets \({\mathfrak {R}}= \left\{ {{r_1},{r_2},\ldots ,{r_i},\ldots ,{r_j},\ldots ,\ldots ,{r_M}} \right\} \) and \({\mathfrak {R}^*} = \left\{ {{r_1},{r_2},\ldots ,{r_i} + {r_j} - r_j^\prime ,\ldots ,{r_j} - r_j^\prime ,\ldots ,\ldots ,{r_M}} \right\} ,\) The sum of utility for \({\mathfrak {R}}\) is

$$\begin{aligned} {O_1} &\mathop = \limits ^\Delta \left( {\sum \limits _{m = 1,m \ne i,m \ne j}^M {U\left( {{r_m},{q_m},{C_m},{r_{{m_0}}}} \right) } } \right) \nonumber \\& \quad +\, U\left( {{r_i},{q_i},{C_i},{r_{{i_0}}}} \right) + U\left( {{r_j},{q_j},{C_j},{r_{{j_0}}}} \right) . \end{aligned}$$
(19)

The sum of utility for \({\mathfrak {R}}^*\) is

$$\begin{aligned} {O_2}& \mathop = \limits ^\Delta \left( {\sum \limits _{m = 1,m \ne i,m \ne j}^M {U\left( {{r_m},{q_m},{C_m},{r_{{m_0}}}} \right) } } \right) \nonumber \\&\quad +\, U\left( {{r_i} + {r_j} - {r_j}^\prime ,{q_i},{C_i},{r_{{i_0}}}} \right) + U\left( {{r_j} - {r_j}^\prime ,{q_j},{C_j},{r_{{j_0}}}} \right) . \end{aligned}$$
(20)

Thus, we have

$$\begin{aligned} {O_2} - {O_1} &= U\left( {{r_i} + {r_j} - {r_j}^\prime ,{q_i},{C_i},{r_{{i_0}}}} \right) - U\left( {{r_i},{q_i},{C_i},{r_{{i_0}}}} \right) \nonumber \\&\quad +\, U\left( {{r_j} - {r_j}^\prime ,{q_j},{C_j},{r_{{j_0}}}} \right) - U\left( {{r_j},{q_j},{C_j},{r_{{j_0}}}} \right) \nonumber \\ & = \int _{{r_i}}^{{r_i} + {r_j} - {r_j}^\prime } {{u_i}\left( r \right) dr} - \int _{{r_j}^\prime }^{{r_j}} {{u_j}\left( r \right) } dr > 0. \end{aligned}$$
(21)

The above deductions suggest that, by giving the amount of resource \({r_j} - {r_j}^\prime \) to the \(i\)th user one will have more utility. This leads to a contradiction, therefore we have the following result.

If utility function of users are concave and \({\mathfrak {R}}\) is the optimal allocation scheme, we must have \(u_j(r_j) = u_i(r_i)\) (see also [21]). This also validates Condition (3) in PEDMU.

After allocating the total amount of resource \(\sum \nolimits _{i = 1}^{{M_1}} {{r_i}_0} /{q_i}\) to the \(M_1\) QoS users, we will only have \(R - \sum \nolimits _{i = 1}^{{M_1}} {{r_i}_0} /{q_i}\mathop = \limits ^\Delta {R_{residue}}\) resource. The total amount of resource \(R_{residue}\) will be allocated to \(M\) users, the feasible region for User \(m\) should be writen as \(\left[ {{r_{{m_0}}}/{q_m},{r_{{m_0}}}/{q_m} + R_{residue}} \right] .\)

If the utility function of users are concave and \({\mathfrak {R}}\) is the optimal allocation, we must have \(u_j(r_j) = u_i(r_i)\). For all of users, the utility function of them are concave in the feasible region, so we should allocate the resource to users with marginal utility equality, that is to say \(u_j(r_j) = u_i(r_i)\) for User \(i\) and \(j\), where \(r_i, r_j\) are in the range of

$$\begin{aligned} \left[ {{r_{{i_0}}}/{q_i},{r_{{i_0}}}/{q_i} + R_{residue}} \right] \end{aligned}$$

and

$$\begin{aligned} \left[ {{r_{{j_0}}}/{q_j},{r_{{j_0}}}/{q_j} + R_{residue}} \right] , \end{aligned}$$

respectively.

4.3 The Total Resource is Insufficient

The total resource is insufficient, if the following inequality is satisfied

$$\begin{aligned} \sum \limits _{i = 1}^M {\left( {{r_i}_0/{q_i}} \right) } > R. \end{aligned}$$
(22)

In this case we deal with the QoS users all as the Hard QoS user. For this case, the principle for resource allocation is either to allocate the full amount resource to the QoS user that they requested at the inflexion point or not to allocate any resource to them. We will first sort QoS users in the queue with the decreasing order by

$$\begin{aligned} \frac{{U_m}}{{q_m}{r_{{m_0}}}}\, U_m = U(r_{m_0}/{q_m}, q_m, C_m, r_{m_0}), \quad m = 1, \dots , M_1, \end{aligned}$$

then pop out the user at the head of queue and determine whether to allocate resource to them or not. For example, assuming the channel quality of User \(m\) is \(q_m (m = 1, \dots , M)\), whose requested resource at the inflexion point is \(r_{m_0}\). If the following condition holds

$$\begin{aligned} \int _{{R_{residue}} - {r_{{m_0}}}/{q_m}}^{{R_{residue}}} {{u_\Sigma }\left( r \right) } dr < {U_m}, \end{aligned}$$
(23)

then we serve the QoS User \(m\) and increase the utility of it to the value larger than the BE users. Note that \({u_\Sigma }\left( r \right) \) is the inverse function of \({u_\Sigma }^{ - 1}\left( u \right) \) given by

$$\begin{aligned} {u_\Sigma }\left( r \right) =\left\{ {u_\Sigma }^{ - 1}\left( u \right) \right\} ^{-1} = \sum \limits _{m = {M_1} + 1}^M {u_m^{ - 1}\left( u \right) }, \end{aligned}$$
(24)

where \(u_m^{ - 1}\left( u \right) \) is the inverse function of marginal utility function of User \(m\). The base station will allocate \(r_{m_0}/q_m\) to User \(m\) and then pop out the next user of head. Otherwise, it will allocate the remaining resource to BE users. So far, we are ready to present the following important theorem.

Theorem 4.3

For User \(m \,(m = 1, \dots , M_1)\) at the head of sorted queue, if

$$\begin{aligned} \int _{{R_{residue}} - {r_{{m_0}}}/{q_m}}^{{R_{residue}}} {{u_\Sigma }\left( r \right) } dr < {U_m}({r_{{m_0}}}/{q_m},{q_m},{C_m},{r_{{m_0}}}), \end{aligned}$$
(25)

then the optimal allocation is to allocate \(r_{m_0}/q_m\) to User \(m\).

Proof

Note that \({{u_\Sigma }\left( r \right) }\) is the inverse function of \({u_\Sigma }^{ - 1}\left( r \right) \). The component

$$\begin{aligned} \int _{{R_{residue}} - {r_{{m_0}}}/{q_m}}^{{R_{residue}}} {{u_\Sigma }\left( r \right) } dr \end{aligned}$$

defines the utility value after the base station allocated the amount of resource \(r_{m_0} / q_m\) to the BE users. \({U_m}({r_{{m_0}}}/{q_m},{q_m},{C_m},{r_{{m_0}}})\) gives the utility of \(r_{m_0}/{q_m}\) allocated to QoS User \(m\). If

$$\begin{aligned} {U_m}({r_{{m_0}}/{q_m}},{q_m},{C_m},{r_{{m_0}}}) > \int _{{R_{residue}} - {r_{{m_0}}}/{q_m}}^{{R_{residue}}} {{u_\Sigma }\left( r \right) } dr, \end{aligned}$$

it is seen that allocating the amount of resource \(r_{m_0}/{q_m}\) to User \(m\) would have more aggregated utility. If

$$\begin{aligned} \int _{{R_{residue}} - {r_{{m_0}}}/{q_m}}^{{R_{residue}}} {{u_\Sigma }\left( r \right) } dr > {U_m}({r_{{m_0}}}/{q_m},{q_m},{C_m},{r_{{m_0}}}), \end{aligned}$$

it is seen that we can allocate \(R_{residue}\) to the BE users to achieve more aggregate utility. Because we either to allocate the full amount resource to the QoS user that they requested at the inflexion point or not to allocate any resource to them, so the allocation is the optimal allocation.□

In summary, for the case where the total resource is insufficient, we will sort the QoS users at the queue by \((U_{r_{m_0 } } q_m )/r_{m_0 } \) and then pop out user at the head of queue. By computing

$$\begin{aligned}&\Delta U \mathop = \limits ^\Delta {U_m}({r_{{m_0}}}/{q_m},{q_m},{C_m},{r_{{m_0}}}) \\&\qquad \qquad - \int _{{R_{residue}} - {r_{{m_0}}}/{q_m}}^{{R_{residue}}} {{u_\Sigma }\left( r \right) } dr, \end{aligned}$$

if \(\Delta U > 0\), we will allocate the resource to User \(m\) and pop out user at the head of queue. Do this again until \(\Delta U \le 0\), at the final stage, we will allocate the residue resource to the BE users according to the marginal utility equality principle.

4.4 The Solution of the NUM Model

Now we are ready to describe the solution procedure of the proposed NUM model (15) and (16) correspondent to the two cases as follows.

  • Case 1: The total resource is sufficient, i.e.,

    $$\begin{aligned} \sum \limits _{i = 1}^M {\left( {{r_i}_0/{q_i}} \right) } \le R. \end{aligned}$$

    Firstly, we should give the resource to the QoS users at the amount they requested at the inflexion point, if the total resource is larger than the total amount that all users requested at the inflexion point. Then we consider to allocate the residue resource to the QoS users and BE users adhere to the marginal utility equality principle. For the optimal allocation set \({\mathfrak {R}}\), for the allocation to the user \(m \, r_m\in {\mathfrak {R}}\), we denote

    $$\begin{aligned} u({r_m})\mathop = \limits ^\Delta {u_{Sufficient}}. \end{aligned}$$

    For the QoS users, we have \({r_m} \ge {r_{{m_0}}}/{q_m}\); while for the BE users, we have \({r_m} > 0\). Because the utility function of the BE user and the QoS users is concave in the feasible region, we can solve

    $$\begin{aligned} u_m^{ - 1}\left( {{u_{Sufficient}}} \right) = {r_m}. \end{aligned}$$

    Because \({\mathfrak {R}}\) is full allocation, we have \(R = \sum \nolimits _{m = 1}^M {{r_m}}. \) Further, we have

    $$\begin{aligned} R = \sum \limits _{m = 1}^M {u_m^{ - 1}\left( {{u_{Sufficient}}} \right) } \mathop = \limits ^\Delta u_\Sigma ^{ - 1}\left( u_{Sufficient} \right) . \end{aligned}$$

    Using the above equation and taking the inverse function of \(u_\Sigma ^{ - 1}\left( u \right) \) we can solve the variable \(u_{Sufficient}\). After solving \(u_{Sufficient}\) for each user \(m\), we can compute \(r_m\) from

    $$\begin{aligned} {r_m} = u_m^{ - 1}\left( {{u_{Sufficient}}} \right) . \end{aligned}$$

    Notice that, for the QoS User \(m\), we have \({r_m} \in \left[ {{r_{{m_0}}}/{q_m},R} \right] \), for the BE User \(m\), we have \({r_m} \in \left[ {0,R} \right] \).

  • Case 2: The total resource is insufficient, i.e.,

    $$\begin{aligned} \sum \limits _{i = 1}^M {\left( {{r_i}_0/{q_i}} \right) } > R, \end{aligned}$$

    we give preference in resource allocation to those QoS users with better channel quality. If the QoS user’s channel quality is poor, we should allocate the resource to the BE users. So we consider firstly allocate the resource to the QoS user with good channel quality in the sorted queue, then we consider allocate the resource to BE user’s with the good channel quality. We will not allocate the resource to the QoS and BE users with the poor channel quality. Firstly, we will sort the QoS users at queue by \((U_{r_{m_0 } } q_m )/r_{m_0 } \). Then we will pop out the users at head of the queue and compute \(r_i =\frac{r_{i_0} }{q_i }\), if the allocation \(r_i\) to the QoS user is reasonable, that is

    $$\begin{aligned} \Delta {U_i} = {U_i} - \int _{{R_{residue}} - {r_i}}^{{R_{residue}}} {{u_\Sigma }\left( r \right) } dr > 0. \end{aligned}$$

    We will give the amount of resource \(r_i\) to them, compute \(R_{residue} =R_{residue} -r_i \) and pop out other users at head, until the queue is empty. If not, we allocate the resource \(R_{residue}\) to the BE users according to the marginal utility equality principle. For all BE users, assuming for User \(j, r_j > 0, r_j\) is the allocation for \(j. u({r_j})\mathop = \limits ^\Delta {u_{Insufficient}}\). We have

    $$\begin{aligned} R = \sum \limits _{j = M_1+1}^M {u_j^{ - 1}\left( {{u_{Insufficient}}} \right) } \mathop = \limits ^\Delta u_\Sigma ^{ - 1}\left( u_{Insufficient} \right) . \end{aligned}$$

    By solving this equation, we can obtain \(u_{Insufficient}\), then we can solve \({r_j} = u_j^{ - 1}\left( {{u_{Insufficient}}} \right) \). we compute

    $$\begin{aligned} r_j =u_j^{-1} \left( {u_\Sigma \left( {r_{Insufficient} } \right) } \right) . \end{aligned}$$

    If \({u_{Insufficient}} \ge {u_j}\left( 0 \right) \), we will not give them the resource; Otherwise, we will give them resource of \(r_j\).

Next, we design three algorithms that can be implemented at the base station to fulfill the aim of optimal resource allocation in a wireless network. We design the main algorithm (Algorithm 1) of the base station in the following way: when the users approach the base station, the base station will run the main algorithm, which will see if the resource is sufficient or insufficient. If yes, the base station will run Algorithm 2 to allocate resource. If not, the base station will run Algorithm 3 to allocate resource.

figure b
figure c
figure d

5 Numerical Simulation and Discussions

In this section, we present simulation results to verify our allocation algorithms. We consider one group of users having different channel quality and the other group of users having the same channel quality. Each group has nine users with the first six users being QoS one while the last three being the BE users. The parameters \(q_m, C_m, B_m, r_{m_0}\) of the first group are described in Table 2 and the parameters \(q_m, C_m, B_m, r_{m_0}\) of the second group are described in Table 3, respectively. We conduct the following calculations: for the first group of users

$$\begin{aligned} \sum \limits _{i = 1}^9 {\left( {{r_i}_0/{q_i}} \right) }= \frac{10}{0.8}+\dots +\frac{0}{0.9}=132.6389, \end{aligned}$$

for the second group of users

$$\begin{aligned} \sum \limits _{i = 1}^9 {\left( {{r_i}_0/{q_i}} \right) }= \frac{10}{0.9}+\dots +\frac{0}{0.9}=122.2222. \end{aligned}$$

We let the total resource vary from 20 to 300. Therefore, the simulation setting for total resource covers the two cases: when the total resource is insufficient and when the total resource is sufficient. The simulations results (Figs. 5, 6, 7) give the resource allocation of \(r_m, r_m-r_{m_0}\) and Fairness Index under different values of the total resource \(R\), for \(20 \le R\le 130\).

Table 2 The parameter settings for the users with different channel quality
Full size table
Fig. 5
figure 5

Resource allocation for users with different channel quality

Full size image

Figure 5 shows the values of \(r_m\) and \(r_m-r_{m_0}\) for mixture traffic with different channel quality. From Fig. 5a, b, one can see that the base station allocates more resource to those users with better channel conditions, as the value of \(R\) increases, the values \(r_m\) of User \(m\) increase. These simulation results are based on the parameter settings given by Table 2. In Fig. 5a, b, we observe that User \(3\) and User \(6\) with the large parameter \(C = 18\) have little value \(r_{m} - r_{m_0}\), because their traffic type is very close to Hard QoS traffic. But as \(R\) increases, the allocated resource to them \(r_{m}\) is fixed at \(r_{m_0}\). This suggests that our resource allocation scheme is also applicable to the scenario where there is Hard QoS traffic.

Fig. 6
figure 6

Resource allocation for users with the same channel quality

Full size image

Figure 6 shows the values of \(r_m\) and \(r_m-r_{m_0}\) for mixture traffic with the same channel quality. From Fig. 6a, b, we can see that the base station allocates the resource to the QoS user with high preference and then consider the channel quality of all of users. Because the BE users utility increases much less than that of QoS traffic with the resource increasing around the inflexion point, the basic rule for resource allocation is that, after we allocate the resource to the QoS traffic and satisfy their requests at their inflexion points, we then consider to allocate resource to the BE users. These simulation results are based on the scenario where the parameter settings are given by Table 3.

Table 3 The parameter settings for the users with the same channel quality
Full size table

Figure 7 shows the variations of the fairness index \(F\) of the allocation against the total resource \(R\). From Fig. 7a, we can see that when the resource is equal to that the QoS User requested at the inflexion point, the fairness index is \(<0.5\). As the value of \(R\) increases, the fairness index \(F\) decreases. This is due to the fact that, in the allocation scheme the base station allocates the resource to the QoS user with higher priority and then considers channel quality of all users. The simulation results presented in Fig. 7a are based on the parameter settings given by Table 2 while the simulation results presented in Fig. 7b are based on the parameter settings given by Table 3.

Fig. 7
figure 7

Fairness index versus total resource: a nine users with different channel quality, b nine users with the same channel quality

Full size image

6 Conclusion

In this paper, we study a challenging problem: utility maximization for resource allocation in wireless networks. We propose a NUM model that takes into account all types of traffic, then we propose algorithms that find the optimal solutions for resource allocation for mixture of Hard QoS, Soft QoS and BE traffic. We discuss two cases, where the total resource is sufficient and where the total resource is insufficient. Utilizing the concept of law of diminishing marginal utility that is widely accepted in economics, we establish the PEDMU for attacking the problem of resource allocation in wireless networks, and based on this we propose the corresponding solution procedures. Tradeoff between utility and fairness is discussed as well. Besides the theocratical analysis, simulation results are provided to validate the proposed model and the algorithms. From the simulation results, we find that different types of traffic need different kind of schemes to achieve optimal allocation. when the total resource is limited, the system tends to allocate more resources to users with better channel conditions; however, when it is abundant, the system gives QoS user priority and then consider the channel quality of all users. This leads us to conclude that an optimal radio resource allocation must depend on the traffic type, the total available resource and user channel quality.

In this paper, we focus only on resource allocation of network utility maximization and discuss the relationship between fairness index and NUM. In the future, extensions can be made such as on the issue how the trade-off between the network aggregate utility, total resource and the fairness can be achieved in a cross-layer optimization framework with consideration to various constraints in various layers.