Distributed resource allocation algorithms for wireless networks

In this thesis, we present distributed resource allocation algorithms for various wireless networks, which include Heterogenous Networks, mmWave Integrated Access and Backhaul networks. We consider the minimum time clearing objective for resource allocation in wireless networks. The minimum time clearing optimization corresponds to clearing a given set of files at the wireless nodes, in the minimum possible time subject to the scheduling constraints. The optimization is NP-complete in general. In this thesis we consider wireless network models with additional structure arising from the above applications. Based on this structure, we propose distributed resource allocation algorithms which only require local information and which do not suffer from a combinatorial explosion in complexity as the size of the network grows large.

We characterize the stability of the considered wireless networks under dynamic scenarios such as random traffic arrivals in time, and time varying channel conditions. Roughly speaking, we refer to the network as stable if the traffic does not build up indefinitely at the nodes in the network. We provide distributed scheduling and flow control algorithms for the wireless networks under dynamic scenarios. We show that a version of the minimum time clearing optimization can be formulated using the queue length information. The solution can then be used as a scheduling algorithm. It follows that the proposed scheduling algorithm can be implemented in a distributed and efficient manner, in topologies where the underlying structure allows for an efficient solution.

With the exception of Chapter 3, the scheduling algorithms proposed in the thesis are throughput optimal, i.e., stabilize the network for all arrival rates within the stability region. The greedy scheduling algorithm proposed in Chapter 3, only uses local information. We show that this proposed algorithm achieves the largest stability region among the class of scheduling policies which only use local information. We also provide conditions under which the greedy scheduling algorithm is throughput optimal.