Decoupled optimization of interference aware routing and scheduling for throughput maximization in wireless relay mesh networks
Preetha Thulasiraman, Xuemin Shen · 2009
The wireless relay mesh network (WRMN) is designed to provide robust and fault tolerant communications between relay and user nodes in broadband wireless networks. In this paper, we investigate the benefits of decoupled optimization of routing and scheduling in WRMNs using the physical interference model and spatial reuse to maximize overall throughput. We model the routing optimization as a linear program using multicommodity flows (MCF). We refer to this problem as multicommodity flow routing optimization (MCF-ROPT). Using the flow per link determined from MCF-ROPT, we develop an optimization formulation to schedule the link traffic such that interference is minimized and time slots are reused appropriately based on spatial TDMA (STDMA). Furthermore, our scheduling approach incorporates the effect of reuse of multiple carriers on the transmission schedule. We refer to this problem as SM-TSS (STDMA multicarrier traffic sensitive scheduling). The SM-TSS is NP-hard and thus is solved using column generation. We compare our formulations with decoupled optimizations that use the protocol interference model and/or single carrier systems and show that our approach guarantees higher throughput by mitigating interference effectively.