The robust joint solution for channel assignment and routing for wireless mesh networks with time partitioning

Joint channel assignment and routing is an essential yet challenging issue for multi-radio multi-channel wireless mesh networks. Though several works are presented in the existing literature to approach this problem, the key question - how to ensure that the resulting network performance can closely track the optimal solution under high traffic variability without incurring too much overhead, remains unanswered. In this work, we present a new solution called "Robust joint Channel Assignment and Routing with Time partitioning (RCART)" for WMNs. RCART consists of three steps: (1) Time Partitioning and Traffic Characterization, which accomplishes the goal of partitioning time into periodic intervals with consistent properties which can be routed efficiently, (2) Robust Routing, which finds a robust routing scheme that provides an upper bound on the worst-case network performance for traffic demands that fall into a convex region, (3) Channel Assignment, which allocates radios to fixed channels during the time interval identified in step 1 and based on the knowledge of traffic distribution from step 2, using the worst-case congestion ratio as a robustness metric in its objective. Introducing time partitions as an additional control variable in the robust mesh routing RCART solution significantly improves average-case performance. Performance evaluation is conducted for RCART using real traffic demand traces. The results show that our RCART solution significantly outperforms the existing works without time partitioning or with simpler traffic profile models. (C) 2011 Elsevier B.V. All rights reserved.