# Convergence and optimality of channel aware scheduling and resource allocation algorithms<br/><br/>

Wednesday, June 29, 2005 - 1:30pm - 2:30pm

EE/CS 3-180

Rajeev Agrawal (Motorola)

With an abstraction of serving rate-adaptive sources on a broadcast-type

wireless channel as a utility maximization problem, it is shown how one

can design many intuitive online scheduling policies based upon the feedback

that one obtains at the scheduler. Using a stochastic approximation argument

it is then shown that the constructed algorithms converge to optimal solutions

of the utility maximization problem over different sets which critically

depend on the quality of the feedback information.

We then apply the theory developed above to the downlink in a CDMA based

wireless network. In terms of operational variables the problem is to select

a subset of the users for transmission at each transmission oppurtunity and

for each of the users selected, to choose the modulation and coding scheme,

transmission power, and number of codes used. We refer to this combination as

the physical layer operating point (PLOP). Each PLOP consumes different amounts

of code and power resources. Thus, the task is to pick the optimal PLOP

taking into account both system-wide and individual user resource constraints

that can arise in a practical system. Using an information theoretic model

for the achievable rate per code results in a tractable convex optimization problem.

By exploiting the structure of this problem, we give algorithms for finding

the optimal solution with geometric convergence. We also use insights obtained

from the optimal solution to construct low complexity near optimal algorithms

that are easily implementable. Numerical results comparing these algorithms are

also given.

wireless channel as a utility maximization problem, it is shown how one

can design many intuitive online scheduling policies based upon the feedback

that one obtains at the scheduler. Using a stochastic approximation argument

it is then shown that the constructed algorithms converge to optimal solutions

of the utility maximization problem over different sets which critically

depend on the quality of the feedback information.

We then apply the theory developed above to the downlink in a CDMA based

wireless network. In terms of operational variables the problem is to select

a subset of the users for transmission at each transmission oppurtunity and

for each of the users selected, to choose the modulation and coding scheme,

transmission power, and number of codes used. We refer to this combination as

the physical layer operating point (PLOP). Each PLOP consumes different amounts

of code and power resources. Thus, the task is to pick the optimal PLOP

taking into account both system-wide and individual user resource constraints

that can arise in a practical system. Using an information theoretic model

for the achievable rate per code results in a tractable convex optimization problem.

By exploiting the structure of this problem, we give algorithms for finding

the optimal solution with geometric convergence. We also use insights obtained

from the optimal solution to construct low complexity near optimal algorithms

that are easily implementable. Numerical results comparing these algorithms are

also given.