Integrating Traffic Estimation and Routing Optimization for Multi-Radio Multi-Channel Wireless Mesh Networks

Traffic routing plays a critical role in determining the performance of a wireless mesh network. To investigate the best solution, existing work proposes to formulate the mesh network routing problem as an optimization problem. In this problem formulation, traffic demand is usually implicitly assumed as static and known a priori. Contradictorily, recent studies of wireless network traces show that the traffic demand, even being aggregated at access points, is highly dynamic and hard to estimate. Thus, in order to apply the optimization-based routing solution into practice, one must take into account the dynamic and unpredictable nature of wireless traffic demand. This paper presents an integrated framework for network routing in multi-radio multi-channel wireless mesh networks under dynamic traffic demand. This framework consists of two important components: traffic estimation and routing optimization. By analyzing the traces collected at wireless access points, the traffic estimation component predicts future traffic demand based on its historical value using time-series analysis, and represents the prediction result in two forms - mean value and statistical distribution. The optimal mesh network routing strategies then take these two forms of traffic demand estimations as inputs. In particular, two routing algorithms are proposed based on linear programming which consider the mean value and the statistical distribution of the predicted traffic demands, respectively. The trace-driven simulation study demonstrates that our integrated traffic estimation and routing optimization framework can effectively incorporate traffic dynamics in mesh network routing, where both algorithms outperform the shortest path algorithm in about 80% of the test cases.