Complexity and Design of QoS Routing Algorithms in Wireless Mesh Networks
Quality of Service (QoS) provisioning in Wireless Mesh Networks (WMNs) is an open issue to support emerging multimedia services. In this paper, the authors study the problem of QoS provisioning in terms of end-to-end bandwidth allocation in WMNs. It is challenging due to interferences in the networks. They consider widely used interference models and show that except a few special cases, the problem of finding a feasible path is NP-complete under the models. They propose a k-shortest path based algorithmic framework to solve this problem. They also consider the problem of optimizing network performance by on-line dynamic routing, and adapt commonly used conventional QoS routing metrics to be used in WMNs. They find the optimal solutions for these problems through formulating them as optimization models.