QOS-AWARE RESOURCE ALLOCATION 29

We investigate the problem of optimal rate allocation in the sense of maximizing the aggregated

utility function

( ).

f f

f F

U x

Î

å

U

f

(x

f

), which is also referred to as the social welfare in the literature [13]. Such

an optimization objective achieves Pareto optimality with respect to the resource utilization and also

realizes different fairness models—including proportional and max-min fairness [14]—when appro-

priate utility functions are speciﬁed. The problem of optimal resource allocation in wireless ad hoc

networks can be then formulated as a nonlinear optimization problem (primal problem):

P:

maximize

( ).

f f

f F

U x

Î

å

U

f

(x

f

) (2.2)

subject to Rx ≤ C (2.3)

over x

f

∈ I

f

(2.4)

This optimization problem maximizes the aggregated utility function in Equation 2.2 with

the resource capacity constraints shown in Equation 2.3 and coming from the shared wireless chan-

nel as discussed in Section 2.2. Note that we are dealing with maximal cliques and clique-ﬂow matrix

R, which represents the “resource usage pattern” of each ﬂow as a constraint in (Equation 2.3). If we

can optimize the problem P, we will get both optimal resource utilization and fair resource alloca-

tions among end-to-end ﬂows spanning multiple hops. However, often arriving toward a solution

of the problem P might be complex and difﬁcult since ﬁnding the right utility functions is difﬁcult,

hence one might look at the dual problem D to problem P and consider pricing-based description

D of the optimal resource allocation problem rather than utility-based description P.

2.3.2 Price-Based Resource Allocation Problem

To proceed toward the solution of the problem P, so that we achieve optimal resource allocation

(and QoS with respect to rate allocation) in terms of both utilization and fairness, we will transform

the problem P into its dual problem as follows. Owing to Assumption 1 in Section 2.3.1, the ob-

jective aggregated utility function

( ).

f f

f F

U x

Î

å

U

f

(x

f

) in Equation 2.2 is differentiable and strictly concave.

Also, the feasible region of the optimization problem in Equations 2.3 and 2.4 is convex and com-

pact. Hence, by nonlinear optimization theory, there exists a maximizing value of argument x for the

above optimization problem. Let us consider the Lagrangian form of the optimization problem P:

= - +

å å å

( ; ) ( ( ) )

f f f q qf q q

f F q Q q Q

L x U x x R Cµ

Î Î Î

µµ

( ).

f f

f F

U x

Î

å

U

f

(x

f

) - x

f

= - +

å å å

( ; ) ( ( ) )

f f f q qf q q

f F q Q q Q

L x U x x R Cµ

Î Î Î

µµ

+

= - +

å å å

( ; ) ( ( ) )

f f f q qf q

q

f F q Q q Q

L x U x x R Cµ

Î Î Î

µµ

(2.5)

where

µ

q

= (

µ

q

, q ∈ Q) is a vector of Lagrange multipliers. Note that Equation 2.5 represents the

method of Lagrange multipliers as we described in Table 2.2, where we have f (x) =

( ).

f f

f F

U x

Î

å

U

f

(x

f

),

Get *Quality of Service in Wireless Networks Over Unlicensed Spectrum* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.