Abstract—Finding a path subject to multiple QoS requirements is regarded as a critical component in wireless mesh networks especially the real-time wireless communication applications become increasingly popular. As far as we know, it is an NP-complete problem. This paper devises a simple and fast K-approximation algorithm (KAMCOP) to deal with it from the perspective of approximate. The theoretical validations for the proposed algorithm show that, its approximation ratio is K and the time complexity is O(Km+nlogn). The simulation results on the special networks show that the time complexity of KAMCOP is as simple as Dijkstra algorithm, which is fit for implementation in wireless routing protocols.

Index Terms—Wireless mesh networks, QoS, constrained path, approximation algorithm

Cite: Weijun Yang and Yun Zhang, “A Fast Algorithm for the Optimal Constrained Path Routing in Wireless Mesh Networks," Journal of Communications, vol. 11, no. 2, pp. 126-131, 2016. Doi: 10.12720/jcm.11.2.126-131