# A Novel QoS Provisioning Algorithm for Optimal Multicast Routing in WMNs
## 3 The Proposed NMHA Algorithm
### Analysis of the NMHA Algorithm  
**Theorem 1**. : _NMHA obtains a feasible multicast routing \(\mathbf{T}^{\mathrm{opt}}\) from source \(s\) to destination set \(\mathbf{D}\), which minimizes \(\max_{1\leq i\leq\mathrm{K}}w_{i}^{\mathrm{N}}(\mathbf{T}_{j})\) among all multicast routing trees in \(\mathbf{G}_{\mathrm{K}}^{\mathrm{N}}(\mathbf{V}_{\mathrm{K}}^{\mathrm{N}}, \mathbf{E}_{\mathrm{K}}^{\mathrm{N}},\mathbf{W}_{\mathrm{K}}^{\mathrm{N}},\tau)\). The worst case time complexity of the algorithm is \(O(qnm^{2}\mathbf{r}^{\mathrm{K}-1})\)._  
**Proof of Theorem 1. ** NMHA consists of two major phases. In the first phase, it calculates the value after scaling and rounding for each edge and initializes the data structures (Lines 1-9), the time complexity of which is constant. In the second phase, it computes the optimal multicast routing tree (Lines 10-25), the time complexity of which is a crucial factor. Since it searches \(\mathbf{P}\left(v,\mathrm{D}_{2},\mathrm{D}_{i},...,\mathrm{D}_{\mathrm{K}}\right)\) in lexicographic order for every adjacent node \(v(v\
otin\mathbf{T}_{j-1}^{\mathrm{opt}})\) of node \(d_{j}\in\mathbf{T}_{j-1}^{\mathrm{opt}}\) in the NMHA algorithm (Lines 10-19), and guarantees that \(d_{i}\) is not more than the largest integer \(\tau\), which means that NMHA searches a shortest path in the space of \(\max_{1\leq i\leq\mathrm{K}}w_{i}^{\mathrm{N}}(\mathbf{T}_{j})\), the NMHA obtains a multicast routing tree \(\mathbf{T}^{\mathrm{opt}}\) from source \(s\) to destination set \(\mathbf{D}\) that minimizes \(\max_{1\leq i\leq\mathrm{K}}w_{i}^{\mathrm{N}}(\mathbf{T}_{j})\) among all multicast routing trees in \(\mathbf{G}_{\mathrm{K}}^{\mathrm{N}}\). During the running of NMHA, \(\mathbf{G}_{\mathrm{K}}^{\mathrm{N}}\) have \(\mathrm{O}(n\tau^{\mathrm{k}-1})\) vertices and \(\mathrm{O}(2m\tau^{\mathrm{k}-1}+n\tau^{\mathrm{k}-1})\) edges, which confirm our observation that the space complexity is fairly large. Moreover, \(\mathbf{G}_{\mathrm{K}}^{\mathrm{N}}\) contains a directed edge from \(\mathbf{P}\left(d_{j},\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)\) with length of \(w_{i}\left(d_{j},v\right)\). Therefore, the optimal multicast routing tree \(\mathbf{T}^{\mathrm{opt}}\) found in NMHA minimizes \(\max_{1\leq i\leq\mathrm{K}}w_{i}^{\mathrm{N}}(\mathbf{T}_{j}^{\mathrm{opt}})\) among multicast routing trees in \(\mathbf{G}_{\mathrm{K}}^{\mathrm{N}}\). Since each \(w_{i}\left(e\right)\) is a positive real-value for \(2\leq i\leq\mathrm{K}\), \(e\in\mathbf{E}\), the existence of a directed edge from \(\mathbf{P}\left(d_{j},\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)\) in \(\mathbf{G}_{\mathrm{K}}^{\mathrm{N}}\) implies that \(\mathrm{C}_{i}\leq\mathrm{D}_{i}\) for \(2\leq i\leq\mathrm{K}\), \(e\in\mathbf{E}\). Therefore, the graph \(\mathbf{G}_{\mathrm{K}}^{\mathrm{N}}\) is acyclic. For an acyclic graph, the worst-case time complexity of each running process is (Lines 11-17). As far as we know, the time complexity of the MPH algorithm is \(\mathrm{O}\left(qn^{2}\right)\) (Lines 18). Therefore, the worst case time complexity of NMHA is \(\mathrm{O}(qmn^{2}\tau^{\mathrm{K}-1})\). **Theorem 2. **_To any feasible multicast routing tree \(\mathbf{T}_{j}\) in \(\mathbf{G}\), it is a feasible multicast routing tree in \(\mathbf{G}_{\mathrm{K}}^{\mathrm{N}}\)._  
**Proof of Theorem 2.