Scheduling Optimization in wireless MESH Networks with Power Control and Rate Adaptation

Wireless MESH networks are a new networking paradigm that allow to extend the coverage of traditional wireless access networks with multi-hop connections through fixed wireless mesh routers. Wireless MESH networks partially replace wired backbone networks, and it is reasonable to carefully plan radio resource assignment in order to provide quality guarantees to traffic flows. Differently from ad hoc networks, energy consumption is usually not a problem with wireless MESH routers, routes are quite stable and bandwidth requirements of traffic flows can be considered almost constants. In this paper we study the scheduling optimization 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 signal-to-interference-and-noise ratio (SINR). Traffic quality requirements are expressed in terms of minimum bandwidth and modelled with constraints defining the number of information units (packets) that must be transmitted on each link per frame. We propose an alternative problem formulation where decision variables represent compatible sets of links active in the same slot. Approaches to solve both lower and upper bound for the problem are proposed: since compatible set variables are exponentially many, we use column generation to compute a lower bound for the problem. Heuristic approaches to compute feasible integer solutions are proposed and tested