Routing, scheduling and channel assignment in Wireless Mesh Networks: optimization models and algorithms

Wireless Mesh networks (WMNs) can partially replace the wired backbone of traditional wireless access networks and, similarly, they require to carefully plan radio resource assignment in order to provide the same quality guarantees to traffic flows. In this paper we study the radio resource assignment ptimization problem in wireless Mesh networks assuming a time division multiple access (TDMA) scheme, a dynamic power control able to vary emitted power slot-by-slot, and a rate adaptation mechanism that sets transmission rates according to the signalto- interference-and-noise ratio (SINR). The proposed optimization framework includes routing, scheduling and channel assignment. Quality requirements of traffic demands are expressed in terms of minimum bandwidth and modeled with constraints defining the number of information units (packets) that must be delivered per frame. We consider an alternative problem formulation where decision variables represent compatible sets of links active in the same slot and channel, called configurations. We propose a two phases solution approach where a set of configurations is first selected to meet traffic requirements along the best available paths, and then configurations are assigned to channels according to device characteristics and constraints. The optimization goal is to minimize the number of used slots, which is directly related to the global resource allocation efficiency. We provide a lower bound of the optimal solution solving the continuous relaxation of problem formulation. Moreover, we propose a heuristic approach to determine practical integer solutions (upper bound). Since configuration variables are exponentially many, our solution approaches are based on the Column Generation technique. In order to assess the effectiveness of the proposed algorithms we show the numerical results obtained on a set of realistic-size randomly generated instances.