# A Novel QoS Provisioning Algorithm for Optimal Multicast Routing in WMNs
## 1 Introduction  
In a relatively short period of time, the Internet has become a critical information delivery infrastructure for global commerce and multimedia [1]. Over the last decade, multicast routing trees for efficient one-to-many communications applications (e.g., web broadcasting, video teleconferencing, Voice over Internet Protocol (VOIP), and High Definition Television (HDTV) have emerged on the Internet in WMNs [2]. Considering different quality-of-service (QoS) provisioning, one of the solutions is the minimal-cost multicast routing. This presents the problem of finding a tree in a graph from the source to a subset of vertices called terminals such that the total edge cost is minimal. Nevertheless, these days, more and more practical problems, including Very Large Scale Integration (VLSI) layout, network design, etc., can be modeled as multicast routing tree subject to multiple QoS constraints. The challenge of multicast routing subject to multiple QoS constraints is usually known as the multiply constrained multicast routing (MCMR) problem. To the best of our knowledge, finding the minimal-cost multicast routing tree (or a Steiner tree) is Non-Deterministic Polynomial (NP)-hard [3]. In that way, it is also NP-hard to find the minimal-cost multicast routing tree subject to multiple QoS constrains. On one hand, there has been much work involved in deterministic algorithms [4], such as the genetic algorithm and the ant colony algorithm, which could finally find optimal solutions for this problem, while the time complexity grows exponentially with the increase of network nodes. On the other hand, there also has been much work involved in designing heuristic solutions for this problem [5; 6; 7; 8; 9; 10; 11; 12; 13], and they can find multicast trees close to the optimal multicast tree in feasible time, which is more suitable for network multicast use, due to the computing and processing performance of network nodes. Recently, it seems that much work has been turned to focus on approximation algorithms to deal with the multiply constrained multicast routing (MCMR) problem. The authors did research on the Steiner tree problem at the earliest, then put forward the MPH algorithm to deal with it [14]. Based on [PERSON]'s study [15], [PERSON] et al. proposed various polynomial time algorithms for the multiply constrained optimal paths (MCOP) problem [16; 17]. [PERSON] and [PERSON] introduced a novel idea to show how a heuristic method can be used to boost the average performance of an approximation algorithm [18]. [PERSON] presented a Constrained Multicast-Max-Flow-Min-Cost algorithm to maximize the throughput of a multicast tree using network coding, subjected to routing cost constraints [19]. At the same time, the authors did research on the optimal constrained path routing in WMNs in the previous paper [20]; following that, the Fast Minimum Path Cost Heuristic (FMPH) algorithm was put forward to deal with the MCMR problem in WMNs. Recently, [PERSON] and his co-authors proposed the cross-layer protocol to decrease the delay [21; 22; 23; 24; 25] and devised a novel energy-saving algorithm. [PERSON] and his co-authors argued for a ring-based multicast routing topology with support from infrastructure nodes for group communications in WMNs [26], and then developed heuristic algorithms to deal with it. Other excellent research on QoS multicast in wireless networks could be found in this literature [27; 28; 29; 30; 31; 32; 33; 34; 35]. Rather than the previous research model, in this paper, multiply constrained optimal multicast routing (MCOMR) is investigated from the perspective of approximation. As far as we know, [PERSON]'s algorithm is currently the fastest for path establishment in unicast routing with multiple QoS constraints [16], and the MPH algorithm is efficient for multicast routing [14]. However, the solution to the MCOMR problem is rarely found or is found to be inefficient in the existing literature. In this study, a novel approximation algorithm is proposed to achieve a more excellent solution.