In this paper, we study the queue-overflow probability of wireless scheduling algorithms. In wireless networks operated under queue-length-based scheduling algorithms, there often exists a tight coupling between the service-rate process, the system backlog process, the arrival process, and the stochastic process governing channel variations. Although one can use sample-path large-deviation techniques to form an estimate of the queue-overflow probability, the formulation leads to a difficult multidimensional calculus-of-variations problem. In this paper, we present a new technique to address this complexity issue. Using ideas from the Lyapunov function approach in control theory, this technique maps the complex multidimensional calculus-of-variations problem to a 1-D calculus-of-variations problem, and the latter is often much easier to solve. Further, under appropriate conditions, we show that when a scheduling algorithm minimizes the drift of a Lyapunov function at each point of every fluid sample path, the algorithm will be optimal in the sense that it maximizes the asymptotic decay rate of the probability that the Lyapunov function value exceeds a given threshold. We believe that these results can potentially be used to study the queue-overflow probability of a large class of wireless scheduling algorithms and to design new scheduling algorithms with optimal overflow probabilities.

We consider the problem of link scheduling for efficient convergecast in a wireless system. While there have been many results on scheduling algorithms that attain the maximum possible throughput in such a system, there have been few results that provide scheduling algorithms that are optimal in terms of some quality-of-service metric such as the probability that the end-to-end buffer usage exceeds a large threshold. Using a large deviations framework, we design a novel and low complexity algorithm that attains the optimal asymptotic decay rate for the overflow probability of the sum-queue (i.e. the total queue backlog in the entire system) as the overflow threshold becomes large. Simulations show that this algorithm has better performance than well known algorithms such as the standard back-pressure algorithm and the multihop version of greedy maximal matching (combined with back-pressure). Our proposed algorithm performs better not only in terms of the asymptotic decay rate at large overflow thresholds, but also in terms of the actual probability of overflow for practical range of overflow thresholds.

While there has been much progress in designing backpressure based stabilizing algorithms for multihop wireless networks, end-to-end performance (e.g., end-to-end buffer usage) results have not been as forthcoming. In this paper, we study the end-to-end buffer usage (sum of buffer utilization along a flow path) over a network with general topology and with fixed, loop-free routes using a large-deviations approach. We first derive bounds on the best performance that any scheduling algorithm can achieve. Based on the intuition from the bounds, we propose a class of (backpressure-like) scheduling algorithms called ¿ß-algorithms. We show that the parameters ¿ and ß can be chosen such that the system under the ¿ß-algorithm performs arbitrarily closely to the best possible scheduler (formally the decay rate function for end-to-end buffer overflow is shown to be arbitrarily close to optimal in the large-buffer regime). We also develop variants which have the same asymptotic optimality property, and also provide good performance in the small-buffer regime. Our results are substantiated using both analysis and simulation.

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 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 probabilities over queue-length ranges of practical interest.