11-03-2011, 01:50 PM
[attachment=9983]
On Wireless Scheduling Algorithms for Minimizing the Queue-Overflow Probability
ABSTRACT:
In this paper, we are interested in wireless scheduling algorithms for the downlink of a single cell that can minimize the queue-overflow probability. Specifically, in a large-deviation setting, we are interested in algorithms that maximize the asymptotic decay rate of the queue-overflow probability, as thequeue-overflowthreshold approaches infinity. We first derive an upper boundonthe 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 cable 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 probabilities over queue-length ranges of practical interest.
Objective
LINK scheduling is an important functionality in wireless networks due to both the shared nature of the wireless medium and the variations of the wireless channel over time. In the past, it has been demonstrated 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 or, in other words, stability. Consider the downlink of a single cell in a cellular network
Existing System
LINK scheduling is an important functionality in wireless networks due to both the shared nature of the wireless medium and the variations of the wireless channel over time. In the past, it has been demonstrated 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 or, in other words, stability.
Proposed system
We study 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. Specifically, we focus on the class
Of “-algorithms,” which pick 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 approaches infinity, the -algorithms asymptotically achieve the largest decay rate of the queue-overflow probability. A key step in proving this result is to use a Lyapunov function to derivea simple lower bound for the minimum cost to overflow underthe -algorithms.
HARDWARE AND SOFTWARE REQUIREMENTS
Software Requirements:
Language : C#.NET
Technologies : Microsoft.NET Framework
IDE : Visual Studio 2008
Operating System : Microsoft Windows XP SP2 or Later Version
Back End : SQL Server 2000
Hardware Requirements:
Processor : Pentium III / IV
Hard Disk : 40 GB
Ram : 256 MB
Monitor : 15VGA Color
Mouse : Ball / Optical
CD-Drive : LG 52X
Keyboard : 102 Keys