Stochastic optimization over parallel queues: channel-blind scheduling, restless bandit, and optimal delay

2011-07-29This dissertation addresses several optimal stochastic scheduling problems that arise in partially observable wireless networks and multi-class queueing systems. They are single-hop network control problems under different channel connectivity assumptions and different scheduling constraints. Our goals are two-fold: To identify stochastic scheduling problems of practical interest, and to develop analytical tools that lead to efficient control algorithms with provably optimal performance. ❧ In wireless networks, we study three sets of problems. First, we explore how the energy and timing overhead due to channel probing affects network performance. We develop a dynamic channel probing algorithm that is both throughput and energy optimal. The second problem is how to exploit time correlations of wireless channels to improve network throughput when instantaneous channel states are unavailable. Specifically, we study the network capacity region over a set of Markov ON/OFF channels with unknown current states. Recognizing that this is a difficult restless multi-armed bandit problem, we construct a non-trivial inner bound on the network capacity region by randomizing well-designed round robin policies. This inner bound is considered as an operational network capacity region because it is large and easily achievable. A queue-dependent round robin policy is constructed to support any throughput vector within the inner bound. In the third problem, we study throughput utility maximization over partially observable Markov ON/OFF channels (specifically, over the inner bound provided in the previous problem). It has applications in wireless networks with limited channel probing capability, cognitive radio networks, target tracking of unmanned aerial vehicles, and restless multi-armed bandit systems. An admission control and channel scheduling policy is developed to achieve near-optimal throughput utility within the inner bound. Here we use a novel ratio MaxWeight policy that generalizes the existing MaxWeight-type policies from time-slotted networks to frame-based systems that have policy-dependent random frame sizes. ❧ In multi-class queueing systems, we study how to optimize average service cost and per-class average queueing delay in a nonpreemptive multi-class M/G/1 queue that has adjustable service rates. Several convex delay penalty and service cost minimization problems with time-average constraints are investigated. We use the idea of virtual queues to transform these problems into a new set of queue stability problems, and the queue-stable policies are the desired solutions. The solutions are variants of dynamic c-mu rules, and implement weighted priority policies in every busy period, where the weights are functions of past queueing delays in each job class. ❧ Throughout these problems, our analysis and algorithm design uses and generalizes an achievable region approach driven by Lyapunov drift theory. We study the performance region (in throughput, power, or delay) of interest and identify, or design, a policy space so that every feasible performance vector is attained by a stationary randomization over the policy space. This investigation facilitates us to design queue-dependent network control policies that yield provably optimal performance. The resulting policies make greedy and dynamic decisions at every decision epoch, require limited or no statistical knowledge of the system, and can be viewed as learning algorithms over stochastic queueing networks. Their optimality is proved without the knowledge of the optimal performance