Abstract—The problem of optimal multicast routing tree in WMNs subject to multiple QoS constraints, which is NP-complete, is studied in this paper. As far as we know, the existing algorithms for finding such a multicast routing tree are not very efficient and effective in wireless mesh networks. Combining the previous effective algorithms, this paper devises a fast multicast path heuristic (FMPH) algorithm to deal with it. The theoretical validations for the proposed algorithm show that its approximation ratio is 2K(1−1/q) and the time complexity is O(Km+qn2). The simulation results on the special network show that the FMPH algorithm is as simple as Dijkstra algorithm in the way of implementation, which is fit for application in wireless routing protocols.
Index Terms—Wireless mesh networks, multicast routing, multiple QoS constrains, approximation algorithm
Cite: Weijun Yang and Yun Zhang, “A Fast Algorithm for Multicast Routing Subject to Multiple QoS Constrains in WMNs," Journal of Communications, vol. 11, no. 8, pp. 733-739, 2016. Doi: 10.12720/jcm.11.8.733-739
Copyright © 2013-2021 Journal of Communications, All Rights Reserved