• Please send your full manuscript to: jocm@vip.163.com

A Fast Algorithm for Multicast Routing Subject to Multiple QoS Constrains in WMNs

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