# A Guaranteed Approximation Algorithm for QoS Anypath Routing in WMNs
## 3 An An Anypath Routing Approximation Algorithm for QoS
### Analysis of HMAA Algorithm
According to the definition of the variable \(w_{m}\), it can obtain  
\[w_{m}(v_{r+1},P^{*}_{v})=\frac{w_{m}(v_{r+1})}{p(v_{r+1},\mathbf{F}(v_{r+1},P^ {*}_{v}))}+\sum_{u_{j}\in\mathbf{F}(v_{r+1},P^{*}_{v})}\beta(u_{j},P^{*}_{v})w _{m}(u_{j},P^{*}_{v}). \tag{9}\]  
According to the implementation of HMAA algorithm, all of the nodes (including neighbor nodes \(u_{j}\)) on the path \(P^{*}_{v}\) are added to the queue \(\mathrm{P}\) before the node \(v_{r+1}\) joins it. For all nodes with subscripts [1, r], the inequality (8) is true. So, there is  
\[w_{m}(u_{j},P^{*}_{v})\geq\hat{w}(u_{j},P^{*}_{v})=\max_{2\leq i\leq\mathrm{K }}w_{i}(u_{j},P^{*}_{v}),\forall u_{j}\in\mathbf{F}(v_{r+1},P^{*}_{v}). \tag{10}\]  
According to the definition of Formula (2), it can obtain  
\[ \begin{array}{rl}\hat{w}(v_{r+1},P^{*}_{v})&=\max_{2\leq i\leq\mathrm{K}}w_ {i}(v_{r+1},P^{*}_{v})\\ &=\max_{2\leq i\leq\mathrm{K}}\left(\frac{w_{i}(v_{r+1})}{p(v_{r+1},\mathbf{F }(v_{r+1},P^{*}_{v}))}+\sum\limits_{u_{j}\in\mathbf{F}(v_{r+1},P^{*}_{v})} \beta(u_{j},P^{*}_{v})w_{i}(u_{j},P^{*}_{v})\right)\\ &=\max_{2\leq i\leq\mathrm{K}}\left(\frac{w_{i}(v_{r+1})}{p(v_{r+1},\mathbf{ F}(v_{r+1},P^{*}_{v}))}\right)+\max_{2\leq i\leq\mathrm{K}}\left(\sum\limits_{u_{j} \in\mathbf{F}(v_{r+1},P^{*}_{v})}\beta(u_{j},P^{*}_{v})w_{i}(u_{j},P^{*}_{v}) \right)\\ &\leq\frac{w_{m}(v_{r+1})}{p(v_{r+1},\mathbf{F}(v_{r+1},P^{*}_{v}))}+\sum \limits_{u_{j}\in\mathbf{F}(v_{r+1},P^{*}_{v})}\beta(u_{j},P^{*}_{v})\max_{2 \leq i\leq\mathrm{K}}w_{i}(u_{j},P^{*}_{v})\\ \end{array}  \tag{11}\]  
By comparing Equations (9)-(11), it can obtain  
\[\hat{w}(v_{r+1},P^{*}_{v})\leq w_{m}(v_{r+1},P^{*}_{v}). \tag{12}\]  
So, the inequality (4) is true for node \(v\) on the anypath \(P^{*}_{v}\). Since the anypath routing is directed and acyclic, HMAA algorithm indexes all of the nodes in reverse order along the optimal anypath \(P^{*}_{v}\). The index value of \(t\) is 0, and \(v\) is the largest one. Moreover, the index value of each node is larger than that of its forwarding set. The mathematical induction is used to prove that the following inequality holds for any node \(v\) on the optimal path \(P^{opt}_{v}\)  
\[w_{m}(v,P^{opt}_{v})\leq\sum\limits_{i=2}^{\mathrm{K}}w_{i}(v,P^{opt}_{v}). \tag{13}\]  
For any node \(v\) in WMNs, define \(P_{v}^{*}\) as the anypath routing from \(v\) to \(t\) calculated by HMAA, \(P_{v}^{opt}\) as the optimal solution to MCOAP. Theorem 1 indicates that an anypath \(P_{v}^{*}\) from \(v\) to \(t\) is the shortest AAW, so the following inequality holds  
\[w_{m}(v,P_{v}^{*})\leq w_{m}(v,P_{v}^{opt}). \tag{23}\]  
According to the inequalities (4), (22) and (23), it holds  
\[\hat{w}(v,P_{v}^{*})\leq(\operatorname{K}-1)\cdot\hat{w}(v,P_{v}^{opt}). \tag{24}\]  
Replace the node \(v\) in the above inequalities with \(s\), then the HAMA algorithm (Lines 26-29) checks if it is feasible for the first parameter that \(w_{1}(v,P_{s}^{opt})\leq L_{1}\), thus it can obtain  
\[\hat{w}(s,P_{s}^{*})\leq(\operatorname{K}-1)\cdot\hat{w}(s,P_{s}^{opt}),s.t. \ \ w_{1}(v,P_{s}^{opt})\leq L_{1}. \tag{25}\]  
That is, HMAA algorithm finds a K-1 approximate solution to the MCOAP problem, thus Theorem 2 is proven.