# A Novel QoS Provisioning Algorithm for Optimal Multicast Routing in WMNs
## 2 Preliminaries  
### Problem Formulation  
A wireless communication network with K QoS constraints can be represented by a connected and undirected graph \(\mathbf{G}(\mathbf{V},\mathbf{E}\widetilde{\mathbf{W}},\widetilde{\mathbf{L}})\), where \(|\mathbf{V}|=n\) is the set of vertices, \(|\mathbf{E}|=m\) is the set of edges, \(\widetilde{\mathbf{W}}\) is the set of weights, and \(\widetilde{\mathbf{L}}\) is the set of constraints. Each edge has \(\mathrm{K}(\mathrm{K}\geqslant 2)\) weights, and \(\widetilde{\mathbf{W}}=\left\{w_{i}\left(e_{x}\right)\right\},w_{i}\left(e_{x} \right)\geqslant 0\) is the \(i\)th weight of an edge \(\left(e_{x}\in\mathbf{E},1\leqslant i\leqslant\mathrm{K}\right)\), a positive constant matrix \(\overset{\rightarrow}{\mathbf{L}}=(\mathrm{L}_{1},\mathrm{L}_{2},\ldots,\mathrm{L}_{ \mathrm{K}})\) is the K constraint. Referring to previous related works, the authors have studied the constrained path routing in the literature [20], and then we have the definitions as follows.  
**Definition 1.** MCMR Problem. Consider an undirected graph \(\mathbf{G}(\mathbf{V},\mathbf{E},\overset{\rightarrow}{\mathbf{W}},\overset{ \rightarrow}{\mathbf{L}})\). Let \(s\in\mathbf{V}\) be the source node and \(\mathbf{D}\) be the set of destination nodes, where \(\mathbf{D}=\{d_{k}\}\subseteq\mathbf{V}\), \(s\
otin\mathbf{D}\), \(k=1,2,\ldots q\). Denote \(\mathbf{T}\left(\mathbf{V_{T}},\mathbf{E_{T}}\right)=\sum\limits_{e_{\lambda} \in\mathbf{T}}e_{x}\) as a multicast routing tree from source \(s\) to the set of destination nodes \(\mathbf{D}\) in \(\mathbf{G}\) with \(\mathbf{D}\subseteq\mathbf{V_{T}}\subseteq\mathbf{V}\), \(\mathbf{E_{T}}\subseteq\mathbf{E}\). Denote \(w_{i}\left(\mathbf{T}_{j}\right)=\sum\limits_{c_{\lambda}\in\mathbf{T}_{j}}w_ {i}(e_{x})\), \(2\leq i\leq\) as the sum of the ith weight on edges along multicast tree \(\mathbf{T}_{j}\). The goal is to find a multicast routing tree \(\mathbf{T}_{j}\) from \(s\) to \(\mathbf{D}\), such that \(w_{i}\left(\mathbf{T}_{j}\right)\leq\mathrm{L}_{i}\). We say that MCMR is feasible if it has a feasible solution; otherwise, it is infeasible.  
**Definition 2.** MCMR Problem. It is a feasible multicast routing tree for \(\mathbf{T}_{j}\), where \(w_{i}\left(\mathbf{T}_{j}\right)\leq\mathrm{\theta}_{j}\mathrm{L}_{i}\) for all \(\mathrm{\theta}_{j},\mathrm{L}_{i}\in(0,1]\). The entire feasible multicast routing tree in \(\mathbf{G}(\mathbf{V},\mathbf{E},\overset{\rightarrow}{\mathbf{W}},\mathbf{L})\) is denoted as \(\left\{\mathbf{T}_{j}\right\}\). The goal is to find an optimal multicast routing \(\mathbf{T}^{*}\) among feasible trees \(\left\{\mathbf{T}_{j}\right\}\) in \(\mathbf{G}\) and \(\mathrm{\theta}^{*}=\min\left\{\mathrm{\theta}_{j}\right\}\) such that \(w_{i}\left(\mathbf{T}^{*}\right)\leq\mathrm{\theta}^{*}\mathrm{L}_{i}\). We call \(\mathrm{\theta}^{*}\) the optimal value to MCMR and \(\mathbf{T}^{*}\) an optimal multicast routing tree or an optimal solution to MCMR.  
**Definition 3.** (\(a\)-Approximation algorithm). Let \(a\geq 1\) be a constant. If the algorithm generates a multicast routing tree \(\mathbf{T}^{pt}\) from \(s\) to \(\mathbf{D}\) such that \(w_{i}\left(\mathbf{T}^{\mathrm{opt}}\right)\leq a\mathrm{\theta}^{*}\mathrm{L} _{i}\), \(2\leq i\leq\mathrm{K}\), then \(\mathbf{T}^{opt}\) is called an \(a\)-Approximation to MCMR, and it is called an \(a\)-Approximation algorithm.  
Table 1 lists frequently used notations.