Fast Algorithms for Resource Allocation in Wireless Cellular Networks

We consider a scheduled orthogonal frequency division multiplexed (OFDM) wireless cellular network where the channels from the base-station to the n mobile users undergo flat fading. Spectral resources are to be divided among the users in order to maximize total user utility. We show that this problem can be cast as a nonlinear convex optimization problem, and describe an O(n) algorithm to solve it. Computational experiments show that the algorithm typically converges in around 25 iterations, where each iteration has a cost that is O(n), with a modest constant.

When the algorithm starts from an initial resource allocation that is close to optimal, convergence typically takes even fewer iterations. Thus, the algorithm can efficiently track the optimal resource allocation as the channel conditions change due to fading. We also show how our techniques can be extended to solve resource allocation problems that arise in wideband networks with frequency selective fading and when the utility of a user is also a function of the resource allocations in the past.

Existing System:

An efficient multi-user loading algorithm for OFDM based broadband wireless systems there in, adaptation decisions are made solely based on the longterm average channel conditions instead of fast channel fading. Specifically channel parameters are replaced by their mean values, resulting in a deterministic rather than stochastic optimization problem.

By doing so, Quality Of Service (QOS) can only be guaranteed in a longterm average sense, since the shortterm ?uctuation of the channel is not considered in the problem formulation. With the increasing popularity of wireless multimedia applications, however, there will be more and more inelastic traffic that require a guarantee on the minimum shortterm data rate. As such, slow adaptation schemes based on average channel conditions cannot provide a satisfactory QOS.

Proposed System:

Resource allocation in wireless networks is fundamentally different than that in wire line networks due to the time-varying nature of the wireless channel. There has been much prior work on scheduling policies in wireless networks to allocate resources among different flows based on the channels they see and the flow state. The flow state can consist of the average rate seen by the flow in the past the delay of the head-of-line packet or the length of the queue.

Much prior work in this area can be divided into two categories:

  • Scheduling for elastic (non real-time) flows

  • Scheduling for Real-Time Flows

Scheduling For Elastic (Non Real-Time) Flows:

The end user experience for an elastic flow is modeled by a concave increasing utility function of the rate experienced by the flow. The proportional fair algorithm where all the resources are allocated to the flow with the maximum ratio of instantaneous spectral efficiency (which depends on the channel gain) to the average rate has been analyzed in roughly speaking this algorithm maximizes the sum of log utilities of average rates over an asymptotically large time horizon. A more general scheduling rule where potentially multiple users can be scheduled simultaneously has been considered in most of the above work assumes that the queues have infinite backlogs, i.e., packets are always available in the buffers of all the queues; extensions to finite queues are provided. Joint design of scheduling and congestion control with modeling of queue dynamics has been considered in this case, packets are always assumed to be available at the congestion controller.

Scheduling For Real-Time Flows:

Real-time flows are typically modeled by a predetermined but unknown arrival process and a delay deadline for each packet for such flows, we can roughly define the stability region as follows: The stability region for a set of queues is defined as the set of arrival rates at the queues for which there exists a scheduling policy such that the length of any queue does not grow without bound over time. A stabilizing policy is one which ensures that the queue lengths do not grow without bound. Stabilizing policies for a vector of arrival rates within the stability region for different wireless network models have been characterized in the scheduling policy in minimizes the percentage of packets lost because of deadline expiry; while the delay performance of the exponential rule was empirically studied in work on providing throughput guarantees for such flows includes references therein.