Joint routing and scheduling in multi-radio multi-channel multi-hop wireless networks

Recent advances in multi-radio multi-channel transmission technology have the potential of substantially improving the system capacity in multi-hop wireless networks. While previous work has primarily focused on the link level protocol design, in this paper we investigate the achievable performance gain, by jointly optimizing routing and scheduling in a multi-radio multi-channel multi-hop network. We formulate the optimization under a deterministic model, and we seek to minimize overall system activation time in use to satisfy given end-to-end traffic demands subjected to the multi-access interference among neighboring transmissions and the radio interface constraint at each node. The exact solution to such an optimization problem is prohibitively complex due to the combinatorial complexity, particularly with the deployment of multi-radio and multi-channel. We develop a column generation based approach to solve this problem, which decomposes the original problem into sub-problems and solves them iteratively. Numerical results are given, and discussions as well as insights into the performance aspects for multi-radio multi-channel deployment are provided.