Design of Efficient Resource Allocation Algorithms for Wireless Networks: High Throughput, Small Delay, and Low Complexity

Designing efficient resource allocation mechanisms is both a vital and challenging problem in wireless networks. In this thesis, we focus on developing resource allocation and control algorithms for wireless networks that are aimed towards jointly optimizing over three critical dimensions of network performance: throughput, delay, and complexity.;We first focus on multihop wireless networks under general interference constraints, and aim to designing efficient scheduling algorithms that jointly optimize the network performance over different dimensions among the aforementioned three dimensions. We develop frameworks that enable us to design throughput-optimal scheduling algorithms that can reduce delays and/or incur a lower complexity in the following sense: smaller amount of required information, simpler data structure, and lower communication overhead.;We then turn to a simpler setting of single-hop multi-channel systems. A practically important example of such multi-channel systems is the downlink of a single cell in 4G OFDM-based cellular networks (e.g., LTE and WiMax). Our goal is to design efficient scheduling algorithms that achieve provably high performance in terms of both throughput and delay, at a low computational complexity. To that end, we first develop new easy-to-verify sufficient conditions for rate-function delay optimality in the many-channel many-user asymptotic regime (i.e., maximizing the decay-rate of the probability that the largest packet waiting time in the system exceeds a certain fixed threshold, as system size becomes large), and for throughput optimality in non-asymptotic settings. These sufficient conditions have been designed such that an intelligent combination of algorithms that satisfy both of the sufficient conditions allows us to develop low-complexity hybrid algorithms that are both throughput-optimal and rate-function delay-optimal. Further, we propose simpler greedy policies that are throughput-optimal and rate-function near-optimal, at an even lower complexity.;Finally, we investigate the scheduling problem in multihop wireless networks with flow-level dynamics. We explore potential inefficiency and instability of the celebrated back-pressure algorithms in the presence of flow-level dynamics, and provide interesting examples that are useful for obtaining insights into developing a unified throughput-optimal solution.;Our results in this thesis shed light on how to design resource allocation and control algorithms that can simultaneously attain both high throughput and small delay in practical systems with low-complexity operations. On the other hand, our studies also reveal that when flow-level dynamics is taken into account, even optimizing a single metric of throughput becomes much more challenging, not to mention achieving high network performance over all the three dimensions.