Slow Adaptive OFDMA System Through Chance Constrained Programming

Abstract:

               Adaptive OFDMA has recently been recognized as a promising technique for providing high spectral efficiency in future broadband wireless systems. The research over the last decade on adaptive OFDMA systems has focused on adapting the allocation of radio resources, such as sub carriers and power, to the instantaneous channel conditions of all users. However, such “fast” adaptation requires high computational complexity and excessive signaling overhead. This hinders the deployment of adaptive OFDMA systems worldwide. This paper proposes a slow adaptive OFDMA scheme, in which the sub carrier allocation is updated on a much slower timescale than that of the fluctuation of instantaneous channel conditions. Meanwhile, the data rate requirements of individual users are accommodated on the fast timescale with high probability, thereby meeting the requirements except occasional outage. Such an objective has a natural chance constrained programming formulation, which is known to be intractable. To circumvent this difficulty, we formulate safe tractable constraints for the problem based on recent advances in chance constrained programming. We then develop a polynomial-time algorithm for computing an optimal solution to the reformulated problem. Our results show that the proposed  slow adaptation scheme drastically reduces both computational cost and control signaling overhead when compared with the conventional fast adaptive OFDMA.

Our work can be viewed as an initial attempt to apply the chance constrained programming methodology to wireless system designs. Given that most wireless systems can tolerate an occasional dip in the quality of service, we hope that the proposed methodology will find further applications in wireless communications.

Algorithm/Technique Used:

                                         Polynomial-time algorithm

Algorithm Description:

                               We then develop a polynomial-time algorithm for computing an optimal solution to the reformulated problem. In this section, we propose an algorithm for solving Problem ˜ Pslow. In ˜ Pslow, the STC arises as a sub problem, which by itself requires a minimization over %. Hence, despite its convexity, the entire problem ˜ Pslow cannot be trivially solved using standard solvers of convex optimization. This is due to the fact that the sub problem introduces difficulties, for example, in defining the barrier function in path-following algorithms or providing the (sub-)gradient in primal-dual methods .Fortunately, we can employ interior point cutting plane methods to solve Problem ˜ Pslow (see [15] for a survey). Before we delve into the details, let us briefly sketch the principles of the algorithm

as follows.

 

A.    The Cutting-Plane-Based Algorithm

                           ^{M i}

             max       ∑    log s _M ⁱ

           { x ^t, s ^t} m=1

B.    Global Convergence Complexity

         

           In the following, we investigate the convergence properties of the proposed algorithm. As mentioned earlier, when the polytope is too small to contain a full-dimensional closed ball of radius α > 0, the potential value will exceeds a certain threshold. Then, the algorithm can terminate since the query point is within a distance of α > 0 to some optimal solution of

˜ Pslow. Where it was shown that the analytic center-based cutting plane method can be used to solve convex programming problems in polynomial time.

Existing System:

In the existing literature, adaptive OFDMA exploits time, frequency, and multi-user diversity by quickly adapting sub carrier allocation (SCA) to the instantaneous channel state information (CSI) of all users. Such “fast” adaptation suffers from high computational complexity, since an optimization problem required for adaptation has to be solved by the base

station (BS) every time the channel changes. Considering the fact that wireless channel fading can vary quickly (e.g., at the order of milli-seconds in wireless cellular system), the implementation of fast adaptive OFDMA becomes infeasible for practical systems, even when the number of users is small. Recent work on reducing complexity of fast adaptive OFDMA. Moreover, fast adaptive OFDMA requires frequent signaling between the BS and mobile users in order to inform the users of their latest allocation decisions. The overhead thus incurred is likely to negate the performance gain obtained by the fast adaptation schemes. To date, high computational cost and high control signaling overhead are the major hurdles that prevent adaptive OFDMA from being deployed in practical systems.

Proposed System:

We consider a slow adaptive OFDMA scheme, to address the aforementioned problem. In contrast to the common belief that radio resource allocation should be readapted once the instantaneous channel

Conditions change, the proposed scheme updates the SCA on a much slower timescale than that of channel fluctuation. Specifically, the allocation decisions are fixed for the duration of an adaptation window, which spans the length of many coherence times. By doing so, computational cost and control signaling overhead can be dramatically reduced. Therein, adaptation decisions are made solely based on the long-term average channel conditions instead of fast channel fading.

           In this paper, we propose a slow adaptive OFDMA scheme that aims at maximizing the long-term system throughput while satisfying with high probability the short-term data rate requirements. The key contributions of this paper are as follows:

                   

                      • We design the slow adaptive OFDMA system based on chance constrained programming techniques. Our formulation guarantees the short-term data rate requirements of individual users except in rare occasions. To the best of our knowledge, this is the first work that uses chance constrained programming in the context of resource allocation

in wireless systems.

                      • We exploit the special structure of the probabilistic constraints in our problem to construct safe tractable constraints (STC) based on recent advances in the chance constrained programming literature.

                     • We design an interior-point algorithm that is tailored for

The slow adaptive OFDMA problem, since the formulation with STC, although convex, cannot be trivially solved using off-the-shelf optimization software. Our algorithm can efficiently compute an optimal solution to

the problem with STC in polynomial time.

Hardware Requirements:

•         System                : Pentium IV 2.4 GHz.

•         Hard Disk            : 40 GB.

•         Floppy Drive      : 1.44 Mb.

•         Monitor               : 15 VGA Colour.

•         Mouse                 : Logitech.

•         Ram                     : 256 Mb.

Software Requirements:

•         Operating System        : - Windows XP Professional.

•         Front End                     : - Asp .Net 2.0.

•         Coding Language         : - Visual C# .Net.