Joint Routing and Channel Assignment in Multi-radio Wireless Mesh Networks

This paper considers the problem of how to maximize throughput in multi-radio multi-channel wireless mesh networks. With mathematical model based on radio and radioto-radio link, we introduce a scheduling graph and show that the feasibility problem of time fraction vector is equal to the problem of whether the scheduling graph is [M]-colorable, where M is the number of slots in one period. We use this equivalence property to derive a sufficient condition of feasibility, and then, using this sufficient condition, we mathematically formulate the joint routing and channel assignment problem as a linear programming problem. Finally, we use vertex coloring to get a feasible schedule and lift the resulting flows. We prove that the optimality gap is above a constant factor. The numeric results demonstrate the effectiveness of our proposed algorithm.