An optimization framework for the joint routing and scheduling in Wireless Mesh Networks

In this paper, we address the problem of computing the transport capacity of Wireless Mesh Networks dedicated to Internet access. Routing and transmission scheduling have a major impact on the capacity provided to the clients. A cross-layer optimization of these problems allows the routing to take into account contentions due to radio interferences. We develop exact linear programs and provide an efficient column generation process computing a relaxation of the problem. It allows to work around the combinatoric of simultaneously achievable transmissions, hence computing solutions on large networks. Our approach is validated through extensive simulations. Evolution of the capacity of a mesh network with its parameters, as well as the algorithmic complexity are then discussed. We conjecture that the problem can be solved in polynomial time and that the gateway placement problem is only subject to localized constraints.