# A Novel QoS Provisioning Algorithm for Optimal Multicast Routing in WMNs
## 3 The Proposed NMHA Algorithm
### Analysis of the NMHA Algorithm
** To a feasible multicast routing tree \(\mathbf{T}_{j}\) in \(\mathbf{G}\), it has  
\[w_{i}(\mathbf{T}_{j})=\sum\limits_{e\in\mathbf{T}_{j}}w_{i}(e)\leq\mathrm{L}_ {i} \tag{3}\]  
It implies that  
\[\frac{\sum\limits_{e\in\mathbf{T}_{j}}w_{i}(e)}{\mathrm{L}_{i}}\cdot\beta= \sum\limits_{e\in\mathbf{T}_{j}}\frac{w_{i}(e)}{\mathrm{L}_{i}}\cdot\beta\leq\beta \tag{4}\]  
Since  
\[w_{i}^{\mathrm{N}}(e)=\left\lfloor\frac{w_{i}(e)}{\mathrm{L}_{i}}\cdot\beta \right\rfloor\leq\frac{w_{i}(e)}{\mathrm{L}_{i}}\cdot\beta \tag{5}\]  
and  
\[\beta\leq\lceil\beta\rceil=\tau \tag{6}\]  
Then, it has  
\[ \begin{array}{ll}w_{i}^{\mathrm{N}}(\mathbf{T}_{j})&=\sum\limits_{e\in \mathbf{T}_{j}}w_{i}^{\mathrm{N}}(e)\\ &=\sum\limits_{e\in\mathbf{T}_{j}}\left\lfloor\frac{w_{i}(e)}{\mathrm{L}_{i}} \cdot\beta\right\rfloor\\ &\leq\sum\limits_{e\in\mathbf{T}_{j}}\frac{w_{i}(e)}{\mathrm{L}_{i}}\cdot \beta\end{array}  \tag{7}\]  
According to Equations (4), (6) and (7), it has  
\[w_{i}^{\mathrm{N}}(\mathbf{T}_{j})\leq\tau \tag{8}\]  
Hence, any feasible multicast routing tree \(\mathbf{T}_{j}\) in \(\mathbf{G}\) is a feasible multicast routing tree in \(\mathbf{G}_{\mathrm{K}}^{\mathrm{N}}\). **Theorem 3. **_The NMHA algorithm finds a 2(1 + \(\varepsilon\))(1 - 1/q)-approximation multicast routing tree to MCOMR._  
**Proof of Theorem 3. ** To the optimal multicast routing tree \(\mathbf{T}^{*}\) in \(\mathbf{G}\), it has  
\[w_{i}(\mathbf{T}^{*})\leq\theta^{*}\cdot\mathrm{L}_{i} \tag{9}\]  
\[w_{i}^{\mathrm{N}}(\mathbf{T}^{*})=\sum\limits_{e\in\mathbf{T}^{*}}w_{i}^{ \mathrm{N}}(e)=\sum\limits_{e\in\mathbf{T}^{*}}\left\lfloor\frac{w_{i}(e)}{ \mathrm{L}_{i}}\cdot\beta\right\rfloor \tag{10}\]  
This implies that  
\[ \begin{array}{ll}w_{i}^{\mathrm{N}}(\mathbf{T}^{*})&\leq\sum\limits_{e\in \mathbf{T}^{*}}(\frac{w_{i}(e)}{\mathrm{L}_{i}}\cdot\beta)\\ &=\frac{w_{i}(\mathbf{T}^{*})}{\mathrm{L}_{i}}\cdot\beta\\ &\leq\theta^{*}\cdot\beta\end{array}  \tag{11}\]On the other hand, \(\mathbf{T}^{\mathrm{opt}}\) 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}}\) and \(\mathbf{T}^{*}\) is a feasible multicast routing tree as mentioned in Theorem 1 and in Theorem 2, respectively, then it has  
\[\max_{1\leq i\leq\mathrm{K}}w_{i}^{\mathrm{N}}(\mathbf{T}^{\mathrm{opt}}) \leq\max_{1\leq i\leq\mathrm{K}}w_{i}^{\mathrm{N}}(\mathbf{T}^{*}) \tag{12}\]  
\[ \begin{array}{ll}w_{i}^{\mathrm{N}}(\mathbf{T}^{opt})=\sum\limits_{e\in \mathbf{T}^{\mathrm{opt}}}w_{i}^{\mathrm{N}}(e)&=\sum\limits_{e\in\mathbf{T}^ {\mathrm{opt}}}\left\lfloor\frac{w_{i}(e)}{\mathrm{L}_{i}}\cdot\beta\right\rfloor \\ &\geq\sum\limits_{e\in\mathbf{T}^{\mathrm{opt}}}\left(\frac{w_{i}(e)}{\mathrm{ L}_{i}}\cdot\beta-1\right)\end{array}  \tag{13}\]  
Since \(\mathbf{T}^{\mathrm{opt}}\) have \(|\mathbf{V}|-1\) hops at most, and there are \(|\mathbf{V}|=n\) nodes in \(\mathbf{G}\), it implies that  
\[ \begin{array}{ll}\sum\limits_{e\in\mathbf{T}^{\mathrm{opt}}}\left(\frac{w_ {i}(e)}{\mathrm{L}_{i}}\cdot\beta-1\right)&=\sum\limits_{e\in\mathbf{T}^{ \mathrm{opt}}}\left(\frac{w_{i}(e)}{\mathrm{L}_{i}}\cdot\beta\right)-\sum \limits_{e\in\mathbf{T}^{\mathrm{opt}}}1\\ &\geq\frac{w_{i}(\mathbf{T}^{\mathrm{opt}})}{\mathrm{L}_{i}}\cdot\beta-(n-1) \end{array}