On Wireless Scheduling Algorithms for Minimizing the Queue-Overflow Probability

 

1.ABSTRACT :

                   We are interested in wireless scheduling algorithms for the downlink of a single cell that can minimize the queue-overflow probability. Specifially, in a large-deviation setting, we are interested in algorithms that maximize the asymptotic decay-rate of the queue-overflow probability, as the queue-overflow threshold approaches infinity. We first derive an upper bound on the decay-rate of the queue-overflow probability over all scheduling policies. We then focus on a class of scheduling algorithms collectively referred to as the “α –algorithms”. For a given α≥ 1, the
α-algorithm picks the user for service at each time that has the largest product of the transmission rate multiplied by the backlog raised to the power . We show that when the overflow metric is appropriately modified,the minimum-cost-to-overflow under the α-algorithm can be achieved by a simple linear path, and it can be written as the solution of a vector-optimization problem. Using this structural property, we then show that when  approaches infinity, the α-algorithms asymptotically achieve the largest decay-rate of the queue overflow probability. Finally, this result enables us to design scheduling algorithms that are both close-to-optimal in terms of the asymptotic decay-rate of the overflow probability, and empirically shown to maintain small queue-overflow probabilitiesover queue-length ranges of practical interest.

2.EXISTING SCHEME :

                         In wireless networks link scheduling is an important functionality due to both the shared nature of the wireless medium and the variations of the wireless channel over time.

                                 It has been proved that, by carefully choosing the scheduling decision based on the channel state and/or the demand of the users, the system performance can be substantially improved. Most studies of scheduling algorithms have focused on optimizing the long term average throughput of the users.

3. PROPOSED SCHEME :

                                  An algorithm is called “throughput-optimal” if, at any offered  load under which any other algorithm can stabilize the system, this algorithm can stabilize the system as well. The proposed “exponential-rule” can maximize the decay-rate of the queue over flow probability over all scheduling policies. A wireless scheduling algorithms for the downlink of a single cell that can maximize the asymptotic decay-rate of the queue-overflow probability, as the overflow threshold approaches infinity, a class of scheduling algorithms collectively referred to as the ”α-algorithms” is utilized.

                A Lyapunov function used to derive a simple lower bound for the minimum-cost -to- overflow under the α-algorithms. This technique, which

is of independent interest, circumvents solving the difficult multi-dimensional calculus-of-variations problem typical in this type of problems.

4.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.

5.SOFTWARE REQUIREMENTS:

•         Operating System       : - Windows XP Professional.

•         Front End                     : - Asp .Net 2.0.

•         Coding Language       : - Visual C# .Net.