• Please send your full manuscript to: jcm@etpub.com

A Fast Algorithm for the Optimal Constrained Path Routing in Wireless Mesh Networks

Weijun Yang 1 and Yun Zhang 2
1. Faculty of Automation, Guangdong University of Technology, Guangzhou, China
2. Department of Electromechanical Engineering, Guangzhou City Polytechnic, Guangzhou, China
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
Copyright © 2013-2017 Journal of Communications, All Rights Reserved
E-mail: jcm@etpub.com