Since Tassiulas and Ephremides proposed the maximum weight scheduling algorithm of throughput-optimality for constrained queueing networks in 1992, extensive research efforts have been made for resolving its high complexity issue under various directions. In this paper, we resolve the issue by developing a generic framework for designing throughput-optimal and low-complexity scheduling algorithms. Under the framework, an algorithm updates current schedules via an interaction with a given oracle system that can generate a solution of a certain discrete optimization problem in a finite number of interactive queries. Therefore, one can design a variety of scheduling algorithms under this framework by choosing different oracles, e.g., the exhaustive search (ES), the markov chain monte carlo (MCMC), the belief propagation (BP) and the cutting-plane (CP) algorithms. The complexity of the resulting algorithm is decided by the number of operations required for an oracle processing a single query, which is typically very small. Somewhat surprisingly, we prove that an algorithm using any such oracle is throughput-optimal for general constrained queueing network models that arise in the context of emerging large-scale communication networks. In particular, the pick-and-compare' algorithms developed by Tassiulas in 1998 and recently developed queue-based CSMA algorithms can be also understood as special cases of such algorithms using ES and MCMC oracles, respectively. To our best knowledge, our result is the first that establishes a rigorous connection between iterative optimization methods and low-complexity scheduling algorithms, which we believe provides various future directions and new insights in both areas.
Design and analysis of resource allocation algorithms in constrained queueing networks have been of great interest for last four decades across various research communities, where the contention resolution protocols in multiple-access broadcast channels have been studied since the mid-1970s @cite_23 . The broadcast channels induce a special constraint in resources usages among queues (i.e., every queue contend with all other queues), and simple distributed contention resolution protocols gained much attention in the ages. It is the year 1992 that the seminal work by Tassiulas and Ephremides proposed a throughput-optimal algorithm, referred to as MW, for general resource constraints. Its main appeal is that it does require only information on the current queue lengths (and instantaneous service rates) and does not rely on the knowledge of underlying system parameters. However, as we mentioned earlier, the MW algorithm suffers from the high implementation complexity, and a huge array of subsequent research has been made to develop algorithms with high performance guarantees and low-complexity.
@cite_23
1987954156
In this paper, we study resource allocation in a downlink OFDMA system assuming imperfect channel state information (CSI) at the transmitter. To achieve the individual QoS of the users in OFDMA system, adaptive resource allocation is very important, and has therefore been an active area of research. However, in most of the the previous work perfect CSI at the transmitter is assumed which is rarely possible due to channel estimation error and feedback delay. In this paper, we study the effect of channel estimation error on resource allocation in a downlink OFDMA system. We assume that each user terminal estimates its channel by using an MMSE estimator and sends its CSI back to the base station through a feedback channel. We approach the problem by using convex optimization framework, provide an explicit closed form expression for the users' transmit power and then develop an optimal margin adaptive resource allocation algorithm. Our proposed algorithm minimizes the total transmit power of the system subject to constraints on users' average data rate. The algorithm has polynomial complexity and solves the problem with zero optimality gaps. Simulation results show that our algorithm highly improves the system performance in the presence of imperfect channel estimation.