Global Optimal Rate Control and Scheduling for Spectrum-Sharing Multi-Hop Networks

The multi-hop multi-flow transmission has been proposed as a promising solution to cope with the spectrum scarcity in densely populated user environments. Due to the mutual interference between different flows and different hops of the same flow, the resource allocation for multi-hop multi-flow wireless networks is in general non-convex, and thus cannot be solved by conventional convex optimization techniques. In this paper, we propose an algorithm to effectively solve the resource allocation problem by jointly optimizing the rate control and scheduling. Specifically, we show that the problem can be decomposed into a set of problems that maximizes the weight-sum-flow rate at each slot. Furthermore, to solve the non-convex weighted sum flow rate maximization problem, we exploit its hidden monotonicity and develop a global optimal rate control and scheduling (G-RCS) algorithm based on the theory of monotonic optimization. Our analysis shows that the proposed G-RCS algorithm is guaranteed to converge to an optimal solution in a finite number of iterations. To reduce the complexity, we propose an accelerated algorithm, referred to as the A-G-RCS, based on the inherent symmetry of the optimal solution. Numerical results validate that the proposed algorithms can serve as a performance benchmark for the existing heuristic algorithms.