Wireless mesh networks have gained significant academic and industry attentions in the recent years. Supporting quality of service in wireless mesh networks is an important and challenging task which involves both medium access control and network layer design. In this paper, we investigate the problem of end-to-end on-demand bandwidth allocation in infrastructure wireless mesh networks. We formulate it as a combinatorial optimization problem, and prove that it is NP-hard. We present a polynomial time 2-approximation algorithm, MCRS (minimum consumption routing and scheduling), based on the concepts of consumption level for routing and bottom set for scheduling. Comprehensive simulation results show that MCRS achieves better performance than traditional methods based on minimum hop routing.
展开▼