Utility Maximization in Wireless Backhaul Networks with Service Guarantees

We consider the problem of maximizing utility in wireless backhaul networks, where utility is a function of satisfied service level agreements (SLAs), defined in terms of end-to-end packet delays and instantaneous throughput. We model backhaul networks as a tree topology and show that SLAs can be satisfied by constructing link schedules with bounded inter-scheduling times, an NP-complete problem known as pinwheel scheduling. For symmetric tree topologies, we show that simple round-robin schedules can be optimal under certain conditions. In the general case, we develop a mixed-integer program that optimizes over the set of admission decisions and pinwheel schedules. We develop a novel pinwheel scheduling algorithm, which significantly expands the set of schedules that can be found in polynomial time over the state of the art. Using conditions from this algorithm, we develop a scalable, distributed approach to solve the utility-maximization problem, with complexity that is linear in the depth of the tree.