# A Novel QoS Provisioning Algorithm for Optimal Multicast Routing in WMNs
## 2 Preliminaries
### Deterministic Algorithm with Auxiliary Graph  
[PERSON] et al. provided an important methodology for finding the approximate optimal path for constrained unicast routing by constructing an auxiliary graph [16]. It transforms an undirected graph \(\mathbf{G}\) to a directed graph \(\mathbf{G}^{\mathrm{K},\tau}\). Each vertex \(v\in\mathbf{G}\) is associated with \(\left(1+\tau\right)^{\mathrm{K}-1}\) vertices, since each weight has been normalized \(w_{i}\left(e\right)/\mathrm{L}_{i}\). Then, \(\tau=\left[\left(n-1\right)/\varepsilon\right]\) (\(\varepsilon\) is the approximation factor) could be regarded as the maximum integer of all constraints in \(\mathbf{G}^{\mathrm{K},\tau}\). For example, from the source node \(s\) to any node \(u\), \(\mathrm{C}_{i}\in[0,\tau],\forall 2\leq i\leq\mathrm{K}\) is used for recording the \(i\)th weight of path length, and \(\mathbf{P}\left(u,\mathrm{C}_{2},\mathrm{C}_{i},\ldots,\mathrm{C}_{\mathrm{K}}\right)\) for all the K weight of path length. To each undirected edge \(\left(u,v\right)\) in \(\mathbf{G}\), the directed edge in \(\mathbf{G}^{\mathrm{K},\tau}\) is constructed from \(\mathbf{P}\left(u,\mathrm{C}_{2},\mathrm{C}_{i},\ldots,\mathrm{C}_{\mathrm{K}}\right)\) to \(\mathbf{P}\left(v,\mathrm{D}_{2},\mathrm{D}_{i},\ldots,\mathrm{D}_{\mathrm{K}}\right)\), where \(\mathrm{D}_{i}=\mathrm{C}_{i}+w_{i}\left(u,v\right)\), \(\forall\mathrm{C}_{i},\mathrm{D}_{i}\in[0,\tau]\). It is clear that the infeasible paths of the latter \(\mathrm{K}-1\) metrics have been filtered. Therefore, an optimal path in \(\mathbf{G}\) corresponds to an optimal path from \(\mathbf{P}\left(s,0,\ldots,0\right)\) to \(\mathbf{P}(d,\tau,\ldots,\tau)\) in \(\mathbf{G}^{\mathrm{K},\tau}\).  
\begin{table}
\begin{tabular}{c c} \hline \hline \(s\) & the source node \\ \(d_{k}\) & the \(k\)th destination nodes \\ \(\mathbf{D}\) & the set of destination nodes \\ \(m,n\) & the edge and the node number of graph \(\mathbf{G}\), respectively \\ \(q\) & the number of terminal nodes \\ \(w_{i}(e_{x})\) & \(i\)th link weight of edge \(e_{x}\) \\ K & the number of Quality-of-Service (QoS) requirements \\ \(\mathbf{W}\) & the set of weights of the edges \\ \(\overset{\rightarrow}{\mathbf{L}}\) & the set of constrains \\ \(\mathrm{L}_{i}\) & \(i\)th QoS requirement \\ \(\mathbf{T}\) & the multicast tree with all nodes in the set of destination nodes \(\mathbf{D}\) \\ \(\mathbf{T}_{j}\) & the Steiner tree with \(j\) destination nodes in the set \(\mathbf{D}\) \\ \(\mathbf{V_{T}},\mathbf{E_{T}}\) & all the nodes and the edges of the multicast trees \(\mathbf{T}\), respectively \\ \(\mathbf{T^{*}},\mathbf{T}^{opt}\) & the optimal and the approximate optimal multicast routing tree, respectively \\ \(w\left(d_{k},\mathbf{T}_{j-1}\right)\) & the total weights from \(d_{k}\) to \(\mathbf{T}_{j-1}\) \\ \(\mathrm{PATH}\left(d_{k},\mathbf{T}_{j-1}\right)\) & the short path connected node \(d_{k}\) to the \(\mathbf{T}_{j-1}\) \\ \(\mathrm{C}_{i},\mathrm{D}_{i}\) & the \(i\)th weight of path length from source \(s\) to any node \(u\) in \(\mathbf{G}^{\mathrm{K},\tau}\) \\ \(\mathbf{P}\left(u,\mathrm{C}_{i},\ldots,\mathrm{C}_{\mathrm{K}}\right)\) & all the K weight of path length from source \(s\) to any node \(u\) in \(\mathbf{G}^{\mathrm{K},\tau}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Frequently used notations.  
The basic idea behind [PERSON]'s algorithm is to replace time with space. As far as we know, [PERSON]'s approximation scheme with the time complexity of \(\mathrm{O}(m\tau^{\mathrm{K}-1})\) is currently the fastest way to calculate a path with multiple QoS constraints. As can be observed from the examples, using [PERSON]'s deterministic algorithm with an auxiliary graph, it is feasible and meaningful to seek an effective and efficient algorithm to approximate optimal multicast routing with multiple constraints.