Joint Routing and Scheduling in WiMAX-Based Mesh Networks

The problem of scheduling and routing tree construction in WiMAX/802.16 based mesh networks is not defined in the standard and has thus been the subject to extensive research. We consider the problem of joint routing and scheduling in WiMAX-based mesh networks, with the objective of determining a minimum schedule period that satisfies a given (uplink/downlink) traffic demand. Minimizing the length of a schedule amounts to maximizing the spectrum spatial reuse by activating concurrently as many links. This group of transmission links active concurrently is referred to as the transmission group and refers to the set of wireless links that can simultaneously transmit without violating the signal-to-interference-plus-noise ratio (SINR) requirement. Our model is referred to as maximum spatial reuse (MSR). We assume centralized scheduling at the base station and attempt to maximize the system throughput through appropriate routing tree selection and achieving efficient spectrum reuse through opportunistic link scheduling. We present an ILP optimization model for the joint problem, which relies on the enumeration of all possible link schedules. Given its complexity, we decompose the problem using a column generation (CG) approach. We present two formulations for modeling MSR, namely the link-based (CGLink) and the path-based (CGPath) formulation. These two formulations differ mainly in the number of routing decision variables. Our experimental results indicate that the path-based formulation needs much less computational (CPU) time than the link-based in order to determine the (same) optimal solution with the same spatial reuse gain.